Multi-agent CBS Path Planning Algorithm Based on Minimum Planning Margin First

doi:10.16182/j.issn1004731x.joss.25-0599

Abstract

Abstract:

To address the problems of chain effect and insufficient solving efficiency in the conflict tree (CT) expansion of the traditional conflict-based search (CBS) framework, a minimum-margin-first CBS algorithm based on planning margin was proposed. The calculation of planning margin was introduced into the underlying A* search, and the robots with the minimum margin were prioritized in the high-level conflict resolution, to suppress the chain expansion of the CT while ensuring path optimality. Simulation experiments show that the proposed algorithm significantly reduces the amount of CT node expansion and the number of root node conflicts and effectively improves the solving efficiency, verifying the effectiveness and superiority of the algorithm.

Key words: path planning, conflict-based search algorithm, planning margin, conflict resolution

CLC Number:

TP242

Liang Longxiao, Mao Jianlin, Wang Niya, Fang Chengyuan, Zhou Wenna. Multi-agent CBS Path Planning Algorithm Based on Minimum Planning Margin First[J]. Journal of System Simulation, 2026, 38(5): 1159-1173.

Figures/Tables 14

Fig. 1

Fig. 2

Fig. 3

Table 1

Robot path planning

路径	t=0	t=1	t=2	t=3	t=4	t=5	t=6
$p 1 . r o o t$	(0,3)	(1,3)	(2,3)	(3,3)	(3,2)	(3,1)	(3,0)
$p 2 . r o o t$	(2,1)	(2,2)	(2,3)	(2,4)
$p 1.1$	(0,3)	(1,3)	(1,2)	(1,1)	(1,0)	(2,0)	(3,0)
$p 3 . r o o t$	(0,3)	(3,1)	(2,1)	(1,1)	(1,0)
$p 1.3$	(4,1)	(1,3)	(1,2)	(2,2)	(3,2)	(3,1)	(3,0)
$p 4 . r o o t$	(0,3)	(2,4)	(3,4)	(3,3)	(3,2)
$p 1.5$	(0,3)	(1,3)	(1,2)	(2,2)	(2,1)	(2,0)

Table 1

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Table 2

Table 3

Table 4

Fig. 8

Fig. 9

Table 5

References 32

[1]	张书凡, 毛剑琳, 张凯翔, 等. 面向不确定性的多机器人路径鲁棒规划研究综述[J]. 控制与决策, 2024, 39(12): 3873-3888.
	Zhang Shufan, Mao Jianlin, Zhang Kaixiang, et al. Survey on Robust Multi-robot Path Planning Under Uncertainty[J]. Control and Decision, 2024, 39(12): 3873-3888.
[2]	Bai Yifan, Kotpalliwar Shruti, Kanellakis Christoforos, et al. Multi-agent Path Planning Based on Conflict-based Search (CBS) Variations for Heterogeneous Robots[J]. Journal of Intelligent & Robotic Systems, 2025, 111(1): 26.
[3]	王雪霖. 基于冲突搜索的动态环境实时多智能体路径规划[D]. 青岛: 青岛科技大学, 2024.
	Wang Xuelin. Real-time Multi-agent Path Planning in Dynamc Environments with Conflict-based Search[D]. Qingdao: Qingdao University of Science and Technology, 2024.
[4]	Yu Jingjin, LaValle S M. Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics[J]. IEEE Transactions on Robotics, 2016, 32(5): 1163-1177.
[5]	林跃杭. 复杂环境下基于跳点的多机器人路径规划算法研究[D]. 成都: 电子科技大学, 2025.
	Lin Yuehang. Research on Multi-robot Path Planning Algorithm Based on Jump Points in Complex Environments[D]. Chengdu: University of Electronic Science and Technology of China, 2025.
[6]	王卓然, 文家燕, 谢广明, 等. 基于改进CBS算法的多智能体路径规划[J]. 智能系统学报, 2023, 18(6): 1336-1343.
	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.
[7]	Fang Chengyuan, Mao Jianlin, Li Dayan, et al. Regional Constraint Module-based Multi-agent Path Planning Approach for Car-like Agents[J]. Journal of Shanghai Jiaotong University (Science), 2024: 1-11.
[8]	宋钰. 多智能体配送路径规划与十字路口自主交会算法的研究[D]. 太原: 山西大学, 2024.
	Song Yu. Research on Multi-agent Distribution Path Planning and Autonomous Intersection Algorithm[D]. Taiyuan: Shanxi University, 2024.
[9]	张云龙. 基于多智能体路径规划的公交车辆排班方法的研究与实现[D]. 北京: 北京邮电大学, 2024.
	Zhang Yunlong. Research on Implementation of Bus Scheduling Approach Based on Multi-agent Path Planning[D]. Beijing: Beijing University of Posts and Telecommunications, 2024.
