通过局部搜索进行大规模多机器人覆盖路径规划 ^†

覆盖路径规划（CPP）是机器人学中的一个基本问题（Galceran 和 Carreras，2013 年），其目的是为机器人找到一条完全覆盖感兴趣地形的路径，例如室内地面（Bormann 等，2018 年）和室外场地（Torres 等，2016 年）。多机器人覆盖路径规划（Multi-Robot Coverage Path Planning，MCPP）是为多机器人系统定制的 CPP 的扩展，旨在协调多个机器人的路径，以完全覆盖给定地形。MCPP 提高了任务效率和系统鲁棒性，促进了环境监测（Collins 等人，2021 年）和搜索救援（Song 等人，2022 年）等各种实际应用。MCPP 的一个基本挑战在于生成成本平衡的覆盖路径，以优化任务效率，通常用 makespan（即所有机器人的最大路径成本）来量化。在处理大规模应用时，机器人的数量和地形的大小都会增加，这就进一步加剧了这一挑战。

在本文中，我们沿用现有的基于图的 MCPP 算法（Zheng 等人，2010 年；Li 等人，2023 年），将需要覆盖的地形表示为一个 4 连接的 2D 网格图 $G$ ，其中每条边连接水平或垂直相邻的顶点。机器人需要从各自的初始顶点出发并返回，就像在覆盖和返回设置中一样（Zheng 和 Koenig，2007 年）。这些基于图形的 MCPP 算法的基础是生成树覆盖（STC）范例（Gabriely 和 Rimon，2001 年和 2002 年），最初是针对（单机器人）CPP 开发的。STC 在地形图 $G$ 上运行，但会在从 $G$ 导出的分解图 $D$ 上以最小的时间跨度找到一条覆盖路径。分解图 $D$ 也是一个 4 连接的 2D 网格图，是将 $G$ 的每个顶点分解为 4 个分解顶点的结果。图 1 显示了要覆盖的地形图 $G$ 及其相应的分解图 $D$ ，其中 STC 通过环绕（即始终沿跨边右侧移动） $G$ 的最小生成树，在 $D$ 上生成单机器人覆盖路径。

与 STC 类似，现有的基于图的 MCPP 算法只对给定的地形图 $G$ 进行操作，以建立树状覆盖--由多棵树组成的森林，每棵树都根植于一个机器人的初始顶点，共同覆盖 $G$ 的所有顶点。然后通过环绕相应的树，获得每个机器人的覆盖路径。从本质上讲，这些算法将 MCPP 简化为 $G$ 上的 NP 难最小-最大有根树覆盖问题（Even 等人，2004 年；Nagamochi 和 Okada，2007 年），该问题旨在优化树覆盖中最大权重树的权重，因为它决定了 $D$ 上所产生覆盖路径的有效期。不过，仅在地形图 $G$ 上运行有两个缺点。首先，它不适用于不完整的地形图 $G$ ，因为在不完整的地形图中，一个顶点的四个分解顶点中的某些顶点可能被阻塞，因此在分解图 $D$ 中不存在。其次， $G$ 上的最优树覆盖并不一定会产生最优 MCPP 解决方案（如图 1-(c) 和 (d) 所示），在最坏的情况下，其产生的 makepan 的渐进次优比为 4（Zheng 等人，2010 年），因为在树覆盖中环绕树木只探索了解决方案空间的一部分，而该空间包含了分解图 $D$ 上所有可能的覆盖路径集。

因此，我们另辟蹊径，探索如何直接在分解图上系统地搜索良好的覆盖路径。我们在算法上的贡献主要体现在以下几个方面：(1) 我们提出了一种新颖的独立算法范式，称为扩展地形图（ESTC），它是 STC 的扩展，通过直接在分解图上操作来解决完整和不完整地形图上的覆盖规划问题。重要的是，我们证明了 ESTC 可以保证单机器人和多机器人环境下的完全覆盖，从而使其成为覆盖路径规划的高效、通用解决方案。(2) 我们提出了三种专门的邻域算子，通过识别分解图中具有成本效益的子图来生成机器人的覆盖路径，从而促进有效的局部搜索过程。这些算子的战略性整合提高了局部搜索探索解决方案空间的效率。(3) 我们演示了如何将这些邻域算子与对 ESTC 范式的迭代调用相结合，从而建立我们提出的 LS-MCPP 框架，用于求解 MCPP。为了验证 LS-MCPP 的有效性，我们进行了大量实验，并将其与三种最先进的基于图形的 MCPP 算法（这些算法仅在完整地形图上运行）进行了比较。结果表明，LS-MCPP 所实现的跨度分别比两种基线算法小 35.7% 和 30.3%，这两种算法都是在地形图上计算次优树覆盖。此外，LS-MCPP 所实现的跨度一直与其余基线算法相当或更好，后者采用混合整数编程（MIP）计算地形图上的最优树覆盖。基线算法需要几十个小时才能完成，而 LS-MCPP 只需几分钟就能完成同样的任务，这充分展示了它在大规模实际覆盖问题上的效率和实用性。

