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

陈劲峰 黄卫华 王 肖 章 政

(武汉科技大学信息科学与工程学院 武汉 430081) (智能信息处理与实时工业系统湖北省重点实验室 武汉 430081)

0 引 言

移动机器人路径规划是机器人研究领域中的一个重要分支和研究热点，它指的是按照一定参考指标，机器人在具有障碍物的环境中寻找一条从起点到目标点最优或次优的无碰撞路径[1]。传统的路径规划方法有栅格法[2]、人工势场法[3]、可视图法[4]、快速探索随机树法[5]等。然而对于一些复杂环境，如震后救援、野外运输等，搜索区域空间大，且障碍物的分布不规则，传统路径规划算法存在寻优效率低等问题。近年来，一些具有启发性智能算法应用于移动机器人路径规划中，其中蚁群算法[6]已得到较为广泛的应用。

蚁群算法是一种自组织算法，具有较强的鲁棒性，优良的并行分布式计算能力、易于与其他算法结合等优点。然而，蚁群算法存在初期信息素匮乏、收敛速度慢、易陷入局部最优解等问题[7]，众多学者展开了一系列的改进工作。文献[8]提出了将信息素与启发信息两者的权重参数互锁，改进启发信息，提高了搜索速度，避免算法陷入局部最优。文献[9]和文献[10]主要提出了蚂蚁双向搜索策略，并辅之信息素更新等方法，提高了避障能力且加快了算法收敛速度。文献[11]将贪婪交叉算子应用于每次迭代结束时的轮盘赌中，以实现交叉操作，加快了求解最优解的速度。文献[12]使用刺激概率与无限步长的启发信息，改进信息素挥发率，加快了算法的收敛速度。文献[13]通过设置初始信息素，以及信息素挥发机制，调整自适应路径长度等策略提高了算法找最优解的收敛速度。文献[14]改进信息素更新机制和信息素平滑机制，丰富了解的多样性且提高了收敛速度。

上述算法，通过改进信息权重参数，信息素挥发与更新机制以及搜索模式有效地提高了全局搜索的收敛速度，但存在一些问题有待于进一步研究，如：(1)当地图中存在多达7个方向的邻节点时，路径判断过程复杂会导致降低算法运算速度，同时引起步数冗余；(2)启发信息缺乏紧密地对蚂蚁的引导性与对环境的适应性；(3)给予初始信息素总量恒定容易导致路径信息素过度积累，使机器人寻优陷入局部最优。

鉴于此，本文设计了一种改进的蚁群算法，并用于解决复杂环境下的移动机器人路径规划问题。首先，通过精简可选孙节点策略，缩小传统蚁群算搜索节点的范围，同时实现减小算法复杂度；其次，将环境规模尺寸与目标点引入到启发函数，使得蚂蚁搜索具有明确的方向性，并且适应不同环境规模；然后，设置每代信息素总量按高斯函数下降趋势自适应给予机制。最后，建立了移动机器人路径规划的复杂环境模型，将本文设计的改进蚁群算法应用于路径规划中，仿真结果证明了本文算法的有效性。

1 问题描述及环境建模

本文中机器人工作环境为复杂的静态2维空间，在全局路径规划中，设工作环境为n×n的栅格环境，黑色栅格用1表示障碍物，白色栅格用0表示自由可行区，不满一个栅格的障碍物仍按照一个栅格处理。栅格序号按自上向下、从左到右的顺序编为1，2，3，…，N。以栅格图左下角为坐标原点，横轴以从左至右为x轴正方向，纵轴以自下向上为y轴正方向，每个栅格长度取为单位长度，每一个栅格记为一个节点，建立的环境模型如图1所示。

图1 栅格环境模型

设栅格序号为Dx，n为每行每列的栅格数，则栅格序号与直角坐标的转换关系为

(1)

式(1)中，MOD(Dx,n)表示Dx/n的取余函数；CEIL(Dx/n)表示求取大于或者等于Dx/n的最小整数函数。提取栅格环境二值信息(0或1)得到对应矩阵G(n,n)，设mr表示矩阵的行，mc表示矩阵的列，则栅格序号与矩阵坐标转换关系为

(2)

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

本文改进的蚁群算法主要分为3个部分：(1)根据蚂蚁已走的两步节点，确定性分析出将运动下一节点最小的选择区域；(2)采用既符合环境规模大小又具有目标点的指引性的启发函数对蚂蚁进行引导；(3)将初始给定信息素总量Q随迭代次数的增加，按照高斯函数下降部分依次递减分配。

