Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (6): 358-368.doi: 10.11896/jsjkx.220800151

• Interdiscipline & Frontier • Previous Articles    

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)

382

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

CLC Number: 

  • 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.
[1] WANG Dongli, YANG Shan, OUYANG Wanli, LI Baopu, ZHOU Yan. Explainability of Artificial Intelligence:Development and Application [J]. Computer Science, 2023, 50(6A): 220600212-7.
[2] XING Ying. Review of Software Engineering Techniques and Methods Based on Explainable Artificial Intelligence [J]. Computer Science, 2023, 50(5): 3-11.
[3] ZHANG Qiyang, CHEN Xiliang, CAO Lei, LAI Jun, SHENG Lei. Survey on Knowledge Transfer Method in Deep Reinforcement Learning [J]. Computer Science, 2023, 50(5): 201-216.
[4] ZHANG Qiyang, CHEN Xiliang, ZHANG Qiao. Sparse Reward Exploration Method Based on Trajectory Perception [J]. Computer Science, 2023, 50(1): 262-269.
[5] LI Ye, CHEN Song-can. Physics-informed Neural Networks:Recent Advances and Prospects [J]. Computer Science, 2022, 49(4): 254-262.
[6] LI Sun, CAO Feng, LIU Zi-shan. Study on Quality Evaluation Method of Speech Datasets for Algorithm Model [J]. Computer Science, 2022, 49(11A): 210800246-6.
[7] ZHAO Hong, CHANG You-kang, WANG Wei-jie. Survey of Adversarial Attacks and Defense Methods for Deep Neural Networks [J]. Computer Science, 2022, 49(11A): 210900163-11.
[8] WANG Lu, WEN Wu-song. Study on Distributed Intrusion Detection System Based on Artificial Intelligence [J]. Computer Science, 2022, 49(10): 353-357.
[9] CHAO Le-men, YIN Xian-long. AI Governance and System:Current Situation and Trend [J]. Computer Science, 2021, 48(9): 1-8.
[10] BAO Yu-xuan, LU Tian-liang, DU Yan-hui, SHI Da. Deepfake Videos Detection Method Based on i_ResNet34 Model and Data Augmentation [J]. Computer Science, 2021, 48(7): 77-85.
[11] JING Hui-yun, WEI Wei, ZHOU Chuan, HE Xin. Artificial Intelligence Security Framework [J]. Computer Science, 2021, 48(7): 1-8.
[12] XIE Chen-qi, ZHANG Bao-wen, YI Ping. Survey on Artificial Intelligence Model Watermarking [J]. Computer Science, 2021, 48(7): 9-16.
[13] JING Hui-yun, ZHOU Chuan, HE Xin. Security Evaluation Method for Risk of Adversarial Attack on Face Detection [J]. Computer Science, 2021, 48(7): 17-24.
[14] QIN Zhi-hui, LI Ning, LIU Xiao-tong, LIU Xiu-lei, TONG Qiang, LIU Xu-hong. Overview of Research on Model-free Reinforcement Learning [J]. Computer Science, 2021, 48(3): 180-187.
[15] CAO Bo, CHEN Feng, CHENG Jing, LI Hua, LI Yong-le. Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search [J]. Computer Science, 2021, 48(11A): 77-80.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.