计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (6): 358-368.doi: 10.11896/jsjkx.220800151

• 交叉&前沿 • 上一篇    

基于冲突搜索的多智能体路径规划研究进展

王子晗, 童向荣   

  1. 烟台大学计算机与控制工程学院 山东 烟台 264005
  • 收稿日期:2022-08-15 修回日期:2022-12-02 出版日期:2023-06-15 发布日期:2023-06-06
  • 通讯作者: 童向荣(xr_tong@163.com)
  • 作者简介:(zihan_won@163.com)
  • 基金资助:
    国家自然科学基金(62072392, 61972360);山东省重大科技创新工程项目(2019522Y020131);烟台市重点实验室高端海洋工程装备智能技术

Research Progress of Multi-agent Path Finding Based on Conflict-based Search Algorithms

WANG Zihan, TONG Xiangrong   

  1. School of Computer and Control Engineering,Yantai University,Yantai,Shandong 264005,China
  • Received:2022-08-15 Revised:2022-12-02 Online:2023-06-15 Published:2023-06-06
  • About author:WANG Zihan,born in 1998,master,is a member of China Computer Federation.His main research interests include multi-agent path finding and trust path search.TONG Xiangrong,born in 1975,Ph.D,professor,master supervisor,is a member of China Computer Federation.His main research interests include compu-ter science,intelligent information processing and social networks.
  • Supported by:
    National Natural Science Foundation of China(62072392,61972360),Major Innovation Project of Science and Technology of Shandong Province(2019522Y020131) and Yantai Key Laboratory:Intelligent Technology of High-end Marine Engineering Equipment.

PDF (PC)

390

摘要： 多智能体路径规划是人工智能领域一个经典的搜索问题,基于冲突的搜索算法是当前解决该问题的最优算法之一。文中讨论了多智能体路径规划的基础研究,对国内外近年来基于冲突搜索算法及其变体的研究成果进行了分类,根据改进方式将其变体分为4类,包括分割策略的改进、启发式算法、对典型冲突的处理和次优算法。同时介绍了基于冲突的搜索算法在多智能体路径规划的扩展问题中的应用。最后根据当前算法的优缺点,指出了目前面临的挑战,并针对这些挑战给出了未来可能的研究方向。

关键词: 人工智能, 多智能体路径规划, 基于冲突的搜索算法, 启发式搜索算法, A*算法

Abstract: Multi-agent path finding is a classic search problem in the field of artificial intelligence.Conflict-based search algorithm is one of the best algorithms to solve this problem.This paper discusses the basic research of multi-agent path finding,and classifies the research results based on conflict search algorithms and their variants in recent years.According to the improved ways,the variants are divided into four categories,including segmentation strategy improvement,heuristic algorithm,bounded suboptimal algorithm and typical conflict processing.It also introduces the application of the conflict-based search algorithm to the extended problem of multi-agent path finding.Finally,according to the advantages and disadvantages of the current algorithm,the existing challenges are pointed out.In view of these challenges,the possible research directions in the future are given.

Key words: Artificial intelligence, Multi-agent path finding, Conflict-based-search, Heuristic search algorithm, A* algorithm

中图分类号: 

  • TP18