2.1 路径精简策略的选择

一般而言，在传统蚁群算法的邻节点选择中，当前节点在邻节点不含有障碍物前提下，除去已走过的上一节点外，对于将选择的下一节点有7个方向需要判断，很大程度上降低了蚂蚁搜索效率，导致步数冗余，造成搜索路径加长。鉴于此，提出一种精简蚂蚁下一步可行区域的策略。以图2所示的孙节点选择方向为例说明路径精简策略，策略如下。

针对一条路径中顺序相连的节点D、F和节点G，按照蚂蚁经过节点D、F和G的顺序，若先经过节点D，其次经过节点F，再经过节点G，则将D记为父节点，F记为子节点，G记为孙节点，同时规定节点G不属于节点D的邻接点。其示意如图2所示。

针对栅格模型中，蚂蚁单步运动行走方式：直线和斜线，分别由图2(a)与图2(b)的路径“父→子”所示。针对图2(a)所示可选的3个孙节点，由移动机器人路径规划定义有，假定每一只蚂蚁由父节点到子节点这一搜索路径是并且就是所寻找的最优路径，也即当前子节点为父节点到达目标点的必经节点，即子节点已定，那么由父节点到当前子节点，有5条可选路径，如图3(a)所示，分别为：①父→a→子；②父→b→子；③父→子；④父→c→子；⑤父→d→子。

图2 孙节点选择方向

图3 父子节点走向图

分析如下，经比较，从起点到目标点，③父→子这一路径长度最短，且无拐角，故路径中如果出现了路径③，那么路径①②④⑤则不会出现在该次搜索路径中，否则搜索路径将会冗余曲折，不符合最短路径要求。基于上述分析，路径精简策略是除了将父节点加入禁忌表中，同时如图3(a)将父节点的相邻节点a、b、c和d不纳入孙节点可选范围，进行屏蔽处理。因此根据父节点到子节点这一既定直线运动趋势，可选孙节点有3个，如图2(a)所示孙1、孙2和孙3。同理针对蚂蚁走斜线的情形，可得到有效孙节点范围如图2(b)所示，孙1、孙2、孙3、孙4和孙5共5个节点。

由上述分析可知，通过使用对下一可选节点的精简策略相对原始搜索需要判断邻近多达7个节点的模式，变为当父与子节点路径呈直线时，孙节点的可走路径如图2(a)有①子→孙1、②子→孙2、③子→孙3，只需判断处理3个节点；呈斜线时孙节点的可走路径如图2(b)有①子→孙1、②子→孙2、③子→孙3、④子→孙4、⑤子→孙5，只需判断处理5个节点。走直线和斜线处理的共同点是当父节点和子节点已定，孙节点的选择区域是在子节点的邻节点中，除去父节点与子节点共有邻节点而余下的节点。2种运动方式中的节点处理数均小于7个，有利于提高搜索效率，降低搜索盲目性，同时降低计算代价。

边界特殊孙节点的处理。针对上述精简下一节点的策略，为避免蚂蚁因根据图2(a)中寻找孙节点的搜索模式运动到环境边界节点，出现如图4(a)中所示的困境，也即当父→子节点已定，子节点的上下邻节点被屏蔽而其右边无孙节点可选，导致出现此蚂蚁由于路径精简策略的局限性而锁死，提出取消搜索局部屏蔽机制，提高蚂蚁的存活率，处理方式为开放其伪孙节点，如图4(b)所示，取消算法对子节点的上下邻节点的屏蔽；同理，针对当蚂蚁若走斜线到达环境角落如图4(c)无孙节点可选的情形时，同样对其开放伪孙节点，如图4(d)所示。

图4 边界孙节点

2.2 启发函数与概率函数选择

基本蚁群算法在搜索过程中具有搜索时间长，存在搜索指向不明确的缺陷。蚁群算法作为启发型算法中的一种，启发函数质量的优劣，对算法的应用效果具有较大影响，但是传统蚁群算法的启发函数1/dij，其中dij表示相邻节点之间的距离，对环境的能见度较低，且不具有目标点的引导作用，导致搜索盲目性。针对此问题，提出一种不受环境规模大小影响的具有引导机制性启发函数，如式(3)所示：

(3)

式(3)中，Jk表示蚂蚁k在一条路径上邻近可选下一节点的集合，n为环境栅格的行列数；DijE表示节点i、j以及目标点依次连接的距离之和。当子节点到孙节点以及目标点的距离越短，其引导性越强。

