于赫年，白 桦，李 超

1.哈尔滨工业大学 机电工程学院，哈尔滨150001

2.芜湖哈特机器人产业技术研究院有限公司 前瞻技术研究中心，安徽 芜湖241000

1 引言

随着电商、快递和新能源等新兴产业的高速发展，大幅带动了仓储AGV 的全面需求，为智能仓储系统的研发与应用注入了全新活力。加之制造业、商贸流通等领域的持续促进，智能仓储系统的发展具备更广阔的市场前景。对于任务规模化、货架密集型的仓储作业环境而言，路径规划算法对于提升智能仓储系统整体性能、降低各方面运营成本和提高企业利润等方面都起到了关键作用。

路径规划问题属于NPH问题[1]，这类问题的大型应用通常只能利用有效的近似算法求解。路径规划算法作为当今移动机器人领域的一大研究热点[2]，主要可划分为基于采样的和完备的两大类算法，基于采样的算法包括RRT[3]等算法，通常计算速度较快，被广泛应用于高维规划问题，但可行解的代价比完备算法高，也会存在有解求不出的问题；完备的算法的规划通常在已构建的网络图上进行，高维规划时代价较大，但在低维尺度上几乎无影响，尤其适用于预先构建了二维地图的仓储物流系统。已被证明比较有效的算法包括Dijkstra 算法、A*算法、蚁群算法等[4-7]，但这些算法对全局信息要求严格，动态适应性差，无法满足多AGV动态路径规划作业需求。

因此，Desaulniers G 等人[8]在贪心算法基础上进行改进，实现少量AGV的路径规划，但无法解决拥堵问题而非最优，Boada B L等人[9]通过动态调节AGV优先级的方式优化路径，Dakulovic M等人[10]提出一种双向D*算法，Guemane R 等人[11]对A*算法进行改进并提出Lazy A*算法，诸如遗传算法[12]等智能算法的改进也被提出。然而这些算法很少考虑动态环境下的实时响应和交通拥堵问题。

近年来的研究多集中在将路径规划算法与空间布置结合，来避免交通拥堵和死锁等问题。Digani V 等人[13]提出了一种基于两层控制架构的自动算法集成方法，巷道间布置多条方向不同通路，Yuan R等人[14]结合拥堵程度及交管规则对A*算法进行改进，同一巷道设置两条方向相同单行通道，Mark B[15]研究了不同通行方式对系统效率的影响。这些研究多以牺牲仓储空间、降低空间利用率或增加绕行的方式去解决拥堵问题。

为了不牺牲空间利用率，有研究者也提出增加时间维的算法，其中Bogdan S 等人[16]提出一种基于时间窗的智能AGV 动态路径规划算法；泰应鹏等人[17]也结合A*算法，增加时间窗对路径规划方法进行了改进，增加了实时避障功能。基于时间窗的算法一定程度上保证路径相对最优，但算法实现复杂，对系统时序要求严格，延迟难以确定[18]，路径易受系统扰动批量失效，无法满足复杂系统要求。

路径规划算法要保证多AGV系统发挥全部工作能力，实现有序、规范和准确作业，以期最短时间内高效完成全部作业。为了实现这种目标，本文首先利用现有优秀静态算法对该领域存在的一些现有问题进行改进，以满足多AGV 动态作业需求，并以此作为分析的对比参照，提出一种具有多步前瞻性的增量式路径规划算法，通过主动性的迭代拟合方法，提早获取路况信息，避开拥堵路段，减少发生冲突的可能，实现实时避障。

2 仓储系统模型构建

2.1 仓储环境描述

基于“货到人”的作业理念，AGV 需要根据订单需求主动将货架搬运到操作工位由人工完成分拣，因此首先要对智能仓储物流系统的作业环境进行构建，将仓储空间划分为两大功能区：

（1）AGV作业区

AGV作业区内含有货架存储站位、AGV停靠站、充电站和分拣站等主要功能站点，构成包括货架存储、AGV停靠充电和出入库分拣三大作业单元。各单元内部设置有供AGV 通行的巷道，各大单元间并由高速通道连接。AGV除停靠充电单元外不可在其他站位长时间停靠，通道内不设置静态障碍物以保障AGV顺畅通行。

（2）人工作业区

人工作业区与AGV 分拣单元相邻，人员在分拣单元以外取送分拣台上货物而不直接进入AGV 作业区，实现人机分离。避免AGV 取送货物过程中人工干扰，并保障了人员安全。

