用于最优多机器人覆盖路径规划的分割区域算法DARP

摘要

本文研究了移动机器人组的路径规划问题，以便覆盖感兴趣的区域，并考虑到预先定义的障碍物。对于单个机器人的情况，也称为单个机器人覆盖路径规划（CPP），已经在文献中提出了一种$O(n)$最优方法，并进行了评估，其中$n$是网格大小。现有的多机器人情况（mCPP）的大多数算法利用了上述算法。然而，由于mCPP的复杂性，现有的mCPP算法的最佳性能至多是最优解的16倍，就机器人队完成覆盖任务所需的时间而言，而计算解决方案所需的时间是多项式的。本文中，我们提出了一种新的算法，该算法至少在存在最优解的情况下收敛到最优解。所提出的技术将原始的整数规划问题（mCPP）转化为多个单机器人问题（CPP），其解决方案构成了最优的mCPP解，从而减轻了原始的mCPP爆炸性组合复杂性。虽然不可能在所提出的算法复杂性方面进行解析界限，但广泛的数值分析表明，实际输入的复杂性受到多项式曲线的限制。所提出方法的核心是DARP算法，它将地形划分为若干个相等的区域，每个区域对应一个特定的机器人，以保证完全覆盖、非回溯解、最小覆盖路径，同时不需要任何准备阶段。

1 简介

自20世纪70年代以来，无人驾驶机器人已经在极低和极高的高度、深海和太空探索以及几乎所有的飞机中日常使用[20]。今天，在多机器人时代，许多机器人挑战，对于单个机器人的确定解决方案必须进行修订，以最佳地纳入多机器人动态。机器人学中的一个基本问题是确定涉及感兴趣区域的所有点的最佳路径，同时避免具有特定特征（例如，障碍物、禁止区域等）的子区域。在文献中，这个问题通常被称为覆盖路径规划问题（CPP），但也可以被称为扫描、详尽的地理搜索、区域巡逻等。这个任务直接涉及大量的机器人应用，例如真空清洁机器人[1]、自主水下机器人[23] [22]、无人机[31]、除地雷机器人[4]、自动化收割机[28]、行星探索[6]、搜索和救援行动[34]。

通常问题的抽象表示为一个带有关联工具（例如传感器、执行器）的机器人，其能够空间覆盖至少与机器人本身大小相同的区域。因此，最常见的区域表示技术之一是将该区域分为相同的单元格（例如与机器人大小相同的大小），以便可以轻松地完成每个单元格的覆盖。显然，对于任意形状的区域，单元格的并集只能近似表示该区域。因此这种技术（也在我们的方法中采用，见第3节）被称为近似细胞分解。关于不同区域分解技术的全面分析以及每个类别的主要代表，可以在[11]中找到。

在过去的十年中，研究人员专注于已知地形中的单机器人覆盖规划问题，提出了许多不同的方法（例如[10]、[38]、[36]等）。其中一个主要方法是生成树覆盖（STC）算法[18]，它能够在线性时间内保证一个最优路径，构建所有空闲单元格的最小生成树。最优这一术语意味着生成的路径不会重复访问同一个单元格（不回溯属性），完全覆盖了感兴趣的区域，并在不需要任何准备工作的情况下实现了上述所有内容（机器人可以在任何非占用单元格处初始化）。这项重要成就基于的假设是作业区域不会比机器人尺寸的两倍更狭窄。我们的方法采用了STC算法，因此它继承了这个要求，在本文的第4节中更加正式地描述了这一要求。

近年来，机器人技术在硬件和相关软件方面取得了长足进步，扩大了可以用于覆盖任务的机器人种类。作为其结果，最近在覆盖路径规划问题中使用多机器人团队（形成多-CPP或mCPP问题）受到了广泛关注。不幸的是，mCPP问题被证明要解决得极其困难。事实上，用最小覆盖时间解决mCPP被证明是NP-hard [39]。以前的研究试图通过提出解决原始mCPP问题的简化版本的算法来克服问题的NP性质，主要集中在覆盖主要目标之一的问题上（有关详细信息，请参见第2节）。此外，在mCPP问题中，除了直接从单个CPP中派生的最优特征，设计路径以充分利用可用的多机器人动力学特性也是一种挑战。实质上，这种条件是任何多机器人系统中的至高境界之一，因为解锁这种特性将允许机器人完全协作，最终充分利用它们的能力。在许多提出的方法中，为了达到主要的覆盖目标（完整性、不回溯），往往会牺牲多机器人动力学的充分利用。此外，在多机器人方法中，一个经常被忽视的问题是为了将机器人从其起始单元格中“转移”所需的成本/时间，从问题中排除初始机器人位置。总的来说，提出的最佳方法可以在严格的多项式时间内实现覆盖时间的16倍。

在本文中，我们提出了一种方法，能够以覆盖时间的最优解（至少在存在时）为mCPP问题提供最优解，而不忽视任何上述方面。与传统的解决此问题的方式[14]相反（通常称为先分配再分解或先分解再分配），其中任务的构建和分配是分开处理[29]的，提出了一种新方法，其中构建任务是面向机器人的。同时，对现实环境进行了扩展的数值分析表明，计算时间在Grid大小和#robots的多项式。本质上，原始的mCPP被转化为一个优化问题，满足一个明确定义的一组约束将最终产生最优解。更具体地说，所提出的方案分为两个阶段。

