Survey of Cooperative Multi-Agent Path Finding

doi:10.16182/j.issn1004731x.joss.25-0576

Abstract

Abstract:

Cooperative multi-agent path finding (Co-MAPF) has been widely applied in fields such as UAV formation and multi-agent systems, which enhances the overall system efficiency through task collaboration, path planning, and task execution among multiple agents. This paper introduced three main system architectures, namely centralized, distributed, and hybrid, along with their advantages and disadvantages based on the definition of the Co-MAPF problem, categorized, and reviewed mainstream Co-MAPF algorithms, including those based on sampling, search, intelligent optimization, and learning. Furthermore, this paper analyzed the main current challenges faced by Co-MAPF algorithms on the basis of summarizing existing research and outlined the future development directions.

Key words: multi-agent, cooperative path finding, task assignment, collaborative control

CLC Number:

TP181

Xiong Jun, Zhang Wenbo, Xiong Zhi, Zhou Feng, Yang Bo. Survey of Cooperative Multi-Agent Path Finding[J]. Journal of System Simulation, 2025, 37(12): 3033-3049.

Figures/Tables 14

Table 1

Table 2

Fig. 1

Table 3

Algorithms based on sampling

类型	算法	核心理论	特点
RRT	改进RRT*^[16]	通过目标偏向采样、动态障碍物建模、运动约束集成进行优化	解决动态环境下多机器人协同避障问题，适用于复杂环境协同任务
	Multi-RRT*^[17]	基于单智能体动态RRT*的分散迭代算法，采用“规划-比较-分配”框架，冲突方视为动态障碍进行局部重规划	解决共享环境协同路径规划，保证有限迭代内收敛到无冲突路径
	RRT*的领导者-跟随者^[18]	双层结构：领导者离线规划全局路径，跟随者通过网络/共识协议协同，并融合APF确保安全距离	用于动态障碍环境下的轨迹规划与跟踪，确保智能体间及与障碍物间的安全距离
	MA-RRT*FN^[19]	对MA-RRT*的改进，引入动态节点移除机制，移除“弱节点”以限制节点数量	降低内存消耗的同时保持规划性能，内存需求低且固定
	MFM-RRT*^[20]	基于RRT*改进，引入探索期和切割周期，提出新路径成本函数并结合APF减少编队变形	用于有严格编队保持要求的任务，保持安全距离
	改进拍卖算法和QS-RRT^[21]	结合改进拍卖算法和QS-RRT(quick and smooth convergence RRT)，引入节点快速收敛策略和协同约束机制	保证路径长度近似最优，降低到达目标时间，提升整体任务执行效率
PRM	改进PRM(能量感知)^[22]	优化采样空间，考虑智能体的能量消耗	智能体根据能量状况规划路径，避免因个体能量不足影响整体任务
	改进PRM(鲁棒性)^[23]	从环境建模、算法优化、路径后处理方面进行改进	提升算法在复杂环境中的鲁棒性和可靠性
	基于“存活策略”^[24]	结合Boustrophedon运动和回溯点检测，实时感知并分解任务，结合PRM生成路径	分布式探索，实时环境感知，生成无冲突路径
Voronoi	结合其他路径规划算法^[25]	基于Voronoi图，结合其他路径规划算法进行协同定位	实现全局目标的无冲突协同定位，提升整体路径规划的效率和效果

Table 3

Fig. 2

Table 4

Algorithms based on search

类型	算法	核心理论	特点
A*	EPEA(enhanced partial expansion A)及其变体^[26-27]	通过算子选择函数(operator selection function, OSF)仅生成当前所需的子节点	优化节点生成效率，避免冗余节点，减少内存和时间消耗
	冲突导向的窗口式分层合作A算法(conflict oriented windowed hierarchical cooperative A, CO-WHCA*)^[28]	基于冲突导向的窗口分层协作A*，动态识别冲突点生成协调窗口	改进在线协同效率，减少无效规划复杂度，动态确定最优协调顺序
	A、A++以及带重构的A*++^[29]	引入成本感知启发函数	提高计算效率，保证最优性，减少节点扩展量，用于动态环境
	冲突搜索与时空混合的A算法(conflict search and space-time hybrid A, CS-STHA)^[30]	融合冲突搜索机制与改进的时空混合路径规划技术	有效解决协同避碰难题
	改进协同A算法(improved cooperative A, ICA*)^[31]	引入转弯成本与路径重复成本，结合动态权重引导策略	减少转向和重叠，优化总移动步数、完成时间和等待时长
	基于时间的协同A*^[32]	引入时间维度扩展状态空间，时序优先级调度	实现时空联合避障，保证最优性，处理动态协调性与计算效率平衡
	基于讨价还价博弈的改进型分层协作A算法(bargaining game based improving hierarchical cooperative A, B-IHCA*)^[33]	通过协商博弈机制构造框架，加入带熔断机制的改进HCA*作为内核	通过调整迭代达成无冲突协调路径方案
