Combining lookahead and propagation in real-time heuristic search

Carlos Hernández, Pedro Meseguer

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationSearch in Artificial Intelligence and Robotics - Papers from the 2008 AAAI Workshop, Technical Report
Pages61-67
Number of pages7
VolumeWS-08-10
Publication statusPublished - 2008
Event2008 AAAI Workshop - Chicago, IL, United States
Duration: 13 Jul 200814 Jul 2008

Other

Other2008 AAAI Workshop
Country/TerritoryUnited States
CityChicago, IL
Period13/07/0814/07/08

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Combining lookahead and propagation in real-time heuristic search'. Together they form a unique fingerprint.

Cite this