多机器人协同覆盖线与面,路径更短更高效。
Optimal Planning for Multi-Robot Simultaneous Area and Line Coverage Using Hierarchical Cyclic Merging Regulation
- 用分层环合并调控优化路径规划
- 路径长度减少至少10.0%,任务时间降低16.9%
- 适合需高效协同巡检的多机器人场景
双覆盖问题旨在为多个机器人在已知环境中规划高效且无碰撞的路径,同时完成线性特征(如表面裂缝或道路)和区域(如停车场或局部区域)的覆盖。每个机器人兼具服务(线状覆盖)与探索(区域全覆盖)双重功能,其中服务操作范围小但成本更高。本文提出基于分层环合并调控(HCMR)的最优规划算法。通过莫尔斯理论分析图遍历时的流形附着过程,证明满足最短路径与无碰撞约束的解属于莫尔斯有界集合。HCMR算法通过环合并搜索调控遍历行为,边序列回溯将调控转化为图边遍历序列,并结合均衡划分,选出最优序列生成各机器人路径。证明了在固定扫掠方向下算法的最优性。多机器人仿真结果表明,相比现有先进方法,HCMR路径长度至少减少10.0%,平均任务时间降低至少16.9%,且确保无冲突运行。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。