Robust coverage by a mobile robot of a planar workspace

In this paper, we suggest a new way to plan coverage paths for a mobile robot whose position and velocity are subject to bounded error. Most prior approaches assume a probabilistic model of uncertainty and maximize the expected value of covered area. We assume a worst-case model of uncertainty and-for a particular choice of coverage path-are still able to guarantee complete coverage. We begin by considering the special case in which the region to be covered is a single point. The machinery we develop to express and solve this problem immediately extends to guarantee coverage of a small subset in the workspace. Finally, we use this subset as a sort of virtual coverage implement, achieving complete coverage of the entire workspace by tiling copies of the subset along boustrophedon paths.