D*	D*分布式求解器^[34]	D*全局规划生成探索点，分布式求解器分配任务，自适应规划器生成轨迹	融合多尺度规划与分布式协作，用于部分未知城市环境，优化行驶距离
RHC	后退水平图搜索算法(receding horizon graph search, RHGS)^[35]	结合后退水平控制与图搜索，采用同步组合FSA(finite state automaton)描述协同，惰性边缘评估减少碰撞检测	结合实时性与最优性，减少碰撞检测计算量
OBS	基于顺序搜索和时间调度的算法(order-based search with kinematics arrival time scheduling, OBS-KATS)^[36]	双层级：高层基于顺序搜索，低层进行运动学到达时间调度	结合全局顺序优化与运动学调度，兼具最优性、完备性和高效性
LNS	协同并行大邻域搜索算法(cooperative parallel large neighborhood search, CPLNS)^[37]	引入分组协作策略，采用SIPPS(safe interval path planning with soft constraints)组内共享最优解，并整合模拟退火增强搜索能力	解决大规模MAPF问题，改进LNS的并行扩展性与效率，优化通信与内存效率
M*	TC-M*^[38]	基于M的冲突检测和MOM的多目标处理技术，在联合图上搜索，动态扩展子图	对所有团队协作路径规划问题(teamwise cooperative path finding, TCPF)完备，保证终止
CBS	TC-CBS^[38]	基于冲突搜索(conflict-based search, CBS)，并扩展到多团队、多目标场景，高层约束管理，低层单智能体规划	在完全协作的场景中，TC-CBS是完备的，能找到所有成本唯一的帕累托最优解
CBS	TC-CBS-t^[39]	引入目标变换，通过为每个团队的目标函数添加一个小的加权项，将问题转化为完全协作问题，从而保证算法完备性	TC-CBS-t解决了TC-CBS的不完备性问题，确保算法在有限时间内终止
LaCAM	LaCAM*^[40]	在LaCAM算法(lazy constraints addition search for MAPF)基础上，增加持续搜索和重写节点间父级关系的机制	具有完备性和最优性，能在找到初始解后逐步优化解的质量
	改进LaCAM*^[41]	提出多种技术，包括非确定性节点提取、递归使用LaCAM*等，融合这些技术提升解的质量	能在实时性要求下提升解的质量，且能处理多达10 000个智能体的极端场景
	Real-Time LaCAM^[42]	通过增量构建LaCAM深度优先搜索，在毫秒级截止时间内计算部分路径并重新规划	运行时间极短，适用于拥挤环境，且可与机器学习策略结合
PBS	D-PBS(dueling priority-based search)^[43]	高层：按冲突对数量递增顺序扩展子节点；低层：优先扩展冲突数量最少的节点	能更快减少冲突，提升在高智能体密度和多障碍物环境下的性能
PBS	贪婪优先级搜索算法(greedy priority-based search, GPBS) ^[44]	整合低层的交替对决式冲突，解决和高层的同伦群优先级绑定技术，在PBS框架下协调多智能体运动	有效解决拥挤环境中的死锁问题，提高在大量非完整约束机器人场景下的可扩展性

Table 4

Fig. 3

Table 5

Algorithms based on intelligent optimization

类型	算法	核心理论	特点
遗传算法	分散式异步协作遗传算法(decentralized asynchronous collaborative GA, DAC-GA)^[45]	分散式异步协作GA，智能体依赖本地GA和稀疏通信交换的“交接值”实现协作，并异步更新交接值	低通信开销，平衡局部优化与全局协作，支持动态环境实时响应
粒子群优化算法	SRVPSO(Simultaneous Replanning Vectorized PSO)^[46]	耦合任务分配与路径规划，任务分配采用妥协视图模型，路径规划采用SRVPSO，碰撞避免	通过PSO群体智能实现高效协同，支持动态环境实时重规划
	妥协视图(compromise view, CV)/最近邻搜索(NNS)^[47]	对比2种任务分配模型，两者均采用SRVPSO进行路径规划	分析不同任务分配策略，CV路径短耗时长，NNS计算快路径略长
	AFSA-PSO^[48]	结合PSO群体搜索和人工鱼群算法(artificial fish swarm algorithm, AFSA)局部觅食模拟，通过粒子位置编码进行协同策略，分群体并行优化并引入变异机制增强多样性	解决集中式控制局限，兼具全局收敛性与快速局部收敛能力
	IPPSO(improved potential field-based PSO)^[49-50]	改进的PSO算法	用于未知环境协同目标搜索，在狭窄区域表现好，能高效搜索覆盖目标簇
