Esta tarea consiste en comentar brevemente qué tipos de problemas no podrían ser resueltos por medio del algoritmo A*, y la verdad es que veo difícil completar el objetivo satisfactoriamente.
Por un lado, a duras penas he entendido el desarrollo del algoritmo, sí los objetivos, pero creo que me falta la base matemática mínima para comprender los procedimientos y la terminología utilizada. Por el otro, en la web hay muy poca información en castellano, y si ya me cuesta entender las explicaciones sobre esto en castellano, pues en inglés… Además, tampoco encuentro en internet, de forma explícita, «carencias» o «limitaciones» del uso de este algoritmo. Esto es lo máximo a lo que he llegado:
Dentro del campo de la Inteligencia Artificial, el algoritmo A es uno de los mejores y más conocidos métodos heurísticos de búsqueda. Un algoritmo de búsqueda de tipo heurístico sirve para encontrar el camino entre dos puntos (pathfinder), pero puede suceder que, en ocasiones, el camino elegido no sea el óptimo, por ejemplo, que elija el más largo o el de más coste. Ahí es donde está la ventaja del algoritmo A*, ya que también tiene en cuenta ese factor.
Buscando en internet sobre las limitaciones de este método de búsqueda he encontrado un trabajo del departamento de Ciencias Computacionales de la Universidad de New Hampshire titulado: When does Weighted A* Fail? Parece que voy bien, ahora solo hay que saber qué diferencia hay entre A* y Weighted A*.
Con ese objetivo, he dado con un artículo en la revista Artificial Intelligence Weighted A∗ search – unifying view and application sobre lo que entiendo que es una variante de este método de búsqueda: «Weighted A* search», donde no sé cómo traducir «Weighted», ¿quizás «Búsqueda ponderada A*? De la lectura del Abstract, ya que no me siento capaz de ir más allá, entiendo que es una variante que sirve para dar más velocidad a la búsqueda, y para ello le da un mayor peso a la parte heurística del método. Es una revisión sobre los trabajos realizados anteriormente, con la aportación propia de los autores, en orden a unificar criterios de aplicación, por lo que supongo que puede hacer valoraciones de las limitaciones del método, pero como digo, no me siento capaz de leer el artículo completo.
Así que volviendo a New Hampshire, y quedándome, de nuevo, en el Abstract, éste empieza diciendo que el Weighted A* es el algoritmo más popular y satisfactorio de la búsqueda heurística, a pesar de que no esté garantizado que aumentar el peso de la parte heurística aumente su velocidad; que está ampliamente asumido que aumentar ese peso da lugar a búsquedas más rápidas, y que el algoritmo voraz, que se guía únicamente de forma heurística, sería el más rápido de todos. Sin embargo, los autores del artículo tratan de demostrar que en algunos dominios, incrementar el peso disminuye la velocidad de búsqueda, y exponen en qué condiciones el algoritmo voraz pueden ser más rápido que el A*.
También he encontrado limitaciones en la aplicación de este método en este blog sobre juegos: https://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php?print=1
Parece lógico que una de las aplicaciones de este algoritmo sean los juegos, ya que en ellos siempre hay elementos que se mueven, un destino al que hay que llegar y obstáculos que hay que sortear. El artículo explica las modificaciones que hay que hacer en el algoritmo para conseguir movimientos más realistas o naturales que el de zigzag, que es el resultado directo de aplicar el A* estándar. Parece ser que en determinados casos este método falla y su corrección depende del tipo de juego, y puede que haya que aplicar algún método de búsqueda más lento, dividir el mapa en regiones más pequeñas, hacer una precomputación si es posible, etc.
Para terminar, la wikipedia considera que el espacio requerido por A* para ser ejecutado es su mayor problema, ya que la cantidad de memoria que requiere es exponencial con respecto al tamaño del problema.
Bibliografía
- Wilt, C. and Ruml, W. When does Weighted A* Fail? Dept. of Computer Sciences, University of New Hampshire.
- Ebendt, R., Drechsler, R. Weighted A∗ search – unifying view and application (2009). Artificial Intelligence 173, 1310-1342.
- Pinter, M. Toward More Realistic Pathfinding. Gamasutra, The Art & Bussiness of Making Games (última visita 29/04/2020)
- Wikipedia.
Zur eta Lur 