PBS 论文

摘要

---

我们研究多智能体寻路（MAPF）的优先规划。现有的优先MAPF算法依赖于经验法则启发式和随机分配，以先验地确定所有智能体的固定总优先级排序。我们转而在新颖的、系统性的、冲突驱动的组合搜索框架中探索所有可能的局部优先级排序的空间。在各种实证比较中，我们展示了最先进的解决方案质量和成功率，其运行时间通常与现有算法相似。我们还开发了新的理论结果，首次探讨了优先规划在完整性和最优性方面的局限性。

引言

---

多智能体路径寻找（MAPF）是一个在许多应用中出现的协调问题，例如飞机牵引车（Morris et al. 2016）、仓库和办公室机器人（Wurman, D’Andrea, and Mountz 2008；Veloso et al. 2015）、游戏角色（Ma et al. 2017c）以及其他多智能体系统（Ma et al. 2017a）。该问题是在给定图中，为多个智能体从其给定的起始顶点规划无碰撞路径至其给定的目标顶点（Ma and Koenig 2017）。解决方案的质量通过流时间（所有智能体到达其目标顶点的到达时间之和）或完工时间（所有智能体到达其目标顶点的到达时间的最大值）来衡量。MAPF在最优求解方面是NP难的（Yu and LaValle 2013b; Ma et al. 2016b）。它可以通过归约到其他得到充分研究的组合问题（Surynek 2015；Yu and LaValle 2013a；Erdem et al. 2013）和专用MAPF算法（Standley and Korf 2011；Luna and Bekris 2011；Goldenberg et al. 2014；Sharon et al. 2013；Wagner and Choset 2015；Sharon et al. 2015）来解决，如几篇综述所述（Ma et al. 2016a；Felner et al. 2017）。

优先规划多代理寻路算法（Silver 2005；Sturtevant and Buro 2006）是解决多代理寻路问题最高效的算法之一。它们基于以下简单的优先规划方案（Erdmann and Lozano-Perez´ 1987）：为每个代理分配一个唯一的优先级，并按优先级顺序计算从其起始顶点到目标顶点的最小成本路径，该路径不与所有具有更高优先级的代理（已规划）的路径发生碰撞。现有的（标准）优先规划多代理寻路算法以其较短的运行时间而闻名，并经常被用作多代理寻路求解器的一部分（Velagapudi, Sycara, and Scerri 2010；Wang and Botea 2011；Cap,´ Vokr´ınek, and Kleiner 2015）。然而，它们预先确定了代理的预定义总优先级排序，因此可能导致解决方案质量较差，甚至在可解的多代理寻路实例中也无法找到任何解决方案，而不同的总优先级排序本可以产生更高质量的解决方案。

在本文中，我们因此将优先规划的概念从具有固定总优先顺序的规划推广到所有可能的总优先顺序的规划。理论上，我们首次为讨论优先规划的局限性建立了一个概念框架。例如，我们识别了优先规划多智能体路径查找（MAPF）算法产生的解集，并根据不同优先顺序的完备性和最优性保证来表征MAPF实例的类别。我们还开发了两种优先MAPF算法，通过系统地探索“良好”的优先顺序来提高优先规划的实用性。我们的第一种算法，基于冲突的搜索（CBSw/P），是对基于冲突的搜索（CBS）（Sharon et al. 2015）的改编。它使用系统性的最佳优先搜索来惰性地探索所有总优先顺序的空间，并且仅在代理路径发生冲突时才引入代理的有序对。我们的第二种算法，基于优先的搜索（PBS），使用系统性的深度优先搜索来惰性地探索所有总优先顺序的空间。它可以接受用户指定的偏序优先顺序作为输入，动态地向其添加新的代理有序对，并规划与由此产生的偏序优先顺序一致的路径。我们证明了标准的优先MAPF算法是PBS的一个特例。在实践中，我们在大量的MAPF实例上评估了我们的优先MAPF算法。我们发现CBSw/P通常计算出最优或接近最优的解，并且比最先进的CBS版本（Felner et al. 2018）更有效。PBS也计算出接近最优的解，并且比CBSw/P更有效。此外，PBS在具有一百多个代理的MAPF实例中保持接近最优和高效，为许多标准优先MAPF算法无法解决的MAPF实例找到了解决方案，并在不到一分钟的时间内解决了具有六百个代理的良构MAPF实例。

