在最近的一篇技术论文中，南加州大学和亚马逊机器人公司的研究人员探索了一种解决终身多智能体路径发现(MAPF)问题的方法，其中一组智能体必须无碰撞地移动到不断变化的目标位置。他们说，在实验中，它可以为多达1000个代理提供“高质量”的解决方案，这比现有的方法要好得多。

MAPF是许多自动化系统的核心部分，例如无人驾驶车辆、无人驾驶飞机机队甚至视频游戏角色AI。毫无疑问，亚马逊对其在仓库机器人上的适用性非常感兴趣。——截至12月，亚马逊的履约网络中有超过20万台移动机器。驱动单元自动将料盒或扁平包装从一个位置移动到另一个位置，并且它们必须继续移动-不断地为它们分配新的目标位置。

研究人员的解决方案将MAPF问题建模为包含由一系列边(线)连接的顶点(节点)的图。顶点对应于位置，而边对应于两个相邻位置和一组代理(例如，驱动单元)之间的连接。在每个时间步骤中，每个代理都可以移动到相邻的位置或在其当前位置等待。如果两个代理计划在同一时间步骤占据同一位置，则会发生冲突。

所提出的解决方案旨在规划无冲突路径，将代理移动到其目标位置，并最大化访问位置的平均数量。给定必须解决冲突的时间范围和重新路由的频率，解决方案将在每个时间步骤更新每个业务代表的起点和目标位置，并计算业务代表访问所有位置所需的步骤数。它还会不断为代理分配新的目标位置，然后找到无冲突的路径，沿着这些生成的路径移动代理，并从序列中删除访问过的目标位置。

在涉及将执行仓库映射到3346网格(障碍率为16%)的模拟实验中，研究人员表明他们的方法在吞吐量方面优于所有其他方法。在一个映射到37 x 77网格的物流分拣中心(有10%的障碍物)，一些单元代表递送槽和工作站，人们将包裹放在驱动器上。他们报告说，少量的时间步长可以加快帧的速度，并将其减少多达6倍，而不会影响吞吐量。

合著者写道：“[o] ur框架不仅适用于通用图形，还可以产生更好的吞吐量。”“一般来说，我们的框架适用于一般的图形。它使用用户指定的频率来调用重调度，并能生成灵活的计划，既能适应在线设置，又能避免浪费大量计算时间来预见遥远的未来。”