[10]	王子晗. 基于冲突搜索的启发式多智能体路径规划算法研究[D]. 烟台: 烟台大学, 2023.
	Wang Zihan. Research on Heuristic Multi-agent Path Finding Algorithm for Conflict-based-search[D]. Yantai: Yantai University, 2023.
[11]	王昱, 张旭秀. 一种结合选择性通信与冲突解决的多智能体路径规划方法[J]. 电子与信息学报, 2025, 47(8): 2830-2840.
	Wang Yu, Zhang Xuxiu. A Multi-agent Path Finding Strategy Combining Selective Communication and Conflict Resolution[J]. Journal of Electronics & Information Technology, 2025, 47(8): 2830-2840.
[12]	Morris R, Pāsāreanu Corina S, Luckow K, et al. Planning, Scheduling and Monitoring for Airport Surface Operations[C]//The Workshops of the Thirtieth AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2016: 608-614.
[13]	Ma Hang, Hönig Wolfgang, Cohen L, et al. Overview: A Hierarchical Framework for Plan Generation and Execution in Multirobot Systems[J]. IEEE Intelligent Systems, 2017, 32(6): 6-12.
[14]	张凯翔, 毛剑琳, 向凤红, 等. 基于讨价还价博弈机制的B-IHCA*多机器人路径规划算法[J]. 自动化学报, 2023, 49(7): 1483-1497.
	Zhang Kaixiang, Mao Jianlin, Xiang Fenghong, et al. B-IHCA*, a Bargaining Game Based Multi-agent Path Finding Algorithm[J]. Acta Automatica Sinica, 2023, 49(7): 1483-1497.
[15]	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.
[16]	吴文君, 王腾达, 孙阳, 等. 多智能体路径规划技术研究综述[J]. 北京工业大学学报, 2024, 50(10): 1263-1272.
	Wu Wenjun, Wang Tengda, Sun Yang, et al. Survey of Multi-agent Path Finding Technology[J]. Journal of Beijing University of Technology, 2024, 50(10): 1263-1272.
[17]	He Zhibo, Liu Chenguang, Chu Xiumin, et al. Dynamic Anti-collision A-star Algorithm for Multi-ship Encounter Situations[J]. Applied Ocean Research, 2022, 118: 102995.
[18]	Standley T. Finding Optimal Solutions to Cooperative Pathfinding Problems[C]//Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence and the Twenty-Second Innovative Applications of Artificial Intelligence Conference and the First Symposium on Educational Advances in Artificial Intelligence. Palo Alto: AAAI Press, 2010: 173-178.
[19]	Sharon Guni, Stern Roni, Felner Ariel, et al. Conflict-based Search for Optimal Multi-agent Pathfinding[J]. Artificial Intelligence, 2015, 219: 40-66.
[20]	Boyarski Eli, Felner Ariel, Stern Roni, et al. ICBS: The Improved Conflict-based Search Algorithm for Multi-agent Pathfinding[C]//Eighth Annual Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2021: 223-225.
[21]	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
	Xuan Zhiwei, Mao Jianlin, Zhang Kaixiang. Low-expansion A* Algorithm Based on CBS Framework for Complex Map[J]. Acta Electronica Sinica, 2022, 50(8): 1943-1950.
[22]	Li Jiaoyang, Ruml W, Koenig S. EECBS: A Bounded-suboptimal Search for Multi-agent Path Finding[C]//Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence and the Thirty-Third Conference on Innovative Applications of Artificial Intelligence and the Eleventh Symposium on Educational Advances in Artificial Intelligence. Palo Alto: AAAI Press, 2021: 12353-12362.
[23]	Fang Chengyuan, Mao Jianlin, Li Dayan, et al. A Coordinated Scheduling Approach for Task Assignment and Multi-agent Path Planning[J]. Journal of King Saud University-Computer and Information Sciences, 2024, 36(1): 101930.
[24]	Silver David. Cooperative Pathfinding[C]//First Artificial Intelligence and Interactive Digital Entertainment Conference. Palo Alto: AAAI Press, 2005: 117-122.
[25]	Ma Hang, Harabor Daniel, Stuckey Peter J, et al. Searching with Consistent Prioritization for Multi-agent Path Finding[C]//Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence. Palo Alto: AAAI Press, 2019: 938.
[26]	张凯翔, 毛剑琳, 宣志玮, 等. 面向关隘地形的分层调度多机器人路径规划[J]. 计算机集成制造系统, 2024, 30(1): 172-183.
	Zhang Kaixiang, Mao Jianlin, Xuan Zhiwei, et al. Hierarchical Scheduling Based Multi-robot Path Planning for Pass Terrain[J]. Computer Integrated Manufacturing Systems, 2024, 30(1): 172-183.
