Buscar un camino: una IA que no aprende nada
Cómo busca un camino una IA que no aprende: anchura, profundidad, coste uniforme, voraz y A*, paso a paso en una cuadrícula. Curso de IA, 0.5.

Curso de IA › Nivel 0 — Cómo ve el mundo una máquina parte 5 de 5
No toda la inteligencia artificial aprende de datos. Una parte, de las más antiguas, resuelve problemas buscando: prueba caminos posibles en un orden pensado para encontrar pronto el bueno, como quien busca la salida de un laberinto (History of artificial intelligence, en la Wikipedia en inglés). Uno de los algoritmos más usados de esa familia, A*, lo publicaron Peter Hart, Nils Nilsson y Bertram Raphael en 1968, para que un robot, Shakey, planificara por dónde moverse (A* search algorithm, en la Wikipedia en inglés). Y no aprende nada: todo lo que sabe se lo ha dicho una persona.
Toca esto primero
Abre la herramienta Búsqueda con una pared en esquina. El triángulo es el inicio, la bandera es la meta y las casillas oscuras son paredes. El algoritmo elegido es A*. Pulsa Play y mira cómo se pinta la cuadrícula: en azul claro, las casillas que ya ha mirado; en naranja, las que ha descubierto y tiene pendientes. Al terminar, el camino sale en azul, y debajo: «Camino de 18 pasos y coste 18, tras expandir 62 casillas».
Ahora cambia Algoritmo a Voraz, o abre la misma esquina con el voraz, y pulsa Play otra vez. Va derecho hacia la meta, se mete en el rincón de la esquina, choca con la pared y tiene que rodearla por abajo: «Camino de 20 pasos y coste 20, tras expandir 31 casillas». Ha mirado la mitad de casillas, pero su camino es más largo.
Debajo de la cuadrícula, la tabla Los cinco sobre esta misma cuadrícula compara todos los algoritmos a la vez, sin que tengas que ejecutarlos uno a uno:
| Algoritmo | Expandidas | Pasos | Coste |
|---|---|---|---|
| Anchura (BFS) | 103 | 18 | 18 |
| Profundidad (DFS) | 21 | 20 | 20 |
| Coste uniforme | 103 | 18 | 18 |
| Voraz | 31 | 20 | 20 |
| A* | 62 | 18 | 18 |
Qué acaba de pasar
Para un programa, la cuadrícula es un conjunto de estados (cada casilla) y de acciones (moverse a una casilla vecina, arriba, abajo, a la izquierda o a la derecha). Cada movimiento cuesta 1, salvo entrar en una casilla de barro, que cuesta 5. Buscar un camino es decidir en qué orden se miran las casillas hasta llegar a la meta.
Con la barra que hay encima de la cuadrícula se pintan, además de paredes, otras casillas. Cada botón de la barra va en el mismo orden que su casilla, debajo:
| Casilla | Qué hace | Cómo la trata cada algoritmo |
|---|---|---|
| Inicio (triángulo) y meta (bandera) | De dónde sale y adónde tiene que llegar | Igual en todos |
| Pared (gris oscuro) | No se puede pasar | Todos la rodean |
| Barro (marrón) | Se puede cruzar, pero entrar cuesta 5 en vez de 1 | Anchura, profundidad y voraz no miran el coste y lo cruzan como cualquier otra casilla; coste uniforme y A* lo rodean si el rodeo sale más barato |
| Dirección única (flecha) | Solo se sale de ella hacia donde apunta la flecha | Todos la respetan |
| Portal (morado, van por parejas) | Quien entra por uno sale por su pareja | Todos pueden usarlo; lo que cambia con él lo verás en el último ejercicio |
Los cinco algoritmos hacen lo mismo una y otra vez: sacan una casilla de las pendientes, la expanden (miran sus vecinas) y apuntan las vecinas nuevas como pendientes. A esa lista de pendientes se la llama frontera. Lo único que cambia de uno a otro es qué casilla de la frontera sacan primero:
- Anchura (breadth-first search, BFS) saca la más antigua. Avanza en ondas, todas las casillas a un paso, luego a dos… Encuentra el camino con menos pasos, pero mira casi todo: 103 casillas.
- Profundidad (depth-first search, DFS) saca la más nueva. Se mete por un pasillo hasta el fondo antes de probar otro. Mira poco, pero el primer camino que encuentra no tiene por qué ser el mejor.
- Coste uniforme saca la que menos ha costado alcanzar desde el inicio. Sin barro, es lo mismo que anchura; con barro, prefiere dar un rodeo a cruzarlo.
- Voraz saca la que parece más cerca de la meta. Para saberlo usa una heurística, una estimación rápida: los pasos en horizontal y en vertical que faltarían si no hubiera paredes. Se llama distancia Manhattan por las calles en cuadrícula de ese distrito de Nueva York, donde para ir de un sitio a otro solo se puede avanzar a lo largo o a lo ancho. Por eso se mete en el rincón: desde dentro, la meta «parece» cerca.
- A* suma las dos cosas: lo que ha costado llegar a una casilla y lo que parece faltar desde ella. La herramienta lo escribe como g + h: g, lo gastado; h, lo que estima la heurística.
Que A* encuentre el camino más barato depende de una condición: que la heurística no exagere nunca lo que falta. Contar los pasos como si no hubiera paredes no exagera nunca, porque una pared solo puede alargar el camino, nunca acortarlo. Con eso, A* llega al mismo coste que coste uniforme, 18, mirando 62 casillas en vez de 103.
El deslizador Peso de la heurística multiplica h y deja ver qué pasa cuando se confía más en la estimación. En la esquina, A* con peso 1 mira 62 casillas y encuentra el camino de coste 18; con peso 2, 46 casillas y coste 20; con peso 5, 33 casillas y coste 20, casi lo mismo que el voraz. Cuanto más pesa la estimación, menos mira y menos garantiza.
Nota
El peso multiplica la estimación en la fórmula con la que A* elige la siguiente casilla. Una casilla a la que ha costado llegar 6 y a la que, según la estimación, le faltan 8, vale 6 + 8 = 14 con peso 1, y 6 + 2 × 8 = 22 con peso 2: cuanto más pesa, más cuenta lo que falta frente a lo gastado. En la esquina:
| Peso | Qué compara A* | Casillas expandidas | Coste del camino |
|---|---|---|---|
| 1 | g + h | 62 | 18 |
| 2 | g + 2 × h | 46 | 20 |
| 5 | g + 5 × h | 33 | 20 |
| (voraz) | solo h | 31 | 20 |
Nada de esto ha aprendido de ningún dato. En Qué es un modelo, la recta salía de los puntos. Aquí, lo que hace lista a la búsqueda es la heurística, y la ha escrito una persona que sabía algo del problema: que las paredes nunca acortan un camino.
El error típico
Podrías pensar que lo más inteligente sería ir siempre hacia la meta. Es lo que hace el voraz, y en la esquina lo lleva a meterse en un rincón sin salida y a dar un camino 2 pasos más largo. Mirar pocas casillas no basta para encontrar el mejor camino.
Pasa lo mismo con los pasos y el coste. Abre el barro en medio, que también está en Ejemplos como Barro en medio (menos pasos no es más barato), y cambia de algoritmo: anchura y voraz cruzan el barro en línea recta, 11 pasos que cuestan 51; coste uniforme y A* lo rodean, 17 pasos que cuestan 17.
Pruébalo tú mismo
- Abre la herramienta Búsqueda con el laberinto. Antes de mirar la tabla, apuesta qué algoritmo dará el camino más largo y cuál mirará menos casillas. Compruébalo.
- Vuelve a la esquina y mueve la meta (con la bandera de la barra que hay encima de la cuadrícula) dentro del rincón, junto a la pared. ¿Sigue equivocándose el voraz?
Ponte a prueba
Abre el barro con A* y sube poco a poco el Peso de la heurística. ¿A partir de qué peso deja A* de rodear el barro y lo cruza?
Peso: ___
Mira la columna «Coste» de A* en la tabla: rodeando cuesta 17; cruzando, 51.
Ver la respuesta
Respuesta: 4.
Con peso 3, A* todavía rodea el barro: 17 pasos que cuestan 17. Con peso 4 lo cruza en línea recta, 11 pasos que cuestan 51, igual que el voraz. Cuanto más pesa la distancia que falta, menos le importa lo que ya lleva gastado, y el barro solo se nota en lo gastado. Con peso 4, acercarse a la meta pesa más que el barro que hay que pisar.
Ponte a prueba
En la pared en esquina, pon el peso de A* en 3. ¿Cuántas casillas expande y cuánto cuesta su camino?
Expande ___ casillas, y su camino cuesta ___.
Cambia el Peso de la heurística y mira la fila de A* en la tabla.
Ver la respuesta
Respuestas: 36 y 20.
Son menos casillas que con peso 2 (46) y el mismo camino de coste 20, que no es el más barato (18). En la esquina, A* ya deja de dar el más barato con peso 2; a partir de ahí, subir el peso solo le ahorra trabajo.
Ponte a prueba
Una casilla está a 5 pasos del inicio (g = 5) y, contando sin paredes, a 7 de la meta (h = 7). Con peso 2, A* le da una f de ___. El voraz, en cambio, solo mira [g / h / g + h].
Ver la respuesta
Respuestas: 19 y h.
A* con peso 2 calcula g + 2 × h = 5 + 2 × 7 = 19. El voraz solo mira h, lo que falta, y no le importa lo que ha costado llegar: por eso se mete en el rincón de la esquina.
Ponte a prueba
Abre el portal: quien entra por un portal sale por su pareja. ¿Por qué A* ya no encuentra el camino más barato?
- Porque entrar en un portal cuesta más que una casilla normal.
- Porque el portal acorta el camino, y contar los pasos sin paredes ya puede exagerar lo que falta.
- Porque A* no usa los portales: no sabe que existen.
Ver la respuesta
La respuesta es la B.
El portal cuesta 1, como cualquier casilla, y todos los algoritmos lo usan. Lo que falla es la condición que pedía A*: que la heurística no exagere nunca. Contar los pasos como si no hubiera paredes nunca exageraba, porque una pared solo alarga el camino. Un portal lo acorta: desde cerca de un portal, la meta puede estar a menos pasos de los que cuenta la heurística, y A* deja de mirar caminos que eran mejores.
Si quieres más
- Jugar contra una máquina: minimax y la poda alfa-beta, del mismo curso: la otra búsqueda clásica, la de los juegos de dos jugadores, en tres en raya y Conecta 4, con la pestaña Juego de la misma herramienta.
- Introduction to the A* Algorithm, de Red Blob Games, en inglés: cuatro de estos algoritmos (todos menos profundidad), con dibujos interactivos y su código, para quien quiera programarlos.
- A* search algorithm, en la Wikipedia en inglés: la historia, desde el robot Shakey, y por qué la heurística no debe exagerar. Exige algo más de matemáticas.
- Aprender por recompensa, del mismo curso: la misma cuadrícula, cuando el agente no conoce el mapa y aprende de premios y castigos.
- Anatomía de un agente, más adelante en el curso: un agente también decide qué paso dar después, aunque sus opciones no quepan en una cuadrícula.
«Buscar un camino: una IA que no aprende nada», de Ramón Invarato en jarroba.com, con licencia Creative Commons Reconocimiento-NoComercial-CompartirIgual 3.0. Obra registrada en Safe Creative.

Te puede interesar
Qué es un modelo (y por qué una recta ya cuenta como uno)
Qué es un modelo, entrenar y predecir, con una recta que ajustas arrastrando puntos. Y por qué un modelo no entiende sus datos. Curso de IA, 0.4.
Cuando un bit se corrompe, y cómo arreglarlo sin saber cuál es
Cómo un ordenador encuentra y arregla un bit estropeado sin saber cuál es: el código de Hamming, sus límites y SECDED. Curso de IA, 0.3.






Deja un comentario