考虑冲突规避的自动化码头多AGV路径规划

doi:10.3778/j.issn.1002-8331.2206-0042

摘要/Abstract

摘要： 针对自动化码头动态作业环境中多自动导引车的路径规划问题，提出一种结合冲突规避的加权实时A*算法。考虑算法收敛速度，为实时A*添加使得收敛效果最优的权重系数，以加快行驶路径收敛于目标点；在算法搜索过程中使用时空坐标记录各AGV位置以实现路径信息共享，在此基础上结合二叉树原理对多AGV之间的冲突进行规避；通过算例验证算法的有效性，并将结果与普通A*进行综合分析与比较。结果表明该方法能有效进行多AGV动态冲突的规避，并且计算时间方面表现的效果更优。

关键词: 自动导引车, 路径规划, 加权实时A*算法, 冲突规避

Abstract: Aiming at the problem of multi-AGVs path planning in dynamic operation automatic terminal, a weighted real-time A* algorithm combined with conflict avoidance is proposed. Firstly, the convergence speed of the algorithm is considered, and the weight coefficient that makes the convergence effect optimal is added to the real-time A* to speed up the convergence of the driving path to the target point. Secondly, the space-time coordinates are used to record the location of each AGV to realize path information sharing in the process of algorithm search. On this basis, combined with the principle of binary tree, the conflicts between multi-AGVs are avoided. Finally, an example is given to verify the effectiveness of the algorithm, and the results are comprehensively analyzed and compared with the ordinary A*. Simulation results show that this method can effectively avoid multi-AGVs dynamic conflicts, and the effect of computing time is better.

Key words: automated guided vehicles, path planning, weighted real-time A*, conflict avoidance

张其娇, 丁一, 秦涛. 考虑冲突规避的自动化码头多AGV路径规划[J]. 计算机工程与应用, 2023, 59(18): 301-308.

ZHANG Qijiao, DING Yi, QIN Tao. Multi-AGVs Path Planning of Automated Terminal Considering Conflict Avoidance[J]. Computer Engineering and Applications, 2023, 59(18): 301-308.

参考文献

[1] 孙毛毛，匡兵.基于时间窗的AGV动态避碰路径规划方法[J].计算机应用研究，2022，39（1）：54-58.
SUN M M，KUANG B.Path planning method for AGV dynamic collision avoidance based on time window[J].Application Research of Computers，2022，39（1）：54-58.
[2] 王晓军，王博，杨春霞，等.紧致密集Auto Store系统AGV路径规划与避碰策略[J].计算机工程与应用，2021，57（15）：259-270.
WANG X J，WANG B，YANG C X，et al.AGV path planning and collision avoidance strategy for compact and dense auto store system[J].Computer Engineering and Applications，2021，57（15）：259-270.
[3] ZHONG M，YANG Y，DESSOUKY Y，et al.Multi-AGV scheduling for conflict-free path planning in automated container terminals[J].Computers & Industrial Engineering，2020，142（4）：106371.
[4] MURAKAMI K.Time-space network model and MILP formulation of the conflict-free routing problem of a capacitated AGV system[J].Computers & Industrial Engineering，2020，141（3）：106270.
[5] 杨雅洁，苌道方，余芳.考虑AGV避碰的自动化码头多资源协同调度[J].计算机工程与应用，2020，56（6）：246-253.
YANG Y J，CHANG D F，YU F.Multi-resource coordinated scheduling of automated terminals considering AGV collision avoidance[J].Computer Engineering and Applications，2020，56（6）：246-253.
[6] 张新艳，邹亚圣.基于改进A*算法的自动导引车无碰撞路径规划[J].系统工程理论与实践，2021，41（1）：240-246.
ZHANG X Y，ZOU Y S.Conflicts free path planning of AGV based on improved A* algorithm[J].System Engineering-Theory & Practice，2021，41（1）：240-246.
[7] 杨周，刘海滨.基于改进蚁群与动态窗口法的AGV动态路径规划[J].计算机工程与应用，2022，58（6）：287-295.
YANG Z，LIU H B.AGV dynamic path planning based on improved ant colony algorithm and dynamic window approach[J].Computer Engineering and Applications，2022，58（6）：287-295.
[8] JIA F，REN C，CHEN Y，et al.A system control strategy of a conflict-free multi-AGV routing based on improved A* algorithm[C]//2017 24th International Conference on Mechatronics and Machine Vision in Practice（M2VIP）.Auckland，New Zealand：IEEE，2017：1-6.
[9] 宋宇，王志明.改进A星算法移动机器人路径规划[J].长春工业大学学报，2019，40（2）：138-141.
SONG Y，WANG Z M.Path planning simultation based on improved A star algorithm[J].Journal of Changchun University of Technology，2019，40（2）：138-141.
[10] 牟德君，初鹏祥.基于改进A*算法的仓储环境AGV路径规划[J].自动化与仪表，2022，37（4）：40-45.
MOU D J，CHU P X.AGV path planning for warehouse environment based on improved A* algorithm[J].Automation & Instrumentation，2022，37（4）：40-45.
[11] KORF R.Real-time heuristic search[J].Artificial Intelligence，1990，42（2/3）：189-211.
[12] BULITKO V，LEE G.Learning in real time search：a unifying framework[J].Artificial Intelligence Research，2006，25：119-157.
[13] KOENIG S，SUN X.Comparing real-time and incremental heuristic search for real-time situated agents[J].Autonomous Agents and Multi-Agent Systems，2009，18（3）：313-341.
[14] CSERNA B，BOGOCHOW M，CHAMBERS S，et al.Anytime versus real-time heuristic search for on-line planning[C]//Proceedings of Symposium on Combinatorial Search.Tarrytown，NY，USA：AAAI Press，2016：131-132.
[15] SIGURDSON D，BULITKO V，YEOH W，et al.Multi-agent pathfinding with real-time heuristic search[C]//2018 IEEE Conference on Computational Intelligence & Games，2018：1-8.
[16] WANG K，BOTEA A.Fast and memory-efficient multi-agent pathfinding[C]//Eighteenth International Conference on Automated Planning & Scheduling.Sydney Australia：AAAI Press，2008：380-387.
[17] LI J，FELNER A，BOYARSKI E，et al.Improved heuristics for multi-agent path finding with conflict-based search[C]//Twenty-Eighth International Joint Conference on Artificial Intelligence.New York：Association for Computing Machinery，2019：442-449.
[18] KOENIG S，LIKHACHEV M.Real-time adaptive A*[C]//Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems.New York：Association for Computing Machinery，2006：281-288.
[19] SLIVER D.Cooperative pathfinding[C]//Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference.California USA：AAAI Press，2005：117-122.