• 首先，通过利用约束满足方案，将可用单元格分为不同的类，与#robots一样多。此聚类的目的是保持以下属性：
• a）完全覆盖，
• b）无需任何准备工作即可操作，最重要的是
• c）充分利用多机器人动态。

在所提出的算法的核心，在基于机器人初始位置的分裂区域（Divide Areas based on Robot’s initial Positions，DARP）算法中，能够根据机器人的初始位置产生最优单元分配方案。这可以通过采用一种特定于手头问题的循环坐标下降方法[35]来实现，并具有已知的收敛特性。

• 在第二阶段中，STC算法以分布式方式设计每个机器人群集的最优路径。

本文的概述如下。第2节描述了相关工作，介绍了mCPP的替代作品。第3节将mCPP问题转化为优化问题，并介绍了所有必要的符号。第4节概述了STC算法的主要步骤，涉及CPP问题的最优解。第5节利用该节的发现放松原始mCPP问题。在同一节中，正式描述了最优解的基本条件。在第6节中，我们提出了DARP算法，并对其性能进行了全面讨论。第7节概述了CPP问题的完整方案，第8节展示了所提出的方案与两种最先进算法在mCPP问题方面的性能比较。最后，在第9节中提出结论性的评论，并展望未来的工作。

2 相关工作

2.1 已知地形的多机器人覆盖路径规划问题

尽管mCPP是一个相对新的研究领域，但已经有大量的研究试图解决该问题的限制和约束。本文的范围不包括对该领域做出深入讨论，因此，为了构建一个更适当和均匀的备选作品池，只包括与我们问题公式化（第3节）一致的出版物。有关最新的CPP / mCPP问题成就的更详细和完整的调查，读者应参考[19]。

作者在文献[21]中首次将单机器人生成树覆盖算法[18]转换为一种能够合并机器人团队的方法。他们的集中式算法（称为MSTC）确保在避开已知障碍物的情况下完全覆盖操作区域。此外，无回溯版本的解决方案只在每个单元格上访问一次，同时具有机器人故障容错能力。不幸的是，每个机器人的路径长度严重依赖于机器人的初始位置，而在最坏情况下，单个机器人的最大路径长度几乎等同于单个机器人情况下的路径长度，即使可能存在可替代的最优路径配置。

同一作者为了缓解上述缺点，提出了增强版本（称为OPT-MSTC）[5]，其中生成树的形式被修改以最小化沿生成树路径的每两个连续机器人之间的最大距离。这种技术的表现比随机生成的树更好，但仍然不能保证初始机器人位置。

另一种利用生成树的替代技术在[39]中被提出。在这项工作中，作者们针对已知地形上的多机器人覆盖算法提供了一种上限性能保证，保证最多为最优成本的十六倍，并同时保持完全覆盖的关键特征。虽然现在已经取消了无回溯保证，但MFC算法在最小化最大机器人路径长度方面表现明显优于MSTC和OPT-MSTC，这表明在机器人路径长度的平等约束不存在的情况下，解远离最优团队利用率。

文献[17]中的作者们发展出一种方法，试图通过一支移动机器人队伍在已知环境中巡逻问题，这支队伍可以被转化为以一定频率访问地形上的所有点。事实上，巡逻问题与最小循环覆盖路径（mCPP）问题密切相关，因此用于巡逻的解决方案可能也适用于mCPP问题。在这项工作中，作者们首先生成了一条最小循环路径，类似于[18]，遍历操作区域的每个单元，然后搜索最佳“机器人初始位置”。这些新位置的计算是为了使其最小化其初始位置和这些要行驶的距离之间的最大距离，并使这些距离大致相同。不幸的是，将其分为两个独立的任务会限制所提出的算法的性能。实际上，即使在存在其他最优解的情况下，要实现机器人路径平等的条件，最坏情况下要访问的单元格数量也没有上限。

2.2 区域划分，用于多机器人任务

本小节介绍主要的区域划分技术，以协助多机器人任务 - 不限于覆盖。

一个属于这一类的有趣方法，在[25]中被提出。使用扫描线法来划分操作区域，并将每个子区域分配给最合适的机器人，基于它们的相对能力。然而，该方法假设机器人最初位于操作区域的边界上，这是不现实的条件。此外，所提出的算法仅考虑了没有障碍物的凸面积区域。

在[8]中，作者提出了一个完整的多无人机覆盖领域问题的方法，并直接应用于农业遥感任务。在第一个步骤中，作者提出了一个区域细分方法，它扩展了众所周知的交替提供协议[30]。这种技术旨在同时以分布式有效的方式执行区域划分和分配任务。尽管该方法在实现细节方面已经很成熟，但它并无性能保证。作者提出了一些性能评估和比较的结果，但这些结果并不完全充分。作者认为最终的子区域分配是一个完美的均衡，但是对于非凸区域或“困难”的初始机器人放置情况，该方法如何克服子优解并没有任何参考。

在[3]中，作者提出了一种替代方法，使用启发式算法来解决任意多边形分割的问题。尽管结果非常有前途，其算法运行时间为多项式，但是产生的解决方案有两个主要缺点。一方面，没有关于区域划分优化的具体保证，另一方面，不考虑初始机器人位置。

