徐玉琼，娄柯，李志锟

（1. 广州大学松田学院 电气与汽车工程系，广东 广州 511370; 2. 高端装备先进感知与智能控制教育部重点实验室，安徽 芜湖 241000; 3. 安徽工程大学 安徽省电气传动与控制重点实验室，安徽 芜湖 241000）

在移动机器人领域，路径规划技术一直都是重要研究内容，其任务是在地图环境中为移动机器人从起点至终点避开障碍物而规划出的最优路径。目前国内外学者针对路径规划技术做了诸多研究，并取得相应成果，常用的传统路径规划算法有遗传算法、模拟退火算法、人工势场法、A*算法[1]等。随着人工智能技术的高速发展，群智能算法在路径规划技术中得到广泛应用和发展，如人工鱼群算法、蜂群算法、蚁群算法[2-4]、蛙跳算法等，人工鱼群算法是一种擅长随机搜索的算法，其算法原理简单，对初始值要求较低，但在算法后期存在收敛速率缓慢、计算结果不够精确。蜂群算法作为模仿蜜蜂行为提出的启发式算法，通过对单一的蜜蜂进行局部寻优，突出全局最优值，容易陷入局部最优，其算法鲁棒性不强。传统的群智能算法已经无法满足移动机器人在复杂环境下进行路径规划，因此，大量学者通过对传统的群智能算法进行改进，如多策略人工鱼群算法[5-7]、双层蚁群算法[8]、启发机制下的蚁群算法[9]等。改进的群智能算法已经明显提高复杂环境下移动机器人的路径规划[10-15]能力。

蚁群算法作为启发式全局优化算法是由意大利学者Dorigo在1992年提出，该算法得益于采用正反馈机制，收敛性能大幅提升，通过分布式计算方式进行搜索以及不同个体同时并行计算，提高了该算法的运算效率以及计算能力，但仍存在收敛速度慢以及死锁问题。因此，文献[9]对蚁群算法进行改进，提出了基于启发式机制的蚁群算法，该算法通过当前节点到终点的距离动态的调整启发函数，当算法处于局部最优时，引入惩罚函数机制，降低最优路径的信息素，减少蚁群算法的正反馈影响而跳出局部最优。文献[14]主要针对于蚁群算法收敛速度慢进行改进，合理分配信息素初始浓度，动态调整信息素挥发因子，进行二次路径规划，有效缩短了移动机器人的路径长度。文献[8]设计了双层蚁群算法，对移动机器人二维栅格环境进行凸化处理，同时用外层蚁群探索出一条路径作为一个小环境，内层蚁群在该环境下重新探索，两条路径择优筛选，提高蚁群算法路径搜索质量。

为了提高蚁群算法收敛速度以及缩短路径长度，本文提出变步长蚁群算法，寻找移动机器人可以达到的跳点，得到不同长度的路径，根据路径长度的不同，不均匀分配初始信息素浓度，以降低边缘障碍物对移动机器人的影响，从而提高算法的计算能力。改进启发式信息矩阵，提高蚁群避障能力，增强蚁群全局路径搜索能力，快速找到最优路径。

1 蚁群算法原理

1.1 环境表示

移动机器人需要在二维空间环境下进行路径规划，因此，需要对移动机器人工作环境进行建模，常规环境建模方法如栅格图法[16-18]、可视图空间法、自由空间法、几何信息法等。本文选取栅格图法对移动机器人二维空间进行建模，将栅格分为黑色区域和白色区域，其中黑色区域为障碍物栅格，白色区域为自由栅格，机器人可以在白色区域自由移动，如图1所示，假设每个栅格为边长为1 m的正方形，不考虑机器人自身身高和体积的影响，机器人始终处于正方形的正中心位置。

图 1 栅格地图Fig. 1 Raster map

1.2 搜索方式

传统蚁群算法中蚁群为单步长[19-20]移动方式，每步移动距离为1或个单元格，在不碰撞障碍物的情况下，可以向四周共8个方向移动，如图2所示。

图 2 移动方式Fig. 2 Moving method

蚁群在寻路过程中，利用信息素相互通信，在经过的路径上释放信息素，当某一条路径通过的蚂蚁越来越多时，该路径的信息素浓度就越高，其他蚂蚁选择该路径的概率就越大，起到正反馈作用，同时也容易陷入局部最优及存在死锁现象。信息素会随着时间的增长而挥发，动态的调整各路径的信息素浓度，蚂蚁在选择路径时，会对信息素浓度、启发因子、路径方向等因素进行综合判断选择下一步移动位置，并利用轮盘算法计算当前节点到下一到达节点的概率：

