PRIMAL：通过强化和模仿寻找路径

多智能体学习

摘要

多代理路径查找 (MAPF) 是许多大规模现实世界机器人部署的重要组成部分，从空中集群到仓库自动化。 然而，尽管社区不断努力，大多数最先进的 MAPF 规划者仍然依赖集中式规划，并且规模很难超过几百个代理。 这种规划方法不适应现实世界的部署，其中噪声和不确定性通常需要在线重新计算路径，而当规划时间为几秒到几分钟时，这是不可能的。 我们提出了 PRIMAL，这是 MAPF 的一种新颖框架，它结合了强化和模仿学习来教授完全去中心化的策略，其中代理在部分可观察的世界中在线反应性地规划路径，同时表现出隐式协调。 该框架通过在训练期间引入专家 MAPF 规划器的演示以及仔细的奖励塑造和环境采样，扩展了我们之前在协作策略的分布式学习方面的工作。 一旦学习，生成的策略可以复制到任意数量的代理上，并自然地扩展到不同的团队规模和世界维度。 我们展示了具有多达 1024 个智能体的随机世界的结果，并将成功率与最先进的 MAPF 规划器进行了比较。 最后，我们通过实验验证了工厂模型的混合模拟中学到的策略，涉及现实世界和模拟机器人。

我简介

鉴于具有嵌入式传感和计算功能的经济型机器人的快速发展，制造应用很快就会定期部署数千台机器人[1, 2]。 为了支持这些应用，我们在多智能体路径查找 (MAPF) [3,4,5,6] 方面投入了大量的研究工作，用于在配送中心部署以及飞机滑行的潜在用途 [7, 8]。 然而，随着系统中代理数量的增加，协调它们的复杂性也随之增加。 当前最先进的最优规划器可以规划数百个智能体，并且社区现在正在接受有界次优规划器作为更大的多智能体系统的潜在解决方案[3, 9]。 另一种常见的方法是依赖反应式规划器，它不会在执行之前规划所有代理的联合路径，而是在线纠正各个路径以避免冲突[5, 10]。 然而，在杂乱的工厂环境中（如图1)，这样的规划器通常效率低下，可能导致死锁和活锁[5]。

图1： 示例问题：$100$ 模拟机器人（白点）必须在大型工厂环境中计算单独的无碰撞路径。

扩展了我们之前关于共享环境中多个智能体的分布式强化学习 (RL) 的工作[11, 12]，本文的主要贡献介绍了 PRIMAL，一种结合了 RL 的去中心化 MAPF 的新型混合框架[13] 以及来自专家集中式 MAPF 规划器的模仿学习 (IL)。 在这个框架中，智能体学会考虑自己的立场对其他智能体的影响，以支持有利于整个团队而不仅仅是他们自己的行动。 也就是说，通过同时学习规划有效的单代理路径（主要通过强化学习）并模仿中心化专家（IL），代理最终学习去中心化策略，在该策略中，它们在在线路径规划期间仍然表现出隐式协调，而不需要显式的协调。代理之间的通信。 由于多个代理学习通用的单代理策略，因此最终学习的策略可以复制到任意数量的代理上。 此外，我们还考虑了代理在部分可观察的世界中进化的情况，他们只能在自己周围的有限视野（FOV）中观察世界。 我们展示了一系列广泛的模拟实验的结果，并表明最终的、训练有素的策略可以自然地扩展到不同的团队和世界规模。 我们进一步强调 PRIMAL 优于其他最先进的 MAPF 规划器的案例以及它表现不佳的案例。 我们还展示了工厂模型混合模拟中经过训练的策略的实验结果。

本文的结构如下：在第 II 节中，我们总结了 MAPF 和多智能体强化学习的最新技术。 我们在第III节中详细介绍了MAPF如何在RL框架中构建，以及在第IV节中如何进行学习。 V 节介绍了我们的结果，VI 节给出了结论。

II 之前的工作

II-A 多代理路径查找 (MAPF)

即使在逼近最优解[14, 15]时，MAPF 也是一个 NP 难题。 MAPF 规划器可以大致分为三类：耦合、解耦和动态耦合方法。 耦合方法（例如，标准$A^{\ast }$)将多智能体系统视为单个、非常高维的智能体，极大地受到规划复杂性呈指数增长的影响。 因此，我们专注于解决大型 MAPF 问题的解耦和动态耦合、最先进的规划器。

