Optimal Planning for Multi-Robot Simultaneous Area and Line Coverage Using Hierarchical Cyclic Merging Regulation
Authors:
- Tianyuan ZhengTZTianyuan Zheng
- Jingang YiJYJingang Yi
- Kaiyan YuKYKaiyan Yu
Preprint
Abstract
The double coverage problem focuses on determining efficient, collision-free routes for multiple robots to simultaneously cover linear features (e.g., surface cracks or road routes) and survey areas (e.g., parking lots or local regions) in known environments. In these problems, each robot carries two functional roles: service (linear feature footprint coverage) and exploration (complete area coverage). Service has a smaller operational footprint but incurs higher costs (e.g., time) compared to exploration. We present optimal planning algorithms for the double coverage problems using hierarchical cyclic merging regulation (HCMR). To reduce the complexity for optimal planning solutions, we analyze the manifold attachment process during graph traversal from a Morse theory perspective. We show that solutions satisfying minimum path length and collision-free constraints must belong to a Morse-bounded collection. To identify this collection, we introduce the HCMR algorithm. In HCMR, cyclic merging search regulates traversal behavior, while edge sequence back propagation converts these regulations into graph edge traversal sequences. Incorporating balanced partitioning, the optimal sequence is selected to generate routes for each robot. We prove the optimality of the HCMR algorithm under a fixed sweep direction. The multi-robot simulation results demonstrate that the HCMR algorithm significantly improves planned path length by at least 10.0%, reduces task time by at least 16.9% in average, and ensures conflict-free operation compared to other state-of-the-art planning methods.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Coverage path planning for multiple unmanned aerial vehicles in maritime search and rescue operationsComputers & Industrial Engineering, 2021
- A survey on multi-robot coverage path planning for model reconstruction and mappingSN Applied Sciences, 2019
- RABIT: implementation, performance validation and integration with other robotic platforms for improved management of bridge decksInternational Journal of Intelligent Robotics and Applications, 2017
- Adaptive continuous‐space informative path planning for online environmental monitoringJournal of Field Robotics, 2017
- Conflict-based search for optimal multi-agent pathfindingArtificial Intelligence, 2015
- A survey on coverage path planning for roboticsRobotics and Autonomous Systems, 2013
- Efficient complete coverage of a known arbitrary environment with applications to aerial operationsAutonomous Robots, 2013
- Coordinated road-network search route planning by a team of UAVsInternational Journal of Systems Science, 2012
- Efficient Boustrophedon Multi-Robot Coverage: an algorithmic approachAnnals of Mathematics and Artificial Intelligence, 2008
- Spanning-tree based coverage of continuous areas by a mobile robotAnnals of Mathematics and Artificial Intelligence, 2001