一种含链式工作方式的多机器人协作路径规划算法

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

摘要/Abstract

摘要：

为解决多机器人具有共同目标点的应用场景下，传统的MAPF算法会导致大量的重复路径从而造成非必要能量损耗的问题，提出了一种具有牵引者的多机器人链式工作方式，将具有共同目标点的机器人划分进一个子组进行多机器人协作路径规划，并给出一种具有牵引者的协作动态优先级安全间隔路径规划(cooperative dynamic priority SIPP with tractor，Co-DPtSIPP)算法。利用多边形费马点原理等方法获取各协作组机器人的串接区域；在考虑采集机器人和牵引机器人串接顺序的情况下进行分段路径规划；在各组采集机器人挂架牵引机器人后，由牵引机器人带动它们以链式方式前行；将牵引机器人的后段路径节点经过时间步调整后填充进各采集机器人的路径当中，以避免牵引机器人在拖动多个采集机器人移动过程中与其他机器人碰撞。实验结果表明：Co-DPtSIPP算法在路径总长度上减少10%~13%，有效降低了机器人能耗。

关键词: 多机器人协作, 路径规划, 安全间隔, 采集机器人, 牵引机器人, 串接区域

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

中图分类号:

TP242

贺志刚,李大焱,王妮娅等 . 一种含链式工作方式的多机器人协作路径规划算法[J]. 系统仿真学报, 2025, 37(4): 953-967.

He Zhigang,Li Dayan,Wang Niya,et al . A Multi-robot Collaborative Path Planning Algorithm with Chain Working Mode[J]. Journal of System Simulation, 2025, 37(4): 953-967.

图/表 15

图1

图2

图3

图4

图5

图6

图7

表1

30×83仓储地图上Wd-SIPP和Co-DPtSIPP算法的路径方案质量对比

机器人数量	$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

表1

表2

100×100仓储地图上Wd-SIPP和Co-DPtSIPP算法的路径方案质量对比

机器人数量	$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

表2

图8

图9

表3

30×83仓储地图上Co-DPtSIPP和Co-DPtSIPP*算法获得的路径方案质量对比

机器人数量	$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

表3

表4

100×100仓储地图上Co-DPtSIPP和Co-DPtSIPP*算法获得的路径方案质量对比

机器人数量	$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

表4

图10

图11

参考文献 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]	喻蝶, 鲍柏仲, 司言, 段暕, 詹小斌, 史铁林. 基于搜索步优化A*算法的移动机器人路径规划[J]. 系统仿真学报, 2025, 37(4): 1041-1050.
[2]	张森, 代强强. 改进型深度确定性策略梯度的无人机路径规划[J]. 系统仿真学报, 2025, 37(4): 875-881.
[3]	杨超, 郑瑞群, 李圳, 张鸿薇, 唐燕群, 李东泽. 面向无人机辅助车联网的并行任务传输与处理优化策略[J]. 系统仿真学报, 2025, 37(3): 635-645.
[4]	林桂娟, 李子涵, 王宇. 基于全局关键点提取的改进A*算法全局路径规划研究[J]. 系统仿真学报, 2025, 37(3): 667-678.
[5]	白宇鑫, 陈振亚, 石瑞涛, 苏蔚涛, 马卓强, 杨尚进. 基于改进哈里斯鹰算法的机器人路径规划研究[J]. 系统仿真学报, 2025, 37(3): 742-752.
[6]	金煦, 莫愿斌. 多策略混合山地瞪羚优化器在机器人路径规划问题中的应用[J]. 系统仿真学报, 2025, 37(3): 803-821.
[7]	李炯逸, 李强, 张新闻, Htet Zin Myo, 蔡永斌. 移动机器人用改进的双向A*二次路径规划算法[J]. 系统仿真学报, 2025, 37(2): 498-507.
[8]	齐本胜, 李岩, 苗红霞, 陈家林, 李成林. 基于改进启发式RRT的AUV路径规划[J]. 系统仿真学报, 2025, 37(1): 245-256.
[9]	许建民, 宋雷, 邓冬冬, 陈尧箬, 杨炜. 基于多尺度A*与优化DWA算法融合的移动机器人路径规划[J]. 系统仿真学报, 2025, 37(1): 257-270.
[10]	王琪玮, 张琪, 杨硕, 彭勇. 动态任务环境下智能体健壮行为树控制架构设计[J]. 系统仿真学报, 2025, 37(1): 54-65.
[11]	尹安琳, 张著洪. 复杂环境下无人机路径规划及其改进型人工兔优化[J]. 系统仿真学报, 2025, 37(1): 79-94.
[12]	王越龙, 王松艳, 晁涛. 基于多步信息辅助的Q-learning路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2137-2148.
[13]	霍韩淋, 邹湘军, 陈燕, 周馨曌, 陈明猷, 李承恩, 潘耀强, 唐昀超. 基于视觉机器人障碍点云映射避障规划及仿真[J]. 系统仿真学报, 2024, 36(9): 2149-2158.
[14]	姬鹏, 张新元, 高帅轩, 魏铄让. 融合改进A*算法与动态窗口法的路径规划研究[J]. 系统仿真学报, 2024, 36(9): 2171-2180.
[15]	孙海杰, 伞红军, 肖乐, 姚得鑫, 陈久朋, 杨晓园. 一种改进的移动机器人路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2193-2207.