基于改进A*算法和系统短期状态预测的仓储AGV路径规划方法

王云峰,曹小华,郭 兴

(武汉理工大学 物流工程学院,湖北 武汉 430063)

0 引言

随着科技的不断进步,AGV(automated guided vehicle)越来越广泛地应用到生产、搬运等工作中,尤其在物流仓储中,AGV扮演着重要的角色。有关AGV路径规划方面的研究一直以来都是重点。常用到的有关路径规划方面的算法有A*算法[1-3]、Dijkstra算法[4-5]、蚁群算法[6]等。荆学东等[7]针对A*算法在复杂地图轨迹规划耗时长、拐点多的问题,提出了一种基于图论及几何方法的改进A*算法,在传统A*算法上结合图论进行路径规划;张新艳等[8]提出一种引入时间因子的改进A*算法,结合时间窗以及优先级策略实现多AGV的动态无碰撞路径规划;吴飞龙等[9]在传统A*算法的评价函数中添加了环境信息和位置信息,并设置了代价函数和启发函数的权重系数来改进A*算法,提高搜索效率。但他们都没有衡量和比较AGV由于频繁转弯带来的时间损耗与AGV总行驶时间之间的最优解关系。在多AGV路径规划方面,DAI等[10]建立了最小化能耗和完工时间的多目标路径规划优化模型,并提出一种改进遗传算法来求解该调度问题。RAHMAN等[11]研究开发了一种适用于码头物料搬运场景的多AGV路径规划方法,通过建立一个混合整数规划模型,采用了遗传算法等元启发式算法,以实现在合理的时间内完成调度;曹小华等[12]提出了基于冲突预测的避碰策略,但没有考虑减少冲突次数来提高系统的运行效率;刘二辉等[13]提出了基于改进花授粉算法的共融AGV作业车间调度,解决了传统智能算法求解AGV与机器集成的车间调度问题效率低且易早熟的缺点。

AGV路径规划的优化目标通常是最短路径[14-15]或最短耗时[16]。但由于AGV因障碍物的存在需要绕路和频繁转弯,降低系统的运行效率;并且存在不同的路段资源使用不均衡的现象,增加了AGV之间的冲突几率,增多路径中的冲突节点。首先在单AGV路径规划中,针对传统A*算法的不足,提出一种改进的A*算法,对单AGV进行全局路径规划,在其启发函数中添加“方向函数”,引入障碍矩阵,在节点搜索的过程中判断目标点和障碍物的位置来不断修正启发函数,减少单AGV不必要的转弯次数;其次在多AGV路径规划中,以单AGV路径规划为基础,提出基于系统短期状态预测的多AGV路径规划方法,优化短期内各路段AGV数量,使道路资源分配更加合理化,减少路径中冲突节点数量。最后在VS2019上搭建的仿真实验平台上进行了验证,改进A*算法可以大幅降低单AGV的转弯次数,避免绕路现象,降低AGV总行驶时间;基于系统短期状态预测的多AGV路径规划方法,减少了多AGV在道路中的冲突节点,降低了任务总完成时间。

1 问题描述与建模

1.1 应用场景

传统电商物流仓储的环节是入库、上架、拣货、包装、分拣到最后配送到用户手中。过去通过人工对货物进行入库、上架、验货、取货、分拣等存在很大的弊端,耗时长、效率低、人力消耗多。现代物流仓储中引入AGV、机械手等自动化设备后,利用相关算法,降低了成本,工作效率以及工作秩序都得到了极大的提升。目前电商物流领头公司顺丰、京东、菜鸟等都在智慧物流领域加大投入。

本文研究的问题基于智慧物流中的仓储AGV搬运任务。仓储模型如图1所示,有AGV初始区域、分拣台区域和货架区以及各种路段。在搬运任务中,AGV需要避开其他货架到达目标点。

在多AGV系统中,每条路段上行驶的AGV数量不同、AGV小车之间的任务执行情况不同、路线不同、速度不同等,某一刻可能会在不同的路径节点处发生冲突,如图2所示。

