¿Qué es el Algoritmo A*? Ventajas y desventajas

El algoritmo A* (pronunciado como “A estrella” o “A asterisco”) es un algoritmo de búsqueda en grafos diseñado para buscar rutas de navegación autónomas. Fue propuesto por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael para encontrar el camino óptimo entre un origen y un destino.

Para resolver el problema, el espacio se divide en una red teselada en la que el centro de cada celda constituye lo que en teoría de grafos se conoce como un nodo. El algoritmo trata entonces de encontrar la ruta que conlleva “menor coste” entre el nodo origen y el nodo destino. Para ello, utiliza una función de evaluación que determina la probabilidad de que los distintos nodos de la red pertenezcan al camino óptimo. Al tratarse de una búsqueda informada – el algoritmo informa de la probabilidad de que cada celda se encuentre en la ruta de menor coste-, se dice que la función es heurística. Pero para que el algoritmo sea potente no solo debe tener en cuenta el valor heurístico de los nodos, sino también el coste del recorrido.

Así, los nodos de la red quedan etiquetados por dos funciones, una que indica la distancia del nodo en evaluación al nodo origen, y otra que calcula la distancia del nodo en evaluación al nodo objetivo. La función final a evaluar es la suma de las dos anteriores:

f(n) = g(n) + h(n)

Donde n es el número del nodo, g(n) es la función que indica la distancia recorrida (del nodo origen al nodo n) y h(n) es la función que indica la distancia que falta por recorrer (del nodo n al nodo destino). 

Se dice que h(n) es una función heurística porque sobre ella se aplica la condición de heurística admisible: h(n) nunca debe ser mayor que la distancia real entre el nodo origen y el objetivo. En el caso contrario, podría encontrarse una solución, pero no sería la óptima. 

El algoritmo A* va explorando los nodos y calculando la función f(n), conocida como función de mérito. Cuanto menor sea f(n), más probable será que el camino más corto atraviese ese nodo. 

Este es el algoritmo en el que se basan muchos videojuegos. Sin embargo, a pesar de que garantiza minimizar el número de nodos explorados, la velocidad de ejecución depende mucho de la función heurística h(n) utilizada. Cuando esta es muy compleja, el proceso se vuelve muy lento. Las funciones heurísticas más utilizadas son tres: la distancia Manhattan, la distancia diagonal y la distancia euclídea. Puedes ver cómo varía el camino en función de la distancia escogida como heurístico en la siguiente figura: 

 

 

Camino óptimo entre el nodo origen y el nodo destino para la distancia Manhattan (arriba), diagonal (centro) y euclídea (abajo). Créditos: Stanford CS Theory.

Es importante notar que, en algunas ocasiones, no estaremos tan interesadas en encontrar la distancia más corta como en encontrar una distancia lo suficientemente corta con el mayor ahorro de coste computacional.

En otro tipo de situaciones, como por ejemplo cuando queremos programar un robot para que se desplace por un terreno desconocido, el algoritmo A* resulta ineficaz, puesto que una vez definida la red de nodos, esta no se modifica. En estos casos es necesario implementar un algoritmo capaz de identificar obstáculos que irán apareciendo según avance la búsqueda en la red. Una posible solución sería el algoritmo D*. 

 

NOTA: tengo una pregunta para el profe, ¿es este el tipo de algoritmos que tiene implementada mi Conga? Porque la pobre se pega cada trastazo...

 

Si quieres saber más…

Heuristics - Stanford CS Theory http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Performance evaluation of pathfinding algorithms. Harinder Kaur Sidhu. Master thesis. University of Windsor. 2019