基于改进蚁群算法的移动机器人路径规划

刘加奇, 王泰华, 董 征

(河南理工大学 电气工程与自动化学院，河南 焦作 454000)

0 引 言

随着科学技术的不断发展，移动机器人在生活服务、工业生产等领域得到了广泛的应用[1]。移动机器人实现自主移动的前提是机器人具有路径规划能力，而路径规划的好坏，关键在路径搜索算法的选取上[2]。根据路径搜索算法原理，路径规划分为传统路径算法(如A*算法[3]、人工势场法[4]等)和智能路径算法[5](如遗传算法(genetic algorithm,GA)[6]、粒子群优化(particle swarm optimization,PSO)算法[7]和蚁群算法(ant colony algorithm，ACA)[8]等)。

蚁群算法自Dorigo M提出以来，在不少领域得到了应用，其中路径规划是其中之一[9,10]。不过蚁群算法在路径规划过程中，也容易陷入局部最优和收敛性差等问题，针对这些问题，不少学者对蚁群算法进行改进[11]。文献[12]基于狼群法则对信息素更新方式进行改进，避免蚂蚁陷入最优，提高算法搜索路径长度的最优性。文献[13]通过改变信息素更新方式，修改信息素挥发系数，在信息素增量更新式子中添加一个动态调节因子，以增大次优路径上信息素浓度的方法，提高搜索最优路径的概率。文献[14]利用鸟群算法对行驶环境进行快速搜索，将规划的路径转化为蚁群算法信息素，对蚁群算法初始信息素进行差异化分配，来提高蚁群算法前期的搜索速度，加快算法的收敛性。文献[15]结合人工势场法，增加一个提高全局搜索能力的诱导因子，改进距离启发函数，提高算法路径搜索的最优性和收敛速度。

为了改进蚁群算法在路径规划上存在的不足，本文通过增加目标点导引修改距离启发函数和建立判断可行节点夹角大小的夹角指数启发函数对状态转移概率进行改进，以及采用部分较优路径信息素增量分段,更新和自适应调节信息素挥发系数对信息素改进的方法，为研究移动机器人静态全局路径规划提供一种参考。

1 环境模型的建立

搭建机器人环境模型，是机器人路径规划重要组成部分。栅格法因其直观和易于实现的特点，在机器人环境建模中得到大量的使用，因此,本文选择栅格法建立移动机器人二维静态环境模型。

2 改进蚁群算法

2.1 改进状态转移概率

利用蚁群算法进行路径规划时，受路径上初始信息素均匀分布，以及节点启发性不强的影响，蚂蚁在路径搜索过程中采用一种盲目的方式，导致蚁群算法存在前期搜索速度慢，规划的路径非最优问题。本文采用一种离目标点最近的可行节点作为下一节点，通过修改距离启发函数，增加目标点导引作用，加快蚁群的收敛速度。另外当节点上信息素浓度过大时，会使节点的启发性不能得到保证的情况，本文基于文献[8]设计一个新的启发函数φij(t)，即夹角指数启发函数。图1中，夹角θij为可行节点j到目标点E和节点i两点之间的夹角，根据可行节点j下的路径1和路径2可知，夹角θij越大，蚂蚁选择路径1的期望值越大，因此,建立一个根据节点夹角大小的启发函数，来保证路径的最优性。

图1 节点夹角

由以上分析可知，期望的程度越大，相应的，余弦函数cos(θij)的相反数也就越大；同时，为了能够增强节点的启发性，添加一个动态调节因子，建立的夹角指数启发函数为

φij=exp(-cos(θij))

(1)

则蚂蚁选择下一可行节点的状态转移概率公式为

(2)

(3)

式中τij(t)为信息素浓度，α为信息素浓度因子；φij(t)为夹角指数启发函数，γ为其启发函数因子；ηiE(t)为可行节点j到目标节点E的启发函数，d(j,E)为可行节点j到目标点E的欧氏距离，β为距离启发函数因子；allowedk为蚂蚁k下一可行节点集。

2.2 改进信息素更新方式

基本蚁群算法信息素更新是针对到达目标点的蚂蚁，算法不仅计算量大，而且蚂蚁容易受最差路径上蚂蚁释放信息素的误导，使蚁群陷入局部最优，影响蚁群的路径规划效果。基于对精英蚁群算法和排序策略[16]的研究，为了更好地区分路径上信息素浓度，使蚂蚁能够搜索到最优路径，本文采用一种对路径长度信息素增量Q差异化的更新方式，即将蚂蚁搜索的路径长度进行分类处理，通过舍弃部分较差路径上的蚂蚁，选择对搜索到最优路径的蚂蚁信息素增量额外补偿，而较优部分蚂蚁正常更新的方式，提高路径规划长度的最优性。信息素更新改进方法如下

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

(4)

(5)

(6)

系数ε为

(7)

2.3 自适应挥发系数

