Abstract
We introduce the Multi-Robot Connected Fermat Spiral (MCFS), a novel algorithmic framework for Multi-Robot Coverage Path Planning (MCPP) that adapts Connected Fermat Spiral (CFS) from the computer graphics community to multi-robot coordination for the first time. MCFS uniquely enables the orchestration of multiple robots to generate coverage paths that contour around arbitrarily shaped obstacles, a feature that is notably lacking in traditional methods. Our framework not only enhances area coverage and optimizes task performance, particularly in terms of makespan, for workspaces rich in irregular obstacles but also addresses the challenges of path continuity and curvature critical for non-holonomic robots by generating smooth paths without decomposing the workspace. MCFS solves MCPP by constructing a graph of isolines and transforming MCPP into a combinatorial optimization problem, aiming to minimize the makespan while covering all vertices. Our contributions include developing a unified CFS version for scalable and adaptable MCPP, extending it to MCPP with novel optimization techniques for cost reduction and path continuity and smoothness, and demonstrating through extensive experiments that MCFS outperforms existing MCPP methods in makespan, path curvature, coverage ratio, and overlapping ratio. Our research marks a significant step in MCPP, showcasing the fusion of computer graphics and automated planning principles to advance the capabilities of multi-robot systems in complex environments. Our code is available at this https URL.
Abstract (translated)
我们介绍了一种名为多机器人连接费马螺旋（MCFS）的新算法框架，这是多机器人覆盖路径规划（MCPP）的第一个将连接费马螺旋（CFS）从计算机图形社区引入到多机器人协同的框架。MCFS独特地使得多个机器人协同生成围绕任意形状障碍物的覆盖路径，这是传统方法所缺乏的。我们的框架不仅提高了面积覆盖，优化了任务性能，尤其是在不规则障碍物的工场中，还解决了非对称机器人路径连续性和弯曲性的挑战，通过生成无分叉的路径来最小化总用时。MCFS通过构建孤立线并将其转化为组合优化问题来解决MCPP，旨在最小化总用时并覆盖所有顶点。我们的贡献包括开发可扩展和可适应的MCPP的统一CFS版本，引入新的优化技术用于成本降低和路径连续性和平滑性，并通过广泛的实验证明MCFS在总用时、路径弯曲度、覆盖比和重叠比方面优于现有MCPP方法。我们的研究标志着MCPP领域迈出了重要的一步，展示了计算机图形和自动规划原则的融合如何推动多机器人系统在复杂环境中的能力。我们的代码可在此处访问：https://www. researchgate.net/publication/331001922/figure/fig2/AS:7610688463543-155822208294251533?fileId=AS7610688463543-9236e8422e22a1f1!3528!161110!2!
URL
https://arxiv.org/abs/2403.13311
