基于改进蚁群算法的智能小车路径规划方法

胡立华，马 瑞，张名师，左威健

(太原科技大学计算机科学与技术学院，太原 030024)

路径规划一直是智能机器领域的研究热点，其任务就是在具有障碍物的复杂环境内，依据耗能最少、路径最优、时间最短等评价标准，寻找一条从起始点到目标点无碰撞的最优路径[1]。路径规划方法主要有传统算法和智能算法两种，相较于传统算法，智能路径规划算法具有运算速度快、总体效率高的优点。经典的智能路径规划方法有：人工神经网络算法[2]，遗传算法[3]，粒子群算法[4]，蚁群算法[5]等，其中由意大利学者 Dorigo 等人提出的蚁群算法对路径规划具有良好的全局优化能力，且在实际路径搜索中能对外界做出动态响应。

基于蚁群算法的路径规划典型的工作有：游晓明等人[6]提出动态搜索诱导算子，有效提高优化解的质量；屈鸿等人[7]通过调整转移概率限定信息素强度的上下界，提高算法的全局搜索能力；汪杰君等人[8]提出了一种基于混合遗传蚁群算法的测试路径规划方案，提高了测试模型转化的效率；王志中[9]设置了信息素感应阈值，扩大了算法前期的搜索范围；张成等人[10]引入障碍物排斥权重和新的启发因子到路径选择概率中，提高避障能力,增加路径选择的多样性；谢智慧等人[11]提出采用动态调整启发因子、改进信息素初始化策略，提高了算法前期搜索效率等。但是在实际应用过程中，针对环境复杂性、障碍物频繁的智能小车路径规划仍存在收敛速度慢、工作效率低的缺点。

因此，本文以树莓派智能小车为对象，针对智能小车行驶在障碍物频繁的环境中路径规划收敛速度慢等问题，提出了一种基于全局动态路径规划的改进蚁群算法。该方法首先采用不均匀分配初始信息素原则，避免经典蚁群算法蚂蚁走回路的问题；其次修改路径上启发信息，为后续蚂蚁的路径选择提供依据；然后优化经典蚁群算法中局部信息素和全局信息素的更新方式，加快路径规划算法的收敛速度；最后在经典算法的转移概率中增加邻域安全因子避免死锁，提高算法的优化效率。

1 经典蚁群算法

经典蚁群算法的路径规划是模仿蚂蚁觅食寻找最优路径的过程，具体流程如下：

1)初始化假设蚂蚁数量为num及信息素；

2)蚂蚁在栅格地图中移动，释放定量的信息素q，称为初始信息素；然后蚂蚁根据启发信息随机选择位置向目标点移动，启发信息定义为：

其中：d(i,j)表示i与j点之间的欧氏距离。allowk表示当前蚂蚁k可以选择的下一个目标点的集合。

3)所有蚂蚁完成一次迭代后对该路径上残余信息素进行更新，则t+1时刻在路径(i,j)上信息素更新为：

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1)

其中，ρ表示信息素的挥发系数，且ρ的取值范围为(0，1)；τij(t)表示在t时刻路径(i，j)上的信息素浓度。Q是一个定值表示信息素的总量，在一定程度上影响算法收敛速度；Lk表示本次循环中，蚂蚁k所经过的路径的长度。

4)状态转移概率公式如下：

其中，α为输入的信息素启发因子；β为期望启发因子。

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

在目标路径规划过程中，基于蚁群算法的智能小车路径规划过程主要分为两个阶段：1)环境建模：目的是建立一个便于计算机进行路径规划所使用的环境模型；2)路径规划：在环境模型基础上，迭代蚁群算法寻找一条目的路径，且该路径距离最短、耗时最少、效率最高。

2.1 环境建模

目前，进行环境建模的方法主要有几何法[12]、可视图法[13]、单元分解法[14]和栅格法[15]等。其中栅格法搜索路径唯一、操作简单、发现路径能力强、便于更新维护，更适用于寻找智能小车的最优路径。

在环境构建过程中，设初始化智能小车的工作空间为二维矩形平面区域，区域范围为R(X,Y).在栅格图中，栅格宽度的设置对构建地图及规划路径影响很大。针对智能小车，若栅格宽度过大，环境信息量小，算法运行时间短，路径规划能力弱；若栅格宽度过小，环境信息量大，算法运行时间长，路径规划较强。因此，栅格的宽度大小若刚好能容纳智能小车，更易模拟小车的路径规划。