在[29]中描述的算法旨在通过将工作场所划分为可用机器人的分离区域来实现增强的多机器人勘探。作者使用K均值算法将可用地形分成距离相关的凸子区域，然后应用机器人 - 子区域分配机制来变换线性规划问题，利用LP-solve软件[2]。不幸的是，这种两阶段过程可能会导致高度次优的解决方案，机器人可能需要走很长的路程（与整个操作区域相比）才能到达其分配的子区域。

关于多机器人环境下的区域划分问题，许多最先进的方法（例如[9]、[13]、[16]）都依赖于Lloyd算法[24]，具有已知的收敛性质[15]，和/或Voronoi分割[7]。虽然这些方法似乎适用于mCPP问题，特别是区域划分问题，但它们在一个非常重要的方面有所不同。这些方法试图回答以下问题：“将机器人放置在哪些最优位置上，以便用它们的板载传感器覆盖非占用空间？”相反，在本文中，“覆盖”这个术语意味着相应的机器人必须实际访问相应的指定区域。上述方法更适合于解决问题，例如将一组机器人定位在一个地形中，以使任何位置都尽可能靠近至少一个机器人[12]，或者以最佳方式监测具有异构感兴趣的动态事件（例如漏油事件），因此，大部分这些方法独立于机器人/代理的初始位置解决区域划分问题。因此，将这些算法直接应用于mCPP问题可能会导致相当次优的结果，因为机器人的区域可能被平均分割，但达到这些子区域所需的时间/成本已经被忽略。

相关文献的细粒度分析清楚地表明，仍有提高机器人能力的空间，而不会危及已经产生的解决方案的重要特征。基于这种需求，本文提出了一个基于网格的多机器人路径规划算法，在已知地形中进行区域划分，根据机器人数量和它们的初始位置。在随后的阶段中，每个机器人独占区域内的精确路径完全以分布方式定义。所提出的算法是mCPP问题的近似多项式时间算法（对于实际规模的输入），能够保证解决方案 i)完全覆盖所有区域 ii)避免在已经访问过的子区域中返回 iii)利用所有可用机器人保证最低覆盖时间 iv)不需要任何准备阶段（机器人可以从它们的初始位置开始旅程）。

3 多机器人覆盖路径规划公式

为了便于理解，假设要覆盖的地形被限制在$(x,y)$坐标系中的矩形中，并且被离散化为有限的等分的单元格，这个数量代表所需空间分辨率和机器人的感知能力。定义

$$\mathcal{U}=\{x,y:x\in [1,rows],y \in [1,cols]\}\tag{1}$$

，其中rows和cols是被覆盖地形的离散化后的行和列数。显然，所有地形单元格的数量为$n=rows\times cols$。

还假设没有放置任何障碍物在$\mathcal{U}$的先验已知位置上。未知障碍物的集合表示为

$$B=\{(x,y)\in \mathcal{U} :(x,y) \ is \ occupied\}\tag{2}$$

机器人无法穿过障碍物，因此需要覆盖的所有单元格总集合被缩

$$\mathcal{L} = \mathcal{U} - B \tag{3}$$

需要覆盖的单元格数量缩小为$l=n-n_0$。

定义1：如果满足以下公式$(4)$，则两个单元格$(x_i,y_i)$和$(x_j,y_j)$视为相邻的。

$$||x_i-x_j||+||y_i-y_j||\leq 1 \tag{4}$$

与许多多机器人覆盖方案一样，假定机器人可以完美地在$\mathcal{U}$内定位自己，并且在每个时间戳，它可以从其当前单元格移动到任何未被阻挡的$(\in \mathcal{L})$相邻单元格，而没有任何运动不确定性。

定义2：

长度为$m$的有效机器人路径被认为是每个单元格序列$X=((x_1,y_1),\cdots ,(x_m,y_m))$，其中遵守以下约束：

• $(x_i,y_i)\in \mathcal{L},\forall i\in\{1,\cdots ,m\}$
• 每两个连续的单元格,即$(x_i,y_i)$和$(x_{i+1},y_{i+1})$，都是相邻的(定义1),$\forall i\in \{1,\cdots,m-1\}$.

此外，长度为$m$的闭合路径是一条路径，如定义2中所定义，其中保持额外条件：

• $(x_1,y_1)$和$(x_m\,y_m)$相邻。

机器人位置被定义为:

$$\mathcal{X}_i(t) = (x_i,y_i) \in \mathcal{L},\forall i \in\{1,\cdots,n_r\}\tag{5}$$

其中$t$表示覆盖路径的具体时间戳，$n_r$表示运行机器人的数量。第$i$个机器人的（给定）初始位置在$\mathcal{L}$内表示为$\mathcal{X}_i(t_0)$。

在上述公式的基础上，mCPP问题可以转换为计算机器人路径$X_i^* \forall i\in \{1,\cdots,n_r\}$，使得：

$$minimize\ max_{i\in\{1,\cdots,n_r\}}|X_i| \tag{6}$$

带入$X_1\cup X_2\cup \cdots \cup X_{n_r} \supseteq \mathcal{L}$

其中$|X_i|$表示路径$X_i$的长度。

4 在非结构化环境下的单机器人覆盖