利用拓扑法对AGV 作业区进行电子地图的构建，图1 为AGV 作业区拓扑地图，其中深绿色区域为停靠充电单元，灰色区域为货架摆放单元，浅绿色为分拣作业单元。AGV 的整体尺寸小于货架，因此电子地图中相邻站点之间的距离取决于货架的尺寸，需要保障移动货架过程中既不会发生干涉又不会使间隙过大降低空间利用率。

图1 AGV作业区拓扑地图

对于任意一个不在地图边界上的站位，其相邻的理论可达站位如图2 所示共有8 个。AGV 可利用差速转向原理实现原地转向，考虑到站位间距及AGV 行进方向，最终确定AGV相邻可达位置为前后左右四个方向，AGV 可前后方向直接行进，左右两个方向的移动需要配合原地转向实现。

图2 AGV理论可达站点

2.2 任务类型

完成电子地图构建后，需要对智能仓储系统的不同任务类型进行划分，以满足不同需求的作业，简单来说就是实现AGV从规定起始站点调度到目标终点站位的过程。按任务的不同启动方式可划分为自启动与订单任务两种方式。自启动任务实现低电充电、自动泊车的作业需求，订单任务满足出入库分拣作业需求。仓储系统中按照一个任务最少需要规划的路径的次数可以分为以下几种类型：

（1）普通移位任务

规定起点到目标站点的单次路径规划寻访作业任务类型，可用于实现车辆调试、出库检修、移位移库、泊车及充电等功能。

（2）货架布置任务

两次路径规划寻访作业。首先指派一辆空闲AGV取得货架，然后将此货架运送至规定站位。可实现仓储空间货架摆放或按出入库热度进行货架调整。

（3）出/入库任务

三次路径规划寻访作业。有货物需要出入库时，由订单下达作业指令，智能仓储货物管理系统自动生成调度任务。由系统指派空闲AGV到达指定货架站位取得货架，运送货架至人工操作站位，由人工对货物处理，完成操作后将货架运送回原站位。

2.3 冲突类型

任务的执行过程中，AGV间相互竞争系统资源，可能会发生碰撞冲突。如图3所示为仓储式多AGV间的三种冲突类型[19]：侧向冲突、同向冲突和对向冲突，货架区只有AGV临近目标点，需要取送货物时才允许访问。

（1）侧向冲突，如图3（a）所示。两辆交叉方向的AGV 同时预约同一个节点，主要发生在十字路口，各AGV 到达节点后可能暂停、直行或转向，情况较为复杂，会产生冲突造成碰撞。

（2）同向冲突，如图3（b）所示。一般情况下AGV速度一致，同向行驶AGV 不会发生碰撞，但是当靠前AGV1 因避障、路口转向或访问货架转向而临时暂停，靠后AGV2预约站点又恰好被AGV1占用时，同样会发生碰撞。

（3）对向冲突，如图3（c）所示。货架间巷道采用单通道布置方式，AGV虽可双向行驶，但同一通道对向驶来的AGV，由于无处避障必然会产生冲突。

图3 几种碰撞冲突类型

3 AGV路径规划算法研究

对于静态路网路径规划问题，全局信息已知，站位及障碍信息不随时间变化，单AGV进行路径规划时，不存在其他AGV 干扰，可以较好地获得理论最优路径。而对于多AGV 的动态路网路径规划问题，地图信息动态变化，多AGV 间相互影响，很难获得系统全局信息。A*算法是一种静态路网中求解最短路最有效的方法[20]，存在应用价值及意义，但是它却不能有效解决多AGV的动态路径规划问题，因此有必要对其进行改进。同时本文提出一种具备多步预测功能的主动式寻路算法，将其与A*算法的改进算法比较，在有效解决冲突的基础上，验证新算法的可靠性和优异性。

3.1 被动式自调优A＊路径规划算法

3.1.1 转向修正

多数路径规划算法主要考虑路径距离最小化，很少考虑转向增加的时间成本，所规划的理论路径（图4 中路径2或路径3）带有多处转向点，规划路径理论距离最优而时间非最优（图4中路径1）。

转向修正的必要性体现在以下正反两个方面：

一方面，不考虑转向修正的路径规划算法[21]多应用于复杂空间环境下的单台移动机器人，侧重于减少无效路径。由于空间的不规律布置，路径必要转向次数较多，很难存在大段连续路径。即使考虑转向修正，效果并不显著，同时也会增加算法自身复杂性，整体性能提升不明显。

图4 规划路径对比图

另一方面，任务完成时间直接影响对系统效率要严格的多AGV 智能仓储系统。该系统空间布置规律，满足大段光滑路径的存在条件。单次任务路径一般较短，转向次数的增加会显著提高AGV 任务运行时间，而且频繁的转弯会使AGV 耗能增加[22]，有必要在路径规划过程中就考虑转向代价，得到时间最优路径。