设小车宽度为w，将工作环境区域R划分成大小相等的n个栅格ri，对划分好的每一个栅格ri按从左到右、从上到下的顺序进行编号，并建立相应的无障碍区域的存储表allow、障碍区域的禁忌表Tabu，如图1所示，白色为无障碍栅格，黑色为障碍栅格。因为障碍物形状大小不一，所以当有障碍区域所占据的栅格不满一格时，则以占一个栅格处理。栅格ri每次移动一个步长(一个栅格为一个步长)，且移动后的栅格rj为栅格ri中allow的栅格，如图2所示。

图1 环境地图建模Fig.1 Map modeling

图2 栅格ri的可行路线Fig.2 Possible routes for grid ri

2.2 改进蚁群算法

2.2.1 初始信息素不均匀分配

图3 初始信息素分配图Fig.3 Initial pheromone distribution

L：Ax+By+C=0

(1)

虚拟路径对蚂蚁的全局行走方向具有指导作用。根据蚂蚁所在栅格距虚拟路径的距离对该栅格进行信息素的分泌，分泌规则如下：

(2)

其中，q为信息素均匀分配的初始量，ij表示由栅格i移动到j，(i，j)表示栅格i到栅格j之间的路径，假设栅格j的坐标为(xj,yj)，d为蚂蚁在栅格j时的坐标值到虚拟路径的距离，根据距离d的大小来确定栅格i到栅格j的初始信息素的分配，则距离计算公式如下：

(3)

蚂蚁的全局路径规划往往是一条从起始点到目标点的非闭合路径，因此改进的初始信息素不均匀分配有利于提高算法的收敛速度。

2.2.2 调整距离启发函数

启发函数ηij(t)表示在t时刻i点相对于j点的可见度，两点之间的距离越近，对蚂蚁的下一个目标点的选择影响越大。然而，在经典蚁群算法中相邻栅格的启发权值差异不明显，算法的搜索效率比较低[16]，因此依据已知目标点的位置，可对目标点的邻域栅格赋予不同的启发权值，即按比例为1∶2∶2∶3∶3∶4∶4∶5进行调整。调整后的启发函数提高了搜索速度，加快了路径选择的准确性。启发函数可定义为：

(4)

其中，λ为启发系数，col为所建立的栅格地图的列数。

2.2.3 信息素的更新规则

为了保证高浓度信息素在较短路径上，低浓度信息素在较长路径上，对信息素更新过程可修改为：假设蚂蚁数量足够多，上一次迭代过程中找到的最短路径为Lh，下一次迭代过程中找到的路径集为Lg，且与上一次最短路径比较，如果有路径比上一次的最短路径短，则更新本次迭代中的最短路径为最短路径；如果没有路径比上一次的最短路径短，则上一次的最短路径仍为本次迭代的最短路径。记经挥发后残余信息素系数为ζ，则有：

(5)

其中，Lc为当前迭代路径集Lg中的随机一条路径。则局部信息素的更新改进为：

(6)

全局信息素的更新为：

(7)

不同路径长度信息素的残余系数不同，信息素的更新数量也不同，在初始信息素的局部和全局更新的驱动下，路径越短，该路径积累的信息素就越多，对后续蚂蚁的路径选择具有很大的驱动作用，提高了算法的收敛速度，避免蚂蚁陷入局部最优。

2.2.4 改进转移概率

在复杂的地形环境中障碍物过多，蚂蚁遍历邻域栅格时会出现重复遍历障碍物栅格，导致耗时长，蚂蚁陷入死锁状态，因此文献[8]提出的死锁时回退一步方法，有利于蚂蚁减少在同一个区域内陷入死锁的概率，但是对于复杂环境频繁回退情况增加了算法的搜索时间，降低了算法的效率。本文利用蚂蚁的邻域安全作为蚂蚁概率转移的重要因素，假设栅格j的邻域为neighbourhood，障碍物栅格为barrier，以遍历的栅格为traverse，则邻域安全为Nsafety定义为：

增加邻域安全因子后的状态转移概率为：

其中，ω为邻域安全权值，迭代一定次数后尽管j点的邻域已大多数遍历或为障碍物栅格，但在迭代未收敛之前，栅格仍为可通行的。

2.2.5 改进后算法实现流程

步骤一：初始化：输入智能小车的环境信息建立栅格地图R，初始化allow表和tabu表,设置蚂蚁的数量num，为最大迭代次数max，及参数值α、β、ω、ρ、ζ等。将蚂蚁放在栅格地图的起始位置start处，开始蚁群算法的迭代。

