基于赋时Petri网的磁导航AGV路径优化方法

张 斌,李 建,马锦程,何仁杰

(中国计量大学 计量测试工程学院,浙江 杭州 310018)

随着工业生产技术的不断提高,效率低下的传统物流方式已经不能满足现代化企业的要求。自动导引小车(Automated guided vehicle,AGV)的出现使企业意识到自动化物流的重要性[1,2],在物流系统里面,使用自动导引小车可以让企业成本大大降底,并且还可以使自动化程度及效率和物流系统的柔性得到提升[3,4]。

磁条导航[5](以下简称磁导航)具有现场施工简单、周期短、成本低的优点,其技术成熟可靠,对于声光无干扰性。AGV运行路径明显,线路二次变更容易、变更成本低。磁条导航是众多AGV导航技术中使用最多的导航方式。但是磁条导航技术仍然面临着一些技术问题,需要进行改进。主要问题有:

(1)AGV小车的站点位置信息不连续,无绝对位置信息。当小车处于两站点之间时,无法通过RFID传感器获取小车的位置信息。

(2)小车在拐弯、到达目标站点或者避让需要减速时,无法进行很好的预判,导致高速运转时稳定性较差。

(3)AGV调度方式单一,一般采用区域管制,无法适应复杂的现场工况,AGV的运行效率较低。

因此,为了能够进一步提升磁条导航AGV的应用水平,必须解决好以上诸多问题,关键是获取AGV运行过程的完整信息,构建完善的AGV系统模型,解决AGV系统运行时的无碰撞的最优路径规划问题。

国内的刘国栋[6]等人提出一种动态路径规划算法。首先,离线找出所有可通行的路径,再通过启发式算法对其进行路径优化。焦福明[7]针对整批执行任务,通过使行驶时间最长的AGV时间最短来规划每个AGV的行驶路线。邢科新[8]提出了一种动态时间窗路径规划方法:首先,规划每个AGV的时间最短路径,获得AGV经过路径上所有节点和路段的时间窗,然后通过比较各个AGV的时间窗,对其进行调整,从而实现多AGV的路径规划。赵东雄[9]通过速度调节平移时间窗,调用优化算法与规避策略实现AGV无碰撞路径规划。国外的Jeon等[10]提出一种基于Q学习的路径规划算法,通过估计行驶中因冲突产生的等待时间,为AGV规划一条行驶时间最短的路径,但是该算法用时较长,且不能避免死锁。

Petri网理论在AGV系统中的应用给AGV系统整体建模提供了一种新的思路[11]。任小龙[12]采用无向Petri网对AGV系统路径布局进行建模,与时间窗结合建立基于时间的可达状态图,提出了时间最短的路径优化算法。胡源[13]基于Petri网和行为轮廓的思想,从过程行为角度进行建模,对扫地机器人路径系统模型的设计进行了分析。赵思萌[14]针对铁路物流中心的卸车业务流程,建立了基于Petri网的业务流程模型并进行了仿真。总的来讲,Petri网理论在AGV系统中的应用还处于初级阶段,没有建立起完整的理论体系,有待进一步的研究。

基于以上对研究现状的调研分析,本文将通过研究基于赋时Petri网理论的磁导航AGV系统建模理论与方法,并结合改进Dijkstra路径搜索算法实现动态的、可避障的多AGV路径规划及调度,进一步提升磁导航AGV的应用水平。

1 赋时Petri网

1.1 时间窗

AGV在执行任务的过程中,如要实时了解AGV的位置信息,可以将AGV经过节点和路径的时间以时间窗的形式记录下来。对于多AGV路径节点占用的情况可以通过集合的方式准确描述:针对AGVk而言,其路径表示为:

pathk={pi,pj,…,pn}

AGVk在执行当前任务的路径节点的时间窗表示为:

对于路径集合(i-j-k)的时间窗的显示情况如图1所示:

图1 路径集合(i-j-k)的时间窗Figure 1 Time window of path set(i-j-k)

1.2 赋时Petri网