以蚂蚁第一步出发并无既定的父子节点位置关系作为指引，本文设计了联合概率函数，如式(4)和式(5)所示：

(4)

式(4)中，τij(t)为t时刻在边ij上的信息素积累，∂为信息素权重参数，∂越大表明蚂蚁越倾向选择过往蚂蚁走过的路径；ηij(t)表示t时刻从节点i转移到节点j的启发信息，β为启发信息权重参数，其值越大，表明蚂蚁越倾向走距离目标点更近的节点。

(5)

式(5)中，Ns表示起始点的相邻有效节点个数，step表示蚂蚁k在一条路径上累计搜索的节点个数；当step=1时，使用等概率搜索，一方面有利于从起点扩大全局搜索范围，同时可解决蚂蚁第一步出发无既定的父子节点位置关系作为指引的限制。

2.3 自适应信息素总量给予机制

在基本蚁群算法中，信息素总量是一个定值，极大可能性存在随着迭代次数的增加，后期路径上的信息素浓度易积累过高导致蚂蚁一定程度上失去搜索优质解能力而陷入局部最优解，针对此问题，提出将信息素的总量根据迭代次数递增而按照高斯函数模型下降部分逐步降低的给予机制。

在一次迭代完成后，针对到达目标点的蚂蚁，将路径上的信息素进行更新，可得：

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

(6)

式(6)中，ρ为信息素挥发系数，其中0<ρ<1，Δτij(t,t+1)表示t+1时刻所有经过边ij之间的蚂蚁残留信息素增量，可得：

(7)

Δτij表示第k只蚂蚁经过边ij残留的信息素，可得：

(8)

式(8)中，Q为信息素常量，Lk为蚂蚁k在本次搜索中的路径长度。其中信息素总量Q的给予机制设计为

(9)

式(9)中，G为算法的迭代次数，设定μ=0对应信息素总量Q的峰值，保证从第一代直至最后一代Q(G)呈下降趋势；取σ=35，使得信息素总量符合正态分布的3σ法则，也即保证最后一代给予的总信息素量近乎为最低值。

3 改进蚁群算法流程

将所设计的改进蚁群算法用于路径规划中，算法流程如下。

步骤1参数初始化。将具有多个障碍物的地图栅格化，并计算任意两节点之间距离，取障碍栅格到其他栅格距离为无穷大，表示不可达；设定节点之间初始信息素，迭代次数K，蚂蚁种群个数M，起始点S，目标点E，信息素权重系数α，启发信息权重系数β和挥发系数ρ，以及信息素总量Q。

步骤2路径选择。利用式(5)计算蚂蚁下一节点的选择概率，然后采用轮盘赌选出下一节点，判断是否满足到达目标点或可选孙节点数小于1的条件，不满足则转至步骤3，满足转至步骤4。

步骤3状态更新。将步骤2选出的子节点同时加入路径列表和禁忌表，计算当前路径总距离，并根据父节点和子节点的位置关系，推导出可选孙节点范围，返回步骤2。

步骤4蚂蚁序号更新。针对没到达目标点且可选孙节点个数小于1的蚂蚁路径长度记为无穷大；m=m+1，计算下一只蚂蚁的搜索路径，返回步骤2；当前蚂蚁序号m等于种群总数M时，转至步骤5。

步骤5信息素更新。将完成一次迭代的所有蚂蚁按式(6)的信息素更新函数进行路径上的信息素更新。

步骤6蚂蚁迭代次数更新。迭代次数k=k+1，返回步骤2；当迭代次数满足设定迭代次数时，结束算法。记录历史最优路径，绘制出每代平均距离曲线与算法收敛曲线。

4 仿真实验与分析

在不同规模的复杂环境下，验证本文设计的改进蚁群算法并用于移动机器人的路径规划，基于栅格法建立如图5(a)和图6(a)所示的环境地图，环境1和环境2分别为20×20与30×30的栅格地图。地图中，一部分障碍物呈现凹陷状，另一部分障碍物设置成无次序且无规则的近似随机分布状态，设置机器人起始点为栅格模型的左上角，目标点为右下角。

4.1 环境1实验结果分析

在20×20的栅格环境1中，传统蚁群算法与本文改进蚁群算法最短路径如图5(a)所示，每代最小路径与平均路径距离分别如图5(b)和图5(c)所示。对比搜索路径，传统蚁群算法在搜索时缺乏目标点的引导作用，导致搜索盲目，同时算法后期路径上信息素积累过高，蚂蚁更多地选择已走路径，从而出现图5(a)虚线所示路径上的第4个不必要的拐点；而本文算法在使用精简下一节点的可选范围策略上，首先就避免了路径直角折点的出现，在实际情形下实现降低移动机器人消耗的能量，其次引入具有启发性的启发函数，自适应递减信息素总量，因此路径无多余曲折的拐点。

