EECBS Multi-robot Path Planning Based on Variable Suboptimal Factors of Prioritizing Conflicts

Authors

Xingyu Yan, 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
Jianlin Mao, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
Zhigang He, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
Dayan Li, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China

Abstract

Abstract: In the process of multi-robot path planning (MRPP), the unavoidable key conflicts between the optimal paths have a significant impact on the efficiency of path solving. To address this issue, an MRPP method based on variable suboptimal factors of prioritizing conflicts (PC) was proposed. Path search was performed at the lower layer of the explicit estimation conflict-based search (EECBS) algorithm; in the upper layer of the EECBS algorithm framework, the PC was determined, and the suboptimal factor of the robot with key conflicts was adaptively increased; by analyzing the distribution of obstacles in the surrounding neighborhoods of key conflicts, the degree of freedom of path nodes was affected, and the suboptimal factor of the robot with key conflicts could be further adjusted. The results under multiple standard maps indicate that compared to the EECBS algorithm, the algorithm proposed in this paper has shortened the solving time by 8.35%~49.14%, and the expansion of the binary constraint tree (CT) of the upper conflict nodes has improved by 3.79%~55.22%, verifying the effectiveness of the proposed algorithm.

Recommended Citation

Yan, Xingyu; Wang, Niya; Mao, Jianlin; He, Zhigang; and Li, Dayan (2024) "EECBS Multi-robot Path Planning Based on Variable Suboptimal Factors of Prioritizing Conflicts," Journal of System Simulation: Vol. 36: Iss. 11, Article 14.
DOI: 10.16182/j.issn1004731x.joss.23-0950
Available at: https://dc-china-simulation.researchcommons.org/journal/vol36/iss11/14

First Page

2662

Last Page

2673

CLC

TP242; TP18

Recommended Citation

Yan Xingyu, Wang Niya, Mao Jianlin, et al. EECBS Multi-robot Path Planning Based on Variable Suboptimal Factors of Prioritizing Conflicts[J]. Journal of System Simulation, 2024, 36(11): 2662-2673.

Corresponding Author

Wang Niya

DOI

10.16182/j.issn1004731x.joss.23-0950