Sensor-based Coverage of Unknown Environments: Incremental Construction of Morse Decompositions
- 1 April 2002
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 21 (4), 345-366
- https://doi.org/10.1177/027836402320556368
Abstract
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.Keywords
This publication has 15 references indexed in Scilit:
- Morse Decompositions for Coverage TasksThe International Journal of Robotics Research, 2002
- Computational Geometry in CPublished by Cambridge University Press (CUP) ,1998
- Topological Modeling for VisualizationPublished by Springer Science and Business Media LLC ,1997
- A terrain-covering algorithm for an AUVAutonomous Robots, 1996
- Path planning and guidance techniques for an autonomous mobile cleaning robotRobotics and Autonomous Systems, 1995
- Robot Motion PlanningPublished by Springer Science and Business Media LLC ,1991
- Dynamic path planning in sensor-based terrain acquisitionIEEE Transactions on Robotics and Automation, 1990
- Region filling operations with random obstacle avoidance for mobile robotsJournal of Robotic Systems, 1988
- Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shapeAlgorithmica, 1987
- Computational GeometryPublished by Springer Science and Business Media LLC ,1985