多智能体路径规划研究进展

doi:10.19678/j.issn.1000-3428.0056738

摘要/Abstract

摘要： 多智能体路径规划是一类寻找多个智能体从起始位置到目标位置且无冲突的最优路径集合的问题，针对该问题的研究在物流、军事和安防等领域有着大量的应用场景。对国内外关于多智能体路径规划问题的研究进展进行系统整理和分类，按照结果最优性的不同，多智能体路径规划算法被分为最优算法和近似算法2类。最优的多智能体路径规划算法主要分为基于A*搜索、基于代价增长树、基于冲突搜索和基于规约的4种算法。近似的多智能体路径规划算法主要分为无边界次优的算法和有边界次优的算法2类。基于上述分类，分析各种算法的特点，介绍近年来具有代表性的研究成果，并对多智能体路径规划问题未来的研究方向进行展望。

关键词: 多智能体路径规划, 人工智能, 搜索, 最优路径集合, 多机器人

Abstract: Multi-Agent Path Planning(MAPP) is the problem of finding an optimal path set for multiple agents from their starting position to the target position without any collisions.Research on this problem has abundant application scenarios in the fields of logistics,military and security.This paper systematically sorts out and classifies the recent research progress in MAPP both at home and abroad.According to the differences in the optimality of results,the MAPP algorithms are classified into optimal group and approximate group.The optimal MAPP algorithms are mainly divided into four categories,which are based on A* search,cost growth tree,conflict based search and protocol respectively.The approximate MAPP algorithms are mainly divided into two categories:the unbounded suboptimal algorithm and the bounded suboptimal algorithm.Based on the classification mentioned above,this paper analyzes the characteristics of each algorithm,introduces the representative researches in recent years and discusses the future research directions of MAPP problem.

Key words: Multi-Agent Path Planning(MAPP), artificial intelligence, search, optimal path set, multi-robot

中图分类号:

TP391

刘庆周, 吴锋. 多智能体路径规划研究进展[J]. 计算机工程, 2020, 46(4): 1-10.

LIU Qingzhou, WU Feng. Research Progress of Multi-Agent Path Planning[J]. Computer Engineering, 2020, 46(4): 1-10.

图/表 6

参考文献 64

