AAAI Publications, Twenty-Fourth International FLAIRS Conference

Font Size: 
Real-Time Planning for Covering an Initially-Unknown Spatial Environment
Vikas Shivashankar, Rajiv Jain, Ugur Kuter, Dana Nau

Last modified: 2011-03-20


We consider the problem of planning, on the fly, a path whereby a robotic vehicle will cover every point in an initially unknown spatial environment. We describe four strategies (Iterated WaveFront, Greedy-Scan, Delayed Greedy-Scan and Closest-First Scan) for generating cost-effective coverage plans in real time for unknown environments. We give theorems showing the correctness of our planning strategies. Our experiments demonstrate that some of these strategies work significantly better than others, and that the best ones work very well; e.g., in environments having an average of 64,000 locations for the robot to cover, the best strategy returned plans with less than 6% redundant coverage, and took only an average of 0.1 milliseconds per action.

Full Text: PDF