李雪　金昕　郑先鹏

摘 要：针对蚁群算法在移动机器人路径规划时会出现收敛速度慢、全局搜索空间大、时间长、效率低、易陷入局部最优解和出现死锁现象等问题，提出了一种改进的蚁群算法.在静态已知环境的条件下利用栅格法建立模型，基于传统蚁群算法的基础上，采用精英选择的方法加快收敛速度、自适应改变挥发系数来使初始时刻的蚁群搜索能力加强、范围扩大，避免陷入局部最优解;针对U型障碍物，提出了丢弃陷入死锁中的蚂蚁.通过仿真结果可以得到改进后的蚁群算法能够快速地搜索到最优路径，与传统蚁群算法以及改进的蚁群算法相比较，具有良好的路径寻优的能力和避障性能.

关键词：移动机器人;轨迹规划;改进蚁群算法;精英选择;自适应;U型障碍

中图分类号：TP242  文献标识码：A  文章编号：1673-260X（2019）11-0103-04

1 引言

移动机器人的研究包括导航定位、运动控制、路径跟踪与路径规划等技术，其中路径规划是研究移动机器人的核心内容之一.所谓机器人路径规划技术，就是指通过其他传感器对环境采集的信息做出一個反馈，并且找出一条从起点到终点无碰撞运动路径.国内外学者将移动机器人的路径规划方法规划为以下几种类型，其中包括模块匹配路径规划、人工势场法、地图构建路径规划和人工智能路径规划等路径规划技术[1].地图构建路径规划中的栅格法在移动机器人全局路径规划中应用较为广泛，但是也存在着缺陷：储存空间小以至于降低了搜索效率等问题.随着遗传算法、神经网络算法、粒子群算法、免疫算法、PID模糊控制算法、蚁群算法等智能算法的提出[2-4]，许多学者利用人工智能算法来路径规划，其中蚁群算法被广泛应用于路径规划.蚁群算法是一种启发式搜索算法，具有较强的鲁棒性等特点[5].同时蚁群算法也具有许多缺陷：收敛速度慢、易陷入局部最优解等问题.所以许多学者对蚁群算法进行了大量改进，其中有信息素更新方式的改进、路径选择策略方面的改进、与其他算法相结合的改进、多重蚁群算法的改进[6].比如文献[7]中就提出了广义信息素更新规则来解决蚂蚁面对凹型障碍物会出现的死锁现象来寻找最优解，文献[8]中就提出了使用不同的期望值，采用自适应挥发系数来更新信息激素来找到最优解，文献[9]中就提出了通过动态调整自适应蚁群算法的参数进而实现对信息素更新来找到最优解，文献[10]中就提出了对较优蚂蚁的路径进行信息素更新，在面对U型障碍物时，提出了蚂蚁回退策略，使算法的收敛速度加快，寻优与避障能力加强.

针对以上提出的问题以及相关学者对这些问题所提出的解决办法可以看出利用改进的蚁群算法来解决路径规划中收敛速度以及局部最优解等问题还需要进一步的改进算法.本文中使用的改进算法主要是依据信息素更新方式的改进，首先自适应调整挥发系数ρ，因为当挥发系数ρ设置过大时，就会加大对之前搜索过的路径的搜索，当挥发系数ρ设置过小时，即使会提高算法的全局搜素能力，但是算法的收敛速度会大幅降低，所以最终采取自适应调整挥发系数ρ来动态调整算法的整体性能，提高其鲁棒性.最后是通过动态改变信息素τij（t），利用精英选择在每次循环结束后对发现的最优解给予额外的信息素增量，用来在下一次的循环中对蚂蚁更具有吸引力，提高算法的收敛速度.以上改进的蚁群算法对不同时刻的信息素都有着全局掌控能力，为提高收敛速度和避免局部最优解提供了保证.最后利用改进的蚁群算法来进行路径规划，并且完成了仿真实验，相比较其他的改进蚁群算法的实验结果可以证明本文的改进蚁群算法的可行性和优越性.

2 环境建模及U型障碍物问题分析

2.1 环境建模

移动机器人工作环境建模主要分为以下几种：特征地图、栅格地图等.其中栅格法普遍应用于机器人环境建模，由于栅格法具有易于实现，分析等优点，所以本文将采用栅格法对移动机器人进行环境建模.

首先定义一个有限二维平面作为机器人的移动区域，不妨设该区域为G，在该区域内存在大小与位置不变的障碍物，其中白色栅格为机器人可移动区域，将白色栅格记为0，黑色栅格为固定的障碍物，将黑色栅格记为1.该区域按照从左到右，从上到下的顺序来依次对栅格进行标记，记为1，2，3，4，…，n，其中每一个数字代表一个栅格;坐标原点定在栅格空间的左下方，从左到右定义为X轴正方向，从下到上定义为Y轴正方向.栅格的长度定义为单位长度，由此建立二维坐标平面XOY.以下是栅格序号和坐标的对应关系：