1号AGV和2号AGV将在节点A处发生冲突,此时应采取必要的避碰策略,如任务优先级避碰策略、贪心算法避碰策略等。在搭建的实验仿真平台中显示各个AGV的实时动态轨迹,若两台及以上AGV同时到达某个节点,将该节点记为路径中的冲突节点。

1.2 数学模型

1.2.1 单AGV路径规划模型

由于AGV在执行任务过程中,需要频繁转弯以及在冲突节点进行避碰处理,会使仓储多AGV系统中AGV的的总行驶时间增加。

设在一次搬运任务中,某台AGV的转弯次数为K,每次由于转弯带来的时间损耗为ta,规划的路径长度为SD,平均运行速度为V,则在本次任务中,由于AGV转弯带来的系统时间损耗

TW=K×ta,

(1)

对于单AGV,其路径规划时的目标函数即为:

min{TW+SD/V}。

(2)

即在单AGV路径规划中,考虑到减少转弯次数,以最小化单次任务中AGV总行驶时间为目标对单AGV进行路径规划,本文采用改进A*算法进行求解。

1.2.2 多AGV路径规划模型

多AGV路径规划是在上述单AGV路径规划基础上进行的,即在多AGV路径规划中,每辆AGV都是上述单AGV路径规划,因此转弯次数多的问题已经解决,但要考虑到路径中的冲突节点数量问题,合理分配任务给各个AGV。设在一段时间T内,共有Nagv辆AGV执行任务,冲突节点的数量为Nc,每个冲突节点带来的时间损耗为tb,第i辆AGV的完成任务时间为Ti,在{T1,T2,T3,...Tk}中的最大值为Tmax。因此,对于多AGV,其路径规划时的目标函数为:

min{Tmax+Nc×tb}。

(3)

即多AGV路径规划时,考虑到路径中冲突节点数量,以最小化多AGV中最大完成时间为目标对多AGV进行路径规划,由于是同时对所有AGV进行路径规划,最大完成时间即为任务总完成时间。本文采用基于系统短期状态预测的多AGV路径规划方法进行求解。

2 A*算法的改进

2.1 传统A*算法

A*算法是一种静态网路中求解最短路径最有效的启发式搜索算法。算法的核心为评价函数:

F(n)=G(n)+H(n)。

(4)

式中:n为节点,G(n)表示从初始节点(起点)到任意节点n的实际代价,H(n)表示从节点n到目标点(终点)启发式评估代价。H(n)的计算方法有很多,如曼哈顿距离、欧几里得距离、对角线距离等。这里选择标准启发函数—曼哈顿距离,即

H(n)=|nx-Dx|+|ny-Dy|。

(5)

式中:nx、ny分别为当前节点n的x坐标、y坐标,Dx、Dy分别为终点的x坐标、y坐标。

算法原理大致为:如图3,图中蓝色方格为障碍物,从红色方格起点S寻找至黄色方格终点D的最短路径,考虑到上述智慧仓储模型,只允许AGV上下左右4个方向运动,并且它们的移动代价都设为1。

步骤1将起点S加入一个待检查节点的列表open list,接着寻找S周围所有可达到的节点,图3中为S的上下左右4个节点,计算它们的G值,将其加入open list,并且将S设为父节点;

步骤2将S从open list中移除,将其加入另一个已检查列表close list;计算每个在open list中的节点的H值,即每个节点到终点D的曼哈顿距离。然后将每个节点的G值和H值相加,记为F;

步骤3选择F值最小的节点,对它进行步骤1的检查,如图4中绿色方格,这也是传统A*算法的不足之处,只考虑移动代价而没有考虑转弯代价。但需要注意:若可达到的节点已经在close list中,则忽略;若不在,则计算其G、H、F,设置父节点,并将其加入open list;若可达到的节点已经在open list中,即它们已经有了父节点,计算从当前节点移动到该节点是否具有更小的G值,若有,则将该节点的父节点重设为当前节点,重新计算G值和F值;

