Incremental A*

Sven Koenig and Maxim Likhachev

College of Computing

Georgia Institute of Technology

 

Abstract

Incremental search techniques find optimal solutions to series of similar search tasks much faster than is possible by solving each search task from scratch. While researchers have developed incremental versions of uninformed search methods, we develop an incremental version of A*. The first search of Lifelong Planning A* is the same as that of A* but all subsequent searches are much faster because it reuses those parts of the previous search tree that are identical to the new search tree.  We also present experimental results that demonstrate the advantages of Lifelong Planning A* for simple route planning tasks.