Búsqueda A*: cómo rodea obstáculos un robot
A* explora el mapa probando siempre primero la casilla más prometedora, usando el coste hasta ahora más una estimación del coste que falta.
The robot repeats this loop many times a second. Tap a step to pause on it.
Imagina el mapa como una cuadrícula. A* guarda una lista de casillas por probar. Para cada una suma la distancia recorrida hasta ahora a una estimación de la distancia que falta, y expande siempre la de menor total.
Así se dirige a la meta sin olvidar el coste de la ruta hasta ahora, encuentra un camino corto y evita perder tiempo buscando lejos de la meta.
Un robot halla una ruta corta y segura entre obstáculos, lo bastante rápido para replanificar si algo se mueve.
Probar todas las rutas tardaría demasiado, y elegirlas al azar puede dar rodeos largos o callejones sin salida.
Necesita un mapa y una buena estimación de coste. En espacios enormes o cambiantes hacen falta métodos más rápidos o ligeros.
¿Qué usa A* para elegir la siguiente casilla?