计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (4): 21-32.doi: 10.11896/jsjkx.241000101

• 智能嵌入式系统 • 上一篇    下一篇

基于动态冲突预测的多智体寻路算法

张萌希, 韩建军, 肖彦   

  1. 华中科技大学计算机科学与技术学院 武汉 430074
  • 收稿日期:2024-10-21 修回日期:2025-02-24 出版日期:2025-04-15 发布日期:2025-04-14
  • 通讯作者: 肖彦(yanx@hust.edu.cn)
  • 作者简介:(m202273677@hust.edu.cn)

Dynamic Conflict-Prediction Based Algorithm for Multi-agent Path Finding

ZHANG Mengxi, HAN Jianjun, XIAO Yan   

  1. College of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China
  • Received:2024-10-21 Revised:2025-02-24 Online:2025-04-15 Published:2025-04-14
  • About author:ZHANG Mengxi,born in 2000,postgra-duate,is a member of CCF(No.V1352G).His main research interests include AI algorithm and multi-agent path finding.
    XIAO Yan,born in 1995,Ph.D.Her main research interests include AI algorithm,privacy preserving,and information security technology.

PDF (PC)

221

摘要： 多智体寻路(MAPF)是为多个智能体寻找无冲突路径的问题,灵活显式估计的基于冲突搜索算法是目前解决MAPF问题最有效的有界次优算法之一,但该算法仍存在调用底层算法次数多、迭代中冲突数量减少速度慢等问题。为此,提出基于动态冲突预测的多智体寻路算法(DCPB-MAPF)。该算法分为两层,在底层提出基于关键区间的动态避障方法与基于路径成本预测的迭代方法,用以提升底层算法的运算效率;以此为基础,在顶层提出基于冲突预测的搜索算法,通过快速预测冲突数量以优化冲突选择技术,进一步提出冲突数量优先的启发式函数以加速减少冲突数量。实验结果表明,相比现有算法,所提算法能显著提升多智体寻路问题的运算效率及成功率。

关键词: 多智体路径寻找, 有界次优算法, 启发式搜索, 路径成本预测, 冲突预测

Abstract: Multi-agent path finding(MAPF) is the problem of searching for collision-free paths for a group of agents.Currently,flexible explicit estimation conflict-based search algorithm(FEECBS) is deemed as one of the most effective bounded suboptimal algorithms to solve the MAPF problem,but it has several disadvantages concerning the frequent invocation of the low-level algorithm and slow reduction in the number of conflicts during iterations.To address such issues,This paper proposes a dynamic conflict-prediction based algorithm for multi-agent path finding(DCPB-MAPF).The DCPB-MAPF algorithm operates on a two-layer framework.On the low level,it investigates an optimized dynamic obstacle avoidance method based on critical intervals and a new iterative method based on path cost prediction for improving its efficiency.On the high level,it develops a conflict-prediction based search method together with the low-level algorithm.Firstly,the conflict selection technique is improved by quickly predicting the number of potential collisions.Further,a new method is proposed to accelerate reducing the number of conflicts by constructing a heuristic function.The extensively empirical experiment results demonstrate that DCPB-MAPF can effectively improve both efficiency and success rate on MAPF instances when compared to the existing algorithms.

Key words: Multi-agent path finding, Bounded suboptimal algorithms, Heuristic search, Path cost prediction, Conflict prediction

中图分类号: 

  • TP301
