A Multi-robot Collaborative Path Planning Algorithm with Chain Working Mode

doi:10.16182/j.issn1004731x.joss.23-1455

Abstract

Abstract:

In order to solve the problem that the traditional MAPF algorithms can lead to a large number of repeated paths and thus non-essential energy loss in application scenarios where multiple robots have a common goal point, a multi-robot chain work mode with a tractor is proposed, which divides the robots with common target points into subgroups for multi robot collaborative path planning, and a collaborative dynamic priority SIPP with tractor (Co-DPtSIPP) algorithm is given. The polygonal Fermat point principle and other methods are used to obtain the serial connection areas of each collaborative group robot; considering the sequence of serial connection between the collection robot and the traction robot, segmented path planning is performed; after the collection robots in each group are suspended and towed, they are driven by the towing robots to move forward in a chain like manner; the later path nodes of the traction robot are adjusted in time steps and filled into the paths of each collection robot to avoid collisions with other robots during the movement of multiple collection robots. Experimental results show that the proposed Co-DPtSIPP algorithm can reduce path length by 10%~13% compared, which can effectively reduce robot energy consumption.

Key words: multi-robot collaboration, path planning, safe interval, collecting robots, traction robot, serial connection area

CLC Number:

TP242

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.

Figures/Tables 15

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Table 1

Comparison of path solution quality obtained by Wd-SIPP and Co-DPtSIPP algorithms on 30×83 warehouse map

机器人数量	$N g$	最大完工时间		路径总代价		路径总长度		运行时间/s
机器人数量	$N g$	Wd-SIPP	Co-DPtSIPP	Wd-SIPP	Co-DPtSIPP	Wd-SIPP	Co-DPtSIPP	Wd-SIPP	Co-DPtSIPP
3	3	126.5	143.8	812.5	737.6	642.2	553.6	0.39	1.4
	6	154.9	170.7	1 770	1 591.3	1 381	1 208.3	0.99	4.81
	9	149.1	169.8	2 556.8	2 307.5	1 993.4	1 707.4	1.6	7.7
	12	148.7	172.2	3 361.8	3 042.9	2 630.6	2 282.7	2.28	10.97
	15	157.7	190.0	4 503.2	4 058.6	3 448.3	3 020.4	3.99	25.03
5	2	135.4	160.8	928.0	844.5	769.0	668.1	0.44	2.27
	4	149.8	176.8	1 894.2	1 723.1	1 554.0	1 384.2	0.99	5.24
	6	150.2	174.2	2 849.73	2 331.3	2 271.0	2 001.5	1.79	8.61
	8	167.0	195.4	3 906.7	3 514.6	3 131.9	2 808.4	3.05	26.4
	10	159.2	197.4	5 004.2	4 497.8	3 948.2	3 549.3	4.65	21.11

Table 1

Table 2

Comparison of path solution quality between Wd-SIPP and Co-DPtSIPP algorithms on 100 ×100 warehouse map

机器人数量	$N g$	最大完工时间		路径总代价		路径总长度		运行时间/s
机器人数量	$N g$	Wd-SIPP	Co-DPtSIPP	Wd-SIPP	Co-DPtSIPP	Wd-SIPP	Co-DPtSIPP	Wd-SIPP	Co-DPtSIPP
3	3	204.4	225.8	1 279.7	1 203.6	985.8	894.1	1.08	2.81
	6	230.4	236.1	2 622.8	2 377.8	1 995.2	1 765.1	2.12	7.89
	9	235.2	255.6	3 835.6	3 543.6	3 009.7	2 721.4	3.36	16.22
	12	251.9	265.6	5 454.8	4 971.9	4 239.4	3 764.3	5.61	26.19
	15	252.3	281.3	6 677.8	6 318.0	5 214.8	4 708.0	6.15	52.48
