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

孙海洋　夏庆锋　杨冠男

摘要：

蚁群算法是机器人路径规划中的经典算法之一，在二维静态环境中，传统蚁群算法在机器人路径规划中还存在一些缺点，如算法收敛较慢、容易陷入局部最优并可能导致算法停滞等。针对这些缺陷，对传统蚁群算法提出相应改进，引入自適应启发式因子、拐点个数等参数，并采用不同启发式因子对随机概率进行更新。使用Matlab对改进前后算法的收敛速度、避障寻径和最短路径长度等进行对比分析。结果显示，改进后的算法较传统算法不仅可以使机器人有效避开所有障碍物，而且能够高效寻找到最短路径，在很大程度上避免了算法陷入局部最优。

关键词：

路径规划；蚁群算法；最优路径；拐点个数；启发式因子

DOIDOI：10.11907/rjdk.182144

中图分类号：TP303

文献标识码：A文章编号文章编号：16727800（2018）009002203

英文标题Research on Robot Path Planning Based on Improved Ant Colony Algorithm

——副标题

英文作者SUN Haiyang，XIA Qingfeng，YANG Guannan，GUO Lili

英文作者单位（School of Information Science and Engineering，Jinling College of Nanjing University， Nanjing 210000，China）

英文摘要Abstract：Ant colony algorithm is one of the classical algorithms in robot path planning.The traditional ant colony algorithm still has some shortcomings in robot path planning. For example， the algorithm converges slowly， it is easy to fall into local optimum， and it may cause the algorithm to stagnate. For these defects， the traditional ant colony algorithm is proposed to improve accordingly， adaptive heuristic factors and parameters such as the number of inflection points are introduced， and different heuristic factors are used to update the random probability. Matlab simulation is used to compare the convergence speed， obstacle avoidance path and the shortest path length of the improved algorithm. The results show that compared with the traditional algorithm， the improved algorithm can not only make the robot avoid all obstacles efficiently， but also can find the shortest path efficiently， and it also avoids the defect of falling into local optimum to a large extent.

英文关键词Key Words：route plan；ant colony algorithm；optimal path；the number of inflection points；heuristic factor

0引言

蚁群算法由意大利学者Dorigo、Maniezzo等于20世纪90年代首次提出，是来自大自然的随机搜索寻优算法，现已陆续应用到组合优化、通讯等各个领域，具有很好的适应性[13]。蚁群算法在机器人路径规划应用中占有非常重要的地位，但传统蚁群算法在机器人路径规划中还存在一些问题，如收敛速度慢、容易陷入局部最优等[45]。

文献[6]利用蚁群算法的进化机制，融合多路径选择和概率选择策略，寻找最短行走路径，在一定程度上能有效求解机器人路径规划问题。文献[2]、文献[7]提出动态有限区域搜索策略，将蚁群算法与A*算法相结合，增强了全局搜索能力，缩小了搜索范围，提高了搜索效率，得到较短的寻优时间，但在一定程度上增加了算法复杂度。文献[8]提出的蚂蚁相遇策略提高了算法搜索效率，通过设置信息素感应阈值扩大算法前期的搜索范围，提高了收敛速度。文献[9]提出参数自适应的伪随机转移策略，有助于蚂蚁寻找全局最优解。仿真结果表明，新算法明显提高了收敛速度和寻优能力，能够较好地满足复杂环境下机器人路径规划的需求。

本文提出一种自适应启发式因子蚁群算法，以提高算法的收敛速度、全局搜索能力，并引入拐点个数，以进一步缩短所寻路径并起到平滑处理的作用。通过Matlab仿真对比验证，得出改进算法的有效性和优越性。

1传统蚁群算法在路径规划中的应用

1.1路径规划流程

传统蚁群算法应用于机器人路径优化问题的主要步骤如下：

（1）使用栅格法构造机器人寻径地图。

（2）初始化信息素矩阵，假设所有位置的初始信息素是相同的，并设置初始化参数及起止坐标[10]。

（3）根据当前信息素算出下一步可前往每一个节点的概率，并计算下一个节点[1011]的选择概率pkij（t），如式（1）所示。

