多智能体路径规划综述

Overview of Multi-Agent Path Finding

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

The multi-agent path finding(MAPF)problem is the fundamental problem of planning paths for multiple agents,where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other.MAPF is widely used in logistics,military,security and other fields.MAPF algorithm can be divided into the centralized planning algorithm and the distributed execution algorithm when the main research results of MAPF at home and abroad are systematically sorted and classified according to different planning methods.The centralized programming algorithm is not only the most classical but also the most commonly used MAPF algorithm.It is mainly divided into four algorithms based on A*search,conflict search,cost growth tree and protocol.The other part of MAPF which is the dis-tributed execution algorithm is based on reinforcement learning.According to different improved techniques,the distributed execution algorithm can be divided into three types:the expert demonstration,the improved communication and the task decomposition.The challenges of existing algorithms are pointed out and the future work is forecasted based on the above classification by comparing the characteristics and applicability of MAPF algorithms and analyzing the advantages and disadvantages of existing algorithms.