基于改进冲突搜索的智能车库多AGV路径规划

doi:10.19562/j.chinasae.qcgc.2023.10.014

摘要/Abstract

摘要：

智能车库中多自主引导车（automated guided vehicle， AGV）的路径规划问题直接影响存取车的效率和安全性。针对智能车库中AGV的任务执行优先级问题，提出了基于改进冲突搜索的路径规划模型（improved conflict-based search with priority， iCBS-pri），该改进模型主要由任务分配（task allocation， TA）、单AGV路径规划（path planning， PP）、多AGV冲突检测与解决（conflict detection and resolution， CDAR）3个模块组成，TA模块将未分配任务分配给AGV，PP模块通过设置直线惩罚函数，减少路径的转弯次数对AGV运行时间的影响以提高AGV任务完成效率，CDAR模块包括冲突检测（conflict detection，CD）子模块和冲突解决（conflict resolution， CR）子模块，CR子模块针对CD子模块检测出的冲突类型，制定基于备用区域（spare zone， SZ）和旁路规划（bypass， BP）的冲突解决策略，以规划多AGV无冲突路线。仿真实验验证了典型场景下的该模型，结果表明：（1）PP模块所提改进A*相较于传统A*算法在路径长度和拐点数量分别减少8.82%和38.62%；（2）任务分配算法的分配成功率达到100%，任务一致性的概率达88.9%；（3）iCBS-pri算法在任务规划成功率方面比iCBS算法平均提升11.3%，算法平均运行时间提升5.93%，进一步提升了智能车库存取车效率。

关键词: 智能车库, 路径规划, 任务执行优先级, 自主引导车, 冲突

Abstract:

Path planning of multiple Automated Guided Vehicles （AGVs） in intelligent garage directly affects the efficiency and security of the vehicle. For the task execution priority of AGVs in RIG， the Improved Conflict-Based Search with priority （iCBS-pri） path planning model is proposed. The improved model is mainly composed of Task Allocation （TA）， single-AGV Path Planning （PP）， multi-AGV Conflict Detection and Resolution modules. The TA module allocates unassigned tasks to AGVs. The PP module improves the completion efficiency of AGV tasks by setting a linear penalty function to reduce the impact of the number of turns of the path on AGV running time. The CDAR module includes Conflict Detection （CD） submodule and Conflict Resolution （CR） submodule. The CR submodule develops conflict resolution policies based on Spare Zone （SZ） and Bypass planning （BP） for the conflict types detected by the CD submodule， so as to plan multi-AGV conflict-free routes. Simulation experiments verify the model under typical scenarios. The results show that：（1） Compared with the traditional A* algorithm， the improved A* proposed by the PP module reduces the path length and the number of inflection points by 8.82% and 38.62%， respectively；（2） The assignment success rate of the task allocation algorithm reaches 100%， with the task consistency probability reaching 88.9%；（3） Compared with the iCBS algorithm， the success rate of task planning of iCBS-pri algorithm is improved by 11.3% on average， with the average running time of the algorithm improved by 5.93%， which further improves the efficiency of RIG access vehicle.

Key words: intelligent garage, path planning, task execution priority, autonomous guide vehicle, conflict

任明辉,梁军,陈龙,张春,王云. 基于改进冲突搜索的智能车库多AGV路径规划[J]. 汽车工程, 2023, 45(10): 1933-1943.

Minghui Ren,Jun Liang,Long Chen,Chun Zhang,Yun Wang. Multi-AGV Path Planning for Intelligent Garage Based on Improved Conflict Search[J]. Automotive Engineering, 2023, 45(10): 1933-1943.

图/表 11

图1

图2

图3

图4

图5

图6

表1

任务分配算法实验结果"

$N$	$S t a / %$	$C t a / %$	$T t a / s$
2	100	100	0.074
4	100	100	0.102
6	100	100	0.303
8	100	100	0.846
10	100	100	1.259
12	100	99.2	1.904
14	100	96.8	2.445
16	100	93.8	3.787

表1

表2

路径规划算法实验结果"

性能指标

A*算法

本文改进

A*算法

路径长度减少率

拐点数量

减少率

L p p

113.93

103.88

8.82%

N t p p

5.93

3.64

