基于改进蚁群算法的多AGV泊车路径规划

郭保青，郝树运，朱力强,b，余祖俊,b

(北京交通大学a.机械与电子控制工程学院；b.载运工具先进制造与测控技术教育部重点实验室，北京100044)

0 引言

随着我国汽车保有量快速增长，城市交通拥堵、停车难等社会问题日益突显，严重影响了人们的出行质量.为解决停车难问题，新技术不断涌现，其中基于AGV的平面智能停车库以占地面积少、存车数量多、车辆存取自动化程度高等优点倍受关注.

AGV存取车辆的路径规划是研究平面智能停车库的核心，其任务是为每台AGV从预存停车位到目标停车位寻找一条最优无碰路径，有序完成所有路径规划任务.近年来，国内外学者针对路径规划问题做了大量研究.文献[1]采用双层模糊逻辑路径规划算法，考虑障碍物距离信息与目标角度信息，通过改变速度提高避碰效率，但不能保证为多机器人规划出全局最优路径；文献[2]采用多人工鱼群算法在静态环境中规划出较优路径，根据避碰规则库实现与动态障碍的避碰；文献[3]提出结合AGV路径容量、安全距离的多参数优化控制模型，通过改进的速度控制策略解决冲突.蚁群算法是一种新型仿生算法，凭借并行性、强鲁棒性、全局最优等优点[4]广泛应用于路径规划问题[5-7].许多学者对基本蚁群算法进行了优化，文献[8]将蚁群算法与遗传算法融合，在蚁群算法中引入改进的交叉算子来避免陷入局部最优；文献[9]提出基于势场优化的蚁群路径规划算法，用势场法路径预规划获得的先验知识构造信息素矩阵，采用参数自适应的伪随机转移策略优化蚁群算法；文献[10]利用人工势场法重构启发函数提出的改进势场蚁群算法收敛速度较快，但容易陷入局部最优.

针对基本蚁群算法容易陷入局部最优和收敛性差的问题，本文提出适用于多AGV路径规划的改进蚁群算法.本文根据典型地下停车库抽象拓扑模型，引入蚂蚁回退策略来增强算法鲁棒性，通过改进启发式信息和信息素更新策略提高全局寻优能力.针对多AGV冲突问题，通过改进冲突解决策略进行局部避碰.仿真结果验证了单AGV情况下改进蚁群算法的性能，并在此基础上完成了多AGV路径规划算法效率和实时性的验证.

1 问题分析及环境建模

典型地下停车库一般分开设置出入口，由于受建筑附属设施影响，部分车位位于非连通路的端点，即存在部分“死路”.为提高吞吐效率，AGV智能停车场可将所有出入口规划为同时出入；为增加停车面积，可将AGV行驶路径规划为双向单车道，同时只允许一个方向的AGV通行.改造后的AGV停车场一般具有如下典型特征：

(1)有两个同时出入的出入口；

(2)通道为双向单车道，允许多台AGV同向行驶，但同时只能有一个方向的AGV通行；

(3)有大量位于非连通路端点的车位；

(4)规划的路径起点或终点必然包含一个出入口；

(5)各AGV被视为质点，每台AGV设有相应安全区域，行驶速度相同，转弯耗时为常数.

基于以上特征，采用拓扑法对某典型地下停车库抽象的AGV停车库模型如图1所示.该模型由节点和线段组成，圆节点代表交叉路口或路径端点，矩形节点代表出入口，线段表示停车库中的路径，虚线为停车场边界.AGV运行路径采用有序节点集合表示，节点顺序表示运行方向.多AGV泊车路径规划既要保证各AGV互不冲突，又要使每台AGV行驶时间最短.

图1 AGV车库拓扑图Fig.1 Topological graph of AGV garage

2 基于改进蚁群算法的AGV路径规划

2.1 基本蚁群算法

蚁群算法是一种典型的路径规划算法，主要依靠蚂蚁之间的信息传递来寻找最优路径.寻路过程中，蚂蚁通过感知环境信息，并按照既定规则来规划路径，最终以一定的评价指标找到起止点间的最优路径.

(1)转移概率.

一般情况下，周围环境是未知的，蚂蚁需要根据转移概率Pij来确定下一步要走的路径.设蚂蚁数量为M，位于节点i处的蚂蚁m(m=1,2,…,M)在t时刻选择节点j的概率为

式中：τij(t)为t时刻路径(i,j)上的信息素浓度；ηij(t)为路径(i,j)在t时刻的启发式信息强度，通常ηij=1/dij，dij为节点i,j间的距离；α，β分别为信息素浓度和启发式信息强度的影响权重；allowed为下一步允许选择的节点集合.

(2)信息素更新.

蚂蚁经过路径时会留下信息素，随着时间推移，信息素会逐渐挥发消逝.每代蚂蚁完成路径搜索后，会按式(2)～式(4)更新信息素.