pkij（t）=[τij（t）]α·[ηij]β∑k∈{N-tabuk}[τij（t）]α·[ηij]β j∈{N-tabuk}0其它（1）

其中，τij（t）表示地图中坐标为（i，j）点的信息素浓度；ηij表示启发式信息值；α、β表示信息素浓度及启发式信息值的权重参数。

（4）更新路径以及路径长度。

（5）重复步骤（3）、步骤（4），直到蚂蚁走到终点坐标或陷入死循环为止。

（6）重复步骤（3）-步骤（5），直到某一代m只蚂蚁全部寻径完毕。

（7）根据式（2）、式（3）更新信息素的矩阵，没有走到目的地的蚂蚁不计在其中。

τij（t+1）=（1-ρ）τij（t）+Δτij（2）

Δτij（t）=QLk（t），蚂蚁k经过i，j

0，蚂蚁k不经过i，j（3）

重复步骤（3）-步骤（7），直到n代蚂蚁全部迭代结束。算法流程如图1所示。

1.2启发式因子

启发式因子采用自适应方式。设蚁群算法的启发式因子为α、β，其中α表示信息启发式因子，是之前蚂蚁所累积信息素对后面蚂蚁的运动起到的作用，其值越小，说明之前蚂蚁所累积的信息素对后面蚂蚁的作用越小，蚂蚁之间的合作性就越小[1213]，反之，蚂蚁之间的合作性就越大，但同时随机选择的概率也会降低，则不容易陷入局部最优的情况；β表示信息素期望启发式因子，是对启发式信息在路径规划中的作用，其值越大，算法速度会相应增加，选择概率会越小，相反，如果其值越小，启发式信息所起到的作用就越小，随机性就越大[13]。所以需根据是否存在障碍物对α、β选择不同的值。例如，当周围存在障碍时，其值可设置为α=10、β=70；反之，其值可设置为α=1、β=7。

1.3 基于固定启发式因子的蚁群算法仿真

对环境的建模采用栅格法[14]，黑色栅格表示障碍物，白色栅格表示自由空间[1516]。采用20×20的栅格建立环境模型，对基于传统蚁群算法的机器人路径规划进行Matlab仿真验证。对函数中各个参数进行初始化：设问题规模的大小为M，蚂蚁个数为N，迭代次数为K，信息素权重参数为α，启发因子权重参数为β，信息素增加强度系数为Q，信息素蒸发系数为ρ。

在满足K=200、M=50、N=100、ρ=0.8、Q=200的情况下，启发式因子设计为α=1、β=10，对该传统固定启发式因子的蚁群算法进行Matlab仿真，得到机器人运动轨迹及算法收敛曲线分别如图2（a）、图2（b）所示。

由图2（a）可以看出，该传统算法的路径规划虽也可从起点到达终点，且能够避开所有障碍，但存在一段“迂回路径”，故不是最短路径。

由图2（b）可以看出，在启发式因子α=1、β=10的情况下，算法大概在第160次迭代之后趋于稳定，最短路径长度约为34。

1.4仿真结果分析

基于传统固定启发式因子的蚁群算法，机器人也可以绕过所有障碍寻到最优路径[1720]。通过图2（b）可以看出，在该地图环境下，采用传统固定启发式因子蚁群算法的机器人路径规划方案，大约需经过160次迭代之后，其最短路径长度才趋于一个稳定值，该稳定值即为最短路径长度，约为34。由此可知，虽然传统蚁群算法也能寻找到最短路径，但其收敛速度较慢。

2蚁群算法改进

本文不采用固定的启发式因子，而使用能够根据环境自适应调整的启发式因子[21]。

修改信息素的更新规则，为了减少机器人运动的时间，加入拐点个数作为路径的评价之一。在机器人仿真运动中只存在3种可能角度：锐角、直角、钝角，若赋予其权重分别记为3、2、1，在蚂蚁寻优完成之后计算该路径上拐点的个数，个数越小路径就越平滑，路径长度也就越短。更新后的信息素公式如式（4）所示，其中GD为第k只蚂蚁寻到的路径拐點个数。