暂且不考虑多机器人的最优移动问题，我们考虑只用一台机器人来覆盖连续的非结构化区域的问题。遵循式（6）中优化问题的符号表示，上述单机器人CPP问题可以定义为：

$$\begin{matrix} minimize\ |X_1|\\X_1 \\ subject \ to \ X_1 \supseteq \mathcal{L} \end{matrix} \tag{7}$$

在文献中已经证明，CPP问题有一个O(n)算法[18]，其中n是网格的规模，能够始终产生最优解。换句话说，生成树覆盖（STC）算法能够构建涵盖所有操作区域$\mathcal{L}$的最小路径，从任意一个未占用的单元格开始。

图1展示了一个示例设计轨迹的基本步骤。在此方法中，地形单元被分组成大的正方形单元，每个单元要么完全被阻塞，要么完全未被阻塞，并且包含四个最初离散的单元格（图1(b)）。更准确地说，阻塞区域不能小于网格单元大小的4倍，这是该算法的唯一要求。接下来，每个未被阻挡的大单元格被转换成一个节点（图1(b)），并为每个相邻的单元格引入一条边。对于产生的图，使用任何最小生成树算法，如Kruskal算法或Prim算法 [33]，构建最小生成树，如图1(c)所示。然后，机器人沿着（逆）顺时针方向绕过跨越树（图1(d)）。生成树的环周遍历产生了一个简单闭合路径$X_1^*$，从覆盖时间的角度来看，这是最优解。

5人减小原始的mCPP问题

利用STC算法在一个机器人情况下的发现结果，原始的mCPP问题可以被简化为：

$$\begin{matrix} minimize\ max_{i\in \{1,\cdots,n_r\}}\\ L\\ subject to \ L_1\cup L_2\cup \cdots \cup L_{n_r} \supseteq \mathcal{L} \tag{8} \end{matrix}$$

其中$L_1\cup L_2\cup \cdots \cup L_{n_r}$表示机器人集合（而不是路径）。
下一步，可以使用$n_r$个STC算法实例在完全分布式的情况下计算这些集合内机器人的准确路径（问题（7））。因此，利用STC算法允许消除关于生成的机器人集合的严格邻接约束（定义2）。换句话说，只需解决在$\mathcal{L}$中构建$L_i$集合的问题，而不需要考虑实际机器人在其中的移动。

在本节的其余部分中，我们将研究必须满足的基本条件，以保证对于整个mCPP（6）问题的最优解。

定义3：

选择$L_1\cup L_2\cup \cdots \cup L_{n_r}$组成mCPP的最优解，如果满足以下条件：

1. $L_i\cap L_j = \emptyset, \forall i,j\in 1,\cdots,n_r, i\neq j$
2. $L_1\cup L_2\cup \cdots \cup L_{n_r} = \mathcal{L}$
3. $|L_1|\approx |L_2|\cdots |L_{n_r}|$
4. $L_i$ is connected $\forall i\in 1,\cdots,n_r$
5. $\mathcal{X}_i(t_0)\in L_i$

第一个条件确保每个单元格必须严格包含在一个机器人的集合中，构成生成解的非回溯保证。第二个条件要求所有$L_i$集合的并集必须包含需要覆盖的区域中的每个未被阻挡的单元格（3），并描绘了完整性的基本覆盖目标。第三个条件通过确保每个机器人集合中的单元格数$|L_i|$大致相同，确立了多机器人动力学的充分利用。第四个条件声明了每个机器人集合内部的单元格应该是紧凑的，形成一个坚实的子区域。换句话说，这个条件确保了划分是绝对公平的，并保证了无缝导航方案，在空间上有凝聚力的区域内进行。根据该声明，没有任何机器人可以花费额外/非包容时间在未连接的区域之间移动。最终条件规定每个机器人的初始位置$\mathcal{X}_i(t_0)$必须包含在其自己的集合$L_i$上，提供了最终的有效层，确保零准备时间和能量。任何能够构建$L_i$集合并确保定义的3个条件的算法都可以与STC结合使用，构建原始mCPP问题（6）的最优解。

关于这些解的存在性，文献[27]已经证明，对于任何多边形和任何分区数量，都存在不需要凸片的公平分区。在此制定的问题是上述问题的一个变体，具有一个额外的条件，表示将多边形的任意点包括在每个分区内。显然，上述问题并不总是有一个解，强烈依赖于需要包括在产生的公平分区中的任意点的排列。问题的整体表述以及所提出的算法是指至少存在一个最优解的情况。

6 基于机器人初始位置的区域划分（DARP）

本部分介绍了基于机器人初始位置的区域划分（DARP）算法，这是一种特别定制的、可以保持最优性的技术，将地图划分为$n_r$个机器人独占的区域。首先，DARP算法采用以下单元格对机器人进行分配方案。对于每个第$i$个操作机器人，都维护一个评估矩阵$E_i$。这个评估矩阵$E_i$表示每个单元格与第$i$个机器人的初始位置$\mathcal{X}_i(t_0)$间的可达性等级（例如，距离）。在每次迭代中，赋值矩阵$A$如下：

$$A_{x,y}={\begin{matrix} argmin \\ i\in \{1,\cdots,n_r\} \end{matrix}} E_{i|x,y}, \forall (x,y)\in \mathcal{L} \tag{9}$$

然后，每个机器人的区域$L_i$可以根据赋值矩阵$A$直接计算如下：

