一种改进蚁群算法的路径规划研究

刘海鹏,念紫帅

(昆明理工大学 信息工程与自动化学院,昆明 650500)

0 引 言

路径规划是机器人研究领域的一个关键问题.通常,路径规划是指机器人根据已知条件独立规划的安全无碰撞的路径[1].路径规划使用的算法有遗传算法[2]、人工势场法[3]、粒子群算法[4]、A*算法[5]、RRT算法[6]等.然而,这些算法存在着稳定性差、效率低等问题.与上述算法相比,蚁群算法具有鲁棒性强、路径规划效果好等优点.但是,在复杂环境下,蚁群算法存在局部最优、搜索时间长等问题.

为此,许多专家学者从信息素更新以及与其他智能算法的结合等方面改进了蚁群算法[7].文献[8]通过设计一种基于路径几何特征的局部优化方法,进一步优化了初始路径,显著的提高了算法的收敛速度.文献[9]通过引入惩罚因子,对死锁路径点上的信息素进行惩罚,有效的减少了死亡蚂蚁的数量,确保了解的多样性.文献[10]通过对路径进行几何局部优化,并沿着势场力的方向扩散信息素,减小了蚂蚁的搜索空间.文献[11]采用进化的思想改进信息素更新策略,使算法的收敛速度得到提高.文献[12]提出了一种孤狼-蚁群组合策略.采用独狼视场机制和自适应增强函数来优化蚁群的寻优能力.文献[13]通过利用零点定理,提出了一种不均衡分配的初始信息素方法,避免了蚁群在搜索过程中过于盲目的情况,使算法的搜索效率得到明显的提高.文献[14]通过引入一种动态分组协作算法,该算法同时结合了蚁群系统和最大最小蚂蚁系统,形成了一个异构的多种群结构,每个种群可以实现相互进化,相互补充,从而显著的提高了算法的整体性能.文献[15]提出了一种具有惩罚性措施的蚁群算法,利用惩罚策略对最坏路径的信息素浓度进行惩罚,通过信息素的挥发降低蚂蚁遍历最坏路径的概率,引导蚂蚁探索其他未知区域,提升了算法的全局搜索能力.文献[16]通过在原有算法的基础上采用了多步搜索策略来代替单步搜索策略的方法,并对信息素更新机制进行重新设计,以及对规划出的路径进行平滑处理,使算法的整体性能得到了明显的提升.

本文对蚁群算法在复杂环境中的问题进行了如下改进:1)通过在启发函数中引入一种自适应调整的放大因子,使相邻节点的启发信息差异得到增大,增加了蚂蚁选择最优路径的可能性;2)采用一种奖惩机制更新路径上的信息素,可以在很大程度上提高算法的收敛性;3)对信息素挥发因子采用动态调整的方法来提高蚁群的搜索速度,使算法快速收敛;4)对改进算法生成的路径进行优化处理,提高了路径的平滑性.

1 环境模型

在研究路径规划的过程中,需要选择状态空间描述方法来建立环境模型.本文采用栅格法[7,17]来进行环境建模.栅格法的工作原理是假定机器人运动的环境是在一个二维空间,就可以将这个空间划分为许多大小相同的单元.可以根据栅格中是否存在障碍物来对栅格的状态进行判断.若栅格中存在障碍物,则对应的栅格状态为1;否则,对应的栅格状态为0.栅格地图如图1(a)所示.白色部分为无障碍物的栅格,机器人可以向其移动,黑色部分为有障碍物的栅格,机器人不能向其移动.如果将机器人看做一个质点,当周围没有障碍物存在时,8个方向都可以满足机器人的运动要求,机器人的运动方向如图1(b)所示.

图1 栅格环境模型Fig.1 Raster environment model

2 传统蚁群算法

蚁群算法是一种比较典型的启发式搜索算法,蚂蚁可以本能地找到从某一点到食物来源的路径.在t时刻,第k只蚂蚁从节点i移动到节点j的概率转移公式如下:

(1)

(2)

式中,τij(t)为信息素浓度,α为信息素启发因子,β为期望启发因子,ηij(t)为启发函数.allowedk为路径搜索所有下一可达节点的集合.dij为当前节点i和待选节点j之间的欧氏距离.