解耦方法计算每个代理的单独路径，然后调整这些路径以避免冲突。 由于可以在低维搜索空间中规划各个路径并针对碰撞进行调整，因此解耦方法可以快速找到大型多智能体系统的路径[5, 16]。 速度规划器固定每个智能体将遵循的单独路径，然后沿着这些路径找到避免碰撞的速度分布[6, 10]。 特别是，ORCA [5] 在单独规划的单代理路径之上在线调整代理的速度大小和方向以避免碰撞，并且最近的工作重点是使用这种避障方法强化学习（RL）[10]。 优先级规划器为每个智能体分配优先级，并按优先级降序规划各个路径，每次都将较高优先级的智能体视为移动障碍物[17,18,19]。 解耦方法的主要缺点是所使用的低维搜索空间仅代表联合配置空间的一小部分，这意味着这些方法不能完整（即找到所有可解决问题的路径） [20]。

最近的几种方法介于耦合和解耦方法之间：它们允许比解耦规划器实现更丰富的代理行为，同时避免在联合配置空间中进行规划。 动态耦合方法遵循的常见方法是在规划期间根据需要扩大搜索空间[3, 21]。 基于冲突的搜索（CBS）及其变体[4, 21]为个体代理进行规划并构建一组约束来找到最佳或接近最佳的解决方案，而无需探索更高维的空间。 将标准 $A^{\ast }$ 扩展到 MAPF，$M^{\ast }$ 及其变体 [3] 首先为各个代理规划路径，然后通过时间搜索碰撞来预测这些单独的计划。 配置空间仅围绕单代理计划之间的任何冲突进行局部扩展，其中联合计划通过（通常是有限的）回溯来执行，以解决冲突并恢复单代理计划。 特别是，OD-recursive-$M^{\ast }$ (ODrM*) [22] 可以通过将其分解为独立的碰撞集来进一步减少需要联合规划的代理集，与算子分解（OD）[23]相结合，以在搜索过程中保持分支因子较小。

II-B 多智能体强化学习 (MARL)

从单智能体学习过渡到多智能体学习时遇到的第一个也是最重要的问题是维度灾难：大多数联合方法都会失败，因为状态-动作空间组合爆炸，需要不切实际的训练数据量才能收敛[24] 。 在这种背景下，最近的许多工作都集中在去中心化的政策学习[25,26,27,28,29]，其中每个代理学习自己的策略，其中应该包含一定程度的代理合作，至少在训练期间。 其中一种方法是训练智能体预测其他智能体的行为[26, 27]，随着团队规模的增加，这种方法通常扩展性很差。 在大多数情况下，涉及某种形式的集中学习，其中所有代理的经验总和可以用于训练问题的共同方面（例如，网络输出或价值/优势计算）[25, 27, 28]。 当集中学习网络输出时，参数共享已用于通过共享神经网络[25]某些层的权重来实现更快、更稳定的训练。 例如，在演员批评家方法中，网络的批评家输出通常通过参数共享进行集中训练，因为它适用于系统中的所有代理，并且已用于训练代理之间的合作[25, 27] 。 通过将所有代理的观察结果聚合到单个学习过程中，集中学习在处理部分可观察系统时也很有帮助[25,27,28]。

其次，许多现有方法依赖于代理之间的显式通信，在策略执行期间（有时也在策略执行期间）共享观察结果或选定的操作[26,27,28]。 在我们之前的工作[11, 12]中，我们专注于扩展最先进的异步优势演员批评家（A3C）算法，使多个智能体能够在共享环境，无需任何显式代理通信。 也就是说，智能体可以访问系统的完整状态（完全可观察的世界），并将彼此视为移动的障碍。 在那里，稳定学习是关键：在相同环境中经历相同事件的智能体获得的学习梯度通常非常相关，并且会破坏学习过程的稳定性。 为了防止这种情况，我们依靠经验重播[30]和仔细随机化的情节初始化。 然而，我们并没有训练特工表现出任何形式的协调能力。 也就是说，在我们之前的 A3C 扩展中，代理协作（即，朝着共同目标努力），但不明确合作（即，采取行动使整个群体受益）而且不仅仅是他们自己）。

在我们的工作中，我们建议依靠专家集中规划器（ODrM*）的模仿学习（IL）来训练代理在部分可观察的世界中表现出协调性，而不需要显式通信。 我们还提出了一个精心设计的奖励结构和一种对代理所面临的挑战进行训练的方法。 由此产生的经过训练的策略由每个代理根据本地收集的信息执行，但仍然允许代理表现出合作行为，并且对于代理故障或添加也具有鲁棒性。

III 政策表述

在本节中，我们将介绍如何将 MAPF 问题转化为 RL 框架。 我们详细介绍了每个代理的观察和行动空间、奖励结构以及代表要学习的策略的神经网络。

III-A 观察空间

我们考虑一个部分可观察的离散网格世界，其中代理只能在以自己为中心的有限视场中观察世界的状态（实际上是$10\times 10$视场）。 我们相信，考虑部分可观察的世界是迈向现实世界机器人部署的重要一步。 在可以使用完整环境地图进行训练的场景中（例如，自动化仓库），始终可以通过使用足够大的 FOV 来使代理具有对系统的完全可观察性。 此外，假设固定的 FOV 可以允许策略推广到任意世界大小，并且还有助于减少神经网络的输入维度。 然而，代理需要访问有关其目标的信息，而该目标通常位于其视野之外。 为此，它始终可以访问指向其目标的单位向量和到其目标的欧几里德距离（见图2)。

在有限的视场中，我们将可用信息分成不同的通道，以简化代理的学习任务。 具体来说，每个观察都由表示障碍物、其他智能体的位置、智能体自己的目标位置（如果在视场内）以及其他可观察智能体的目标位置的二进制矩阵组成。 当智能体接近世界边缘时，世界边界之外的所有位置都会添加障碍。

图2： 每个智能体的观察空间（此处为浅蓝色智能体）。 代理显示为彩色方块，他们的目标显示为类似颜色的星星，障碍物显示为灰色方块。 每个智能体只能访问以其位置为中心的有限视野（FOV），其中信息被分解为多个通道：障碍物的位置、附近智能体的位置、这些附近智能体的目标位置（投影到智能体的边界上） FOV（如果在 FOV 之外），以及目标位置（如果在 FOV 之内）。 请注意障碍物通道的底行是如何充满障碍物的，因为这些位置位于世界边界之外。 每个智能体还可以访问指向其目标（通常在其视场之外）及其大小（到目标的距离）的归一化向量，作为让智能体学习选择其总体行进方向的自然方式。

III-B 行动空间

智能体在网格世界中采取离散的行动：沿四个基本方向之一移动一个单元格或保持静止。 在每个时间步长，某些动作可能是无效的，例如移入墙壁或另一个代理。 在训练期间，仅从有效动作中对动作进行采样，并且附加的损失函数有助于学习此信息。 我们通过实验观察到，与因选择无效动作而给予代理负面奖励相比，这种方法可以实现更稳定的训练。 此外，为了防止收敛到振荡策略，智能体在训练期间被阻止返回到他们在上一个时间步长中占据的位置（智能体在多个连续时间步长中仍然可以保持静止）。 这对于鼓励探索和学习有效的政策（即使也使用 IL）是必要的。

如果代理在测试期间选择了无效的移动，它将在该时间步内保持静止。 在实践中，一旦经过充分训练，智能体很少会选择无效的动作，这表明它们有效地学习了每个状态下的有效动作集。

图3： 该神经网络由与 maxpooling 层交错的 $7$ 卷积层和后跟 LSTM 组成。

III-C 奖励结构

我们的奖励函数（表I)遵循网格世界的大多数奖励函数所使用的相同直觉，其中代理因没有达到目标的每个时间步而受到惩罚，从而导致尽快实现目标的策略尽可能。 我们对保持静止的智能体的惩罚比对移动的智能体的惩罚稍重，这对于鼓励探索是必要的。 尽管模仿有助于探索，但我们发现去除奖励函数的这一方面会导致收敛性较差，这可能是由于 RL 和 IL 梯度之间的冲突造成的。 虽然无效的移动（移回前一个单元格或进入障碍物）会在训练过程中从动作空间中过滤掉，如第 III-B 节中所述，因为代理按随机顺序依次行动，但它是它们仍然有可能发生碰撞，例如，当多个智能体选择在同一时间步移动到同一位置时。 代理碰撞会导致 $-2$ 奖励。 特工完成一集后（即所有特工同时实现其目标时）会收到 $+20$ 奖励。

