Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)
Maxim Likhachev, Geoffrey J. Gordon, Sebastian Thrun
In real world planning problems, time for deliberation is often limited. Anytime planners are well suited for these problems: they ﬁnd a feasi- ble 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 ﬁnding a suboptimal solution quickly using a loose bound, then tightens the bound progressively as time allows. Given enough time it ﬁnds a provably optimal solution. While improving its bound, ARA reuses previous search efforts and, as a result, is signiﬁcantly more efﬁ- cient 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 prob- lem for an outdoor rover.