[1]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]
Copy

Multi-agent path planning based on improved CBS algorithm

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 18 Number of periods: 2023 6 Page number: 1336-1343 Column: 吴文俊人工智能科学技术奖论坛 Public date: 2023-11-05
Title:
Multi-agent path planning based on improved CBS algorithm
Author(s):
WANG Zhuoran1;  WEN Jiayan1; 2;  XIE Guangming1; 3;  JIANG Wenyu1
1. School of Automation, Guangxi University of Science and Technology, Liuzhou 545616, China;
2. Guangxi Key Laboratory of Automobile Components and Vehicle technology, Guangxi University of Science and Technology, Liuzhou 545006, China;
3. College of Engineering, Peking University, Beijing 100871, China
Keywords:
multi-agent; global-path planning; conflict-based search algorithm; improved conflict-based search algorithm; machine learning; ranking learning; RankNet algorithm; conflict selection policy
CLC:
TP23；TP18
DOI:
10.11992/tis.202211006
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.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems