Combining lookahead and propagation in real-time heuristic search

Real-time search methods allow an agent to perform path-finding tasks in unknown environments. Some real-time heuristic search methods may plan several el-ementary moves per planning step, requiring lookahead greater than inspecting inmediate successors. Recently, the propagation of heuristic changes in the same plan-ning step has been shown beneficial for improving the performance of these methods. In this paper, we present a novel approach that combines lookahead and propaga-tion. 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 num-ber 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 other-wise. We provide experimental evidence of the benefits of this approach, with respect to other real-time algo-rithms on existing benchmarks