Escaping Heuristic Depressions in Real-Time Heuristic Search (Extended Abstract)
Carlos Hernández, Jorge A. Baier · 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. Categories andSubjectDescriptors