表一： 简单的奖励结构。

Action	Reward
Move [N/E/S/W]	-0.3
Agent Collision	-2.0
No Movement (on/off goal)	0.0 / -0.5
Finish Episode	+20.0

III-D 演员评论家网络

我们的工作依赖于异步优势行动者批评家 (A3C) 算法[31]，并扩展了我们之前关于共享环境中多个代理的分布式学习的工作[11, 12] 。 我们使用深度神经网络来近似代理的策略，它将当前对其周围环境的观察映射到要采取的下一个行动。 该网络有多个输出，其中一个是实际策略，其他仅用于训练策略。 我们使用如图 3 所示的 6 层卷积网络，其灵感来自 VGGnet [32]，在每个 max 之间使用几个小的 $3\times 3$ 内核-池化层。

具体来说，神经网络的两个输入——局部观察和目标方向/距离——在通过神经网络中途连接之前被独立预处理。 表示局部观察的四通道矩阵($10\times 10\times 4$张量）经过三个卷积和最大池化的两个阶段，然后是最后一个卷积层。 同时，目标单位向量和幅度通过一个全连接 (fc) 层。 然后，这两个预处理输入的串联通过两个 fc 层，最终输入到输出大小为 $512$ 的长短期记忆 (LSTM) 单元中。 残差快捷方式[33]将串联层的输出连接到LSTM的输入层。 输出层由具有 softmax 激活的策略神经元、值输出和用于训练每个智能体以了解其是否阻止其他智能体实现其目标的特征层组成（详细信息请参见第 IV-A1)。

在训练期间，策略、值和“阻止”输出会在每 $n=256$ 步骤或训练集结束时批量更新。 通常，通过最小化以下值来更新该值以匹配总折扣回报 ($R_t={\sum }_{i=0}^k{\gamma }^i{r}_{t+i}$)：

$$L_V=\sum _{t=0}^T{(V(o_t;\theta )-R_t)}^2.$$ (1)

为了更新策略，我们通过使用价值函数引导来使用优势函数的近似值：$A(o_t,a_t;\theta )={\sum }_{i=0}^{k-1}{\gamma }^i{r}_{t+i}+{\gamma }^{k}V(o_{k+t};\theta )-V(o_t;\theta )$（其中$k$受批量大小$T$限制） 。 我们还在策略损失中添加了一个熵项$H(\pi (o))$，事实证明，它可以通过惩罚总是选择相同操作的策略来鼓励探索并阻止过早收敛[34]。 政策损失如下：

$$L_{\pi }={\sigma }_H\cdot H(\pi (o))-\sum _{t=0}^T\log (P(a_t|\pi ,o;\theta )A(o_t,a_t;\theta ))$$ (2)

具有较小的熵权${\sigma }_H$（实际上是${\sigma }_H=0.01$)。 我们依赖两个额外的损失函数来帮助指导和稳定训练。 首先，通过最小化$L_{blocking}$（预测错误的对数可能性）来更新阻塞预测输出。 其次，我们定义损失函数$L_{valid}$以最小化选择无效移动[11]的对数可能性，如III-B节中所述。

四学习

在本节中，我们将详细介绍用于学习具有隐式代理协调的 MAPF 的分布式框架。 我们框架的强化学习部分建立在我们之前针对共享环境中的多个代理的分布式强化学习工作的基础上[11, 12]。 在我们的工作中，我们引入了一个 IL 模块，允许代理从专家演示中学习。

IV-A 协调学习

训练去中心化政策的关键挑战之一是鼓励代理人无私地行动，即使这可能不利于他们立即最大化奖励。 特别是，当代理人停止实现自己的目标时，通常会表现出不良的自私行为，同时阻止其他代理人实现自己的目标。 我们之前的工作[11]的幼稚实现，其中代理分布式地学习完全自私的策略，在具有许多狭窄环境特征的密集环境中失败，其中阻止其他代理的可能性很高。 也就是说，智能体只是学会尽可能快地实现他们的目标，然后永远不会偏离它，甚至不让其他智能体访问他们自己的目标（尽管事实上这会提前结束情节，这会导致为所有代理提供更高的奖励）。

