改进IACA-GM 算法在移动机器人路径规划中的研究

李笑勉，左大利，舒雨锋，聂清彬

（1.东莞职业技术学院机电工程学院，广东 东莞 523808；2.西南交通大学希望学院，四川 成都 610400）

1 引言

路径规划是研究机器人领域中的核心技术，是指在有障碍物的工作环境下，为机器人构建出一条从起始点到目标点的无碰撞且连续的最优路径。目前，国内外相关领域的研究者都对机器人的路径规划进行了许多有效的探索，提出了诸多切实可行的经典算法并得到了广泛的应用，常见的经典算法有遗传算法[6、8]、人工势场法、神经网络法、粒子群算法、蚁群算法等。文献[1]提出了利用动态调节启发因子并对初始化信息素进行改进、建立对可选节点进行筛选机制的方案，从而实现对算法进行改进，改进算法搜索出来的最优路径距离虽然有所增加，但降低了算法循环次数，获得了一条无碰撞、没有穿过障碍物的最优路径，且时间消耗无增加，保障了机器人的安全性，提高算法的速度；文献[2]创新地提出关于一种离线路径规划算法，算法在采样前就生成包括了起始点和目标点之间的有界连通性区域，然后利用人工势场法优化采样过程，降低计算工作量，在势场合力的作用下，对有界区域内进行目标偏差采样，同时对采样区域进行调整，使得在较短时间内就生成较优路径。该算法明显减少了任务执行时间；文献[3]提出一种基于阶段变异策略与聚集度因子改进QPSO 算法，采用目标函数来分析出粒子对应的适应度，将改进聚集度因子加入到压缩扩张因子中进行划分搜索阶段，同时利用分阶段变异的策略更新个体位置，该算法提升了解的精度，该算法具有较高与较好的稳定性；文献[4]提出一种提出了自适应设置挥发系数，调整每条路径上的初始浓度，改进全局信息素更新方式，提升了算法的速度，整体效率得到提高，容易得到全局最优路径。这些算法都从不同的方面改进了算法的性能，获取全局最优路径，但在提高解的收敛速度和效率方面，仍需不断改进。

在以上最新研究基础之上，提出一种基于栅格模型的改进蚁群算法IACA-GM，并且将IACA-GM 算法应用在机器人路径规划当中，算法对传统蚁群算法效率低、易陷入局部最优等缺陷进行改进，缩小了寻优范围，加快算法收敛速度，增强机器人搜索路径的方向性，提升机器人寻找全局最优路径效率。

2 栅格环境模型

设定机器人移动的环境为二维矩形空间，对该空间利用栅格地图法[5]形式进行建模，栅格环境中障碍物的大小、形状、位置固定而且不会随着机器人的转移而改变。栅格大小定义为正方形，其边长为2，地图按照从左到右，从下到上的序号0，2，…20，如图1 所示。工作环境中的白色栅格代表可以自由通行路径，黑色栅格表示有障碍区域，机器人只能在白色栅格中移动，图中：S 点—移动机器人出发位置；G 点—机器人目标点的位置。机器人路径规划问题利用该栅格环境表示为在该栅格工作环境当中，构建一条连续的且使机器人移动距离最短的栅格路径。

图1 基于栅格法环境模型Fig.1 Environment Modeled by Grid Method

3 蚁群算法描述

蚁群优化算法[7]，该算法模拟自然界中的蚂蚁群体寻找食物源的过程，它源于意大利研究人员Dorigo 的博士论文，众多学者对该算法一直进行了深入的探索并运用到生活中的各个领域，算法描述的是在蚂蚁觅食过程中，蚂蚁会在经过的路径上释放出一种信息素，后面的蚂蚁在选择下一个节点时会凭借该节点上信息素浓度的高低来判定是否选择该路径，如果该节点的信息素浓度越高，蚂蚁选择该节点的概率就越大，当路径被众多蚂蚁选择以后，会产生一条从起始点到目标点浓度最高的路径，这条路径就是从全部路径中搜索出来的最短路径。在传统蚁群算法中，蚂蚁k 在t 时刻从节点i 选择转移到节点j 的概率表示为：

4 IACA-GM 算法模型

传统蚁群算法中，蚂蚁总是容易选择浓度相对较高的路径，导致有的路径的信息素浓度过高，算法虽然能够在很短时间内让蚂蚁找到最短路径，但是这样的局限，往往找到的总是局部最优路径，同时也缩小了搜索范围，容易陷入局部最优，为了能提高算法效率，在相对较短的时间内获取全局最优解，针对传统蚁群算法的缺陷，对其进行以下改进。

4.1 期望启发函数改进

以起点S 到当前节点i 的距离表示为dsi，下一条路径j 到目标路径G 的距离表示为djg，以djg距离信息作为选择下一个节点的主要导向因素，可以最大化增强蚂蚁搜索食物源的目的性，提高算法的收敛速度。

其计算公式如下：

则当djg越小时，说明节点j 距离目标点越近，则η 越大，此时该路径j 被选择的概率也就越大，由此增强了蚂蚁移动的方向性，提高了算法的收敛速度，将该距离函数应用于改进标准蚁群算法，改进公式如下：

4.2 概率转规则改进

在传统蚁群算法的概率转移公式基础之上加入随机选择机制，在蚂蚁转移概率公式中设置由参数q0控制的伪随机因子状态转移规则，公式如下：

式中：q0—［0，1］中是平均分布的随机选择参数；q—［0，1］之间的一个常数，当q≤q0时，选择的下一条路径为所有可选路径中最大值的节点，当q>q0时，根据式（5）计算到下一个节点的概率，算法趋于收敛。

4.3 信息素更新方式改进

