| dc.description | 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. | |
