最近一篇技术论文，南加州大学和亚马逊机器人公司（Amazon Robotics）研究人员开发一款解决终身多智能代理人路径查找（Multi-Agent Path Finding，MAPF）问题的解决方案，其中一组智能代理人（机器人）必须移动到不断变化的目标位置而不发生碰撞。他们指出，实验可为多达 1 千台智慧代理机器人提供“高品质”解决方案，表现远胜现有方法。
MAPF 是许多自动化系统的核心，如自驾车、无人机群，甚至电子游戏的 AI。毫无疑问，亚马逊最感兴趣的是仓储机器人（Warehouse Robot）适用性，截至去年 12 月，亚马逊在物流配送网络（Fulfillment Network）拥有超过 20 万台移动机器人。驱动单元（Drive Unit）会自动将库存箱或平装包裹从一个位置移动到另一位置，且必须持续移动，以便不断指派新的目标位置。
研究人员的解决方案将 MAPF 问题建模成一个图形，包含由一系列边（线）连接的顶点（点）。顶点对应位置，而边则对应两个相邻位置与一组智慧代理人（例如驱动单元）之间的连结。每台智能代理人都可在每个时步（Timestep）移动到相邻位置，或在目前位置等待。如果两台智能代理人计划同一时步占据相同位置，就会发生碰撞。
（图片来源：ARXIV）
此方案机器人吞吐量更甚其他方法，在少量时步可提升 6 倍速度
此解决方案旨在规划无碰撞路径，以便将智能代理人移动到目标位置，同时最大化平均访问位置数。考量到每次碰撞的时间范围必须解决，同时每条路径的频率必须重新规划，此方案更新每个时步的每台智能代理的起点与目标位置，并计算智慧代理人需要访问所有位置的步数，也会不断指派新目标位置给智慧代理人，直到找到无碰撞路径，并沿着生成的路径移动智慧代理人，并按顺序删除访问过的目标位置。
模拟实验中，研究人员将一个物流配送仓库映射到一个 33×46 的网格，上有 16% 的障碍物，研究人员表示，吞吐量方面，他们的方法优于其他方法。将物流分拣中心（Logistic Sorting Center）映射到 37×77 网格（有 10% 障碍物），某些格子代表输送槽及人们会将包裹放在驱动单元上的工作站，论文并指出，少量时步可在不影响吞吐量的情况下让整体设计框架的速度提高 6 倍。
“我们的设计框架不仅适用于一般图形，而且还能产生更好的吞吐量，”共同作者写道：“整体而言，我们的框架适用一般图形，透过使用者指定的频率呼叫执行重新规划，并能生成灵活的计划，不仅可适应在线设置，而且还可避免对遥远未来的期待会浪费不必要的运算量。”
- Amazon’s AI tool can plan collision-free paths for 1,000 warehouse robots
-
Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
（首图来源：亚马逊）