Δτk（i，j）=QLk+GD（4）

在初始参数为K=200、M=50、ρ=0.8、Q=200的环境下，对引入拐点个数因子并采用自适应式启发因子的改进蚁群算法进行Matlab仿真。

由图3（a）可以直观地看出，改进算法已经去掉了传统算法对应路径轨迹中多走的一段“迂回路径”。

由图3（b）可知，引入拐点个数及自适应式启发因子的改进蚁群算法，大约在第9次迭代之后收敛于稳定值，最小路径长度约为31。

3结语

针对传统蚁群算法在路径规划方案中存在的收敛速度慢、容易陷入局部最优等问题，本文引入了自适应式启发因子、设置路径拐点个数等参数的改进蚁群算法。通过Matlab仿真实验，改进算法在一定程度上避免了陷入局部最优，大大提高了收敛速度，并且所寻路径更短、更圆滑，证明了改进算法的有效性和可行性。

参考文献参考文献：

[1]张美玉，黄翰，郝志峰，等.基于蚁群算法的机器人路径规划[J].计算机工程与应用，2005（25）：3437.

[2]葛延峰，陈涛，孔祥勇，等.改进蚁群算法在城市汽车导航中的应用[J].控制工程，2016，23（1）：133137.

[3]葛斌，韩江洪，魏臻，等.最小最大车辆路径问题的动态自适应蚁群优化算法[J].模式识别与人工智能，2015，28（10）：930938.

[4]TUNCER A，YILDIRIM M.Dynamic path planning of mobile robots with improved genetic algotithm[J].Comptuers & Electrical Engineering，2012，38（6）：15641572.

[5]DEEPAK B L，PARHI D R，KUNDU S.Innate immune based path path planner of an autonomous mobile robot [J].Procedia Engineering，2012，38：26632671.

[6]柴寅，唐秋华，邓明星，等.机器人路径规划的栅格模型构建与蚁群算法求解[J].机械设计与制造，2016（4）：178181.

[7]李龙澍，喻环.改进蚁群算法在复杂环境中机器人路径规划上的应用[J].小型微型计算机系统，2017，38（9）：20672071.

[8]王志中.基于改进蚁群算法的移动机器人路径规划研究[J].机械设计与制造，2018（1）：242244.

[9]王钦钊，程金勇，李小龙.复杂环境下机器人路径规划方法研究[J].计算机仿真，2017，34（10）：296300.

[10]张成，凌有铸，陈孟元.改进蚁群算法求解移动机器人路径规划[J].电子测量与仪器学报，2016（11）：17581764.

[11]柳长安，鄢小虎，刘春阳，等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报，2011（5）：12201224.

[12]吴虎发，李学俊，章玉龙.改进的蚁群算法求最短路径问题[J].计算机仿真，2012 （8）：215218.

[13]THOMAS STUTZLE T，HOLGER H HOOS.Maxmin ant system[J].Future Generation Computer Systems，2000，16（8）：889914.

[14]卜新蘋，苏虎，邹伟，等.基于复杂环境非均匀建模的蚁群路径规划[J].机器人，2016，38（3）：276284.

[15]曾明如，徐小勇，刘亮，等.改进的势场蚁群算法的移动机器人路径规划[J].计算机工程与应用，2015，51（22）：3337.

[16]游晓明，刘升，吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策，2017，32（3）：552556.

[17]袁亚博，刘羿，吴斌.改进蚁群算法求解最短路径问题[J].计算机工程与应用，2016（6）：812.

[18]葛延峰，陈涛，孔祥勇，等.改进蚁群算法在城市汽车导航中的应用[J].控制工程，2016（1）：133137.

[19]刘建华，杨建国，刘华平，等.基于势场蚁群算法的移动机器人全局路径规划方法[J].农业机械学报，2015，46（9）：1827.

[20]游晓明，刘升，吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策，2017，32（3）：552556.

[21]屈鸿，黄利伟，柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报，2015，44（2）：260265.

责任编辑（责任编辑：何丽）