Multi-robot Hierarchical Collaborative k-robust Path Planning for Path Interference

doi:10.16182/j.issn1004731x.joss.24-0229

Abstract

Abstract:

To plan collision-free paths for multiple robots in interference environments, based on the multi-robotk-robust path planning, this paper designed a multi-robot hierarchical collaborative k-robust path planning framework. In the priority optimization layer, in response to the starting predicament caused by the solution sequence, the multi-robot path solving sequence was determined based on the closure factor. In the multi-robot robust coordination layer, with the goal of improving solution efficiency, a safety interval was introduced as the basis for the design of k-robustness and collision-free avoidance. A collision-free path constraint for multiple robots in the sense of k-robustness was given. In the core solution layer, dynamic resistance factors were used to guide high priority robots to avoid the starting area of low priority robots during planning. The test results show that the proposed algorithm can effectively reduce the impact ofk-robust starting predicament with small path loss, and the success rate ofk-robust path solutions can be improved by more than 39% on average compared to existing advanced algorithms.

Key words: multi-robot system, path planning, robust planning, delay, interference

CLC Number:

TP242

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.

Figures/Tables 16

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Table 1

Table 2

Solution of IkR-SIPP in case of k=5

机器人	路径	具体方案
a₁	$π 1$	{(1,2), (2,2), (2,2), (2,2), (2,2), (2,2), (2,2), (2,2), (2,2), (2,2), (3,2), (4,2), (5,2), (6,2), (6,3), (6,4), (6,5), (6,6)}
a₂	$π 2$	{(8,3), (8,4), (8,5), (7,5)}
a₃	$π 3$	{(6,4), (7,4), (7,4), (7,4), (7,4), (7,4), (7,4), (8,4), (8,5), (8,6)}
a₄	$π 4$	{(6,1), (5,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,1), (4,2), (3,2), (2,2), (1,2), (1,1)}
a₅	$π 5$	{(6,3), (6,2), (5,2), (4,2), (3,2), (3,3), (3,4), (4,4), (4,5)}
a₆	$π 6$	{(2,5), (2,6), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,7), (2,6), (2,5), (2,4), (3,4), (3,3), (3,2), (4,2), (5,2), (5,1)}
a₇	$π 7$	{(1,4), (2,4), (2,4), (2,4), (2,4), (2,4), (2,5), (2,6), (3,6), (3,7)}
a₈	$π 8$	{(2,3), (2,3), (2,3), (2,3), (2,3), (2,3), (2,3), (2,3), (2,3), (2,3), (2,3), (2,4), (2,5), (2,6), (1,6)}

Table 2

Fig. 10

Fig. 11

Fig. 12

Fig. 13

Fig. 14

References 37

[1]	Li Changmin, Zhang Lu, Zhang Liang. A Route and Speed Optimization Model to Find Conflict-free Routes for Automated Guided Vehicles in Large Warehouses Based on Quick Response Code Technology[J]. Advanced Engineering Informatics, 2022, 52: 101604.
[2]	Okumura Keisuke, Machida Manao, Défago Xavier, et al. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding[J]. Artificial Intelligence, 2022, 310: 103752.
[3]	Wang Hanlin, Rubenstein M. Walk, Stop, Count, and Swap: Decentralized Multi-agent Path Finding with Theoretical Guarantees[J]. IEEE Robotics and Automation Letters, 2020, 5(2): 1119-1126.
[4]	Kudo Fumiya, Cai Kai. A TSP-based Online Algorithm for Multi-task Multi-agent Pickup and Delivery[J]. IEEE Robotics and Automation Letters, 2023, 8(9): 5910-5917.
[5]	Hu Kewei, Chen Zheng, Kang Hanwen, et al. 3D Vision Technologies for a Self-developed Structural External Crack Damage Recognition Robot[J]. Automation in Construction, 2024, 159: 105262.
[6]	Ratner D, Warmuth M. Finding a Shortest Solution for the N × N Extension of the 15-puzzle is Intractable[C]//Proceedings of the Fifth AAAI National Conference on Artificial Intelligence. Palo Alto: AAAI Press, 1986: 168-172.
[7]	Sharon G. Novel Search Techniques for Path Finding in Complex Environment[D]. Be'er Sheva: Ben-Gurion University of the Negev, 2015.
[8]	Ma Hang. Target Assignment and Path Planning for Navigation Tasks with Teams of Agents[D]. Los Angeles : University of Southern California, 2020.
[9]	Sharon Guni, Stern Roni, Felner Ariel, et al. Conflict-based Search for Optimal Multi-agent Pathfinding[J]. Artificial Intelligence, 2015, 219: 40-66.
[10]	张洪琳, 吴耀华, 胡金昌, 等. 一种基于改进冲突搜索的多机器人路径规划算法[J]. 控制与决策, 2023, 38(5): 1327-1335.
	Zhang Honglin, Wu Yaohua, Hu Jinchang, et al. A Multi-robot Path Finding Algorithm Based on Improved Conflict Search[J]. Control and Decision, 2023, 38(5): 1327-1335.