赋时Petri网属于高级Petri网,它在普通Petri网基础上加入了时间因素,模拟系统中不同变化的延时,以此来对系统的性能进行分析。

赋时Petri网通常分为两类,第一类TTPN(Transition-timed petri net),即变迁时间增加时的延时;第二类PTPN(Place-timed petri net),即库所时间增加时的延时。将TTPN与PTPN相结合,可构建磁导航AGV的赋时Petri网模型。

在模型中,用库所表示节点,用变迁表示可双向通行的路径,用令牌表示AGV,用标识描述AGV系统状态。如果库所为空,说明AGV不在该位置;如果库所中有一个令牌,代表AGV停留或者是正在穿过该位置。模型可用以下六元组进行描述:

PN=(P,T,F,D0,D1,M0)

◆P={p1,p2,…,pm},pi代表库所,i=(1,2,…,m)。

◆T={t1,t2,…,tn},tj代表变迁,j=(1,2,…,n)。

◆F为m×n的矩阵,其元素fij为0时,表示pi与tj不相连;fij为1时,表示pi与tj相连。

◆D0={d1,d2,…,dn}为变迁的可变时延集,其中di为变迁ti的时延。

◆D1={g1,g2,…,gm}为库所的可变时延集,其中gi为库所pi的时延。

◆M0为系统的初始状态。

该模型描述了AGV系统的地图拓扑结构及时间信息。

在任意时刻,某一节点或者某一段路径上只能存在一个AGV,所以变迁的激发指AGV离开当前节点,沿着原有路线向另外一个连接的路线行驶,对于同一变迁,在不同状态下完成该变迁的时间是不同的。

变迁的激发规则:库所pi里面有一个令牌,在时刻Ta激发与其相连接的变迁tj,在Tb时刻,把令牌转移到和变迁tj连接的库所pk,而且这个时候库所pk为空,同时Tb-Ta≥dj(dj就是在理想状态下变迁tj激发的时间延迟),即AGV穿越同一路径要用到的时间由系统的交通状况决定,但通过时间都应大于或者等于理想状态下穿越路径的时间。

库所的时延规则:令牌在Te时刻移入库所pi,在Tr时刻令牌移出库所pi,激发与其相连接的变迁,要求Tr-Te≥gi,gi为理想状态下令牌在库所pi的停留时间,即AGV通过节点所用的时间均应大于或者等于理想状态下穿越节点的时间。AGV穿越同一节点时的行驶状态可以分两种情况:AGV直行通过该节点,要求Tr-Te≥tc,即gi=tc;AGV在该节点处转弯,要求Tr-Te≥tb,即gi=tb。

根据上述模型和相关规则定义,可以用Mi=[mi,TMi]来表示AGV的状态,其中mi为系统Petri网的标识,TMi为此标识形成的时刻,故m相同而时间不同表示不同的状态。AGV系统的状态变化过程即标识M的演变过程。因此,AGV的运动状态可以通过一系列赋时Petri网标识的变化来体现。

2 单AGV路径规划

AGV的路径规划是在全局信息已知的静态环境下进行的,单AGV的路径规划是在起始点处,利用已知环境找寻到一条评价指标最优的路径。本文选用Dijkstra算法作为单台AGV路径搜索算法,将AGV的行驶时间当作优化目标,考虑AGV行驶到交叉路口时候的直行和转弯两种路线。

如图2所示,当小车从3号站点运动至1号站点时,可以有多个路径选项,比如路线1和路线2等。路线1与路线2经过的站点相同,转弯次数相同,但是路线1比路线2行程短,所用的运动时间较少。

图2 最短行程示意图Figure 2 Schematic diagram of the shortest stroke

但是行程最短时,AGV完成任务的时间不一定最优。如下图3所示,路线1比路线2的行程短,但是考虑到AGV小车在转弯时所需的加减速时间和转弯时间,路线2的运动时间很有可能是优于路线1的。同样,途经的站点数最少的路线也未必是时间最优的。

图3 时间最优路线示意图Figure 3 Schematic diagram of time optimal route

