基于改进的A*算法集装箱码头自动导引小车路径规划研究*

曹 莹 陈沿伊 冯 睿

(武汉理工大学交通学院1) 武汉 430063) (武汉理工大学物流工程学院2) 武汉 430063)

0 引 言

提高港口通过能力有两种方法:①外延扩大，增加码头泊位数量，扩大堆场面积等，此方法不确定因素多，投入成本巨大，花费时间较长，短期内一般不予采用；②增加港口内涵，采取先进机械设备，加快港口的集疏运能力，智能化管理技术优化分工，加强协作关系，把船、车作业纳入规范，实行系统化管理.我国集装箱码头土地资源很难再扩大，一般多为优化集装箱码头装卸工艺流程来提高港口通过能力.根据港口企业统计，集装箱码头水平运输已成为集装箱装卸工艺中的瓶颈，且集装箱运输费用已成为集装箱码头运营成本中最大的支出.

当前集装箱码头最先进的水平运输机械设备是自动导引小车(AGV)，其运输管理系统的核心部分是AGV路径规划，优化AGV路径规划可极大提高港口工作效率和港口吞吐量.自动化机器领域不同于人类领域，需要对所有AGV可能出现的行为进行事先编程.因此，环境的复杂性使得集装箱码头总会出现不可预测的情况，利用引入碰撞因子的A*算法研究码头AGV路径规划问题，在时间和空间上均提高了AGV搜索路径的科学性，降低了系统的不可预测性，货损率及物流成本降低，实现了对港口的智能化管理.

AGV路径规划主要是运用数学归纳法建立整数规划模型、动态规划模型、petri网模型等随着生产力的发展，新型高效的调度原则在不断地提出，比如Enrico等[1]采用割平面法对AGV进行调度，将码头分成多个独立的小区域，不同区域内根据任务数量分配对应数量AGV独立实行调度；Hamed等[2]在动态作业中构建了一种最大流量的启发式算法，建立动态规划模型，实时确定AGV的需求量，但在实际应用中，港口生产工序复杂，网络数据处理时间长；A*是一种新型的启发性算法，能够快速高效的求得近似最优解，杨璐等[3]通过传感器技术和A*算法，当AGV遇到障碍物时可立即重新规划路径，提高了A*算法可采纳性；针对AGV规划路径时避免发生碰撞的研究，Chin等[4-5]采用FIFO原则和低速区设置的原则，减少AGV发生的碰撞.针对多辆AGV同时运行时发生的冲突碰撞问题，Mohammad等[6]以AGV完成任务时间最短为目标,建立蚁群算法模型，减少了AGV发车频率，达到减少相互碰撞的可能性.针对单回访路线，张煜等[7]提出了AGV运行途中交叉口区域设置模糊控制缓冲带，以此来避免拥堵碰撞.目前国内外均没有将A*算法与避免碰撞结合的方法，本文将基于A*算法路径规划时引入碰撞因子，规划出避免碰撞的最佳路径.

1 传统A*算法基本原理

A*算法属于人工智能范畴中具有明显启发式特征的搜索算法，因为其速度快、灵活度高并且对各种路状适应性强，是路径规划常用的工具.A*算法通过将初始起点与中间节点的实际距离函数以及中间节点到目标节点的启发式函数两方面结合分析当前节点.

A*算法的评价函数为

f(k)=g(k)+h(k)

(1)

式中：f(k)为初始点、节点k,以及目标节点三者间所有距离的评价函数；g(k)为初始节点到达节点k之间的实际距离函数；h(k)为节点k到达目标节点最优路径的估计距离函数，也可称为启发函数.

启发函数在A*算法中起着关键性作用，决定算法准确性的高低.若h(k)=0，即f(k)=g(k)，则 A*算法就转换成Dijkstra算法；若g(k)=0,即f(k)=h(k),则A*算法转化为贪婪算法.若h(k)低于g(k)，则A*算法经过扩展得到的结点数量就会增加，此时的算法的运行速率就会降低；若h(k)相于g(k)，此时算法可以最快的搜索到最佳路径同时还不会进行额外拓展；若h(k)高于g(k)，此时可能无法寻找到最优路径，但是算法的运行速率提升了.

计算在二维平面中的两节点(X1,Y1),(X2,Y2)之间的距离函数主要有切比雪夫距离、曼哈顿距离和欧氏距离最短距离.结合港口实际情况，AGV小车运行途中一定会遇到不可避免的障碍物，所以不采用切比雪夫距离.在传统8领域A*算法中，竖直方向和水平方向欧式距离和曼哈顿距离计算结果是相同的，而在对角线方向上欧式距离计算结果与实际情况的偏差较曼哈顿计算结果误差较小，所以欧式距离更能满足实验的要求，为