在完成一次迭代后,蚂蚁会在路径上留下信息素,路径上原有的信息素会得到改变.信息素更新公式如下:

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

(3)

(4)

(5)

3 蚁群算法改进

3.1 启发函数的设计

传统蚁群算法的启发函数通常只取相邻节点距离的倒数,由此忽略了待选节点与目标节点之间的距离,这使得蚂蚁在进行路径选择时倾向于选择距离当前节点最近的节点.当蚂蚁无法搜索到最优路径时,就会发生死锁的状况.于是,本文不仅考虑了待选节点与目标节点的距离,还引入起始节点到待选节点的距离.由于相邻节点距离差异较小,对整体的启发信息影响不算明显.为此,本文采用一种随迭代次数自适应变化的放大系数.算法前期,使得相邻栅格的启发信息差异得到明显增大,在很大程度上增加了蚂蚁选择最优路径的可能性.算法后期,可以减小启发信息带来的影响,有效的避免了局部最优情况的发生.对应的改进公式如下:

(6)

(7)

式中,djg为待选节点和目标节点之间的欧式距离,dSj为起始节点和待选节点之间的欧氏距离,N为当前迭代次数,Nmax为最大迭代次数.

3.2 改进信息素更新策略

传统的信息素更新策略是在一次迭代结束后,将那些到达目标点的蚂蚁找出来,并在它们所经过的路径上增加信息素.但是,这种情况下,如果给那些劣质蚂蚁走过的路径增加信息素,就会影响到后续迭代中的蚂蚁.于是,本文采用一种奖惩机制[18]来更新路径上的信息素,即对最优路径上的信息素采取奖励的措施,对最差路径上的信息素采取惩罚的措施,从而使算法快速收敛.对应的信息素更新策略的改进公式如下:

(8)

(9)

式中,Lb和Lw为当前迭代中最优路径和最差路径的长度,Lave为当前迭代中的平均路径长度,Lk为本次迭代第k只蚂蚁走过的路径长度,ψ、φ为权重系数.

3.3 改进信息素挥发因子

由于路径规划的特殊性,不同阶段对信息素挥发因子ρ的取值要求也不一样.ρ过大会出现路径上信息素挥发较快的情况,不利于算法收敛.反之,随着时间的增加,信息素会被大量积累,就会出现算法陷于局部最优的情况.于是综合以上情况,本文采用一种动态调整的方法来改进ρ.在算法初始阶段,给ρ设定一个较大的值来加大搜索范围;在后续过程中,采用不断减小ρ的方式来加快算法的收敛速度.对应的改进公式如下:

(10)

式中,ρmax和ρmin为信息素挥发因子的最大值和最小值.

3.4 路径优化策略

3.4.1 拐点优化算法

为了减少路径中的冗余节点,本文引入了一种拐点优化算法,该算法可以在很大程度上将路径长度和平滑度进行优化.

拐点优化算法的过程如下:在一条起点到目标点的路径中,节点间的连线不经障碍物,则连接下一节点,直到与障碍物相交,将起点与临近的那个未穿越障碍物的节点相连接,并将该节点作为新的起点,直至所选节点与目标点重合才算完成整个优化过程.如图2(a)所示,初始路径为S→A→B→C→D→G,经过拐点优化处理后的路径为S→B→C→G.由此可见,经过拐点优化,路径节点更少,路径长度更短.

图2 路径优化处理Fig.2 Path optimization processing

3.4.2 分段B样条曲线

为了进一步改善路径的平滑性,引入分段B样条曲线[19]对拐点优化算法所生成的路径进行进一步的优化处理.采用分段B样条曲线可以更好地满足机器人在栅格环境下的运动要求,在一定程度上减少了机器人与障碍物发生碰撞的可能性.

由u+1个控制点Hi和一个结点向量n定义的B样条曲线,公式为:

(11)

式中Fi,k(n)是基于B样条的函数,下面是递归公式:

(12)

(13)

分段B样条对原始路径每个转折点附近的路径进行平滑处理.分段B样条处理结果如图2(b)所示.Li-1→Li→Li+1表示未经处理的路径,Li为路径上面的转折点,Li附近的路径需要进行平滑处理.

M1Li=M2Li

(14)

在Li-1Li上取一点M1,同时在LiLi+1上面取一点M2,M1M2为优化后的曲线,在这里对转折点两侧选定同样长度的线段进行优化处理,具体选取的线段长度根据具体的实验环境而定.