$$L_i = \{(x,y)\in \mathcal{L}:A(x,y)=i\}, \forall i\in \{1,\cdots, n_r\}\tag{10}$$

此外，每个机器人分配的单元格数量可以定义为$L_i$的基数

$$k_i = |L_i|,\forall i\in \{1,\cdots, n_r\}\tag{11}$$

通过采用以上单元分配策略，无论机器人的评估矩阵$E$如何，定义3的第1、2和5个条件总是得到满足。具体来说，一个单元只能被分配给一个机器人（第1个条件），每个单元都已分配给某个机器人的操作计划（第2个条件），并且假定初始机器人位置总是分配给相应的机器人区域（第5个条件）。简言之，DARP算法是一个迭代过程，它以协调的方式适当地修改机器人的评估矩阵$E$，以满足其余两个(在许多情况下相冲突的) 要求。

此外，上述单元分配策略自动承担了与机器人轨迹时间调度相关的额外任务。如果允许机器人占据相同的单元，则应该进行细致的分析以防止机器人之间的碰撞。这个事实可能会导致整体解决方案质量的严重降级，即使集合 $L_i$ 相等的情况下也是如此。

6.1 等分空间

最初，机器人评估矩阵$E_i$仅包含距离信息

$$E_{i|x,y} = d(\mathcal{X}_i(t_0),[x,y]^{\tau}),\forall i\in \{1,\cdots, n_r\}\tag{12}$$

其中$d(\cdot)$表示选择的距离函数（例如欧几里德）。因此，初始分配矩阵$A$(9) 应为经典的$Voronoi$图。

DARP算法的核心思想是，可以通过一个名为$m_i$的项如下所示，将每个评估矩阵$E_i$适当地“校正”，

$$E_i = m_iE_i\tag{13}$$

其中$m_i$是第$i$个机器人的标量校正因子。

定义 3 的第三个条件等价于最小化

$$J=\frac{1}{2}\sum_{r=1}^{n_r}(k_i-f)^2\tag{14}$$

其中 $f$ 表示全局“公平份额”：$f = l/n_r$（未占用单元格数除以机器人数）。

可以采用标准的梯度下降方法更新$m$,即

$$m_i = m_i-\eta \frac{\delta J}{\delta m_i}, \eta >0,\forall i\in \{1,\cdots, n_r\}\tag{15}$$

当试图最小化代价函数（14）的值时会遇到两个缺点。首先，${\delta J}/{\delta m_i}$无法通过代数计算获得，因为不存在关联$J$和$m_i$的解析形式。另一方面，无法保证$J$仅有一个（全局）最小值。

为了克服以上问题，采用循环坐标下降（CD）方法[35，算法1]。坐标下降算法通过沿坐标方向或坐标超平面连续执行近似最小化来解决优化问题。全局成本函数在固定其余坐标为其已更新的值的情况下，沿着每个坐标轴循环最小化。每个这样的子问题都是一个标量最小化问题，因此通常可以比完整问题更容易地解决。

首先，该函数的全局最小值将始终在$k_1=k_2=\cdots=k_{n_r}=f$的情况下。因此，如果我们求解$n_r$单维度优化问题，可以获得（14）的全局最小值，其目标函数如下所示：

$$J_i = \frac{1}{2}(k_i-f)^2 \tag{16}$$

通过应用上述变换，我们可以实现以下：首先，上述搜索是在局部最小自由空间中进行的。

引理1 对于(16)的所有子问题而言，它们对应的可控参数$m_i$是凸的。

证明：假设在前一次迭代中，第$i$个机器人基于其评估矩阵$E_i$，所占用的单元格少于所需的阈值 $( < f)$。根据公式 (13) 和 (9)，可以看出，相应的校正因子 $m_i (<1)$ 的小幅减小 将会导致分配的单元格数量 $k_i$ 的增加，假设其他机器人的评估矩阵 $E$ 保持不变。因此，对应的目标函数 $J_i$(16) 会降低。但是，如果我们过度降低 $m_i$ 因子，将会分配许多单元格给第 $i$ 个机器人。此时，$J_i$ 将重新增加，因为 $k_i$ 将大于$f$。从这点来看，如果我们继续降低 $m_i$，第$i$个机器人将被分配更多的单元格，因为 $k_i$ 只能在响应于 $m_i$ 降低上升。当第$i$个细胞分配所有可用单元格$(l-n_r+1)$时，$J_i$ 的值会饱和，此后至少减小 $m_i$ 对 $k_i$ 和 $J_i$ 都不会再有影响。因此，$J_i$将随着$m_i$的减少而单调增加，直到最大可能的

$$J_i|_{k_i=l-n_r+1}=\frac{1}{2} (\frac{(l-n_r)(n_r-1)}{n_r})^2$$

因此，先前遇到的最小值就是全局最小值。如果我们假设第$i$个机器人被分配给了比预期多的单元格，那么证明仍然成立。

此外，对于每个目标函数（16），可以直接计算出$m_i$的更新规则，如下所示：

$$\begin{matrix} m_i = m_i-\eta \frac{\delta J_i}{\delta m_i}\\ =m_i-\eta(k_i-f)\frac{\delta k_i}{\delta m_i} \end{matrix}\tag{17}$$