(2)

传统A*算法实现的具体步骤见图1.

图1 A*算法流程图

2 改进的A*算法原理

2.1 栅格地图设置

在AGV路径规划系统中，获取环境地图是路径规划的前提，由于栅格地图环境表达直观，地图构建简单方便，在AGV路径规划系统中，对环境地图的描述形式通常使用栅格地图.栅格地图又称单元分解地图，是把实际复杂的工作环境转变成为一个二维平面数组，其具体操作如下：首先将环境的分割为一个个栅格，根据环境实际情况对存在障碍物的栅格定义为障碍栅格，否则定义为通行栅格，再对可能使用到的栅格做概率标记.

在栅格地图中，信息传递的精度取决于栅格的精度，栅格过大信息传递不准确，栅格过小会大大增加计算的复杂程度.在构建栅格地图时，若实际地图的长为a，宽为b，则栅格的面积S为a×b.再根据港口实际使用的AGV车身大小(设AGV长L,宽为D)，将大栅格分割成一个个小格，则栅格的行数为X=a/L，列数为Y=b/L，计算结果均向上取整，且一个小格视为AGV运行的最小单元.

2.2 引入碰撞威胁改进原理

A*算法规划出的路径不仅要符合AGV运行安全规范，避免与障碍物发生碰撞，还要保证路径转折点较少.若规划路径转折较多意味着AGV算法在实际运行途中需要多次改变运行方向，AGV在转向时速度降低，这不仅会降低作业效率，而且还会增加AGV的安全风险.因此提出启发函数引入碰撞威胁因子，以此来解决折点较多、碰撞威胁较大的问题，进一步提高A*算法规划路径的可采用性.

A*算法评价函数f(k)中的启发式函数h(k)是指从AGV当前位置k到目标节点B的估计行驶的总距离，但在实际AGV的路径中应包括估计距离hs(k)和碰撞威胁ht(k)两部分，并根据港口实际情况加入权数w调节两者的平衡，其表达式为

h(k)=wshs(k)+wtht(k)

(3)

式中：k为AGV当前位置；s为估计距离；t为碰撞威胁；hs(k)为路径节点位置间距离的累加，即AGV当前节点位置k到上一节点位置k-1的距离；例如：hs(1)为起点到节点1的距离，hs(2)为hs(1)加上节点1与节点2之间的估计距离，即hs(2)=hs(1)+s2；ht(k)为当前节点位置的碰撞威胁的累加，即上一节点所有碰撞威胁ht(k-1)与当前节点时可能与障碍物发生的碰撞成本；例如：ht(1)为起点到节点1的碰撞威胁，ht(2)为ht(1)加上节点2与当前可能与障碍物发生的碰撞成本，即ht(2)=ht(1)+t2；ws为已行驶距离在启发式函数h(k)的占比；wt为碰撞威胁在启发式函数h(k)的占比.

