计算机科学

计算机科学 ›› 2026, Vol. 53 ›› Issue (10): 312-319.doi: 10.11896/jsjkx.250800030

• 人工智能 • 上一篇    下一篇

基于拥塞避免和振荡解除的多智能体路径规划

张永良1, 赵国友1, 王小妃1, 李子文1, 王保红2   

  1. 1 浙江工业大学计算机科学与技术学院 杭州 310014
    2 浙江大学医学院附属第一医院传染病诊治国家重点实验室、国家传染病临床研究中心、传染病诊治协同创新中心 杭州 310003
  • 收稿日期:2025-08-07 修回日期:2025-11-23 发布日期:2026-10-13
  • 通讯作者: 张永良(titanzhang@zjut.edu.cn)
  • 基金资助:
    国家重点研发计划(2021YFA1301001)

Congestion-avoidance and Oscillation-resolution Enabled Multi-agent Pathfinding

ZHANG Yongliang1, ZHAO Guoyou1, WANG Xiaofei1, LI Ziwen1, WANG Baohong2   

  1. 1 College of Computer Science & Technology,Zhejiang University of Technology,Hangzhou 310014, China
    2 State Key Laboratory for Diagnosis and Treatment of Infectious Diseases,National Clinical Research Center for Infectious Diseases,Collaborative Innovation Center for Diagnosis and Treatment of Infectious Diseases,The First Affiliated Hospital,Zhejiang University School of Medicine,Hangzhou 310003, China
  • Received:2025-08-07 Revised:2025-11-23 Online:2026-10-13
  • About author:ZHANG Yongliang,born in 1977,Ph.D,associate professor.His main research interests include biometric features re-cognition,artificial intelligence and multirobot system.
  • Supported by:
    National Key R&D Program of China(2021YFA1301001).

PDF (PC)

58

摘要： 基于深度强化学习的多智能体路径规划算法因其对环境的良好适应性而受到广泛关注。随着相关领域应用需求的增长,地图规模日趋复杂,智能体数量持续增加,导致智能体间的交互难度显著提升。现有方法主要通过通信机制增强智能体间的信息交互,但在高密度场景下,仍难以避免智能体陷入区域拥塞或产生往返振荡的运动,进而影响整体路径规划效率。针对上述问题,提出一种基于拥塞避免和振荡解除的多智能体路径规划方法(CAOR),该方法综合考虑智能体周围物体密度与相邻智能体的活跃度,据此重构奖励函数以引导智能体规避拥塞区域;同时针对振荡问题,通过检测各智能体的往返动作识别振荡状态,为出现振荡的智能体打上振荡标签,并对带有该标签的智能体采用搜索算法重新规划路线。实验结果显示,在结构化地图中,当智能体数量不超过64个时,CAOR的求解成功率均为100%;在大规模场景下,相较于现有基于学习的方法,CAOR也展现出更优的求解性能。

关键词: 深度强化学习, 路径规划, 拥塞避免, 选择通信, 振荡解除

Abstract: Multi-agent path finding(MAPF) algorithms based on deep reinforcement learning(DRL) have received extensive attention due to their good adaptability to the environment.With the growth of application demands in related fields,map structures have become increasingly intricate,and the number of agents has continued to increase,leading to a significant rise in the difficulty of interactions among agents.Existing methods mainly enhance information exchange among agents through communication mechanisms,but in high-density scenarios,it is still difficult to avoid agents getting stuck in regional congestion or generating reciprocating oscillations,which in turn affects the efficiency of overall path planning.To address the above issues,a multi-agent pathfinding method named CAOR(Congestion-Avoidance and Oscillation-Resolution Enabled Multi-Agent Pathfinding) is proposed.This method comprehensively considers the density of objects around the agents and the activity of adjacent agents,and accordingly redesigns the reward function to guide the agents to avoid congested areas.Meanwhile,for the oscillation problem,CAOR identifies oscillation states by detecting the reciprocating movements of each agent,attaches oscillation labels to the agents that exhibit oscillations,and applies a search algorithm to these labeled agents to replan their routes.Experimental results show that in structured maps,when the number of agents does not exceed 64,the success rate of CAOR reaches 100%.In large-scale scenarios,compared with existing learning-based methods,CAOR also shows better solution performance.

Key words: Deep reinforcement learning, Path planning, Congestion-avoidance, Selective communication, Oscillation-resolution

中图分类号: 

  • TP391
