Incremental Replanning for Mapping

Maxim Likhachev* and Sven Koenig**

*Carnegie Mellon University, **Georgia Institute of Technology

maxim+@cs.cmu.edu, skoenig@cc.gatech.edu

 

Abstract

Incremental heuristic search methods can often replan paths much faster than incremental or heuristic search methods individually, yet are simple to use. So far, they have only been used in mobile robotics to move a robot to given goal coordinates in unknown terrain. As far as we know, incremental heuristic search methods have not yet been applied to the problem of mapping unknown terrain. In this paper, we therefore describe how to apply our incremental heuristic search method D* Lite, that combines ideas from Lifelong Planning A* and Focussed D*, to mapping unknown terrain, which is rather nontrivial. We then compare its runtime against that of incremental search and heuristic search alone, demonstrating the computational benefits of their combination. By demonstrating the versatility and computational benefits of incremental heuristic search, we hope that this underexploited technique will be used more often in mobile robotics.