李文振，李富康，蔡宗琰，杨 嘉，杨新坤，赵宁宁

(长安大学工程机械学院，西安 710064)

0 引言

移动机器人的路径规划是通过避开障碍物，在其工作空间内找到起点和目标点之间的行程最短且无碰撞的最优路径[1]。为解决路径规划中存在的问题，学者们提出了人工势场法(APF)[2]、动态窗口法(DWA)[3]、遗传算法(GA)[4]、模糊逻辑法(FLA)[5]、神经网络法(NN)[6]和模拟退火算法(SA)[7]等。然而，这些算法都有一定自身的缺陷，如局部最小化、搜索效率低、收敛时间长、自适应能力差等问题，已不能很好地满足当下移动机器人获得最优路径的需求。

意大利研究人员在上世纪90年代提出了蚁群算法[8]，这是一种具有随机性的启发式搜索算法，属于群智能算法的一种，它源自于自然界中蚂蚁的集体觅食行为。由于自身善于解决分配问题的特点，蚁群算法已被成功地应用于作业分配、生产调度等相关领域[9]，蚁群算法还因为具有良好的自组织性、协同性和自适应能力强等特点，已逐渐在移动机器人路径规划领域得到应用[10]。

研究表明，蚁群算法中的转移规则是找到最短路径的关键，通过改进转移概率以帮助蚂蚁选择一个有很多安全出口的栅格；并基于全局启发式信息使其适应于大规模应用；同时，建立了一个改进的信息素更新规则，以提高全局搜索能力和加速收敛速度。

1 环境建模

三种常用的机器人环境建模方法有几何法、拓扑图法和栅格法。本文借助栅格法创建机器人的作业环境，工作区域被划分为二进制信息的栅格单元，其中二进制信息表示障碍物栅格为“1”，自由栅格为“0”。栅格地图为二维环境，置于正交参考坐标系XOY中，计算每个网格的坐标。通过假设整个栅格具有整数及其长度等于坐标的单位长度，栅格i所对应的坐标公式为：

(1)

式中，mod为取余运算；i为栅格的序号；int为取整运算；Nx表示每行的栅格数；Ny表示每列的栅格数。

图1为一个10×10栅格地图，其中黑色栅格代表空间障碍物，白色栅格代表自由空间。从图中可以看出，机器人可以向前、向后、右、左、右上、右下、左上、左下8个方向移动。

图1 栅格地图

2 蚁群算法理论

蚁群算法是一种求解优化问题的进化智能启发式搜索算法。它是根据蚂蚁在寻找从居住地到食物来源的捷径时的行为而开发的。在随机探索环境寻找食物的过程中，每只蚂蚁在经过的路径上都会释放出一定量的信息素；一旦有蚂蚁找到了食物，蚂蚁就会向信息素浓度高的方向移动，因为它们可以察觉到信息素的强度。当蚂蚁继续向信息素强的路径前进时，导致该路径信息素浓度增加，这将会吸引更多的蚂蚁到这条路径上，从而进一步增加该路径上的信息素浓度，以此类推，蚂蚁最终就会找到一条最短路径。

在每个时间t，蚂蚁k从它当前的栅格i移动到一个未访问的栅格j，基于它们之间的距离和连接它们的边缘上的信息素的数量。如果存在多个未访问的栅格，则蚂蚁k将根据以下的转换概率选择下一个栅格的位置。

(2)

式中，α和β表示路径选择过程中影响信息素和启发式信息的权重系数，Jk(i)表示未被访问的栅格集合，τij表示路径上的信息素浓度，ηij为启发式因子，表示从栅格i转移到栅格j的期望程度。

其中，ηij等于栅格i到栅格j之间距离的倒数，如公式(3)所示：

(3)

当所有的蚂蚁完成一次游历，路径上的信息素浓度将通过蒸发原有的信息素和增加蚂蚁积累的信息素来进行更新。信息素更新公式为：

τij(t+n)=(1-ρ)τijt+△τij

(4)

其中，ρ(0<ρ<1)表示路径上信息素的蒸发系数，1-ρ表示信息素的持久性系数；△τij表示本次迭代中边ij上信息素的增量，即：

(5)

(6)

3 改进蚁群算法

在传统的蚁群算法中，概率选择并不总能保证得出最优解，有时在优化早期段，算法就可能陷入局部最优；同时由于启发式搜索的局限性，算法收敛速度较慢。为了提高原有蚁群算法的性能并克服其缺陷，本文进行了以下改进。

3.1 改进转移概率

转移概率是一个组合运算，为了让蚂蚁更容易地选择下一个最佳栅格，它必须是一个可访问的栅格且有多个出口指向目标。这个概率取决于栅格周围障碍物的数量。所以，栅格周围的障碍物越少，概率就越大，栅格就越有吸引力。要确定转移概率，需要以下组合。