AGV与障碍物发生的碰撞威胁可通过AGV安全报警系统中的外侧轮廓点与障碍物间的距离进行量化.定义Tk为AGV与障碍物发生碰撞的威胁，AGV安全警报系统中的外侧轮廓特征点到障碍物距离为d，AGV设定的安全距离为dsafe.当AGV到障碍物的距离均大于安全距离时(d≥dsafe)，可认为当前节点与障碍物发生碰撞的概率为0；当AGV到障碍物的距离的最小值小于安全距离时(d

(4)

从起始点到AGV当前位置k的所有碰撞威胁Tk(i=0,1,2,…,k)，则碰撞威胁为

(5)

综上所述，改进的A*算法评价函数为

f(k)=g(k)+wshs(k)+wtht(k)

(6)

改进后的A*算法的启发式函数h(k)包括估计距离hs(k)和碰撞威胁ht(k)两部分,流程图见图2.

图2 加入碰撞威胁后的流程图

3 案例分析

3.1 洋山深水港介绍

洋山深水港区坐落于浙江省嵊泗崎岖列岛，是我国首个海岛式人工码头，同时也是目前世界上最大的集装箱港口.其岸线长约为2.8 km，平均陆域纵深约500 m，总用地面积223.16万m2，码头前沿自然水深大部分在11～15 m，港区全年可作业天数在315 d以上.建有五个5万t级泊位，两个7万t级泊位，码头强度结构均按15万t级集装箱船舶设计建造.港口作业采用采用了垂岸式的作业线、高密度堆垛方式，极大地提高了土地资源与海岸线资源的利用程度.码头内部交通流自东向西，集装箱卡车进港后单向行驶，根据货物的特性在堆场外侧设立不同的装卸区域，高效的完成集装箱的转运工作.

目前配备“双小车集装箱装卸桥+AGV+自动轨道式龙门起重机(ARMG)”的装卸工艺方案，主要装卸环节均实现了全电力驱动，提高了能源利用效率，降低了能耗，减小了废气和噪声对环境的影响.配有10台双小车集装箱岸桥、38台自动轨道式龙门吊，以及50辆自动引导小车.AGV为长为15.878 m、宽为2.85 m，设最大行驰速度30 km/h，连续里程110 km，续行时间8 h，额定载重量为61 t，满载重量为74.5 t其中，每台AGV平均1 h可完成40 TEU的水平运输作业.

3.2 实验过程及结果

在MatLab2016b的实验环境条件下，根据洋山深水港四期实际布局，选择50 000 t泊位，配备两台岸桥，集装箱分配于堆场一个危险品堆场和四个普通集装箱堆场，港内水平运输均由AGV完成，最终由港外集装箱卡车运出.将一个小格视为AGV运行的最小单元，则栅格地图尺寸选择45×30；栅格地图采用直角坐标标记，设左下角为坐标原点(0,0)，水平向右为X轴正半轴，竖直向上为Y轴正半轴，每一个栅格都可由唯一直角坐标(X,Y)表示.栅格地图中的障碍栅格和通行栅格根据洋山深水港四期码头特征选择，其中障碍物包括堆场箱位区、装卸区等固定功能区域、港区有关的安全标示和港区内其他机械设施，实验中选取小圆圈标注障碍栅格，见图3～4.

图3 洋山深水港仿真实验栅格地图

图4 路径规划仿真实验对比图

在改进的A*算法中预先设定估计距离成本和碰撞威胁成本两部分的权数分别为0.7和0.3[8].根据洋山深水港相关规定，AGV与障碍物的安全距离为2.5 m，即可设定为为0.2个栅格.

表1为传统A*算法与改进后的A*算法主要参数对比，goal-distance为不考虑障碍物存在，从起始节点到目标节点的直线距离.同组实验只中改变了障碍物的数量与位置，其余参数保证不变，所以goal-distance是相等的.path-cost为A*算法规划出路径的实际距离.由于改进A*算法的估计距离成本函数更复杂，扩展节点更多，规划路径所用的时间有所增加，但在实际运行中规划路径变短、AGV改变方向次数减少会使得AGV完成任务的总体时间减少.

表1 传统A*算法与改进后的A*算法主要参数对比

通过改变洋山港AGV起始点位置及不同环境中，设计多组实验，仿真结果见图5～8，表2对比了传统A*算法与引入碰撞威胁因子的A*算法主要参数.

图5 第一组路径规划仿真实验

图6 第二组路径规划仿真实验

图7 第三组路径规划仿真实验

图8 第四组路径规划仿真实验

表2 传统A*算法与引入碰撞因子的A*算法主要参数对比

引入碰撞因子的A*算法引入碰撞威胁因子后，扩展节点增加，其搜索的结果更加精准，其规划的路径转折点较少，路径更加平滑，AGV拐弯次数更少，有效的保证了货物和车辆的安全，由表2可知，改进后的A*算法规划距离缩短1 m，规划时间增加约为0.04 s，整体效率提高显著，有利于AGV的自动运行.

4 结 束 语

针对A*算法规划出的路径发生碰撞的可能性较大，往往规划出的路径在港口实际运行中不是最优解，提出了引入碰撞威胁因子的A*算法，最后通过在matlab 2016b环境下的仿真实验，验证了改进A*算法思路上的可行性和合理性.通过上海洋山深水港实际案例，设计仿真实验，实验结果表明改进的A*算法的具有一定实用性.

需要指出本文在栅格地图设置中存在的不足，将一个小格视为AGV运行的最小单元，地图的精度还有待进一步提高；且本文仅设置了通行栅格和障碍栅格，对于一些可移动障碍物实AGV也许只需稍加等待便可按初始最佳路径行驶，无需二次规划路径，若能在栅格地图中加入一些特殊障碍栅格，并引用时间窗的思想，对AGV运行路径进行实时动态规划，可进一步提搞AGV的容错性.