步骤4不断重复以上步骤,直到终点D加入open list中,其H=0,即结束算法,通过父节点回溯得到最短路径,如图5所示。

2.2 改进A*算法

传统A*算法在寻找最短路径时非常有效,很多时候可以寻找到最短路径,但是在上述智慧物流仓储中,路径最短并不一定效率最高,这是因为AGV由于转弯会带来时间损耗。而传统A*算法带来的多余的转弯主要是由于障碍物的存在使其必须变向扩展节点。

一方面,改进A*算法实行“奖惩机制”,寻路扩展节点时,让它更偏向于沿直线扩展节点,若扩展的节点出现拐点,则在其评价函数中予以“惩罚”,即增加其代价值,惩罚函数如下:

(6)

其中:λ为惩罚因子;C为单位移动代价,即上述地图中相邻栅格之间的移动代价;xp为扩展节点的父节点x坐标;yp为扩展节点的父节点y坐标;xo为扩展节点的子节点x坐标;yo为扩展节点的子节点y坐标。

另一方面,引入“AGV的方向感”概念,在其启发函数H(n)中加入“方向函数”H*(n)。“AGV的方向感”是指通过障碍矩阵M,判断和比较任务终点位置以及AGV周围障碍物的位置,使算法在扩展节点时有方向性,给予符合条件的节点一定的奖励,即减少其代价值来不断修正启发函数。

矩阵M大小与模型地图保持一致,由0和1组成,0表示可通行,1表示障碍物。

AGV在进行路径规划时,将自身所在位置坐标和任务终点坐标与矩阵M中相应位置坐标匹配,比较AGV位置与障碍物位置的相对关系,确定障碍物相对于AGV的方向。对矩阵M中AGV位置以及任务终点的周围进行检查,若周围为0,则表示没有障碍物,若为1,则表示有障碍物。在有障碍物的情况下,改进A*算法在扩展节点时,若该节点方向与障碍物所在方向一致,则通过方向函数对其H值予以修正。方向函数H*(n)

H*(n)=H(n)+δ×C。

(7)

式中δ为方向系数,根据具体模型取值。

经过惩罚函数P以及方向函数H*(n)修正后的评价函数F(n)为:

F(n)=G(n)+H(n)+(P+δ)×C。

(8)

如图6,绿色路径为传统A*算法所规划,橙色路径为改进A*算法所规划,可以看出,改进A*算法没有走到障碍前才进行避障,相比于传统A*算法,在路径长度不变的情况下减少了转弯次数,可以降低AGV的总行驶时间。

改进A*算法的流程图如图7所示:

由式(2)可得,单AGV路径规划综合评价函数LS为:

LS=Kp×Sp/V+N×ta。

(9)

式中:Kp为改进A*算法得到得路径节点数量;Sp为路径节点长度;V为AGV平均运行速度;N为路径节点中拐点数量;ta为AGV每转弯耗时。

综合评价函数LS反映了改进A*算法在减少AGV总行驶时间方面的优化效果,函数LS的值越小,说明优化效果越好。

2.3 算法实现过程

图8中,橙色栅格表示货架,S表示AGV初始位置,D表示AGV终点,即目标货架所在位置,现需将S处的货架送回原处D。

步骤1将起点S点、终点D点位置与障碍矩阵M中相对应的位置匹配,对S点和D点之间进行障碍检测,如图8,D点位于S点的右上方,并确定两点之间有障碍物。将S点上下左右4个方向的扩展节点加入open list中,对他们进行代价值计算时,增加其上方节点的代价值;

步骤2检测终点D周围障碍物情况,如图9所示,D的下方一格没有障碍物,上方一格有障碍物,右侧障碍物数量低于左侧,对open list中的节点计算代价值时,减少其右方节点的代价值;

