Exact cellular decompositions are structures that globally encode the topology of a robot’s free space, while locally describing the free space’s geometry. These structures have been widely used for path planning between two points, but can be used for mapping and coverage. We define exact cellular decompositions in terms of critical points of Morse functions where critical points indicate the location of cell boundaries. Morse theory assures that between critical points, the structure of a space is effectively the same, so simple control strategies to achieve tasks, such as coverage, are feasible within each cell. We introduce a general framework for defining decompositions in terms of critical points that are general in an m-dimensional Euclidean space.
When the free space of a robot is not known a priori or it is too cumbersome to input into a robot, incremental construction of exact cellular decompositions becomes utmost important. The two main issues of incremental construction are
- Critical point sensing and
- Guaranteeing to “see” all of them by a robot.
We develop a method that uses range sensors to sense critical points. Our method is practical to implement on robots that have sensor suits such as sonar rings, laser range finders etc.. Completeness of exact cellular decomposition is utmost important for applications such as humanitarian de-mining. Our algorithms guarantee to encounter all critical points in unknown environments. Therefore our incremental construction method is proven to be complete.