[1]WANG K H C,BOTEA A.Fast and memory-efficient multi-agent pathfinding[C]//Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling.2008:380-387.
[2]MA H,YANG J,COHEN L,et al.Feasibility study:Movingnon-homogeneous teams in congested video game environments[C]//Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment.2017.
[3]VEDDER K,BISWAS J.X*:Anytime multi-agent path finding for sparse domains using window-based iterative repairs[J].Artificial Intelligence,2021,291:103417.
[4]HAN S D,YU J.Ddm:Fast near-optimal multi-robot path planning using diversified-path and optimal sub-problem solution database heuristics[J].IEEE Robotics and Automation Letters,2020,5(2):1350-1357.
[5]BARTÁK R,ŠVANCARA J,ŠKOPKOVÁ V,et al.Multi-agent path finding on real robots[J].AI Communications,2019,32(3):175-189.
[6]DRESNER K,STONE P.A multiagent approach to autonomous intersection management[J].Journal of Artificial Intelligence Research,2008,31:591-656.
[7]BUZACHIS A,CELESTI A,GALLETTA A,et al.A multi-agent autonomous intersection management(MA-AIM) system for smart cities leveraging edge-of-things and Blockchain[J].Information Sciences,2020,522:148-163.
[8]WALKER T T,CHAN D M,STURTEVANT N R.Using hie-rarchical constraints to avoid conflicts in multi-agent pathfinding[C]//Twenty-Seventh International Conference on Automated Planning and Scheduling.2017.
[9]HÖNIG W,PREISS J A,KUMAR T K S,et al.Trajectory plan-ning for quadrotor swarms[J].IEEE Transactions on Robotics,2018,34(4):856-869.
[10]CHE J Y,TONG X R.Dynamic Weighted Anytime BoundedCost Search Algorithm[C]//2021 7th International Conference on Systems and Informatics(ICSAI).IEEE,2021:1-6.
[11]KONG R,TONG X R.Anytime dynamic heuristic search for suboptimal solution on path search[C]//2020 13th International Congress on Image and Signal Processing,BioMedical Enginee-ring and Informatics(CISP-BMEI).IEEE,2020:1070-1074.
[12]KONG R,TONG X R.Dynamic weighted heuristic trust path search algorithm[J].IEEE Access,2020,8:157382-157390.
[13]WEI T,TONG X R.Robust trust path generation based on weighted heuristic search[J].Journal of Nanjing University,2018,54(6):1161-1170.
[14]LIU Y,CHEN M,HUANG H.Multi-agent pathfinding based on improved cooperative A* in Kiva system[C]//2019 5th International conference on control,automation and robotics(ICCAR).IEEE,2019:633-638.
[15]LI J,TINKA A,KIESEL S,et al.Lifelong multi-agent pathfinding in large-scale warehouses[C]//Association for the Advancement of Artificial Intelligence.2020:1898-1900.
[16]SUN S,GU C,WAN Q,et al.CROTPN based collision-free and deadlock-free path planning of AGVs in logistic center[C]//2018 15th International Conference on Control,Automation,Robotics and Vision(ICARCV).IEEE,2018:1685-1691.
[17]ZHANG Z,WU L,ZHANG W,et al.Energy-efficient path planning for a single-load automated guided vehicle in a manufactu-ring workshop[J].Computers & Industrial Engineering,2021,158:107397.
[18]HART P E,NILSSON N J,RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE transactions on Systems Science and Cybernetics,1968,4(2):100-107.
[19]SURYNEK P.Towards optimal cooperative path planning inhard setups through satisfiability solving[C]//Pacific Rim International Conference on Artificial Intelligence.Berlin/Heidelberg:Springer,2012:564-576.
[20]SURYNEK P,FELNER A,STERN R,et al.Efficient SAT approach to multi-agent path finding under the sum of costs objective[C]//Proceedings of the Twenty-second European Confe-rence on Artificial Intelligence.2016:810-818.
[21]SURYNEK P,STERN R,BOYARSKI E,et al.Migrating Techniques from Search-Based Multi-Agent Path Finding Solvers to SAT-Based Approach[J].Journal of Artificial Intelligence Research,2022,73:553-618.
[22]YU J,LAVALLE S M.Planning optimal paths for multiple robots on graphs[C]//2013 IEEE International Conference on Robotics and Automation.IEEE,2013:3612-3617.
[23]YU J,LAVALLE S M.Optimal multirobot path planning on graphs:Complete algorithms and effective heuristics[J].IEEE Transactions on Robotics,2016,32(5):1163-1177.
[24]WANG H,CHEN W.Multi-Robot Path Planning With DueTimes[J].IEEE Robotics and Automation Letters,2022,7(2):4829-4836.
[25]RYAN M.Constraint-based multi-robot path planning[C]//2010 IEEE International Conference on Robotics and Automation.IEEE,2010:922-928.
[26]SHARON G,STERN R,GOLDENBERG M,et al.The increasing cost tree search for optimal multi-agent pathfinding[J].Artificial Intelligence,2013,195:470-495.
[27]SHARON G,STERN R,FELNER A,et al.Conflict-basedsearch for optimal multi-agent pathfinding[J].Artificial Intelligence,2015,219:40-66.
[28]STERN R,STURTEVANT N R,FELNER A,et al.Multi-agent pathfinding:Definitions,variants,and benchmarks[C]//Twelfth Annual Symposium on Combinatorial Search.2019.
[29]LIU Q Z,WU F.Research progress of multi-agent path planning[J].Computer Engineering,2020,46(4):1-10.
[30]CHE J,TONG X,KONG R.Intelligent trust path search[C]//2020 13th International Congress on Image and Signal Proces-sing,BioMedical Engineering and Informatics(CISP-BMEI).IEEE,2020:1075-1080.
[31]STANDLEY T.Finding optimal solutions to cooperative pathfinding problems[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2010.
[32]FELNER A,GOLDENBERG M,SHARON G,et al.Partial-expansion A* with selective node generation[C]//Twenty-Sixth AAAI Conference on Artificial Intelligence.2012.
[33]SILVER D.Cooperative Pathfinding[J].Aiide,2005,1:117-122.
[34]SRINIVASAN A,HAM T,MALIK S,et al.Algorithms for discrete function manipulation[C]//1990 IEEE International Conference on Computer-Aided Design.IEEE Computer Society,1990:92-95.
[35]BOYARSKI E,FELNER A,STERN R,et al.ICBS:Improved conflict-based search algorithm for multi-agent pathfinding[C]//Twenty-Fourth International Joint Conference on Artificial Intelligence.2015.
[36]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.2019:279-283.
[37]SHARON G,STERN R,FELNER A,et al.Meta-agent conflict-based search for optimal multi-agent path finding[C]//International Symposiumon Combinatorial Search.2012.
[38]LEE H,MOTES J,MORALES M,et al.Parallel HierarchicalComposition Conflict-Based Search for Optimal Multi-Agent Pathfinding[J].IEEE Robotics and Automation Letters,2021,6(4):7001-7008.
[39]FELNER A,LI J,BOYARSKI E,ET AL.Adding heuristics to conflict-based search for multi-agent path finding[C]//Procee-dings of the International Conference on Automated Planning and Scheduling.2018.
[40]FELNER A,KORF R E,HANAN S.Additive pattern database heuristics[J].Journal of Artificial Intelligence Research,2004,22:279-318.
[41]LI J,FELNER A,BOYARSKI E,et al.Improved heuristics for multi-agent path finding with conflict-based search[C]//Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence.2019:442-449.
[42]BOYARSKI E,FELNER A,LE BODIC P,et al.f-Aware con-flict prioritization & Improved heuristics for conflict-based search[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2021:12241-12248.
[43]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.2019:6087-6095.
[44]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.2020,30:193-201.
[45]LI J,HARABOR D,STUCKEY P J,et al.Pairwise symmetry reasoning for multi-agent path finding search[J].Artificial Intelligence,2021,301:103574.
[46]BOYARSKI E,FELNER A,LE BODIC P,et al.Further improved heuristics for conflict-based search[C]//Proceedings of the International Symposium on Combinatorial Search.2021:213-215.
[47]YU J,LAVALLE S M.Structure and intractability of optimal multi-robot path planning on graphs[C]//Twenty-Seventh AAAI Conference on Artificial Intelligence.2013.
[48]MA H,TOVEY C,SHARON G,et al.Multi-agent path finding with payload transfers and the package-exchange robot-routing problem[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2016.
[49]POHL I.Heuristic search viewed as path finding in a graph[J].Artificial Intelligence,1970,1(3/4):193-204.
[50]PEARL J,KIM J H.Studies in semi-admissible heuristics[J].IEEE Transactionson Pattern Analysis and Machine Intelligence,1982(4):392-399.
[51]BARER M,SHARON G,STERN R,et al.Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem[C]//Seventh Annual Symposium on Combinatorial Search.2014.
[52]CHAN S H,LI J,GANGE G,et al.ECBS with flex distribution for bounded-suboptimal multi-agent path finding[C]//Procee-dings of the International Symposium on Combinatorial Search.2021:159-161.
[53]RAHMAN M,ALAM M A,ISLAM M M,et al.An Adaptive Agent-Specific Sub-Optimal Bounding Approach for Multi-Agent Path Finding[J].IEEE Access,2022,10:22226-22237.
[54]LI J,RUML W,KOENIG S.EECBS:A bounded-suboptimalsearch for multi-agent path finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence(AAAI).2021.
[55]SEMIZ F,POLAT F.Incremental multi-agent path finding[J].Future Generation Computer Systems,2021,116:220-233.
[56]KOENIG S,LIKHACHEV M.D*lite[C]//Eighteenth National Conference on Artificial Intelligence,American Association for Artificial Intelligence.Menlo Park,USA:CA,2002:476-483.
[57]MA H,LI J,KUMAR T K S,et al.Lifelong multi-agent path finding for online pickup and delivery tasks[C]//Proceedings of the International Conference on Autonomous Agents and Multiagent Systems(AAMAS).2017:837-845.
[58]WAN Q,GU C,SUN S,et al.Lifelong multi-agent path finding in a dynamic environment[C]//2018 15th International Confe-rence on Control,Automation,Robotics and Vision(ICARCV).IEEE,2018:875-882.
[59]WALKER T T,STURTEVANT N R,FELNER A.Extended increasing cost tree search for non-unit cost fomains[C]//Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence.2018:534-540.
[60]ANDREYCHUK A,YAKOVLEV K,ATZMON D,et al.Multi-agent pathfinding with continuous time[C]//IJCAI Interna-tional Joint Conference on Artificial Intelligence.2019:39-45.
[61]PHILLIPS M,LIKHACHEV M.Sipp:Safe interval path planning for dynamic environments[C]//2011 IEEE International Conference on Robotics and Automation.IEEE,2011:5628-5635.
[62]ANDREYCHUK A,YAKOVLEV K,BOYARSKI E,et al.Improving continuous-time conflict based search[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2021:11220-11227.
[63]COHEN L,URAS T,KUMAR T K S,et al.Optimal andbounded-suboptimal multi-agent motion planning[C]//Twelfth Annual Symposium on Combinatorial Search.2019.
[64]AI B,JIANG J,YU S,et al.Multi-agent path finding with hete-rogeneous edges and roundtrips[J].Knowledge-Based Systems,2021,234:107554.
[65]SHAHAR T,SHEKHAR S,ATZMON D,et al.Safe Multi-Agent Pathfinding with Time Uncertainty[J].Journal of Artificial Intelligence Research,2021,70:923-954.
[66]SOLIS I,MOTES J,SANDSTRÖM R,et al.Representation-optimal multi-robot motion planning using conflict-based search[J].IEEE Robotics and Automation Letters,2021,6(3):4608-4615.
[67]MA H,WAGNER G,FELNER A,et al.Multi-agent path fin-ding with deadlines[C]//Proceedings of the 27th International Joint Conference on Artificial Intelligence.2018:417-423.
[68]ATZMON D,STERN R,FELNER A,et al.Robust multi-agent path finding[C]//Eleventh Annual Symposium on Combinato-rial Search.2018.
[69]ATZMON D,STERN R,FELNER A,et al.Robust multi-agent path finding and executing[J].Journal of Artificial Intelligence Research,2020,67:549-579.
[70]CHEN Z,HARABOR D,LI J,et al.Symmetry breaking for k-robust multi-agent path finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2021:12267-12274.
[71]WEN L,LIU Y,LI H.CL-MAPF:Multi-Agent Path Finding for Car-Like robots with kinematic and spatiotemporal constraints[J].Robotics and Autonomous Systems,2022,150:103997.
[72]YU L,WANG Z.Multi-Robot Robust Motion Planning based on Model Predictive Priority Contouring Control with Double-Layer Corridors[J].Applied Sciences,2022,12(3):1682.
[73]LIU Z,WANG H,WEI H,et al.Prediction,planning,and coordination of thousand-warehousing-robot networks with motion and communication uncertainties[J].IEEE Transactions on Automation Science and Engineering,2020,18(4):1705-1717.
[74]VARGA L Z.Solutions to the routing problem:towards trustworthy autonomous vehicles[J].Artificial Intelligence Review,2022,55:5445-5484.
[75]HO F,GERALDES R,GONÇALVES A,et al.Decentralizedmulti-agent path finding for UAV traffic management[J].IEEE Transactions on Intelligent Transportation Systems,2022,23:997-1008.
[76]PIANPAK P,SON T C,TOUPS Z O,et al.A distributed solver for multi-agent path finding problems[C]//Proceedings of the First International Conference on Distributed Artificial Intelligence.2019:1-7.
[77]FINES K,SHARPANSKYKH A,VERT M.Agent-based dis-tributed planning and coordination for resilient airport surface movement operations[J].Aerospace,2020,7(4):48.
[78]HUANG T,KOENIG S,DILKINA B.Learning to resolve conflicts for multi-agent path finding with conflict-based search[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2021:11246-11253.
[79]SURYNEK P,STERN R,BOYARSKI E,et al.Migrating Techniques from Search-based Multi-Agent Path Finding Solvers to SAT-based Approach[J].Journal of Artificial Intelligence Research,2022,73:553-618.
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
本系统由北京玛格泰克科技发展有限公司设计开发