多智能体路径规划综述

来源：计算机工程与应用杂志2022年第20期北京时间：

作者：刘志飞, 曹雷, 赖俊, 陈希亮, 陈英

单位：1.陆军工程大学 指挥控制工程学院，南京 210007；2.东部战区总医院 博士后科研工作站，南京 210007；

摘要：多智能体路径规划（multi-agent path finding，MAPF）是为多个智能体规划路径的问题，关键约束是多个智能体同时沿着规划路径行进而不会发生冲突。MAPF在物流、军事、安防等领域有着大量应用。对国内外关于MAPF的主要研究成果进行系统整理和分类，按照规划方式不同，MAPF算法分为集中式规划算法和分布式执行算法。集中式规划算法是最经典和最常用的MAPF算法，主要分为基于[A*]搜索、基于冲突搜索、基于代价增长树和基于规约四种算法。分布式执行算法是人工智能领域兴起的基于强化学习的MAPF算法，按照改进技术不同，分布式执行算法分为专家演示型、改进通信型和任务分解型三种算法。基于上述分类，比较MAPF各种算法的特点和适用性，分析现有算法的优点和不足，指出现有算法面临的挑战并对未来工作进行了展望。

关键词：多智能体路径规划,人工智能,搜索,分布式,强化学习