Combining Lookahead and Propagation in Real-Time Heuristic Search

Contents

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.