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

姚晓通，李致远，程 晓

(兰州交通大学电子与信息工程学院，甘肃 兰州 730070)

1 引言

目前，机器人在各个领域的应用越来越广泛，机器人路径规划在其中占有很重要的地位。所谓路径规划，是机器人从起始位置到目标点位置这两点之间，以一定的优化准则(如行走路径最短)，找到一条可以躲避障碍物的最优路径或次优路径，指导机器人去逼近找到的路径，完成任务[1]。对于机器人路径规划的研究，涉及很多传统的全局路径规划算法，其中包括A*算法，D*算法，人工势场法，以及C空间法[2]。但是在面对比较复杂的障碍物环境时，以上算法的效果不佳。随后，一些研究人员根据自然界生物行为的启发，又相继提出了应用在路径规划方面的智能算法，如粒子群算法，遗传算法，神经网络法，以及蚁群算法[3]。其中，蚁群算法和以上其它智能算法相比，具有信息正反馈，分布式计算及全局求解能力强的特点，所以在机器人路径规划领域中，其作为一种很有效的规划算法，应用很广泛。

蚁群算法是意大利学者M.Dorigo于20世纪90年代通过对蚂蚁觅食行为的观察研究后，受到启发，而提出来的一种仿生模拟算法[4]。该算法首先成功的解决了旅行商问题(TSP问题)，在求解旅行商路径最短问题上取得了比较理想的效果。后续，有学者便将蚁群算法应用到路径规划方面，虽然相比于其它智能算法，其具有一定的优势。但是基本蚁群算法还是存在一定的缺陷和不足，因此许多研究人员对基本蚁群算法进行了改进。文献[5]提出了将环境中局部的机器人路径信息引入到蚁群信息素的初始化和路径选择概率中，提高了蚁群算法的收敛速度，但路径质量不是很理想。文献[6]将遗传算法算子引入到了蚁群算法中，缺点是运算复杂，效率低。文献[7]提出了使用混合型信息素更新策略，提高了收敛速度并能够避免局部最优，但在最优路径距离上效果不是很好。文献[8]通过根据蚂蚁迭代次数手动设置信息素增强系数去达到提高算法收敛速度的目的，但是容易陷入局部最优。文献[9]提出了一种基于改进蚁群算法的自适应蚁群算法，该方法针对二维环境的路径规划效果较好，在三维环境中收敛缓慢，而且容易陷入局部最优。

上述方法虽然在避免陷入局部最优问题和提高蚁群算法的收敛速度上取得一定的效果，但是仍存在全局路径效果不佳且搜索到的路径长度偏长的问题。为了更好地解决这些问题，得到更优质量的路径。本文提出了改进的蚁群算法，在蚁群状态转移策略中引入了基于hocaoglu算法思想的引导函数，引导蚂蚁更好地逼近最优解。在信息素更新规则中，设计了一种自适应信息素挥发因子更新方法，避免蚁群陷入局部最优解。

2 基本蚁群算法概述

2.1 蚁群算法的思想

自然界的单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。蚂蚁在寻找食物的过程中会在经过的路径上释放一种被称作信息素的化学物质，以便其它后来的蚂蚁可以感知[10]。在刚开始时，由于路径上没有蚂蚁经过，不会存在信息素，蚂蚁会随机选择遇到的路径。随着时间的推移，距离短的路径经过的蚂蚁会越来越多，从而会使路径上累积的信息素浓度越来越高，后续的蚂蚁选择此路径的概率也会增大，最终蚂蚁群会找到一条到达目标点的最优路径。

2.2 蚁群算法的数学模型

1)状态转移概率

蚂蚁根据信息素浓度去选择下一个需要移动的节点。同时，还要受到当前节点与周围节点之间的期望信息的影响。对于蚂蚁的状态转移规则如式(1)所示[11]

(1)

2)信息素更新规则

由上可知，禁忌表tabuk用来记录在当前迭代中蚂蚁走过的节点，直到完成本次迭代，否则不能再次访问禁忌表记录的节点。当所有蚂蚁完成对所有节点的访问后，在禁忌表中便记录每只蚂蚁所走过的节点，构成路径的可行解。之后，要对之前的路径信息素进行削弱，对新引入的信息素进行加强，规则如下

τij(t+n)=(1-ρ)τij(t)+Δτij(t，t+n)

(2)

(3)

(4)

3 改进蚁群算法

3.1 改进蚁群算法引导函数

针对基本蚁群算法中蚂蚁搜索路径存在一定的盲目性且逼近目标点的效果不理想的问题，本文提出了一种基于hocaoglu算法思想的引导函数。hocaoglu算法是一种多尺度路径规划算法，其原理如图1所示[12]。

图1 hocaoglu算法原理图

在上图中，s为起始点，e为目标点。显然可知，从s到e的最短路径是它们之间的直线段。若在se之间有障碍物，则做se的垂直平分线ab，那么sb、be就是为到达目标点所规划的路径。当sb之间也存在障碍物时，继续做sb的垂直平分线，就可以找到sc、cb、be的可达路径。以此类推，最后一定可以找到一条不经过障碍物的路径。可以发现，越靠近se附近的节点，节点与起始点和目标点的距离之和越小，路径越短，反之，则路径越长。基于此，本文设计了带有权重调节因子的引导函数，如式5所示

(5)

(6)

