南加州大学(University of Southern California)和亚马逊机器人公司(Amazon Robotics)的研究人员探索了一种解决终身多智能体寻路(MAPF)问题的方法。在MAPF中，一组智能体必须被移动到不断变化的目标位置，而不会发生碰撞。他们说，在实验中，它可以为多达1000种药剂提供“高质量”的解决方案，显著优于现有的方法。

MAPF是许多自动系统的核心部分，比如无人驾驶汽车、无人机群，甚至是电子游戏中的人物AI。毫无疑问，亚马逊感兴趣的是它对仓储机器人的适用性。截至去年12月，亚马逊在其物流网络中拥有超过20万台移动机器。驱动单元自动将库存舱或平板包从一个位置移动到另一个位置，并且它们必须继续移动，它们被连续分配到新的目标位置。

研究者的解决方案将MAPF问题建模为含有由一系列边（线）连接的顶点（节点）的图形。垂直点与位置对应，边缘对应两个相邻地点和一组代理（如驱动单元）之间的连接。在每个时间步，每个代理都可以移动到相邻位置或等待当前位置。如果两个代理计划在同一时间占据同一个位置,就会发生碰撞。

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

在模拟实验中，研究人员将一个仓库映射到一个33×46的网格上，网格上有16%的障碍物。研究人员说，他们的方法在吞吐量方面超过了其他所有方法。和物流分拣中心映射到37 -到- 77网格以10%的障碍,在某些细胞代表交付降落伞和工作站在人类把包放在驱动单元,他们报告说,少量的步伐加快了框架至多6倍的前提下的吞吐量。

合著者写道。“总的来说，我们的框架适用于一般的图形，使用用户指定的频率调用重新规划，并且能够生成灵活的计划，不仅能够适应在线设置，而且避免在预测遥远的未来时浪费计算工作。”