利用当前点(xm,ym)、父节点(xm-1,ym-1)和子节点(xm+1,ym+1) 、目标终点(xend,yend) 的位置关系，通过公式（1）与公式（2）可判定AGV行驶方向。

当公式（1）与公式（2）计算数值相等时，AGV直行，否则发生转向。根据行进方向修证：

其中，k 为转向修正系数，确保AGV优先选择直行。

将转向修正后的理论路径储存到走位路径容器Q(s1,s2,…,send)中，并建立如图5 所示存储AGV 父站位sm-1、当前站位sm和子站位sm+1的动态走位表P(sm-1,sm,sm+1)实时更新AGV 实际行驶路径。判定AGV 预计行驶方向时将容器Q 首位站点传入sm+1，若预计行驶方向不变则sm+1为初始传入值，并移除容器Q 首位站点；否则sm+1更新为sm值，AGV 原地转向或暂停，容器Q暂不改变。

图5 动态滑移表

3.1.2 优先级自动调优

对于两辆AGV间的相互作用关系可以较容易判断出如图3的三种状态。但实际作业环境中随着AGV数量的增加，很难进行冲突的有效划分，以图6多AGV间相互作用关系为例。预计AGV3 与AGV4 将会发生冲突，若AGV3 的优先级高则只需AGV4 重新规划路径，而若AGV4 的优先级高则AGV1～AGV3 都需要重新寻路，AGV的优先级顺序将直接影响整体的路径规划代价。

图6 多AGV间相互作用关系

因此建立一个初始状态只存储当前AGV序号的链表L(vcurr)，通过如图7 所示AGV 指向链表判定规则完成链表L(vcurr→vnext1→…→vend)的更新，并通过链表自动调节AGV执行任务优先级，使解决冲突代价最小。

图7 AGV指向链表判定规则

3.1.3 算法流程

被动式自调优A*路径规划算法的流程如图8所示，具体步骤如下：

步骤1 分配调度任务，并启动调度系统。

步骤2 系统根据制定规则，有选择地将任务分配给空闲AGV，各AGV获得需要执行任务的始末站点位置及类型的信息。

步骤3 根据任务信息及地图实时位置信息规划路径为空的执行状态AGV 的理论最优路径，并将规划后路径存入预约走位路径容器Q 内。

步骤4 根据行进方向规则与各AGV的走位路径容器内的路径信息，更新走位表P 的实时信息。

步骤5 按链表L 规则调节AGV 优先级，优先更新可走无碍AGV 操作状态为已完成，并清空存在冲突的AGV预约走位路径容器Q 内位置信息，跳转到步骤3，直至所有AGV状态信息为已操作。

步骤6 各AGV 根据对应走位表P 信息完成相关行驶操作，并更新各预约走位路径容器Q 内信息，重置所有AGV为未操作状态。

图8 被动式自调优A*路径规划算法

步骤7 判断各AGV 任务完成状态，完成当前任务的AGV 标记为空闲状态，等待分配新任务。存在未完成任务的AGV 或系统内有未分配的任务存在则从步骤2开始重复执行操作，直至所有AGV完成任务，且系统内无新调度任务，终止所有调度。

3.2 多步前瞻算法

3.2.1 启发函数确定

路径规划算法层面上，无论是否考虑了转向修正，工程中都要考虑转向的实现，并不会增加系统硬件层面上的困难程度，因此转向修正更多考虑的是实施必要性。由于只需对代价相同的备选节点进行修正，计算时间的增加极少，远远小于拓扑地图中相邻节点的奔赴代价，减少多次转向的路径时间代价反而更优，缩短了任务完成时间，提升了系统整体效率。

一般来说，启发函数常采用曼哈顿距离、对角线距离、欧几里德距离和平方后的欧几里德距离等方法[23]。这些方法各有优缺点，针对具体模型，本文是在考虑了转向修正基础上进一步研究。

在考虑转向修正后，利用曼哈顿距离法一般可获得较少转向的路径，但当临近目标终点时，如图9（a）所示，AGV从右侧驶入路口，预测上、左两节点代价相同，进行修正后选择直行，可能导致局部绕行；其他方法如图9（b）所示欧式距离法，在邻近目标点时，不需要修正或修正后最优路径代价依然最小，可避免绕行，但需要更长的求解时间，且在远离目标点时，修正系数过小而常起不到修正作用，虽仍优于一般算法，但转向次数依然有所增加。

图9 不同启发函数搜索路径