C(8，Nobw)是某一栅格i周围障碍物可能分布的个数，计算如下：

(7)

C(8-Nobw-1，1)，表示蚂蚁k可以离开栅格j的出口数量，表示为：

(8)

(9)

改进转移概率计算公式如(10)所示：

(10)

3.2 改进全局启发式信息

原有蚁群算法中，步长固定于相邻两个栅格之间，降低了栅格搜索的效率，导致收敛速度降低，使得算法无法找到最短路径。为了避免这些问题，采用了无限步长原理[16]，建立了新的全局信息，即在无限的启发式搜索和一个扩展视野的基础上的，移动机器人视野中的所有栅格都可以参与到下一个栅格的选择过程。

假设i和j分别是当前和下一个栅格，S和E分别是开始和目标栅格，d为两者之间的距离d(S,i)，d(i,E)，d(S,j)，d(j,E)，d(i,i)和d(S,E)。

在初始时刻，蚂蚁的运动方向必须朝向目标栅格，

(11)

在初始时刻之后，我们加入了多样性启发式搜索，我们必须保持既定目标栅格的方向不变。

如果d(S，i)

d(i，E)>d(j，E)，则：

(12)

如果d(S，i)

d(i，E)

(13)

如果d(S，i)>d(S，j)，则：

(14)

3.3 改进信息素更新原则

信息素的数量是选择一条最优路径的必要因素，然而，这其中含有一定数量的不良信息素，是由最劣的蚂蚁产生的，它可以使其他蚂蚁移动到目标不可达点或可能导致“早熟”停滞现象。因此，这就要求我们在每次迭代过程中，使最差局部路径的信息素浓度尽可能的减少，去增加最优局部路径的信息素浓度，以获得最优路径。

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

(15)

式中，

(16)

(17)

式中，spmax和spmin分别为转移概率的最大值和最小值，nbest和nworst分别为最优和最劣蚂蚁的个数，Lbest和Lworst分别为最优和最劣局部路径的长度。

4 算法实现

具体算法实现步骤如下：

步骤1：栅格化模型构建；

步骤2：参数初始化，令t=0，迭代次数NC=0，设定最大迭代次数T，起始点S，目标点E，蚂蚁数量m，启发因子α，β，蒸发系数ρ等参数；

步骤3：路径选择, 蚂蚁根据改进的状态转移概率公式(10)算出下一个栅格j；

步骤4：找出本次迭代的最佳路径并记录，利用公式(14)进行信息素更新；

步骤5：判断是否达到最大迭代次数T，如果满足条件输出最佳路径，否则返回继续执行步骤2。

改进算法的流程图如图2所示。

图2 改进蚁群算法流程图

5 仿真分析

为了验证改进蚁群算法的有效性，在(15×15)、(20×20)的栅格环境下分别对传统的蚁群算法和改进后的蚁群算法进行了MATLAB仿真验证。设定参数值分别为：m=50，T=100，α=1，β=5，ρ=0.5，Q=30。其中，起始点S位于左上角，结束点E位于右下角。

仿真结果如图3～图6所示，其中图3和图5分别为(15×15)、(20×20)的栅格环境下两种蚁群算法的路径；图4、图6为两种的栅格环境下的传统算法和改进算法的收敛曲线。表1为两种算法的统计结果。

(a) 传统蚁群算法 (b) 改进蚁群算法图3 (15×15)栅格环境下两种算法的路径图

图4 (15×15)栅格环境下两种算法的收敛曲线

(a) 传统蚁群算法的路径 (b) 改进蚁群算法的路径图5 (20×20)栅格环境下两种算法的路径图

图6 (20×20)栅格环境下两种算法的收敛曲线

表1 两种算法统计结果

可以看出，改进蚁群算法比传统算法具有更短的搜索路径、更快的收敛速度、更小的迭代次数等特点。因此，优化后的蚁群算法与传统蚁群算法相比具有一定的优越性。

6 结束语

本文提出了一种改进的蚁群算法，并在解决移动机器人路径规划问题时与传统算法进行了比较，证明了改进后蚁群算法的优越性。主要在以下三个方面进行了改进：提出了一种基于转移概率的转移准则，用以选择一个安全可达的栅格；采用自由步长的方法，建立了新的全局启发式信息原则，增加了可视精度和搜索效率；改进了信息素更新原则，提高了全局搜索能力和收敛速度。仿真结果表明，本文提出的改进蚁群算法在缩短搜索路径和提高收敛速度方面明显优于传统蚁群算法。由此可见，研究结果证明了所改进的蚁群算法在解决静态环境下的路径规划问题的潜力。

未来，将进一步针对动态环境中的路径规划问题，对所提出的算法进行后续的优化改进以及实验验证。