现有的 MCPP 算法首先将给定地形划分为多个区域，然后使用单机器人 CPP 算法为机器人生成每个区域的覆盖路径。在不失一般性的前提下，我们将现有的 MCPP 算法分为基于分解的算法和基于图的算法。基于分解的算法首先使用待覆盖地形折线上的几何临界点对地形进行分割（Karapetyan 等人，2017 年；Vandermeulen、Groß 和 Kolling，2019 年），然后生成之字形路径覆盖每个分割区域。尽管这些方法在相对开放的环境中非常简单，但由于依赖于几何分区，且无法考虑加权地形的非均匀穿越成本，因此不适合障碍物较多的地形（如迷宫）。

我们的论文侧重于基于图的 MCPP 算法（Zheng 等人，2010 年；Li 等人，2023 年），因为这些算法将需要覆盖的地形建模为图，并通过为边或顶点分配权重来考虑非均匀遍历成本，所以用途更为广泛。在图上求解 MCPP 以实现时间跨度最小化已被证明是 NP 难（Zheng 等人，2010 年）。现有方法包括多项式时间近似算法（Hazon 和 Kaminka，2005 年；Tang、Sun 和 Zhang，2021 年）、数值优化（Kapoutsis、Chatzichristofis 和 Kosmatopoulos，2017 年）以及 MIP 方案（Tang 和 Ma，2023 年）。一个密切相关的问题是目标为最小值的多旅行推销员问题（mTSP）（França 等人，1995 年），其目的是为多个推销员找到访问所有给定城市的最佳路线。然而，现有的可扩展 mTSP 算法都是针对欧几里得空间设计的（He and Hao 2023）。我们还不知道有哪种 mTSP 算法直接适用于基于图的 MCPP 问题。

在 MCPP 实例中，我们给定了一个相连的二维网格地形图 $G=(V_{g},E_{g})$ 及其相应的分解图 $D=(V_{d},E_{d})$ ，其中 $V_{g}$ 中的每个地形顶点在 $V_{d}$ 中被分解为四个相邻的小顶点，如图 1-(a) 所示。为清楚起见，我们用 $\delta_{v}\in V_{g}$ 表示分解后的 $v\in V_{d}$ 的相应地形顶点，用 $\varepsilon=(\delta_{u},\delta_{v})\in E_{g}$ 表示连接 $\delta_{u}$ 和 $\delta_{v}$ 的边。每个 $\varepsilon\in E_{g}$ 的权重为 $w_{\varepsilon}$ 。请注意，加权边的定义不同于考虑加权顶点的文献（Zheng 等人，2010 年），但是通过将每条边的权重平均分配给其两个端点顶点，将加权边转换为加权顶点是非常方便的。在这种情况下，每个 $\delta_{v}\in V_{g}$ 都有 $w_{\delta_{v}}=\sum_{\varepsilon\sim{\delta_{v}}}w_{\varepsilon}$ ，其中 $\varepsilon\sim\delta_{v}$ 表示 $\delta_{v}$ 是 $\varepsilon$ 的端点。这样， $D$ 的每条边 $e=(u,v)\in E_{d}$ 的权重 $w_{e}=\frac{1}{4}\cdot\frac{1}{2}\cdot\left[\sum_{\varepsilon\sim\delta_{u}}w_{\varepsilon}+\sum_{\varepsilon\sim\delta_{v}}w_{\varepsilon}\right]$ 就被定义为将每条 $\delta\in V_{g}$ 的权重 $w_{\delta}$ 平均分配给 $w_{\delta}/4$ 的四个分解顶点（Tang 和 Ma，2023 年）。

对于 $D$ 上的任意路径 $\pi=(e_{1},e_{2},...,e_{|\pi|})$ ，其中每个 $e_{i}\in E_{d}$ ，我们将其成本定义为 $c(\pi)=\sum_{i=1}^{|\pi|}w_{e_{i}}$ 。给定一组 $I=\{1,2,...,k\}$ 机器人和一组 $R=\{r_{i}\}_{i\in I}\subseteq V_{d}$ 初始根顶点，基于图的 MCPP 问题是找到一组 $\Pi=\{\pi_{i}\}_{i\in I}$ 的 $k$ 路径，使得每个 $v\in V_{d}$ 至少被一条覆盖路径访问以实现完全覆盖，且每个 $\pi_{i}$ 在 $r_{i}$ 开始和结束。解决方案的质量是通过跨度 $\tau=\max\{c(\pi_{1}),c(\pi_{2}),...,c(\pi_{k})\}$ 来衡量的。