[11]	Boyarski Eli, Felner Ariel, Stern Roni, et al. ICBS: The Improved Conflict-based Search Algorithm for Multi-agent Pathfinding[C]//Proceedings of the International Symposium on Combinatorial Search: Palo Alto: AAAI Press, 2015: 223-225.
[12]	Barer Max, Sharon Guni, Stern Roni, et al. Suboptimal Variants of the Conflict-based Search Algorithm for the Multi-agent Pathfinding Problem[C]//Proceedings of the Twenty-first European Conference on Artificial Intelligence. NLD: IOS Press, 2014: 961-962.
[13]	Li Jiaoyang, Harabor Daniel, Stuckey Peter J, et al. Pairwise Symmetry Reasoning for Multi-agent Path Finding Search[J]. Artificial Intelligence, 2021, 301: 103574.
[14]	Erdmann M, Lozano-Pérez Tomás. On Multiple Moving Objects[J]. Algorithmica, 1987, 2(1): 477-521.
[15]	Silver David. Cooperative Pathfinding[C]//Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Palo Alto: AAAI Press, 2021: 117-122.
[16]	Phillips M, Likhachev M. SIPP: Safe Interval Path Planning for Dynamic Environments[C]//Proc.of the 2011 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2011: 5628-5635.
[17]	Yakovlev Konstantin, Andreychuk Anton, Stern Roni. Revisiting Bounded-suboptimal Safe Interval Path Planning[C]//Proceedings of the International Conference on Automated Planning and Scheduling. Palo Alto: AAAI Press, 2020: 300-304.
[18]	Chen Zhe, Alonso-Mora Javier, Bai Xiaoshan, et al. Integrated Task Assignment and Path Planning for Capacitated Multi-agent Pickup and Delivery[J]. IEEE Robotics and Automation Letters, 2021, 6(3): 5816-5823.
[19]	Ma Hang. Graph-based Multi-robot Path Finding and Planning[J]. Current Robotics Reports, 2022, 3(3): 77-84.
[20]	Tai Ruochen, Wang Jingchuan, Chen Weidong. A Prioritized Planning Algorithm of Trajectory Coordination Based on Time Windows for Multiple AGVs with Delay Disturbance[J]. Assembly Automation, 2019, 39(5): 753-768.
[21]	Atzmon Dor, Diei Amit, Rave Daniel. Multi-train Path Finding[C]//Proceedings of the International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2019: 125-129.
[22]	张丹露, 孙小勇, 傅顺, 等. 智能仓库中的多机器人协同路径规划方法[J]. 计算机集成制造系统, 2018, 24(2): 410-418.
	Zhang Danlu, Sun Xiaoyong, Fu Shun, et al. Cooperative Path Planning in Multi-robots for Intelligent Warehouse[J]. Computer Integrated Manufacturing Systems, 2018, 24(2): 410-418.
