Combining lookahead and propagation in real-time heuristic search

Carlos Hernández, Pedro Meseguer

Resultado de la investigación: Conference contribution

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 originalEnglish
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
EstadoPublished - 2008
Evento2008 AAAI Workshop - Chicago, IL, United States
Duración: 13 jul 200814 jul 2008

Other

Other2008 AAAI Workshop
PaísUnited States
CiudadChicago, IL
Período13/07/0814/07/08

Huella dactilar

Planning

ASJC Scopus subject areas

  • Engineering(all)

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)
Hernández, Carlos ; Meseguer, Pedro. / Combining lookahead and propagation in real-time heuristic search. Search in Artificial Intelligence and Robotics - Papers from the 2008 AAAI Workshop, Technical Report. Vol. WS-08-10 2008. pp. 61-67
@inproceedings{cf0141318a6240b594c2387f78f88ee4,
title = "Combining lookahead and propagation in real-time heuristic search",
abstract = "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.",
author = "Carlos Hern{\'a}ndez and Pedro Meseguer",
year = "2008",
language = "English",
volume = "WS-08-10",
pages = "61--67",
booktitle = "Search in Artificial Intelligence and Robotics - Papers from the 2008 AAAI Workshop, Technical Report",

}

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, 2008 AAAI Workshop, Chicago, IL, United States, 13/07/08.

Combining lookahead and propagation in real-time heuristic search. / Hernández, Carlos; Meseguer, Pedro.

Search in Artificial Intelligence and Robotics - Papers from the 2008 AAAI Workshop, Technical Report. Vol. WS-08-10 2008. p. 61-67.

Resultado de la investigación: Conference contribution

TY - GEN

T1 - Combining lookahead and propagation in real-time heuristic search

AU - Hernández, Carlos

AU - Meseguer, Pedro

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=66149171492&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:66149171492

VL - WS-08-10

SP - 61

EP - 67

BT - Search in Artificial Intelligence and Robotics - Papers from the 2008 AAAI Workshop, Technical Report

ER -

Hernández C, Meseguer P. 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. 2008. p. 61-67