Real-Time Planning for Covering an Initially-Unknown Spatial Environment

Abstract

We consider the problem of planning, on the fly, a path whereby a robotic vehicle will cover every point in an ini-tially unknown spatial environment. We describe four strate-gies (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 strate-gies. Our experiments demonstrate that some of these strate-gies 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 re-turned plans with less than 6 % redundant coverage, and took only an average of 0.1 milliseconds per action.