为了方便评估AGV运动过程所需要的时间,得到时间最优的路径,现对AGV系统作如下设定:

(1)AGV行驶速度恒定,直行和转弯速度分别为Vs和Vr;

(2)AGV启停时间为td,即速度可以在td时间内实现从零到AGV的匀速段行驶速度,以及从AGV的匀速段行驶速度到零的变化;

(3)AGV从某一站点到相邻站点的匀速运动时间为ta,在站点处转弯所需时间为tb,AGV直行通过站点的时间为tc。

那么AGV的整个运动过程所需要的时间:

H(R)=∑ta+∑tb+∑td+∑tc

(1)

根据改进的Dijkstra算法,可获得时间最优的AGV运行路径,算法如下:

步骤1:设初始节点p0,目标节点pg,建立空的搜索路径表SELECT表和可达路径表REACH表。

步骤2:将初始节点p0作为唯一站点生成初始路径,放入SELECT表。

步骤3:对SELECT表中的所有路径进行扩展,在路径末尾添加最末节点plast的所有相邻节点p＇,p＇必须是该路径中未曾出现的,并且是无障碍的节点。如果符合要求的相邻节点不存在,则删除该路径。

步骤4:如果p′=pg,则将该路径放入REACH表中。

步骤5:完毕所有可行的路径后,根据式(1)计算出每条可行路径完成所需要的时间。对REACH表中的所有路径按照时间进行排序,找出时间最优的路径作为搜索结果。

改进后的Dijkstra算法以时间最优为指标,提高AGV的工作效率。

3 多AGV的路径规划

对于多AGV路径规划问题,将基于赋时Petri网的AGV系统模型与单AGV的路径规划算法相结合,实现多AGV的路径规划与调度。

图4 变迁tj的第q段空闲时间示意图Figure 4 Schematic diagram of the q-th period of free time in the transition tj

图5 库所pi的第h段空闲时间示意图Figure 5 Schematic diagram of the h-th period of free time in the place pi

对于多AGV行驶过程中的冲突问题可以分为节点冲突、同向冲突、相向冲突三类。冲突不同,解决的策略不同。

3.1 等待策略

节点冲突与同向冲突是常见冲突,可以采用等待策略解决。对于赋时Petri网而言,首先要进行变迁激发的判定,保证小车正常启动。判定方法如下:

(1)AGV接受任务,确定起始节点p0和目标节点pg,对于Petri网模型是确定初始标识m0与目标标识mg,及接受的时间TM0,故初始状态为M0=[m0,TM0]。

(2)若m0与mg相同,则返回1)。若两者不相同,则利用改进的Dijkstra算法规划出一条时间最优的路径,更新系统变迁与库所的时间窗。

变迁激发判定后,行驶过程中遇到冲突采用等待策略。方法如下:

物理意义为两辆AGV同时争夺库所的使用权,即AGV1在变迁tj的路径上行驶,欲要穿越节点pi,此时节点pi正在被AGV2所占用,为了避免冲突,AGV1需要在变迁tj的路径上减速或者等待,当库所处于空闲状态下再继续行驶。

行驶中不仅要考虑下一库所是否冲突,还要在此基础上考虑下一路段的交通状况。方法如下:

(C)其他情况则后继状态不存在。

在上述情况中,状态m0经变迁tj后产生多个后继状态mi,将每一种状态对应的变迁占用的时间段在系统时间窗内进行相应的更新。

上述(B)的意义为:AGV1在变迁tj所代表的路径上行驶,欲要穿越节点pi后使用变迁ti所代表的路径,但此时ti代表的路径正在被另一个AGV2占用,为了避免冲突,AGV1应在变迁tj所代表的路径上减速等待,当变迁ti所代表的路径空闲时再继续正常行驶。

3.2 重新规划策略

对于相向冲突,若采用上述策略AGV系统会发生死锁,所以采用重新规划策略解决该冲突。以两车为例,若存在AGV1在变迁ti路段上行驶,欲穿过库所pk进入变迁tj路段,此时AGV2在路段上行驶,欲要穿过库所pk进入变迁ti路段,如图6所示。