问题定义

---

我们将 MAPF 形式化如下：给定一个连通的无向图 G = (V, E) 和 M 个智能体 {ai | i ∈ [M ]}（[M ] = {1, . . . , M }）。每个智能体 ai 都有一个唯一的起始顶点 si ∈ V 和一个唯一的目标顶点 ti ∈ V。在每个离散时间 t = 0, . . . , ∞，每个智能体要么移动到一个相邻的顶点，要么停留在同一个顶点。令 πi(t) 表示智能体 ai 在时间t所占据的顶点。一个规划由一组路径组成，每条路径 πi = ⟨πi(0), . . . , πi(Ti), πi(Ti + 1), . . .⟩ 对应一个智能体 ai，其中 πi(0) = si，并且对于所有时间 t = Ti, . . . , ∞，有 πi(t) = ti。具体来说，智能体 ai 到达其目标顶点的 arrival time Ti 被定义为它到达目标顶点并停止移动的最早时间。顶点碰撞是一个元组 ⟨ai, aj, v, t⟩，其中智能体 ai 和 aj 在同一时间 t 占据同一个顶点 v。边碰撞是一个元组 ⟨ai, aj, u, v, t⟩，其中智能体 ai 和 aj 在同一时间 t 以相反的方向遍历同一条边 (u, v)。一个解是一个由所有智能体的无碰撞路径组成的规划。其质量通过 flowtime ∑i∈[M ] Ti 来衡量，定义为所有智能体到达时间的总和。

优先规划

---

优先规划（Erdmann and Lozano-Perez´ 1987）是一种用于多智能体路径规划（MAPF）的解耦方法，其中智能体根据预定义的总优先级排序进行排序。这个想法很简单：可以为每个智能体单独规划，而不必像耦合 MAPF 算法那样同时为所有智能体计算规划。这意味着首先为最高优先级的智能体规划，并计算其单独最优路径；即它只避开固定障碍物。然后为优先级越来越低的智能体规划，并为每个智能体计算其单独最优路径，该路径不仅避开固定障碍物，还避开与所有更高优先级智能体（视为动态障碍物）的（已规划）路径的碰撞。我们通过使用部分优先级排序来推广MAPF的优先规划。

定义 1.优先排序 ≺ 是 [M ] 上的严格偏序。当且仅当 i ≺ j 时，智能体 ai 的优先级高于智能体 aj。

图 1：用于证明的 MAPF 实例。

它不提供完整性或最优性保证。尽管如此，它因其效率而广受欢迎。其主要挑战在于确定一个良好的优先级排序 ≺≺≺，因为糟糕的排序可能导致低质量的解决方案，甚至导致问题求解失败。全局排序预先为所有代理分配固定的优先级，并在移动开始前解决所有冲突。优先级可以任意分配（Warren 1990；Bennewitz、Burgard 和 Thrun 2002；Silver (2005) 或源于当前问题（Erdmann and Lozano-Perez´ 1987）。例如，优先级也可以使用启发式方法计算，例如到目标顶点的距离（Van Den Berg and Overmars 2005）或偏好某些路径类型而非其他类型（Buckley 1989；Ferrari et al. 1998）。局部排序为某些代理分配临时优先级，以实时解决冲突。此类算法要求代理遵循其分配的路径，并且在达到僵局时，动态分配优先级以确定谁等待（O’Donnell and Lozano-Perez´ 1989；Azarm and Schmidt 1997）。一些现有工作试图对所有总优先级排序的空间进行推理，这在一般情况下是难以处理的，因为存在 M ! 种排列。Bennewitz、Burgard 和 Thrun (2002) 通过在爬山方案的一部分中随机生成几种总优先级排序来探索该空间的一部分。Azarm 和 Schmidt (1997) 枚举了最多三个代理的所有总优先级排序。

理论结果

---