步骤3综合步骤1 和步骤2计算open list中的节点代价值,由于S点右方节点代价值小,将其加入close list中;重复步骤1和步骤2;

步骤4如图10,将红色方格加入open list中,检测到上方节点与终点D之间没有障碍物,对它们进行代价值计算时,减少上方红色节点的代价值。

步骤5继续完成整个寻路过程,如图11,其中蓝色路径代表改进的A*算法寻找的路径,比传统A*算法寻找的紫色路径减少了不必要的转弯。

综上所述,改进A*算法可以在扩展节点时根据自身、障碍以及目标所在位置,通过上述方向函数不断修正代价值以减少不必要的转弯,降低AGV的总行驶时间。

3 基于短期状态预测的多AGV路径规划方法

3.1 拣选作业系统的短期运行状态分析

在本文研究的智慧物流仓储AGV路径规划中,上文针对单AGV提出了改进A*算法,使得单AGV在执行多任务时能够减少转弯次数、避免不必要的路径节点。现提出基于短期状态预测的多AGV路径规划方法,在单AGV路径规划基础上对多AGV进行路径规划。在多AGV路径规划问题中,系统短期运行状态与货架数量、拣选台数量、AGV数量等系统配置相比,不能在系统运行过程中提前获取,而是会随着搬运任务的处理情况和调度方案实时变化。整个系统的多AGV路径规划除了考虑对AGV资源的分配,还应考虑到对作业区域道路资源的分配。尤其是在实际作业中,道路资源不是无限制使用的,其分配对系统运行效率有着极大的影响。因此,在本文的研究中,将重点考虑短期路段AGV通行量对路径规划的影响。

图12为某一时段(100 s)内仓储模型中某6条路段AGV通行量分布图,可以看出多AGV系统的道路资源的占用情况在系统运行过程中并不是均匀的,在1s～20s这段时间内,道路2经过的AGV比较多,而道路6经过的AGV数量相对较少。而6号路段再20s～60s这段时间的AGV通行量大幅增加,这就意味着在这一段时间内6号路段更容易发生拥堵以及冲突等情况,而1、4、5路段则更容易顺畅通过。同样也可以看出在90 s～100 s的时段内,路段3的通行量逐渐增加,这同样表明了AGV在路段3的拥塞冲突的可能性逐渐增加。因此,对于多AGV系统来说,路段的短期AGV通行量对AGV的通行状态有着不可忽视的影响,路段资源的合理分配能降低拥堵和冲突几率。

3.2 基于短期状态预测的路径规划方法

仓储多AGV系统的路径规划是一个复杂且高实时性的问题,对于多AGV系统的路径规划方法来说,掌握系统状态信息越多越及时,做出合理规划的可能性就越大。而单一的规划方法如任务完成时间最少、AGV总路径最短等没有考虑到道路资源的占用情况以及AGV的拥塞、冲突等情况。因此,在单一规划方法的基础上,提出一种基于系统短期状态预测的路径规划方法,通过时间轴来模拟预测短期时段内道路的AGV通行量以及可能发生的冲突碰撞等情况,降低冲突次数,降低任务总完成时间。

图13为短期状态预测下的多AGV路径规划方法流程图。预测方法采用按时间轴进行模拟预测,即对于若干辆AGV,利用改进A*算法对其进行路径规划,将它们的路径节点存放在数组中。从某一时刻起,在已知AGV的平均速度以及每转弯耗时后,上述若干AGV的路径节点与时间轴具有一一对应关系。通过判断时间轴上同一位置的节点是否一致来预测该节点是否为冲突节点。同时,由于每个路径节点与各条路段一一对应,可以对短期内各路段的AGV通行量进行预测,然后在此基础上建立新的路径规划评价函数,为AGV和正在请求的任务进行路径规划,以优化道路资源使用不平衡现象、减少AGV之间冲突节点数量为目标,得到新的路径方案。AGV将按照新的路径方案展开作业,直到系统作业结束。

下面给出基于短期状态预测的多AGV路径规划方法详细过程:

已知在决策时刻T0时,系统共有Nagv台AGV,作业系统已产生Np个任务,其中,Nf个任务已处理完毕,尚有Nw个任务正在执行过程中。在未完成的Nw个任务中,有Nm个任务处于执行状态,有Na个任务处于接受状态,处于这两种状态下的任务无法重新分配。除此之外,还有Nr个任务处于请求状态,这种状态下的订单可以重新分配。以最短路径规划方法分配Nm和Na个任务给数量为Nv的AGV,每台AGV执行一个或多个任务,通过改进A*算法给出AGV的行驶路线如式(10)和式(11)所示:

Pathj={Rj1,Rj2,Rj3,…,RjN},

(10)

Stepj={Pj1,Pj2,Pj3,…,PjS}。

(11)

其中:Pathj和Stepj分别表示j号AGV的规划行驶路段和路径节点,RjN表示j号AGV经过的路段,PjS表示j号AGV经过的路径节点,N表示对应的AGV经过的路段数量,S表示对应的AGV经过的路径节点数量。路径节点与路段属于映射关系,每个路径节点都有唯一的路段与之对应(交叉节点只计算一次)。

在多AGV系统的作业场景中,有路段数量为NR的集合,如式(12)所示:

Roads={R1,R2,R3,...,Ri,...,RNR}。

(12)

已知在当前时刻T0,有Nm个任务处于执行状态,Na个任务处于接受状态,Nv台AGV正在运行中。T0时刻,对于j号AGV来说,其路径节点如式(11),此时位于节点Pjk(1≤k≤S),AGV的平均速度V(单位:m/s)以及节点之间的距离Sp(单位:m),可以预测在未来一段时间t(单位:s)内,j号AGV行驶节点数n至节点Pj(k+n),节点数

n=V×t/Sp。

(13)

由于节点Pjk到节点Pj(k+n)与式中的各路段相对应,对于路段Rk来说,经过路段的AGV数量可以由式(14)和式(15)给出:

(14)

(15)

Nr个新增待接受任务{O1,O2,O3,…,Oi,…,ONr-1,ONr}随机分配给空闲的数量为Nagv-Nv的AGV,通过改进A*算法得到如式(10)和式(11)的模拟路径方案,重复上述过程,在未来一段时间t内,路段Rk的新增经过的AGV数量ΔNAGVk由式(15)和式(16)给出:

(16)

上述Nr个新增任务得到模拟路径方案,每个方案中节点移动耗时为tp,

tp=Sp/V。

(17)

若该节点为拐点,由式(1)可知耗时为ta,则这Nagv-Nv个AGV的冲突节点数量

(18)

其中:Smin为路径方案中的最小值;Ti和Tj分别表示不同AGV模拟走过相同数量节点时所花费的时间,有:

Ti=tp×s+ta×Kis,

(19)

Tj=tp×s+ta×Kjs。

(20)

其中:s为AGV模拟走过的节点数量;Kis为第i辆AGV模拟走过的拐点数量;Kjs为第j辆AGV模拟走过的拐点数量;根据式(19),记Ti(i=1,2,3,…,Nagv-Nv) 中的最大值为Tmax,即为AGV最大完成时间,由于同时进行路径规划,最大完成时间也为该批新增任务完成总时间。

因此,对于路段AGV通行量NAGV有方差S2,

(21)

多AGV路径规划方法目标函数:

(22)

约束条件为:

(22)

多AGV路径规划方法综合评价函数LM:

LM=ξ1×(Tmax+Nc×tb)+ξ2×S2。

(23)

式(22)和式(23)中:tb为每个冲突节点带来的时间损耗;Nc为冲突节点数量;ξ1为时间权重;ξ2为方差权重。