当前解决这个自私问题的许多多智能体训练技术都因环境的大小和智能体的有限视场而失效。 事实证明，共享批评者[27]在多代理信用分配方面是有效的。 然而，当代理几乎拥有有关其环境的完整信息时，通常会使用这些方法。 在我们高度去中心化的场景中，当代理无法观察到惩罚的来源时，例如，当代理无法观察到长长的走廊是死胡同时，向代理分配信用可能会令人困惑，而通用批评家却急剧降低了价值函数。 另一种流行的多智能体训练技术是对智能体应用联合奖励，试图帮助他们认识到通过个人牺牲来造福团队的好处[35, 12]。 我们简单地尝试将联合奖励分配给同一视场内的代理。 然而，这在行为上没有产生明显的差异，因此我们放弃了它，转而采用下面描述的方法。

为了成功地教授智能体协作行为，我们依靠三种方法：在训练中应用惩罚来鼓励其他智能体的移动（称为“阻止惩罚”），在训练期间使用专家演示，以及在训练过程中定制随机环境以使智能体面临更困难的环境。杂乱的场景。 我们强调，如果没有这三种方法，学习过程要么不稳定（没有学习），要么收敛到比所有三种方法更糟糕的策略，如图 5 所示。

IV-A1 拦网处罚

首先，如果一个智能体决定保持目标，同时阻止另​​一个智能体实现其目标，我们会通过严厉的惩罚（实际上是$-2$)来增强表I中显示的奖励函数。 这种奖励背后的直觉是为代理人离开他们的目标提供激励，抵消（自私的）局部最大代理人的经验，同时依靠目标。 我们对阻塞的定义包括一个代理不仅阻止另一个代理实现其目标的情况，还包括一个代理显着延迟另一个代理的情况（实际上，通过 $10$ 或更多步骤来匹配代理的大小）代理人的视野）。 由于智能体的视场较小，这种宽松的阻挡定义是必要的。 尽管在更大的世界中，代理周围可能存在替代路线，但当协调可能导致路径缩短时，在代理周围移动是不合逻辑的，特别是如果替代路线位于代理的视野之外（因此是不确定的）。

我们使用标准 $A^{\ast }$ 来确定代理从当前位置到目标的路径长度，以及当其他每个代理从世界中移除时其路径的长度。 如果第二条路径比第一条路径短$10$步以上，则其他代理被视为阻塞。 网络的“阻塞”输出经过训练，可以预测代理何时阻塞其他代理，从而隐式向代理提供在这种情况下将产生的额外惩罚的“解释”。

IV-A2 结合 RL 和 IL

其次，事实证明，结合 RL 和 IL 可以带来更快、更稳定的训练以及更高质量的机器人操作解决方案[36,37,38]。 这些优势可能是由于 IL 可以帮助快速识别智能体状态动作空间的高质量区域，而 RL 可以通过自由探索这些区域来进一步改进策略。 在我们的工作中，我们在每集开始时随机选择是否涉及 RL 或 IL（从而将中央开关设置在图 4 的中间）。 此类演示是依靠集中式规划器 ODrM* [3]（使用 $ϵ=2$)动态生成的。 为每个智能体获得观察和动作$T\in {(𝒪\times 𝒜)}^n$的轨迹，并且我们最小化行为克隆损失：

$$L_{bc}=-\frac{1}{T}\sum _{t=0}^T\log (P(a_t|\pi ,o_t;\theta )).$$ (3)

图4： 我们的混合 RL/IL 方法的结构。 在每一集的开始，随机抽签决定该集是基于 RL 还是基于 IL，并相应地设置“开关”（中间）。 对于基于强化学习的学习，在每个时间步，每个代理 ($1,..,n$) 从世界中获取其先前行为的观察结果 $o_i$ 和奖励 $r_i$（学习环境）并使用观察结果通过其自己的神经网络副本选择操作$a_i$。 不同代理的动作以随机顺序顺序执行。 由于代理经常从公共的共享神经网络中推拉权重，因此它们最终在各自的网络中共享相同的权重。 对于基于IL的学习，专家集中规划器在事件期间协调所有智能体，智能体学习模仿其行为，从而使它们能够学习协调的行为。

