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

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.