基于冲突优先级变次优因子的EECBS多机器人路径规划

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

摘要/Abstract

摘要：

在多机器人路径规划（multi robot path planning，MRPP）过程中，最优路径之间无法规避的关键冲突对路径求解效率具有较大影响。为解决这一问题，提出一种基于冲突优先级变次优因子的多机器人路径规划方法。在融合显式估计的冲突搜索（explicit estimation conflict-based search，EECBS）算法下层执行路径搜索；在EECBS算法框架的上层对冲突优先级进行判断，并自适应增加关键冲突机器人的次优因子；通过分析关键冲突周围邻域的障碍物分布影响路径节点自由度情况，进一步调整关键冲突机器人的次优因子。在多个标准地图下的实验结果表明，相较于EECBS算法，本文方法的求解时间改善了8.35%~49.14%，上层冲突节点的二叉约束树（constraint tree，CT）拓展量改善了3.79%~55.22%，验证了本文方法的有效性。

关键词: 多机器人路径规划, 自适应次优因子, 冲突优先级, 约束树, 路径自由度

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

中图分类号:

TP242

闫星宇,王妮娅,毛剑琳等 . 基于冲突优先级变次优因子的EECBS多机器人路径规划[J]. 系统仿真学报, 2024, 36(11): 2662-2673.

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

图/表 19

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

图10

图11

图12

表2

表3

表4

表5

图13

图14

参考文献 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