由于问题的性质，对于$m_i$的$k_i$变化将始终为负数（见引理1中的证明），对于每个机器人（针对给定的子问题（16）），它们的变化几乎相同。此外，两个评估矩阵集$\{E_1,\cdots,E_{n_r}\}$和$\{\alpha E_1,\cdots ,\alpha E_{n_r}\}$，其中$\alpha$表示任意正常数，对应于相同的分配矩阵（9）。因此，可以安全地忽略$|\delta k_i/ \delta m_i|$的影响，并且可以近似为最终更新策略，如下所示

$$m_i = m_i +c(k_i-f) \tag{18}$$

其中，$c$表示正调节参数。

综上，使用引理1，我们可以建立全局代价函数$f$一般可能是非凸的——依赖于机器人和障碍物的形成，有许多局部最小值，每个机器人的贡献$J_i$是关于可控参数$m_i$ 的凸函数 。正如[37]所示，循环坐标下降方法，在该属性持有的情况下，能够收敛到全局最优解集$m^*$

$$J(m^*) \leqslant J(m),\forall m\in dom(J) \tag{19}$$

与初始评估矩阵$E_i$(12)有关。

6.2构建空间连接区域虽然，

上述过程可以很容易地收敛到在不同机器人之间共享可用单元格，但无法保证每个机器人的子区域的连续性(条件4，定义3)。为了处理这种情况，对于每个占据多个不同区域的第$i$个机器人，引入以下矩阵

$$\mathcal{C} = min(||[x,y]-r||)-min(||[x,y]-q||),\forall r\in \mathcal{R}_i, q\in \mathcal{Q}_i \tag{20}$$

其中$\mathcal{R}_i$表示第$i$个机器人实际所处的单元格的连接集合$(\mathcal{X}_i(t_0))$，$\mathcal{Q}_i$表示所有其他连接集合的联合，这些集合已分配给第$i$个机器人，但它们与$\mathcal{R}_i$集不具备空间连接性。在更抽象的概念化中，$\mathcal{C}_i$是按照一种方式构建的，以奖励第$i$个机器人位置子集周围的区域，并惩罚其他未连接子集周围的区域，逐渐构建一个封闭的区域。如果所有分配给第$i$个机器人的单元格都属于同一封闭形状区域，那么$\mathcal{C}_i$被设置为全一矩阵。

第$i$个评估矩阵中的最终更新计算为：

$$E_i = \mathcal{C}_i \odot (m_i E_i\tag{21}$$

其中$\odot$表示逐元素乘法。前几个小节的发现在图2中进行了说明，其中呈现了所提出算法的流程图。

6.3性能讨论

虽然概念简单，但DARP算法旨在在至少存在一个最佳单元分配的情况下提供该分配。图3展示了一个示例，其中地形由$42\times 42$个单元格组成，机器人数量为 $n_r=5$。初始机器人位置被压缩在操作区域的左下空间内，其尺寸为$10\times 10$个单元格。每个子图展示了对应迭代中分配矩阵$A$（9）的状态。显然，该算法在260次迭代后终止，满足了定义3的所有条件。

值得强调的是，与机器人的连续评估矩阵$E_i$不同，最终分配给每个机器人的子区域可能是任意不连通的（至少是临时的，例如图3(b)）。实际上，这个DARP算法的关键特点是允许逐步向每个机器人的子区域中加入任意位置的单元，从而逃避局部最小值。更具体地说，DARP算法能够暂时违反关于每个机器人分配矩阵连通性的条件，随后通过强化机器人评估$E_i$的原始子区域（机器人实际所在的子区域）来逐步消除不连通区域的存在。当机器人集合$L_i$内部的连通性被恢复时，评估矩阵$E_i$的形式将完全改变，并且理想情况下趋近于最优单元分配。

所提出的算法与一般的局部搜索算法不同，它改变当前状态的方式主要是基于全局最优状态，而不仅仅是通过评估当前状态和候选状态的信息。此外，DARP算法近似于梯度下降算法的行为，具有有效搜索和达到全局最优解的额外能力，即使在存在多个局部最小值的情况下也能实现。

6.4 从近似角度分析计算和存储复杂度

算法的存储需求可以直接计算，因为它使用具有尺寸$(n_r \times n)$的常数个矩阵。换句话说，算法的存储复杂度与输入大小$(n_r \times n)$成线性关系，即$\mathcal{O}(\beta \times n_r \times n)$。

主要优化循环执行了$\alpha \times n_r \times n$次操作，其中$\alpha$是一个常数，因此算法的计算复杂度为$\mathcal{O}(\alpha \times n_r \times n)^6$。然而，主优化循环的执行次数（MaxIter）不是固定的或线性的，而是以非线性方式取决于当前问题的特定特征。由于无法找到将最大所需（主优化循环）迭代次数与机器人数量$n_r$，初始部署$\mathcal{X}_i(t_0)$和网格大小$n$相关联的闭合形式，因此采用了以下算法计算需求的近似方案。

进行了一系列模拟，以测量构建最佳解决方案（定义3）所需的最大迭代次数（主优化循环）。对于每个配置（$n_r$和$n$），都通过使用不同的随机选择初始$\mathcal{X}_i(t_0)$来重复实验以验证结果，以便能够逼近最坏情况下的MaxIter。

请注意，由于初始机器人位置的可能组合数量巨大，因此实际计算每种配置的最坏情况在实践中是不可行的。尽管如此，在每个不同的设置中，随机创建的实例数量与输入参数（$n_r$和$n$）成比例。通过这样做，可以确保计算出的最坏情况复杂度代表可能发生的不同配置数量。每种配置的实验次数从50为$\{n_r = 3, n=500\}$开始，达到$\{n_r = 20, n=5000\}$的5000次，构建了超过120000个不同的实验。

为了呈现DARP复杂性的总体近似（$MaxIter\times n_r\times n$)，对于每个$\{n_r,n\}$方案，提取所需迭代次数MaxIter的最差情况（最大值）。这些情况针对每个方案被转化为曲面，采用多项式最小二乘曲线拟合技术进行绘制。在图4中用蓝色表示产生的曲面，其中操作需求的增长与输入量在线性和对数尺度上同时表示。此外，为了评估生成的复杂度结果，使用了一些多项式曲面。具体而言，黄色、品红色和绿色分别说明了$f_1(n_r,n)=n_r^2\times n^2,f_2(n_r,n) = n_r^3\times n^2$和$f_3(n_r,n) = n_r^2\times n^3$
情况下的复杂度曲线。这种表示的证据表明DARP的复杂度对于问题的输入$(n_r\times n)$是三次的，因为在$n_r^3\times n^2$曲线下，复杂度曲线的近似值严格受到限制，至少在最大模拟参数$n_r=20$和$n_r=5000$的情况下如此。

