Sensor-based Coverage: Incremental Construction of Cellular Decompositions

December 2002

Sensor-based Coverage: Incremental Construction of Cellular Decompositions

Authors:

E. Acar and H. Choset

Abstract:

Coverage path planning determines a path that passes a robot, a detector, or some type of effector over all points in an environment. Previous work in coverage used cellular decompositions to pass a robot over all points in a target space. We defined a class of cellular decompositions termed Morse Decompositions which were defined by Morse functions; varying the Morse function changes the pattern by which the space was covered. In this paper, we prescribe a provably complete sensor-based coverage path planner that can accommodate detectors with variable effective detecting ranges that go beyond the robots periohery. In vast open spaces, the robot can use the full range of its detector, so we cover these spaces as if the robot were as big as the detector. In narrow and cluttered spaces, we obstacles lie within the detector range and thus the detection range fills the surrounding area; in this case, the robot simply follows the generalized Voronoi diagram in the cluttered spaces. Therefore, we introduce a new hierarchical decomposition that combines Morse decompositions and generalized Voronoi diagrams. We show how to use this hierarchical decomposition to cover unknown spaces.
@workshop{Acar-2002-121497,
author = {E. Acar And H. Choset},
title = {Sensor-based Coverage: Incremental Construction of Cellular Decompositions},
booktitle = {Proceedings of 5th International Workshop on the Algorithmic Foundations of Robotics (WAFR '02)},
year = {2002},
month = {December},
pages = {399 - 415},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.