Algorithms for Robot Coverage Under Movement and Sensing Constraints

This thesis explores the problem of generating coverage paths—that is, paths that pass within some sensor footprint of every point in an environment—for mobile robots. It both considers models for which navigation is a solved problem but motions are constrained, as well for models in which navigation must be considered along with coverage planning because of the robot’s unreliable sensing and movements. The motion constraint we adopt for the former is a common constraint, that of a Dubins vehicle. We extend previous work that solves this coverage problem as a traveling salesman problem (TSP) by introducing a practical heuristic algorithm to reduce runtime while maintaining near-optimal path length. Furthermore, we show that generating an optimal coverage path is NP-hard by reducing from the Exact Cover problem, which provides justification for our algorithm’s conversion of Dubins coverage instances to TSP instances. Extensive experiments demonstrate that the algorithm does indeed produce path lengths comparable to optimal in significantly less time. In the second model, we consider the problem of coverage planning for a particular type of very simple mobile robot. The robot must be able to translate in a commanded direction (specified in a global reference frame), with bounded error on the motion direction, until reaching the environment boundary. The objective, for a given environment map, is to generate a sequence of motions that is guaranteed to cover as large a portion of that environment as possible, in spite of the severe limits on the robot’s sensing and actuation abilities. We show how to model the knowledge available to this kind of robot about its own position within the environment, show how to compute the region whose coverage can be guaranteed for a given plan, and characterize regions whose coverage cannot be guaranteed by any plan. We also describe an algorithm that generates coverage plans for this robot, based on a search across a specially-constructed graph. Simulation results demonstrate the effectiveness of the approach