[1]	TANG Yong,HE Donglin,ZHU Xinping.Aircraft taxiing path planning based on multi-agent system[J].Journal of Jiangsu University(Natural Science Edition),2019(5):559-565.(in Chinese)唐勇,何东林,朱新平.基于多智能体系统的飞机滑行路径规划[J].江苏大学学报(自然科学版),2019(5):559-565.
[2]	WURMAN P R,D'ANDREA R,MOUNTZ M.Coordinating hundreds of cooperative,autonomous vehicles in warehouses[C]//Proceedings of the 22nd AAAI Conference on Artificial Intelligence.[S.l.]:AAAI Press,2007:56-78.
[3]	DRESNER K M,STONE P.A multiagent approach to autonomous intersection management[J].Journal of Artificial Intelligence Research,2008,31(3):591-656.
[4]	VELOSO M,BISWAS J,COLTIN B,et al.CoBots:robust symbiotic autonomous mobile service robots[C]//Proceedings of International Conference on Artificial Intelligence.[S.l.]:AAAI Press,2015:566-574.
[5]	HUANG Jin,HUANG Zongwen,LING Ziyan.Application of multi-agent road finding system in computer games[J].Computer Knowledge and Technology,2012,8(13):3159-3164.(in Chinese)黄进,黄宗文,凌子燕.多智能体寻路系统在计算机游戏上的应用[J].电脑知识与技术,2012,8(13):3159-3164.
[6]	FU Mengjia,YOU Xiaoming.A survey of multi robot system and its path planning methods[J].Software Guide,2017,16(1):177-179.(in Chinese)付梦家,游晓明.多机器人系统及其路径规划方法综述[J].软件导刊,2017,16(1):177-179.
[7]	SURYNEK P.An optimization variant of multi-robot path planning is intractable[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence.[S.l.]:AAAI Press,2010:67-89.
[8]	RYAN M R K.Exploiting subgraph structure in multi-robot path planning[J].Journal of Artificial Intelligence Research,2008,31:497-542.
[9]	STANDLEY T.Finding optimal solutions to cooperative pathfinding problems[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence.[S.l.]:AAAI Press,2010:173-178.
[10]	GOLDENBERG M,FELNER A,STURTEVANT N R,et al.Optimal-generation variants of EPEA[EB/OL].[2019-11-02].https://webdocs.cs.ualberta.ca/~holte/Publications/SoCS2013-EPEA.pdf.
[11]	GOLDENBERG M,FELNER A,STERN R,et al.Enhanced partial expansion A*[J].Journal of Artificial Intelligence Research,2014,50(1):141-187.
[12]	WAGNER G,CHOSET H.Subdimensional expansion for multirobot path planning[EB/OL].[2019-11-02].https://www.ri.cmu.edu/pub_files/2015/2/subdim_journal.pdf.
[13]	FERNER C,WAGNER G,CHOSET H.ODrM* optimal multirobot path planning in low dimensional search spaces[C]//Proceedings of 2013 IEEE International Conference on Robotics and Automation.Washington D.C.,USA:IEEE Press,2013:56-89.
[14]	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.
[15]	SRINIVASAN A,HAM T,MALIK S,et al.Algorithms for discrete function manipulation[C]//Proceedings of IEEE International Conference on Computer-aided Design.Washington D.C.,USA:IEEE Press,1990:78-90.
[16]	SHARON G,STERN R,FELNER A,et al.Conflict-based search for optimal multi-agent pathfinding[J].Artificial Intelligence,2015,219:40-66.
[17]	BOYARSKI E,FELNER A,STERN R,et al.ICBS:improved conflict-based search algorithm for multi-agent pathfinding[C]//Proceedings of International Conference on Artificial Intelligence.[S.l.]:AAAI Press,2015:67-90.
[18]	BOYARSKI E,FELNER A,SHARON G,et al.Don't split,try to work it out:bypassing conflicts in multi-agent pathfinding[C]//Proceedings of International Conference on Automated Planning and Scheduling.Washington D.C.,USA:IEEE Press,2010:47-51.
[19]	FELNER A.Adding heuristics to conflict-based search for multi-agent path finding[EB/OL].[2019-11-02].http://idm-lab.org/bib/abstracts/papers/icaps18a.pdf.
[20]	LI J,HARABOR D,STUCKEY P,et al.Disjoint splitting for multi-agent path finding with conflict-based search[C]//Proceedings of International Conference on Automated Planning and Scheduling.Washington D.C.,USA:IEEE Press,2019:279-283.
[21]	RYAN M.Constraint-based multi-robot path planning[C]//Proceedings of International Conference on Robotics and Automation.Washington D.C.,USA:IEEE Press,2010:38-54.
[22]	SURYNEK P.Towards optimal cooperative path planning in hard setups through satisfiability solving[C]//Proceedings of the Pacific Rim International Conferences on Artificial Intelligence.Washington D.C.,USA:IEEE Press,2012:564-576.
[23]	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 ECAI-European Conference on Artificial Intelligence.Berlin,Germany:Springer,2016:810-818.
[24]	SURYNEK P,JIRI S,FELNER A,et al.Integration of independence detection into SAT-based optimal multi-agent path finding-a novel sat-based optimal MAPF solver[C]//Proceedings of the 9th International Conference on Agents and Artificial Intelligence.Berlin,Germany:Springer,2017:116-136.
[25]	BARTÁK R,ŠVANCARA J.On SAT-based approaches for multi-agent path finding with the sum-of-costs objective[EB/OL].[2019-11-02].http://svancara.net/files/socs_soc.pdf.
[26]	ERDEM E,KISA D G,OZTOK U,et al.A general formal framework for pathfinding problems with multiple agents[C]//Proceedings of AAAI Conference on Artificial Intelligence.[S.l.]:AAAI Press,2013:290-296.
[27]	YU J,LAVALLE S M.Planning optimal paths for multiple robots on graphs[EB/OL].[2019-11-02].https://arc.cs.rutgers.edu/files/YuLav13ICRA.pdf.
[28]	YU J,LAVALLE S M.Optimal multirobot path planning on graphs:complete algorithms and effective heuristics[J].IEEE Transactions on Robotics,2016,32(5):1-15.
[29]	SHU Xiangxiang.Research on optimal path planning of multi robots[J].China Computer and Communication,2017(15):62-64.(in Chinese)舒翔翔.多机器人最优路径规划研究[J].信息与电脑,2017(15):62-64.
[30]	SPIRALRIS D K G M P.Coordinating pebble motion on graphs,the diameter of permutation groups,and applications[EB/OL].[2019-11-02].https://www.computer.org/csdl/proceedings-article/focs/1984/0715921/12OmNC3FGi5.
[31]	SILVER D.Cooperative pathfinding[C]//Proceedings of the 1st Artificial Intelligence and Interactive Digital Entertainment Conference.[S.l.]:AAAI Press,2005:78-90.
[32]	STANDLEY T S,KORF R E.Complete algorithms for cooperative pathfinding problems[C]//Proceedings of the 22nd International Joint Conference on Artificial Intelligence.[S.l.]:AAAI Press,2011:668-673.
[33]	STURTEVANT N R,BURO M.Improving collaborative pathfinding using map abstraction[EB/OL].[2019-11-02].https://www.aaai.org/Papers/AIIDE/2006/AIIDE06-017.pdf.
[34]	ZHAO Yongsheng,SUN Wenlei.Multi robot path planning with dynamic path modification[J].Mechanical Science and Technology for Aerospace,2018,37(10):13-18.(in Chinese)晁永生,孙文磊.动态修改路径的多机器人路径规划[J].机械科学与技术,2018,37(10):13-18.
[35]	BNAYA Z,FELNER A.Conflict-oriented windowed hierarchical cooperative A*[C]//Proceedings of IEEE International Conference on Robotics and Automation.Washington D.C.,USA:IEEE Press,2014:56-78.
[36]	CAO Qixin,HUANG Xianqun,ZHU Xiaoxiao,et al.Path planning of distributed multi robot based on reserved area[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2018,46(12):76-81.(in Chinese)曹其新,黄先群,朱笑笑,等.基于保留区域的分布式多机器人路径规划[J].华中科技大学学报(自然科学版),2018,46(12):76-81.
[37]	KORNHAUSER D,MILLER G,SPIRAKIS P.Coordinating pebble motion on graphs,the diameter of permutation groups,and applications[C]//Proceedings of the 25th Annual Symposium on Foundations of Computer Science.Washington D.C.,USA:IEEE Press,2002:998-1024.
[38]	KHORSHID M M,HOLTE R C,STURTEVANT N.A polynomial-time algorithm for non-optimal multi-agent pathfinding[EB/OL].[2019-11-02].http://webdocs.cs.ualberta.ca/~holte/Publications/SoCS11Multiagent.pdf.
[39]	SURYNEK P.A novel approach to path planning for multiple robots in bi-connected graphs[C]//Proceedings of IEEE International Conference on Robotics and Automation.Washington D.C.,USA:IEEE Press,2009:678-690.
[40]	BOTEA A,SURYNEK P.Multi-agent path finding on strongly biconnected digraphs[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence.[S.l.]:AAAI Press,2015:56-80.
[41]	LUNA R,BEKRIS K E.Efficient and complete centralized multi-robot path planning[C]//Proceedings of the 14th Annual Symposium on Combinatorial Search.Washington D.C.,USA:IEEE Press,2011:899-920.
[42]	SAJID Q,LUNA R,BEKRIS K E.Multi-agent path finding with simultaneous execution of single-agent primitives[EB/OL].[2019-11-02].http://www.ryanluna.com/papers/Sajid_SoCS_12.pdf.
[43]	DEWILDE B,MORS A W T,WITTEVEEN C.Push and rotate:a complete multi-agent pathfinding algorithm[J].Journal of Artificial Intelligence Research,2014,51:443-492.
[44]	WANG K H C,BOTEA A.Fast and memory-efficient multi-agent pathfinding[C]//Proceedings of International Conference on Automated Planning and Scheduling.Washington D.C.,USA:IEEE Press,2008:380-387.
[45]	JANSEN M R,STURTEVANT N R.A new approach to cooperative pathfinding[C]//Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems.Washington D.C.,USA:IEEE Press,2008:12-16.
[46]	WANG J,LI J,MA H,et al.A new constraint satisfaction perspective on multi-agent path finding:preliminary results[C]//Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems.Washington D.C.,USA:IEEE Press,2019:2253-2255.
[47]	PIANPAK P,SON T C,TOUPS Z O,et al.A distributed solver for multi-agent path finding problems[C]//Proceedings of the 1st International Conference on Distributed Artificial Intelligence.New York,USA:ACM Press,2019:2-10.
[48]	SURYNEK P,FELNER A,STERN R,et al.Modifying optimal SAT-based approach to multi-agent path-finding problem to suboptimal variants[C]//Proceedings of the 20th Annual Symposium on Combinatorial Search.Washington D.C.,USA:IEEE Press, 2017:25-43.
[49]	WANG Yiran,JING Xiaochuan,TIAN Tao,et al.Multi-Agent path planning based on reinforcement learning[J].Computer Application and Software,2019,36(8):165-171.(in Chinese)王毅然,经小川,田涛,等.基于强化学习的多Agent路径规划方法研究[J].计算机应用与软件,2019,36(8):165-171.
[50]	ZHENG Yanbin,LI Bo,AN Deyu,et al.Multi-Agent path planning method based on hierarchical reinforcement learning and artificial potential field[J].Computer Application,2015,35(12):3491-3496.(in Chinese)郑延斌,李波,安德宇,等.基于分层强化学习及人工势场的多Agent路径规划方法[J].计算机应用,2015,35(12):3491-3496.
[51]	SUN Shudong,LIN Mao.Coordinated path planning of multiple mobile robots based on genetic algorithm[J].Acta Automatica Sinica,2000,26(5):672-676.(in Chinese)孙树栋,林茂.基于遗传算法的多移动机器人协调路径规划[J].自动化学报,2000,26(5):672-676.
[52]	FAN Yuan,LI Wenfeng,HE Lijun.Cooperative scheduling of intelligent storage multi mobile robot based on improved genetic algorithm[J].Journal of Wuhan University of Technology(Information and Management Engineering),2019,41(3):293-298,311.(in Chinese)范媛,李文锋,贺利军.基于改进遗传算法的智能仓储多移动机器人协同调度[J].武汉理工大学学报(信息与管理工程版),2019,41(3):293-298,311.
[53]	LEI Xiaoyu,YANG Shengyue,ZHANG Yaming,et al.Path planning of multi-agent robot based on coevolution[J].Computer Systems and Applications,2010,19(11):157-161.(in Chinese)雷小宇,杨胜跃,张亚鸣,等.基于协同进化的多智能体机器人路径规划[J].计算机系统应用,2010,19(11):157-161.
[54]	WU Liang,HE Qinghua,HUANG Zhixiong,et al.Centralized and coordinated path planning of multi robots based on ant colony algorithm[J].Robot Technology and Application,2006(3):42-47.(in Chinese)吴靓,何清华,黄志雄,等.基于蚁群算法的多机器人集中协调式路径规划[J].机器人技术与应用,2006(3):42-47.
[55]	GU Junhua,MENG Huijie,XIA Hongmei,et al.Research on multi robot path planning based on improved ant colony algorithm[J].Journal of Hebei University of Technology,2016,45(5):28-34.(in Chinese)顾军华,孟慧婕,夏红梅,等.基于改进蚁群算法的多机器人路径规划研究[J].河北工业大学学报,2016,45(5):28-34.
[56]	POHL I.Heuristic search viewed as path finding in a graph[J].Artificial Intelligence,1970,1(3):193-204.
[57]	GILON D,FELNER A,STERN R.Dynamic potential search-a new bounded suboptimal search[C]//Proceedings of the 9th Annual Symposium on Combinatorial Search.Washington D.C.,USA:IEEE Press,2016:45-65.
[58]	WALKER T T,STURTEVANT N R,FELNER A.Extended increasing cost tree search for non-unit cost domains[C]//Proceedings of International Joint Conference on Artificial Intelligence.Washington D.C.,USA:IEEE Press,2018:534-540.
[59]	PEARL J,KIM J H.Studies in semi-admissible heuristics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1982,4(4):392-399.
[60]	BARER M,SHARON G,STERN R,et al.Suboptimal variants of the conflict-based search algorithm for the multi-agent path finding problem[J].Frontiers in Artificial Intelligence and Applications,2014,263:961-962.
[61]	COHEN L,KOENIG S.Bounded suboptimal multi-agent path finding using highways[C]//Proceedings of International Joint Conference on Artificial Intelligence.Washington D.C.,USA:IEEE Press,2016:3978-3979.
[62]	COHEN L,URAS T,KUMAR T K S,et al.Improved solvers for bounded-suboptimal multi-agent path finding[C]//Proceedings of International Joint Conference on Artificial Intelligence.[S.l.]:AAAI Press,2016:677-690.
[63]	BAE H,KIM G,KIM J,et al.Multi-robot path planning method using reinforcement learning[J].Applied Sciences,2019,9(15):3057-3059.
[64]	SURYNEK P.Unifying search-based and compilation-based approaches to multi-agent path finding through satisfiability modulo theories[C]//Proceedings of the 12th Annual Symposium on Combinatorial Search.Washington D.C.,USA:IEEE Press,2019:15-20.