式中：ρ为信息素挥发系数；Δτij(t,t+1)为本次循环中路径(i,j)上的信息素增量；Mij为本次循环中经过路径(i,j)的蚂蚁集合；为第m只蚂蚁在路径(i,j)上产生的信息素增量；Lm为第m只蚂蚁在本次循环中搜索的路径长度；Q为常数.

2.2 改进蚁群算法

(1)蚂蚁回退策略.

蚂蚁在搜索路径时总是以所处节点为中心选择下一节点.由于AGV运行环境有较多不连通路径，蚂蚁在搜索路径时可能陷入其中而导致搜索异常终止.为避免此类情况，加入蚂蚁回退策略来提高算法鲁棒性.如图2所示，蚂蚁搜索从S点到E点的路径，在搜索过程中陷入D点，此时蚂蚁未完成路径搜索而又无法找到下一节点，于是采取回退策略将蚂蚁置于前一节点F，并更新禁忌表，使此轮蚂蚁无法再搜索到D点.

图2 蚂蚁回退策略示意图Fig.2 Schematic diagram of fallback strategy

(2)启发式信息.

在基本蚁群算法中，蚂蚁在搜索路径时是以所处节点与相邻节点距离的倒数为启发式信息，路径搜索盲目性较大.为提高算法寻路速度，本文以蚂蚁所处节点与终点距离的倒数作为启发式信息，提高蚂蚁对终点的可见度，如式(5)所示.

式中：E代表终点；P代表蚂蚁所处节点.

(3)信息素更新.

基本蚁群算法搜索路径时受非最优路径信息素的干扰可能陷入局部最优.针对此问题，本文以原有信息素更新策略为基础，对每次迭代的最优路径释放更多信息素，对最差路径减少部分信息素.改进的信息素更新公式为

式中：Nb和Nw分别为经过本次迭代最优和最差路径的蚂蚁数量；Lb和Lw分别为本次迭代最优和最差路径的路径长度.

3 改进AGV冲突解决策略

3.1 AGV冲突类型

多AGV路径规划是要保证在系统无冲突情况下为每台AGV规划出1条最优路径，根据前面模型，多AGV运行过程中会出现图3所示的几种冲突情况.

图3 AGV冲突情况Fig.3 AGV conflict situation

图3(a)中2台AGV同时到达同一节点，又分别驶向不同的方向，2台AGV会在节点处发生碰撞，称为节点冲突.

图3(b)中，若 AGV1的速度大于 AGV2，AGV1会在运行过程中撞到AGV2，称为赶超冲突.

图3(c)和图3(d)中2台AGV相向行驶并发生碰撞，称为相向冲突.

3.2 改进AGV冲突解决策略

为避免上述冲突，需要制定冲突解决策略.当AGV按照各自预定路径行驶而遇到冲突时，采用对应策略协调各自的运动.

(1)停车等待策略.

对于节点冲突及赶超冲突，采用停车等待策略进行解决.当发生冲突时，1台AGV停车等待，而另一台AGV继续行驶.而针对不同冲突，解决方法稍有不同：

对节点冲突，可通过规定优先级来解决，当多台AGV同时到达同一节点时，优先级高的AGV优先通过.

对赶超冲突，可通过设定安全距离来解决，当后方与前方AGV距离小于安全距离时，后方AGV暂停行驶.

(2)临时规避—重新寻路策略.

对相向冲突，除避碰问题外还要考虑冲突解决的合理性.传统的重新寻路算法虽能解决相向冲突，但在某些情况下严重影响任务完成效率，甚至会引起新的后续冲突.

为弥补重新寻路算法的不足，本文提出临时规避—重新寻路策略来解决相向冲突.当AGV到达某一节点且要行走的下一路径存在与之相向冲突的AGV时，当前AGV根据不同情况选择临时规避或重新规划该节点到终点的路径.若AGV所处节点路口数大于2，且AGV临时规避的等待时间与原剩余路径的运行时间之和小于重新规划路径上的运行时间，则选择临时规避措施；否则，选择重新规划该节点到终点的路径.临时规避—重新寻路策略流程如图4所示.

图4 临时规避—重新寻路策略流程Fig.4 Temporary avoidance and re-planning strategy flow chart

4 仿真实验

4.1 单AGV路径规划仿真

(1)主要参数优化.

目前蚁群算法一般通过经验选取参数，本文通过在参数变化范围内设置不同的参数组合，并对每个参数进行10次仿真，将求得的路径长度均值进行对比来选取最优参数.主要测试参数为：α∈{0 .0,0.5,1.0,2.0,5.0},β∈{0,5,8,10,15},ρ∈{0.0,0.3,0.5,0.8,1.0} ，其中默认值设为α=1.0，β=10，ρ=0.5，每次实验只改变1个参数，其余为默认值，结果如表1所示.

