基于改进A*算法的AGV智能泊车算法①

张 原， 陈宇轩， 魏璐璐

1(西北工业大学 电子信息学院，西安 710072)

2(西安市铁一中学，西安710054)

引言

随着机器人产业的迅猛发展， 国内的一些企业也在积极开发AGV业务. 在2016年底第三届世界互联网大会期间， 针对车位紧张、停车难的问题， 海康威视AGV智能泊车系统提出全新的停车体验， 通过AGV智能泊车， 停车数量增加40%以上， 而且运营期间， 智能泊车AGV根据电量阈值和任务紧密程度自主进行充电任务， 不需要认为干预， 保证停车场的正常运营，大大缩减了用户停车、取车时间[1-4].

海康威视AGV采用视觉和惯性双导航技术实现自主定位， 定位精度误差小于5 mm； 采用4组舵轮差速驱动， 支持前进、后退、平移、旋转等运动控制， 运动过程平滑柔顺； 激光雷达监测蔽障， 前/后急停按钮安全防护， 实现安全可靠的运动控制； 可完成各类汽车的升举、搬运、旋转、下放. 该方案的实施， 用户只需将车辆放置在指定位置， 出入库任务交由AGV完成， 省去用户的停车时间以及节约取车等待时间.

目前各类停车场智能泊车算法只是针对单任务泊车提出解决方案， 这种情况过于理想化， 对错综复杂的大型停车场来说， 存在着多个出入库任务同时进行的情况， 本文在海康威视AGV智能机器人的基础上， 旨在解决多个AGV同时工作的情况， 提出新的解决方案: 本设计在A*算法的基础上， 将等待时间加入启发函数， 提出三维A*算法以解决停车场的智能泊车[5]. 在该停车场管理系统， 客户进入停车场不需人工停车， 入库时只需将车停到入口位置并发出入库指令， 入库停车任务交由AGV完成， 并且在停车场内部设有自动泊车引导系统， 采用算法规划出到达指定车位的最优路径， 将车送入预留车位， 进而节省车主寻找有效泊车位的时间； 客户在出库时， 发出出库任务指令， 系统收到指令在最短时间内规划出最优出库路线， AGV将车送至出口， 完成出库任务[6-8].

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

停车场环境的建模是建立一个便于AGV进行路径规划和使用的环境模型， 以实现AGV对出入口、障碍物、车位以及通道等标识的识别， 便于AGV控制器存储、处理、更新和使用， 有效的规划出入库合理的路径. 环境模型如图1所示， 以左下角为原点， 每个栅格代表一个单位， 地图中P表示车位， ×表示障碍物(B)， 右面*表示入口 (I)， 左面*表示出口 (E)， 地图中存在唯一的出入口， 白色表示行车道路(X)， 每个车位都与行车道路(X)相邻， 每个车位(P)只能停一辆车[9，10].

规划出车辆出入库的最优轨迹， 记录在白色的栅格上， 在地图上存储AGV运载车辆的允许轨迹， 和障碍等相关信息， AGV的轨迹被分解为单个的移动， 每秒移动一个单位， 单个的移动轨迹被记录在每个栅格上， 每个栅格上的移动信息规定了AGV在这个栅格的移动方向(前、后、左、右移动).

图1 停车场环境建模

图2 AGV移动方向

2 停车算法设计

本算法主要分为两部分， 第一部分是车位预处理，第二部分是路径规划算法.

预处理车位分配预处理， 预处理中忽略了AGV的影响， 只从车位和汽车信息来计算出初步方案， 提前为每辆车计算好预留车位数， 入库时通过预留车位数选择合理车位， 相比安排具体车位， 这种方式能够提高车位的利用率和停车场的效率. 通过这种预处理方式将原本的三维数据降低至二维， 大大加快了数据的处理速度， 从而可以得到较优的全局解.

2.1 车位预处理