蚁群优化算法	改进ACO^[51]	智能体动态采集信息更新信息素，结合计算机视觉调整启发式权重	利用信息素机制实现间接协作
	基于ACO^[52]	模拟蚁群自组织和正反馈，引入模糊神经网络处理不确定性，结合主成分分析(principle component analysis, PCA)评估效率	实现分布式全局最优路径搜索，提升复杂环境中自适应性与协作效率
	蚁群信息素决策^[53]	将信息素机制与分布式通信结合	实现无人集群自主协同与动态环境适应
萤火虫算法	ASBAF^[54]	MAS和萤火虫算法融合，结合信任机制和奖励驱动策略，利用FA优化路径选择	有效任务分配与协作决策，应对复杂事件能力强，性能优势明显
甲虫触角搜索算法	BAS(beetle antennae search, BAS)+PSO^[55]	融合BAS和PSO	解决传统PSO在机器人数量较少时易过早收敛的问题
BNN	双改进生物启发神经网络算法(dual improved bio-inspired neural network, DIBNN)^[56]	通过改进的神经网络模型和协作机制，构建了DIBNN，从而实现未知复杂环境下的多机器人高效协同区域搜索	兼顾搜索效率与路径优化，为未知环境协同任务提供新思路

Table 5

Fig. 4

Table 6

Table 7

Table 8

Table 9

Fig. 5

References 83

[1]	Torreño Alejandro, Onaindia Eva, Komenda Antonín, et al. Cooperative Multi-agent Planning: A Survey[J]. ACM Computing Surveys, 2018, 50(6): 84.
[2]	Stern Roni, Sturtevant Nathan R, Felner Ariel, et al. Multi-agent Pathfinding: Definitions, Variants, and Benchmarks[C]//Proceedings of the Twelfth International Symposium on Combinatorial Search (SoCS 2019). Palo Alto: AAAI Press, 2019: 151-158.
[3]	Greshler Nir, Gordon Ofir, Salzman Oren, et al. Cooperative Multi-agent Path Finding: Beyond Path Planning and Collision Avoidance[C]//2021 International Symposium on Multi-robot and Multi-agent Systems (MRS). Piscataway: IEEE, 2021: 20-28.
[4]	Ho Florence, Geraldes Rúben, Gonçalves Artur, et al. Decentralized Multi-agent Path Finding for UAV Traffic Management[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(2): 997-1008.
[5]	Ho Florence, Salta Ana, Geraldes Ruben, et al. Multi-agent Path Finding for UAV Traffic Management[C]//Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems. Richland: International Foundation for Autonomous Agents and Multiagent Systems, 2019: 131-139.
[6]	Choudhury S, Solovey Kiril, Kochenderfer M, et al. Coordinated Multi-agent Pathfinding for Drones and Trucks Over Road Networks[EB/OL]. (2022-02-10) [2025-04-16]. .
[7]	Xiang Hongyu, Han Yuhang, Pan Nan, et al. Study on Multi-UAV Cooperative Path Planning for Complex Patrol Tasks in Large Cities[J]. Drones, 2023, 7(6): 367.
[8]	Huang Taoan, Li Jiaoyang, Koenig S, et al. Anytime Multi-agent Path Finding via Machine Learning-guided Large Neighborhood Search[C]//Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2022: 9368-9376.
[9]	Li Jiaoyang, Tinka A, Kiesel S, et al. Lifelong Multi-agent Path Finding in Large-scale Warehouses[C]//Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. Richland: International Foundation for Autonomous Agents and Multiagent Systems, 2020: 1898-1900.
[10]	Phan T, Phan Timy, Koenig S. Generative Curricula for Multi-agent Path Finding via Unsupervised and Reinforcement Learning[J]. Journal of Artificial Intelligence Research, 2025, 82: 2471-2534.
[11]	Sturtevant N R. Benchmarks for Grid-based Pathfinding[J]. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(2): 144-148.
[12]	Gebser Martin, Obermeier Philipp, Otto Thomas, et al. Experimenting with Robotic Intra-logistics Domains[J]. Theory and Practice of Logic Programming, 2018, 18(3/4): 502-519.
[13]	Skrynnik Alexey, Andreychuk Anton, Borzilov Anatolii, et al. POGEMA: A Benchmark Platform for Cooperative Multi-agent Pathfinding[EB/OL]. (2025-04-08) [2025-04-16]. .
[14]	Gul Faiza, Mir Adnan, Mir Imran, et al. A Centralized Strategy for Multi-agent Exploration[J]. IEEE Access, 2022, 10: 126871-126884.
[15]	Kantamneni A, Brown L E, Parker G, et al. Survey of Multi-agent Systems for Microgrid Control[J]. Engineering Applications of Artificial Intelligence, 2015, 45: 192-203.
[16]	Li Yang, Cui Rongxin, Yang Chenguang, et al. Multi-robot Path Planning Based on the Developed RRT* Algorithm[C]//Proceedings of the 32nd Chinese Control Conference. Piscataway: IEEE, 2013: 7049-7053.
[17]	Verbari Paolo, Bascetta Luca, Prandini Maria. Multi-agent Trajectory Planning: A Decentralized Iterative Algorithm Based on Single-agent Dynamic RRT*[C]//2019 American Control Conference (ACC). Piscataway: IEEE, 2019: 1977-1982.
[18]	Agachi C, Arvin F, Hu Junyan. RRT*-based Leader-follower Trajectory Planning and Tracking in Multi-agent Systems[C]//2024 IEEE 12th International Conference on Intelligent Systems (IS). Piscataway: IEEE, 2024: 1-6.
[19]	Jiang Jinmingwu, Wu Kaigui. Cooperative Pathfinding Based on Memory-efficient Multi-agent RRT*[J]. IEEE Access, 2020, 8: 168743-168750.
[20]	Zhu Yiwen, Hu Jiawei, Xiong Zhenhua. Multi-agent Formation Maintaining RRT* (MFM-RRT*) Considering Formation Maintenance[C]//2024 IEEE International Conference on Advanced Intelligent Mechatronics (AIM). Piscataway: IEEE, 2024: 1518-1523.
[21]	Li Qingze, Hua Yongzhao, Zhai Haoran, et al. Multi-agent Weapon Target Assignment and Cooperative Path Planning Based on QS-RRT Algorithm[C]//2022 41st Chinese Control Conference (CCC). Piscataway: IEEE, 2022: 4909-4914.
[22]	Li Weimin, Wang Lei, Zou Awei, et al. Path Planning for UAV Based on Improved PRM[J]. Energies, 2022, 15(19): 7267.
[23]	Jin Qingeng, Hu Qingwu, Zhao Pengcheng, et al. An Improved Probabilistic Roadmap Planning Method for Safe Indoor Flights of Unmanned Aerial Vehicles[J]. Drones, 2023, 7(2): 92.
[24]	Koval Anton, Sina Sharif Mansouri, Nikolakopoulos George. Multi-agent Collaborative Path Planning Based on Staying Alive Policy[J]. Robotics, 2020, 9(4): 101.
[25]	Huang Chaochun, Du Bin, Chen Mou. Multi-UAV Cooperative Online Searching Based on Voronoi Diagrams[J]. IEEE Transactions on Aerospace and Electronic Systems, 2024, 60(3): 3038-3049.
[26]	Goldenberg Meir, Felner Ariel, Sturtevant N, et al. Optimal-generation Variants of EPEA*[C]//Proceedings of the International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2013: 89-97.
[27]	Goldenberg Meir, Felner Ariel, Stern Roni, et al. Enhanced Partial Expansion A*[J]. Journal of Artificial Intelligence Research, 2014, 50(1): 141-187.
[28]	Bnaya Zahy, Felner Ariel. Conflict-oriented Windowed Hierarchical Cooperative A*[C]//2014 IEEE International Conference on Robotics and Automation (ICRA). Piscataway: IEEE, 2014: 3743-3748.
[29]	Votion J, Cao Yongcan. Diversity-based Cooperative Multivehicle Path Planning for Risk Management in Costmap Environments[J]. IEEE Transactions on Industrial Electronics, 2019, 66(8): 6117-6127.
[30]	Yao Jiyu, Longhui Gang. Ship Collaborative Path Planning Method Based on CS-STHA[J]. Journal of Marine Science and Engineering, 2022, 10(10): 1504.
[31]	Liu Yiming, Chen Mengxia, Huang Hejiao. Multi-agent Pathfinding Based on Improved Cooperative A* in Kiva System[C]//2019 5th International Conference on Control, Automation and Robotics (ICCAR). Piscataway: IEEE, 2019: 633-638.
[32]	Gibson J, Schuler T, McGuire L, et al. Swarm and Multi-agent Time-based A* Path Planning for Lighter-than-air Systems[J]. Unmanned Systems, 2020, 8(3): 253-260.
[33]	张凯翔, 毛剑琳, 向凤红, 等. 基于讨价还价博弈机制的B-IHCA*多机器人路径规划算法[J]. 自动化学报, 2023, 49(7): 1483-1497.
	Zhang Kaixiang, Mao Jianlin, Xiang Fenghong, et al. B-IHCA*, a Bargaining Game Based Multi-agent Path Finding Algorithm[J]. Acta Automatica Sinica, 2023, 49(7): 1483-1497.
[34]	Vokřínek Jiří, Komenda Antonín, Pěchouček Michal. Cooperative Agent Navigation in Partially Unknown Urban Environments[C]//Proceedings of the 3rd International Symposium on Practical Cognitive Agents and Robots. New York: ACM, 2010: 41-48.
[35]	Scheffe Patrick, V A Pedrosa Matheus, Flaßkamp Kathrin, et al. Receding Horizon Control Using Graph Search for Multi-agent Trajectory Planning[J]. IEEE Transactions on Control Systems Technology, 2023, 31(3): 1092-1105.
[36]	Yan Zhongxia, Zheng Han, Wu C. Multi-agent Path Finding for Cooperative Autonomous Driving[C]//2024 IEEE International Conference on Robotics and Automation (ICRA). Piscataway: IEEE, 2024: 12361-12367.
[37]	Chen Kai, Qu Qingjun, Zhu Feng, et al. CPLNS: Cooperative Parallel Large Neighborhood Search for Large-scale Multi-agent Path Finding[J]. IEEE Transactions on Parallel and Distributed Systems, 2024, 35(11): 2069-2086.
[38]	Ren Zhongqiang, Zhang Chaoran, Rathinam S, et al. Search Algorithms for Multi-agent Teamwise Cooperative Path Finding[C]//2023 IEEE International Conference on Robotics and Automation (ICRA). Piscataway: IEEE, 2023: 1407-1413.
[39]	Ren Zhongqiang, Cai Yilin, Wang Hesheng. Multi-agent Teamwise Cooperative Path Finding and Traffic Intersection Coordination[C]//2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Piscataway: IEEE, 2024: 7990-7995.
[40]	Okumura K. Improving Lacam for Scalable Eventually Optimal Multi-agent Pathfinding[C]//Proceedings of the Thirty-second International Joint Conference on Artificial Intelligence. California: IJCAI, 2023: 243-251.
[41]	Okumura K. Engineering LaCAM*: Towards Real-time, Large-scale, and Near-optimal Multi-agent Pathfinding[C]//Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems. Richland: International Foundation for Autonomous Agents and Multiagent Systems, 2024: 1501-1509.
[42]	Liang Runzhe, Veerapaneni R, Harabor Daniel, et al. Real-time LaCAM for Real-time MAPF[C]//Proceedings of the International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2025: 196-200.
[43]	Zhang Xiaotong, Xiong Gang, Wang Yuanjing, et al. D-PBS: Dueling Priority-based Search for Multiple Nonholonomic Robots Motion Planning in Congested Environments[J]. IEEE Robotics and Automation Letters, 2024, 9(7): 6288-6295.
[44]	Chan S H, Stern Roni, Felner Ariel, et al. Greedy Priority-based Search for Suboptimal Multi-agent Path Finding[C]//Proceedings of the International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2023: 11-19.
[45]	Pallin Martin, Rashid Jayedur, Ögren Petter. A Decentralized Asynchronous Collaborative Genetic Algorithm for Heterogeneous Multi-agent Search and Rescue Problems[C]//2021 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR). Piscataway: IEEE, 2021: 1-8.
[46]	Biswas Sumana, Anavatti Sreenatha G, Garratt Matthew A. Particle Swarm Optimization Based Co-operative Task Assignment and Path Planning for Multi-agent System[C]//2017 IEEE Symposium Series on Computational Intelligence (SSCI). Piscataway: IEEE, 2017: 1-6.
[47]	Biswas Sumana, Anavatti Sreenatha G, Garratt Matthew A. A Time-efficient Co-operative Path Planning Model Combined with Task Assignment for Multi-agent Systems[J]. Robotics, 2019, 8(2): 35.
[48]	Zuo Jiankai, Chen Jiatong, Tan Yaxin, et al. A Multi-agent Collaborative Work Planning Strategy Based on AFSA-PSO Algorithm[C]//2019 International Conference on Robots & Intelligent System (ICRIS). Piscataway: IEEE, 2019: 254-257.
[49]	Cai Yifan, Yang S X. An Improved PSO-based Approach with Dynamic Parameter Tuning for Cooperative Target Searching of Multi-robots[C]//2014 World Automation Congress (WAC). Piscataway: IEEE, 2014: 616-621.
[50]	Cai Yifan, Yang S X. An Improved PSO-based Approach with Dynamic Parameter Tuning for Cooperative Multi-robot Target Searching in Complex Unknown Environments[J]. International Journal of Control, 2013, 86(10): 1720-1732.
[51]	Lhoussaine Ait Ben Mouh, Baslam Mohamed, Ouhda Mohamed, et al. Ant Trajectory Planning with Multi-agents Collaboration and Computer Vision[C]//International Conference on Advanced Intelligent Systems for Sustainable Development (AI2SD'2023). Cham: Springer Nature Switzerland, 2024: 83-91.
[52]	Xie Qian, Chen Weiyi, Zhuang Yumu. Research on Task Planning and Efficiency Evaluation of Multi-agent Collaborative Search Based on Ant Colony Optimization[C]//2023 3rd International Signal Processing, Communications and Engineering Management Conference (ISPCEM). Piscataway: IEEE, 2023: 302-307.
[53]	吴傲, 杨任农, 梁晓龙, 等. 基于信息素决策的无人机集群协同搜索算法[J]. 北京航空航天大学学报, 2021, 47(4): 814-827.
	Wu Ao, Yang Rennong, Liang Xiaolong, et al. Cooperative Search Algorithm Based on Pheromone Decision for UAV Swarm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(4): 814-827.
[54]	Gharrad Hana, Jabeur Nafaa, Ansar Ul-Haque Yasar, et al. A Five-step Drone Collaborative Planning Approach for the Management of Distributed Spatial Events and Vehicle Notification Using Multi-agent Systems and Firefly Algorithms[J]. Computer Networks, 2021, 198: 108282.
[55]	Yang Fan, Li Sheng, Chen Chen. Multi-robot Cooperative Search Method Based on Biological Heuristic Algorithm[C]//2021 China Automation Congress (CAC). Piscataway: IEEE, 2021: 642-646.
[56]	Chen Bo, Zhang Hui, Zhang Fangfang, et al. DIBNN: A Dual-improved-BNN Based Algorithm for Multi-robot Cooperative Area Search in Complex Obstacle Environments[J]. IEEE Transactions on Automation Science and Engineering, 2025, 22: 2361-2374.
[57]	Mohammed El Habib Souidi, Toufik Messaoud Maarouk, Ledmi Abdeldjalil. Multi-agent Ludo Game Collaborative Path Planning Based on Markov Decision Process[C]//Inventive Systems and Control. Singapore: Springer Singapore, 2021: 37-51.
[58]	Megherbi D B, Kim M. A Collaborative Distributed Multi-agent Reinforcement Learning Technique for Dynamic Agent Shortest Path Planning Via Selected Sub-goals in Complex Cluttered Environments[C]//2015 IEEE International Multi-Disciplinary Conference on Cognitive Methods in Situation Awareness and Decision. Piscataway: IEEE, 2015: 118-124.
[59]	Lamini Chaymaa, Fathi Youssef, Benhlima Said. Collaborative Q-learning Path Planning for Autonomous Robots Based on Holonic Multi-agent System[C]//2015 10th International Conference on Intelligent Systems: Theories and Applications (SITA). Piscataway: IEEE, 2015: 1-6.
[60]	Huang Beinuo, Chen Xin, Sun Yipu, et al. Multi-agent Cooperative Strategy Learning Method Based on Transfer Learning[C]//2022 13th Asian Control Conference (ASCC). Piscataway: IEEE, 2022: 1095-1100.
[61]	Wang Zilu, Liu Lin, Jiangtao Lü. Multi-UAV Cooperative Exploration Route Planning Based on Reinforcement Learning[C]//2024 6th International Conference on Electronic Engineering and Informatics (EEI). Piscataway: IEEE, 2024: 1436-1441.
[62]	Lu Maikao, Ge Mingfeng, Ding Tengfei, et al. SDF-based Reinforcement Learning for Adaptive Path Planning and Formation Control of Multiagent Systems[J]. IEEE Internet of Things Journal, 2025, 12(12): 19944-19954.
[63]	Xiao Ziren, Li Peisong, Liu Chang, et al. MACNS: A Generic Graph Neural Network Integrated Deep Reinforcement Learning Based Multi-agent Collaborative Navigation System for Dynamic Trajectory Planning[J]. Information Fusion, 2024, 105: 102250.
[64]	Poudel Sabitri, Moh Sangman. Priority-aware Task Assignment and Path Planning for Efficient and Load-balanced multi-UAV Operation[J]. Vehicular Communications, 2023, 42: 100633.
[65]	Zhao Xiaoru, Yang Rennong, Zhong Liangsheng, et al. Multi-UAV Path Planning and Following Based on Multi-agent Reinforcement Learning[J]. Drones, 2024, 8(1): 18.
[66]	Shang Zhihao, Mao Zhiqiang, Zhang Huachao, et al. Collaborative Path Planning of Multiple Carrier-based Aircraft Based on Multi-agent Reinforcement Learning[C]//2022 23rd IEEE International Conference on Mobile Data Management (MDM). Piscataway: IEEE, 2022: 512-517.
[67]	Murata Kazuhi, Miyazaki Kenta, Matsunaga Nobutomo. Experiment of Cooperative Transportation Using Multi-robots by Multi-agent Deep Deterministic Policy Gradient[C]//2022 13th Asian Control Conference (ASCC). Piscataway: IEEE, 2022: 1120-1123.
[68]	Liu Qi, Gao Jianqi, Zhu Dongjie, et al. Multi-agent Target Assignment and Path Finding for Intelligent Warehouse: A Cooperative Multi-agent Deep Reinforcement Learning Perspective[EB/OL]. (2024-10-27) [2025-04-25]. .
[69]	Shen Hang, Li Xiang, Wang Yan, et al. Collaborative Path Penetration in 5G-IoT Networks: A Multi-agent Deep Reinforcement Learning Approach[J]. Peer-to-Peer Networking and Applications, 2025, 18(3): 113.
[70]	Liu Ping, Ma Xiangyu, Ding Jie, et al. Multi-agent Collaborative Path Planning Algorithm with Reinforcement Learning and Combined Prioritized Experience Replay in Internet of Things[J]. Computers and Electrical Engineering, 2024, 116: 109193.
[71]	司鹏搏, 吴兵, 杨睿哲, 等. 基于多智能体深度强化学习的无人机路径规划[J]. 北京工业大学学报, 2023, 49(4): 449-458.
	Si Pengbo, Wu Bing, Yang Ruizhe, et al. UAV Path Planning Based on Multi-agent Deep Reinforcement Learning[J]. Journal of Beijing University of Technology, 2023, 49(4): 449-458.
[72]	Lu Siyao, Xu Rui, Li Zhaoyu, et al. Lunar Rover Collaborated Path Planning with Artificial Potential Field-based Heuristic on Deep Reinforcement Learning[J]. Aerospace, 2024, 11(4): 253.
[73]	Li Qingbiao, Gama F, Ribeiro A, et al. Graph Neural Networks for Decentralized Multi-robot Path Planning[C]//2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Piscataway: IEEE, 2020: 11785-11792.
[74]	Dai Hanqi, Lu Weining, Yang Jun, et al. Cooperative Path Planning of Multi-agent Based on Graph Neural Network[C]//2022 34th Chinese Control and Decision Conference (CCDC). Piscataway: IEEE, 2022: 5620-5624.
[75]	Luo Tianze, Subagdja Budhitama, Wang Di, et al. Multi-agent Collaborative Exploration through Graph-based Deep Reinforcement Learning[C]//2019 IEEE International Conference on Agents (ICA). Piscataway: IEEE, 2019: 2-7.
[76]	Wang Weizheng, Mao Le, Wang Ruiqi, et al. Multi-robot Cooperative Socially-aware Navigation Using Multi-agent Reinforcement Learning[C]//2024 IEEE International Conference on Robotics and Automation (ICRA). Piscataway: IEEE, 2024: 12353-12360.
[77]	Parada L, Yu K, Angeloudis P. IntNet: A Communication-driven Multi-agent Reinforcement Learning Framework for Cooperative Autonomous Driving[J]. IEEE Robotics and Automation Letters, 2025, 10(3): 2478-2485.
[78]	Li Qingbiao, Lin Weizhe, Liu Zhe, et al. Message-aware Graph Attention Networks for Large-scale Multi-robot Path Planning[J]. IEEE Robotics and Automation Letters, 2021, 6(3): 5533-5540.
[79]	Ma Ziyuan, Luo Yudong, Ma Hang. Distributed Heuristic Multi-agent Path Finding with Communication[C]//2021 IEEE International Conference on Robotics and Automation (ICRA). Piscataway: IEEE, 2021: 8699-8705.
[80]	Sartoretti G, Kerr J, Shi Yunfei, et al. PRIMAL: Pathfinding via Reinforcement and Imitation Multi-agent Learning[J]. IEEE Robotics and Automation Letters, 2019, 4(3): 2378-2385.
[81]	Luo Zhiyao, Sartoretti Guillaume. Deep Reinforcement Learning Based Multi-agent Pathfinding[EB/OL]. [2025-05-18]..
[82]	Damani Mehul, Luo Zhiyao, Wenzel Emerson, et al. PRIMAL₂: Pathfinding Via Reinforcement and Imitation Multi-agent Learning-lifelong[J]. IEEE Robotics and Automation Letters, 2021, 6(2): 2666-2673.
[83]	Liu Jiaming, Zheng Zhi. A Path Planning Method Based on Collaborative Learning for Multi-robot with Connectivity and Obstacle Avoidance Constraints[C]//2022 China Automation Congress (CAC). Piscataway: IEEE, 2022: 6770-6775.

对比维度	MAPF	Co-MAPF
核心目标	为每个智能体规划无碰撞路径，确保所有智能体从起点到达终点，主要关注路径可行性	在无碰撞的基础上，通过智能体间协同合作提升整体性能
协作方式	通过优先级规划、冲突避免等被动方式避免碰撞，智能体间无主动信息共享或目标协调	引入主动协作机制，智能体主动调整行为以配合其他个体
信息依赖	依赖局部或全局信息进行路径规划，但不强调智能体间的实时信息交互	需要智能体间通信，以实现动态协同决策
应用场景	对整体效率要求较低、智能体交互简单的场景	适用于大规模、高动态场景，需提升整体系统效率

架构	优点	缺点
集中式	全局优化路径质量高；规划效率稳，适合静态小规模场景	计算复杂度指数级增长，可扩展性差；依赖中央节点单点容错差
分布式	动态适应性强，支持大规模集群；通信压力低	局部优化易导致全局次优；依赖高效协同协议，冲突风险高
混合式	平衡规划质量与灵活性；部分容错性提升	接口设计复杂，层级通信瓶颈需额外管理；全局约束可能导致局部僵化

算法	核心理论	特点
Q-learning^[57]	设计动态奖励函数，引入协作优先级策略	通过Q-learning和设计策略引导协作
混合势场+Q-learning^[58]	混合势场与Q-learning结合学习局部路径，利用环境知识进行跨子目标增量学习	减少随机探索步数，分布式实现
基于Holonic系统的协作Q-learning^[59]	本地决策更新本地Q表，头Holon协作整合经验，通过置信度权重更新全局Q表	平衡个体贡献可靠性，分层协作架构
Q-learning+迁移学习(transfer learning, TL)^[60]	多智能体并行学习生成独立Q表，通过迁移学习整合子Q表作为初始Q表	加速整体学习过程
VDN^[61]	采用价值分解网络(value-decomposition networks, VDN)	解决因局部观测导致的“虚假奖励”问题，避免“懒惰智能体”现象
符号距离场(signed distance field, SDF)^[62]	SDF-FPP(SDF-based formation path planning)+RL生成虚拟领导者轨迹，AOFC算法(adaptive-offset formation control)将SDF信息转为动态偏移函数	将SDF引入编队控制，实现编队形变避障。维持编队结构，处理输入饱和和不确定扰动

算法	核心理论	特点
MACNS(multi-agent collaborative navigation system)^[63]	设计图近端策略优化算法，将GNN集成到策略网络	实现智能体的同质化决策，优于传统PPO方法
AMTP^[64]	将AC运用于多智能体强化学习(MARL)并结合DDPG	协同优化任务分配和路径规划；适用动态环境及高实时性场景
SAC+AIT*^[65]	将SAC算法与基于采样的路径规划方法AIT*(adaptively informed trees)结合	解决复杂环境下的多智能体避障导航问题
基于MADDPG的模型^[66]	采用集中训练与分散执行框架，设计状态/动作空间，结合稀疏与形式化奖励	针对复杂多机避障与路径优化，实现多机协同决策
基于MADDPG的模型^[67]	机器人自主选择目标位置，通过全局策略共享提升协作	无需预设机器人与目标点对应关系，提升协作效率
基于MADDPG的模型^[68]	将动态分配与MAPF建模为MARL框架，通过共享策略网络实现协作	实现跨智能体的协作决策
MADDPG+PER^[69]	MADDPG中引入优先经验回放机制(prioritized experience replay, PER)，根据TD-error(temporal difference error)调整学习优先级	加速策略收敛，提升路径稳定性
CPER-MADDPG^[70]	MADDPG结合组合优先级经验回放(combined prioritized experience replay, CPER)，设计双优先级回放机制；融合TD-error、即时奖励计算经验重要性	显著提升关键样本利用率，在大规模复杂环境下表现更优
NP-MAPPO(network pruning-based multi-agent PPO)^[71]	扩展PPO至多智能体场景，引入网络剪枝技术优化策略网络结构	较传统MAPPO显著提高训练效率，多目标场景下路径规划成功率优于MADDPG等
APF融入DRL^[72]	通过APF构建势场，将其转化为DRL的动态奖励信号	在部分可观测环境中同步完成路径规划与任务决策

算法	核心理论	特点
GNN^[73-74]	结合CNN和GNN；实现信息的局部共享	解决受限观测和通信下的协同导航，促进智能体间协作
GNN^[73-74]	结合CNN、GraphSAGE和MLP	实现局部通信与观测下的协作，增强全局认知
MAG-DQN^[75]	将GCN与DRL结合，利用GCN处理图拓扑信息，结合集中式深度Q学习分配探索目标	利用图拓扑信息进行动态目标分配
SAMARL^[76]	通过时空图建模复杂交互，利用注意力机制捕捉时空依赖生成策略，采用CTDE范式	多智能体协同社会感知导航，保持安全距离
IntNet^[77]	引入意图共享和自适应通信调度，预测模块生成未来状态/意图。结合GAT处理邻居消息，通信调度器优化传输	减少冗余通信
MAGAT^[78]	引入键-查询注意力机制评估邻居消息重要性，通过软加权聚合关键信息	解决GNN无法区分消息优先级问题，减少冗余通信和规划冲突
DHC^[79]	利用图卷积和多头注意力机制实现局部通信协调，采用分布式独立Q学习框架，通过课程学习增加复杂度	用于拥挤环境下协同路径规划，协调行动避免碰撞，支持大规模扩展