Incremental heuristic search methods use heuristics to focus
their search and reuse information from previous searches to
find solutions to series of similar search tasks much faster
than is possible by solving each search task from scratch. In
this paper, we apply Lifelong Planning A* to robot navigation
in unknown terrain, including goal-directed navigation in unknown
terrain and mapping of unknown terrain. The resulting
D* Lite algorithm is easy to understand and analyze. It implements
the same behavior as Stentz’ Focussed Dynamic A*
but is algorithmically different. We prove properties about
D* Lite and demonstrate experimentally the advantages of
combining incremental and heuristic search for the applications
studied. We believe that these results provide a strong
foundation for further research on fast replanning methods in
artificial intelligence and robotics.