38.62%

表2

图7

图8

表3

参考文献 17

1	CHEN G， HOU J， DONG J， et al. Multi-objective scheduling strategy with genetic algorithm and time-enhanced A* planning for autonomous parking robotics in high-density unmanned parking lots［J］. IEEE/ASME Transactions on Mechatronics， 2020， 26（3）： 1547-1557.
2	ZHANG J， LI Z， LI L， et al. A bi-level cooperative operation approach for AGV based automated valet parking［J］. Transportation Research Part C： Emerging Technologies， 2021， 128： 103140.
3	HU Y， DONG L， XU L. Multi-AGV scheduling and routing problem based on a three-stage decomposition method［J］. Mathematical Biosciences and Engineering， 2020， 17（5）： 5150-5172.
4	QU S， XU Z， LU F， et al. ITDP-Robot： design of an intelligent transport dispatch parking robot［J］. Smart City Application， 2019， 2（5）： 24-32.
5	STERN R. Multi-agent path finding-an overview［J］. Artificial Intelligence， 2019： 96-115.
6	LI J， RUML W， KOENIG S. Eecbs： a bounded-suboptimal search for multi-agent path finding［C］. Proceedings of the AAAI Conference on Artificial Intelligence （AAAI）， 2021： 12353-12362.
7	BARER M， SHARON G， STERN R， et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem［C］. Seventh Annual Symposium on Combinatorial Search， 2014.
8	BOYARSKI E， FELNER A， STERN R， et al. ICBS： improved conflict-based search algorithm for multi-agent pathfinding［C］. Twenty-Fourth International Joint Conference on Artificial Intelligence， 2015.
9	OKOSO A， OTAKI K， NISHI T. Multi-agent path finding with priority for cooperative automated valet parking［C］. 2019 IEEE Intelligent Transportation Systems Conference （ITSC）. IEEE， 2019： 2135-2140.
10	SHARON G， STERN R， FELNER A， et al. Conflict-based search for optimal multi-agent pathfinding［J］. Artificial Intelligence， 2015， 219： 40-66.
11	TSUBOI Y， KANAMORI R， YAMAMOTO T， et al. Analysis of parking lot choice behaviors by utilizing accounting data［J］. Journal of the Eastern Asia Society for Transportation Studies， 2015， 11： 523-536.
12	MA H， HARABOR D， STUCKEY P J， et al. Searching with consistent prioritization for multi-agent path finding［J］. Proceedings of the AAAI Conference on Artificial Intelligence， 2019， 33（1）： 7643-7650.
13	李鑫，廖凯文，陈薇，等.多自动导引车路径规划的时空冲突约束A*算法［J］.计算机集成制造系统，2021，27（11）：3219-3226.
	LI Xin， LIAO Kaiwen， CHEN Wei， et al. A* algorithm with spatial-temporal conflict constraints for path planning of multiple automatic guided vehicles ［J］. Computer Integrated Manufacturing Systems，2021，27（11）：3219-3226.
14	AI B， JIANG J， YU S， et al. Multi-agent path finding with heterogeneous edges and roundtrips［J］. Knowledge-Based Systems， 2021， 234： 107554.
15	ZHAO Y， LIU X， WU S， et al. Spare zone based hierarchical motion coordination for multi-AGV systems［J］. Simulation Modelling Practice and Theory， 2021， 109： 102294.
16	XU R， FENG H， LIU J， et al. Dynamic spare point application based coordination strategy for multi-AGV systems in a wip warehouse environment［J］. IEEE Access， 2022， 10： 80249-80263.
17	BOYRASKY E， FELNER A， SHARON G， et al. Don't split， try to work it out： bypassing conflicts in multi-agent pathfinding［C］. Proceedings of the International Conference on Automated Planning and Scheduling， 2015， 25： 47-51.

车位占有率	规划方法	平均运行时间/s
车位占有率	规划方法	2	4	6	8	10	12	14	16
30%	CBS	0.037	0.043	0.052	0.181	1.351	1.879	2.582
	CBS+SZ	0.039	0.045	0.049	0.163	1.293	1.781	2.373	3.278
	CBS+BP	0.054	0.073	0.125	0.576	1.502	2.502	3.815	5.512
	iCBS	0.057	0.081	0.143	0.527	1.397	2.137	3.368	4.953
	iCBS-pri	0.052	0.078	0.134	0.485	1.310	1.939	2.642	4.233
