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

Authors

• Jinbao Zhang, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
• Jianlin Mao, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
• Chengze Qian, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
• Guimi Sun, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
• Kaixin Tong, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China

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.

Recommended Citation

Zhang, Jinbao; Mao, Jianlin; Qian, Chengze; Sun, Guimi; and Tong, Kaixin (2026) "Improved PBS Algorithm for Multi-agent Path Planning Based on Conflict Guidance and Punishment Mechanism," Journal of System Simulation: Vol. 38: Iss. 7, Article 11.
DOI: 10.16182/j.issn1004731x.joss.25-0864
Available at: https://dc-china-simulation.researchcommons.org/journal/vol38/iss7/11

First Page

1950

Last Page

1963

CLC

TP242; TP18

Recommended Citation

Zhang Jinbao, Mao Jianlin, Qian Chengze, et al. 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.

Corresponding Author

Mao Jianlin

DOI

10.16182/j.issn1004731x.joss.25-0864