0. 简介

作为路径规划而言，不单单有单个机器人自主路径规划，近年来随着机器人行业的兴起，多机器人自主路径规划也越来越受到关注，对于多智能体寻路(MAPF)。一般的操作会给定一个地图、机器人集群、以及它们的初始位置和目的地，MAPF会最终输出一组没有碰撞的路径，用于控制机器人集群完成运动。《Iterative Refinement for Real-Time Multi-Robot Path Planning》文中认为迭代细化MAPF是可取的，原因有三:1)多智能体优化是棘手的，2)次优解可以立即获得，3)在线场景中需要考虑的时间有限，所以要求MAPF是实时规划的。

文中的方案使用次优MAPF求解器来快速获得初始解，然后迭代两个过程:1)选择代理子集，2)使用最优MAPF求解器来优化所选代理的路径，同时保持其他路径不变。由于单个最优求解器只会优化所选代理机器人的路径，因此该方案可以快速生成足够有效的解决方案，同时提供高可伸缩性。相应的代码也在Github上开源了，可以这么说，这套方法还是很有意义的，

1. 文章贡献

1. 文中提出了一个通用的框架，基于现有求解器的有效组合可以快速的提供anytimeMAPF求解。 文中的框架首先使用次优MAPF求解器快速获得初始可行解，然后使用最优MAPF求解器找到良好的邻域解。精确地说，该框架通过选择一组代理并使用最优求解器来细化它们的路径，同时保持其他路径固定，迭代地细化解决方案。尽管在细化过程使用了最优求解器，但是每次细化都能快速完成，因为它解决的是一个子问题，其大小取决于选择的代理机器人数量，通常比原问题小得多。我们还提出了合理的候选人，用于选择代理子集。
2. 文中研究了在各种基准测试中该方法的有效性，并经验地发现，在小型实例中，该框架在短时间内几乎收敛到最优，并且即使对于非常大的实例（即大环境和/或许多代理）也保持着高效响应。换句话说，它比先前的技术带来了许多实际优势。
3. 从更广泛的角度来看，我们的研究也可以被看作是解决一个非常大规模的邻域搜索[24]。更接近我们的概念，Balyo等人[25]研究了针对独立于领域的规划问题的局部重新规划，以优化最长时间。它重复以下操作：创建一个子问题，通过基于SAT的技术获得一个最优子解，并用新的解决方案替换原来的部分解决方案。
   

2. 主要框架

该框架首先使用次优MAPF求解器获得初始解决方案，然后迭代地细化解决方案的选定部分，即选定代理子集的路径，使用最优MAPF求解器。我们在算法1中给出了伪代码

下面我们来详细的看一下，第1行输入的是次优求解器快速获得初始可行解决方案。在第二行中，我们称所用的次优MAPF求解器为初始求解器。如果初始求解器未能获得解决方案，则框架以失败告终;否则，开始细化，也就是3-6行里面的内容。细化重复以下两个过程，直到中断:

1. 使用当前解决方案π [第4行]创建修改集M ⊆ A。
2. 使用最优MAPF求解器[第5行]改变M中代理的路径来细化当前解决方案π。我们称这个求解器为细化求解器。细化求解器只改变M中代理的路径；M中代理以外的路径不变。细化继续进行直到中断，例如超时、达到预定迭代次数、不再有改进时、用户中断等。
   最终，框架返回最终解决方案[第7行]。

上文中提到的初始求解器可以是任何次优MAPF求解器，只要它能提供可行解即可。作为细化求解器，最好使用从最优求解器改编的版本。改编很简单；让它为M中的代理规划路径，并将其他代理视为动态障碍。例如，对于CBS算法，只为M中的代理求解MAPF，同时禁止低级别搜索使用M中代理以外的所有空间时间对。确切地说，细化求解器并不局限于最优MAPF求解器（可以使用单机器人的求解器）。要求是细化解决方案从原始解决方案不变差。考虑到M中代理以外的路径成本不变，要求是M中代理的路径成本在细化之前和之后都不会增加。

3. 细化求解器性质与要求

下面有一些性质显然是由对细化求解器的要求所设定的。

3.1 定理1(单调性)：

对于算法1中的每次迭代，解决方案成本都是不增加的。
一个关键点是细化求解器重新计算所选子集M（一部分机器人）中代理的路径，而不是所有代理的集合A（所有机器人）。与直接使用最优求解器解决原问题相比，细化求解器在每次迭代中解决的问题明显小得多，确保框架即使对于大量代理也是可扩展的。同时下面有几种方法来有效的降低计算的时间。

A.提前终止（早停）
即使细化求解器解决的子问题与原问题相比计算量已经是较小的了，但是如果本身的|M|仍然太大，细化仍然可能需要很长时间。在这种情况下，最好通过返回当前解决方案来中止当前细化，然后使用新的集合M开始新的迭代。标准可以是超时或使用细化求解器中搜索树大小的阈值。

B.局限性
作为一个限制，该框架可能具有局部最小值，并且没有来自最优解的次优性界限。
命题1(没有次优性界限)：考虑最优成本c^_。在算法1中，总是c≤wc^_，除非将A本身选为修改集M，其中c是每次迭代中的解决方案成本。
证明：考虑图1中的一个例子。假设初始解决方案将a_1分配给顺时针路径(成本：k)和a_2分配给逆时针路径(成本：1)。当k≥6时，这就不是最优的模型了，因为a_1可以采取逆时针路径，并经过a_2来移动到目标处（总成本：6）。除非M ≠ A，否则细化的解决方案不变。假设w≥1，使得c≤wc^*。我们可以取任意k，与w的存在相矛盾。

