[1]王卓然,文家燕,谢广明,等.基于改进CBS算法的多智能体路径规划[J].智能系统学报,2023,18(6):1336-1343.[doi:10.11992/tis.202211006]
WANG Zhuoran,WEN Jiayan,XIE Guangming,et al.Multi-agent path planning based on improved CBS algorithm[J].CAAI Transactions on Intelligent Systems,2023,18(6):1336-1343.[doi:10.11992/tis.202211006]
点击复制
WANG Zhuoran,WEN Jiayan,XIE Guangming,et al.Multi-agent path planning based on improved CBS algorithm[J].CAAI Transactions on Intelligent Systems,2023,18(6):1336-1343.[doi:10.11992/tis.202211006]
基于改进CBS算法的多智能体路径规划
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
18
期数:
2023年第6期
页码:
1336-1343
栏目:
吴文俊人工智能科学技术奖论坛
出版日期:
2023-11-05
- Title:
- Multi-agent path planning based on improved CBS algorithm
- Keywords:
- multi-agent; global-path planning; conflict-based search algorithm; improved conflict-based search algorithm; machine learning; ranking learning; RankNet algorithm; conflict selection policy
- 分类号:
- TP23；TP18
- 摘要:
- 在基于冲突的搜索(conflict-based search, CBS)算法中，冲突的选择具有随机性，导致CBS算法在多智能体路径规划方面的求解效率不佳。为此，本文提出一种改进CBS算法的多智能体路径规划算法。首先，基于冲突子节点的相关信息，提出了一种新的冲突选择策略；然后，为发挥新策略的优势和进一步减少算法的运行时间，采用基于神经网络的RankNet算法来学习新策略，从而得到一个训练好的排序模型；最后，利用训练好的排序模型为CBS算法选择冲突。通过设计实验对改进CBS算法进行仿真验证，结果表明，所提改进算法相比于已有的改进算法，能够有效提高算法的求解效率。
- Abstract:
- In the conflict-based search (CBS) algorithm, random conflict selection leads to poor solution efficiency in multi-agent path planning. Therefore, an improved CBS-based multi-agent path-planning algorithm is proposed in this paper. First, a new conflict selection strategy is introduced according to the information related to the child nodes associated with the conflict. Next, the RankNet algorithm based on a neural network is used to learn the new strategy and further reduce the running time of the algorithm, obtaining a trained ranking model. Finally, this well-trained ranking model is utilized to select conflicts for the CBS algorithm. Simulation verification of the improved CBS algorithm was performed by designing experiments. Results show that the proposed CBS algorithm effectively enhances the efficiency of the algorithm compared with the existing improved algorithm.
- 参考文献/References:
-
[1] 刘庆周, 吴锋. 多智能体路径规划研究进展[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
[2] 张飞, 白伟, 乔耀华, 等. 基于改进D*算法的无人机室内路径规划[J]. 智能系统学报, 2019, 14(4): 662–669
ZHANG Fei, BAI Wei, QIAO Yaohua, et al. UAV indoor path planning based on improved D* algorithm[J]. CAAI transactions on intelligent systems, 2019, 14(4): 662–669
[3] LI J, TINKA A, KIESEL S, et al. Lifelong multi-agent path finding in large-scale warehouses[C]//Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems. Auckland: International Foundation for Autonomous Agents and Multiagent Systems, 2020: 1898-1900.
[4] ZHANG Zheng, GUO Qing, CHEN Juan, et al. Collision-free route planning for multiple AGVs in an automated warehouse based on collision classification[J]. IEEE access, 2018, 6: 26022–26035.
[5] MA Hang, YANG Jingxing, COHEN L, et al. Feasibility study: moving non-homogeneous teams in congested video game environments[C]//Proceedings of the 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Arizona: AAAI Press, 2017, 13(1): 270-272.
[6] MOHANTY S, NYGREN E, LAURENT F, et al. Flatland-RL: multi-agent reinforcement learning on trains[EB/OL]. (2020-10-10)[2022-11-10]. https://arxiv.org/abs/2012.05893.pdf.
[7] CHOUDHURY S, SOLOVEY K, KOCHENDERFER M, et al. Coordinated multi-agent pathfinding for drones and trucks over road networks[C]//Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems. New Zealand: International Foundation for Autonomous Agents and Multiagent Systems, 2022: 272-280.
[8] CARTUCHO J, VENTURA R, VELOSO M. Robust object recognition through symbiotic deep learning in mobile robots[C]//2018 IEEE/RSJ International Conference on Intelligent Robots and Systems. Madrid: IEEE, 2019: 2336-2341.
[9] SHARON G, STERN R, FELNER A, et al. Conflict-based search for optimal multi-agent pathfinding[J]. Artificial intelligence, 2015, 219: 40–66.
[10] 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. Buenos Aires: AAAI Press, 2015: 740-746.
[11] FELNER A, LI Jiaoyang, BOYARSKI E, et al. Adding heuristics to conflict-based search for multi-agent path finding[C]//Proceedings of the 28th International Conference on Automated Planning and Scheduling. California: AAAI Press, 2018, 28: 83-87.
[12] LI Jiaoyang, GANGE G, HARABOR D, et al. New techniques for pairwise symmetry breaking in multi-agent path finding[C]//Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling. Nancy: AAAI Press, 2020, 30: 193-201.
[13] LI Jiaoyang, HARABOR D, STUCKEY P J, et al. Disjoint splitting for multi-agent path finding with conflict-based search[C]//Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling. California: AAAI Press, 2021, 29: 279-283.
[14] BOYARSKI E, FELNER A, LE BODIC P, et al. Further improved heuristics for conflict-based search[C]//Proceedings of the Fourteenth International Symposium on Combinatorial Search. Guangzhou: AAAI Press, 2021, 12(1): 213-215.
[15] BOYARSKI E, FELNER A, LE BODIC P, et al. Faware conflict prioritization & improved heuristics for conflict-based search[C]//Proceedings of the 35th AAAI Conference on Artificial Intelligence. Vancouver: AAAI Press, 2021, 35(14): 12241-12248.
[16] 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.
[17] BOYARSKI E, FELNER A, HARABOR D, et al. Iterative-deepening conflict-based search[C]//Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Yokohama: International Joint Conferences on Artificial Intelligence Organization, 2020: 4084-4090.
[18] LI Jiaoyang, RUML W, KOENIG S. EECBS: a bounded-suboptimal search for multi-agent path finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence. Virtual: AAAI Press, 2021, 35(14): 12353-12362.
[19] HUANG Taoan, 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. Virtual: AAAI Press, 2021, 35(13): 11246-11253.
[20] BURGES C, SHAKED T, RENSHAW E, et al. Learning to rank using gradient descent[C]//Proceedings of the 22nd international conference on Machine learning. New York: ACM, 2005: 89-96.
[21] STERN R, STURTEVANT N, FELNER A, et al. Multi-agent pathfinding: definitions, variants, and benchmarks[C]//Proceedings of the international symposium on combinatorial search. California: AAAI Press, 2021, 10(1): 151-158.
[22] SILVER D. Cooperative pathfinding[C]//Proceedings of the First AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. California: AAAI Press, 2021, 1(1): 117-122.
[23] 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.
[24] LI Jiaoyang, 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. Macao: International Joint Conferences on Artificial Intelligence Organization, 2019: 442-449.
[25] BOYRASKY E, 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. Prague: PKP, 2015, 25: 47-51.
- 相似文献/References:
-
[1]谭树彬,刘建昌.Multi-Agent的连续轧制过程控制系统研究[J].智能系统学报,2008,3(2):150.
TAN Shu-bin,LIU Jian-chang.Research On multiAgent based control system for continuous rolling process[J].CAAI Transactions on Intelligent Systems,2008,3():150.
[2]雷明,周超,周绍磊,等.考虑时变时滞的多移动智能体分布式编队控制[J].智能系统学报,2012,7(6):536.
LEI Ming,ZHOU Chao,ZHOU Shaolei,et al.Decentralized formation control of multiple mobile agents considering timevarying delay[J].CAAI Transactions on Intelligent Systems,2012,7():536.
[3]郭文强,高晓光,侯勇严,等.采用MSBN多智能体协同推理的智能农业车辆环境识别[J].智能系统学报,2013,8(5):453.[doi:10.3969/j.issn.1673-4785.201210057]
GUO Wenqiang,GAO Xiaoguang,HOU Yongyan,et al.Environment recognition of intelligent agricultural vehicles based on MSBN and multi-agent coordinative inference[J].CAAI Transactions on Intelligent Systems,2013,8():453.[doi:10.3969/j.issn.1673-4785.201210057]
[4]张文旭,马磊,王晓东.基于事件驱动的多智能体强化学习研究[J].智能系统学报,2017,12(1):82.[doi:10.11992/tis.201604008]
ZHANG Wenxu,MA Lei,WANG Xiaodong.Reinforcement learning for event-triggered multi-agent systems[J].CAAI Transactions on Intelligent Systems,2017,12():82.[doi:10.11992/tis.201604008]
[5]徐鹏,谢广明,文家燕,等.事件驱动的强化学习多智能体编队控制[J].智能系统学报,2019,14(1):93.[doi:10.11992/tis.201807010]
XU Peng,XIE Guangming,WEN Jiayan,et al.Event-triggered reinforcement learning formation control for multi-agent[J].CAAI Transactions on Intelligent Systems,2019,14():93.[doi:10.11992/tis.201807010]
[6]成怡,肖宏图.融合改进A*算法和Morphin算法的移动机器人动态路径规划[J].智能系统学报,2020,15(3):546.[doi:10.11992/tis.201812023]
CHENG Yi,XIAO Hongtu.Mobile-robot dynamic path planning based on improved A* and Morphin algorithms[J].CAAI Transactions on Intelligent Systems,2020,15():546.[doi:10.11992/tis.201812023]
[7]殷昌盛,杨若鹏,朱巍,等.多智能体分层强化学习综述[J].智能系统学报,2020,15(4):646.[doi:10.11992/tis.201909027]
YIN Changsheng,YANG Ruopeng,ZHU Wei,et al.A survey on multi-agent hierarchical reinforcement learning[J].CAAI Transactions on Intelligent Systems,2020,15():646.[doi:10.11992/tis.201909027]
[8]赵玉新,杜登辉,成小会,等.基于强化学习的海洋移动观测网络观测路径规划方法[J].智能系统学报,2022,17(1):192.[doi:10.11992/tis.202106004]
ZHAO Yuxin,DU Denghui,CHENG Xiaohui,et al.Path planning for mobile ocean observation network based on reinforcement learning[J].CAAI Transactions on Intelligent Systems,2022,17():192.[doi:10.11992/tis.202106004]
[9]陆升阳,赵怀林,刘华平.场景图谱驱动目标搜索的多智能体强化学习[J].智能系统学报,2023,18(1):207.[doi:10.11992/tis.202111034]
LU Shengyang,ZHAO Huailin,LIU Huaping.Multi-agent reinforcement learning for scene graph-driven target search[J].CAAI Transactions on Intelligent Systems,2023,18():207.[doi:10.11992/tis.202111034]
[10]蒲兴成,张玲侠.基于合作?竞争关系马尔可夫切换下异质多智能体系统均方二分组一致研究[J].智能系统学报,2023,18(4):803.[doi:10.11992/tis.202201045]
PU Xingcheng,ZHANG Lingxia.Mean square couple-group consensus for heterogeneous multiagent systems based on Markov switching and cooperative-competitive relation[J].CAAI Transactions on Intelligent Systems,2023,18():803.[doi:10.11992/tis.202201045]
备注/Memo
收稿日期:2022-11-7。
基金项目:国家自然科学基金项目（61963006）；广西自然科学基金面上项目（2018GXNSFAA050029）；广西科技重大专项（桂科AA22068064）；2022年广西汽车零部件与整车技术重点实验室自主研究课题（2022GKLACVTZZ01）.
作者简介:王卓然,硕士研究生,主要研究方向为多智能体路径规划;文家燕,教授,博士,中国自动化学会青年工作委员会委员,广西自动化学会理事。主要研究方向为多智能体系统协同控制、多机器人编队控制。现主持国家自然科学基金及省部级基金项目5项,获专利授权8项,发表学术论文2余篇;谢广明,教授,博士生导师,中国自动学会机器人竞赛工作委员会副主任,国际水中机器人联盟创始人,中国仿真学会机器人系统仿真专委会主任委员,主要研究方向为复杂系统动力学与控制、智能仿生机器人多机器人系统与控制。现主持国家自然科学基金重点项目等 8 项,获发明专利授权20 余项。曾荣获国家自然科学奖二等奖、教育部自然科学奖一等奖、吴文俊人工智能科学技术奖创新奖二等奖,发表学术论文 200 余篇
通讯作者:文家燕.E-mail:wenjiayan2012@126.com
更新日期/Last Update:
1900-01-01