Multi-robot Path Planning Based on CBS Algorithm

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

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%.

Key words: multi-agent path finding(MAPF), two-way search, focus search, path planning, conflict-based search(CBS)

CLC Number:

TP242

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

Figures/Tables 13

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Table 1

Fig. 9

Fig. 10

Fig. 11

Fig. 12

References 16

1	刘晶, 姚维, 章玮. 移动机器人全覆盖路径规划算法研究[J]. 工业控制计算机, 2019, 32(12): 52-54.
	Liu Jing, Yao Wei, Zhang Wei. Research on Complete Coverage Path Planning Algorithm of Mobile Robots[J]. Industrial Control Computer, 2019, 32(12): 52-54.
2	王洪斌, 尹鹏衡, 郑维, 等. 基于改进的A*算法与动态窗口法的移动机器人路径规划[J]. 机器人, 2020, 42(3): 346-353.
	Wang Hongbin, Yin Pengheng, Zheng Wei, et al. Mobile Robot Path Planning Based on Improved A* Algorithm and Dynamic Window Method[J]. Robot, 2020, 42(3): 346-353.
3	强宁, 高洁, 康凤举. 基于PSO和三次样条插值的多机器人全局路径规划[J]. 系统仿真学报, 2017, 29(7): 1397-1404.
	Qiang Ning, Gao Jie, Kang Fengju. Multi-Robot Global Path Planning Based on PSO and Cubic Spline Interpolation[J]. Journal of System Simulation, 2017, 29(7): 1397-1404.
4	张云旺. 物流中心多任务场景下多AGV的路径规划算法设计[D]. 哈尔滨: 哈尔滨工业大学, 2021.
	Zhang Yunwang. Path Planning Algorithm Design of Multi-AGV in Multi-Task Scenario of Logistics Center[D]. Harbin: Harbin Institute of Technology, 2021.
5	杨伦. 消解基于冲突搜索的多智能体路径规划算法中的对顶冲突[D]. 长春: 吉林大学, 2020.
	Yang Lun. Resolving the Top Conflict in the Multi-Agent Path Planning Algorithm Based on Conflict Search[D]. Changchun: Jilin University, 2020.
6	万千. 基于CBS算法的物流分拣多AGV路径规划的研究[D]. 哈尔滨: 哈尔滨工业大学, 2018.
	Wan Qian. Research on Multi-AGV Path Planning for Logistics Sorting Based on CBS Algorithm[D]. Harbin: Harbin Institute of Technology, 2018.
7	Li Jiaoyang, Andrew Tinka, Scott Kiesel, et al. EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding[C]//35th AAAI Conference on Artificial Intelligence. California, SC: Association for the Advancement of Artificial Intelligence, 2021: 12353-12362.
8	朱宝艳. 移动机器人全覆盖路径规划算法研究[D]. 淄博: 山东理工大学, 2017.
	Zhu Baoyan. Research on Complete Coverage Planning Algorithm for Mobile Robots[D]. Zibo: Shandong University of Technology, 2017.
9	赵萍, 雷新宇, 陈波芝, 等. 基于TI-A*的多机器人动态规划协调方法研究[J]. 系统仿真学报, 2019, 31(5): 925-935.
	Zhao Ping, Lei Xinyu, Chen Bozhi, et al. Research on Multi-Robot Dynamic Programming Coordination Method Based on TI-A*[J]. Journal of System Simulation, 2019, 31(5): 925-935.
10	李颀, 汪伟. 多全向轮协同分拣平台的路径规划[J]. 系统仿真学报, 2021, 33(3): 698-709.
	Li Qi, Wang Wei. Path Planning of Multi-omnidirectional Wheel Collaborative Sorting Platform [J]. Journal of System Simulation, 2021, 33(3): 698-709.
11	陈志梅, 李敏, 邵雪卷, 等. 基于改进RRT算法的桥式起重机避障路径规划[J]. 系统仿真学报, 2021, 33(8): 1832-1838.
	Chen Zhimei, Li Min, Shao Xuejuan, et al. Obstacle Avoidance Path Planning of Bridge Crane Based on Improved RRT Algorithm[J]. Journal of System Simulation, 2021, 33(8): 1832-1838.
12	黄晓冬, 苑海涛, 毕敬, 等. 基于DQN的海战场舰船路径规划及仿真[J]. 系统仿真学报, 2021, 33(10): 2440-2448.
	Huang Xiaodong, Yuan Haitao, Bi Jing, et al. Ship Path Planning and Simulation in Naval Battlefield Based on DQN[J]. Journal of System Simulation, 2021, 33(10): 2440-2448.
