BUSCANDO EL RUMBO: EL ALGORITMO A* 👀💻

 

El Algoritmo A* es un algoritmo de búsqueda  que se desarrolló en 1968, el cual  encuentra la ruta más corta entre dos puntos. Su diseño inicial le permitía resolver problemas transversales de grafos; posteriormente, se usó para aplicaciones de búsqueda de caminos en videojuegos, inteligencia artificial y robótica. 

 

Este algoritmo presenta un diseño que le permite identificar una ruta óptima desde una posición inicial dada hasta una posición de destino dada y combina la búsqueda de costo uniforme (del Algoritmo Dijkstra) y los algoritmos de búsqueda codiciosos; si lo comparamos con otros algoritmos, presenta un tiempo de ejecución más breve, de fácil implementación y una  alta eficiencia.

Puedes ahondar en su funcionamiento visitando la página: https://www.lanshor.com/pathfinding-a-estrella/

Es un algoritmo informado, utiliza una heurística (información acerca de la posibilidad de que un nodo específico sea mejor para intentar la próxima elección que cualquier otro nodo) lo que marca una tendencia hacia la meta reduciendo de manera significativa el espacio de  búsqueda; esta heurística es admisible, es decir, no sobreestima la distancia sobrante entre el nodo presente y el nodo de la meta.

Función heurística de A*

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

La función se encuentra compuesta por: 

g(n) : es el costo de las movidas realizadas. 

h(n) : es la función heurística. Representa el costo estimado del mejor camino.

Ya que la g(n) nos da el coste del camino desde el nodo inicio al nodo n, y la h(n) el coste estimado del camino más barato desde n al objetivo, tenemos: f(n)= coste más barato estimado de la solución a través de n.

                                 Créditos de imagen: https://www.lanshor.com/pathfinding-a-estrella/

¿Qué tipos de problemas no podrían ser resueltos por medio del algoritmo A*?

v -  El algoritmo A* es útil en ambientes estáticos, pero no en un sistema cambiante,  donde las condiciones externas  sean alteradas por factores que no controlamos.

v -  La calidad de A* depende de la calidad en la heurística estimadora h (n), si se acerca bastante al verdadero costo del camino restante, su eficiencia será alta, pero si es muy bajo, su eficiencia disminuye.

v  - No puede resolver problemas en los que la dimensión del espacio de búsqueda sea muy grande.

v - En Pathfinding, (planificación de una ruta), el algoritmo tendría dificultades cuando el problema contenga múltiples agentes, en los que el número de nodos a expandir sean exponenciales en longitud de la solución; lo que hace que se quede sin espacio antes de que se quede sin tiempo.

v  - Problemas con más de una solución correcta.

v -  Problemas de consecuencia incierta: no es posible planificar con certeza pues no se sabe que ocurrirá luego del siguiente movimiento, según García (2009).

v  - Los algoritmos de búsqueda heurística de agente único no pueden ser utilizados en aplicaciones en tiempo real, debido a su costo computacional  y el hecho de que no pueden comprometerse a una acción antes de que se conozca su resultado final. Korf (1990) 

      Por ultimo, elucubrando, problemas en donde el algoritmo debe crear rutas y no encontrarlas.  

Fuentes:

Lasso-Cardona, Franco-Ocampo, Agudelo-Acevedo.  (2020). Algoritmos voraces y heurísticos: un enfoque en el problema de la ruta mínima. INGE CUC, 16(2), 67–85.

Daniel García López (2009). Curso Inteligencia Artificial. Unidad III: Solución de problemas por búsqueda

Tomás, V., Núñez, F., Andrade, E. Análisis de algoritmos de búsqueda en espacio de estados. Ciencias Huasteca Boletín científico de la escuela superior de Hueutla.

DOI: https://10.29057/ESH.V3I5.1089

Korf, R. (1990). Real-Time Heuristic Search.  Artificial Intelligence, 42(2-3), 189-211

DOI: https://10.1016/0004-3702(90)90054-4

Algoritmo A*. Instituto Tecnológico de Nuevo Laredo

http://www.itnuevolaredo.edu.mx/takeyas/libroisc/03.-ConceptosAlgoritmos.pdf

https://revistascientificas.cuc.edu.co/ingecuc/article/download/2752/3531?inline=1