<title>Sensor-based planning: exact cellular decompositions in terms of critical points</title>

Abstract

A coverage path planning algorithm produces a path that directs a robot (or its detector range, occupied volume, etc.) to sweep out a target volume. The goal of this work is to direct an agent to cover (fill) an unknown space using different coverage patterns. We achieve coverage by dividing the target region into sub-regions, termed cells, such that coverage in each cell can be accomplished by basic maneuvers, such as simple back-and-forth motions. This approach to coverage employs a representation of the free space called an exact cellular decomposition, which already has been widely used for path planning between two points. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the locations of cell boundaries. Morse functions are those whose critical points are non-degenerate. Different Morse functions induce different coverage patterns. Between critical points, the structure of a Morse function is effectively the same, so simple control laws to achieve tasks, such as coverage, are feasible within each cell. This paper addresses the issue of how to cover a space with varying patterns, but it also suggests a common framework for many conventional path planners. A companion paper describes the sensor based implementation of this approach.