ARA*: Anytime A* search with provable bounds on sub-optimality.

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

In real world planning problems, time for deliberation is often limited. Anytime planners are well suited for these problems: they find a feasible solution quickly and then continually work on improving it until time runs out. In this paper we propose an anytime heuristic search, ARA*, 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. While improving its bound, ARA* reuses previous search efforts and, as a result, is significantly more efficient than other anytime search methods. In addition to our theoretical analysis, we demonstrate the practical utility of ARA* with experiments on a simulated robot kinematic arm and a dynamic path planning problem for an outdoor rover.

The full paper is available in PDF and gzipped Postscript

@INPROCEEDINGS{Likhachev03b,
  AUTHOR	= {M. Likhachev and G. Gordon and S. Thrun},
  TITLE		= {{ARA*}: Anytime {A*} Search with Provable Bounds on Sub-Optimality},
  YEAR		= {2003},
  BOOKTITLE	= {Proceedings of Conference on Neural Information Processing Systems (NIPS)},
  EDITOR	= {S. Thrun and L. Saul and B. Sch\"{o}lkopf},
  PUBLISHER	= {MIT Press}
}