总之，在这一部分中，值得一提的是所提出的算法无法绕过mCPP问题的NP本质，但在特定的（实际感兴趣的）输入下，它提供了一个近似多项式的算法。如果机器人的大小和单元的数量增长超过上述输入的数量级，算法可能会失去其多项式行为。

6.5 超越经典的mCPP

值得指出的是，DARP算法是一种基于优化的算法，它允许包括其他次要目标，具体取决于最终的多机器人应用，如机器人子区域的平滑等，只需修订适当的性能标准。在文献中，mCPP问题通常如第3节所述，它要求产生平衡的路径，以便利用所有可用的机器人功能。然而，在某些情况下，特定的机器人特性（例如感知模块，电池寿命等）会对不同机器人之间产生不同的利用率。所提出的方法能够通过适当修改$J_i$(16)的计算来直接包含这些额外的信息。更精确地说，第$i$个机器人的目标函数将按照以下方式轮换：

$$J_i= \frac{1}{2}(k_i-p_i)^2 \tag{22}$$

其中$p_i$是第$i$台机器人需要根据其能力或限制覆盖的地图部分$(\sum _{i=1}^{n_r}p_i=1)$。

然而，为了与普通的mCPP形式保持一致，我们仅限于对只考虑平等单元格划分的情况下（以第8节中模拟评估为例）。

7. 提出的多机器人覆盖路径规划算法概述

本节总结了将DARP和STC算法的发现融合起来，针对mCPP问题（6）提出的完整算法。所提出的算法分为两个阶段：在第一阶段中，DARP算法将$\mathcal{L}$集合单元格划分为$n_r$个互斥的区域$L_i$，用于每个可用的机器人，如第6节所述。这个过程的结果$L_i$分别作为每个机器人的操作区域（第4节）。

在应用DARP算法和相应生成的$L_i$集合之后，原始的多机器人优化问题（6）被降级为$n_r$个单机器人CPP问题，减轻了其组合爆炸性的复杂性。这些问题都可以表示为最小化

$$\begin{matrix} \begin{matrix} minimize \\ X_i \end{matrix} |X_i| \\ subject \ to \ X_i \supseteq L_i \end{matrix} \tag{23}$$

其中$X_I$代表定义2中的机器人路径。如第4节所示，利用STC算法可以在栅格连接环境中解决这类优化问题（单个机器人的情况）。

即使最终路径$\{X_1,X_2,\cdots,X_{n_r}\}$是以完全分布的方式构建的，所产生的解的并集实际上是等式（6）问题的最优解，没有在解的质量或广泛性上做出任何妥协。本文提出的算法可以通过初始构建$L_i$集合来实现，从而满足第3个定义条件。算法不仅可以完全并行化，而且大大降低了初始mCPP问题的复杂度，使其与STC算法的数量级相当。

图5展示了所提出的算法的一个执行示例。子图5(a)展示了初始机器人位置以及固定障碍物的位置。子图5(b)表示采用图2中描述的区域划分方法得出的结果，每个子区域的最小生成树用子图5(c)表示，并提供了关于$\mathcal{L}$内部节点的空间信息。最终，所提出的算法允许机器人沿着绕过相应生成树的路径移动，如子图5(d)所示。值得注意的是，生成的路径构成了一个最优解，因为分配给每个机器人的单元格数量为$[12 13 12 12 12 13 12 12 12]$（定义3，条件3）。对应的求和式转换为操作世界的形式，即 $4 (127 + 132) = 440$，这正是需要覆盖的细胞数（定义3中的条件2）。

8模拟结果

本节介绍提出的DARP+STC算法与两种最先进方法（MFS和Optimized MSTC，详见相关工作）的比较研究。为了产生可比较的结果，我们采用与[39]相同的模拟设置。具体来说：