我们的实现与[36, 39]不同，因为我们将离策略行为克隆与在策略行为者批评者学习相结合，而不是与离策略深度确定性策略梯度相结合。 我们探索了这种方法，因为我们可以在新的训练集开始时以低廉的成本在线生成专家演示，而不是学习代理只能访问一组有限的预先记录的专家轨迹。 ODrM* 中使用的启发式本质上有助于生成与我们的奖励结构相关的高质量路径（表 I)，其中代理尽快移动到目标（同时避免碰撞）并在此基础上休息。 因此，RL/IL梯度自然是一致的，从而避免了学习过程中的振荡。

利用演示是我们系统的必要组成部分：没有它，学习进度会慢得多，并且会收敛到一个明显更差的解决方案。 然而，我们尝试了各种 IL 比例($10$-$50\%$，增量为 $10\%$)，并观察到 ​​RL/IL 比例似乎不会影响性能训练有素的政策的很多。 最后，尽管由于实时规划器的可用性，我们可以使用动态方法，例如 ${\text{DA}}_{\text{GGER}}$ [40] 或置信推理 [41] ，我们选择使用行为克隆是因为它简单且易于实现。 目前尚不清楚使用此类方法是否会导致性能提高，这将是未来工作的主题。

IV-A3 环境采样

最后，在训练过程中，我们在每集开始时随机化世界的大小和障碍物密度。 我们发现，对世界的大小和密度进行统一采样并没有使智能体暴露在足够多的情况下，因为智能体与智能体之间的交互相对稀疏，因此需要进行协调。 因此，我们从有利于更小和更密集环境的分布中对尺寸和障碍物密度进行采样，迫使智能体学习协调，因为它们更频繁地经历智能体与智能体之间的交互。

IV-B 训练详情

IV-B1 环境

方形环境的大小在每集开始时随机选择为 $10$、$40$ 或 $70$，概率分布使得 $10$大小的世界的可能性是其两倍。 障碍物密度是从$0$和$50\%$之间的三角形分布中随机选择的，峰值以$33\%$为中心。 障碍物、代理和目标的放置在整个环境中是统一随机的，但需要注意的是每个代理都必须能够达到其目标。 也就是说，每个智能体最初都被放置在与其目标相同的连接区域中。 代理有可能在不可能的环境中进行训练（例如，两个代理可能会在同一个狭窄的连接区域中产生，每个代理都针对另一个目标），尽管可能性很小。 代理的动作在每个时间步以随机顺序顺序执行，以确保它们具有相同的优先级（即随机解决竞争条件）。

IV-B2 参数

我们使用 $0.95$ 的折扣因子 ($\gamma$)、$256$ 的剧集长度和 $128$ 的批量大小，以便每个智能体每集执行两次梯度更新。 每集观看演示的概率为 $50\%$。 我们使用 Nadam 优化器 [42]，其学习率从 $2\cdot {10}^{-5}$ 开始，并与情节计数的平方根倒数成比例衰减。 我们在 $3$ 独立环境中训练每个 $8$ 代理，在每个步骤开始时在同一环境中同步代理，并允许它们并行操作。 训练在匹兹堡超级计算中心 (PSC) [43] 上在 Intel Xeon E5-2695 的 $7$ 个内核和一个 NVIDIA K80 GPU 上进行，持续时间约为 $20$ 天。 用于训练代理的完整代码可在 https://goo.gl/T627XD 获取。

V 结果

在本节中，我们将介绍一系列广泛的模拟结果，将 PRIMAL 与网格世界中最先进的 MAPF 规划器进行比较。 这些测试是在具有不同障碍物密度、网格大小和团队规模的环境中进行的。 最后，我们展示了在室内工厂模型中物理和模拟机器人在线规划路径的场景的实验结果。

V-A 与其他 MAPF 规划器的比较

在我们的实验中，我们选择 CBS [21] 作为我们的最优集中式规划器，选择 ODrM* [3] 作为次优集中式选项（通货膨胀因子 $ϵ=1.5$ 和 $ϵ=10$)，以及 ORCA [5] 作为完全解耦的速度规划器。 请注意，所有其他规划器都可以访问系统的整个状态，而 PRIMAL 假设每个代理仅具有系统的部分可观察性。 世界规模为$\{10,20,40,80,160\}$、密度$\{0,0.1,0.2,0.3\}$和团队规模$\{4,8,\mathrm{\dots },1024\}$。 我们在 $10$ 大小的世界中放置的代理不超过 $32$ 个，在 $20$ 大小的世界中放置的代理不超过 $128$ 个，并且没有$40$ 大小的世界中超过 $1024$ 个特工。

