ARA*: Anytime A* with Provable Bounds on Sub-Optimality - Robotics Institute Carnegie Mellon University

ARA*: Anytime A* with Provable Bounds on Sub-Optimality

Maxim Likhachev, Geoff Gordon, and Sebastian Thrun
Conference Paper, Proceedings of (NeurIPS) Neural Information Processing Systems, pp. 767 - 774, December, 2003

Abstract

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.

BibTeX

@conference{Likhachev-2003-109738,
author = {Maxim Likhachev and Geoff Gordon and Sebastian Thrun},
title = {ARA*: Anytime A* with Provable Bounds on Sub-Optimality},
booktitle = {Proceedings of (NeurIPS) Neural Information Processing Systems},
year = {2003},
month = {December},
pages = {767 - 774},
}