AbstractM. Likhachev and S. Koenig. A Generalized Framework for Lifelong Planning A*. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pages 99-108, 2005.
Abstract: Recently, it has been suggested that Lifelong Planning A* (LPA*), an incremental version of A*, might be a good heuristic search-based replanning method for HSP-type planners. LPA* uses consistent heuristics and breaks ties among states with the same f-values in favor of states with smaller g-values. However, HSP-type planners use inconsistent heuristics to trade off plan-execution cost and planning time. In this paper, we therefore develop a general framework that allows one to develop more capable versions of LPA* and its nondeterministic version Minimax LPA*, including versions of LPA* and Minimax LPA* that use inconsistent heuristics and break ties among states with the same f-values in favor of states with larger g-values. We then show experimentally that the new versions of LPA* indeed speed it up on grids and thus promise to provide a good foundation for building heuristic search-based replanners.
Download the paper in pdf.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.