我们现在分析优先级规划在不同类别的 MAPF 实例中关于完整性和最优性的有效性。我们首先将一个众所周知的结果（Erdmann and Lozano-Perez´ 1987）推广到具有部分优先级排序的优先级规划。

定理1. 对于一般的多智能体路径规划（MAPF），具有任意优先级排序 ≺≺≺ 的优先规划是不完备的。

证明. 如图 1(a) 所示的反例仅有的三种可能的优先级排序是 {1 ≺ 2}, {2 ≺ 1} 或 ∅。对其中任何一种的优先规划都无法得到解。接下来，我们定义一类我们称之为 P-可解的 MAPF 问题实例。当且仅当一个 MAPF 问题实例存在一个可以通过优先规划计算出的解时，它才属于此类，即存在一个固定的优先级排序，其中高优先级智能体从不等待低优先级智能体。

定义 2。一个解 L = {πi | i ∈ [M ]} 与优先级排序 ≺≺≺ 一致，当且仅当对于所有满足 i ≺ j 的代理对，通过从代理集合中移除 aj 永远无法改善 ai 在 ti 的到达时间。

定义 3。当且仅当存在一个解 L = {πi | i ∈ [M ]} 与某个优先级排序 ≺≺≺ 一致时，MAPF 问题是 P 可解的。

图 2：用于证明的 MAPF 实例。

例如，对于图 1(a) 所示的 MAPF 实例，不存在任何与任何固定优先级排序一致的解。因此，图 1(a) 所示的 MAPF 实例不是 P 可解的。下一个结果表明，存在 P 可解的 MAPF 实例，其解仅与一个总优先级排序一致。

定理 2. 对于任何给定的优先级排序 ≺≺≺，优先规划对于 P-可解 MAPF 实例类是不完备的。

证明. 图 1(b) 展示了一个仅有一个最优解的 P-可解 MAPF 实例，即

π1 = 〈 (1, 2), (2, 2), (3, 2), (4, 2), (5, 2) 〉
π2 = 〈 (3, 2), (3, 1), (3, 2), (2, 2) 〉. 

该解仅与全优先序 {1 ≺ 2} 一致。对于任何其他优先序，优先规划均不产生解。

下一个结果关注的是良构实例，这是一类对仓库物流至关重要的、可行的且 P-可解的 MAPF 问题（Cap, ́ Vokr ́ınek, and Kleiner 2015; Ma et al. 2017b）。图 1© 展示了一个例子。该类问题的显著特点是，每个智能体都可以在其起始顶点和目标顶点无限期等待，而不会阻塞任何其他智能体。

定理 3. 具有任意给定总优先级排序 ≺≺≺ 的优先规划对于良构 MAPF 实例类是完备的。

证明。给定一个格式良好的 MAPF 实例和任何总优先级排序 ≺≺≺，可以通过以下方式始终计算出一致的解：所有智能体在其起始顶点等待，直到所有更高优先级的智能体到达其目标顶点。然后，该智能体遵循一条个体最优路径从其起始顶点移动到其目标顶点。

下一个结果表明，对于某些 P-可解的 MAPF 实例（包括良构实例），优先规划在所有给定的总优先级排序下都可能产生次优解。

定理 4. 对于 P-可解 MAPF 实例类，优先规划在一般情况下对于流时目标而言并非最优的。

证明（草图）。图 2(a) 中所示的反例承认一个不一致的最优解 L∗，其流时为 48。我们声称不存在任何优先级排序 ≺≺≺ 能够产生流时小于 49 的一致优先级解。我们草拟 L∗ 如下：

• 1 ≺ 2 在时间 1 的位置（3,3）。
• a1 走粗体路径，在时间 4 到达（6,2）。
• a2 走虚线路径，在时间 4 到达（6,4）。
• a3 走粗体路径，在时间 6 到达（6,2）。
• 2 ≺ 1 位置（7,3）在时间5（L∗不一致）。
• a2 在时间7到达其目标顶点：a1 和 a3 在时间8到达其目标顶点。
• 所有其他代理都遵循其各自的最佳路径。