在本节中，我们将介绍新的扩展地形图（ESTC）范式，以解决不完整地形图的覆盖问题。我们的定义是，如果 $\delta_{v}\in V_{g}$ 的四个分解顶点都出现在 $V_{d}$ 中，则 是完整的，否则是不完整的。如果一个地形图 $G$ 的所有顶点都是完整的，那么它就是完整的，否则就是不完整的。STC 只适用于完整地形图，因为它依赖于环绕 $G$ 的跨边。如图 1-(c)(d)所示，STC 的这一限制也使得基于 STC 的 MCPP 算法（Tang 和 Ma 2023）即使在完整地形图上也无法找到好的解决方案。在本文中，我们的重点是覆盖一个连通但可能不完整的分解图，因为覆盖一个不连通的分解图只需要在其每个连通的组成部分中增加一个机器人。

为了生成通过不完整地形顶点的覆盖路径，我们提出的 ESTC 范例巧妙地将 Full-STC（Gabriely 和 Rimon，2002 年）的路径变形程序集成到 STC 的离线计算中。Full-STC 专为未知地形图上的在线（单机器人）CPP 而设计。它可以应用于不完整地形图，但对于已知地形图上的 CPP 实例来说则不是最佳选择，因为它没有考虑不同生成树所产生的不同路径成本。图 2 举例说明了 Full-STC 的次优性。

与 Full-STC 一样，ESTC 也在增强地形图 $G^{\prime}$ 上运行，其中 $G$ 中的一些边在 $G^{\prime}$ 中被移除，以反映其地形顶点之间的连通性。具体来说，如果地形顶点 $\delta_{u}$ 的每个分解顶点 $u$ 与地形顶点 $\delta_{v}$ 的每个分解顶点 $v$ 不相邻，则在 $G^{\prime}$ 中删除边 $\varepsilon=(\delta_{u},\delta_{v})\in E_{g}$ 。一种特殊情况是，每个不完整的地形顶点 $\delta\in V_{g}$ 只有两个对角相对的分解顶点，在 $G^{\prime}$ 中会被两个不相邻的地形顶点取代，因为它的两个分解顶点是不相邻的。与 Full-STC 不同，ESTC 考虑了不均匀的边权重。如果 $\delta_{u}$ 和 $\delta_{v}$ 都是完整的，则边 $\varepsilon=(\delta_{u},\delta_{v})$ 的权重与 $G$ 中的权重相同。否则， $\varepsilon$ 的操作边权重为

其中 $w_{\max}$ 是 $E_{g}$ 的最大边权重，优先使用连接完整地形顶点的边。图 2 显示了增强地形图 $G^{\prime}$ 的一个示例。

根据构造， $G^{\prime}$ 是相连的 $D$ 。然后，ESTC 在 $G^{\prime}$ 而不是 $G$ 上建立最小生成树（MST），并使用与 Full-STC（Gabriely 和 Rimon，2002 年）中定义的相同路径变形规则来通过不完整顶点。从本质上讲，只要由于分解顶点之间的非相邻关系而无法沿右侧移动，该规则就会重新规划生成边左侧的覆盖路径。式（1）中操纵的边权重优先使每个不完整顶点成为 MST 的叶子，这可以防止一些分解顶点在路径变形中因重定向而重复覆盖，从而提高 CPP 解的质量（见图 2）。根据（Gabriely 和 Rimon，2002 年）中定理 3.1 证明中使用的论点，ESTC 保证生成的路径能覆盖连通分解图 $D$ 中的所有顶点，因为该论点不受添加边权重和边优先级的影响。

我们的 LS-MCPP 框架的设计基于上述定理所阐述的原则。其目的是为机器人搜索一组良好的子图 $D_{i}$ ，每个子图都是连通的，其所有顶点的联合就是顶点集 $D$ ，以确保完全覆盖。

在本节中，我们将介绍三种边界编辑算子：增长算子、重复算子和交换算子。这些操作符旨在修改每个子图 $D_{i}$ 的边界，包括添加或删除顶点。我们将重复集 $V^{+}=\{v\in V_{d}\,|\,n_{v}>1\}$ 定义为一个以上机器人覆盖的分解顶点集，其中 $n_{v}=\sum_{i\in I}\left|\{x\in V_{d,i}|x=v\}\right|$ 计算所有子图中顶点 $v\in V_{d}$ 的出现次数。边界编辑算子会改变子图集合 $\{D_{i}\}_{i\in I}$ ，但会确保其完全覆盖属性（即 $\bigcup_{i\in I}V_{d,i}=V_{d}$ ）和子图连通性保持不变。该运算符的目的是只引入必要的重复，这样就有可能在更新的子图集上用 ESTC 改进 MCPP 解决方案。