时间权重ξ1和方差权重ξ2的取值与任务数量Nr和AGV数量(Nagv-Nv)有关,应使时间和方差两者取权重后数量级基本一致,具体取值视具体模型而定。式(22)为基于系统短期状态预测的多AGV路径规划方法的目标函数:一是最小化多AGV中的最大完成时间(任务完成总时间),二是最小化各路段资源AGV经过次数的方差,以优化资源使用不平衡现象。式(23)为基于短期状态预测的多AGV路径规划方法综合评价函数,函数值越小,说明优化效果越好。

4 实验分析

4.1 实验场景

为了验证本文提出的改进A*算法以及多AGV路径规划方法的有效性,采用C#语言在Visual Studio 2019上搭建仿真实验平台。如图14所示为智慧物流仓储AGV实验平台。

实验场景为智慧物流中“货到人”分拣系统,即一次搬运任务中,AGV需要将目标货架搬运至指定分拣台进行分拣作业,待分拣完成后再将货架搬运回原位置,进行下一次任务。图14中黄色栅格为货架区,白色栅格为AGV初始区域,灰色栅格为分拣台区域。

4.2 仿真分析

单AGV路径规划中,为了验证改进A*算法的有效性,对比传统A*算法。实验条件如表1所示,实验为1台AGV分别执行不同数量的任务,对比算法为传统A*算法、Dijkstra算法以及改进A*算法。Dijkstra算法属于广度优先算法,由于需要处理的节点很多,运行耗时比A*算法长,但能保证找到一条最短路径,同时和传统A*算法一样,没有考虑到转弯次数对AGV总行驶时间的影响。结果如图15和图16以及表2和表3所示。

表1 算法对比实验参数表

表2 算法对比实验结果1

表3 算法对比实验结果2

如图15所示,随着任务数量的增多,改进A*算法在减少AGV的转弯次数上效果越来越显著;由表2可知,改进A*算法的每任务平均转弯次数相较于传统A*算法和Dijkstra算法分别降低了25.6%和28.4%;从图16和表3可以看出,改进A*算法在降低AGV总行驶时间方面显著优于传统A*算法和Dijkstra算法,相较于后两者,改进A*算法在总行驶时间上分别降低了21.1%和11.2%。

为了验证基于系统短期状态预测的多AGV路径规划方法的有效性,与最短路径规划方法对比。最短路径规划方法是以完成所有任务时AGV总行程最少为目标。实验参数如表4所示。

表4 基于短期状态预测多AGV路径规划方法实验参数表

设定系统不断生成总计100个任务,由2台、4台、6台等依次递增的AGV执行任务,记录它们完成任务时的冲突节点个数以及总时间进行对比,实验结果如图17和图18以及表5和表6所示。

表5 基于短期状态预测多AGV路径规划方法实验结果1

表6 基于短期状态预测多AGV路径规划方法实验结果2

从图17和表5可以看出,相比于最短路径多AGV规划方法,基于短期状态预测多AGV路径规划方法的AGV平均冲突节点个数降低了23.1%;从图18和表6可知,在任务总完成时间上,基于短期状态预测路径规划方法比最短路径规划方法减少了8.8%。因此,基于短期状态预测路径规划方法可以有效降低AGV之间的冲突节点个数和任务总完成时间。

5 结束语

本文针对多AGV系统在路径规划中存在的转弯次数多、冲突节点多的问题提出了基于改进A*算法和基于系统短期状态预测路径规划方法,实验结果表明,改进A*算法相比于传统A*算法能够有效减少转弯次数,降低AGV行驶总时间;系统短期状态预测多AGV路径规划方法相比于最短路径规划方法能够有效降低多AGV在路径中的冲突节点个数和任务总完成时间。其中短期状态预测路径规划方法中将AGV所在节点位置、AGV平均速度以及每转弯耗时,与时间轴相结合来预测未来一段时间内的各路段AGV通行量,虽然足够精确,但由于计算量较大,导致运行效率不高,仍有较大改进空间,在未来的工作中,可以考虑引入LSTM(long short-term memory)模型预测,提高程序运行效率。