证明是通过枚举进行的，但结果仅取决于智能体 a1、a2 和 a3 的路径选择。所有其他智能体都遵循其个体最优路径，根据与智能体 a1、a2 和 a3 的交互情况决定是否等待。例如，如果智能体 a1 选择虚线（反之）路径，它将避免与智能体 a2 的另一次交叉，并加速其到达 (7, 3) 的过程。然而，这需要由于与智能体 a5 和 a6 的冲突而引入至少两次延迟。与此同时，智能体 a2 试图跟随智能体 a1，但这会引入来自智能体 a5、a6、a7 和 a8 的新延迟。或者，智能体 a2 可以切换到粗线路径，该路径较慢，并由于与智能体 a4 的冲突而引入延迟。这两种选择都会导致流时大于 48 的解决方案。

推论 5。定理 4 对 makespan 目标成立。

证明。（草图）图 2(b) 中所示的反例允许一个不一致的最优解，且 makespan= 7。该解要求在 (3, 2) 处满足 1 ≺ 2，并在 (7, 2) 处满足 2 ≺ 1。不存在一个优先级排序 ≺≺≺ 能够产生一个具有 makespan< 8 的一致优先级解。证明类似于定理 4 的证明。

我们现在关注一类 MAPF 实例，对于这类实例，存在一个最优优先解，该解同时也是一般意义上的最优解。我们将这类问题称为 OP-可解问题。

定义 4。当且仅当：(1) 存在一个解 L∗ 满足某个优先级排序 ≺≺≺∗ 且与该排序一致；以及 (2) L∗ 是所有解（无论是否与该排序一致）中的最优解时，一个 MAPF 实例才具有 OP 可解性。

下一个结果表明，即使对于可 OP- 求解的问题，优先规划也可能找不到最优解，甚至找不到任何解。

定理 6. 对于 OP-可解问题类别，具有任意给定固定全序 ≺≺≺ 的优先规划在一般情况下是不完备的。

证明。图 1(d) 中所示的反例仅对固定总序 {1 ≺ 3 ≺ 2} 承认一致的最优解（对于流时和完工时间两个目标）。该解为：

π1 = 〈 (2, 1), (3, 1), (4, 2), (5, 1) 〉
π3 = 〈 (2, 2), (2, 2), (3, 1), (4, 2) 〉
π2 = 〈 (4, 1), (4, 1), (4, 1), (3, 1) 〉

然而，最高优先级的智能体还有另一条单独最优的路径可供选择，该路径涉及在时间 2 移动到位置 (4, 1)，这将导致智能体 a2 死锁。

总结如下：(1) 一些可解的 MAPF 实例无法通过优先规划求解。(2) 一些可以通过优先规划求解的 MAPF 实例仅能通过单一总优先级排序的优先规划求解。(3) 一些可以通过优先规划求解的 MAPF 实例无法通过任何总优先级排序的优先规划求解。(4) 更糟糕的是，一些可以通过优先规划求解的 MAPF 实例不仅需要正确的总优先级排序，还需要在规划代理路径时正确地打破平局，如果处理不当，可能会导致优先规划无法找到任何解。

基于优先级的冲突搜索

---

（标准）基于冲突的搜索（CBS）是一种最小化流时间的双层算法。带优先级的基于冲突的搜索（CBSw/P）是 CBS 在优先级规划中的一种适应。与 CBS 类似，CBSw/P 在高级别执行最佳优先搜索以解决代理之间的冲突，从而构建约束树（CT）。每个 CT 节点 N 包含一组约束 N.constraints、一个服从这些约束的计划 N.plan（所有代理的路径）以及一个成本 N.cost，该成本等于其计划中所有路径在目标顶点处的到达时间之和。CBSw/P 始终扩展具有最小成本的 CT 节点。与 CBS 不同，CBSw/P 还在每个 CT 节点 N 中存储一个优先级排序 ≺≺≺N，并且在扩展父 CT 节点 N 时，仅生成其优先级排序 ≺≺≺N′ 扩展了 ≺≺≺N 的子 CT 节点 N ′。

定义 5。一个优先序 ≺≺≺A extends 扩展了一个优先序 ≺≺≺B 如果 ∀i, j ∈ [M ] : i ≺B j =⇒ i ≺A j，即 ≺≺≺A 保持了 ≺≺≺B 的所有优先信息。

