|The goal of coverage path planning
is to determine a path that passes a detector over all points in an environment.
This work prescribes a provably complete coverage path planner for robots
in unknown spaces. We achieve coverage using Morse decompositions which
are exact cellular decompositions whose cells are defined in terms of critical
points of Morse functions. Generically, two critical points define a cell.
We encode the topology of the Morse decomposition using a graph that has
nodes corresponding to the critical points and edges representing the cells
defined by pairs of critical points. The robot simultaneously covers the
space while incrementally constructing this graph. To achieve this, the
robot must sense all the critical points. Therefore, we first introduce
a critical point sensing method that uses range sensors. Then we present
a provably complete algorithm which guarantees that the robot will encounter
all the critical points, thereby constructing the full graph, i.e., achieving
complete coverage. We also validate our approach by performing experiments
on a mobile robot equipped with a sonar ring.