在最近的技术论文中，南加州大学和亚马逊机器人公司的研究人员探索了解决终身多智能体路径查找（MAPF）问题的解决方案，该解决方案中必须将一组智能体移动到不断变化的目标位置而不会发生碰撞。他们说，在实验中，它可以为多达1,000名代理商提供“高质量”解决方案，大大优于现有方法。

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

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

拟议的解决方案旨在规划无冲突的路径，以将特工移动到其目标位置，同时最大化访问的平均位置数。给定必须解决冲突的时间范围以及需要重新计划路径的频率，解决方案将在每个时间步更新每个业务代表的起点和目标位置，并计算业务代表访问所有位置所需的步骤数。它还连续地向探员分配新的目标位置，然后找到无冲突的路径，并沿这些生成的路径移动探员，并从序列中删除访问的目标位置。

在涉及将执行仓库映射到33 x 46网格（障碍率为16％）的模拟实验中，研究人员表示，在吞吐量方面，他们的方法优于所有其他方法。在一个映射到37 x 77网格（有10％障碍物）的物流分拣中心中，某些单元代表交付斜槽和工作站，人们将包裹放在驱动器上，他们报告说，少量的时间步加快了框架最多可减少6倍，而不会影响吞吐量。

共同作者写道：“ our框架不仅适用于一般图形，而且产生了更好的吞吐量。” “总体而言，我们的框架适用于一般图形，使用用户指定的频率调用重新计划，并且能够生成灵活的计划，这些计划不仅可以适应在线设置，而且还可以避免在遥远的未来上浪费计算工作。