在我们的实验中，我们比较了不同规划者的成功率，即他们是否在给定的挂钟时间或时间步长内完成了给定的问题。 对于 CBS 和 ODrM*，我们分别使用 $300$ 秒和 $60$ 秒的超时来匹配之前的结果 [3]。 我们将 ODrM* 的超时除以 $5$，因为我们使用了 $C++$ 实现，经实验测量，该实现比之前使用的 Python 实现快约 $5$ 倍。 对于 ORCA，我们使用 $60$ 秒的超时，但当所有代理都陷入死锁时提前终止（定义为所有代理被卡住超过 $120$ 秒模拟时间，这对应于$10$ 的物理时间）。 最后，对于 PRIMAL，我们让智能体为 $10$ 到 $40$ 大小的世界($384$)规划最多 $256$ 个时间步长的单独路径> $80$ 大小的世界的时间步长，以及 $160$ 大小的世界的 $512$ 时间步长。 传统规划器的实验在一台台式计算机上进行，该计算机配备 AMD Threadripper $2990$WX，具有 $64$ 逻辑核心，时钟频率为 $4$Ghz 和 $64$GB RAM。 PRIMAL 的实验部分在同一台计算机上运行，​​该计算机还配备了 $3$ GPU（NVIDIA Titan V、GTX $1080$Ti 和 $1070$Ti），如下所示以及配备 Intel i$7$-$7700$K、$16$Gb RAM 和 NVIDIA GTX $1070$ 的简单台式机。

图5： 训练期间的平均剧集长度，越低越好。 虚线显示从 ODrM* 专家规划师处获得的基线。 当我们从我们的方法中删除环境采样、阻塞惩罚或模仿学习时，策略会收敛到更糟糕的解决方案。

