Los algoritmos de búsqueda heurística incremental combinan la búsqueda tanto incremental como heurística para acelerar las búsquedas de secuencias de problemas de búsqueda similares, lo cual es importante en dominios que solo 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 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 desinformados. [3] Los problemas de búsqueda resultantes, a veces denominados problemas de planificación de rutas dinámicas, 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 borde, el vértice inicial o los vértices de meta 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 que estén 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 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 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 rutas de costo mínimo, IEEE Trans. Syst. 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. Networks 14, 275–323, 1984.
- ^ X. Sun y S. Koenig. El algoritmo de búsqueda A * que ahorra márgenes: 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 conjunta internacional sobre agentes autónomos y sistemas multiagente (AAMAS), 469-476, 2008.
- ^ S. Koenig, M. Likhachev y D. Furcy. Planificación de por vida A *. Inteligencia artificial, 155, (1-2), 93-146, 2004.
- ^ 6. A. Stentz. El algoritmo Focussed D * para 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 la navegación en terreno desconocido. Transactions on Robotics, 21, (3), 354-363, 2005.