信息素挥发系数的取值，对蚁群算法的性能起到重要作用，信息素挥发系数过大或过小都将影响蚁群算法规划的收敛速度和路径长度。传统蚁群算法信息素挥发系数采用的是一个定值，不利于蚂蚁在路径长度和收敛速度都保持最优性。基于以上原因，本文研究一种基于等差数列递减的自适应信息素挥发系数，采取在优先保证蚁群算法收敛性的情况下，对信息素挥发系数采取逐次递减，后期再增大蚂蚁搜索范围的方式，对信息素挥发系数进行自适应调节。自适应挥发系数为

(8)

式中ρmax为最大信息素挥发系数，ρmin为最小信息素；t为当前蚂蚁迭代次数，T为蚂蚁最大迭代次数。

2.4 算法实现步骤

步骤1：利用栅格法建立移动机器人栅格环境模型，布置机器人环境中白色可行栅格和黑色不可行障碍物栅格；步骤2：设置起始点坐标S和目标点坐标E，以及初始化蚁群算法参数；步骤3：将蚂蚁m放在起始点位置，蚂蚁k按照式(2)选择路径下一可行节点，并将蚂蚁走过的放进禁忌表tabuk中；判断节点是否达到目标点，对到达目标点的蚂蚁，按照步骤4进行下一步，否则，继续；步骤4：按照路径长短进行排序，选取部分较优路径按照式(4)进行信息素更新；步骤5：判断是否达到最大循环次数，条件成立输出全局最优路径，否则执行步骤2。

3 实验仿真与分析

为了验证改进蚁群算法的性能，在MATLAB 2015b仿真平台上进行测试。设置公式中的参数，其中最大循环次数为100，蚂蚁数量为50，信息素浓度α，距离启发函数β，夹角指数启发函数γ分别为1，4，2。设置两种环境模型，与文献[12]和文献[16]对比，验证改进蚁群算法的性能。

3.1 环境1

凹型障碍物是导致路径搜索长度增加的重要环境模型，本文在搭建环境时，将机器人环境1设置成20×20带有凹型的环境模型，对文献[12]、文献[16]和改进蚁群三种算法进行仿真，得到改进蚁群算法最优路径和收敛曲线如图2所示。

图2 改进蚁群算法最优路径及收敛曲线

对文献[12]、文献[16]和改进蚁群算法各运行20次，算法分别从最优路径长度、迭代次数、最差路径长度、平均路径长度及平均迭代次数上进行比较，统计结果如表1所示。

表1 20×20环境算法性能比较

从表1可知，文献[16]和改进蚁群算法在最优路径长度是相等的，并且相比文献[12]减少了1.94 %；在最优路径长度下的收敛曲线，文献[12]和文献[16]是相等的，改进蚁群算法相比两个算法减少了80.21 %；在最差路径长度上，文献[16]和改进蚁群算法相比文献[12]分别减少了7 %,7.72 %；从平均路经长度上，文献[16]和改进蚁群算法相比文献[12]，分别减少了4.54 %,4.70 %；在平均迭代次数上，文献[12]和改进蚁群算法均优于文献[16]，分别减少了20.63 %,87.30 %。通过表1的数据统计结果可知，在搜索的路径长度上，文献[16]和改进蚁群算法均优于文献[12]，并且改进蚁群算法又优于文献[16]；在收敛曲线上，文献[12]和改进蚁群算法相比文献[16]均能较快的收敛，同时改进蚁群算法又较快于文献[12]，表明改进蚁群算法具有路径搜索能力强和收敛性快的优点。

3.2 环境2

为进一步验证改进蚁群算法性能的优越性，本文在文献[12] 30×30环境的基础上增加环境的复杂度，将机器人环境2设置成30×30多障碍物和多凹型栅格环境模型，对文献[12]、文献[16]和改进蚁群三种算法再次进行仿真比较，得到改进蚁群算法最优路径和收敛曲线如图3所示。

图3 改进蚁群算法最优路径及收敛曲线

对文献[12]、文献[16]和改进蚁群算法各运行20次，算法分别从最优路径长度、迭代次数、最差路径长度、平均路径长度及平均迭代次数上进行比较，如表2所示。

表2 30×30环境算法性能比较

从表2可知，文献[16]和改进蚁群算法在最优路径长度上，相比文献[12]分别减少了8.43 %和9.64 %；在最优路径长度下的收敛曲线，文献[12]和改进蚁群算法相比文献[16]分别减少了25 %,78.79 %；从最差路径上对比可知，文献[16]和改进蚁群算法相比文献[12]分别减少了16.61 %,16.10 %；在平均路径长度上，文献[16]和该蚁群算法相比文献[12]分别减少了13 %,13.89 %；从平均迭代次数上看，文献[12]和改进蚁群算法又都优于文献[16]，并且相比文献[16]分别减少了50.14 %,90.31 %。通过对表1和表2中数据分析可知，改进蚁群算法能够绕开凹型障碍物，并且在复杂环境下能够快速搜索到最优路径，同时具有稳定性强的优点。

4 结 论

针对基本蚁群算法在移动机器人路径规划上，搜索的路径长度和收敛性非最优问题，本文通过对基本蚁群算法的结构进行改进，并将改进蚁群算法应用到栅格环境模型下的移动机器人路径规划上，与文献[12]和文献[16]仿真对比可知，改进蚁群算法具有路径规划能力强，收敛速度快和适用范围大的优点。