计算机工程 ›› 2020, Vol. 46 ›› Issue (4): 1-10.doi: 10.19678/j.issn.1000-3428.0056738
刘庆周, 吴锋
收稿日期:
2019-11-28
修回日期:
2020-02-05
出版日期:
2020-04-15
发布日期:
2020-02-07
作者简介:
刘庆周(1994-),男,硕士研究生,主研方向为多智能体路径规划;吴锋,副教授。
基金项目:
LIU Qingzhou, WU Feng
Received:
2019-11-28
Revised:
2020-02-05
Online:
2020-04-15
Published:
2020-02-07
摘要: 多智能体路径规划是一类寻找多个智能体从起始位置到目标位置且无冲突的最优路径集合的问题,针对该问题的研究在物流、军事和安防等领域有着大量的应用场景。对国内外关于多智能体路径规划问题的研究进展进行系统整理和分类,按照结果最优性的不同,多智能体路径规划算法被分为最优算法和近似算法2类。最优的多智能体路径规划算法主要分为基于A*搜索、基于代价增长树、基于冲突搜索和基于规约的4种算法。近似的多智能体路径规划算法主要分为无边界次优的算法和有边界次优的算法2类。基于上述分类,分析各种算法的特点,介绍近年来具有代表性的研究成果,并对多智能体路径规划问题未来的研究方向进行展望。
中图分类号:
刘庆周, 吴锋. 多智能体路径规划研究进展[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.
[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. |
[1] | 姜妍, 张立国. 面向深度学习模型的对抗攻击与防御方法综述[J]. 计算机工程, 2021, 47(1): 1-11. |
[2] | 苏炯铭, 刘鸿福, 项凤涛, 吴建宅, 袁兴生. 深度神经网络解释方法综述[J]. 计算机工程, 2020, 46(9): 1-15. |
[3] | 尚迪雅, 孙华, 洪振厚, 曾庆亮. 基于无梯度进化的神经架构搜索算法研究综述[J]. 计算机工程, 2020, 46(9): 16-26. |
[4] | 邓志辉, 王少辉, 王平. 基于合数阶双线性对的可搜索加密方案分析与改进[J]. 计算机工程, 2020, 46(9): 123-128,135. |
[5] | 杨小东, 陈桂兰, 李婷, 刘瑞, 赵晓斌. 基于无证书密码体制的多用户密文检索方案[J]. 计算机工程, 2020, 46(9): 129-135. |
[6] | 张凯, 周德云, 杨振, 潘潜. 基于自适应谐振理论的武器目标分配快速决策算法[J]. 计算机工程, 2020, 46(9): 283-291,297. |
[7] | 杜学武, 张明新, 沙广涛, 伍秋玉. 基于改进蝙蝠算法的模糊PID规则优化研究[J]. 计算机工程, 2020, 46(8): 305-312. |
[8] | 王汝言, 刘宇哲, 张普宁, 亢旭源, 李学芳. 面向物联网的边云协同实体搜索方法[J]. 计算机工程, 2020, 46(8): 43-49. |
[9] | 周诗源, 王英林. 基于布谷鸟搜索优化算法的多文档摘要方法[J]. 计算机工程, 2020, 46(7): 58-64,71. |
[10] | 蔡延光, 乐冰, 蔡颢, 李旭阳. 暴雨天气下高速公路短时交通流预测[J]. 计算机工程, 2020, 46(6): 34-39. |
[11] | 陈鹏, 王子磊. 融合深度学习与搜索的实时策略游戏微操方法[J]. 计算机工程, 2020, 46(6): 50-59. |
[12] | 牛淑芬, 陈俐霞, 刘文科, 王彩芬, 杜小妮. 电子邮件系统中支持关键字搜索的代理重加密方案[J]. 计算机工程, 2020, 46(6): 136-143. |
[13] | 王斌, 房新秀, 魏天佑. 基于差异节点集的加权频繁项集挖掘算法[J]. 计算机工程, 2020, 46(5): 150-156. |
[14] | 李晓, 司怀伟, 郭宗沂, 李东雨, 谭国真. 一种维持约束网络相容性的双向传播策略[J]. 计算机工程, 2020, 46(4): 46-52. |
[15] | 李嘉伟, 张激, 赵俊才, 丁如艺. 一种SRIO网络负载均衡最短路径路由算法[J]. 计算机工程, 2020, 46(3): 214-221,228. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||
|
公众号