Multi-robot Path Planning Based on CBS Algorithm

Authors

Qiao Qiao, Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China;Follow
Yan Wang, Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China;Follow
Zhicheng Ji, Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China;

Abstract

Abstract: Aiming at the long multi-robot planning path and long one-way search running time of conflict-based search(CBS) in the multi-agent path finding(MAPF), an improved CBS algorithm is proposed, which in a two-way A^* focus search is used to optimize the search direction and search method. The suboptimal factorωis introduced into the underlying search function of the CBS algorithm to improve the efficiency of path search. The one-way search in the conflict search algorithm is optimized to a two-way A^* search. The experimental results show that the path cost of the improved CBS algorithm is shortened by 14.82%, and the total running time is shortened by 10.63%.

Recommended Citation

Qiao, Qiao; Wang, Yan; and Ji, Zhicheng (2022) "Multi-robot Path Planning Based on CBS Algorithm," Journal of System Simulation: Vol. 34: Iss. 12, Article 15.
DOI: 10.16182/j.issn1004731x.joss.22-FZ0926
Available at: https://dc-china-simulation.researchcommons.org/journal/vol34/iss12/15

First Page

2659

Revised Date

2022-09-23

DOI Link

https://doi.org/10.16182/j.issn1004731x.joss.22-FZ0926

Last Page

2669

CLC

TP242

Recommended Citation

Qiao Qiao, Yan Wang, Zhicheng Ji. Multi-robot Path Planning Based on CBS Algorithm[J]. Journal of System Simulation, 2022, 34(12): 2659-2669.

Corresponding Author

Yan Wang,wangyan@jiangnan.edu.cn

DOI

10.16182/j.issn1004731x.joss.22-FZ0926