EECBS Multi-robot Path Planning Based on Variable Suboptimal Factors of Prioritizing Conflicts

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

Abstract

Abstract:

In the process of multi-robot path planning (MRPP), the unavoidable key conflicts between the optimal paths have a significant impact on the efficiency of path solving. To address this issue, an MRPP method based on variable suboptimal factors of prioritizing conflicts (PC) was proposed. Path search was performed at the lower layer of the explicit estimation conflict-based search (EECBS) algorithm; in the upper layer of the EECBS algorithm framework, the PC was determined, and the suboptimal factor of the robot with key conflicts was adaptively increased; by analyzing the distribution of obstacles in the surrounding neighborhoods of key conflicts, the degree of freedom of path nodes was affected, and the suboptimal factor of the robot with key conflicts could be further adjusted. The results under multiple standard maps indicate that compared to the EECBS algorithm, the algorithm proposed in this paper has shortened the solving time by 8.35%~49.14%, and the expansion of the binary constraint tree (CT) of the upper conflict nodes has improved by 3.79%~55.22%, verifying the effectiveness of the proposed algorithm.

Key words: multi robot path planning(MRPP), adaptive suboptimal factor, prioritizing conflicts, constraint tree (CT), degrees of freedom in pathways

CLC Number:

TP242

Yan Xingyu, Wang Niya, Mao Jianlin, He Zhigang, Li Dayan. EECBS Multi-robot Path Planning Based on Variable Suboptimal Factors of Prioritizing Conflicts[J]. Journal of System Simulation, 2024, 36(11): 2662-2673.

Figures/Tables 19

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Table 1

Fig. 10

Fig. 11

Fig. 12

Table 2

Table 3

Table 4

Table 5

Fig. 13

Fig. 14

References 13

1	Stern Roni, Sturtevant Nathan, Felner Ariel, et al. Multi-agent Pathfinding: Definitions, Variants, and Benchmarks[C]//Proceedings of the Twelfth International Symposium on Combinatorial Search (SoCS 2019). Palo Alto: AAAI Press, 2019: 151-158.
2	Lin Guichao, Zhu Lixue, Li Jinhui, et al. Collision-free Path Planning for a Guava-harvesting Robot Based on Recurrent Deep Reinforcement Learning[J]. Computers and Electronics in Agriculture, 2021, 188: 106350.
3	张凯翔, 毛剑琳, 向凤红, 等. 基于讨价还价博弈机制的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.
4	宣志玮, 毛剑琳, 张凯翔. 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.
5	Sharon Guni, Stern Roni, Felner Ariel, et al. Conflict-based Search for Optimal Multi-agent Pathfinding[J]. Artificial Intelligence, 2015, 219: 40-66.
6	乔乔, 王艳, 纪志成. 基于冲突搜索算法的多机器人路径规划[J]. 系统仿真学报, 2022, 34(12): 2659-2669.
	Qiao Qiao, Wang Yan, Ji Zhicheng. Multi-robot Path Planning Based on CBS Algorithm[J]. Journal of System Simulation, 2022, 34(12): 2659-2669.