总距离越长的库， AGV处理时的功耗和时间代价相应也越较高， 因此提高总距离较短车库的使用率有利于降低总体代价. 车位预处理的目的是在车入库选择时， 为后面的待入库车辆预留数个更优的车位[11]， 以节省AGV载车能耗以及提升整个停车系统的效率. 车位预处理采用链表的存储方式处理， 具体的步骤如下:

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

根据公式(1)计算每辆车的优先级系数，

其中，W是车重量，是待入库车的平均重量， 是T车的停车时间， 是待入库车的平均停车时间，α、β是比重系数，P是该辆车的优先级.

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

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

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

A*算法的基本思想是:

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

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

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

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

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

由于建模的AGV只有前后左右四个方向， 所以在遍历当前节点的临近节点时， 只需遍历当前节点上下左右的四个临近节点， 若存在停车路径， A*算法通过父指针由目标节点回到初始节点完成路径规划.

2.3 三维A*算法的路径优化

2.3.1 可达点判断

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

2.3.2 启发函数的改进

增加了栅格是否可达的判断之后， 彻底解决了碰撞和相遇的冲突， 但在复杂的停车场内， 出入库任务和AGV返回任务同时进行的几率很大， 最终导致路径规划并不是最优路径甚至规划失败. 如图4所示， 假设停车场内同时进行1号AGV到P6车位入库以及2号AGV返回到入口待命的任务， 采用A*算法规划出的两条路径之间存在一大段的重叠， 根据可达点的判断，如果规划出可用路径， 其中一条路径必须“躲避”一个栅格才能成功规划出路径， 但是这种做法会增加路径搜索长度， 对于AGV较多的大型停车场， 路径规划的运算时间也会急剧上升.

图3 可达点判断流程图

图4 A*算法路径规划

本文对启发函数进行改进， 在曼哈顿函数的基础上， 修改在Y轴的比例系数， 使得在路径规划的时候，优先选择在Y轴方向的栅格， 改进后的启发函数如式(3):

其中，θ＞1，θ为 Y 轴的比例系数， 规划路径时， 优先搜索Y轴方向的空闲栅格， 可以在一定程度上有效的减少路径重叠， 避免增加路径长度的代价， 加快了路径搜索的同时也更容易获得更优路径， 改进后的1号AGV和2号AGV的路径如图5所示， 选择可达点时， 优先选择在Y轴方向的栅格有效的减少了路径重叠的发生， 同时减少了运算时间， 获得优化路径.

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

2.3.3 三维最优路径求解

改进后的启发式函数虽然在一定程度上避免了路径重叠的问题， 但是在对于多AGV的大型停车场来说， 运动错综复杂， 上述方法不足以完全消除路径重叠和路径过长甚至规划失败， 为了保证停车场的正常运作， 在改进启发函数的基础上， 构建三维 A*算法， 本文采用任务延时机制， 路径规划时， 遇到重叠， 通过任务延时， 增加等待时间这一维度， 进一步判断路径代价，进而规划出最优路径.

三维A*算法和传统A*算法相比关键因素在于增加了时间因素， 将等待时间加入启发函数， 综合路径距离和等待时间两个因素进而规划出入库和出库任务的最佳路径， 以提高错综复杂的大型停车场的运营效率.

执行路径规划任务时， 设置任务延时初始值为0，定义代价向量Cost(n)和最小代价向量minCost(n)， 代价向量Cost(n)是AGV从初始栅格到终点的代价， 其中包括等待时间代价W(n)和行程代价D(n)， 最小路径代价定义为最新路径规划的代价和上次计算路径代价之间的差值. 在AGV执行出入库任务的过程中， 对周围的点进行可达判断， 调用三维A*算法规划路径， 若不可达， 否则延时一个时间单位， 重新进行规划， 若规划出可达路径， 计算路径代价和最小路径代价， 暂存在Cost(n)和minCost(n)， 延时一个时间单位， 再次调用三维 A*算法规划路径， 每次迭代记录最小路径代价， 直至时间延时代价大于最小路径代价， 终止循环， 返回最优路径.则Cost(n)可以通过以下函数计算:

