A generalized framework for Lifelong Planning A* search
Maxim A. Likhachev, Sven Koenig · 2005
Recently, it has been suggested that Lifelong Planning A* (LPA*), an incremental version of A*, might be a good heuris-tic 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 pa-per, we therefore develop a general framework that allows one to develop more capable versions of LPA * and its nondeter-ministic 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 ver-sions of LPA * indeed speed it up on grids and thus promise to provide a good foundation for building heuristic search-based replanners.