[27]	Li Haodong, Zhao Tao, Songyi Dian. Prioritized Planning Algorithm for Multi-robot Collision Avoidance Based on Artificial Untraversable Vertex[J]. Applied Intelligence, 2022, 52(1): 429-451.
[28]	杨邹, 毛剑琳, 李大焱, 等. 基于冲突概率反馈的CBS分层多机器人路径规划[J]. 计算机集成制造系统, 2025, 31(9): 3391-3400.
	Yang Zou, Mao Jianlin, Li Dayan, et al. CBS Hierarchical Multi-agent Path Finding Based on Conflict Probability Feedback[J]. Computer Integrated Manufacturing Systems, 2025, 31(9): 3391-3400.
[29]	Li Jiaoyang, Harabor Daniel, Stuckey Peter J. Disjoint Splitting for Multi-agent Path Finding with Conflict-based Search[C]//Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling. Palo Alto: AAAI Press, 2019: 279-283.
[30]	周雯娜, 毛剑琳, 王妮娅, 等. 基于多地形因素引导的群机器人CBS路径规划算法[J]. 计算机工程与应用, 2026, 62(2): 359-370.
	Zhou Wenna, Mao Jianlin, Wang Niya, et al. CBS Path Planning Algorithm for Swarm Robots Guided by Multiple Terrain Factors[J]. Computer Engineering and Applications, 2026, 62(2): 359-370.
[31]	Sturtevant N R. Benchmarks for Grid-based Pathfinding[J]. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(2): 144-148.
[32]	Okumura K. Improving LaCAM for Scalable Eventually Optimal Multi-agent Pathfinding[C]//Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. California: IJCAI, 2023: 243-251.

地图	机器人数量	HCA*	LaCAM*	PBS	MMF-CBS-DS
random-64-64-10	10	430.8	439.4	429.9	429.9
	20	864.3	901.1	863.0	863.0
	30	1 268.1	1 337.2	1 267.5	1 267.5
	40	1 701.4	1 811.1	1 700.0	1 691.5
	50	2 149.8	2 270.5	2 137.9	2 111.7
	60	2 593.0	2 754.4	2 576.9	2 532.9
	70	3 031.5	3 287.8	3 006.5	3 150.8
	80	3 456.0	3 762.3	3 431.7	3 374.8
random-64-64-20	10	457.0	463.8	456.1	456.1
	20	918.4	934.9	906.2	906.2
	30	1 354.2	1 411.1	1 332.5	1 332.4
	40	1 810.2	1 910.2	1 777.3	1 777.2
	50	2 278.3	2 386.0	2 213.0	2 212.9
	60	2 735.4	2 900.0	2 632.6	2 632.3
	70	3 200.2	3 443.0	3 076.0	3 062.7
random-32-32-10	10	222.8	229.2	222.4	222.4
	20	448.4	477.1	447.2	447.2
	30	670.8	737.8	664.3	664.1
	40	896.8	999.6	887.3	887.1
	50	1 132.2	1 286.5	1 092.0	1 091.0
	60	1 365.4	1 507.8	1 276.5	1 215.3

地图	机器人数量	CBS	CBS-DS	MMF-CBS-DS
random-64-64-10	10	1.6	1.6	1.2
	20	4.6	4.5	3.4
	30	355.7	49.4	40.3
	40	2 134.3	327	108.3
	50	32 644.0	2 095.0	290.7
	60	31 133.6	4 632.8	410.6
	70	54 797.0	4 608.0	566.5
	80	31 797.7	4 755.7	2 999.8
random-64-64-20	10	1.2	1.2	1.4
	20	21.6	11.4	11.0
	30	426.0	136.1	78.1
	40	21 166.8	2 412.0	690.1
	50	22 588.4	6 559.5	2 648.7
	60	438 308.1	57 003.9	5 491.0
	70	525 043.7	71 492.3	70 817.7
random-32-32-10	10	15.6	6.3	6.5
	20	49.3	19.0	16.5
	30	46 735.5	1 286.7	383.6
	40	211 694.2	11 066.5	3 057.3
	50	236 498.5	28 155.9	4 887.0
	60	4 997.0	2 668.5	487.0

地图	机器人数量	CBS	CBS-DS	MMF-CBS-DS
random-64-64-10	10	1.7	1.7	0.88
	20	4.4	4.3	4.7
	30	1 722.0	181.5	170.7
	40	5 103.3	703.0	242.9
	50	126 960.1	8 197.8	689.8
	60	111 600.8	16 178.3	987.4
	70	169 686.6	10 306.5	1 095.7
	80	40 658.4	7 363.9	4 558.8
random-64-64-20	10	0.88	1.2	0.88
	20	53.1	99.2	17.7
	30	1 099.1	655.1	327.5
	40	66 633.8	6 251.8	4 363.4
	50	37 193.2	24 750.2	12 293.2
	60	891 989.6	791 882.1	106 313.1
	70	832 745.8	918 059.7	110 843.1
random-32-32-10	10	63.8	19.4	22.8
	20	149.5	49.4	47.0
	30	224 965.4	4 852.1	1 240.5
	40	501 823.9	18 364.6	7 332.8
	50	498 414.6	50 606.5	4 887.0
	60	6 861.8	3 461.3	585.5