当每只蚂蚁经过一条路径以及实现对全部路径的遍历之后，对遍历过的节点上残留信息素进行立刻更新[8]有利于加快算法收敛速度，在每时每刻蚂蚁对该路径进行了遍历后，马上对该路径进行局部更新，当所有蚂蚁完成了对全部路径的遍历以后，马上对搜索结果进行全局更新[9-10]。规则表示如下：

4.3.1 局部更新规则

当蚂蚁从一个路径i 转移到路径j 以后，立刻对路径（i，j）上的信息素进行更新，公式如下：

式中：τ0—路径上的信息素浓度初始值；ρ—信息素挥发系数，其值范围ρ∈（0，1）。

4.3.2 全局更新改进规则

为了加快算法的收敛速度，尽可能让蚂蚁搜索范围更能集中在最优路径的范围内，从而减少对最差路径附近的搜索，降低最差路径对蚂蚁的误导，在全部蚂蚁经过一次迭代以后，对最差路径（i，j）的信息素进行全局更新，公式如下：

式中：ρ—信息素挥发系数；dgood—当前迭代过程中出现的最优的路径；dbad—当前迭代过程中出现的最差的路径。对最差路径上的信息素进行更新以后，使得最差路径上的信息素得到有效抑制，最优路径的信息素得到增强，增加最差路径与最优路径的信息素浓度差，进而增大最优路径被选择的概率。

5 算法流程

（1）采用栅格矩阵对实验环境进行建模，设置移动机器人的起点位置为S，目标点位置为G，并将m 只蚂蚁放置在起点S，并设置初始迭代次数n=0 和最大迭代次数为nmax并初始化相关参数。（2）蚂蚁从起始点S 出发，每只蚂蚁通过状态转移规则式（6）计算到下一个节点的概率，并对已经走过的路径加入到对应禁忌表tabuk。（3）当蚂蚁k 到达终点G 时，根据信息素局部更新规则式（6）对该蚂蚁遍历过的路径进行更新。（4）重复以上步骤（2），步骤（3）直到所有蚂蚁都遍历完成，根据式（8）对路径上信息素进行全局更新。读取禁忌表tabuk里面的路径信息，比较每只蚂蚁经过的路径长度，得到最短路径。（5）迭代次数自增，并判定当前迭代次数，如果n≤nmax，则跳转到步骤（2）继续执行，如果n>nmax，结束程序，此时从数据库中选出的路径即为全局最优路径。

6 实验仿真结果与分析

为了验证IACA-GM 算法的有效性，硬件环境配置如下CPU Core i5，2.4GHz，4 内存。利用MATLAB 与VC++6.0 搭建实验平台进行仿真模拟测试，实验环境，如图1 所示。将障碍物随机分布到全局静态（20×20）的栅格矩阵中，机器人起点在栅格图左下角的S 点，目标点在栅格图右上角的G 点，黑色填充单元格表示为不能通行的障碍物，白色栅格表示可以自由通行区域，实验中IACA-GM 算法参数值设置，如表1 所示。

表1 实验参数Tab.1 Experiment Parameters

将这里的IACA-GM 算法与最新改进QPSO 算法[3]在相同的实验条件下进行对比试验，实验数据如图2 中的改进QPSO 算法实验结果和图3 中的IACA-GM 算法实验结果所示，其中，图2中的虚线代表移动机器人采用改进QPSO 算法计算出的全局最优路径，图3 中的实线代表移动机器人采用IACA-GM 算法出的全局最优路径。从图2 和图3 能够看出，在相同条件下，比较两种不同的改进算法在（20×20）栅格环境下，从起始点S 移动到目标点G 到实验结果，移动机器人采用改进QPSO 算法在搜索路径过程中，容易因为路径上信息素浓度增强贪图当前最优路径，而容易陷入局部最优，相比改进QPSO 算法，IACA-GM 算法在在选择路径过程中，通过加入参数q0控制的伪随机因子，增加了可选路径的多样性，扩大了搜索范围，以下一个节点到目标节点的距离来改进期望启发函数，使得机器人搜索的更加具有明显方向性，采用改进信息素更新方式，增强最优路径上的信息素，降低最差路径上的信息素，加快算法收敛速度。实验数据表明：在相同实验环境条件下，IACAGM 算法搜索效率更快，相比于改进QPSO 算法能够搜索到更短的最优路径，得到的解的质量明显优于改进QPSO 算法。

图2 改进QPSO 算法实验结果图Fig.2 Experimental Results of Improved QPSO Algorithm

图3 IACA-GM 算法最优路径实验结果Fig.3 Experimental Results of Improved IACA-GM Algorithm

为了验证算法的稳定性，改变栅格环境下的（20×20）尺寸，障碍物的大小、位置、个数、移动机器人出发的位置和目标点位置、两种算法的参数设置，如表1 所示。通过建立6 种不同的实验环境，进行6 次独立实验，实验数据，如表2 所示。从表2 中可以看出，随着实验环境的改变，IACA-GM 算法和改进QPSO 算法相比，IACA-GM 算法有效缩短了搜索时间，减少了迭代次数，提高了寻找最优路径的效率，算法性能得到进一步验证。

表2 迭代次数对比Tab.2 Comparison of Iteration Times

7 结语

针对传统蚁群算法应用在移动机器人路径规划的过程中，搜索范围过大，易陷入局部最优，收敛速度过慢等问题，通过将下一节点到目标点的距离来改进传统蚁群算法中的期望启发函数，采用加入伪随机因子，增加解的多样性，通过提高最优路径信息素，改进信息素更新方式，加快算法收敛速度。通过仿真实验表明，IACA-GM 算法在减少算法循环次数，缩短最优解的搜索时间，在提高算法效率方面具有明显的优势。