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 方面显著优于现有算法，并且在运行时间方面具有数量级的优势，对于大规模实际覆盖任务具有重要的好处。