[1] STERN R,STURTEVANT N,FELNER A,et al.Multi-agent pathfinding:Definitions,variants,and benchmarks[C]//Proceedings of the International Symposium on Combinatorial Search.2019:151-158.
[2] AHN K,PARK H,PARK J.Learning to Schedule in Multi-Agent Pathfinding[C]//2023 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS).IEEE,2023:7326-7332.
[3] LIKHOUZOVA T,DEMIANOVA Y.Robot path optimization in warehouse management system[J].Evolutionary Intelligence,2022,15(4):2589-2595.
[4] FAISAL A,KAMRUZZAMAN M,YIGITCANLAR T,et al.Understanding autonomous vehicles[J].Journal of Transport and Land Use,2019,12(1):45-72.
[5] LIU Q Y,YOU X,ZHANG X,et al.Review of Path Planning Algorithms for Mobile Robots[J].Computer Science,2025,52(S1):159-168.
[6] SIEMIATKOWSKA B,STECZ W.A framework for planningand execution of drone swarm missions in a hostile environment[J].Sensors,2021,21(12):4150.
[7] GUO T,CHEN X,WANG Y,et al.Large language model based multi-agents:A survey of progress and challenges[J].arXiv:2402.01680,2024.
[8] SHARON G,STERN R,FELNER A,et al.Conflict-basedsearch for optimal multi-agent pathfinding[J].Artificial Intelligence,2015,219:40-66.
[9] BARER M,SHARON G,STERN R,et al.Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem[C]//Proceedings of the International Sympo-sium on Combinatorial Search.2014:19-27.
[10] LI J,RUML W,KOENIG S.Eecbs:A bounded-suboptimalsearch for multi-agent path finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2021:12353-12362.
[11] BANFI J,BASILICO N,AMIGONI F.Intractability of time-optimal multirobot path planning on 2D grid graphs with holes[J].IEEE Robotics and Automation Letters,2017,2(4):1941-1947.
[12] SHI D X,PENG Y X,YANG H H,et al.DQN-based Multi-agent Motion Planning Method with Deep Reinforcement Lear-ning[J].Computer Science,2024,51(2):268-277.
[13] SARTORETTI G,KERR J,SHI Y,et al.Primal:Pathfindingvia reinforcement and imitation multi-agent learning[J].IEEE Robotics and Automation Letters,2019,4(3):2378-2385.
[14] HUSSEIN A,GABER M M,ELYAN E,et al.Imitation lear-ning:A survey of learning methods[J].ACM Computing Surveys,2017,50(2):1-35.
[15] FERNER C,WAGNER G,CHOSET H.ODrM* optimal multirobot path planning in low dimensional search spaces[C]//2013 IEEE International Conference on Robotics and Automation.IEEE,2013:3854-3859.
[16] MA Z,LUO Y,MA H.Distributed heuristic multi-agent path finding with communication [C]//2021 IEEE International Conference on Robotics and Automation(ICRA).IEEE,2021:8699-8705.
[17] MA Z,LUO Y,PAN J.Learning selective communication formulti-agent path finding[J].IEEE Robotics and Automation Letters,2021,7(2):1455-1462.
[18] SONG Z,ZHANG R,CHENG X.HELSA:Hierarchical Reinforcement Learningwith Spatiotemporal Abstraction for Large-Scale Multi-Agent Path Finding[C]//2023 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS).IEEE,2023:7318-7325.
[19] WANG Y,XIANG B,HUANG S,et al.SCRIMP:Scalable communication for reinforcement and imitation-learning-based multi-agent pathfinding[C]//2023 IEEE/RSJ International Confe-rence on Intelligent Robots and Systems(IROS).IEEE,2023:9301-9308.
[20] ZHANG Y L,LI Z W,XU J H,et al.Congestion-aware andCached Communication for Multi-agent Pathfinding[J].Computer Science,2025,52(8):317-325.
[21] CHUNG J,GULCEHRE C,CHO K H,et al.Empirical evaluation of gated recurrent neural networks on sequence modeling[J].arXiv:1412.3555,2014.
[22] VASWANI A,SHAZEER N,PARMAR N,et al.Attention isall you need[C]//Proceedings of the 31st International Confe-rence on in Neural Information Processing Systems.2017:6000-6010.
[23] TESAURO G.Temporal difference learning and TD-Gammon[J].Communications of the ACM,1995,38(3):58-68.
[24] HODSON T O.Root mean square error(RMSE) or mean absolute error(MAE):When to use them or not[J].Geoscientific Model Development Discussions,2022,2022:1-10.
[25] TAN M.Multi-agent reinforcement learning:Independent vs.cooperative agents[C]//Proceedings of the Tenth International Conference on Machine Learning.ACM,1993:330-337.
[26] VAN HASSELT H,GUEZ A,SILVER D.Deep reinforcement learning with double q-learning[C]//Proceedings of the AAAI Conference on Artificial Intelligence.AAAI,2016:2094-2100.
[27] WANG Z,SCHAUL T,HESSEL M,et al.Dueling network architectures for deep reinforcement learning[C]//International Conference on Machine Learning.ACM,2016:1995-2003.
[28] JU C,LUO Q,YAN X.Path planning using an improved a-star algorithm[C]//2020 11th International Conference on Prognostics and System Health Management(PHM-2020 Jinan).IEEE,2020:23-26.
[29] HORGAN D,QUAN J,BUDDEN D,et al.Distributed prioritized experience replay[J].arXiv:1803.00933.2018.
[30] BENGIO Y,LOURADOUR J,COLLOBERT R,et al.Curriculum learning[C]//Proceedings of the 26th Annual International Conference on Machine Learning.ACM,2009:41-48.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市两江新区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发