13	林彬, 韩光辉, 宋晨晨, 等. 基于辐射扫描算法的机器人路径规划与仿真[J]. 系统仿真学报, 2021, 33(1): 84-90.
	Lin Bin, Han Guanghui, Song Chenchen, et al. Robot Path Planning and Simulation Based on Radiation Scanning Algorithm[J]. Journal of System Simulation, 2021, 33(1): 84-90.
14	刘恒麟. 多AGV路径规划算法的研究与实现[D]. 南京: 东南大学, 2020.
	Liu Henglin. Research and Implementation of Multi-AGV Path Planning Algorithm[D]. Nanjing: Southeast University, 2020.
15	Li Jiaoyang, Andrew Tinka, Scott Kiesel, et al. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses[C]//35th AAAI Conference on Artificial Intelligence. California, SC: Association for the Advancement of Artificial Intelligence, 2021: 11272-11281.
16	Li J, Ran M, Xie L. Efficient Trajectory Planning for Multiple Non-holonomic Mobile Robots Via Prioritized Trajectory Optimization[C]//IEEE Robotics and Automation Letters, 2021, 6(2): 405-412. DOI: 10.1109/LRA.2020.3044834 .

机器人数量/个	ECBS运行时间/s	改进ECBS 运行时间/s	运行时间降低百分比/%
4	0.000 43	0.000 42	2.32
8	0.000 59	0.000 58	1.69
12	0.000 85	0.000 72	15.3
16	0.001 29	0.001 14	11.6
20	0.002 43	0.002 50	-2.88
24	0.005 93	0.004 14	30.2
28	0.017 94	0.017 39	3.07
32	0.071 10	0.018 10	74.5

[1]	Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2397-2408.
[2]	Ni Peilong, Mao Pengjun, Wang Ning, Yang Mengjie. Robot Path Planning Based on Improved A-DDQN Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2420-2430.
[3]	Zhang Kaixiang, Mao Jianlin, Wang Niya, Xu Zhihao. Multi-robot Hierarchical Collaborative k-robust Path Planning for Path Interference [J]. Journal of System Simulation, 2025, 37(8): 2074-2088.
[4]	Wan Yuhang, Zhu Zilu, Zhong Chunfu, Liu Yongkui, Lin Tingyu, Zhang Lin. Dynamic Path Planning for Robotic Arms Based on an Improved PPO Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1462-1473.
[5]	Ye Chen, Shao Peng, Zhang Shaoping, Li Wenting, Zhou Tengming. Enhanced Artificial Gorilla Algorithm for Mobile Robot Path Planning [J]. Journal of System Simulation, 2025, 37(6): 1474-1485.
[6]	Zhang Yan, Li Binghua, Huo Tao, Liu Rong. Research on Robot Dynamic Obstacle Avoidance Method Based on Improved A* and Dynamic Window Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1555-1564.
[7]	Zhou Xiaohui, Li Yanqiang, Wang Yong, Zhao Decai, Yang Xiaoyao. Robot Path Planning Based on Ant Colony Algorithm with Dual Heuristic Information [J]. Journal of System Simulation, 2025, 37(5): 1280-1289.
[8]	Yu Die, Bao Baizhong, Si Yan, Duan Jian, Zhan Xiaobin, Shi Tielin. Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm [J]. Journal of System Simulation, 2025, 37(4): 1041-1050.
[9]	Zhang Sen, Dai Qiangqiang. UAV Path Planning Based on Improved Deep Deterministic Policy Gradients [J]. Journal of System Simulation, 2025, 37(4): 875-881.
[10]	He Zhigang, Li Dayan, Wang Niya, Mao Jianlin, Wang Ning. A Multi-robot Collaborative Path Planning Algorithm with Chain Working Mode [J]. Journal of System Simulation, 2025, 37(4): 953-967.
[11]	Lin Guijuan, Li Zihan, Wang Yu. Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction [J]. Journal of System Simulation, 2025, 37(3): 667-678.
[12]	Bai Yuxin, Chen Zhenya, Shi Ruitao, Su Weitao, Ma Zhuoqiang, Yang Shangjin. Research on Robot Path Planning Based on Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2025, 37(3): 742-752.
[13]	Jin Xu, Mo Yuanbin. Multi-strategy Hybrid Mountain Gazelle Optimizer for Robot Path Planning [J]. Journal of System Simulation, 2025, 37(3): 803-821.
[14]	Li Jiongyi, Li Qiang, Zhang Xinwen, Htet Zin Myo, Cai Yongbin. Improved Bidirectional A* Quadratic Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2025, 37(2): 498-507.
[15]	Peng Yi, Lei Yunkui, Yang Qingqing, Li Hui, Wang Jianming. Improved PID Search Algorithm for UAV Path Planning in Mountainous Environments [J]. Journal of System Simulation, 2025, 37(12): 3075-3086.