En informática , la búsqueda de puntos de salto (JPS) es una optimización del algoritmo de búsqueda A * para cuadrículas de costo uniforme. Reduce las simetrías en el procedimiento de búsqueda mediante la poda de gráficos, [1] eliminando ciertos nodos en la cuadrícula en base a suposiciones que se pueden hacer sobre los vecinos del nodo actual, siempre que se cumplan ciertas condiciones relacionadas con la cuadrícula. Como resultado, el algoritmo puede considerar largos "saltos" a lo largo de líneas rectas (horizontales, verticales y diagonales) en la cuadrícula, en lugar de los pequeños pasos de una posición de cuadrícula a la siguiente que considera A * ordinario. [2]
La búsqueda de puntos de salto conserva la optimización de A *, al tiempo que reduce potencialmente su tiempo de ejecución en un orden de magnitud. [1]
Historia
La publicación original de Harabor y Grastien proporciona algoritmos para la poda de vecinos y la identificación de sucesores. [1] El algoritmo original para la poda de vecinos permitía que ocurriera el corte de esquinas, lo que significaba que el algoritmo solo podía usarse para agentes en movimiento con ancho cero, limitando su aplicación a agentes de la vida real (por ejemplo, robótica) o simulaciones (por ejemplo, muchos juegos ).
Los autores presentaron reglas de poda modificadas para aplicaciones donde no se permite el corte de esquinas el año siguiente. [3] Este documento también presenta un algoritmo para preprocesar una cuadrícula con el fin de minimizar los tiempos de búsqueda en línea.
Los autores publicaron varias optimizaciones adicionales en 2014. [4] Estas optimizaciones incluyen la exploración de columnas o filas de nodos en lugar de nodos individuales, "saltos" de pre-cálculo en la cuadrícula y reglas de poda más estrictas.
Trabajo futuro
Aunque la búsqueda de puntos de salto se limita a cuadrículas de costos uniformes y agentes de tamaño homogéneo, los autores están colocando futuras investigaciones en la aplicación de JPS con técnicas de aceleración basadas en cuadrículas existentes, como las cuadrículas jerárquicas. [4] [5]
Referencias
- ^ a b c D. Harabor; A. Grastien (2011). Poda de gráficos en línea para la búsqueda de rutas en mapas de cuadrícula (PDF) . XXV Congreso Nacional de Inteligencia Artificial. AAAI.
- ^ Witmer, Nathan (5 de mayo de 2013). "Explicación de la búsqueda de puntos de salto" . anticipación positiva de ancho cero . Consultado el 9 de marzo de 2014 .
- ^ D. Harabor; A. Grastien (2012). El sistema de búsqueda de caminos de JPS . XXVI Congreso Nacional de Inteligencia Artificial. AAAI.
- ^ a b Harabor, Daniel; Grastien, Alban. "Mejora de la búsqueda de puntos de salto" (PDF) . Facultad de Ingeniería y Ciencias de la Computación de la Universidad Nacional de Australia . Asociación para el Avance de la Inteligencia Artificial (www.aaai.org) . Consultado el 11 de julio de 2015 .
- ^ Adi Botea; Martin Muller (2004). "Búsqueda de rutas jerárquicas casi óptimas" (PDF) . Universidad de Alberta . Universidad de Alberta.