Optimal Multi-Robot Planning for Simultaneous Area and Line Coverage
Tianyuan Zheng, Kaiyan Yu, Mingyang Gao, Jingang Yi
AI summary
Problem
Robotic inspection tasks often require teams to simultaneously explore open areas and service linear features like cracks or pipelines, yet existing methods lack rigorous frameworks to unify these competing roles without path discontinuities or conflicts.
Approach
The authors map disjoint area and linear feature domains onto a unified manifold using quotient and stitching operations, then apply the Hierarchical Cyclic Merging Regulation (HCMR) algorithm to generate continuous, topology-constrained Eulerian tours for optimal multi-robot path planning.
Key results
- Novel formulation of the multi-robot double coverage problem
- Topological analysis proving path optimality equals Morse boundedness
- HCMR algorithm for continuous, optimal Eulerian tours
- Experimental validation showing ≥10% path reduction and ≥17% time savings
Why it matters
Enables efficient, reliable deployment of multi-robot teams for real-world infrastructure inspection and repair tasks that require both broad surveying and precise feature servicing.
Abstract
Robotic coverage tasks often require teams of robots to not only survey regions of interest but also trace and interact with linear features such as cracks, seams, or pipelines. We term this the double coverage problem, where robots must balance two competing roles: wide-area exploration for inspection and precise trajectory following for servicing linear structures. This paper develops an optimal multi-robot planning framework that unifies area coverage and line servicing. We formulate a topological analysis in manifold space and introduce the hierarchical cyclic merging regulation (HCMR) method, for which optimality under a fixed sweep direction is proven. The framework is experimentally validated for a multi-robot crack survey and filling application. Benchmark comparisons demonstrate that HCMR reduces planned path length by at least 10.0%, shortens task completion time by at least 16.9%, and ensures complete crack coverage with virtually conflict-free operation, outperforming state-of-the-art coverage planners. These results highlight the feasibility and efficiency of deploying topology-informed multi-robot planning for practical inspection and repair scenarios.