Escaping heuristic depressions in real-time heuristic search
Carlos Hernández, Jorge A. Baier · Adaptive Agents and Multi-Agents Systems · 2011
Heuristic depressions are local minima of heuristic functions. While visiting one them, real-time (RT) search algorithms like LRTA* will update the heuristic value for most of their states several times before escaping, resulting in costly solutions. Existing RT search algorithm tackle this problem by doing more search and/or lookahead but do not guide search towards leaving depressions. We present eLSS-LRTA* a new RT search algorithm based on LSS-LRTA* that actively guides search towards exiting regions with heuristic depressions. We show that our algorithm produces better-quality solutions than LSS-LRTA* for equal values of lookahead in standard RT benchmarks.