基于静电势场法改进的蚁群算法用于路径规划

文/尤润川

（湖北工业大学 湖北省武汉市 430068）

近年来，智能自主移动机器人得到了广泛的关注。在机器人技术中导航任务十分复杂，其中路径规划是非常重要的一项技术。移动机器人的路径规划指的是确定移动机器人如何安全地到达目标的策略，以确保避免障碍[1]。

针对移动机器人路径规划的问题，国内外学者做了很多方面的研究。文献[2]中引入激励函数改进基本蚁群算法的启发函数，增强了路径平滑性，降低搜索过程的死锁现象，文献[3]中利用机器人当前朝向和下一次位置的方位之间的夹角来改变蚂蚁的转移概率，不仅增强了路径的平滑性，也缩短了路径的长度。文献[4]中提出了静电势场法用于路径规划，和人工势场法不同的是，静电势场是标量场只有大小没有方向，便于计算，降低了路径规划过程中计算的复杂度，缩短了路径规划的时间。

本文将蚁群算法与静电势场法结合，将静电势场函数引入蚁群算法的启发函数中，不仅考虑下一个节点到目标点的距离，还考虑障碍物的影响，增加初始搜索阶段的目的性；加入回退机制，减少蚁群算法容易死锁的问题；将挥发因子设置为动态的，增强初始阶段的搜索能力，同时保证后期的收敛速度。

1 基本的蚁群算法

1.1 环境的建模

本文主要研究二维平面内移动机器人的路径规划问题，不考虑环境中障碍物以及机器人的高度，采用栅格法对环境进行建模，将环境抽象为一个二维平面，根据移动机器人的大小和步长将平面分为若干个等大的正方形栅格，如图1所示。

栅格编号与坐标的转换公式如下：

其中a为栅格的边长，mod为取余运算，Ni为栅格编号，l为每行栅格的个数。ceil为向上取整运算。同时将障碍物也抽象为栅格，黑色的栅格表示障碍物。为了防止障碍物与机器人的碰撞，对障碍物进行膨胀处理，使障碍物的边界向外膨胀，膨胀的宽度为机器人的半径。机器人所在位置在没有障碍的情况下有8个可移动的位置。

1.2 蚁群算法的基本原理

首例蚁群算法由Dorigo提出，被称为蚂蚁系统[5]。在蚂蚁系统中，最核心的是转移概率，表示蚂蚁从点i移动到点j的概率,计算公式如下：

其中djE表示位置j到位置E的距离。α，β分别表示信息素浓度和启发式信息对转移概率的影响程度，体现了蚂蚁对记忆的优质路径和先验知识的倾向性。

当一代蚂蚁全部从起点移动到终点或者走到没有位置可以移动的节点，表示这一代蚂蚁工作结束，开始对信息素进行更新。更新公式为：

其中t表示迭代次数，ρ表示信息素挥发系数，m表示每代蚂蚁的数量，Q是一个常数，表示一只蚂蚁在所在路径上释放的信息素，Lk表示蚂蚁所走过完整路径的长度。

2 静电势场法

静电势场法同样以栅格法对环境建模，然后对每个障碍物建立势场函数，把每个障碍物看做是带正电荷的粒子，在周围产生势场，势场函数为：

其中(xi,yi)表示编号为i的障碍物的中心坐标，βi是与障碍物的面积成反比。

Ai表示编号为i障碍物的面积，将所有障碍物的势场函数累加得到下式。

建立势场函数意在使移动机器人尽量避开势场高的地方，从而找到一条没碰撞的路径。然而这样并不能保证能够找到一条比较优质到达目标点的路径，因此定义代价函数：

通过找到当前位置周围8个位置上代价函数最低的位置作为下一次移动的位置，重复这个过程，直到到达终点。

图1：栅格法环境建模

图2：死锁示意图

3 基于电势场法的蚁群算法

利用传统的蚁群算法进行路径规划时，前几代蚂蚁留下的信息素少，同时初始化信息素是平均分配的，蚂蚁在寻找路径的过程中，主要在启发函数的作用下进行移动，避障能力较弱，效率低下，很多路径都是在重复无用的搜索。因此本文对启发函数进行改进，让算法早期的搜索更有目的性，不仅具有向目标点搜索的能力，同时也能具有避开障碍物的能力。在蚁群算法前期，需要快速的找到可行解，不需要过度要求路径的长度，使用静电势场法快速避障的特点，快速找到可行的解。到了蚁群算法后期，要得到更高质量的路径，即蚁路径长度要求尽可能的短，因此要降低静电势场的影响，使路径不是主要绕行障碍，而是能够尽快到达目标点，后期就要降低启发函数中静电势场的影响值。改进的启发函数如下式：

