Improved PBS Algorithm for Multi-agent Path Planning Based on Conflict Guidance and Punishment Mechanism

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

Abstract

Abstract:

To address the bottleneck in which the priority-based search (priority-based search, PBS) algorithm for multi-agent path planning easily falls into conflict loops and generates invalid node expansions in complex scenarios, an improved algorithm based on conflict guidance and a punishment mechanism (improved PBS multi-agent path finding algorithm based on conflict guidance and punishment mechanism, CGP-PBS) was proposed. A conflict-guided node expansion mechanism was constructed; in high-level search, it comprehensively evaluated path cost and the number of conflicts, preferentially expanded child nodes with high potential for conflict resolution, and delayed the expansion of high-conflict nodes, thereby effectively compressing the search space. A conflict weight punishment mechanism based on time steps and congestion density was introduced; it applied weight attenuation to repeated conflicts and completely avoided infinite loops. Simulation experiments on the Benchmark test set show that, compared with PBS and EECBS algorithms, CGP-PBS significantly improves the solution success rate and solving speed on maps with different densities, verifying its excellent scalability.

Key words: multi-agent, path planning, conflict guidance, conflict punishment, weight attenuation

CLC Number:

TP242

Zhang Jinbao, Mao Jianlin, Qian Chengze, Sun Guimi, Tong Kaixin. Improved PBS Algorithm for Multi-agent Path Planning Based on Conflict Guidance and Punishment Mechanism[J]. Journal of System Simulation, 2026, 38(7): 1950-1963.

Figures/Tables 13

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 1

Conflict record table

ID	$α$	$γ$	CP	W	$N c o u n t$	$N p c$
140	0.1	0.95	<1,8>	0.279	1	12
142	0.1	0.95	<0,3>	0.039	2	8
144	0.1	0.95	<0,16>	0.272	1	4
145	0.1	0.95	<10,26>	0.018	1	2
146	0.1	0.95	—	0	—	0

Table 1

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Table 2

References 21

[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]	Stern Roni, Sturtevant Nathan, Felner Ariel, et al. Multi-agent Pathfinding: Definitions, Variants, and Benchmarks[C]//Proceedings of the International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2021: 151-158.
[3]	Yu Jingjin, Lavalle S M. Optimal Multi-robot Path Planning on Graphs: Structure and Computational Complexity[EB/OL]. (2015-07-12) [2025-08-07]. .
[4]	Varambally Sumanth, Li Jiaoyang, Koenig S. Which MAPF Model Works Best for Automated Warehousing?[C]//Proceedings of the International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2022: 190-198.
[5]	Li Jiaoyang, Sun Kexuan, Ma Hang, et al. Moving Agents in Formation in Congested Environments[C]//Proceedings of the 19th International Conference onAutonomous Agents and Multi-agent Systems. Richland: International Foundation for Autonomous Agentsand Multiagent Systems, 2020: 726-734.
[6]	Wang Chen, Mao Jian. Summary of AGV Path Planning[C]//2019 3rd International Conference on Electronic Information Technology and Computer Engineering (EITCE). Piscataway: IEEE, 2019: 332-335.
[7]	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.
[8]	Stern Roni. Multi-agent Path Finding——An Overview[M]//Gennady S Osipov, Aleksandr I Panov, Konstantin S Yakovlev. Artificial Intelligence: 5th RAAI Summer School, Dolgoprudny, Tutorial Lectures. Cham: Springer International Publishing, 2019: 96-115.
[9]	Sharon Guni, Stern Roni, Felner Ariel, et al. Conflict-based Search for Optimal Multi-agent Pathfinding[J]. Artificial Intelligence, 2015, 219: 40-66.
[10]	Boyarski Eli, Felner Ariel, Stern Roni, et al. ICBS: Improved Conflict-based Search Algorithm for Multi-agent Pathfinding[C]//Proceedings of the 24th International Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2015: 740-746.
[11]	Li Jiaoyang, Harabor Daniel, Stuckey Peter J, et al. Disjoint Splitting for Multi-agent Path Finding with Conflict-based Search[C]//Proceedings of the International Conference on Automated Planning and Scheduling. Palo Alto: AAAI Press, 2019: 279-283.
[12]	宣志玮, 毛剑琳, 张凯翔. 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.
[13]	Li Jiaoyang, Ruml Wheeler, Koenig S. EECBS: A Bounded-suboptimal Search for Multi-agent Path Finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2021: 12353-12362.
[14]	Phillips M, Likhachev M. SIPP: Safe Interval Path Planning for Dynamic Environments[C]//2011 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2011: 5628-5635.
[15]	Yakovlev Konstantin, Andreychuk Anton, Stern Roni. Revisiting Bounded-suboptimal Safe Interval Path Planning[C]//Proceedings of the International Conference on Automated Planning and Scheduling. Palo Alto: AAAI Press, 2020: 300-304.
[16]	Erdmann M, Lozano-Pérez Tomás. On Multiple Moving Objects[J]. Algorithmica, 1987, 2(1): 477-521.
[17]	Silver David. Cooperative Pathfinding[C]//Proceedings of the First AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Palo Alto: AAAI Press, 2005: 117-122.
[18]	张凯翔, 毛剑琳, 向凤红, 等. 基于讨价还价博弈机制的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.
[19]	Okumura Keisuke, Machida Manao, Défago Xavier, et al. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding[J]. Artificial Intelligence, 2022, 310: 103752.
[20]	Ma Hang, Harabor Daniel, Stuckey Peter J, et al. Searching with Consistent Prioritization for Multi-agent Path Finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2019: 7643-7650.
[21]	Sturtevant N R. Benchmarks for Grid-based Pathfinding[J]. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(2): 144-148.