算法 1 展示了 CBSw/P 的高层搜索。带星号的行不用于 CBS。在高层，CBSw/P 从根 CT 节点开始，该节点具有空约束集和空优先级排序 [第1-2行]。它执行低层搜索，为每个代理独立找到一个单独最优的路径（没有任何约束）。因此，根 CT 节点的计划包含所有代理的路径 [第3行]，其成本是所有路径到达时间之和 [第4行]。当 CBSw/P 展开一个 CT 节点 N 时，它会检查 CT 节点是否包含无冲突的计划 [第9行]。如果是这种情况，N 是一个目标节点，CBSw/P 成功终止 [第10行]。否则，CBSw/P 选择一个冲突进行解决 [第11行]（[NT2]CBSw/p遵循(Felner et al. 2018)中使用的策略来选择冲突），并尝试生成两个候选子 CT 节点 N1 和 N2，分别对应有序对 j ≺ i 和 i ≺ j [第12行]。当且仅当其父 CT 节点 N 的优先级排序 ≺≺≺N 不包含其对应有序对 j ≺ i（i ≺ j） 的反转 i ≺ j（j ≺ i） 时，它才实际生成子 CT 节点 N1(N2) [第13行]。每个子 CT 节点从 N 继承计划、所有约束和优先级排序 [第15-17行]。如果待解决的冲突是顶点冲突 ⟨ai, aj, v, t⟩，CBSw/P 将顶点约束 ⟨ai, v, t) 添加到 N1（如果已生成），以禁止代理 ai 在时间 t 占据 v，并类似地将顶点约束 ⟨aj, v, t⟩ 添加到 N2（如果已生成）。如果需要解决的冲突是边冲突 ⟨ai, aj, u, v, t⟩，CBSw/P 将边约束 ⟨ai, u, v, t⟩ 添加到 N1（如果已生成），以禁止代理 ai 在时间 t 从 u 移动到 v，并类似地将边约束 ⟨aj, v, u, t⟩ 添加到 N2（如果已生成） [第16行]。对于每个子 CT 节点，例如 N1，如果序对 j ≺ i 尚未在 ≺≺≺N1 中，CBSw/P 将其对应的序对 j ≺ i 添加到其优先级排序 ≺≺≺N1 中 [第18-19行]。CBSw/P 使用与 CBS 相同的底层搜索（时空A*）为代理 ai 找到一条个体最优路径，该路径尊重 N1.constraints 中与代理 ai 相关的所有约束。如果找到新路径，CBSw/P 将 N1.plan 中代理 ai 的旧路径替换为底层搜索返回的新路径 [第20行]，相应地更新 N1 的成本，从而将 N1 插入到 OPEN 中 [第22-23行]。

属性。CBSw/P 在子 CT 节点分裂时，为其优先级排序添加一对新的偏序关系，即生成父 CT 节点的一个子 CT 节点。因此，CT 任何分支中的分裂次数为 O(M 2)（所有可能有序对的数量）。然而，CBSw/P 的高层搜索是无界的，因为每个代理（也为其扩展了 CT 节点）之间所有可能碰撞的数量不是有限的。

基于优先级的搜索

---

基于优先级的搜索（PBS）是一种用于优先级规划的两层算法。它在高层执行深度优先搜索以动态构建优先级顺序，从而构建优先级树（PT）。概念上，当遇到冲突时，PBS 会贪婪地选择哪个代理应获得更高的优先级。只有当当前分支没有解决方案时，它才会高效地回溯并探索其他分支。因此，它有效地逐步构建单个部分优先级顺序，直到找不到冲突。PBS 在高层与 CBSw/P 具有一些相似之处。与 CBSw/P 类似，PBS 仅在两个代理发生冲突时才拆分 PT 节点并引入额外的有序对。与 CBSw/P 不同，PBS 不在 PT 节点中存储约束，而是维护一个不变式：如果代理 ai 的优先级高于代理 aj (i ≺N j)，则当 PBS 处理 PT 节点 N 时，它们之间没有冲突。

