Avoiding and Escaping Depressions in Real-Time Heuristic Search
  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 inaccurate compared to the actual cost to reach a
solution. Early real-time search algorithms, like LRTA*, easily become trapped
in those regions since the heuristic values of their states may need to be
updated multiple times, which results in costly solutions. State-of-the-art
real-time search algorithms, like LSS-LRTA* or LRTA*(k), improve LRTA*s
mechanism to update the heuristic, resulting in improved performance. Those
algorithms, however, do not guide search towards avoiding 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 propose two ways in which depression avoidance can be
implemented: mark-and-avoid and move-to-border. We implement these strategies
on top of LSS-LRTA* and RTAA*, producing 4 new real-time heuristic search
algorithms: aLSS-LRTA*, daLSS-LRTA*, aRTAA*, and daRTAA*. When the objective is
to find a single solution by running the real-time search algorithm once, we
show that daLSS-LRTA* and daRTAA* outperform their predecessors sometimes by
one order of magnitude. Of the four new algorithms, daRTAA* produces the best
solutions given a fixed deadline on the average time allowed per planning
episode. We prove all our algorithms have good theoretical properties: in
finite search spaces, they find a solution if one exists, and converge to an
optimal after a number of trials.
