AAAI Publications, Ninth Annual Symposium on Combinatorial Search

Font Size: 
Weighted Lateral Learning in Real-Time Heuristic Search
Vadim Bulitko, Alexander Sampley

Last modified: 2016-06-20


Real-time heuristic search models an autonomous agent solving a search task. The agent operates in a real-time setting by interleaving local planning, learning and move execution. In this paper we propose a simple parametric algorithm that combines weighting with learning from multiple neighbors. Doing so breaks heuristic admissibility but allows the agent to escape heuristic depressions more quickly. We prove completeness of the algorithm and empirically compare it to several competitors more than twenty years apart. In a large-scale evaluation the new algorithm found better solutions than the recent algorithms, despite not learning additional information that they do. Finally, we study robustness of the algorithms to noise in the heuristic function — a desirable property in a physical implementation of real-time heuristic search. The new algorithm outperforms its contemporaries.


real-time heuristic search, heuristic learning

Full Text: PDF