为了实现不同子图集之间的高效转换，我们将运算符的设计限制为任意子图上的边缘运算；也就是说，每个运算符只涉及为每个子图添加或移除一条边缘。这种设计基于这样的观察，即当 ESTC 应用于生成的子图时，对单个顶点的操作有时会给覆盖路径带来不必要的重复，例如从顶点 $u\in V_{d,i}$ 到其邻居 $v\in V_{d,i}$ 再回到 $u$ 的不良路径。相比之下，边缘算子在每次操作时都会同时修改两个顶点，从而消除了这种顾虑，确保了更有效的调整。值得注意的是，边缘操作符可以实现与涉及多条边缘的操作符相同的结果。此外，我们的操作符只添加或删除两个端点由同一地形顶点分解而来的边，因为操作其他边会带来不必要的重复。形式上，我们将任何 $D_{i}$ 的此类边缘集合表示为

在本节中，我们将介绍 LS-MCPP，这是一种用于有效解决 MCPP 问题的新型局部搜索框架。LS-MCPP 整合了边界编辑算子，直接对分解图 $D$ 进行操作，通过调整子图 $D_{i}$ 来探索良好的覆盖路径。如果 $D_{i}$ 从 ESTC 得到的覆盖路径成本 $c(\pi_{i})$ 不大于所有子图的平均覆盖路径成本 $\bar{c}$ ，我们将其归类为轻型子图；否则，它就是重型子图。LS-MCPP 在轻子图上使用增长算子，在重子图上使用重复算子来消除冗余，并使用交换算子来平衡子图之间的路径成本。其目标是以最少的重复实现成本平衡的解决方案。在更高层次上，LS-MCPP 采用分层抽样方法，在每次局部搜索迭代中有效探索所构建的邻域。它采用轮盘选择法（Goldberg，1989 年）从三个池中选择一个算子池，每个池都包含相同类型的算子。然后，引入新的启发式方法，从选定的算子池中抽取算子。LS-MCPP 还定期调用重复数据删除函数，以利用当前邻域并实现低akespan 解决方案。

本节将介绍我们在英特尔 ^® Xeon ^® Gold 5218 2.30 GHz Linux 服务器上的实验结果，该服务器配备 300 GB 内存。所有 LS-MCPP 实验都在 12 次重复中进行，种子跨度从 0 到 11。实例：我们使用的 MCPP 实例来自（Tang 和 Ma 2023），其中图顶点、图边和机器人的数量范围分别为 $46$ 至 $824$ 、 $60$ 至 $1495$ 和 $4$ 至 $12$ 。如图 6 和表 1 所示，我们又设计了三个更大的实例。如图 6 和表 1 所示，我们还设计了三个更大的实例，其地形图采用了流行的二维寻路基准（Sturtevant，2012 年）。上述所有实例都有完整的地形图。基准：我们使用 MFC（Zheng 等人，2010 年）、MSTC ${}^{*}$ （Tang、Sun 和 Zhang，2021 年）和 MIP/MIP(H) （Tang 和 Ma，2023 年）作为基线算法，它们都使用 STC 将 $G$ 上的树覆盖转换为 MCPP 解决方案。MFC 和 MSTC ${}^{*}$ 都能计算出次优树覆盖。MIP 使用 MIP 模型计算最优树覆盖。MIP(H) 使用缩小的 MIP 模型计算次优树覆盖，但比 MIP 更有效。我们还设计了一种新的基线 VOR，它首先根据机器人的初始顶点计算 $G$ 的沃罗诺图（即 $k$ 子图），然后使用 ESTC 在子图上生成覆盖路径。参数对于所有用 LS-MCPP 求解的实例，池权重衰减因子 $\gamma$ 设为 $0.01$ ，温度衰减因子 $\alpha$ 设为 $\exp{\frac{\log{0.2}}{M}}$ ，以将温度 $t$ 从 $1$ 降到 $0.2$ 。对于 (Tang 和 Ma 2023) 中的实例，我们将最大迭代次数 $M$ 设置为 $3e3$ ，将强制重复数据删除步骤 $S$ 设置为 $1e2$ ，对于表 1 中的另外三个较大实例，我们将 设置为 ，将强制重复数据删除步骤 设置为 。对于表 1 中另外三个较大的实例，我们将 $M$ 设置为 $1.5e4$ ，将 $S$ 设置为 $5e2$ 。

我们介绍了 LS-MCPP，这是一种新的局部搜索框架，它集成了新颖的独立 ESTC 范例和边界编辑算子，首次直接在分解图上系统地探索 MCPP 解决方案。未来的工作包括利用机器学习技术加强算子选择，利用并行化技术加快 LS-MCPP 在更大规模实例中的运行速度，以及利用多代理寻路（Stern 等人，2019 年）技术解决隐蔽环境中潜在的机器人间碰撞问题。

这项工作得到了国家科学和技术研究委员会（NSERC）的资助，资助编号为 RGPIN2020-06540 和 CFI JELF 奖。