ARA*: Formal analysis.

M. Likhachev, G. Gordon, and S. Thrun.

In real world problems, time for deliberation is often limited. Anytime algorithms are beneficial in these conditions as they usually find a first, possibly highly suboptimal, solution very fast and then continually work on improving the solution until allocated time expires. While anytime algorithms are popular, existing anytime search methods are unable to provide a measure of goodness of their results. In this paper we propose the ARA* algorithm. ARA* is an anytime heuristic search which tunes its performance bound based on available search time. It starts by finding a suboptimal solution quickly using a loose bound, then tightens the bound progressively as time allows. Given enough time it finds a provably optimal solution. In addition to the theoretical analysis we demonstrate the practical utility of ARA* with experiments on a simulated robot kinematic arm and dynamic path planning problem for an outdoor rover.

The full paper is available in PDF and gzipped Postscript

@TECHREPORT{Likhachev03c,
  AUTHOR        = {M. Likhachev and G. Gordon and S. Thrun},
  TITLE         = {{ARA*}: Formal Analysis},
  YEAR          = {2003},
  NUMBER        = {CMU-CS-03-148},
  INSTITUTION   = {Carnegie Mellon University, Computer Science Department},
  ADDRESS       = {Pittsburgh, PA}
}