对比收敛曲线，如图5(b)所示，在传统蚁群算法中由于没有目标点的引导作用，在前60代搜索中只有4代搜索到了最短路径，直至接近第90代平均路径与最短路径才最终汇合，归结于传统蚁群算法的初期信息素匮乏，导致收敛速度慢；而本文算法中蚂蚁搜索存在目标点的引导作用，以高斯函数下降部分按迭代次数递减信息素总量避免信息素积累的基础上，不仅在第13代就能找到最短路径，而且在图5(c)可以看出平均路径距离开始逐步降低且趋于稳定，由于信息素的自适应给予机制使得全体蚂蚁搜索路径收敛很快。

(a) 传统蚁群算法与本文算法最优路径图

(b) 传统蚁群算法与本文算法路径最小曲线

(c) 传统蚁群算法与本文算法路径平均距离曲线图5 环境1中实验结果比较

4.2 环境2实验结果分析

在环境2中，传统蚁群算法与本文算法最短路径实验结果如图6(a)所示，最小路径距离和平均距离曲线图分别如图6(b)和图6(c)所示。栅格环境中设置了更多凹陷区，对于基本蚁群算法结果而言，其路径由于没有目标点的引导作用，同时由于路径信息素的积累作用，导致后期信息素过高，后期蚂蚁选择前期蚂蚁走过的路径，出现了3个多余的拐点，如图6(a)曲线直角所示，在实际搜索中增加了能量损耗，而本文算法由于设置了自适应信息素总量给予机制，避免了路径上的信息素过度积累，在以找到最短路径为目标时，只出现了不可避免最少的拐点数。

(a) 传统蚁群算法与本文算法最优路径图

(b) 传统蚁群算法与本文算法路径最小曲线

(c) 传统蚁群算法与本文算法路径平均距离曲线图6 环境2中实验结果比较

在最小路径图6(b)中，与环境1类似，由于具有目标点对蚂蚁的紧密引导作用，本文算法在找到最短路径的代数远远早于传统蚁群算法找到最短路径的代数；鉴于采用了精简可选节点策略，实现降低搜索范围，使得蚂蚁搜索路径集中，本文算法平均路径不仅下降速度比传统蚁群算法快，而且距离更短。

本文实验参数设置如表1所示，针对实验参数的取值，本文在计算下一节点概率函数中取消信息素项，然后依旧以轮盘赌的方式选择下一节点做测试。结果显示，平均曲线与最小曲线均呈现杂乱无序状况，即表明假使缺失信息素项的作用，算法将失效，表明了信息素项在所取该值的情况下，发挥了其在蚁群算法中使蚁群相互协作的作用，同时表明了所取值的合理性。

表1 本文实验参数设置

本文算法与传统蚁群算法在环境1与环境2的实验结果分别如表2和表3所示。

表2 环境1实验结果

表3 环境2实验结果

由表2以及表3知，采用相同的蚂蚁群体个数和迭代次数，本文算法与传统蚁群算法在2种环境的路径规划比较中，本文算法获得路径距离更短，收敛代数更早，拐点数目更少，最优路径上总的拐角度数之和更小，即路径更为平滑，对于实际机器人有利于降低能量与时间消耗。综合而言，改进算法比传统蚁群算法在复杂环境中更加体现出其优越性，具有更快的搜索速度及路径平滑度。

5 结 论

本文针对传统蚁群算法在移动机器人路径规划时出现初期信息素缺乏、易陷入局部最优、收敛速度慢等问题，对可选转移节点进一步优化，使用精简可选节点策略，实现降低了盲目搜索性，降低了计算代价；在此基础上，设计符合环境变化的启发函数，将目标点引入其中，增强对蚂蚁搜索的引导作用；最后，为了加强后期蚂蚁受前期蚂蚁在路径上残留信息素的影响，同时为了避免搜索后期信息素过度积累，引入符合高斯函数模型随迭代次数而递减的自适应总信息素给予机制。仿真实验表明，与传统蚁群算法相比，在获得路径质量更优的前提下，本文算法所规划的路径更短、更平滑，具有更快的收敛速度，证实了本文算法在不同复杂环境中作为移动机器人路径规划算法的有效性与优越性。