3.5 本文算法的步骤

步骤1.栅格法建模,并对算法中所用到的各个参数进行初始化设置;

步骤2.将m只蚂蚁放在起始点,并将该点加入禁忌表;

步骤3.利用式(6)计算启发函数并用转轮赌法来选择下一节点,并更新禁忌表;

步骤4.若蚂蚁抵达目标点,则进入步骤5,否则回到步骤3;

步骤5.若蚂蚁达到m只,则进入步骤6,否则回到步骤2;

步骤6.利用式(8)更新路径上的信息素;

步骤7.若满足N=Nmax,则进入步骤8,否则回到步骤2;

步骤8.利用拐点优化算法和分段B样条曲线对规划出的初始路径进行平滑处理,输出最终结果.

4 仿真与分析

为了充分验证本文算法的有效性,选用了3种不同规模的地图来进行机器人路径规划的仿真实验,分别是20×20规模、30×30规模和40×40规模的栅格地图.考虑到本文所研究的算法与其他文献中的算法在参数的数值设置方面存在着一定程度上的差异,为此这里直接引用原始文献中的实验数据来进行仿真实验上的对比分析[20].并且考虑到算法运行时间这个指标在很大程度上与计算机所对应的处理器的性能有关联,这里引用文献[21]实验中不同实验设备等效耗时的思想,将原文文献中的时间与本文算法中的运行时间进行比例换算,即根据原文文献设备得出的算法运行时间,通过换算得到原文文献在本文设备中的算法运行时间.通过这种方法有效的解决了不同实验设备在时间指标上存在差异的情况,在一定程度上使实验的数据结果变得真实可靠.同时为了便于实验的对比分析,4.1、4.2和4.3所用到的实验参数会与公共参数存在略微差异,这里为了使Nmax和m这两个实验参数尽可能的与原文文献保持一致,最大程度上保证实验上的严谨性,后面实验中就不再对修改实验参数这项进行更多的说明.实验运行环境为:Windows11 64 bit;Matlab R2021a;处理器Intel(R)Core(TM)i5-1135G7 @ 2.40GHz;内存16GB.本文实验设计中所用的公共参数是根据许多次的的实验分析所得出的,这里采用多次实验的方式来找出满足实验最优结果的最佳参数值.实验公共参数如表1所示.

表1 实验公共参数Table 1 Experimental public parameters

4.1 20×20仿真环境

在20×20规模的地图环境下,将本文算法与传统蚁群算法,文献[22]算法进行仿真实验.实验参数:m=30,其他参数与表1相同.3种算法规划的路径如图3(a)所示,其中带圆圈标记的细实线为传统蚁群算法规划的路径,细实线为文献[22]算法规划的路径,粗实线为本文算法规划的路径;收敛曲线对比如图3(b)所示;实验结果对比如表2所示.从实验结果可以看出,本文算法的路径长度要优于其他两种算法,可见本文算法具有很强的搜索能力,能够搜索到较优的路径.并且本文算法的路径更加平滑,表明在经过拐点优化算法与分段B样条曲线的优化处理后,路径的平滑性有了进一步的提高.通过图3(b)可以很明显的看出,本文算法要比其他两种算法更快的找到最优路径,收敛于最优解.在程序运行时间方面,本文算法和文献[22]算法差别不大,相比传统蚁群算法则有着较大的改进.显然,本文的改进算法在20×20规模的地图环境下,相比较其他两种算法路径更优,算法的收敛性更强,搜索路径的效率更高.

表2 实验结果对比Table 2 Comparison of experimental results

图3 路径规划结果Fig.3 Path planning results

4.2 30×30仿真环境

在30×30规模的地图环境下,利用两个不同的地图环境,进行两组不同的对比实验.

4.2.1 实验1