表1 参数优化结果Table 1 Parameter optimization result

由表1可以看出：α最优值在1.0附近，β最优值在10附近，ρ对算法影响较小，在0.8附近最优.基于以上结果，本文对基本蚁群算法和改进蚁群算法进行仿真测试时，各参数设置如下：迭代次数k=100，蚂蚁数量M=50，α=1.0，β=10，ρ=0.8.

(2)寻路成功率对比.

由于不连通路径会导致寻路失败，可以通过寻路成功率来比较算法性能.图1拓扑图共有46个节点，其中2个为出入口，44个为交叉路口或路径端点.现分别以2个出入口为AGV任务的起点或终点，44个节点分别为另一点，对比两种算法的寻路成功率，结果如表2所示，其中寻路成功率计算公式为

表2 寻路成功率比较Table 2 Comparison of path finding success rate

表2基本蚁群算法中，以S1分别为起点和终点的寻路成功率为59%和64%；以S2分别为起点和终点的寻路成功率为64%和70%.而无论何种情况，改进蚁群算法的寻路成功率均为100%.由此可见，改进蚁群算法有较高的鲁棒性.

(3)寻路质量及算法收敛性比较.

为了全面客观地验证改进蚁群算法的性能，本文在基本蚁群算法中加入回退策略(称为回退蚁群算法)，与改进蚁群算法进行寻路质量及算法收敛性比较.本文通过在停车库随机选取3个内部节点与出入口组成3组路径任务进行仿真.图5为两种算法得到的最终路径和平均路径长度收敛曲线，实线和虚线分别代表回退蚁群算法和改进蚁群算法.表3列出了两种算法得到的具体路径数据和算法耗时，由图5及表3可以看出改进蚁群算法得到的路径更短，收敛速度更快.

表3 寻路质量及算法收敛性比较Table 3 Comparison of path quality and algorithm convergence

(4)算法复杂度分析.

算法复杂度主要包括时间和空间复杂度.时间复杂度是指算法执行基本操作的次数，由于本文对蚁群算法的改进主要在启发式信息、信息素更新和增加回退及避碰策略上，改进和基本蚁群算法在时间复杂度上都为T(n)=O(k∙n2∙M)，具有相同的量级.因此，本文采用算法编译运行时间来评估算法时间复杂度，由表3的耗时可以看出，改进算法有较高的执行效率.

空间复杂度是指算法执行时间内占用的存储单元.改进算法中的数据包括用来描述问题和实现算法功能的辅助数据，空间复杂度为S(n)=O(n2)+O(n∙M).实际应用中，停车场环境信息使用数据文件存储，数据格式非常简单，占用存储空间很少，空间复杂度很低.

图5 路径任务和算法收敛曲线Fig.5 Pathing task and algorithm convergence curve

4.2 多AGV路径规划仿真

将改进冲突解决策略与冲突判别条件相结合编制成多AGV路径规划算法.为了验证算法性能，本文以相向冲突为例对3个AGV进行仿真，并与重新寻路算法进行比较.仿真前，用改进蚁群算法为每台AGV规划出起止点间的最优路径.为方便观察路径冲突情况，以时间窗来表示AGV路径占用情况.设AGV同时从各自起点开始行驶，仿真结果如图6所示.

图6结果分别表示避碰前、重新寻路和本文避碰算法3种情况下3台AGV的路径图及对应时间窗，其中AGV1运行在1→17的路径上，AGV2运行在40→2的路径上，AGV3运行在2→43的路径上.图6中，初始路径在(28,29)上发生相向冲突；为避免冲突，重新寻路算法以节点29为起点重新规划到终点的剩余路径；本文算法则将AGV2临时停靠在路径(29,30)且靠近节点29的29(P)位置.3种方法的对比如表4所示，原始路径由于存在相向冲突，无法完成相应任务，故表4中任务时间和算法耗时均为空；重新寻优算法虽然能够实现冲突后路经的重新规划，但任务时间较长；而本文算法在任务完成时间和算法耗时上都由于重新寻优算法，不仅能有效避免冲突，规划的新路径也更合理，算法效率更高.

表4 多AGV路径规划算法性能比较Table 4 Multi-AGV path planning algorithm performance comparison

图6 多AGV路径及时间窗Fig.6 Multi-AGV path and time windows diagram

5 结 论

针对智能停车库多AGV泊车路径规划问题，本文提出了基于改进蚁群算法的多AGV泊车路径规划算法.仿真实验表明，本文算法在效率和性能上相比基本蚁群算法均有提高，不仅能为单AGV规划出1条无碰优化路径，而且能在多AGV同时运行的情况下避免冲突，满足AGV存取车路径规划的需要.下一步计划在此基础上研究停车位优化布局方法和AGV数量与停车效率的关系，为智能AGV停车场设计提供指导.