The sensor-based coverage task is useful for many applications such as autonomous lawn mowing, floor scrubbing, and snow removal, where the environment may not be known a priori or it is too cumbersome to input into the robot. However, the motivating application for this work is humanitarian de-mining, whose goal is to find and remove every land mine from a target region.

Our approach to the coverage path planning problem makes use of the exact cellular decomposition method. Exact cellular decompositions represent the free space by dividing it into non-overlapping regions called cells such that adjacent cells share a common boundary, the interior of each cell intersects no other cell, and the union of all of the cells covers the free space. We decompose the space into cells using the critical points of Morse functions. We use a graph representation to represent the topology of the cellular decomposition. In this graph each node represents a critical point and each edge represents a cell. Generically each cell is characterized by two critical points and a cell is an edge between two nodes. By using this graph, we reduce the sensor-based coverage to the incremental construction of exact cellular decomposition in terms of critical points of Morse Functions.

We demonstrate our critical point sensing method and the coverage algorithm by performing experiments with a Nomad 200 mobile robot equipped with 16 ultrasonic sensors. The sonar measurements are processed using the ATM method. This method improves the angular resolution of the sonar measurements.