上海交通大学陈卫东教授团队提出“未知延迟下基于路径协调的鲁棒、快速和可扩展的多智能体寻路算法”，该成果发表在IEEE Transactions on Automation Science and Engineering杂志上。本文提出未建模延迟下基于路径协调的多机器人路径规划或多智能体寻路方法。算法整体采用层次规划思路，在单机器人路径规划层，采用多值决策图（MDD）图结构，提前计算出多个最优路径，方便后续的协调与路径切换，缓解死锁现象和后续的协调难度；在全局多机器人协调层，采用不可逆依赖图（IDG）对机器人之间的避让关系进行编码，以便在死锁产生后可以快速给出机器人的死锁修复方案（因为路径协调时空间解耦特性，并不能保证完全无死锁）；在局部多机器人协调层次采用优先级分配方法进行协调。统计研究、消融研究、极限案例测试等验证方法表明，该方法具有鲁棒、快速、可扩展的优点。论文共同第一作者是硕士生叶伟斌和博士生王汉符，陈卫东教授为通讯作者。

W. Ye, H. Wang, and W. Chen, "Path coordination for robust, fast and scalable multi-agent path finding under unforeseen delays," IEEE Trans. Autom. Sci. Eng., pp. 1–1, 2025, doi: 10.1109/TASE.2025.3615989.

关键词：多智能体寻路，路径协调，运动延迟，多机器人系统，路径规划

原文链接：https://doi.org/10.1109/TASE.2025.3615989

多智能体寻路（MAPF）是当前物流机器人、AGV、智能交通、港口机场调度等应用领域中的共性关键技术。机器人或车辆运动时，常常因为通信、控制精度、定位精度、外界干扰等，受到未建模延迟（指并无对延迟时间、发生概率的先验知识）的影响；且随着应用场景中的机器人或智能体团队的规模越来越大（百、千），在未建模延迟下实现快速且鲁棒的MAPF是一项艰巨的挑战。

针对这些挑战，研究者基于经典的路径协调思路，提出图1所示的层次规划方法。经典的路径协调方法具有简单、快速、解耦的优点，但应用到大规模场景中时，死锁现象加剧，难以进行协调。为了解决以上难题，所提出方法在单机器人路径规划层，采用多值决策图（MDD）图结构，提前计算出多个最优路径，方便后续的协调与路径切换，缓解死锁现象和后续的协调难度；在全局多机器人协调层，采用不可逆依赖图（IDG）对机器人之间的避让关系进行编码，以便在死锁产生后可以快速给出机器人的死锁修复方案（因为路径协调时空间解耦特性，并不能保证完全无死锁）；在局部多机器人协调层次采用优先级分配方法进行协调。

图1：多智能体寻路的层次规划方法架构图

为了验证该方法的有效性，在MAPF公开数据集上，进行了广泛的统计研究、消融研究、极限案例测试。与当前已有方法相比（图2），所提出方法在路径总代价、运行时间、任务完成率、案例覆盖率等均有一定优势，验证了所提出方法的鲁棒性、快速性和扩展性。

图2：与其他方法的对比性能测试结果

陈卫东教授研究团队长期致力于多机器人系统基础理论和应用研究，在多机器人任务分配、任务调度、路径规划、定位与导航等方向有着长期的技术积累，并在机器人物流、巡检等领域与国内外知名企业开展合作。