算法 2 展示了 PBS 的高层搜索过程。我们现在指出它与 CBSw/P 的区别。在高层，PBS 从根 PT 节点开始，该节点包含一个初始优先级排序 ≺≺≺0 [Line 1]。对于（标准）PBS，这是空优先级排序 ∅。然后，它调用函数 UpdatePlan(N, ai) 为每个智能体 ai 找到个体最优路径 [Line 4]，并且在空初始优先级排序下总是成功 [Line 5]。当 PBS 扩展一个 PT 节点 N 时，PBS 总是生成两个子 PT 节点 N1 和 N2，分别对应有序对 j ≺ i 和 i ≺ j [Line 15]，因为智能体 ai 与智能体 aj 不会发生碰撞，如果它们相对于 ≺≺≺N 是可比的 (i ≺N j 或 j ≺N i)。对于每个子 PT 节点，例如 N1，PBS 调用函数 UpdatePlan(N1, ai) 为智能体 ai 找到一条避免与所有更高优先级智能体的路径发生碰撞的个体最优路径 [Line 20]。PBS 倾向于选择成本最小的子 PT 节点，因此以成本非递增的顺序将（如果生成了）子 PT 节点插入堆栈 [Line 23]。

Function UpdatePlan(N, ai)。函数 UpdatePlan(N, ai) 为代理 ai 寻找一个单独最优的路径，该路径可避免与所有更高优先级代理的路径发生碰撞，并保持任何优先级低于它的代理 aj 的路径仍满足 ≺≺≺N 的不变性（如有必要，为该代理 aj 寻找新路径）。为此，PBS 对 i 和所有满足 j 且 i ≺N j 的代理进行拓扑排序 [Line 26]。对于拓扑排序顺序中的每个 j，如果代理 aj 的路径与更高优先级的代理 ak 发生碰撞，PBS 将执行低级别搜索，为代理 aj 计算一条新的单独最优路径，该路径需满足优先级排序 ≺≺≺N（Lines 28-29）。

底层搜索。在底层，PBS 使用一种特殊的底层搜索来为代理 aj 寻找一条不与任何具有更高优先级的 ak（即 k ≺N j) 的路径发生碰撞的个体最优路径。约束的数量可能是无限的，因为这样的代理 ak 在其到达时间 Tk 之后将永远停留在其目标顶点 tk。这与 CBSw/P 的底层搜索不同，后者的约束数量是有限的。因此，可能不存在到达目标顶点 tj 的路径。因此，PBS 使用时空 A* 算法来处理所有不大于更高优先级代理 ak（即 k ≺N j) 的到达时间的最大值的时间，然后切换到标准的 A* 算法（不考虑时间维度和之后的等待动作）。CBS 在打破平局时倾向于选择与最少其他代理路径发生碰撞的路径，这已被经验证明可以提高其高层搜索的效率（Sharon et al. 2015）。类似地，PBS 在打破平局时，首先倾向于选择与与代理 aj 在 ≺≺≺N 关系下不可比较的代理 ak′ 的路径发生碰撞最少的路径，其次倾向于选择与较低优先级代理 ak′′（即 j ≺N k′′) 的路径发生碰撞最少的路径，以尽可能避免之后为这些代理重新规划路径。

属性。PBS 在分割父 PT 节点时，会为子 PT 节点的优先级排序引入一个新的有序对。因此，PT 的任何分支中的分割数量为 O(M^2)（所有可能的有序对的数量）。由于 PBS 在扩展 PT 节点时会分割 PT 节点，所以 PT 的深度也是 O(M^2) 。在实践中，在我们的实验中，对于每个找到解决方案的 MAPF 实例，PBS 扩展的 PT 节点要少得多。

属性。当 PBS 拆分父 PT 节点时，它会向子 PT 节点的优先级排序中引入一个新的有序对。因此，PT 的任何分支中的拆分数量为 O(M 2)（所有可能的有序对的数量）。PT 的深度也为 O(M 2)，因为 PBS 在扩展 PT 节点时会拆分 PT 节点。在实践中，PBS 在我们的实验中找到解决方案的每个 MAPF 实例中，会扩展少得多的 PT 节点。