x=mod（L，N）-0.5ifx=-0.5，x=19.5y=N+0.5-ceil（L，N）  （1）

式（1）中：mod为求余运算;L为栅格的序列号;N为栅格的行列数.

为了避免机器人与障碍物发生碰撞，对障碍物的边界进行膨化处理，于是机器人可以等效于一个质点.

2.2 U型障碍物问题分析

蚁群算法在进行移动机器人路径规划时，当遇到复杂的环境有可能会陷入局部最优解.在算法运行过程中，为了避免蚂蚁重复访问同一个节点，因此引入了禁忌表，已访问的节点存储在储存器中，作为蚂蚁在下一次选择过程中的不需要访问的节点.这样就导致蚂蚁在遇到U型障碍物时会陷入死锁现象，图2所示为U型障碍物1，从中可以清楚地看到蚂蚁可以有以下路线：1→2→3、1→4→3、1→2→4→3，蚂蚁在遇到U型障碍物1时可以顺利通过，并且不会出现死锁现象.虽然不会出现死锁现象，但是会影响蚂蚁在寻优路径所需要的时间.图3所示为U型障碍物2，从中可以清楚地看到蚂蚁可以有以下路线：1→2→3、1→4→3、1→2→4→3、1→2→4→5→6、1→4→5→6，蚂蚁在路线1→2→4→5→6、1→4→5→6时就会出现死锁现象，导致蚁群整体能量的损耗降低了收敛速度.

针对U型障碍物，有以下几种处理办法.

（1）将U型障碍进行凸型处理，以牺牲环境为代价，在实际环境中采取这种方法较为困难，因此不采用此方法.

（2）若蚂蚁陷入死锁，则将蚂蚁视为死亡蚂蚁，因此不再进行路径搜索，并且清除死亡蚂蚁在路径上产生的信息素，停止更新.

（3）回退策略，当蚂蚁无路径搜索时，此时释放禁忌表，目的是回退一步.如图3所示，当蚂蚁陷入死锁状态到达节点6，无路可走时，则通过释放禁忌表选择节点5，将节点6加入禁忌表，同时清除路径节点5、节点6点的信息素，以此为循环直至“逃离”陷阱.

（4）更新信息素，当遇到U型障碍物并陷入死锁状态时，将该路径的信息素清零，当遇到U型障碍物1时采取信息素渐灭方式[3].

本文采用（2）方式进行凹型障碍物避障，当遇到U型障碍物1和U型障碍物2时，采取丢弃陷入死锁的蚂蚁.遇到U型障碍物时采取本文改进的蚁群算法可以有效地提高蚁群搜索效率以及寻优路径.

3 改进蚁群算法设计

3.1 蚁群算法改进

传统蚁群算法具有鲁棒性强，易与其他算法相结合等优点，缺点是收敛速度慢，易陷于局部最优解，出现搜索停滞等.为了提高算法的有效性与实用性，本文主要针对蚂蚁在避障时找到最优路径以及在陷入U型障碍时遇到的问题所做出的处理方法.首先采用自适应调整挥发系数ρ，最后是通过动态改变信息素τij（t），利用精英选择在每次循环结束后对发现的最优解给予额外的信息素增量，用来在下一次的循环中对蚂蚁更具有吸引力，有效地提高了算法的收敛速度和全局搜索能力.

3.1.1 自适应调整挥发系数ρ

蚁群算法在运行过程中会受到许多因素的影响，本文所提到的动态调整参数ρ来解决算法在运行过程中收敛速度慢、易陷入局部最优解等问题.当挥发系数ρ设置比较大时，之前蚂蚁走过的路径被再次选择的机会就会加大，过小时会提高全局搜索能力导致收敛速度降低.于是初始时刻将参数ρ设置为最大值，虽然以前搜索路径被再次选择可能性加大，但是信息正反馈占主导作用.

本文对参数ρmin设置为0.1，ρ的自适应调整公式如下：

3.1.2 精英选择较优路径信息素更新

当全部蚂蚁都完成一次路径搜索以后，按每个蚂蚁行走路径的长短进行排序（L1≤L2≤L3≤…≤Lm），每只蚂蚁对信息素更新的贡献根据该蚂蚁的排序进行加权，加权值记为φ.更新公式（3）（4）和（5）如下：

