Combining lookahead and propagation in real-time heuristic search

Carlos Hernández, Pedro Meseguer

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferencia

Resumen

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
Páginas61-67
Número de páginas7
VolumenWS-08-10
EstadoPublicada - 2008
Evento2008 AAAI Workshop - Chicago, IL, Estados Unidos
Duración: 13 jul 200814 jul 2008

Otros

Otros2008 AAAI Workshop
PaísEstados Unidos
CiudadChicago, IL
Período13/07/0814/07/08

Áreas temáticas de ASJC Scopus

  • Ingeniería (todo)

Huella 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

    Hernández, C., & Meseguer, P. (2008). Combining lookahead and propagation in real-time heuristic search. En Search in Artificial Intelligence and Robotics - Papers from the 2008 AAAI Workshop, Technical Report (Vol. WS-08-10, pp. 61-67)