仓储物流中自动导引车的路径规划研究*
2019-01-03刘敬一孙维堂董君陶
刘敬一，孙维堂，刘 闽，董君陶
(1.中国科学院大学，北京 100049；2.中国科学院 沈阳计算技术研究所 智能控制与装备部,沈阳 110168；3.沈阳市环境监测中心站 沈阳 110000；4沈阳市第二十七中学 沈阳 110011)
0 引言
随着柔性制造系统的广泛应用，国内对自动导引车的需求量也渐渐增长。在整个自动化仓储物流中，AGV运输成本占总成本比重较高，仓储任务的精准调度以及AGV良好的路径规划策略，对提高物流作业效率、降低运输成本有重要意义。
针对多AGV的路径寻优问题，刘国栋等[1]提出了一种两阶段的交通控制方法来解决AGV路径冲突问题,王佳溶[2]提出改进型的两阶段控制策略，他们针对任务的优先级未做详细描述，当任务和车辆非常多时，容易产生任务饥饿；胡彬等[3]提出一种基于时间窗的动态路径规划方法，先搜索出备选路径，然后通过计算和排布时间窗来规避冲突，但提出的时间窗是基于边的，也就是一条较长车道只能被一台AGV保留，效率比节点时间窗低。
对AGV路径规划中路径成本最优化以及调度效率问题，提出一种基于优先级队列和时间窗动态排序的路径规划方法。首先构建任务优先级队列，然后用A-Star算法启发式搜索路径，通过对节点时间窗进行精确计算和加锁，实现了多AGV的路径实时规划和动态调优，在无碰撞冲突条件下保证了仓储物流路径成本最低，而且提高了系统运行效率。
1 问题描述
1.1 环境地图
本文所考虑的是自动化仓储物流中AGV群体运动规则问题，根据其所在的仓储环境采用拓扑建模法构建地图，并作以下假设：
(1)相邻节点间的路线为单行道可双向行驶。
(2)AGV在4个方向上以同一速度匀速行驶，且转向速度固定；
(3)AGV间安全制动距离为0.8m；
(4)AGV共有4种状态：无任务静止状态(包括充电状态)，有任务待负载行驶状态，负载搬运状态，临时等待状态。
图1 仓储环境下拓扑地图
1.2 目标函数
针对AGV仓储物流环境，建立拓扑地图，如图1所示，在有向连接网络G=
ey={vp→vq：vp，vq∈V}
(1)
多AGV路径规划的目的是规划出一条时间代价最小的路径。AGV在仓储环境中的耗时分为到达装载点时间，搬运状态时间和避障等待时间，分别设为的tk、carrytk和Ωk。因此所有AGV的时间代价之和可由以下公式得到：
(2)
其中，k为仓储任务的编号。
1.3 任务调度
(1)亟待充电且携带任务，将已分配的任务作为高优先级重新分配，然后将充电任务作为中优先级重新分配；
(2)亟待充电且无任务无负载，将充电任务作为中优先级重新分配；
(3)一般性实时任务作为低优先级分配；
(4)同一优先级按照FCFS方法分配。
1.4 避障要素
(1)相向相遇冲突。如图2所示，相向行驶的两辆车相遇；
图2 相向冲突示意图
(2)垂直相遇冲突。如图3所示，垂直方向的两辆车在节点相遇；
图3 垂直相遇冲突示意图
(3)占位冲突(车辆空闲)。如图4所示，前方因AGV空闲停车阻止了其他车的前进。
图4 占位冲突1示意图
(4)占位冲突(故障)。如图5所示，前方因故障停车阻止了其他车的前进。
图5 占位冲突2示意图
(5)追尾冲突(超速)。如图6所示,即将赶超。
图6 追尾冲突示意图
2 基于时间窗的避障路线规划法
2.1 时间窗定义
如图1所示，在有向连接网络G=(V，E)中，假设有x辆车参与任务执行，那么任务的AGV集合为A={a1，a2,…，ax}。所有任务的起点、终点都不同，那么任务的起点集合和终点的集合分别记为S和D,且S⊆V，D⊆V。那么自动导引车所经过节点的时间窗可以定义为：
(3)
图7 节点保留时间窗模型图
2.2 时间窗计算
为了保障仓储物流过程的安全性，需要对时间窗进行精准计算，如图7所示。设AGV到达节点i的时间为ti,则有公式：
(4)
其中，tb为车辆安全制动时间，te为允许最大误差时间，包括在节点处突发断电及故障引起的制动误差。
如图8所示，设AGV车身的长度为l，AGV直行通过节点时，则有公式：
(5)
其中，vst是小车统一默认的直行速度。
图8 自动导引车通过节点i示意图
如图9所示，当AGV在节点处转弯时，则有：
(6)
其中，vtu是小车转弯通过节点的速度。
图9 自动导引车转弯通过节点i示意图
2.3 AGV最优路径规划算法
在进行多AGV路径寻优时，采用拓扑建模法构建仓储电子地图，且携带任务的AGV在运行过程中可双向行驶。将一个仓储搬运任务定义为：
carryk(t)={PQk(t),btk,Sk,Dk,LBk(t)}
(7)
其中，PQk表示第k个任务的实时优先级，参数越大优先级越低；btk表示第k个任务的开始时间；Sk和Dk分别表示第k个任务的装载点和卸载点，且Sk∈V、Dk∈V；枚举类型的参数LBk(t)表示第k个任务的搬运状态,如公式(8)所示。
(8)
给任务分配不同的优先级PQ：如图10所示，将任务队列划分为高中低三个优先级队列，分别用PQh、PQm和PQl来表示。
(1)当LBk(t)=0时，小车正在去装载点的路途中，即当有任务无负载的AGV小车亟待充电或突发断电等故障时，已安排的任务的需要重新分配，将该任务carryk(t)放入高优先级队列，将充电或维修任务放入中优先级队列；
(2)当LBk(t)=1时，AGV在装载点Sk和目的地Dk之间，即有任务有负载的AGV亟待充电或突发断电等故障时，已安排的任务的需要重新初始化，因为装载点Sk已经改变，然后将新任务carryk(t)放入高优先级队列，将充电或维修任务放入中优先级队列；
(3) 把一般性实时任务放入低优先级队列。
图10 三叉堆优先级队列示意图
体现在冲突一：后续的长任务需要不断地寻找次优路线；体现在冲突二：后续的长任务需要不断地负载等待。二者都容易造成任务饥饿，会降低调度系统的效率。
我们有了任务的优先级分配和时间窗的计算，下面来介绍路径规划算法的具体实现步骤，如图11所示。
(1)根据上位机系统管理员输入仓储物流参数，将任务划分优先级，插入优先级队列，并初始化多个运输任务，carryk(t)={PQk(t),btk,Sk,Dk,LBk(t)}。
(2)按照任务的优先级顺序进行车辆调度：选用离装载点[6]最近的空闲AGV来执行任务。
(3)用A-Star算法对路径进行启发式搜索，得到临时的最短行驶路径。
(5)初始化节点时间窗Wk，如果存在任务p和q使Wp∩Wq≠∅，说明节点时间窗因尚未加锁而出现重叠现象，即在的某个保留时间窗内出现了其他车辆[7]。
(6)根据重叠时间窗和拓扑地图，来确定将会发生哪种节点冲突，然后对每个节点的时间窗加锁。如果存在如图2所示的冲突一相向相遇冲突[8]，选择PQk(t)较大的任务重新调度，由于根据启发式算法规划的临时最优路线会出现碰撞[9]，因此需要继续搜索次优路径，返回执行步骤(3)，若最后所有路线都会出现冲突一，那么返回执行步骤(2)更换AGV车辆；如果冲突类型只剩冲突二垂直相遇冲突[10]，那么携带低优先级任务的AGV原地等待一个节点时间窗的时间，直到重叠窗口消失；如果两种冲突都存在，则先按照相向相遇冲突处理。
(7)生成可执行任务(指定AGV，明确路线)，AGV执行完任务空闲后，由于该AGV可能成为其他任务的障碍，所以要优先派发该车辆。重复执行步骤(1)等待管理员动态分发新需求。
图11 AGV路径规划算法流程图
考虑其他三种冲突，任务执行过程中，对于冲突三,那么将更改此空闲AGV所占有的节点周围四条边的权重为无穷大,修改任务的起始点，执行算法中的步骤(3)；对于冲突四，可能为突发断电(非亟待充电提醒)或机械老化等故障，需要人工维修或清除，然后更新可用AGV信息；对于冲突五，由于环境中假设AGV速度相同，所以不会出现赶超冲突，即使在前面的AGV制动减速的时候也不会出现赶超冲突，因为在计算时间窗时，AGV制动时间tb已经被保留在时间窗内。
3 算法仿真验证
使用 Visual Studio 2015作为仿真开发平台，编写调度程序对提出的路径寻优算法进行验证。选取某仓储物流中心如图1拓扑地图所示，仓储区域长30m，宽30m，仓储节点36(不包括充电区域)，144个货架，14条车道纵横交错,AGV直行速度为0.5m/s。转向时间固定为2s。
设计两组仿真对比实验：一组是无时间窗加锁和有时间窗加锁的路径寻优结果，另一组是不含优先级队列和含优先级队列的路径寻优结果。从两个维度来验证所提出算法的可行性和高效性。
(1)针对第一种仿真对比实验，我们分别初始化三个任务：
carry1(t)={1,0,a1,c5, -1}。
carry2(t)={2,0,g3,b3, -1}。
carry3(t)={3,0,e1,b2, -1}。
首先根据任务的预估时间来初始化优先级，时间越长，PQk(t)数字越小，优先级越高。
无时间窗加锁的情况如图12所示，执行任务carry1(t)的车辆将会与执行carry3(t)的车辆在b1到c1路段发生相向相遇冲突，执行任务carry1(t)的车辆将会与执行carry2(t)的车辆在c3节点发生垂直相遇冲突[11]；
图12 无时间窗加锁含优先级路径寻优结果
含时间窗加锁的情况如图13所示，由于经过时间窗的重新排布，任务carry3(t)已经重新规划路线，有效避免与任务carry1(t)相向相遇冲突，且在节点c2进行等待规避，避免垂直相遇冲突，任务carry3(t)将会在节点c3处进行规避等待，有效避免死锁和碰撞[12]。
图13 含时间窗加锁含优先级路径寻优结果
(2)针对第二种仿真对比实验，在不含优先级的算法中我们分别初始化三个任务，这里PQk(t)均为1，即：
carry1(t)={1,0,a1,c5, -1}。
carry2(t)={1,0,g3,b3, -1}。
carry3(t)={1,0,e1,b2, -1}。
算法执行过程如图14所示。
图14 含时间窗加锁不含优先级路径寻优结果
考虑图13和图14所示的两种仿真执行过程，对不含优先级和含优先级的两种调度算法进行路径代价对比，如表1和表2所示。根据目标函数公式计算出：含优先级的调度算法路径成本Cost小于不含优先级的调度算法。
表1 不含优先级队列的调度算法执行分析
表2 含优先级队列的调度算法执行分析
4 结论
对多AGV路径寻优和调度效率问题，提出基于优先级队列和时间窗模型的调度算法。在多AGV动态路径寻优中，解决了多AGV的碰撞冲突问题，而且通过构建任务优先级队列优先级优化了调度顺序，不仅保证了路径最优，而且可以避免任务饥饿与死锁。最后通过仿真实验得出，算法在保证车辆无碰撞的条件下可使AGV路径成本最低，同时提高了任务和车辆调度的效率。