传统的蚁群算法在前期的搜索过程中盲目性强，在地形复杂的环境中，如U形障碍，容易陷入死锁，导致本次蚂蚁搜索无效。

如图2所示，移动机器人在R所标注的位置，当其向图示方向移动时就会陷入死锁问题。当移动机器人从位置R移动到位置1时，它下一次移动的位置只能是位置2，到达位置2陷入死锁，此时采用回退机制，让移动机器人回退到位置1，位置2加入禁忌表中，然后发现移动机器人依然没有位置可以移动，继续回退，退到位置R,将位置1加入禁忌表中，移动机器人回到位置R,可以正常移动。同时对位置R到位置1，位置1到位置2进行惩罚，使其信息素含量降低50%，避免下一只蚂蚁进入死锁。

传统的蚁群算法中，在一代蚂蚁全部移动到终点或出现死锁的情况之后再对信息素进行更新，所有的蚂蚁走过的路径信息素都会增加，然而早期蚂蚁的路径的随机性强，所走出来的路径不够优质，因此没有必要将所有的路径都进行信息素的更新，只需要选择其中路径相对较短的路径进行信息素的更新，使算法更快收敛，更新公式如下式。

蚁群算法前几代蚂蚁的路径的参考价值相对较低，这里动态的改变信息素挥发因子的ρ，使其在蚁群算法早期有一个相对较大的值，降低蚁群算法前期的信息素对转移概率的影响，然而到后期有一个相对较小的值使信息素对转移概率的影响较大，加快收敛速度。基于静电势场法的蚁群算法路径规划步骤如下：

（1）初始化参数，用矩阵G表示已知的环境模型，确定起始点S和终点E，通过式（1）计算出障碍物的坐标。设定表示信息素和启发函数重要程度的参数α，β，种群数量为M，迭代次数上限为K。初始化信息素强度Tau,设定信息素增强系数为Q。

图3：改进前后的蚁群算法在障碍物较多的环境下仿真结果

（2）蚂蚁种群从起始位置出发，获取可行节点，通过式(2)建立概率分布律，利用轮判赌的方式选择当前这只蚂蚁移动的下一个位置，蚂蚁移动到所选择的位置，并将上一个位置加入禁忌表中。如果蚂蚁获取可行节点的数量为零，蚂蚁回退到上一次位置，将当前位置加入禁忌表，并降低回退机制触发时所移动位置的信息素至50%，降低其他蚂蚁和后代蚂蚁选择此节点的概率。然后进行下一个节点的选择，直至到达终点E。

（3）当此代蚂蚁全部寻路完毕，记录M只蚂蚁的路径长度，对没有到达终点E的蚂蚁的路径长度设置为无穷大。通过式（12）计算当代蚂蚁信息素发挥率，然后对路径长度短的路径通过式（11）进行信息素更新。

（4）判断迭代次数是否到达上限，若没有到达上限，迭代次数加一，然后重复进行步骤（2）、（3）、（4），直到迭代次数到达上限，然后输出最短的路径。

4 仿真结果与分析

本文利用MATLAB 2014b软件进行仿真，实现了基本蚁群算法的路径规划以及改进后的蚁群算法路径规划。基本蚁群算法的参数为，改进的蚁群算法参数为，信息素挥发速率采用式(12)，启发函数采用式(10)。本文在复杂环境下分别利用基本蚁群算法和改进的蚁群算法进行路径规划，仿真结果如图3所示。

由图3可知，基本蚁群算法和改进的蚁群算法均能得到一条可行的路径到达目标点，改进后的蚁群算法得到了更短的路径，收敛速度更快，由于回退机制的加入，死锁情况减少，到达目标点的路径更多。

5 结束语

针对基本蚁群算法前期搜索能力差并容易出现死锁的问题，改进了蚁群算法的启发函数，使蚁群算法前期的搜索能力更强，对死锁问题进行回退处理，增加路径的有效性，使搜索能力加强。同时动态化信息素的挥发速率，使得前期信息素影响小，搜索能力强，后期信息素影响大，加快收敛。仿真表明，改进的蚁群算法的搜索能力更强，在复杂环境下比基本蚁群算法规划的路径更短，收敛速度更快。