5	2	206.8	235.9	1 463.7	1 328.5	1 210.5	1 080.9	1.36	6.16
	4	219.8	240.2	2 897.1	2 485.2	2 343.6	2 050.6	3.35	12.31
	6	241.1	264.5	4 592.6	4 104.7	3 725.7	3 357.7	6.57	21.4
	8	242.5	271.9	6 237.5	5 477.5	5 065.6	4 422.0	11.25	28.15
	10	256.0	286.7	8 134.4	7 113.3	6 408.1	5 693.8	16.67	40.48

Table 2

Fig. 8

Fig. 9

Table 3

Comparison of path solution quality obtained by Co-DPtSIPP and Co-DPtSIPP* algorithms on 30×83 warehouse map

机器人数量	$N g r o u p$	最大完工时间		路径总代价		路径总长度		运行时间/s
机器人数量	$N g r o u p$	Co-DPtSIPP	Co-DPtSIPP*	Co-DPtSIPP	Co-DPtSIPP*	Co-DPtSIPP	Co-DPtSIPP*	Co-DPtSIPP	Co-DPtSIPP*
3	3	143.8	140.2	737.6	711.5	553.6	544.2	1.40	3.23
	6	170.7	171.1	1 591.3	1 564.0	1 208.3	1 166.0	4.81	9.01
	9	169.8	163.9	2 307.5	2 248.5	1 707.4	1 641.9	7.70	18.13
	12	172.2	165.0	3 042.9	2 951.1	2 282.7	2 195.6	10.97	36.60
	15	191.2	178.1	4 072.3	3 927.6	3 027.9	2 849.6	24.46	51.42
5	2	160.8	161.2	844.5	834.8	668.1	661.0	2.27	3.70
	4	176.8	175.1	1 723.1	1 694.4	1 384.2	1 366.0	5.24	9.34
	6	174.2	173.0	2 331.3	2 416.8	2 001.5	1 949.9	8.61	25.34
	8	195.4	193.6	3 514.6	3 469.8	2 808.4	2 715.8	26.40	49.91
	10	196.7	191.4	4 497.1	4 391.0	3 534.8	3 438.4	20.41	79.20

Table 3

Table 4

Comparison of path solution quality obtained by Co-DPtSIPP and Co-DPtSIPP* algorithms on 100×100 warehouse map

机器人数量	$N g r o u p$	最大完工时间		路径总代价		路径总长度		运行时间/s
机器人数量	$N g r o u p$	Co-DPtSIPP	Co-DPtSIPP*	Co-DPtSIPP	Co-DPtSIPP*	Co-DPtSIPP	Co-DPtSIPP*	Co-DPtSIPP	Co-DPtSIPP*
3	3	224.2	224.5	1 199.0	1 191.5	890.7	885.6	2.77	6.64
	6	234.7	236.8	2 379.1	2 370.5	1 768.1	1 745.1	7.96	15.93
	9	254.2	252.7	3 512.1	3 506.6	2 700.0	2 641.5	15.87	29.14
	12	265.6	264.0	4 971.9	4 908.4	3 764.3	3 664.7	26.19	55.08
	15	281.3	270.4	6 318.0	6 081.5	4 708.0	4 467.6	52.48	64.56
5	2	235.9	236.1	1 328.5	1 329.1	1 080.9	1 075.5	6.16	5.62
	4	240.2	236.7	2 485.2	2 492.4	2 050.6	2 040.2	12.31	17.17
	6	271.1	266.7	4 122.6	4 096.8	3 379.1	3 337.3	22.23	34.2
	8	271.5	274.9	5 493.1	5 476.9	4 432.4	4 367.1	28.99	58.94
	10	286.2	287.7	7 137.3	7 007.7	5 711.8	5 577.6	40.41	95.37

Table 4

Fig. 10

Fig. 11

References 23

1	Stern Roni, Sturtevant N, Felner Ariel, et al. Multi-agent Pathfinding: Definitions, Variants, and Benchmarks[C]//Proceedings of the Twelfth International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2019: 151-158.
2	Sun Yifei, Zhang Zikai, Li Yidong, et al. Joint Optimization of Path Planning and Task Assignment for Space Robot[C]//2021 12th International Symposium on Parallel Architectures, Algorithms and Programming (PAAP). Piscataway: IEEE, 2021: 47-51.
3	毛建旭, 贺振宇, 王耀南, 等. 电力巡检机器人路径规划技术及应用综述[J]. 控制与决策, 2023, 38(11): 3009-3024.
	Mao Jianxu, He Zhenyu, Wang Yaonan, et al. Review of Research and Applications on Path Planning Technology for Power Inspection Robots[J]. Control and Decision, 2023, 38(11): 3009-3024.