3.2 定理2（局部最小值存在）

根据初始解决方案，除非将A本身选为M，否则可能无法达到最优解。

注意，当M = A时，细化求解器必须能够解决原始MAPF问题。

4. 修改集选择

我们从上面可以看到在优化的时候，修改集的选择会影响到整个系统的性能，而如何有效的选择修改集这个就非常重要了。修改集是框架的重要组成部分，其设计会影响计算时间和解决方案质量等性能。本节定义了几个选择规则，以提供合理的候选修改集。

4.1 随机的

一个天真的方法是随机挑选一个代理子集。然后，修改集的大小M就是一个用户指定的参数。需要注意的是，大的M修改有机会在一次迭代中很大程度上降低成本，但由于子问题变得具有挑战性，因此需要花费时间进行细化。

4.2 单一代理

这个规则总是选择一个单一的代理，因为M可以被视为前一个规则（随机）的一个特例。即使只有一个代理，成本也可能因细化而降低。在这种情况下，细化只是一个单一代理的路径寻找问题，可以在没有MAPF求解器的情况下有效地计算出来，例如，通过A^∗来计算即可，可以简化为一个机器人在其余障碍物（机器人）中规划出来的最优路径。

4.3 着重目标

考虑图2中的一个例子。假设当前的解决方案是π1 = (v2, v3, v6, v3, v3) 和π2 = (v1, v2, v3, v4, v5) 。代理人a_1不能实现更短的路径，因为代理人a_2在第2个时间步长(第三个值)使用了a_1的目标（即v3）。一般来说，对于a_i来说，理想成本dist(π_i[0], g_i)和实际成本成本(a_i, π)之间存在差距的一个原因可能是另一个代理人a_j在时间步骤t≥dist(π_i[0], g_i)时使用了a_i的目标（即g_i）。至少在t之前，a_i不能到达g_i并留在那里。在这种情况下，需要联合完善a_i和a_j的路径。这一观察促使我们创建了一个简单的规则，将当前的解决方案π和一个代理a_i作为输入。

4.4 围绕目标的局部修复

这是上一条规则（关注目标）的一个特例。再次假设图2的例子；π1=(v2, v3, v6, v3, v3)，π2 = (v1, v2, v3, v4, v5)。在聚焦目标（focus-at-goals）中，a_1的M是{a_1, a_2}，因此，细化求解器必须用两个代理解决一个子问题；然而，这种努力可以减少。考虑为a_1获得一个更好的路径，忽略π_2。在这个例子中，通过目标周围的局部修复获得一条新的路径，不需要搜索；(v2, v3, v3, v3, v3)。接下来，为a_2计算一条路径，同时避免与这条新路径和其他代理的路径发生碰撞。如果两条新路径的成本之和小于原始路径，就用新路径替换π_1和π_2。由于搜索工作量减少，预计细化工作会更快完成。一般来说，当π_i=（…，g_i，v，g_i，…，g_i），其中v ≠ g_i，而另一个代理a_j在该时间步长使用g_i时，可以应用这一规则。

4.5 使用MDD

给定一个单一的路径成本c，从π_i[0]到g_i的一组路径可以紧凑地表示为一个多值决策图（MMDD）[35]；一个有向无环图，其中一个顶点是一对位置v∈V和一个时间步长t∈N。

1. 在该时间段从起点出发的可达位置；
2. 从该时间段到目标的可达位置。
   让MDDc i是一个成本为$$c$$的$$a_i$$的MDD，图3显示了两个例子。$$MDD^2_1$$和$$MDD^3_1$$。MDD在MAPF求解器中经常使用[28], [36]。

使用MDD^c_i，其中dist (π_i[0], g_i) ≤ c < cost (a_i, π)，可以检测到一组干扰π_i的代理。见图3中的一个例子。假设当前的解决方案是π_1 = (v3, v3, v4, v5) 和π_2 = (v7, v4, v2, v1)。考虑用π_2来更新MDD^2_1；删除MDD^2_1中与π_2相撞的顶点，即(v4，1)。然后，删除所有不满足第一个操作带来的两个条件的多余顶点：（v3，0）和（v5，2）。现在，事实证明，a_1不可能以2的代价达到其目标，因为没有剩余的顶点。换句话说，π_2是为了防止a_1达到更小的成本；因此，π_1和π_2应该被共同完善。我们在算法2中描述了程序

4.6 使用瓶颈代理

再考虑图3的例子；π_1 = (v3, v3, v4, v5) 和π_2 = (v7, v4, v2, v1)。如果去掉π_2，a_1可以走一条更短的路径，这意味着，a_2是a_1的瓶颈。有机会通过与这样的瓶颈代理和没有代理也能走较短路径的代理联合精炼来减少成本。我们在算法中描述这个概念

4.7 构成

每条规则都可能有合适的情况，例如，专注于目标的规则（第四章C节）在创建修改集方面不需要花费任何费用，但当解决方案在某种程度上已经很有效时，它在检测有效集方面可能就很弱。另一方面，使用MDD的规则（IV-E）需要时间，但它们在检测有效集合方面的预期很高。因此，一个有希望的方向是复合这些规则，即执行第一条规则，直到预期没有改进，然后切换到第二条规则；与上述相同。