基于蚁群算法的机器人移动路径规划优化*

徐 刚

(淮南师范学院机械与电气工程学院 安徽淮南 232038)

蚁群算法在解决机器人移动路径规划问题方面取得了较优的应用效果，是人工智能领域的关键性应用技术[1]。蚁群算法是基于蚂蚁觅食行为生成的一种群体智能算法，由于蚂蚁觅食期间是以一种最短的路径完成食物搬运，由此为各行业路径规划问题提供了借鉴与参考。其原因在于蚂蚁在觅食过程中自身释放一种信息素，一同觅食的蚂蚁可以感知信息素的存在，以最少的时间找到高浓度的信息素所在路线，下一次搬运食物时行走这条高信息素浓度的路线，每次搬运食物的蚂蚁留下更多的信息素，久而久之信息素浓度越来越多[2，3]。所以蚁群通过信息素这一介质构建了一种内部的信息通信机制，传递最短路径信息。该研究基于这一原理对传统的蚁群算法进行改进，以获取理想的机器人移动路径规划效果。

1基于蚁群算法的机器人移动路径规划优化方法

1.1基于栅格法的机器人移动环境建模

机器人所处的移动环境存在一定障碍物，所以需要对机器人移动环境进行建模处理，方便清晰获得最佳的机器人移动路径。此次研究使用应用频率较高的栅格法进行环境建模，图1为建模的具体情形。图中机器人移动环境的障碍物用黑色栅格描述，没有障碍的自由移动环境使用白色栅格描述。将环境中的障碍物转换为栅格模型过程中，可能存在不足一个栅格的障碍，此时以膨化方式进行处理，即不足一个栅格的障碍也视为一个栅格区域[4]。完成机器人环境建模后便可进行机器人最优路径规划研究。

图1 基于栅格法的机器人移动环境建模

1.2动态自适应信息素挥发因子更新

蚁群算法实现过程中准确把握信息素这一变量十分关键，决定了算法是否能够获得最优的机器人觅食路径。所以该研究着重对传统蚁群算法的“信息素”获取进行改进，包括两个方面：一是信息素挥发因子，二是信息素启发因子，实现方法如下。

传统蚁群算法中信息素挥发因子ρ为固定常数，难以实现算法高速收敛以及获得全局最优解，较小的信息素挥发因子虽然优化了算法的多样性、提高了算法搜索解的能力，但是收敛的时间开销较长；较大的信息素挥发因子则削弱算法多样性，虽然收敛的速度较快，但是往往得不到全局最优解，陷入局部最优。所以本研究根据算法所处的各个阶段以及实际情况确定ρ值，同时考虑算法的收敛速度与全局最优解问题。在蚁群算法中，公式(1)为蚁群路径信息素更新方法：

λpq=(1-ρ)·λpq+ρΔλpq

(1)

参考牛龙辉等人的研究对蚁群算法的固定信息素挥发因子进行调整[5]，采用公式(2)所示的动态调整函数进行ρ参数优化：

(2)

式中，算法迭代次数为n，δ、ε为常数。此公式中信息素挥发因子的变化取决于n，为单调递增的函数关系，同时决定了蚁群算法迭代过程中信息素挥发因子为动态变化的，其规律如下：算法前阶段n逐渐增加信息素挥发因子ρ平稳上升，这样可以为最优机器人路径选取留下更多的候选信息；算法迭代到中期阶段随着n的增加信息素挥发因子ρ上升的速度加快，这样可以加快算法收敛速度；算法后阶段尽管迭代次数n增加，但是ρ上升的趋势放缓。这种动态调整蚁群算法信息素挥发因子的策略有效解决了各阶段算法收敛速度、获取全局最优解的问题，更容易获得最优的机器人移动路径。

1.3信息素启发因子调整

蚁群算法中的信息素启发因子采用α表示，用于描述当前路径信息素对后面蚂蚁选择此条路径的影响程度，α值与后续蚂蚁选择当前路径的概率成正比；同时存在一个期望启发因子β，是对启发信息对蚂蚁路径选择影响程度的描述。由于算法迭代次数的增加，信息素的浓度、蚂蚁到达下一节点的距离作用产生不同程度的变化，所以算法前阶段搜索的时间开销增加[6]，此处采用公式(3)对两个启发因子α、β进行动态调整以解决上述问题：

