Incremental replanning for mapping

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.

Authors

• Maxim Likhachev
• Sven Koenig

Keywords

• Search methods
• Mobile robots
• Navigation
• Rain
• Terrain mapping
• Mobile computing
• Robot kinematics
• Computer science
• Runtime
• Educational institutions
• Heuristic Search
• Heuristic Method
• Mobile Robot
• Performance Measures
• Shortest Path
• State Machine
• Unknown Status
• Range Of Sensors
• Planning Time
• Linear Graph
• Combined Search
• Recommendations For Action
• Breadth-first Search
• Navigation Strategies
• Terrain Map