其中Dis为当前节点与起始节点的距离，die为与目标节点的距离。引导函数的值与节点到目标点的距离和到起始点的距离之和有关，也和节点与目标点的距离有关。由式(5)可知，在se附近的节点且越靠近目标点的节点，且引导函数的值越大，相应的路径距离越小。同时，对引导函数设置调节因子λ，在搜索前期λ大于0.5，更偏向于se附近的节点，在搜索后期λ小于0.5，更侧重于靠近目标点的节点，这样有助于蚂蚁在后期更快的找到目标点。Ns为当前节点所在节点的次序，Nm为搜索的中期节点的次序。所以改进后的算法的状态转移规则如式7所示

(7)

γ为启发引导因子，表示引导函数的重要程度。

3.2 自适应信息素挥发因子的设计

相比于其它参数，信息素挥发因子ρ对算法性能的影响最大。当ρ过小时，信息素挥发慢，导致路径上的信息素浓度差异小，蚂蚁会充分搜索地图上的每条路径，但是收敛速度会变慢[13]；而ρ过大时，路径上的信息素挥发速度过快，之前信息素浓度低的路径，信息素浓度会更低，信息素浓度差异变大，会出现强烈的正反馈效果，这样虽然会加快算法的收敛速度，但是很容易陷入局部最优。面对信息素挥发因子很难找到一个特定的值去适应蚂蚁搜索迭代的整个周期，本文提出了一种自适应的信息素挥发因子的方法。对于ρ的区间范围为[0，1]，将ρ的初始值设置为0.95，若连续10次迭代中相邻两次最优解的差值小于等于0.1%时，ρ自动调节为原来的0.9倍；当ρ小于0.2时，强制设置ρ为0.2，表达式如式8所示

(8)

式(8)中，约束条件的设定，某种程度上可以防止蚂蚁在搜索过程中陷入局部最优，同时既可以信息素 挥发因子过大，又可以防止过小，对算法性能产生坏的影响。基于以上，改进后的蚁群算法流程图如图2所示。

图2 改进后的蚁群算法流程图

4 实验结果与分析

为了验证改进算法的有效性，本文在matlab2016a环境下搭建仿真地图并进行对比实验。相比于可视图法、节点法和自由空间法，栅格法具有规划空间表达一致，便于计算机建模、存储、处理更新和分析等优点，故采用栅格法对环境地图进行建模。为了排除地图环境因素的影响，建立了两种不同的障碍物仿真地图：一种是简单的障碍物环境地图(规格为10*10)，另一种是复杂障碍物环境地图(规格为20 *20)。由于蚁群算法参数较多，采用控制变量，利用单一参数对算法性能的影响来确定最佳参数值，其它参数的选取则都是在已经确定的之前参数的最佳值的基础上进行实验的。本文对最佳参数的选取(以平均路径长度和平均迭代次数为评判准则)，进行了10次实验，每次迭代的次数为100，然后再取10次实验最佳值的平均值。最终参数确定如下：蚂蚁数目m=35，信息启发因子α=4，期望启发因子β=5，引导启发因子γ=3，信息素强度系数Q=100，路径初始信息素浓度τ0=0.3，信息素挥发因子ρ=0.95，最大迭代次数NCmax=100。

路径规划的两种地图环境模型，它们的起始点都为(1，1)，目标点分别为(10，10)，(20，20)，其中黑色为障碍物，白色为可规划路径地图。在简单环境地图模型下，基本蚁群算法和改进后的蚁群算法路径规划仿真运行图，如图3、4所示，它们的迭代收敛曲线图，如图5、6所示。

图3 基本蚁群算法路径规划图

图4 改进蚁群算法路径规划图

图5 基本蚁群算法收敛图

图6 改进蚁群算法收敛图

由图3、图4、图5和图6可知，改进蚁群算法规划的最优路径的长度明显小于基本蚁群算法规划的路径距离，本文改进算法的收敛长度为15.95，且在第28代就开始收敛；而基本蚁群算法的路径收敛长度为19.32，收敛代数为52代，显然改进蚁群算法在最优路径长度和收敛速度要优于传统蚁群算法。

图7、图8为另一种复杂环境地图下蚁群算法的路径规划仿真运行图。

图7 基本蚁群算法路径规划图

图8 改进蚁群算法路径规划图

图9、10为复杂地图环境下基本蚁群算法和改进蚁群算法的收敛曲线图。

图9 基本蚁群算法收敛图

图10 改进蚁群算法收敛图

由图9、图10分析可知，在复杂障碍物环境下，改进蚁群算法的性能也是要优于基本蚁群算法的。改进蚁群算法在42代就收敛到最优路径，路径长度为30.56，而基本蚁群算法最优路径长度为34.23，收敛的代数为68。在两种地图环境下，可以看出改进蚁群算法通过引入引导函数，加强精英蚂蚁的路径信息素浓度和对信息素挥发因子的自适应调节使其全局寻优能力和收敛速度都好于基本蚁群算法，使蚂蚁的寻优效率更高，更有目的性，而且不易陷入局部最优。

5 结论

本文提出了一种基于改进蚁群算法的机器人路径规划方法。针对传统蚁群算法路径规划中存在的一些问题，提出了相应的改进。首先，在蚁群状态转移策略中引入基于hocaoglu算法思想的引导函数并对其设置调节因子；其次，在蚁群信息素更新规则中采用自适应的信息素挥发因子；最后在matlab环境下对所提方法进行仿真验证，结果表明改进的蚁群算法在寻优能力和收敛速度上具有明显优势，求解最优解更有目的性，在提高收敛速度的同时又可以避免陷入局部最优，能找到更优质量的路径，具有实际工程意义。