• 地形的大小始终为[行数；列数] = 98x98。
• 我们考虑两种地形：1）空地形[empty]和2）其10%的单元被障碍物占据的地形[outdoor]。障碍物的布置采用随机均匀分布。
• 机器人的数量从2、8、14到20个不等。
• 机器人的初始放置可以根据它们之间的最大距离（聚类）分为三种不同类型。具体来说，两个机器人之间的最大距离可以是1）最大地形维度的30% [30]或2）60% [60]，或3）没有距离限制（自由选择）[none]。

为了与MFC和优化的MSTC算法进行公平比较，我们对每个场景重复了100次。每种不同评估场景和算法组合的结果如表1所示，报告了所有机器人的最长 [Max] 和最短 [Min] 路径长度所花费的最大和最小覆盖时间。同时，对于每个场景，我们提供理想的覆盖时间 [Ideal Max]，它代表了问题的最优解。换句话说，这个值只是通过将未占据的单元格数除以机器人数（f）来计算。显然，离理想覆盖时间越远，机器人路径之间的差异就越大，导致不平衡、次优的路径。每种场景对于每种算法的总体得分，相对于理想覆盖时间，在 [Ratio] 列中给出，报告了实际（最大）行驶路线和理想覆盖时间之间的比率。

直接观察表明，所提出的DARP+STC算法的性能似乎不受机器人数量、障碍物和初始机器人聚类的影响，因为它在不同场景下的比率几乎相同。此外，所有的结果都接近于[Ideal Max]，两个机器人路径之间的最大差异最多只有4个单元，与机器人数量和/或网格大小无关，即 $|||X_i|-|X_j|||\leq 4,\forall i,j\in 1,\cdots, n_r$。以上有效性界限可以直接从DARP算法的最优性保证中得出。DARP算法计算了具有至多1个单元差异的$L_i$区域，这些区域涉及不同的第$i$个机器人（见图2）。在应用STC算法（第4部分）之后，这种最大差异被转化为4个单元。总体而言，这些发现通过实验证实了所提出算法的性能。

上述最佳性能并非没有缺点。在所有情况下，会将导致次优结果的初始配置从测试用例池中删除，而另外两个算法都能够直接生成一些次优操作计划。在附录A中提供了不能获得最优解的情况的适当分类，并提供了与所提出的方法相一致的初步解决方案。

9 结论和未来工作

本文提出的方法协调多个机器人团队的最佳协调，以完全覆盖感兴趣的区域。在初步分析中，通过明确定义必须保持的确切属性，将基础mCPP问题转化为约束满足问题，该方法的核心是DARP方法，一种搜索算法，它使用循环坐标下降方法为每个机器人找到最优单元分配，考虑到机器人的初始位置和障碍物的形成。 DARP算法的结果构成每个移动机器人的一组排他性操作区域。这些定义良好的区域被传递给每个机器人的规划器，通过采用STC算法，计算覆盖分配区域的确切路径。整体导航方案实现遍历完整个操作区域，从确切的初始机器人位置开始，无需返回已访问的区域。据我们所知，文献中没有其他方法能够同时展示所有上述特征。

留下了许多探索领域供未来的研究。其中一个方向可以是放松第3条定义中的一个或多个约束条件。例如，取消非回溯属性，可以构造出仅为凸形的路径（更整洁），并且STC的形状可以适当修改，以便最小化机器人路径中的转弯。此外，我们打算在我们的方法中再增加一个阶段，负责自动识别/检测非最优情况，以直接应用适当的预定义解决方案。最后，我们的未来计划包括开发DARP算法的在线版本，以便能够在完全未知的地形内操作。在没有最优解的情况下：

A 最优解不存在的情况

问题的公式，如第3节中所定义的那样，可能会包含一些情况，其中障碍物或机器人的指定位置会阻碍对一个或多个单元格的访问。然这些情况被认为超出了本文的范围，并且被排除在考虑的场景之外，但在附录中我们将它们归类并提出一些初步的解决方案，与所提出的方法相一致。

第一类情况包括由于机器人的初始放置位置而无法获得mCPP问题的最优解（子图6（a））。在这些情况下，可以花费一些准备步骤来重新安排机器人的位置，以将问题转化为可解决的场景（通过所提出的DARP+STC方法）。这种重新排列并不简单，并形成另一个优化问题，其中目标是找到最小路径以使问题可处理。

另一种情况是，覆盖任务无法在可用机器人之间平等分配，在一个或多个机器人被困在非避免的有界子区域内的情况下发生（子图6（b））。在这些情况下，可以直接应用所提出的方法，次数等于有界区域的数量，并且再次保证可以获得最优解。显然，在这种情况下，很难在所有机器人规划器的路径长度上达到平衡。实际上，现在产生的路径长度高度依赖于相应有限面积的大小。然而，处于相同子区域中的不同机器人应该具有几乎相同的工作量（定义3，条件3）。

此外，还有不可恢复的情况，其中一个或无法到达更多子区域（子图 6(c)）。在这种情况下，所提出的算法可以应用于剩余地形，确保最佳机器人路径构建。最后，可能会出现上述情况的组合，然后可以应用上述解决方案的混合版本

值得强调的是，在所有这些情况下，所提出的方法不能提供最佳路径集合，并不是一种弱点，而是由于最优解，并不符合定义 3 中所定义的属性。