Algoritmo de búsqueda
Los algoritmos de búsqueda heurística incremental combinan búsqueda incremental y heurística para acelerar las búsquedas de secuencias de problemas de búsqueda similares, lo cual es importante en dominios que sólo se conocen de forma incompleta o que cambian dinámicamente. [1] La búsqueda incremental se ha estudiado al menos desde finales 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 finales de la década de 1960.
Los algoritmos de búsqueda heurística, a menudo basados en A* , utilizan 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 gráficos en los que las rutas deben encontrarse repetidamente porque la topología del gráfico, 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ístico, es decir, distancia aproximada al objetivo) de la búsqueda anterior durante la búsqueda actual para hacerlos más informados (ejemplo: Adaptativo Generalizado A* [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 una transformación del árbol de búsqueda A* de la búsqueda anterior en el árbol de búsqueda A* para el búsqueda actual (ejemplos: Lifelong Planning A* , [7] D* , [8] D* Lite [9] ).
Las tres clases de algoritmos de búsqueda heurística incremental se diferencian 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 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. Redes 14, 275–323, 1984.
- ^ P. Hart, N. Nilsson y B. Raphael, Una base formal para la determinación heurística de rutas de costo mínimo, IEEE Trans. Sistema. Ciencia y Cibernética, SSC-4(2), 100-107, 1968.
- ^ N. Deo y C. Pang. Algoritmos de ruta más corta: taxonomía y anotación. Redes 14, 275–323, 1984.
- ^ X. Sun y S. Koenig. El algoritmo de búsqueda A* que ahorra margen: un estudio de viabilidad. En Actas de la Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI), 2391-2397, 2007.
- ^ X. Sun, S. Koenig y W. Yeoh. Adaptativo generalizado A*. En Actas de la Conferencia Internacional Conjunta sobre Agentes Autónomos y Sistemas Multiagente (AAMAS), 469-476, 2008.
- ^ S. Koenig, M. Likhachev y D. Furcy. Planificación permanente 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. Transacciones sobre Robótica, 21, (3), 354-363, 2005.
enlaces externos
- La página de Maxim Likhachev
- La página web de Sven Koenig
- Página web de Anthony Stentz.
