代婷婷

(昭通学院 数学与统计学院,云南 昭通 657000)

0 引 言

目前，机器人在众多领域发挥着重要的作用，人们可通过编程设计让机器人完成很多危险复杂的工作.关于机器人路径规划问题，科研人员提出了很多解决方案，例如，遗传算法、粒子群算法、人工势场法、蚁群算法等[1-4].虽然相关的智能算法比较多，但仍存在一些不足[5].其中，蚁群算法虽然在理论上能够找到最优解，在机器人路径规划方面的性能不错，但其仍存在如何快速有效地在全局范围内搜索出最优解的问题，对此，学者们对蚁群算法进行了各种改进.例如，Deng等[6]提出了动态搜索诱导算子，通过阈值p的动态变化极大地提高了算法解的质量和收敛速度；Cai等[7]通过人工势场法对蚁群算法信息素的挥发系数进行改进，提高了算法的最优解质量；赵静等[8]对蚁群算法的启发函数表达式进行了改进，在启发函数中加入了下一节点到目标节点之间的欧氏距离，使得当前节点与目标节点的联系更加紧密，从而提高了算法的求解效率；顾军华等[9]对于蚁群算法的信息素浓度更新提出了新的方案，从相反的方向对每次迭代中的最优最差路径上的信息素释放量进行干扰，避免了收敛过快而导致局部最优解的出现.在此基础上，本研究将文献[8]与文献[9]中相关的改进蚁群算法巧妙地融合而得出一种新的改进蚁群算法，并将其用于解决机器人路径规划问题，取得了较好的效果.

1 路径规划问题的环境建模方法

针对机器人的路径规划问题，通常需要对机器人所处的环境进行模拟建模.对此，本研究选择最常用的栅格法进行环境建模，此方法具有建立、表示与保存简单等优点.其思路是：将机器人所处的模拟环境分割成大小相同的一些正方形栅格，一个栅格表示一个单位，而每个栅格边长是环境最小行走单元，栅格内的情况可以忽略不计.具体步骤包括：首先，规定使用中心点来表示机器人的栅格坐标，并对栅格进行标记和编号，其可采用坐标法和序号法;其次，按照栅格所具有的属性，使用2种颜色将安全区域和障碍区域区别开，即机器人曾经走过的栅格划掉，其他安全的区域可以任意行走.图1为20×20栅格示例.

图1 20×20栅格示例图

2 基本蚁群算法

基本蚁群算法的思路是：在寻找食物的过程中，蚂蚁会在自己走过的搜索路径上释放信息素，而信

息素会对其他蚂蚁产生吸引作用.正是有这种相互作用的正反馈，使得蚂蚁搜索到的最短路径的概率和该路径上的信息素浓度成正比.按照此机制，就可以达到寻找到最短路径的目的.其具体的模型为：设i为外出觅食蚂蚁的出发点，则其到达觅食终点j的随机行进概率可表为，

(1)

式(1)表明:蚂蚁觅食过程中最容易被选到的那条路径具有较高的信息素浓度且距离蚂蚁较近；每一次每一只蚂蚁经过某一条路径后都会马上按照式(2)和式(3)更新该路径上的信息素[10].

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

(2)

(3)

3 改进蚁群算法与流程图

3.1 改进启发函数

基于基本蚁群算法的原理分析以及结合相关的文献，本研究认为，不但节点之间的概率转移能影响最短路径的计算结果，而且行走路径上的信息素浓度的更新对最短路径的影响也较为明显.一般情况下，可使用相邻节点i和j间的欧氏距离的倒数来表示转移概率中的启发函数.但事实上，开始搜索的最初阶段，由于蚂蚁数量不多，释放的信息素浓度较少使得更多蚂蚁偏离正确寻找路径的概率加大，从而形成局部最优解或无效解.对此，文献[8]在启发函数中引入了下一节点和目标节点之间的欧氏距离，从而加强了当前节点与目标节点的联系，其数学表达式为，

(4)

式中，dij表示当前节点i与下一个可行节点j之间的欧氏距离，djE是下一可行节点j到目标节点E的欧氏距离.

式(4)表明，由于加强了搜索路径的方向性，相应的运算时间可大为缩短，提高了算法的计算效率.

3.2 更新信息素浓度

研究表明，蚁群算法的效率受信息素浓度更新的影响极大[10].影响信息素浓度更新的主要因素包括：第一，行走路径的长度与信息素浓度的更新关系非常地密切，为了防止其积累过多而使算法过早局部收敛，信息素浓度进行更新是必不可少的；第二，由于大自然的固有特性，蚂蚁行走路径上的信息素浓度会随着时间的推移而挥发掉一部分，即浓度会不断降低；第三，经过行走路径的所有蚂蚁都会释放信息素，即最短路径上的蚂蚁最多，信息素浓度也最强；最后，要在全部路径中凸显出最优路径[11].对此，文献[9]的主要做法是沿相反的方向对当次迭代的最优和最差路径上的信息素进行改变，即最优的加强，最差的减弱，并将其按照式(5)的方式更新，防止算法收敛过快而陷入局部最优，