将本文算法与传统蚁群算法,文献[13]算法进行仿真实验.3种算法规划的路径如图4(a)所示,其中带圆圈标记的细实线为传统蚁群算法规划的路径,细实线为文献[13]算法规划的路径,粗实线为本文算法规划的路径;收敛曲线对比如图4(b)所示;实验结果对比如表3所示.从实验结果可以看出,本文算法搜索到的路径长度更短,路径更加平滑,搜索到的路径也更加符合机器人的行走路线,而传统蚁群算法和文献[13]算法路径长度还需要得到进一步的优化,特别的就传统蚁群算法而言,由于算法搜索路径的效率较低,以及路径搜索中难以避免的陷入局部最优解的情况,所生成的路线过于差,不能很好的满足机器人的行走要求.程序运行时间方面,本文算法要稍逊于文献[13]算法,相比较传统蚁群算法仍然存在着明显的提高.根据图4(b)可以很明显的看出,本文算法在收敛速度上要优于另外两种算法,并且所对应的收敛曲线并没有存在什么波动,整体更加平稳,同时根据收敛曲线可以很清楚地看出,本文算法要更早的达到稳定效果.至于与文献[13]算法在时间方面的不足可以进行舍弃,以得到路径长度和收敛速度上的提升.综合以上可以得出,本文算法得到的的路径相对于其他两种算法而言,路径更优,同时收敛速度更快.

图4 路径规划结果Fig.4 Path planning results

4.2.2 实验2

将本文算法与传统蚁群算法,文献[23]算法进行仿真实验.实验参数:Nmax=150,m=100,其他参数与表1相同.3种算法规划的路径如图5(a)所示,其中带圆圈标记的细实线为传统蚁群算法规划的路径,细实线为文献[23]算法规划的路径,粗实线为本文算法规划的路径;收敛曲线对比如图5(b)所示;实验结果对比如表4所示.从实验结果可以看出,由于本文算法高效的搜索能力以及拐点优化算法和分段B样条曲线先后两次优化处理,使得本文算法在路径长度上优于文献[23]算法和传统蚁群算法.根据图5(b)可知,传统蚁群算法和文献[23]算法都存在着较明显的波动,而本文算法基本没什么波动,整体来看较为平稳.同时,本文算法在收敛速度上相对于另外的两种算法明显更快.表明,本文算法的改进策略可以使算法的收敛速度得到明显的提高.因此,本文算法相比其他两种算法,具有搜索能力强和快速收敛的特点.

表4 实验结果对比Table 4 Comparison of experimental results

图5 路径规划结果Fig.5 Path planning results

4.3 40×40仿真环境

在40×40规模的地图环境下,将本文算法与文献[23]算法,传统蚁群算法进行仿真实验.实验参数:Nmax=400,m=100,其他参数与表1相同.3种算法规划的路径如图6(a)所示,其中带圆圈标记的细实线为传统蚁群算法规划的路径,细实线为文献[23]算法规划的路径,粗实线为本文算法规划的路径;收敛曲线对比如图6(b)所示;实验结果对比如表5所示.从实验结果可以看出,本文算法经过前期的改进以及后面拐点优化算法和分段B样条曲线的优化处理,所规划的路径更加平滑,也符合机器人的行走路线.文献[23]算法和传统蚁群算法的路径长度要高于本文算法,整体上还需要进一步的提高.从图6(b)可知,传统蚁群算法在前期存在十分明显的波动情况,只是随着迭代的增加这种波动情况开始逐渐减小,直至稳定.文献[23]算法同样前期存在着较大的波动,后面才得到明显的降低,迭代到一定程度才稳定下来.而本文算法几乎没有存在波动的情况,整体比较平稳,说明本文算法的收敛效果较为明显.由此可见,本文算法在规模大,环境复杂度高的地图中,仍然存在着很大的优势.

表5 实验结果对比Table 5 Comparison of experimental results

图6 路径规划结果Fig.6 Path planning results

5 结 论

本文提出了一种改进蚁群算法的路径规划研究方法,来解决机器人在复杂环境下的路径规划问题.该方法在启发函数中引入动态调整的放大因子,来增大相邻节点的启发信息差异,从而增加蚂蚁选择最优路径的概率;采用一种奖惩机制更新路径上的信息素,使算法的收敛速度得到加快;通过动态调整信息素挥发因子,加快了算法的收敛速度;在最优路径的基础上进行路径优化,改善了路径的平滑性,更好的满足机器人在栅格环境下的运动要求.实验研究表明,本文改进的算法能够应用在规模性大,复杂度高的地图环境中,并且在一定程度上有着较高的实用意义.由于本文研究主要是在静态环境下进行的,下一步研究可以将路径规划应用在动态环境领域.