4	Kumar V, Sahin F. Cognitive Maps in Swarm Robots for the Mine Detection Application[C]//SMC'03 Conference Proceedings. 2003 IEEE International Conference on Systems, Man and Cybernetics. Conference Theme - System Security and Assurance. Piscataway: IEEE, 2003: 3364-3369.
5	Dai Loulei, Wang Hongguo, Pan Quanke. An Effective Multi-objective Evolutionary Algorithm Based on Decomposition for a Robot Rescue Path Planning Problem[C]//2022 41st Chinese Control Conference (CCC). Piscataway: IEEE, 2022: 2065-2070.
6	Wang Chen, Mao Jian. Summary of AGV Path Planning[C]//2019 3rd International Conference on Electronic Information Technology and Computer Engineering (EITCE). Piscataway: IEEE, 2019: 332-335.
7	Ma Hang, Hönig Wolfgang, Kumar T K S, et al. Lifelong Path Planning with Kinematic Constraints for Multi-agent Pickup and Delivery[C]//Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence. Palo Alto: AAAI Press, 2019: 7651-7658.
8	Zhang Jing, He You, Peng Yingning, et al. Cooperative Path Planning for Adversarial Target Based on Neural Network and Artificial Potential Field[C]//2018 IEEE CSAA Guidance, Navigation and Control Conference (CGNCC). Piscataway: IEEE, 2018: 1-5.
9	Lu Yafei, Wu Anping, Chen Qingyang, et al. An Improved UAV Path Planning Method Based on RRT-APF Hybrid Strategy[C]//2020 5th International Conference on Automation, Control and Robotics Engineering (CACRE). Piscataway: IEEE, 2020: 81-86.
10	Zhao Dewei, Zhang Sheng, Shao Faming, et al. Path Planning for the Rapid Reconfiguration of a Multi-robot Formation Using an Integrated Algorithm[J]. Electronics, 2023, 12(16): 3483.
11	Tai Lei, Paolo Giuseppe, Liu Ming. Virtual-to-real Deep Reinforcement Learning: Continuous Control of Mobile Robots for Mapless Navigation[C]//2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Piscataway: IEEE, 2017: 31-36.
12	张凯翔, 毛剑琳, 向凤红, 等. 基于讨价还价博弈机制的B-IHCA^*多机器人路径规划算法[J]. 自动化学报, 2023, 49(7): 1483-1497.
	Zhang Kaixiang, Mao Jianlin, Xiang Fenghong, et al. B-IHCA^*, a Bargaining Game Based Multi-agent Path Finding Algorithm[J]. Acta Automatica Sinica, 2023, 49(7): 1483-1497.
13	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A^*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
	Xuan Zhiwei, Mao Jianlin, Zhang Kaixiang. Low-expansion A^* Algorithm Based on CBS Framework for Complex Map[J]. Acta Electronica Sinica, 2022, 50(8): 1943-1950.
14	Sharon Guni, Stern Roni, Felner Ariel, et al. Conflict-based Search for Optimal Multi-agent Pathfinding[J]. Artificial Intelligence, 2015, 219: 40-66.
15	Phillips M, Likhachev M. SIPP: Safe Interval Path Planning for Dynamic Environments[C]//2011 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2011: 5628-5635.
16	Carlos Hernández Ulloa, Yeoh W, Baier Jorge A, et al. A Simple and Fast Bi-objective Search Algorithm[C]//Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling. Palo Alto: AAAI Press, 2020: 143-151.
17	Okumura Keisuke, Tixeuil Sébastien. Fault-tolerant Offline Multi-agent Path Planning[C]//Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence. Palo Alto: AAAI Press, 2023: 11647-11654.
18	Atzmon Dor, Stern Roni, Felner Ariel, et al. Robust Multi-agent Path Finding[C]//Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. Palo Alto: AAAI Press, 2018: 1862-1864.
19	Yakovlev Konstantin, Andreychuk Anton, Stern Roni. Revisiting Bounded-suboptimal Safe Interval Path Planning[C]//Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling. Palo Alto: AAAI Press, 2020: 300-304.
20	Silver D. Cooperative Pathfinding[C]//Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference. Palo Alto: AAAI Press, 2021: 117-122.
21	Mandow Lawrence, José Luis Pérez De La Cruz. Multiobjective A^* Search with Consistent Heuristics[J]. Journal of the ACM, 2008, 57(5): 27.
22	Khorshid M, Holte R, Sturtevant N. A Polynomial-time Algorithm for Non-optimal Multi-agent Pathfinding[C]//Proceedings of the Fourth Annual Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2011: 76-83.
23	Greshler Nir, Gordon Ofir, Salzman Oren, et al. Cooperative Multi-agent Path Finding: Beyond Path Planning and Collision Avoidance[C]//2021 International Symposium on Multi-Robot and Multi-Agent Systems (MRS). Piscataway: IEEE, 2021: 20-28.

[1]	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.
[2]	Zhang Sen, Dai Qiangqiang. UAV Path Planning Based on Improved Deep Deterministic Policy Gradients [J]. Journal of System Simulation, 2025, 37(4): 875-881.
[3]	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.
[4]	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.
[5]	Jin Xu, Mo Yuanbin. Multi-strategy Hybrid Mountain Gazelle Optimizer for Robot Path Planning [J]. Journal of System Simulation, 2025, 37(3): 803-821.
[6]	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.
[7]	Qi Bensheng, Li Yan, Miao Hongxia, Chen Jialin, Li Chenglin. Research on Path Planning Method for Autonomous Underwater Vehicles Based on Improved Informed RRT [J]. Journal of System Simulation, 2025, 37(1): 245-256.
[8]	Xu Jianmin, Song Lei, Deng Dongdong, Chen Yaoruo, Yang Wei. Path Planning of Mobile Robot Based on the Integration of Multi-scale A* and Optimized DWA Algorithm [J]. Journal of System Simulation, 2025, 37(1): 257-270.
[9]	Wang Qiwei, Zhang Qi, Yang Shuo, Peng Yong. Design of Robust Behavior Tree Control Architecture for Agents in Dynamic Task Environment [J]. Journal of System Simulation, 2025, 37(1): 54-65.
[10]	Yin Anlin, Zhang Zhuhong. UAV Path Planning in Complex Environments and Its Improved Artificial Rabbits Optimization Algorithm [J]. Journal of System Simulation, 2025, 37(1): 79-94.
[11]	Wang Yuelong, Wang Songyan, Chao Tao. Multi-step Information Aided Q-learning Path Planning Algorithm [J]. Journal of System Simulation, 2024, 36(9): 2137-2148.
[12]	Huo Hanlin, Zou Xiangjun, Chen Yan, Zhou Xinzhao, Chen Mingyou, Li Chengen, Pan Yaoqiang, Tang Yunchao. Visual Robot Obstacle Avoidance Planning and Simulation Using Mapped Point Clouds [J]. Journal of System Simulation, 2024, 36(9): 2149-2158.
[13]	Ji Peng, Zhang Xinyuan, Gao Shuaixuan, Wei Shuorang. Path Planning Based on Improved A* and Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(9): 2171-2180.
[14]	Sun Haijie, San Hongjun, Xiao Le, Yao Dexin, Chen Jiupeng, Yang Xiaoyuan. An Improved Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2024, 36(9): 2193-2207.
[15]	Liu Jialun, Yang Fan, Xie Lingli, Li Shijie, Wang Tengfei. Research on Virtual Simulation Testing Technology for Intelligent Navigation Collision Avoidance Decision-making and Planning [J]. Journal of System Simulation, 2024, 36(8): 1780-1789.