图6 变迁路段相向冲突示意图Figure 6 Schematic diagram of the conflict between changing road sections

此时,比较两车正常到达库所pk的时间,若AGV1经过变迁ti路段到达库所pk时产生新的标志mj,其状态mj的时间为TMj,AGV2经过变迁tj路段到达库所pk时产生新的标志mi,其状态mi的时间为TMi。当系统检测到上述情况时,若TMi≥TMj,则代表AGV2先到达库所pk,此时AGV1在变迁ti路段等待,AGV2到达库所pk后,系统再次利用改进Dijkstra算法,以库所pk为新的起点,重新搜索新的路径,AGV1待AGV2驶出库所pk后正常行驶,系统将后续的时间窗进行相应的更新。反之,AGV2原地等待,直至AGV1找寻新的路径后正常行驶。

4 仿真实验

为了验证上述方法的可行性,对其进行仿真验证。如图7所示,系统满足任意两个库所之间至少存在两条路径,且任意变迁代表的路段中只允许一个AGV存在。系统包括两台AGV,p1和p3表示存放AGV的工作站,p12和p13表示生产产品的工作站,p2表示储存产品的工作站,其它库所表示磁条铺设时的交叉点。图8为AGV的Petri网模型的仿真界面,表1为理想状态下AGV穿越各路径所需时间,表2为系统向AGV发出的运送请求,根据上述算法得到的多AGV运行优化路径如表3,表中[]表示节点和路段的起止时间,节点转弯所需时间设置为3 s,直行通过节点的时间为1 s。

图7 AGV的Petri网模型Figure 7 Petri net model of AGV

图8 多AGV路径规划的仿真界面Figure 8 Simulation interface of multiple AGV path planning

表1 理想状态下在T1～T18路径行驶所需时间Table 1 Traveling time on the T1～T18 route under ideal conditions

表2 向AGV提出的运送请求Table 2 Shipping request to AGV

表3 多AGV运行优化路径Table 3 Optimization path of multi-AGV operation

上述事件中,AGV1在路段T12处行驶,欲要经过库所p10后使用路段T13,此时AGV2先经过库所p10占用了路段T13,根据上述算法中的(B)情况,AGV1需在路段T12处等待,直至AGV2驶出路段T13。当两车返回时,AGV1优先经过库所p11,进入路段T13,AGV2需在路段T14处等待,直至AGV1驶出路段T13。两车在路段T13处发生两次占用路段冲突,运用上述算法后有效解决了该冲突问题。

本文设计的AGV调度控制软件在实际生产中已经得到应用,图9是AGV调度控制软件在某生产车间内的实际应用效果场景图。在每个生产线上都放有一个呼叫器,方便任务的发布。当上位机调度控制软件收到呼叫请求时,就会自动搜索出呼叫站点与AGV当前所在的位置之间的最优路径,并且通过无线通讯模块对AGV发出指令,AGV就会沿着最优路径到达目标站点,完成对应的任务。

图9 调度软件的实际应用效果场景图Figure 9 Scenario diagram of actual application effect of scheduling software

图10是生产车间工作需要而铺设的磁条路径轨道,每一个路口都存在一条生产流水线,虽然实际的实验环境与仿真系统存在差别,但是规划出的行驶路径依然是时间最优路径,实际表明本文设计的调度控制软件可以用于实际生产中,效果良好。

图10 现场车间铺设的磁条路线Figure 10 The magnetic stripe route laid by the on-site workshop

5 结 论

本文以提升AGV调度系统的灵活性和运行效率为研究目标,对AGV的路径规划及避障问题进行了相关的研究。以赋时Petri网理论为基础,构建了磁导航AGV的系统模型,结合改进的Dijkstra算法,实现了AGV的时间最优路径的规划,并且在动态情况下有效解决了障碍冲突,提高了系统的运输能力。该优化方法有助于解决动态AGV路径优化问题,具有借鉴作用,并且设计的AGV调度软件可以满足工况需求,具有实际应用价值。