多智能体寻路（Multi-agentpathfinding/MAPF）在人工智能、机器人学、理论计算机科学和实际运维研究中得到广泛研究。本文讨论了将MAPF方法推广到现实场景时出现的问题以及解决这些问题的四个研究方向。我们强调解决这些问题的重要性，而不是为MAPF问题的标准模型开发更快的方法。1.引言多智能体寻路（MAPF，又称Multi-AgentPathFinding）在人工智能、机器人、理论计算机科学和实践研究中得到了广泛的研究。（标准）MAPF的任务是在给定的图（graph）中为多个智能体（agents）找到从它们当前的顶点（vertices）到它们的目标的路径，而不与其他智能体发生碰撞，同时优化成本函数）。MAPF使用的现有方法包括：减少可满足性问题、整数线性规划、答案集规划[YuandLaValle,2013b;Erdem等人，2013年；Surynek,2015]，最优/有界次优或次优搜索方法[Silver，2005；Sturtevant和Buro，2006年；瑞安，2008年；王和博蒂亚，2008；斯坦德利，2010年；斯坦德利和科尔夫，2011年；王和博蒂亚，2011年；Luna和Bekris，2011年；沙龙等人，2013年；deWilde等人，2013年；Barer等人，2014年；戈登堡等人。.,2014;瓦格纳和乔塞特，2015年；Boyarski等人，2015年；沙龙等人，2015]。我们最近研究了将MAPF推广到现实场景时出现的各种问题，包括Kiva（亚马逊机器人）仓库系统[Wurman等人，2008年]（图1）和自主飞行器拖船[Morris等人，2016年].这些问题可分为两个一般问题：1.为MAPF问题的标准模型开发更快的方法是不够的，因为在许多实际情况下，可以利用新结构或需要新问题模型。2.将MAPF或其新模型作为组合优化问题进行研究是不够的，因为生成的MAPF解决方案还需要实现。我们从不同的角度讨论解决这两个问题的四个研究方向：1.在许多实际的多智能体系统中，在为所有智能体寻找最佳路径之前，首先将智能体分成小组，然后为每个小组分配特定的目标，每个代理需要从它所在的组中分配一个目标。我们为不同的代理组制定了组合目标分配和路径查找（TAPF/目标分配和路径查找）问题来解决这个困难。我们还开发了一种优化的TAPF方法，可扩展到数十个组和数百个代理[Ma和Koenig，2016]。2.在许多实际的多代理系统中，代理是匿名的（可交换的），但它们的有效载荷是非匿名的（不可交换的），需要传递给给定的目标。代理通常可以在这样的系统中交换它们的有效载荷。作为第一次尝试，我们设计了包裹交换机器人路由(PERR)问题来解决更一般的（允许有效载荷转移）运输问题[Maetal.,2016]。在本文中，我们还展示了近似最优MAPF解决方案的难度（复杂性）。3.在许多实际的多智能体系统中，智能体运动的一致性和智能体运动结果的可预测性很重要（尤其是在人类和智能体共享的工作空间中），但是现有的MAPF方法没有考虑到这一点。我们分两个阶段探索了MAPF示例的问题结构：在第一阶段，我们开发了一个方案，让代理找到一条由用户提供的多条高速公路组成的路径，该方案实现了一致性和可预测性代理人的运动[Cohenetal.,2015]；在第二阶段，我们开发了自动生成高速公路的方法[Cohenetal.,2016]。4.MAPF主要受到多机器人系统的导航或运动规划模块的启发。然而，MAPF解决方案的最优性或有限的次优性并不一定意味着它们的稳健性，特别是考虑到现实世界机器人的计划执行能力不完美。我们开发了一个框架，可以有效地对MAPF方法的输出进行后处理，以创建可由实际多机器人系统执行的计划执行时间表。图1：（左）自驱动单元和用于存储可由驱动单元移动的产品的存储舱；（右）典型Kiva仓库系统的布局（Wurman等人，2008年），以推广MAPF方法转向实际场景，我们现在展示这些研究方向的效用，以证明解决这两个问题同样重要（如果并不比为MAPF问题开发更快的标准模型方法更重要）。2代理组的目标分配和路径查找（TAPF）的组合通常，目标分配给代理所在的每个组。首先将Agent分组，然后需要从组中为每个Agent分配一个目标，以获得Agent从当前顶点到其目标的路径，以优化成本函数。例如，在Kiva仓库系统中，将存储单元从仓库移动到新存储位置的驱动单元形成一个组，因为它们中的每一个都需要分配一个可用的存储位置。以前的MAPF方法假设存在一个目标分配程序，这样每个代理都预先分配了一个目标，但是为了实现最优，我们对TAPF进行建模，它集成了目标分配和路径寻找问题并定义了一个共同的目标。在TAPF中，代理被分成组，每个组的目标数与该组中的代理数一样多。TAPF的任务是给agent分配目标，规划agent从当前顶点到自己目标的无碰撞路径，使得每个agent恰好移动到所属组的一个目标，从而访问到组内的所有目标，并且最大完成时间（所有智能体都达到目标并停止移动时的最早时间步长）被最小化。一个组中的每个代理都可以分配给该组的目标，因此同一组中的代理可以互换。但是，不同组中的代理不可互换。TAPF可以看作是（标准）MAPF和MAPF的匿名变体的概括：如果每个组仅由一个代理组成，则来自TAPF的（标准）MAPF导致组数等于代理数。将目标分配给代理是预先确定的，因此代理是非匿名的（不可交换的）。如果只有一组（包含所有代理），则MAPF（也称为目标不变MAPF）的匿名变量来自TAPF。代理可以分配任何目标，因此可以交换。它可以使用基于流的MAPF方法（flow-basedMAPFmethod）在多项式时间内获得最优解[YuandLaValle,2013a;Turpin等人，2014]。当前最先进的最优TAPF方法——称为基于冲突的最小成本流[Ma和Koenig，2016年]——结合了搜索和基于流的MAPF方法。可以推广到几十个群，几百个agent。3MAPF的ParcelExchangeRobotRouting(PERR)和新的复杂度计算结果代理通常是匿名的，但携带指定目标的有效负载（包），因此是非匿名的。例如，在Kiva仓库系统中，驱动单元是匿名的，但它们携带的存储Pod是指定的存储位置，因此是非匿名的。如果每个代理都携带一个包，则该问题等同于（标准）MAPF。事实上，包裹通常可以在代理人之间传递，从而导致更普遍的运输问题，例如，乘客共乘转机[Coltin和Veloso，2014年]和在办公室使用机器人递送包裹[Veloso等人。等人，2015]。我们使用PERR作为理解这些问题的第一步[Maetal.,2016]。在PERR中，每个agent携带一个包裹，相邻顶点的任意两个agent可以交换它们的包裹，并且每个包裹需要被递送到给定的目的地。因此，PERR可以看作是（标准）MAPF的修改版本：PERR中的包可以看作是在（标准）MAPF中自行移动的代理。相邻顶点中的两个包装器允许在PERR中交换它们的顶点，但相邻顶点中的两个代理不允许在（标准）MAPF中交换它们的顶点。K-PERR是PERR的概括，封装分为K种，同种封装可以互换。因为在TAPF中，agent是分组的，同一个团队的agent是可以互换的，所以K-PERR可以看作是TAPF的K组修改版，同理，PERR可以看作是（Standard）Modified版本的MAPF。我们已经证明了近似最优PERR和K-PERR解决方案的难度（对于K≥2）。我们研究的一个推论是MAPF和TAPF的近似值对于在小于4/3的任何因子内最大制造时间最小化是NP难的，即使对于只有两个团队的TAPF也是如此。我们还证明，向MAPF添加交换操作在理论上不会降低其复杂性，但会使PERR比MAPF更容易求解。在不同的实际场景中产生的连续问题：“一个代理有多个包裹”产生了经典的农村邮递员问题；“与包裹一样多的代理”产生MAPF、TAPF或PERR。理解这两个极端有助于我们解决一般问题，这也是许多其他现实世界任务的要求。图2：User-suppliedhighway4ExplorationproblemstructureandpredictableofmotioninasimulatedKivawarehousesystem智能体与人类共享工作空间，其运动的一致性及其运动结果的可预测性这对人类安全很重要，因此现有的MAPF方法无法经过考虑的。这促使我们探索给定MAPF示例的问题结构，并设计一种方案来激励代理沿着用户提供的一组边移动，称为高速公路[Cohenetal.,2015]。我们在简单的通货膨胀方案的背景下使用基于经验图的高速公路[Phillipsetal.,2012]的想法来推导出新的启发式值用于MotivatedMAPF方法返回包含高速公路边缘的路径，这避免了代理之间的头对头碰撞，并在其运动中实现一致性和可预测性。例如，在Kiva仓库系统中，我们可以沿着存储位置之间的狭窄通道设计高速公路，如图2中的箭头所示。我们已经在模拟的Kiva仓库系统中证明，这样的高速公路可以显着加快MAPF方法，同时保持所需MAPF解决方案成本的有界次优性。TAPF和PERR示例的问题结构也可以使用相同的方法。在可行性研究中，我们还开发了一种自动生成道路的方法，可与用户提供的道路相媲美。5解决不完善的规划执行能力最先进的MAPF或TAPF方法可以在合理的计算时间内为数百个代理找到最佳或无碰撞路径，或者使用用户提供的次优保证。它们甚至可以在Kiva仓库系统等杂乱紧凑的环境中工作。然而，智能体的规划执行能力往往不完善，无法完美同步动作，这会导致频繁的重新规划和浪费时间。因此，我们提出了一个框架，该框架使用一个简单的时间网络来高效地对MAPF解决方案进行后处理，并创建一个适用于非完整机器人的计划执行时间表，给定它们的最大平移和旋转速度，从而提供保证机器人之间的安全距离和松弛边界（定义为最近和最早进入时间的位置差异），以减轻不完美的计划执行并避免在许多情况下耗时的重新计划[Honig¨etal.,2016]。该框架已经在模拟和真实机器人中进行了评估。TAPF和PERR方法也可以应用在同一框架中。未来工作中要解决的问题包括增加用户提供的安全距离、额外的运动约束、不确定性下的规划和重新规划。6结论我们讨论了四个研究方向，以解决将MAPF方法推广到实际场景并探索问题结构或现有MAPF方法时出现的问题。我们的目标是为MAPF领域的研究人员指明有趣的研究方向。
