Real-Time Heuristic Search with Depression Avoidance
Carlos Hernandez and Jorge Baier
Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is exceedingly low compared to the actual cost to reach a solution. Real-time search algorithms easily become trapped in those regions since the heuristic values of states in them may need to be updated multiple times, resulting in costly solutions. State-of-the-art real-time search algorithms like LSS-LRTA*, LRTA*(k), etc., extend LRTA* with better mechanisms to update the heuristic values, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding and escaping depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We apply the approach to LSS-LRTA*, and produce aLSS-LRTA*, a new real-time search algorithm whose search is guided towards exiting regions with heuristic depressions. We show that our algorithm outperforms LSS-LRTA* in standard real-time benchmarks. In addition we prove aLSS-LRTA* has most of the good theoretical properties of LSS-LRTA*.