多代理路径找寻（Multi－agentpathfinding／MAPF）已在人工智能、机器人、理论计算机科学和实际操作研究中获得大量的研究。本文辩论了在将MAPF方法推展到实际场景时经常出现的问题与解决问题这些问题的四个研究方向。我们特别强调的是解决问题这些问题的重要性，而不是为MAPF问题的标准模型研发更慢的方法。1章节多代理路径找寻（MAPF，也叫多代理寻径）在人工智能、机器人、理论计算机科学和实际操作研究中获得大量的研究。

（标准）MAPF的任务是为多个代理（agent）寻找在等价图（graph）中从其当前顶点（vertices）到其目标而不与其它代理再次发生撞击的路径，同时优化成本函数（costfunction）。现有的MAPF用于的方法还包括：从可符合性增加问题（reductionstoproblemsfromsatisfiability）、整数线性规划（integerlinearprogramming）、问集编程（answersetprogramming）［YuandLaValle，2013b；Erdemetal．，2013；Surynek，2015］、拟合／受限次优（optimal，bounded－suboptimal）或次优搜寻方法（suboptimalsearchmethod）［Silver，2005；SturtevantandBuro，2006；Ryan，2008；WangandBotea，2008；Standley，2010；StandleyandKorf，2011；WangandBotea，2011；LunaandBekris，2011；Sharonetal．，2013；deWildeetal．，2013；Bareretal．，2014；Goldenbergetal．，2014；WagnerandChoset，2015；Boyarskietal．，2015；Sharonetal．，2015］。

我们最近研究了将MAPF推展到实际场景时经常出现的各种问题，还包括Kiva（AmazonRobotics）仓库系统［Wurmanetal．，2008］（图1）和自动飞行器牵引车［Morrisetal．，2016］。这些问题可以分成两个一般问题：1、为MAPF问题的标准模型研发更慢的方法是过于的，因为在许多实际情况下，可以利用新的结构或必须新的问题模型。2、仅有将MAPF或其新的模型作为人组优化问题展开研究是过于的，因为所产生的MAPF解决方案也必须继续执行。

我们从有所不同的角度辩论了解决问题这两个问题的四个研究方向：1．在许多实际的多代理系统中，在为所有代理寻找最佳路径之前，代理再行被区分成组（team），然后给每个组分配特定的目标，每个代理必须从所在的组中被登录一个目标。我们早已为有所不同组的代理制订了人组目标分配和路径查询（TAPF／targetassignmentandpathfinding）问题来解决问题这个艰难。我们还研发了一个最佳TAPF方法，它可以扩展到几十个组和数百个代理［MaandKoenig，2016］。

2．在许多实际的多代理系统中，代理是电子邮件的（可互相交换的），但是它们的有效载荷所谓电子邮件的（不能互相交换的），并且必须被传送给等价的目标。代理一般来说可以在这样的系统中互相交换其有效载荷。作为第一次尝试，我们设计了包覆互相交换机器人路由（package－exchangerobotrouting／PERR）问题，以解决问题更加多一般化的（容许有效载荷移往的）运输问题［Maetal．，2016］。

在这篇文章中，我们还证明了近似于拟合MAPF解法的困难性（复杂度）。

本文来源：凯发一触即发(中国区)官方网站-www.tj97.com