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]	Teng Li, Peipei Ding, Jinfang Liu. Multi-Stage Multi-AGV Path Planning with Walk under Shelves for Robotic Mobile Fulfillment Systems [J]. Journal of System Simulation, 2022, 34(7): 1512-1523.
[2]	Sen Zhang, Mengyan Zhang, Jingping Shao, Jiexin Pu. Multi-UAVs 3D Path Planning Method Based on Random Strategy Search [J]. Journal of System Simulation, 2022, 34(6): 1286-1295.
[3]	Dun Meng, Zhuo Hu, Huajun Zhang. Simulation of Multi-layer Ship Evacuation System Based on Improved A* Algorithm [J]. Journal of System Simulation, 2022, 34(6): 1375-1382.
[4]	Xiangyang Deng, Limin Zhang, Wei Fang, Miao Tang. Robot Path Planning Based on Bidirectional Aggregation Ant Colony Optimization [J]. Journal of System Simulation, 2022, 34(5): 1101-1108.
[5]	Zhaoqiang Li, Shiyu Zhang. Research on 3D Path Planning Algorithm Based on Fast RRT Algorithm [J]. Journal of System Simulation, 2022, 34(3): 503-511.
[6]	Qiming Wang, Gaoqiang Zong, Jinming Xu. Optimal Path Planning for Multi-stage Automatic Parking and Simulation Analysis [J]. Journal of System Simulation, 2022, 34(2): 385-395.
[7]	Li Zhang, Huizhen Zhang, Dong Liu, Yuxin Lu. Particle Swarm Algorithm for Solving Emergency Material Dispatch Considering Urgency [J]. Journal of System Simulation, 2022, 34(09): 1988-1998.
[8]	Chen Zhimei, Li Min, Shao Xuejuan, Zhao Zhicheng. Obstacle Avoidance Path Planning of Bridge Crane Based on Improved RRT Algorithm [J]. Journal of System Simulation, 2021, 33(8): 1832-1838.
[9]	Li Qi, Wang Wei. Path Designing of Multi-omnidirectional Wheel Collaborative Sorting Platform [J]. Journal of System Simulation, 2021, 33(3): 698-709.
[10]	Huang Xiaodong, Yuan Haitao, Bi Jing, Liu Tao. DQN-based Path Planning Method and Simulation for Submarine and Warship in Naval Battlefield [J]. Journal of System Simulation, 2021, 33(10): 2440-2448.
[11]	Lin Bin, Han Guanghui, Song Chenchen, Zhang Yajing. Traversal Path Planning and Simulation of Robot based on Radiation Scanning [J]. Journal of System Simulation, 2021, 33(1): 84-90.
[12]	Zhu Daqi, Zhu Tingting, Yan Mingzhong. Multi-AUV Complete Coverage Path Planning Based on Improved Neural Network [J]. Journal of System Simulation, 2020, 32(8): 1505-1514.
[13]	Shi Yan, Zhang Lihua, Dong Shouquan, Wang Jue. Cruise Missile Path Planning Based on ACO Algorithm and Bezier Curve Optimization [J]. Journal of System Simulation, 2020, 32(1): 122-129.
[14]	Shi Min, Wei Yukun, Jin Xiangchen, Wang Suqin, Mao Tianlu. Virtual Scene Roaming Method Supporting Multi-layer Path Planning [J]. Journal of System Simulation, 2019, 31(7): 1358-1366.
[15]	Zhao Ping, Lei Xinyu, Chen Bozhi, Yang Jiaoyun. TI-A* Based Multi-robot Dynamic Planning and Coordination Method [J]. Journal of System Simulation, 2019, 31(5): 925-935.