算法流程图如图6所示.

图6 延时最优路径流程图

三维A*算法算法将等待时间加入最优路径的判断条件， 仅通过一个任务延时变量就优化了路径， 算法简单利于实现， 对停车场的运营效率的提升具有较大实际意义.

3 算法验证仿真

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

采用改进后的三维A*算法对存在多个出入库任务的情景进行仿真， 以验证算法的可行性.

图7为停车场在某一时刻的使用状况， 停车场剩余8个车位空闲， 其余车位被占用， 图中红色代表车位已被占用. 车辆到达停车场入口的时间服从泊松分布，短时间内有4辆车顺序进入停车场待进入停车场车位，并有P1、P8两个车位的2辆车发出出库命令. 根据车位预处理算法， 选取车位P3、P4、P9作为3辆车的待入库车位， 采用顺序执行和三维A*算法分别对6辆车的出入库进行路径规划， AGV的路径距离和执行任务时间段如表1所示， 其中s表示单位长度， t表示单位时间.

图7 当前停车场状态

表1 路径长度和消耗时间数据

由表1可知， 任务顺序执行任务的路径距离为37 s， 消耗的总时间为 37 t； 三维 A*算法完成 6辆车入出库任务的路径距离为37 s， 消耗总时间为12 t， 三维A*算法可完成停车场的智能泊车过程. 相对于按照顺序依次执行任务， 虽然总的路径长度不变或者可能会在一定程度上增加路径长度， 但是整个任务执行消耗时间大大减少， 这种方案更能满足用户的实际需要， 提高停车场的运营效率.

3.2 三维A*算法效率分析

泊车行为是由人、车和泊车位有机组成， 传统停车场的运营效率的属性主要包括入口至泊车的行驶距离、时间以及泊车位至用户目的地的步行距离和时间(用户需步行往返这个距离进行放车和取车)， 而第一个属性主要取决于驾驶员的驾车技术和侧方停车技术，所需时间因人而异， 如果驾驶技术不娴熟， 在多任务同时进行的停车场内， 事故发生的可能性极大， 造车不必要的损失， 而基于AGV的智能停车场入出库的任务交由AGV完成， 三维A*算法存在可达点的判断以及规划出的最优路径， 不仅避免了事故的发生， 而且省去了用户停车和返回时间； 第二个属性， 由于用户不同， 假设用户的目的地都为出口处， 而AGV停车场用户不需到达泊车位， 只需在出口处更短的时间等待， 即可提车使用， 大大提高停车场的运营效率.

三维A*算法的停车场管理效率主要取决于启发函数里θ值的选择， 针对不同的θ值， 针对图7模型停车场， 在处理一定数量车辆的入出库任务进行仿真， 与传统停车场的效率进行对比， 结果如表2所示.

表2 AGV智能停车场和传统停车场效率对比(单位: t)

表2中Cin表示仿真入库任务的车辆数量，Cout表示仿真出库任务的车辆数量，Tin表示处理入库任务完成所需时间，Tout表示出库任务完成所需时间. 从表中可以看出， 无论比例系数θ取值多大， AGV智能停车场的效率都明显高于传统停车场， 但是θ并不是越大越好，θ具体的取值根据停车场的实际布局情况而定.

4 结束语

本文在A*算法的基础上， 提出了改进的三维A*路径规划算法， 通过仿真验证了智能泊车算法的合理性和可行性， 算法可满足智能停车场的正常运营， 且系统可预留出最优车位， 规划出出入库的最优路径， 该问题的研究不仅避免了客户对于车位选择的盲目性，而且省去了停车时间以及节约了取车的等待时间， 有效的降低了停车场的运营成本， 并提高了停车场的运营效率智能化程度， 使得停车场内部管理更加规范化、有序化， 尤其对于车位较多的大型停场管理具有重要的实际意义.