PBS 的其他版本。可以给出非空的初始优先级排序 ≺≺≺0 [Line 1]，以便PBS找到的解必须满足 ≺≺≺0。然而，可能不存在任何与 ≺≺≺0 一致的解。因此，PBS 可能会在根节点 PT 处终止 [Line 6]。例如，对于图 1(b) 所示的 MAPF 实例，具有初始优先级排序 ≺≺≺0 = {2 ≺ 1} 的 PBS 找不到任何解，但标准的 PBS（空的初始优先级排序）构造了优先级排序 ≺≺≺ = {1 ≺ 2} 并找到了一个解。标准的优先级MAPF 算法是 PBS 的一个特例，其中初始优先级排序是全序。

实验

---

我们将 CBSw/P 和 PBS 与 CBS 以及模拟具有不同总优先级排序的标准优先 MAPF 算法的几种 PBS 变体进行了比较。我们考虑以下算法：CBS-H（标记为CBS）是 CBS 的最新实现（Felner et al. 2018）；FIX 是一种 PBS 变体，其总优先级排序由 MAPF 实例中代理的顺序指定，模拟了 CA*（Silver 2005）；LH 是一种具有固定总优先级排序的 PBS 变体，其中代理的优先级越高，其从起始顶点到目标顶点的个体最优路径越长，这模拟了 Van Den Berg and Overmars 2005 中的启发式方法；SH 是一种具有固定总优先级排序的 PBS 变体，其中代理的优先级越高，其从起始顶点到目标顶点的个体最优路径越短，这与 LH 的启发式方法相反；RND 是一种 PBS 变体，它使用十次不同的随机生成总优先级排序运行 PBS，并选择成本最小的解决方案，这模拟了 Bennewitz, Burgard, and Thrun 2002 中的随机策略。所有实验均在主频为 2.50 GHz、内存为 6 GB 的 Intel Core i5-2450M 笔记本电脑上运行，除 RND 的十次运行各限制一分钟运行时间外，每个 MAPF 实例的每个算法的运行时间限制为一分钟。我们使用代理的不同随机生成的起始和目标顶点，对每个代理数量的每次实验重复了 50 次，并报告了平均值。

实验1：20 × 20 网格。我们在具有 0% 和 10% 障碍物（由随机阻塞单元格表示）的 20 × 20 四邻域网格上使用 MAPF 实例，其中包含随机的起点和终点顶点，分别位于空网格（0% 障碍物）和 10% 单元格被障碍物填充的网格中。

图 3：20×20 网格上的结果。

图 3(a) 和 (b) 显示了算法的成功率，即在时间限制内解决的 MAPF 实例的百分比（如果 RND 在其十次运行中的任何一次在时间限制内解决了 MAPF 实例，则认为 RND 解决了该 MAPF 实例），作为代理数量的函数。CBSw/P 的成功率高于 CBS，尽管两者都随着代理数量的增加而趋近于零，这是由于 CT 的规模不断增大。PBS 及其变体具有高得多的成功率。FIX、LH 和 SH 经常无法找到解决方案，但 PBS 和 RND 能够为除一些具有超过 70 个代理和 10% 障碍物的“困难”实例之外的所有 MAPF 实例找到解决方案。对于“困难”实例，PBS 从未报告“无解”，但在其中一些实例上达到了运行时间限制，而 RND 在所有十次运行中从未达到运行时间限制，但在其中一些实例上报告了所有十次运行的“无解”。在所有具有总优先级排序的 PBS 变体中，SH 的成功率最低，因为在 SH 中，高优先级代理倾向于更早地到达其目标顶点，因此更有可能阻止低优先级代理到达其目标顶点。图 3© 和 (d) 显示了算法的运行时间。对于达到运行时间限制的 MAPF 实例，将一分钟的运行时间进行了平均。CBSw/P 比 CBS 快。RND 比其他 PBS 变体慢，因为它多次解决了同一个 MAPF 实例。PBS 的速度几乎与其他具有总优先级排序的 PBS 变体一样快（始终在数量级内），但随着代理数量的增长，运行时间差异会增大。