在每轮路径搜索结束后对较优蚂蚁的路径上的信息素进行更新，随着参数ρ的逐渐降低，这将增大路径上信息素的差异，增加了全局搜索能力，但此时算法的收敛速度降低.由于蚂蚁在寻优路径的时候会倾向于信息素浓度大的路径，所以通过精英选择对较优蚂蚁路径的信息素浓度的额外加权，增加了该路径的信息素浓度也有助于缩短算法的求解时间，提高算法的运行效率.

3.2 改进蚁群算法流程

改进后蚁群算法流程如图4所示.

4 实验结果与分析

为了验证本文改进的蚁群算法的可行性，将本文算法应用在移动机器人路径规划中，同时和传统的蚁群算法和其他学者改进的蚁群算法做一个比较来证明本文改进的蚁群算法的优越性.实验环境是在windows7操作平台上运行MATLAB2016a软件将这三种算法进行比较.设置蚂蚁总数为M=100，初始ρ=0.8，C=0.8，参数α=1，β=5，信息素总量Q=1，最大迭代次数Nmax=100.图5和图6是本文改进的蚁群算法仿真实验结果.表1是本文改进的蚁群算法与文献[9]的比较.，通过表1对比可以发现，文献[9]中的改进的算法经过22次迭代达到稳定，而本文中的实验结果只需要经过16次迭代就达到稳定状态，收敛速度得到了显著的提高.

为了进一步验证本文所提出的改进的蚁群算法的可行性，对20*20的环境模型进行研究，图7、图8是本文改进的蚁群算法的实验结果，表2是与文献[10]的对比结果.通过表2可以看出本文的实验结果明显优于文献[10]的实验结果.虽然文献[10]与本文在最优路径长度上一样，但是本文在相同环境下，收敛速度更快，耗时不到文献[10]所用的的二分之一.对比结果进一步证明本文提出的改进的蚁群算法的有效性和优越性.

通过上述仿真实验的对比分析，传统蚁群算法具有收敛速度慢，易陷入局部最优解等问题，本文提出的改进蚁群算法有效地解决了这些不足.在改进算法运行初始阶段通过动态调整参数ρ来实现数据的更新，后期通过对信息素τij（t）的更新，能够提高算法的寻优能力，加快算法的收敛速度，快速找到最优路径.并且在遇到U型障碍物时，能够快速避开且继续寻找最优路径.

5 结论

本文针对移动机器人在路径规划中存在的收敛速度慢，易陷入局部最优解等问题，提出了一种全新的改进蚁群算法，首先自适应更新挥发系数ρ，使算法前期对搜索到的较优路径加大了搜索力度，后期则提高了算法的全局搜索能力，但是算法的收敛速度会明显降低.最后是通过动态改变信息素τij（t），利用精英选择在每次循环结束后对发现的最优解给予额外的信息素增量，用来在下一次的循环中对蚂蚁更具有吸引力，提高算法的收敛速度.在处理U型障碍物时，提出了丢弃死锁蚂蚁.通过以上大量仿真实验证明，改进后的蚁群算法在寻优能力上得到了显著的提高，有效地避免了出现死锁的现象，在与其他算法的比较中可以发现本算法在移动机器人路径规划中具有优越性和有效性.

参考文献：

〔1〕朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010（7）：4-10.

〔2〕Azimirad V， Shorakaei H. Dual hierarchical genetic-optimal control： A new global optimal path planning method for robots [J]. Journal of Manufacturing Systems， 2014， 33（1）：139-148.

〔3〕张广林，胡小梅，柴剑飞，赵磊，俞涛.路徑规划算法及其应用综述[J].现代机械，2011（5）：85-90.

〔4〕王雷，李明，唐敦兵，等.基于改进遗传算法的机器人动态路径规划[J].南京航空航天大学学报，2016，48（6）：841-846.

〔5〕吴庆洪，张颖，马宗民.蚁群算法综述[J].微计算机信息，2011，29（3）：1-2.

〔6〕黄挚雄，张登科，黎群辉.蚁群算法及其改进形式综述[J].2006，25（3）：35-38.

〔7〕裴振兵，陈学波.改进蚁群算法及其在机器人在避障中应用[J].智能系统学报，2015，10（1）：90-96.

〔8〕万晓凤，胡伟，方武义，等.基于改进蚁群算法的机器人路径规划研究[J].计算机工程与应用，2014， 50（18）：63-66.

〔9〕屈正庚，杨川.基于改进蚁群算法的移动机器人全局轨迹规划研究[J].南京师大学报：自然科学版，2015，38（1）：81-85.

〔10〕侯欣磊，于莲芝.基于改进蚁群算法的移动机器人路径规划[J].软件导刊，2017，16（12）：162-164.