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

TLDR

Real‑world planning often has limited deliberation time, making anytime planners attractive. This paper introduces ARA*, an anytime heuristic search that adjusts its sub‑optimality bound according to available time. ARA* begins with a loose bound to quickly find a sub‑optimal solution, then progressively tightens the bound while reusing prior search effort, yielding higher efficiency than other anytime methods. With sufficient time, ARA* converges to a provably optimal solution, as shown in experiments on a simulated robot arm and an outdoor rover path‑planning task.

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.