我们随后考虑 CBS、CBSw/P、PBS 和 FIX 求解的所有 MAPF 实例的结果。图 3(e) 和 (f) 显示了流时与最优流时（由 CBS 计算）的比率。我们看到 CBSw/P 几乎总是能找到最优解。PBS 找到的解非常接近最优解，随着代理数量的增加而略有下降，但最差也不会超过最优解的 4%。相比之下，FIX 找到的解比最优解差 5% 以上，而且常常差很多。图中所示的结果得到了图 3(g) 所示表格中报告的结果的证实。

其中还报告了我们为每个代理数所考虑的实例数（sol）。

我们也考虑了被 PBS、FIX、LH、SH 和 RND 同时解决的实例集的结果，以便于比较它们的行为。图 3(h) 和 (i) 显示 PBS 几乎与 SH 没有区别，SH 优于 RND，而 RND 又优于 FIX，FIX 又优于 LH。图 3(j) 显示 LH 在具有总优先级排序的算法中具有最多的低层节点扩展数。PBS 具有大量的低层节点扩展数，因为它为更多的优先级排序进行规划，从而执行更多的低层搜索。RND 具有最多的低层节点扩展数，因为它多次解决每个 MAPF 实例。图 3© 和 (d) 中的运行时表现得像低层节点扩展数，因为算法将大部分运行时花在低层搜索上。

实验2：游戏地图。我们还在游戏《龙腾世纪：起源》的两个标准基准地图 brc202d（一个 481 × 530 的四邻域网格）和 lak503d（一个 192 × 192 的四邻域网格）上使用 MAPF 实例（Sturtevant 2012）。我们还在这些网格上使用 MAPF 实例，标记为 brc202d(WF) 和 lak503d(WF)，其中智能体在首次到达目标顶点后会从网格中移除，以便它们之后不会阻挡其他智能体。

图 4：游戏地图上的结果。

我们首先关注 brc202d 和 lak503d 的结果。在成功率（图4(a)和(b)）和运行时间（图4©和(d)）方面，CBSw/P 优于 CBS，并且在解的质量方面几乎没有降低（图4(e)和(f)）。在成功率方面，PBS 优于 FIX、CBS 和 CBSw/P，而在运行时间方面接近 FIX。与 FIX 相比，PBS 几乎总能找到接近最优的解（图4(e)和(f)）。图 4(k) 显示了所有在运行时间限制内所有算法都能解决的 MAPF 实例的结果。对于brc202d，PBS 和 FIX 扩展的低层节点比 CBS 和 CBSw/P 更多，因为狭窄的走廊使得高优先级代理的约束比其他地图更重要，特别是当这些代理提前到达目标顶点并停止移动时，这解释了为什么 PBS 和 FIX 在 brc202d 上对于 120 和 160 个代理的某些实例在时间限制内达到了运行时间限制。

我们随后关注 brc202d(WF) 和 lak503d(WF) 的结果。正如低层节点扩展的数量所示，与 brc202d 和 lak503d 上的实例相比，这些 MAPF实例对于 PBS 和 FIX 来说更容易解决。CBSw/P 和 CBS 在成功率和运行时间方面几乎没有区别（图4(g)至(j)），而 brc202d 和 lak503d则并非如此。

我们进一步测试了 PBS 在具有大量代理的 brc202d(WF) 上的可扩展性。PBS 可扩展至 600 个代理，且永不达到运行时间限制（如下表所示）。

结论

---

我们从概念和实践的角度探讨了为优先规划探索“良好”排序的主要挑战。在概念层面，我们开发了第一个讨论优先规划局限性的理论框架。在实践层面，我们开发了两种新算法，CBSw/P 和 PBS，它们搜索“良好”的排序，从而计算出具有“良好”排序的解决方案。这两种算法都通过仅对两个代理施加排序来解决它们之间的冲突，从而惰性地对代理进行排序，并且它们都以系统的方式探索排序：CBSw/P 使用最佳优先搜索，PBS 使用深度优先搜索。

论文代码 ：https://github.com/Jiaoyang-Li/PBS