步骤二：蚂蚁在移动过程中每搜到一个栅格点，就将该栅格点加入tabu表中，从表allow中删除该栅格点，根据公式(1)-(3)对信息素进行初始不均匀分配，在启发函数公式(4)的作用下对路径进行选择，完成一次路径选择后通过公式(5)-(7)对该路径上的信息素进行更新；然后记录蚂蚁从起始点走到终止点的路径长度。并选出当前路径中的最优路径，一次迭代完成。

步骤三：蚂蚁再次迭代，根据改进的状态转移概率公式(8)确定蚂蚁从当前点要移动到的下一个目标点，蚂蚁每次移动更新tabu表和allow表。

步骤四：蚂蚁完成路径选择后，淘汰未到达目标点的蚂蚁，更新路径上信息素浓度，记录路径长度信息，找出最优路径，如果当前最优路径优于步骤二中的最优路径，则更新当前路径为最优路径，否则，步骤二中的路径仍为最优路径，继续迭代。

步骤五：设置迭代阈值θ，当迭代次数T<θ时，蚂蚁的路径长度不在发生变化，则迭代收敛；当θ

步骤六：保存最优路径信息，算法结束。

3 实验结果与分析

为了验证算法的有效性，本节模拟了不同规模和不同复杂度的环境地图进行了两组仿真实验。第一组仿真实验在25*25的环境下，比较了对本文算法、文献[17]的算法和经典蚁群算法的路径规划结果；第二组仿真实验在30*30的环境下，采用本文算法和经典一群算法进行仿真结果比较。算法运行环境为WINDOWS 10 64 bit；MATLAB R2016a；处理器i5-4210U CPU；内存4 GB.仿真实验均使用Matlab语言。

3.1 仿真实验一

首先随机建立规模为25*25环境地图，表1为本文方法和文献[17]算法、与经典蚁群算法的参数设置。

表1 参数设置Tab.1 Parameter setting

然后对本文算法、经典蚁群算法和文献[17]中的算法进行仿真实验，其中路径规划起始位置可设置为：起始点为图4的左上角，终止点为图4的右下角。共进行100次实验得到的最优路径如图4所示，路径迭代收敛曲线图如图5所示。

图4 路径规划结果对比图Fig.4 The comparison of path planning results

图5 算法收敛曲线对比图Fig.5 The comparison of algorithm convergence curve

最后对三种算法的最优路径长度、迭代收敛次数、拐点数、平均消耗时间进行了对比。对比结果如图4-图5所示。

从图4中可以看出，本文算法的最优路径最短，拐点最少；从图5中可以看出，本文改进算法的迭代次数最少，收敛速度更快，具体的路径规划结果如表2所示。

表2 实验结果对比Tab.2 The comparison of experimental results

从表2中可以看出：本文提出的改进蚁群算法有效缩短了路径搜索所需要的时间，并且找到了比经典算法和文献[17]更优的路径，从而验证了本文算法的有效性。

3.2 仿真实验二

第二组仿真实验，随机建立规模为30*30环境地图，设置本次实验算法中所需要的各个参数值如表3所示。

表3 参数设置Tab.3 Parameter setting

与仿真实验一采用相同的步骤进行100次实验后找到的最短路径和蚂蚁的迭代次数如图6-图7所示。

图6 路径规划结果图Fig.6 The comparison of path planning results

图7 算法迭代收敛曲线图Fig.7 The comparison of algorithm convergence curve

从图6中可以看出，本文改进的蚁群算法的最优路径最短，拐点最少；从图7中可以看出，本文改进算法的迭代次数最少，收敛速度更快，具体的路径规划结果见表4.

表4 实验结果对比Tab.4 The comparison of experimental results

由表4可以看出：在起始点和终止点坐标相同的情况下，改进的蚁群算法最优路径短、平均消耗时间少、收敛速度快。

综合3.1与3.2的结果，可知针对复杂环境下的路径规划，本文算法在迭代次数更少、收敛速度更快，所搜索路径更稳定。

4 结束语

本文针对基于经典蚁群算法的路径规划收敛速度慢、消耗时间长、易陷入局部最优的问题，提出了一种基于改进蚁群算法的动态路经规划方法。该方法首先对初始信息素进行不均匀分配，避免经典算法中走回路现象；其次优化距离启发函数，为后续蚂蚁的路径选择提供依据；然后改进信息素的更新方式，增加最优路径上的信息素浓度，加快算法的收敛速度；最后在改进转移概率中引入邻域安全因子，避免蚂蚁陷入死锁。仿真实验验证了本文算法可有效提高智能小车的路径规划效率。但是，对于算法在不同参数、较大规模优化问题下的有效性验证，以及是否可以将本文改进的蚁群算法应用在更多的优化问题上将是论文的下一步工作。