60%	CBS	0.035	0.046	0.051	0.185	1.390	1.852	2.574
	CBS+SZ	0.041	0.047	0.053	0.180	1.312	1.814	2.439	3.463
	CBS+BP	0.057	0.071	0.131	0.583	1.557	2.483	3.790	5.527
	iCBS	0.074	0.103	0.165	0.599	1.429	2.334	3.653	5.326
	iCBS-pri	0.068	0.094	0.154	0.584	1.374	2.298	3.550	5.227
90%	CBS	0.039	0.049	0.056	0.191	1.367	1.903	2.610
	CBS+SZ	0.049	0.053	0.061	0.193	1.403	1.964	2.633
	CBS+BP	0.054	0.073	0.125	0.576	1.502	2.502	3.815	5.512
	iCBS	0.089	0.117	0.203	0.667	1.627	2.703	3.973	5.697
	iCBS-pri	0.071	0.105	0.212	0.636	1.592	2.697	3.892	5.557

[1]	杨彪, 韦智文, 倪蓉蓉, 王海, 蔡英凤, 杨长春. 基于动作条件交互的高效行人过街意图预测[J]. 汽车工程, 2024, 46(1): 29-38.
[2]	胡满江,牟斌杰,杨泽宇,边有钢,秦晓辉,徐彪. 基于DBSCAN与二分法的混合A*路径规划方法[J]. 汽车工程, 2023, 45(3): 341-349.
[3]	胡杰,朱琪,陈锐鹏,张敏超,张志豪,刘昊岩. 引入必经点约束的智能汽车全局路径规划[J]. 汽车工程, 2023, 45(3): 350-360.
[4]	程腾,侯登超,张强,石琴,郭利港. 基于D-S证据理论的多模态结果级融合框架研究[J]. 汽车工程, 2023, 45(10): 1815-1823.
[5]	胡杰,朱令磊,陈瑞楠,钟鑫凯,徐文才,张敏超. 狭小车位平行泊车路径规划方法研究[J]. 汽车工程, 2022, 44(7): 1040-1048.
[6]	高强,陆洲,段晨东,徐婷. 汽车垂直泊车路径规划与路径跟踪研究[J]. 汽车工程, 2021, 43(7): 987-994.
[7]	张志勇,龙凯,杜荣华,黄彩霞. 自动驾驶汽车高速超车轨迹跟踪协调控制[J]. 汽车工程, 2021, 43(7): 995-1004.
[8]	张旭东,徐福康,邹渊,郭宁远,张宇. 融合TangentBug与Dubins曲线的智能轮式车辆局部路径规划算法[J]. 汽车工程, 2021, 43(6): 833-841.
[9]	李彩霞,卢少波,张博涵,吴文娟,陆嘉峰. 基于行人位置预测的人车转向避撞路径规划[J]. 汽车工程, 2021, 43(6): 877-884.
[10]	胡林,周登辉,黄晶,杜荣华,张新. 考虑信号灯和能耗的电动车最优路径规划[J]. 汽车工程, 2021, 43(5): 641-649.
[11]	张家旭,王晨,赵健. 基于改进人工势场法的汽车弯道超车路径规划与跟踪控制[J]. 汽车工程, 2021, 43(4): 546-552.
[12]	张家旭,王晨,郭崇,滕飞,李东燃. 基于自适应神经模糊推理系统的平行泊车路径规划[J]. 汽车工程, 2021, 43(3): 323-329.
[13]	陈吉清,翁楚滨,兰凤崇. 智能车辆换道潜在冲突分析与风险量化方法[J]. 汽车工程, 2021, 43(11): 1565-1576.
[14]	朱冰, 韩嘉懿, 赵健, 刘帅, 邓伟文. 基于安全场改进RRT^算法的智能汽车路径规划方法^[J]. 汽车工程, 2020, 42(9): 1145-1150.
[15]	熊莹, 毛雪松. 无人驾驶车通过高速公路闸口区的方法研究[J]. 汽车工程, 2020, 42(9): 1263-1269.