[1]BAO X Y.Application practice of general cooperative vehicle infrastructure in the field of transportation[J].Information and Communications Technology and Policy,2024,50(3):53-59.
[3]LI J,LIN E,VU H L,et al.Intersection coordination with priori-ty-based search for autonomous vehicles[C]//Proceedings of the AAAI Conference on Artificial Intelligence.Menlo Park,CA:AAAI,2023:11578-11585.
[4]LI J,CHEN Z,ZHENG Y,et al.Scalable rail planning and replanning:Winning the 2020 flatland challenge[C]//Proceedings of the International Conference on Automated Planning and Scheduling.Menlo Park,CA:AAAI,2021:477-485.
[5]HU D,GAN V J L,WANG T,et al.Multi-agent robotic system(MARS) for UAV-UGV path planning and automatic sensory data collection in cluttered environments[J].Building and Environment,2022,221:109349.
[6]LIU Z F,CAO L,LAI J,et al.Overview of multi-agent path finding[J].Computer Engineering and Applications,2022,58(20):43-62.
[7]FERGUSON D,LIKHACHEV M,STENTZ A.A guide to heuristic-based path planning[C]//Proceedings of the International Workshop on Planning under Uncertainty for Autonomous Systems,International Conference on Automated Planning and Scheduling.Menlo Park,CA:AAAI,2005:9-18.
[8]SHARONG,STERN R,FELNER A,et al.Conflict-based search for optimal multi-agent pathfinding[J].Artificial Intelligence,2015,219:40-66.
[9]WALKER T T,STURTEVANT N R,FELNER A,et al.Conflict-based increasing cost search[C]//Proceedings of the International Conference on Automated Planning and Scheduling.Menlo Park,CA:AAAI,2021:385-395.
[10]BARTAK R,ZHOU N F,STERN R,et al.Modeling and solving the multi-agent pathfinding problem in picat[C]//2017 IEEE 29th International Conference on Tools with Artificial Intelligence.Piscataway,NJ:IEEE,2017:959-966.
[11]BOYARSKIE,FELNER A,SHARON G,et al.Don’t split,try to work it out:Bypassing conflicts in multi-agent pathfinding[C]//Proceedings of the International Conference on Automated Planning and Scheduling.Menlo Park,CA:AAAI,2015:47-51.
[12]BOYARSKIE,FELNER A,STERN R,et al.Icbs:The improved conflict-based search algorithm for multi-agent pathfinding[C]//Proceedings of the International Symposium on Combinatorial Search.New York:ACM,2015:223-225.
[13]BOYARSKIE,HARABOR D,STUCKEY P,et al.F-cardinalconflicts in conflict-based search[C]//Proceedings of the International Symposium on Combinatorial Search.New York:ACM,2020:123-124.
[14]BOYARSKIE,FELNER A,HARABOR D,et al.Iterative-deepening conflict-based search[C]//Proceedings of the Twenty-Ninth International Conference on International Joint Confe-rences on Artificial Intelligence.San Francisco,CA:Morgan Kaufmann,2021:4084-4090.
[15]FELNERA,LI J,BOYARSKI E,et al.Adding heuristics to conflict-based search for multi-agent path finding[C]//Proceedings of the International Conference on Automated Planning and Scheduling.Menlo Park,CA:AAAI,2018:83-87.
[16]GANGEG,HARABOR D,STUCKEY P J.Lazy CBS:implicit conflict-based search using lazy clause generation[C]//Proceedings of the International Conference on Automated Planning and Scheduling.Menlo Park,CA:AAAI,2019:155-162.
[17]LI J,FELNER A,BOYARSKI E,et al.Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search[C]//Proceedings of the International Conference on International Joint Conferences on Artificial Intelligence.San Francisco,CA:Morgan Kaufmann,2019:442-449.
[18]LI J,HARABOR D,STUCKEY P J,et al.Disjoint splitting for multi-agent path finding with conflict-based search[C]//Proceedings of the International Conference on Automated Planning and Scheduling.Menlo Park,CA:AAAI,2019:279-283.
[19]LI J,HARABOR D,STUCKEY P J,et al.Symmetry-breaking constraints for grid-based multi-agent path finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence.Menlo Park,CA:AAAI,2019:6087-6095.
[20]LI J,GANGE G,HARABOR D,et al.New techniques for pairwise symmetry breaking in multi-agent path finding[C]//Proceedings of the International Conference on Automated Planning and Scheduling.Menlo Park,CA:AAAI,2020:193-201.
[21]YU J,LAVALLE S.Structure and intractability of optimalmulti-robot path planning on graphs[C]//Proceedings of the AAAI Conference on Artificial Intelligence.Menlo Park,CA:AAAI,2013:1443-1449.
[23]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.New York:ACM,2014:19-27.
[23]PEARL J,KIM J H.Studies in semi-admissible heuristics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1982(4):392-399.
[24]LI J,RUML W,KOENIG S.EECBS:A bounded-suboptimalsearch for multi-agent path finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence.Menlo Park,CA:AAAI,2021:12353-12362.
[25]THAYER J T,RUML W.Bounded suboptimal search:A direct approach using inadmissible estimates[C]//Proceedings of the International Conference on International Joint Conferences on Artificial Intelligence.San Francisco,CA:Morgan Kaufmann,2011:674-679.
[26]CHAN S H,LI J,GANGE G,et al.Flex Distribution for Bounded Suboptimal Multi-Agent Path Finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence.Menlo Park,CA:AAAI,2022:9313-9322.
[27]CHAN S H,STERN R,FELNER A,et al.Greedy priority-based search for suboptimal multi-agent path finding[C]//Proceedings of the International Symposium on Combinatorial Search.New York:ACM,2023:11-19.
[28]LI J,CHEN Z,HARABOR D,et al.MAPF-LNS2:Fast repairing for multi-agent path finding via large neighborhood search[C]//Proceedings of the AAAI Conference on Artificial Intelligence.Menlo Park,CA:AAAI,2022:10256-10265.
[29]KOENIG S,LIKHACHEV M.D* lite[C]//Eighteenth NationalConference on Artificial Intelligence.Menlo Park,CA:AAAI,2002:476-483.
[30]JIN J Z,ZHANG Y,ZHOU Z P,et al.Conflict-based search with D* lite algorithm for robot path planning in unknown dynamic environments[J].Computers and Electrical Engineering,2023,105:108473.
[31]LIKHACHEV M,GORDON G J,THRUN S.ARA*:Anytime A* with provable bounds on sub-optimality[C]//Advances in Neural Information Processing Systems.San Francisco,CA:Morgan Kaufmann,2003.
[32]STERN R,STURTEVANT N,FELNER A,et al.Multi- agent pathfinding:Definitions,variants,and benchmarks[C]//Proceedings of the International Symposium on Combinatorial Search.New York:ACM,2019:151-158.
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
本系统由北京玛格泰克科技发展有限公司设计开发