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

Authors

• Longxiao Liang, 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
• Niya Wang, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
• Chengyuan Fang, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
• Wenna Zhou, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China

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.

Recommended Citation

Liang, Longxiao; Mao, Jianlin; Wang, Niya; Fang, Chengyuan; and Zhou, Wenna (2026) "Multi-agent CBS Path Planning Algorithm Based on Minimum Planning Margin First," Journal of System Simulation: Vol. 38: Iss. 5, Article 3.
DOI: 10.16182/j.issn1004731x.joss.25-0599
Available at: https://dc-china-simulation.researchcommons.org/journal/vol38/iss5/3

First Page

1159

Last Page

1173

CLC

TP242; TP 18

Recommended Citation

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

Corresponding Author

Mao Jianlin

DOI

10.16182/j.issn1004731x.joss.25-0599