7	Dergachev Stepan, Yakovlev Konstantin. Distributed Multi-agent Navigation Based on Reciprocal Collision Avoidance and Locally Confined Multi-agent Path Finding[C]//2021 IEEE 17th International Conference on Automation Science and Engineering (CASE). Piscataway: IEEE, 2021: 1489-1494.
8	Zhang Han, Yao Mingze, Liu Ziang, et al. A Hierarchical Approach to Multi-agent Path Finding[C]//Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS2021)209. Palo Alto: AAAI Press, 2021: 209-211.
9	Boyarski Eli, Felner Ariel, Stern Roni, et al. ICBS: The Improved Conflict-based Search Algorithm for Multi-agent Pathfinding[C]//Proceedings of the Eighth International Symposium on Combinatorial Search (SoCS-2015). Palo Alto: AAAI Press, 2015: 223-225.
10	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 Seventh Annual Symposium on Combinatorial Search (SoCS 2014). Palo Alto: AAAI Press, 2014: 19-27.
11	Li Jiaoyang, Harabor Daniel, Stuckey Peter J, et al. Disjoint Splitting for Multi-agent Path Finding with Conflict-based Search[C]//Proceedings of the Twenty-ninth International Conference on Automated Planning and Scheduling (ICAPS 2019). Palo Alto: AAAI Press, 2019: 279-283.
12	Li Jiaoyang, Ruml Wheeler, Koenig S. EECBS: A Bounded-suboptimal Search for Multi-agent Path Finding[C]//The Thirty-fifth AAAI Conference on Artificial Intelligence (AAAI-21). Palo Alto: AAAI Press, 2021: 12353-12362.
13	Li Jiaoyang, Felner Ariel, Boyarski Eli, et al. Improved Heuristics for Multi-agent Path Finding with Conflict-based Search[C]//Proceedings of the Twenty-eighth International Joint Conference on Artificial Intelligence (IJCAI-19). California: IJCAI, 2019: 442-449.

算法	时间	CT拓展量	代价值
EECBS(w=1.10)	2.891	2 433	62
EECBS(w=1.15)	1.430	1 341	66
EECBS(w=1.20)	0.706	594	68
EECBS-PCW(w=1.10)	1.238	1 209	62

机器人数量	算法类型
机器人数量	EECBS (w=1.2)	EECBS (w=1.3)	EECBS-PCW (w=1.2)	EECBS-PCW (w=1.3)
30	2 132.65	2 133.35	2 132.65	2 133.35
40	2 902.00	2 908.80	2 901.95	2 908.30
50	3 674.55	3 682.60	3 674.65	3 682.25
60	4 501.75	4 523.10	4 502.30	4 522.75
70	5 360.10	5 389.70	5 358.35	5 390.10
80	6 179.80	6 247.45	6 181.65	6 245.60
90	—	7 122.35	7 032.85	7 119.00
100	—	8 031.05	—	8 019.45

机器人数量	算法类型
机器人数量	EECBS(w=1.02)	EECBS(w=1.03)	EECBS(w=1.04)	EECBS-PCW (w=1.02)	EECBS-PCW (w=1.03)
20	501.70	501.70	501.80	501.60	502.40
30	740.70	741.25	741.70	740.65	741.30
40	985.45	989.25	989.30	985.40	988.50
50	1 257.45	1 259.70	1 262.70	1 257.55	1 257.95
60	1 509.90	1 521.45	1 523.60	1 515.45	1 521.15
70	1 773.05	1 783.80	1 782.65	1 770.15	1 781.10
80	—	2 051.85	2 061.70	2 038.90	2 049.55
90	—	2 293.60	2 290.85	2 275.30	2 293.55

机器人数量	算法类型
机器人数量	EECBS (w=1.2)	EECBS (w=1.3)	EECBS-PCW (w=1.2)	EECBS-PCW (w=1.3)
30	4.05	3.50	4.05	3.50
40	7.70	6.10	7.60	6.10
50	11.50	9.00	11.40	9.00
60	17.75	13.00	17.55	13.00
70	27.45	17.80	26.60	15.44
80	63.55	25.30	43.75	25.05
90	—	36.40	86.70	36.80
100	—	53.70	—	49.70

机器人数量	算法类型
机器人数量	EECBS(w=1.02)	EECBS(w=1.03)	EECBS(w=1.04)	EECBS-PCW (w=1.02)	EECBS-PCW (w=1.03)
20	3.10	2.60	2.20	2.40	2.25
30	8.95	5.90	6.00	6.00	5.60
40	16.30	14.30	13.35	11.55	11.40
50	37.20	17.20	15.90	16.70	17.25
60	133.05	46.45	23.45	22.25	22.90
70	122.75	75.15	48.40	57.95	43.40
80	—	125.60	75.80	104.85	76.70
90	—	407.35	164.95	167.25	131.55