﻿ 基于改进A*算法的AGV智能泊车算法
 计算机系统应用  2019, Vol. 28 Issue (1): 216-221 PDF

1. 西北工业大学 电子信息学院，西安 710072;
2. 西安市铁一中学，西安710054

AGV Intelligent Parking Algorithm Based on Improved A* Algorithm
ZHANG Yuan1, CHEN Yu-Xuan2, WEI Lu-Lu1
1. School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710072, China;
2. Xi’an Tieyi Middle School, Xi’an 710054, China
Foundation item: Innovation and Venture Fund for Students in Northwestern Polytechnical University (Z2017150)
Abstract: With the development of society and the advancement of civilization, human beings are increasingly demanding the level of intelligence, convenience, and safety of vehicles. In view of the problem of less parking lot and difficult parking, the waiting time factor is added to the A* algorithm, and the waiting time is added to the number of heuristic functions, the distance of the comprehensive path and the waiting time are two factors to plan the best path for the tasks of parking into the lot and driving out of the lot, and a three-dimensional A* intelligent parking algorithm is designed. Under the structured environment, the optimal parking space is reserved according to the given parking lot map, the optimal path of the Automated Guided Vehicle (AGV) is planned for multiple simultaneous tasks, and the AGV vehicle is arranged to go to the designated parking space or to move out of the lot, with minimized waiting time of the customers to park or take the car, and making the total cost minimum, presenting a truly " Internet-enabled” smart parking experience.
Key words: three-dimensional A* algorithm     intelligent parking     optimal path     AGV     heuristic function

1 停车场环境和AGV模型建立

 图 1 停车场环境建模

 图 2 AGV移动方向

2 停车算法设计

2.1 车位预处理

1) 计算每个车位离出入口的总距离, 并进行降序排序.

 $P = \frac{{\alpha *\left( {{W^2}} \right)}}{{\bar W}} - {T_{\rm {in}}} - \frac{{\beta *\left( {{T^2}} \right)}}{{\bar T}}$ (1)

2) 建立任务队列, 若任务队列为空, 直接分配车位; 否则, 根据车的优先级排列任务队列, 依次输出预留车位.

2.2 二维A*算法的路径规划

A*是在Dijkstra的基础上一种启发式的局部优化算法, 所谓的"启发式", 就是对每一个搜索的位置进行评估, 也就对当前位置离目标的距离节点进行评估. A*算法是一种静态路网中求解最短路径的最有效的搜索方法[1214], 很好的应用在停车场存在固定障碍物的路径规划中, 启发的估价函数表示式(2).

 $f\left( n \right) = g\left( n \right) + h\left( n \right)$ (2)

A*算法的基本思想是:

(1)建立两个列表存放节点数据, 分别为open列表和close列表, 首先将源节点放入open列表;

(2)将f值最小的点作为当前节点, 并从open列表中删除, 添加到close列表;

(3)如果当前节点为终点节点, 则结束搜索;

(4)处理当前节点的所有临近节点: 若已经在open列表, 再次计算g值, 与之前的g值进行比较, 以判断是否更新父节点和g值; 若不在open列表中, 那么就添加到open列表, 若该节点为障碍物或者已经被添加至close列表, 此节点不予处理;

(5)如果open列表不为空, 转为步骤(2).

2.3 三维A*算法的路径优化 2.3.1 可达点判断

A*算法有效的解决了单个AGV工作的出入库路径规划的问题, 但是对于大型停车场存在多个AGV同时工作的情况, 就会出现同一栅格碰撞和时间维度上相遇的冲突, 导致停车场内不必要的损失. 为了实现合理规避同时工作的AGV并且具有最短的行程时间的路径, 解决时间冲突问题, 本文主要基于传统二维A*算法的算法思想, 实时对周围可达点进行判断, 若时间发生冲突时, 使该点不可达, 而选取其他周围临近点, 从而到达到指定车位, 完成出入库动作.

2.3.2 启发函数的改进

 图 3 可达点判断流程图

 图 4 A*算法路径规划

 $h\left( n \right) = \left| {{X_1} - {X_2}} \right| + \theta \left| {{Y_1} - {Y_2}} \right|$ (3)

 图 5 改进启发函数的路径规划

2.3.3 三维最优路径求解

 $Cost\left( n \right) = W\left( n \right) + D(n)$ (4)

 图 6 延时最优路径流程图

3 算法验证仿真 3.1 三维A*算法有效性的仿真

 图 7 当前停车场状态

3.2 三维A*算法效率分析

4 结束语

 [1] AGV智能泊车初探(一). AGV智能泊车初探(一). 智能机器人, 2017(1): 22-23. [2] 范秋秋. 基于物联网技术的城市停车诱导系统研究[硕士学位论文]. 淮南: 安徽理工大学, 2017. [3] 张席洲, 邱永涵. 基于RFID的停车诱导系统设计. 武汉理工大学学报(交通科学与工程版), 2011, 35(3): 484-487. DOI:10.3963/j.issn.1006-2823.2011.03.012 [4] 王淼弛. 基于A*算法的移动机器人路径规划[硕士学位论文]. 沈阳: 沈阳工业大学, 2017. [5] Frampton KD. Acoustic self-localization in a distributed sensor network. IEEE Sensors Journal, 2016, 6(1): 166-177. [6] 朱云虹, 袁一. 基于改进A*算法的最优路径搜索. 计算机技术与发展, 2018, 28(4): 55-59. DOI:10.3969/j.issn.1673-629X.2018.04.012 [7] 杨嘉华. 基于双向最短路径的大型停车场停车路径优化算法. 信息技术与信息化, 2016(9): 58-60. DOI:10.3969/j.issn.1672-9528.2016.09.011 [8] 李伟, 余森, 王伟. 基于时间最短路径的停车场车位引导算法. 自动化仪表, 2015, 36(8): 23-25. [9] 胡娟娟. 停车诱导系统关键技术研究[硕士学位论文].长春: 吉林大学, 2006. [10] 刘军. 基于ZigBee的智能停车场管理系统的设计与实现[硕士学位论文]. 哈尔滨: 哈尔滨工程大学, 2012. [11] 王殿君. 基于改进A*算法的室内移动机器人路径规划. 清华大学学报(自然科学版), 2012, 52(8): 1085-1089. [12] 彭红星, 解凤玲. 改进Dijkstra算法在停车诱导系统中的应用与仿真. 计算机应用, 2011, 31(S2): 63-66. [13] Comelli P, Ferragina P, Granieri M N, et al. Optical recognition of motor vehicle license plates. IEEE Transactions on Vehicular Technology, 1995, 44(4): 790-799. DOI:10.1109/25.467963 [14] 陈红伟. 公路不停车收费系统中的车辆识别. 仪器仪表与分析监测, 2002(1): 13-14. DOI:10.3969/j.issn.1002-3720.2002.01.004