(5)

3.3 改进蚁群算法与计算流程

本研究根据以上2种文献相关算法改进的优点，将文献[8]中的启发函数改进和文献[9]中的信息素浓度更新的方案融合起来构成一种新的改进蚁群算法，即对启发函数进行改变，把与最终节点的距离加入其中，同时，增加或减少在信息素更新时找到的最优和最差解的信息素浓度，从而提高算法的性能.本研究的改进蚁群算法的具体计算流程如图2所示.

图2 改进蚁群算法的计算流程示意图

4 实证分析

为了验证本改进蚁群算法的实际效果，本研究选用MATLAB分析软件进行仿真实验，具体做法是分别使用基本的蚁群算法和本改进蚁群算法来进行测试.其步骤是，将机器人处于图1所示中的栅格障碍环境中，让机器人在该环境中寻找无碰撞的最短路径.在实验的过程中，设定找到一条从起点到终点的没有碰撞的最短路径是机器人工作的目的，从而比较使用2种算法使机器人在这个寻找最短路径的过程中找到最优路径用时最短的方法.

在测试中，对本改进蚁群算法在实验中的参数做表1所示的具体设置.

表1 实验过程中改进蚁群算法的参数设置

通过MATLAB分析软件的仿真试验，2种算法的测试结果如图3、图4所示.

图3 20×20栅格最优路径

图4 20×20栅格环境下基本蚁群算法与改进蚁群算法的收敛曲线

由图3可知，基本蚁群算法和本改进蚁群算法都寻找到了长度为29.21的最优路径，即2种算法找到的最优路径相同.尽管2种算法得到的最优路径是一样的，但从图4可以看出，这2种算法所使用的时间是完全不同的，基本蚁群算法找到最优路径需要18次迭代，而本改进的蚁群算法仅迭代到第3次的时候就已经找到了最优路径.此也表明，本研究的改进蚁群算法收敛速度很快，其搜索效率与基本蚁群算法相比有较大提升，可以在极短时间内搜索到最优解.

为了进一步显示本改进蚁群算法的特点，本研究将其与文献[8]和文献[9]所提算法的性能进行了对比，结果如图5所示.

图5 20×20栅格环境下3种算法的收敛曲线

由图5可知，由于同时对启发函数和信息素浓度的更新方式进行了改进，使得本研究所提算法具有明显的优势.与其他2种算法相比，本算法在搜索初期所走的路线更短.文献[8]算法在迭代第12次时，得到的路径长度为29.21，但收敛速度较慢.虽然文献[9]算法在迭代第8次时就得到长度为30.36的最优路径，拥有较快的收敛速，但得到的却是局部最优解.本算法在迭代第3次时就获得了长度为29.21的最短路径，明显地在大幅度提升收敛速度的同时获得了最短路径.

为更直观地展现本文算法与其他2种算法的对比优势，在表2中列出了上述3种算法运行10次的仿真结果.

表2 20×20栅格环境下3种算法仿真结果对比

根据表2的仿真结果对比可知:从搜索路径的长度上看，本文算法在迭代次数内仅有一次陷入了局部最优，其余几次均能快速地找到全局最优解，且在距离启发函数和自适应挥发因子的共同作用下拥有极强的逃离局部最优解的能力;文献[8]算法有数次找到了最优解，但还是有几次未能很好地实现寻优;文献[9]算法出现了几次搜寻路径较长，其寻优能力弱于上述2种算法.在迭代次数上，本文算法与文献[9]算法次数相差不大，与文献[8]算法相比大幅降低.在运算时间上，本文算法稍优于文献[9]算法，但均优于传统算法.据此可知，本文的相关改进使蚁群算法的缺点得到了较大改善，避免了算法易陷入局部最优的难题,同时收敛速度提升明显.

5 结 语

针对机器人路径规划问题，本研究根据文献[8]和文献[9]中的相关算法，提出了一种新的改进蚁群算法，具体改进体现为：第一，对启发函数中的2段距离之和做了平方处理，加强了搜索的方向性，使得搜索时间有所减少；第二，对信息素浓度的更新方式做了改变，避免了出现局部最优的情况.利用MATLAB分析软件对相关算法进行了仿真测试，结果表明：本改进蚁群算法与基本蚁群算法相比，虽然在相同的栅格环境中寻找的最优路径完全相同，但所需要的迭代次数较少；与文献[8]与文献[9]的2种算法相比，在寻找最优解和收敛速度方面都有比较明显的提升.