Algoritmo de búsqueda
Los algoritmos de búsqueda heurística incremental combinan tanto la búsqueda incremental como la heurística para acelerar las búsquedas de secuencias de problemas de búsqueda similares, lo que es importante en dominios que solo se conocen de manera incompleta o cambian dinámicamente. [1] La búsqueda incremental se ha estudiado al menos desde fines de la década de 1960. Los algoritmos de búsqueda incremental reutilizan información de búsquedas anteriores para acelerar la búsqueda actual y resolver problemas de búsqueda potencialmente mucho más rápido que resolverlos repetidamente desde cero. [2] De manera similar, la búsqueda heurística también se ha estudiado al menos desde fines de la década de 1960.
Los algoritmos de búsqueda heurística, a menudo basados en A* , utilizan el conocimiento heurístico en forma de aproximaciones de las distancias objetivo para enfocar la búsqueda y resolver problemas de búsqueda potencialmente mucho más rápido que los algoritmos de búsqueda no informados. [3] Los problemas de búsqueda resultantes, a veces llamados problemas de planificación dinámica de rutas, son problemas de búsqueda de grafos en los que las rutas deben encontrarse repetidamente porque la topología del grafo, sus costos de aristas, el vértice inicial o los vértices objetivo cambian con el tiempo. [4]
Hasta ahora, se han desarrollado tres clases principales de algoritmos de búsqueda heurística incremental:
- La primera clase reinicia A* en el punto donde su búsqueda actual se desvía de la anterior (ejemplo: Fringe Saving A* [5] ).
- La segunda clase actualiza los valores h (heurísticos, es decir, distancia aproximada al objetivo) de la búsqueda anterior durante la búsqueda actual para hacerlos más informados (ejemplo: A* adaptativo generalizado [6] ).
- La tercera clase actualiza los valores g (distancia desde el inicio) de la búsqueda anterior durante la búsqueda actual para corregirlos cuando sea necesario, lo que puede interpretarse como la transformación del árbol de búsqueda A* de la búsqueda anterior en el árbol de búsqueda A* de la búsqueda actual (ejemplos: Lifelong Planning A* , [7] D* , [8] D* Lite [9] ).
Las tres clases de algoritmos de búsqueda heurística incremental son diferentes de otros algoritmos de replanificación, como la planificación por analogía, en que la calidad de su plan no se deteriora con el número de episodios de replanificación.
Aplicaciones
La búsqueda heurística incremental se ha utilizado ampliamente en robótica , donde un mayor número de sistemas de planificación de rutas se basan en D* (normalmente los sistemas anteriores) o D* Lite (sistemas actuales), dos algoritmos de búsqueda heurística incremental diferentes.
Referencias
- ^ S. Koenig, M. Likhachev, Y. Liu y D. Furcy. Búsqueda heurística incremental en inteligencia artificial. Revista de Inteligencia Artificial, 25(2), 99-112, 2004.
- ^ N. Deo y C. Pang. Algoritmos de ruta más corta: taxonomía y anotación. Networks 14, 275–323, 1984.
- ^ P. Hart, N. Nilsson y B. Raphael, Una base formal para la determinación heurística de trayectorias de costo mínimo, IEEE Trans. Syst. Science and Cybernetics, SSC-4(2), 100-107, 1968.
- ^ N. Deo y C. Pang. Algoritmos de ruta más corta: taxonomía y anotación. Networks 14, 275–323, 1984.
- ^ X. Sun y S. Koenig. El algoritmo de búsqueda A* que ahorra espacio: un estudio de viabilidad. En Actas de la Conferencia conjunta internacional sobre inteligencia artificial (IJCAI), 2391-2397, 2007.
- ^ X. Sun, S. Koenig y W. Yeoh. A* adaptativo generalizado. En Actas de la Conferencia conjunta internacional sobre agentes autónomos y sistemas multiagente (AAMAS), 469-476, 2008.
- ^ S. Koenig, M. Likhachev y D. Furcy. Planificación de la vida A*. Inteligencia artificial, 155, (1-2), 93-146, 2004.
- ^ 6. A. Stentz. El algoritmo D* enfocado para la replanificación en tiempo real. Actas de la Conferencia conjunta internacional sobre inteligencia artificial, 1652-1659, 1995.
- ^ S. Koenig y M. Likhachev. Replanificación rápida para navegación en terreno desconocido. Transactions on Robotics, 21, (3), 354-363, 2005.
Enlaces externos
- La página de Maxim Likhachev
- Página web de Sven Koenig
- Página web de Anthony Stentz