针对以上问题，提出了考虑转向代价修正的曼哈顿距离与欧几里德距离融合方法，在远离目标站点的位置采用曼哈顿距离方式提高运算效率减少转向次数，在临近目标终点位置采用欧几里德距离方式避免绕行。

其中，k为方向修正系数。当|xend-xm+1|＜4 或|yend-ym+1|＜3 时，H(m+1)计算方法为公式（4），其他情况通过公式（5）计算。

3.2.2 冲突预测及路径拟合

由于动态路网全局信息实时变化，搜索出的理论最优路径会由于扰动而失效。此方法在寻路过程中不需要获得完整路径，只需补算前k 步路径，储存在多步位置信息地图链表M(m0,m1,…,mk-1,mk) 中用于判定AGV间位置关系，如图10所示除m0表用于存放当前地图AGV 位置及站位信息外，其他各表用于存储前瞻k步的趋势位置信息。

图10 位置信息地图链表

冲突预测及路径拟合以图11 为例，随机生成一段普通移位任务，初始状态时（图11（a））预计无冲突，随着AGV 行进在预测步内突然出现故障AGV（图11（b）），选择不增加代价的无冲突路径（图11（c））继续行驶，通过逐步迭代拟合方式（图11（d）至图11（f））得到完整路径。

图11 冲突预测及路径拟合过程

所谓不增加代价的无冲突路径选择，并非路径整体拟合后相比无冲突路径代价不增，而是基于当前路况信息进行计算，体现在三方面：第一，优先选择不增加路径代价或少量增加转向次数的趋向目标的通畅路径；第二，无通畅路径时选择少绕行或等待时间最少路径；第三，从概率的角度对同代价路径进行判别，选择后续更少出现冲突的路径。

3.2.3 算法流程

其操作方法如图12所示，并给出相应操作方法：

步骤1 启动系统并加入调度任务。

步骤2 分配任务给空闲AGV。

步骤3 针对未操作状态的AGV根据地图链表信息及其不可访问站点状态按搜索规则补齐路表中站位点数量少于k 步的缺失点位。

步骤4 顺序访问未操作状态的AGV，判断对应路径表走位的可通行状态。更新可通行AGV对应位置信息地图链表上位置信息并标记已操作状态，对于出现障碍的AGV，回溯路径至无冲突长度并设置该AGV不可访问的站点并返回步骤3。

步骤5 全部AGV 状态都为已操作状态后，发送信号，传递给各AGV 行进站位信息，并重置其操作状态；否则返回步骤4重复执行。

步骤6 标记到达目标终点AGV 为空闲状态，对于无空闲AGV的情况，返回步骤4重复执行，出现空闲车辆并有未分配任务存在则返回步骤2重复执行，AGV全部空闲并无闲置任务则停止调度系统。

3.2.4 算法总结

被动式自调优A*路径规划算法，属于被动式冲突解决方案，在运行过程中，由于意外路径可能会失效。因避障而重新规划路径容易导致非必要绕行，并且会造成未达路径的计算量浪费。

对于提出的趋向终点的主动式多步前瞻算法，这是一种增量式的路径规划算法，通过迭代方式逐步拟合出完整路径，由于事先不需要规划全部路径，重新寻路时减少了计算损失。

前瞻步数被确定为至少可以预测两个直行路口或半个货架回环，可防止死锁或陷入局部最优解，又不至于过多增加计算量。在不发生冲突的情况下，拟合路径与最优静态算法一致，保证了完整路径的最优性。预测冲突或拥堵时，主动选择代价较小和更通畅路径。

由于该算法综合考虑多AGV 协同工作，因此路径规划的前提是整体最优而非某几辆AGV局部最优。增量寻路过程中结合实时信息和前序路况信息，在不过多增加路径代价的前提下，主动选择更小可能重新寻路的路径。

4 仿真结果分析

4.1 仿真环境

采用QT 图形化工具作为开发环境，利用C++语言开发出一种用于仓储多AGV路径规划的仿真平台。用户可根据需要自由添加任务，选择路径规划算法，配置AGV 数量，实时显示行程状态，可查任务执行日志，仿真界面如图13所示。

图13 路径规划仿真平台

4.2 路径规划算法分析

为了直观比较不同算法效果，利用3 辆AGV 随机分配普通移位任务进行对比，并给出任务信息如下：

T{s1,e1}，其中s1=(4,7),e1=(18,7)

T{s2,e2}，其中s2=(16,7),e2=(2,4)

T{s3,e3}，其中s3=(13,10),e3=(5,2)

