Combining lookahead and propagation in real-time heuristic search

Carlos Hernández, Pedro Meseguer

Producción científica: Contribución a los tipos de informe/libroContribución a la conferenciarevisión exhaustiva


Real-time search methods allow an agent to perform path-finding tasks in unknown environments. Some real-time heuristic search methods may plan several elementary moves per planning step, requiring lookahead greater than inspecting inmediate successors. Recently, the propagation of heuristic changes in the same planning step has been shown beneficial for improving the performance of these methods. In this paper, we present a novel approach that combines lookahead and propagation. Lookahead uses the well-known A* algorithm to develop a local search space around the current state. If the heuristic value of a state inspected during lookahead changes, a local learning space is constructed around that state in which this change is propagated. The number of actions planned per step depends on the quality of the heuristic found during lookahead: one action if some state changes its heuristic, several actions otherwise. We provide experimental evidence of the benefits of this approach, with respect to other real-time algorithms on existing benchmarks.

Idioma originalInglés
Título de la publicación alojadaSearch in Artificial Intelligence and Robotics - Papers from the 2008 AAAI Workshop, Technical Report
Número de páginas7
EstadoPublicada - 2008
Evento2008 AAAI Workshop - Chicago, IL, Estados Unidos
Duración: 13 jul. 200814 jul. 2008


Otros2008 AAAI Workshop
País/TerritorioEstados Unidos
CiudadChicago, IL

Áreas temáticas de ASJC Scopus

  • Ingeniería (todo)


Profundice en los temas de investigación de 'Combining lookahead and propagation in real-time heuristic search'. En conjunto forman una huella única.

Citar esto