nips nips2003 nips2003-2 nips2003-2-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Maxim Likhachev, Geoffrey J. Gordon, Sebastian Thrun
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. 1
[1] B. Bonet and H. Geffner. Planning as heuristic search. Artificial Intelligence, 129(12):5–33, 2001.
[2] T. L. Dean and M. Boddy. An analysis of time-dependent planning. In Proc. of the National Conference on Artificial Intelligence (AAAI), 1988.
[3] D. Haehnel. Personal communication, 2003.
[4] S. Koenig and M. Likhachev. Incremental A*. In Advances in Neural Information Processing Systems (NIPS) 14. Cambridge, MA: MIT Press, 2002.
[5] R. E. Korf. Linear-space best-first search. Artificial Intelligence, 62:41–78, 1993.
[6] M. Likhachev, G. Gordon, and S. Thrun. ARA*: Formal Analysis. Tech. Rep. CMUCS-03-148, Carnegie Mellon University, Pittsburgh, PA, 2003.
[7] J. Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984.
[8] R. Zhou and E. A. Hansen. Multiple sequence alignment using A*. In Proc. of the National Conference on Artificial Intelligence (AAAI), 2002. Student abstract.
[9] S. Zilberstein and S. Russell. Approximate reasoning using anytime algorithms. In Imprecise and Approximate Computation. Kluwer Academic Publishers, 1995.