Lifelong Planning for Mobile Robots

Maxim Likhachev and Sven Koenig

College of Computing

Georgia Institute of Technology

mlikhach@cc.gatech.edu, skoenig@cc.gatech.edu

 

Abstract

Mobile robots often have to replan as their knowledge of the world changes. Lifelong planning is a paradigm that allows them to replan much faster than with complete searches from scratch, yet finds optimal solutions. To demonstrate this paradigm , we apply it to Greedy Mapping, a simple sensor-based planning method that always moves the robot from its current cell to the closest cell that it has not yet observed yet, until the terrain is mapped. Greedy Mapping has a small mapping time, makes only action recommendations and can this coexist with other components of a robot architecture that also make action recommendations, and is able to take advantage of prior knowledge of parts of the terrain (if available). We demonstrate how a robot can use our lifelong-planning version of A* to repeatedly determine a shortest path from its current cell to the closest cell that it has not observed yet. Our experimental results demonstrate the advantage of lifelong planning for Greedy Mapping over other search methods. Similar results had so far been established only for goal-directed navigation in unknown terrain.

 

Keywords: search, incremental search, planning, lifelong planning, mapping