根据我们的结果，我们首先注意到我们的方法在低障碍物密度中表现得非常好，在这种情况下，智能体可以很容易地绕过彼此，但在密集的环境中很容易表现不佳，在这种环境中，联合行动似乎是智能体实现其目标所必需的（有时需要大幅改变路径）。 同样，但性能明显较差，ORCA 无法防止死锁，并且由于其完全解耦的反应性性质，在涉及超过 $16$ 个代理和任何障碍的大多数场景中，其性能非常差。 其次，我们注意到，由于我们的训练涉及不同大小的世界，但团队规模恒定，因此特工本质上会面临其视场内特工密度的微小变化。 在我们的结果中，我们观察到，随着 FOV（小世界，大团队）中附近智能体数量的增加，智能体的训练表现会更差，我们认为可以通过在 期间改变团队规模来纠正这种影响。 这将在未来的工作中进行研究。 然而，我们预计传统的规划者在小型($10$-$20$大小）世界中通常会优于我们的方法，即使是在更大的团队中也是如此。 第三，我们注意到 PRIMAL 生成的路径有时比其他规划器的路径长两倍以上。 然而，其他规划器允许智能体在我们的 MAPF 问题定义中无法采取的移动：智能体可以相互跟随，彼此之间没有空白空间，可以交换（类似于小跑），等等。 [3]，这会导致路径较短。 此外，对 PRIMAL 生成较长路径的情况进行目视检查表明，除了少数落后者之外，大多数智能体都能有效地实现其目标。 最后，由于智能体在训练期间从未接触过大于 $70\times 70$ 的世界，因此在测试期间它们在较大世界($\ge 80$ 大小）中的表现似乎极差。 然而，通过限制智能体状态下的目标距离，PRIMAL 在更大世界中的成功率可以大大提高。 在此处针对 $80$ 和 $160$ 大小的世界提供的结果中，在智能体状态下，到目标的距离上限为 $75$（经验设置）。 有关各种环境中 PRIMAL 的接近最优和严重次优计划的示例视频，请访问 https://goo.gl/T627XD。

由于篇幅限制，我们选择讨论图 6 中所示的三种主要场景：一种情况是 PRIMAL 远远优于所有其他规划器，一种情况是 PRIMAL 稍微优于它们，另一种情况是 PRIMAL 表现不佳。 完整的结果集（针对所有团队规模、障碍物密度和世界大小）可以在 https://goo.gl/APktNk 中找到，并且还包含不同规划器生成的路径长度作为计划时间。 首先，在没有障碍的大世界中($160\times 160$)，集中式规划者尤其困难，因为联合配置空间迅速增长以涵盖所有智能体，使得规划超过 $100$ 个智能体非常耗时-消耗。 另一方面，PRIMAL 可以轻松应对最多 $1024$ 个特工的团队，并且成功率近乎完美。 其次，在障碍物密度较低的中等规模世界中，中心化规划者可以轻松地为数百个智能体进行规划。 PRIMAL 的成功率比其他规划器更早开始下降，但在具有 $512$ 代理的情况下仍高于 $60\%$，而所有其他规划器表现不佳。 第三，在一个障碍物非常密集的较小世界中，所有规划器最多只能处理 $64$ 个智能体，但 PRIMAL 开始努力超越 $8$ 个智能体，而 ODrM* 可以处理最多 $64$ 个代理。 然而，即使 PRIMAL 无法完成完整的问题，它通常也会设法让许多智能体快速实现其目标，只有少数智能体未能实现其目标。 此时，可以使用传统的规划器来完成问题，这对于基于图的求解器来说变得很简单，因为大多数智能体应该在其目标上保持静止。 未来的工作将研究 PRIMAL 与完整规划器的结合，以利用 PRIMAL 快速、分散的规划，同时保证完整性。

V-B 实验验证

我们还在工厂模型中不断发展的小型自主地面车辆 (AGV) 车队上实施了 PRIMAL。 在这个混合系统中，两个物理机器人与两个（然后，在实验进行到一半时，三个）模拟机器人一起进化。 物理机器人可以访问模拟机器人的位置，反之亦然，因为它们都使用我们的去中心化方法在线计划下一步行动。 PRIMAL 显示了清晰的在线功能，因为每个步骤和每个代理的规划时间远低于标准 GPU 上的 $0.1$ 秒（并且远低于 CPU 上的 $0.2$ 秒）。 图7显示了我们的工厂模型和模拟环境。 完整视频可在 https://goo.gl/T627XD 获取。

图6： 不同规划者在三种情况下的成功率。 PRIMAL 在顶级无障碍世界中优于所有规划器，在低障碍物密度世界中略微优于其他规划器，在高障碍物密度世界中明显优于其他规划器。

图7： 工厂模型中不断演化的物理和模拟机器人的快照。 左：模型和机器人的俯视图（顶部）和侧视图（底部）。 右：可视化显示障碍物（黑色实心）、机器人（蓝色圆圈）、它们的目标（蓝色方块）和当前移动（绿色方块）。

六结论

在本文中，我们提出了 PRIMAL，一种多智能体路径查找的新方法，它依赖于将分布式强化学习和集中式专家规划器的模仿学习相结合。 通过大量的实验，我们展示了 PRIMAL 如何适应不同的团队规模、世界规模和障碍物密度，尽管只允许智能体访问有关世界的本地信息。 在低障碍物密度环境中，我们进一步展示了 PRIMAL 如何表现出同等性能，甚至在某些情况下超越最先进的 MAPF 规划器，即使它们可以访问系统的整个状态。 最后，我们展示了一个在工厂模型中的物理和模拟机器人上部署 PRIMAL 的示例，展示了机器人如何从我们的在线、基于本地信息的分散式 MAPF 方法中受益。

未来的工作将集中于使我们的训练程序适应类似工厂的环境，障碍物密度低到中等，但环境的某些部分非常稀疏，而其他部分则高度结构化（例如走廊、过道等）。 我们还相信，将我们的方法扩展到后退视野规划（智能体提前计划多项行动）可能有助于通过教导智能体明确协调其路径来提高 PRIMAL 的性能。

致谢

匿名审稿人的详细评论对本文的呈现和质量做出了贡献。 这项研究得到了卡内基梅隆大学制造业未来计划的支持，并由理查德金梅隆基金会促成。 Justin Kerr 是 CMU SURF 的学生，由美国国家科学基金会 (NSF) 资助。 南加州大学的这项研究得到了 NSF 拨款 1409987、1724392、1817189 和 1837779 的支持。 这项工作使用了 Bridges 系统，并得到了匹兹堡超级计算中心 NSF 拨款 ACI-1445606 的支持[43]。