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

我们介绍了 Multi-Robot Connected Fermat Spiral（MCFS），这是一个新颖的算法框架，用于多机器人覆盖路径规划（MCPP），它将来自计算机图形学界的 Connected Fermat Spiral（CFS）首次应用于多机器人协调。MCFS 独特地实现了多个机器人编排生成环绕任意形状障碍物的覆盖路径，这是传统方法明显缺乏的功能。我们的框架不仅增强了面积覆盖和任务性能优化，特别是在充满不规则障碍物的工作空间中的完成时间方面，而且通过生成连续平滑的路径而解决了非完整机器人的路径连续性和曲率的挑战，而无需对工作空间进行分解。MCFS 通过构造等值线图并将 MCPP 转换为组合优化问题来解决 MCPP，旨在最小化完成时间同时覆盖所有顶点。我们的贡献包括开发了可扩展且适应性强的 MCPP 统一 CFS 版本，通过优化技术降低成本并保持路径的连续性和平滑性，通过广泛的实验证明 MCFS 在完成时间、路径曲率、覆盖比率和重叠比率方面优于现有的 MCPP 方法。我们的研究在 MCPP 方面迈出了重要的一步，展示了计算机图形学和自动规划原理的融合，以推动多机器人系统在复杂环境中的能力。我们的代码可在此 https URL 找到。

多机器人连接费马螺线覆盖

Multi-Robot Connected Fermat Spiral Coverage

We study graph-based Multi-Robot Coverage Path Planning (MCPP) that aims to
compute coverage paths for multiple robots to cover all vertices of a given 2D
grid terrain graph $G$. Existing graph-based MCPP algorithms first compute a
tree cover on $G$ -- a forest of multiple trees that cover all vertices -- and
then employ the Spanning Tree Coverage (STC) paradigm to generate coverage
paths on the decomposed graph $D$ of the terrain graph $G$ by circumnavigating
the edges of the computed trees, aiming to optimize the makespan (i.e., the
maximum coverage path cost among all robots). In this paper, we take a
different approach by exploring how to systematically search for good coverage
paths directly on $D$. We introduce a new algorithmic framework, called
LS-MCPP, which leverages a local search to operate directly on $D$. We propose
a novel standalone paradigm, Extended-STC (ESTC), that extends STC to achieve
complete coverage for MCPP on any decomposed graphs, even those resulting from
incomplete terrain graphs. Furthermore, we demonstrate how to integrate ESTC
with three novel types of neighborhood operators into our framework to
effectively guide its search process. Our extensive experiments demonstrate the
effectiveness of LS-MCPP, consistently improving the initial solution returned
by two state-of-the-art baseline algorithms that compute suboptimal tree covers
on $G$, with a notable reduction in makespan by up to 35.7\% and 30.3\%,
respectively. Moreover, LS-MCPP consistently matches or surpasses the results
of optimal tree cover computation, achieving these outcomes with orders of
magnitude faster runtime, thereby showcasing its significant benefits for
large-scale real-world coverage tasks.

我们研究基于图的多机器人覆盖路径规划 (MCPP)，旨在计算多个机器人覆盖给定 2D 网格图 $G$ 的所有顶点的路径。我们提出了一种新的算法框架 LS-MCPP，利用局部搜索直接在图 $D$ 上操作，通过扩展 STC 实现 MCPP 在任何分解图上的完全覆盖，并结合三种新颖的邻域操作符来引导搜索过程。我们的实验结果表明，LS-MCPP 在优化 makespan 方面显著优于现有算法，并且在运行时间方面具有数量级的优势，对于大规模实际覆盖任务具有重要的好处。

大规模多机器人覆盖路径规划中的局部搜索

Large-Scale Multi-Robot Coverage Path Planning via Local Search

We investigate time-optimal Multi-Robot Coverage Path Planning (MCPP) for
both unweighted and weighted terrains, which aims to minimize the coverage
time, defined as the maximum travel time of all robots. Specifically, we focus
on a reduction from MCPP to Rooted Min-Max Tree Cover (RMMTC). For the first
time, we propose a Mixed Integer Programming (MIP) model to optimally solve
RMMTC, resulting in an MCPP solution with a coverage time that is provably at
most four times the optimal. Moreover, we propose two suboptimal yet effective
heuristics that reduce the number of variables in the MIP model, thus improving
its efficiency for large-scale MCPP instances. We show that both heuristics
result in reduced-size MIP models that remain complete (i.e., guarantee to find
a solution if one exists) for all RMMTC instances. Additionally, we explore the
use of model optimization warm-startup to further improve the efficiency of
both the original MIP model and the reduced-size MIP models. We validate the
effectiveness of our MIP-based MCPP planner through experiments that compare it
with two state-of-the-art MCPP planners on various instances, demonstrating a
reduction in the coverage time by an average of 42.42% and 39.16% over them,
respectively.

本研究采用混合整数规划和启发式算法对多机器人覆盖路径规划进行优化，其中包括两种减少规模的启发式算法，通过实验证明，相比现有算法，本研究提出的方法可以显著降低路径覆盖时间。