R* Search
Maxim Likhachev* and Anthony Stentz**
Abstract
Optimal heuristic searches such as A* search are widely used for
planning but can rarely scale to large complex problems. The
suboptimal versions of heuristic searches such as weighted A* search
can often scale to much larger planning problems by trading off the
quality of the solution for efficiency. They do so by relying more
on the ability of the heuristic function to guide them well towards
the goal. For complex planning problems, however, the heuristic
function may often guide the search into a large local minimum and
make the search examine most of the states in the minimum before
proceeding. In this paper, we propose a novel heuristic search,
called R* search, which depends much less on the quality of the
heuristic function. The search avoids local minima by solving the
whole planning problem with a series of short-range and
easy-to-solve searches, each guided by the heuristic function
towards a randomly chosen goal. In addition, R* scales much better
in terms of memory because it can discard a search state-space after
each of its searches. On the theoretical side, we derive
probabilistic guarantees on the sub-optimality of the solution
returned by R*. On the experimental side, we show that R* can scale
to large complex problems.