[23]	Nekvinda Michal, Barták Roman. Contingent Planning for Robust Multi-agent Path Finding[C]//2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI). Piscataway: IEEE, 2021: 487-492.
[24]	Semiz Fatih, Polat Faruk. Incremental Multi-agent Path Finding[J]. Future Generation Computer Systems, 2021, 116: 220-233.
[25]	Koenig S, Likhachev M. D*Lite[C]//Eighteenth National Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2002: 476-483.
[26]	曹其新, 黄先群, 朱笑笑, 等. 基于保留区域的分布式多机器人路径规划[J]. 华中科技大学学报(自然科学版), 2018, 46(12): 71-76.
	Cao Qixin, Huang Xianqun, Zhu Xiaoxiao, et al. Distributed Multi-robot Path Planning Based on Reserved Area[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2018, 46(12): 71-76.
[27]	唐昀超, 祁少军, 朱立学, 等. 移动机器人避障运动研究[英][J]. 系统仿真学报, 2024, 36(1): 1-26.
	Tang Yunchao, Qi Shaojun, Zhu Lixue, et al. Obstacle Avoidance Motion in Mobile Robotics[Eng.][J]. Journal of System Simulation, 2024, 36(1): 1-26.
[28]	Atzmon Dor, Stern Roni, Felner Ariel, et al. Robust Multi-agent Path Finding[C]//Proceedings of the International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2018: 1-9.
[29]	Goldenberg Meir, Felner Ariel, Stern R, et al. Enhanced Partial Expansion A*[J]. Journal of Artificial Intelligence Research, 2014, 50(1): 141-187.
[30]	Chen Zhe, Harabor Daniel D, Li Jiaoyang, et al. Symmetry Breaking for k-robust Multi-agent Path Finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2021: 12267-12274.
[31]	Atzmon Dor, Stern Roni, Felner Ariel, et al. Robust Multi-agent Path Finding and Executing[J]. Journal of Artificial Intelligence Research, 2020, 67: 549-579.
[32]	李昊楠, 毛剑琳, 张凯翔, 等. 一种基于安全区间的多机器人路径k鲁棒规划算法[J]. 仪器仪表学报, 2023, 44(10): 274-282.
	Li Haonan, Mao Jianlin, Zhang Kaixiang, et al. Multi-robot Path k Robust Planning Algorithm Based on Safe Interval[J]. Chinese Journal of Scientific Instrument, 2023, 44(10): 274-282.
[33]	张凯翔, 毛剑琳, 向凤红, 等. 基于讨价还价博弈机制的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.
[34]	Li Jiaoyang, Ruml W, Koenig S. EECBS: A Bounded-suboptimal Search for Multi-agent Path Finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence: AAAI Press, 2021: 12353-12362.
[35]	Stern Roni, Sturtevant Nathan, Felner Ariel, et al. Multi-agent Pathfinding: Definitions, Variants, and Benchmarks[C]//Proceedings of the International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2019: 151-158.
[36]	Standley T. Finding Optimal Solutions to Cooperative Pathfinding Problems[C]//Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2010: 173-178.
[37]	Zain Alabedeen Ali, Yakovlev Konstantin. Safe Interval Path Planning with Kinodynamic Constraints[C]//Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2023: 12330-12337.

k值	求解时间/ms					SoC/步
k值	kR-EPEA^*	kR-CBS	IkR-CBS	kR-SIPP	IkR-SIPP	kR-EPEA^*	kR-CBS	IkR-CBS	kR-SIPP	IkR-SIPP
0	32.53	35.25	32.51	1.92	1.96	49	49	49	52	51
1	50 273.51	49 744.77	864.16	2.02	2.03	55	55	55	60	60
2	NA	NA	59 105.80	2.09	2.28	NA	NA	63	74	78
3	NA	NA	NA	2.40	2.46	NA	NA	NA	103	88
4	NA	NA	NA	NA	2.34	NA	NA	NA	NA	98
5	NA	NA	NA	NA	2.62	NA	NA	NA	NA	108