(3)

式中，信息素的启发因子与期望启发因子的原始值用α1、β1表示；h和g分别为常数，在算法迭代的前中后期取值各有不同，相应的迭代比例系数以及迭代次数也有所差别，具体的取值规律如下[7]：

(1)前期：当h取值不小于0小于1时，g取值不小于1且小于2，u1

(2)中期：当h取值不小于1小于2时，g取值不小于0且小于1，r1×u2u1

(3)后期：当h取值不小于0小于1时，g取值不小于1且小于2，u1r2×u2，此时信息素量积累达到一定规模，容易陷入局部最优困境，因此需要削弱信息素对算法在此阶段迭代的干扰。上述描述中算法迭代次数最大值与此刻迭代次数分别使用u2、u1表示，迭代比例系数为r1、r2。

以上两种信息素的调整策略可以较好的避免算法陷入局部最优，并且缩短各个阶段收敛的时间开销，有利于蚁群算法在规划机器人移动路径过程中得到最优路径，并且提高规划效率。

2测试与分析

基于MATLAB平台进行仿真实验以验证文章方法在机器人移动路径规划中的有效性及应用效果。实验硬件条件设置如下：计算机为Windows10系统，内存为4GB，CPU为Core(TM)i5 2.6GHz。基于文章方法构建机器人路径规划的二维栅格地图，包括30×30个栅格，算法最大迭代次数设置为80，随后实验中机器人按照文章提出的改进蚁群算法进行路径规划。此外，将基于传统蚁群算法的机器人路径规划方法、基于自适应蚁群算法的机器人路径规划方法作为对比方法。

2.1 算法收敛曲线分析

在复杂环境中进行机器人移动路径规划测试，三种方法的收敛曲线如图2所示。

(a)基于传统蚁群算法的机器人路径规划方法

图2(a)中，传统蚁群算法的机器人路径规划方法由于选取的信息素挥发因子、启发因子均为固定值，没有根据算法迭代过程进行适时调整，所以在算法迭代前期和中期均经历了一定的困难，经过长时期的搜索才进行收敛，花费的时间较长。图2(b)中，自适应蚁群算法的机器人路径规划方法由于对信息素挥发因子进行了自适应调整，所以只有算法迭代的前期花费时间较长，在迭代中期和后期已经进入快速收敛阶段。相比之下，图2(c)中文章方法进行机器人移动路径规划的收敛曲线较为简单，说明该方法对信息素的挥发因子、启发因子优化调整后，较快完成机器人移动最优路径搜索，达到理想的收敛速度。总体而言，文章方法经过改进取得了较好的迭代收敛效果。

2.2 算法路径规划的性能分析

记录了实验中三种方法规划的最优路径以及所花费时间情况，结果如表1所示。

表1 三种方法的路径规划性能统计

表1数据显示，文章方法规划的最优路径最短，优于另外两种方法；并且文章方法仅通过22次迭代实现路径搜索，而基于传统蚁群算法的机器人路径规划方法、基于自适应蚁群算法的机器人路径规划方法分别经历78次、69次迭代才完成路径搜索，说明这两种方法的收敛效率较低；另外，文章方法获得最优路径的时间开销与另外两种方法所用时间相差不多，说明另外两种方法很可能是陷入了局部最优解，没有在接近的时间段内搜索到全局最优解。

4结论

文章对传统的蚁群算法的信息素进行改进得到一种崭新的机器人路径搜索方法，文章在蚁群算法迭代的前、中、后三个阶段对信息素挥发因子和启发因子进行动态改进，以应对算法各阶段可能发生的收敛速度慢、陷入局部最优的问题。在测试与分析环节证明了文章方法解决上述问题的有效性与可靠性，该方法在机器人移动路径规划方面不仅能够获得最短的路径规划结果，并且快速实现收敛提高了路径规划的效率，证明了该研究行之有效。