地图	智能体数量	EECBS	HCA*	PBS	PIBT	CGP-PBS
room-32-32-4	30	829.5/20	858.2/20	819.1/20	904.5/19	821.5/20
	50	1 485.3/20	1 528.7/19	1 454.2/20	1 664.9/20	1 466.5/20
	70	2 211.1/20	2 269.4/16	2 207.8/20	2 522.1/13	2 190.6/20
	90	2 901.6/16	3 082.3/15	3 035.5/19	3 598/13	2 992.2/20
	110	NA/0	3 994.4/5	3 981.4/19	4 741.1/7	3 882.4/19
	130	NA/0	5 058/3	5 071.2/13	6 138.7/7	4 981.8/20
	150	NA/0	5 943/1	6 447.8/7	8 112.3/4	6 258.6/17
random-32-32-20	50	1 156.7/20	1 196.2/20	1 140.4/20	1 320.8/19	1 173/20
	100	2 459.8/20	2 592/20	2 395.4/20	2 980.1/10	2 502.3/20
	150	3 969.3/20	4 264.1/17	3 929.4/20	5 192.7/7	4 040.1/20
	200	5 445/2	6 234.3/3	5 804.2/18	7 750/1	5 805.1/20
	250	NA/0	NA/0	7 802/2	NA/0	7 996.2/18
	270	NA/0	NA/0	NA/0	NA/0	9 020.1/17
maze-32-32-2	25	1 464.3/20	1 532.4/20	1 446.6/20	1 663.6/17	1 491.2/20
	50	3 251.8/20	3 428.2/20	3 161.5/19	3 733.4/16	3 281.8/20
	75	4 914/6	5 466.7/18	5 212.5/17	5 993.9/14	5 340.3/20
	100	6 380/1	7 483/7	7 410.6/8	8 723.6/10	7 697.9/20
	100	2 164.8/20	2 216.1/20	2 148.7/20	2 617.2/20	2 194.5/20
empty-32-32	200	4 539.8/20	4 849.8/20	4 392.5/20	5 957.3/20	4 702.4/20
	300	7 458.9/20	7 945.5/18	7 142/20	10 123.7/18	7 661.5/20
	400	NA/0	NA/0	NA/0	15 467.1/18	11 236.7/20