式中：τij为路径(i,j) 上的信息素；ηij为位置i到位置j的启发因子；ak为蚂蚁k下一步可到达节点的集合；α 表征信息素重要程度；β表征启发因子重要程度；dij是蚂蚁从位置i到位置j构建的路径长度。

为了避免蚂蚁选择已经达到过的节点，采用禁忌表记录蚂蚁k当前所达到过的位置，经过t时刻，所有蚂蚁都已完成了一次路径规划，计算所有蚂蚁完成的有效路径长度，筛选出最短路径长度，同时更新各路径上的信息素，经过时间的增长，信息素将挥发一部分：

式中：ρ 是信息素挥发系数，同时，蚂蚁也将在路径中释放信息素：

式中：Δτkij是第k只蚂蚁在所经过的路径上释放的信息素，定义如下：

由式(5)可知，蚂蚁所构建的路径长度dij越小，那么各路径将得到更多的信息素，在以后的迭 代中该路径被其他蚂蚁选择的概率也将更大。

2 变步长蚁群算法

传统蚁群算法步长选择为单步长，蚁群仅能向相邻栅格位置移动，不能满足移动机器人实际需求，且搜索效率低及路径长度无法满足最优，因此，本文提出变步长选择策略，在避开障碍物的条件下，移动机器人可以从当前位置向全局地图的任何位置移动，大幅提高移动机器人搜索效率。

2.1 步长选择策略

跳点的选择即步长的选择，所谓跳点就是移动机器人在搜索过程中从当前节点可以到达下一步的节点。如图3所示。移动机器人从起点到终点有4条路径可供选择，方案1为当前节点1跳跃至节点2再到终点3，节点1到节点2步长为3.16 m，节点2至节点3路径长度为2 m，因此，方案1路径总长度为5.16 m，方案2为节点1变步长跳跃至节点4再到节点5，最后由节点5单步移动至终点3，方案2路径总长度为4.65 m，方案3为传统蚁群算法的单步长移动方式，从当前节点1到节点6，再移动到节点7，再移动到节点8，最后再到终点3，该方案路径总长度为4.83 m，方案4为节点1跳跃至节点9，从节点9单步长移动到节点8，最后移动到终点3，该方案路径总长度为5.16 m，显然，方案2作为变步长移动方式优于其他方案，变步长蚁群算法在寻路过程中，对每种方案的路径长度进行评估，最终挑选出路径最短的方案。

图 3 步长选择Fig. 3 Step size selection

在图3中，节点1为起始点，节点3为终点，移动机器人进行路径规划时，将节点1作为父节点，通过变步长选择策略，将下一步移动机器人要到达的节点4作为子节点，再将节点4作为父节点确定下一子节点，以此方法进行迭代，最终确定了本轮迭代后的最优路径{1,4,5,3}，结合变步长蚁群算法的优点，移动机器人对于下一步所选择的节点越接近于终点，则可以减少节点转折的次数，同时，转折点越接近于障碍物，则可以减少无效路径，因此，为了缩短移动机器人路径长度，引入终点诱导因子 φ 及障碍物诱导因子 μ，其选择概率为

式中：k为常数，保证概率范围为(0,1)；ε 为终点诱导系数；ω 为障碍物诱导系数； γis为移动机器人当前节点到下一步可到达所有节点的距离总和，σ 为移动机器人下一步到达的节点与终点之间的距离，其值越小，则距离终点越近，被选择的概率也将越大，λ 为移动机器人下一步到达的节点与其最近的障碍物之间的距离，优先考虑障碍物相邻的节点，可以有效缩短无效路径，提高移动 机器人避障能力。

2.2 信息素分布策略

在移动机器人路径规划之前，需要给栅格地图环境的信息素进行初始化，初始化信息素采用不均匀分布，障碍物栅格的信息素设置为0，加强起点至终点直线所涉及到栅格的信息素浓度，平行的向外衰减，将栅格地图建立直角坐标系，如图4所示。

图 4 信息素分布策略Fig. 4 Pheromone distribution strategy

连接移动机器人的起始点及终点，则该直线方程为

