Graphics enhanced version of this site
Coverage Path Planning in the Plane: Exact Cellular Decompositions
This project is no longer active.
Head: Howie Choset
Contact: Howie Choset (choset@cs.cmu.edu)
Mailing address:
Carnegie Mellon University
Robotics Institute
5000 Forbes Avenue
Pittsburgh, PA 15213
Associated lab/group: Biorobotics
For more information, see this project's homepage.
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
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.
Note: This list may not be comprehensive. It contains only those publications in the RI publications database. Entries are listed in reverse chronological order.