图14为单AGV理论路径，换言之就是各AGV在忽略其他动态车辆下的路径规划。多AGV若采取此种规划路径行驶，AGV1 与AGV2 将在（10，7）处由于同时占位发生碰撞，AGV2 与AGV3 将在（13，7）与（5，4）两处碰撞。

图14 单AGV理论路径

图15 为多AGV 动态路径规划算法。自调优A*算法预测AGV1与AGV2在（10，7）位置产生冲突，动态调整优先级，使AGV1保持直行而AGV2掉头，AGV2增加了一定绕行距离；AGV2与AGV3预计在（13，7）处发生冲突，AGV2 获取更高优先级而率先通过，AGV3 等待AGV2 通过后继续行驶。多步前瞻算法提前k 步进行前瞻性预测，针对（10，7）处可能发生冲突，AGV2 在上一路口提前转向，避免绕行，AGV3 预测到左行路段繁忙，改为上行避开拥堵路段。

图15 防止冲突的多AGV路径规划

各种算法的对比分析如表1，可以发现单独应用静态算法无法解决冲突问题，而两种动态算法都实现了无冲突的路径规划，多步前瞻算法无论是单项指标还是总体代价都优于自调优A*算法，接近或优于单AGV理论最优路径。

4.3 性能评价

AGV系统的研究并没有统一的评价标准。多数研究者在研究AGV 数量配置时会引入AGV 的利用率进行评价，对于本文所涉及仓储系统而言，任务类型多样，随着AGV 数量的增多系统愈发复杂，规划路径长度动态可变，单独运用AGV 利用率评价并不客观。故针对仓储系统抽象后，提出如下评价指标：

表1 不同路径规划算法对比

（1）空行比：AGV 总空载代价与AGV 总行进代价之比，空行比的数值越小，额外代价也就越小，效率越高。

（2）平均行进时间：AGV完成所有任务的平均行进耗时。

（3）任务总耗时：系统完成全部任务的最大系统耗时。

（4）总运算次：各AGV每同时完成一次站位更新视为一步，完成全部任务时的计算步长为总运算次。

随机生成150 组离散的出/入库任务，并选取最多32 辆AGV，采用顺序分配任务方式对两种路径规划算法进行仿真。

AGV执行任务的先后顺序会对系统的整体性能造成影响，图16 为150 个任务下，两种算法的空行比关系对比，根据仿真结果不同数量AGV 两种算法的空行比趋于稳定，波动不大，用以衡量任务对AGV 分配的均衡性。

图16 空行比关系

图17为AGV完成每个任务的平均时间，随着AGV数量的增多，交通状况繁忙而导致平均任务完成时间呈上升趋势。图18为两种算法任务总耗时与总计算次的关系，它们的总体趋势相同。

图17 平均任务完成时间关系

图18 任务总耗时与总计算次关系

图19 为两种算法效率对比，从任务的平均计算时间上来看，由于多步前瞻算法引入了冲突提前判断机制，在计算时间上有所增加，但最多仅增加54.3 ms，在非拥堵路段计算时间甚至有所降低。但是从任务的总耗时的角度来看，多步前瞻算法极大节省了任务完成时间，最大提前完成率甚至达到41.63%。

图19 两种算法效率对比

对比自调优A*算法与多步前瞻算法。将无冲突时理论最优路径的平均任务完成时间视为基值，前者的基值不仅要略高于后者7.96%，而且平均任务完成时间的增速是后者的2.47 倍。同一仓储环境，随AGV 的数量增多，系统的全部任务的完成时间会随AGV 增多逐渐减少至最小值后平缓上扬，后者最小完成任务耗时仅相当于前者54.40%。

AGV 系统的小车数量配置是综合了AGV 系统的投入成本以及生产系统因为AGV 系统服务水平下降造成生产损失成本所综合后产生的最优解[24]。本文仅从整体总耗时角度分析，自调优A*算法在19辆AGV时达到完成耗时最小，而多步前瞻算法可以持续增加AGV数量提高系统性能，在30辆AGV时达到最优。关于本系统理论上的全局最优AGV数量配置还要结合实际系统各方面成本综合考虑。

5 结束语

针对仓储系统多AGV 路径规划问题，结合实际需求，提出了两种路径规划算法。自调优A*算法在满足系统实时动态规划需求及解决AGV可能存在冲突的前提下，在路径规划方面考虑了转向代价，所规划理论路径减少了AGV不必要转向，不仅距离最优，而且时间开销更小；预测启发式算法在路径规划方面性能更好，且具备前瞻性冲突判断功能，可提前预测可能发生冲突，提前选择非拥堵路段通行，极大减少了绕行距离，使多AGV整体性能最优。