A Generalized Framework for Lifelong Planning A*

June 2005

A Generalized Framework for Lifelong Planning A*

Authors:

Maxim Likhachev and Sven Koenig

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.
@conference{Likhachev-2005-109736,
author = {Maxim Likhachev And Sven Koenig},
title = {A Generalized Framework for Lifelong Planning A*},
booktitle = {Proceedings of 15th International Conference on Automated Planning and Scheduling (ICAPS '05)},
year = {2005},
month = {June},
pages = {99 - 108},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.