在本文中，C取值为20或30，分别对应简单栅格环境和复杂栅格环境，令τij(0)=τ0为信息素浓度的初始值，根据初始信息素浓度的衰减方式，障碍物栅格的初始信息素 τ0直接取0，非障碍物栅格初始信息素取值如下：

式中：T为调整系数，T∈(1,20)，初试信息素的分布有利于蚁群提高搜索速度，快速收敛。

为了防止某条路径的信息素过高或过低，避免蚂蚁集中在某条路径上，将每条路径的信息素设置上下限为 [τmin,τmax]，当该条路径信息素浓度低于信息素下限时，将该条路径信息素设置为τmin，当该条路径信息素浓度高于信息素上限时，该条路径信息素设置为 τmax，这样可以避免算法陷入局部最优解，当蚁群经过一轮迭代后，挑选出最优路径，对其信息素进行更新，加强对最优路径的利用，当所有蚂蚁完成一次迭代后，对路径上的信息素进行全局更新：

为了提高搜索效率，一只蚂蚁在一轮迭代中走过的完整路径将不被以后的蚂蚁所选择，对于需要更新信息素的路径，可以是本轮迭代的最优解 ，也可以是全局最优解。

2.3 改进启发函数

结合变步长蚁群算法的优点，在直角坐标系中，利用蚁群下一步到达的节点距离起点至终点连线的长短，对启发函数进行改进，传统蚁群算法的启发函数为蚁群下一步所选择的节点到终点之间距离的倒数，如式(2)所示，该函数收敛性不强，且容易使蚁群寻优路径冗长，改进后的启发函数如下：

式中，(xi,yj) 为下一步所选择节点的坐标，当其距离起点至终点对角线的长度越小，被选择概率则越大，与传统蚁群算法的启发函数相比，改进后的启发函数促使移动机器人将下一步选择的节点趋近于移动机器人起点到终点连线处，使移动机器人在路径寻优中能更快地找到最优解，提高了算法的收敛速度，因此，改进后的启发函数作用得到加强，有利于提高算法的收敛速度，提高算法的全局搜索能力。

3 改进算法步骤

图5为变步长蚁群算法的流程图，算法的具体步骤如下：

1) 针对各项相关参数进行初始化：路径规划的起始点及终点、信息素重要程度参数 α、启发因子重要程度参数 β、迭代次数、蚂蚁数量、信息素挥发系数及增强系数等相关参数，建立地图二维栅格模型，邻接矩阵模型。

2) 初始化信息素采用不均匀分布，加强起点至终点直线所涉及栅格的信息素浓度，平行的向外衰减；改进启发式信息矩阵，调整移动机器人当前位置到终点位置的启发函数计算方法，建立启发式信息矩阵。

3) 建立禁忌表以及对禁忌表初始化，将起点、障碍物节点、引起死锁的节点均加入禁忌表中。

4) 计算启发信息，根据信息素浓度以及概率公式确定蚂蚁下一步可以到达的节点，记录路径并更新，更新禁忌表。

5) 当所有蚂蚁完成一次迭代后，保存最优路径，更新信息素及禁忌表，如果没有完成一次迭代，则继续开始下一只蚂蚁路径寻优。

6) 如果蚂蚁完成所有迭代次数，则输出最优路径及收敛迭代次数，如果没有完成所有迭代次数，则继续开始下一次迭代。

图 5 变步长蚁群算法流程Fig. 5 Flow chart of variable step size ant colony algorithm

4 算法仿真

为了验证变步长蚁群算法的有效性，本文分别在简易环境和复杂环境下进行仿真对比，简易环境为 20 ×20 的栅格环境，对传统蚁群算法、本文算法进行仿真，与文献[8]进行对比，复杂环境为 3 0×30 的栅格环境，对本文算法进行仿真，与文 献[8]进行对比。

4.1 20×20 栅格环境

在 20×20 的栅格环境下，对传统蚁群算法和本文算法进行仿真，其中，路径规划仿真分别如图6、7所示，实验数据如表1所示，传统蚁群算法路径规划长度为30.870 m，文献[8]算法路径规划长度为32.1421 m，本文算法路径规划长度为28.042 m，显然，本文算法在路径规划方面优于文献[8]算法及传统蚁群算法，本文算法较文献[8]算法、传统蚁群算法的路径长度分别缩短了12.76%及9.16%。本文算法提出信息素不均匀分布策略，提高了最优路径上节点被选择的概率，通过节点距离起点至终点对角线的距离，改进启发函数，提高了算法的全局搜索能力，有效缩短了全局 最优路径的长度。

