Complete sensor-based coverage of unknown spaces: Incremental construction of cellular decompositions

The goal of coverage path planning is to determine a path that passes a detector or an effector over all points in an environment. This thesis prescribes provably complete coverage path planners that can accommodate detectors and sensors with variable effective detecting and sensing ranges. Our sensor-based planners exploit on-line sensor data to achieve complete coverage of a priori unknown planar spaces. We simplify coverage by decomposing free space of a robot into regions, called cells, that allows a planner to determine a “simple” path within each cell. The collection of these cells is termed a cellular decomposition. For coverage with detectors that are the same size as the robot, we introduce a specific family of cellular decompositions, termed Morse decompositions, whose cells are formed using critical points of Morse functions, functions with non-degenerate critical points, at which topologically meaningful events occur. Each cell of the Morse decompositions can be covered by performing simple motions such as farming maneuvers. For coverage with detectors that have extended ranges, we also introduce a hierarchical decomposition comprising Morse decompositions and cells characterized by generalized Voronoi diagrams which are sets of points equidistant to two obstacles. The hierarchical decomposition divides the robot's free space into two regions: vast and narrow. In the vast regions, we use Morse decompositions and in the narrow regions we simply have the robot follow the generalized Voronoi diagram to cover the unknown space. To interchange coverage modes from vast to narrow, we introduce a method that uses range data. We encode all topologically meaningful information about the decompositions using graph representations and thus we reduce complete coverage of an unknown space to incremental graph construction procedures. We also use topological and geometrical features of our algorithm and Morse decompositions to prevent some of the failures of our algorithm due to bad sonar data. Finally, we exploit the structure of Morse decompositions to plan a path between two critical points that is less “sensitive” to dead-reckoning error.