图 6 传统蚁群算法路径规划(20×20)Fig. 6 Path planning of traditional ant colony algorithm

图 7 本文算法路径规划(20×20)Fig. 7 Algorithm path planning in this paper

表 1 各算法实验结果对比Table 1 Comparison of experimental results of various algorithms

收敛迭代仿真分别如图8、9所示，传统蚁群算法收敛迭代次数为25次，文献[8]算法收敛迭代次数为4次，本文算法收敛迭代次数为2次，显然，本文算法在收敛速度方面优于文献[8]算法及传统蚁群算法，本文算法较文献[8]算法、传统蚁群算法的收敛迭代次数分别减少了50%及92%。图10为本文算法在该环境下各代蚂蚁最优路径规划路线，各代路线集中于起点至终点的连线处，表明信息素不均匀分布的有效作用，在 2 0×20 栅格环境中，本文算法无论是在最优路径上还是在收敛速度上，都优于其他两 种算法。

图 8 传统蚁群算法收敛曲线Fig. 8 Convergence curve of traditional ant colony algorithm

图 9 本文算法收敛曲线Fig. 9 Convergence curve of the algorithm presented inthis paper

图 10 本文算法各代蚁群最优路径规划(20×20)Fig. 10 Optimal path planning of each generation of ant colony in this algorithm (20×20)

4.2 3 0×30 栅格环境

在 30×30 栅格环境下，采用文献[8]中的同一个栅格地图，对本文算法进行仿真实验，实验数据如表2所示，本文算法的路径规划如图11所示，本文算法的最佳路径长度为41.961 m，文献[8]的最佳路径长度为45.112 7 m，本文算法较文献[8]关于最佳路径长度缩短了6.99%，因此，在复杂栅格环境下，本文算法依然保持良好的路径规划能力，通过变步长蚁群算法，有效地缩短了最优路径长度，收敛迭代效率如图12所示，本文算法的收敛迭代次数为6次，文献[8]算法的收敛迭代次数为8次，本文算法较文献[8]算法关于收敛迭代次数减少了25%，栅格地图越复杂，本文算法的优越性越明显，各代最优路径规划路线如图13所示，各代路径规划的路线依然集中于起点至终点的连线处，移动机器人将快速的寻找出最优路 径。

表 2 两种算法实验结果对比Table 2 Comparison of experimental results of various algorithms

图 11 本文算法路径规划(30×30)Fig. 11 Algorithm path planning in this paper (30×30)

图 13 本文算法各代蚁群最优路径规划(30×30)Fig. 13 Optimal path planning of each generation of ant colony in this algorithm (30×30)

4.3 实验研究

本文采用自主搭建的移动机器人进行实验验证，如图14及图15所示，一个纸箱代表两个正方形障碍物栅格，空白场地为自由栅格，实验场景为 2 0×20 的栅格环境，实验数据如表3所示，本文算法路径规划最优长度为3.26 m，移动机器人从起点至终点耗时13.56 s，传统蚁群算法路径规划最优长度为5.13 m，耗时19.67 s，验证了本文算法在移动机器人实际应用中能够较快地找到最优路径，有效地提高了路径规划的工作 效率。

图 14 移动机器人起点位置Fig. 14 Starting position of mobile robot

图 15 移动机器人运行过程Fig. 15 Mobile robot running process

表 3 各算法路径规划实验数据Table 3 Experimental data of path planning for each algorithm

5 结束语

传统蚁群算法在移动机器人路径规划中存在搜索效率低、路径过长、收敛较慢等问题，本文在传统蚁群算法的基础上引入了变步长策略对其进行改进，扩充蚁群可以到达节点的集合，在不触碰障碍物的条件下，从蚁群当前位置的相邻位置扩大至全局地图的任意自由栅格位置，达到变步长策略，改进信息素分布策略以及调整启发函数计算方法，大幅提高本文算法的收敛速度，快速地寻找到最优路径。本文基于变步长蚁群算法在收敛速度和路径寻优方面有着较好的性能，不仅适用于简单栅格环境，也适用于复杂的栅格环境，使本文算法在实际应用场景中得到较好的应用，通过对整个地图状态空间的探索点进行采样，能够增加搜索区域，适合解决移动机器人在复杂环境下的路径规划。