基于改进势场与蚁群算法的机器人路径规划法

刘 瀛

(辽东学院化工与机械学院，辽宁 丹东 118000)

1 引言

路径规划是机器人控制领域研究的重要方向和组成部分[1]，是指为移动机器人在已知或未知障碍环境下从起点规划一条至目标点的能耗与时间最少的最优安全无碰撞路径，目前，国内外在这一方面的诸多研究已取得显著成果，如Dijkstra算法、人工势场算法[2]、A*算法[3]、蚁群算法[4]及神经网络算法等。

蚁群算法具有较强的鲁棒性，采用正反馈机制和并行分布式计算，更适于障碍环境的路径规划，但传统蚁群算法搜索效率较低，且易陷入局部最优[4]。人工势场算法(Artificial Potential Field，APF)原理简单且计算量小，具有较快的路径规划效率，但复杂障碍物环境下，易出现死锁和目标不可达现象[2]，为此，近年来，研究人员综合了势场和蚁群两种算法优点，提出基于人工势场和蚁群算法的联合算法[5]，但由于势场与蚁群算法自身问题影响，势场蚁群算法仍存在计算量大、收敛慢和最优解性能较差等问题[6]。张强[7]等以有效障碍物识别和边界中间点设置改进APF，并以改进的APF优化蚁群初始路径筛选，缓解初始路径交叉影响收敛速度问题，以负反馈通道构建全局和局部信息素的自适应更新，保证算法的收敛速度与全局搜索能力的统一；王钦钊[8]等以势场法得到的预规划信息构建信息素矩阵优化蚁群初始路径搜索，以自适应伪随机转移函数和代价函数平滑信息素更新过程，得到复杂障碍环境下的最优路径规划，新算法具有较好的收敛速度和全局寻优能力[9]；LIU等[10]以改进的APF算法优化蚁群算法的初始信息素设置，提高蚂蚁在路径搜索初期的方向性；Park等[11]以改进后的APF合力优化启必信息和挥发因子的设置，并联合APF目标距离避免算法陷入停滞；李宪强等[12]将APF算法引入到初始信息素分配中，避免迭代初期信息素与启发信息不匹配而造成的路径趋向于强启发信息一侧，其次以APF引导函数优化蚁群状态转移函数，避免盲目选择影响算法的收敛速度。陈余庆等[13]将改进的APF引力和斥力附加到蚁群路径寻径过程的信息素增量计算中，提高了蚁群算法的全局路径寻优的效率；王晓燕等[14]将APF初始预规划路径及不均衡分配策略附加到蚁群算法的启发信息和初始信息素中，改善了蚁群算法的全局搜索效率。

在已有研究基础上，提出了基于改进的势场与蚁群算法的机器人路径规划算法。算法首先利用斥力距离值引入和增设虚拟子目标点改进经典人工势场算法，以优化其目标不可达和局部欠优问题，并通过过滤振荡点平滑最优路径，其次，在改进势场优化蚁群初始路径筛选基础上，通过挥发因子的自适应设置与全局搜索策略的改进，提高蚁群算法对不同复杂障碍环境的适应性和全局最优路径的有效性。实验结果验证了该算法的有效性。

2 改进APF局部路径规划

2.1 运动环境模型构建

运动环境的合理建模是实现机器人行进路径精确规划的基础，为此，将环境建模为二维平面，而移动机器人则为平面内的点状移动物体。设环境栅格为M={Mi，i=0，1，2，3}，则栅格值i=0，1，2，3分别描述了起始位置、无障碍区域、障碍区域和目标位置，如图1所示为环境建模结果。

图1 算法分析采用的环境模型

环境模型使用的栅格大小影响路径规划的精确性，较大的栅格值可减少计算量，但路径较为粗糙，且长度会增加，而过小的栅格尺寸，可以提高路径的精细度，但计算过程缓慢，算法的实时性较差，为此，实验中对环境进行建模时，通过需要根据实际环境情况确定建模栅格尺寸，即

(1)

式中，r与R分别为障碍物和机器人建模后的等效尺寸半径，δ为预设的距离安全值。划的准确度就会提高，但规划过程缓慢。根据图1和式(1)建模后，机器人路径规划可描述为在栅格化环境模型中搜索一条连续最短的无障碍路径。

2.2 传统APF算法

APF算法为基于运行环境中的斥力与引力合力作用的一种人工力场虚拟力法[9]，运动声中的障碍物对机器人产生斥力作者，而规划路径的最终目标点则对机器人产生引力作用，两种人工力场的共同牵引作用下，机器人以最优路径到过目标点。

根据图1所示，设机器人与目标点的位置分别为M1=X=[x，y]和M3=XM=[xm，ym]，则APF的引力为[9]：

(2)

(3)

式中，k0>0为斥力增益系数，ξ为机器人与障碍物之间的距离，ξ0为障碍物作用范围，ξ≤ξ0，则运动环境中，机器人的受力合力为

F(X)=FG(X)+F0(X)

(4)

传统APF算法通常存在局部最小值、引力斥力不足及目标不可达等问题，为此，提出改进的APF算法。

2.2 改进APF算法

针对传统APF存在的目标不可达局限，根据已有文献[11]研究，对传统APF算法的斥力中引入距离值，同时约束合力势场的全局极小值点为路径目标点，以使机器人稳定停止在目标位置，优化后的斥力势场函数为

(5)

式中，ρo为目标点附近障碍物的影响范围值，ρ(X，Xo)为某一时刻机器与障碍物之间的欧氏距离，当ρ(X，Xo)≤ρo时，上式成立，反之有Urep(X)=0，ρ(X，Xg)不某一时刻机器人与目标点之间的欧氏距离，n为某正的调节常数。对式(5)所示斥力势场函数求负梯度，则得到改进算法的斥力计算式为

Frep(X)=Frep1(X)-Frep2(X)

(6)

式中，Frep1(X)和Frep2(X)的计算式为

(7)

(8)

从式(7)和式(8)计算式可以看出，式(6)中的Frep1(X)和Frep2(X)分别描述了障碍物指向机器人的斥力和机器人指向目标点的引力，这样，当机器人向目标移动时，Frep1(X)减少至0，而当0

(9)

式中，m为目标点附件的存在有效斥力的障碍物数。设F与坐标x轴夹角为θ，k为路径序号点，则机器人的下一路径点(xk+1，yk+1)为

(10)

式中，l为机器人运动步长。

针对传统APF算法易陷入局部极小值问题，文中采用增设虚拟子目标的改进方法，通过虚拟外力引入，使陷入局部极小值点的机器人摆脱陷阱，抵达目标点。

首先以机器人移动的连续5个步长作为其是否陷入局部最小的判断依据，当连续步长各小于βl，β∈[2，4]时，通过调节β值，可较快的检测机器人是否陷入局部最小。当机器人判断出已经陷入局部最小时，存储相关障碍物信息，并将这些障碍物视为一个障碍物群体，然后以障碍物群与目标之间的连线为中心，以障碍物较多的一侧作为有效障碍物群，按式(11)计算虚拟子目标位置，即

(11)

式中，(x，y)和(xg，yg)为机器人当前位置和目标位置，(xb，yb)为有效障碍物群位置，β1>0和β2>0为调节系数。根据式(11)机器人跳出局部极小值益后，撤回虚拟子目标，机器在原合力作用下断续进行路径规划。

2.3 路径震荡点过滤

由于步长与障碍物作用距离的不匹配及解算过程的离散化，使得APF算法难以避免路径振荡点，即使使用虚拟子目标方法也只是减少震荡次数，而无法避免，为此，文中对震荡路径点进行过滤，以进一步平滑最优路径。

设k时刻路径点为qk，当与qk-2路径点之间的距离满足ρ(qk，qk-2)l时，记为震荡结束点qe=qk-1，由qb到qe组成震荡簇。

当qe与qb位于簇异侧时，有ρ(qe，qb)>l，此时，将直线L(qb，qe)等分后获得n+1个新路径点，即

(12)

式中，q1=qb，qn+1=qe，n=〖ρ(〗qe，qb)/l〗，〖·〗〗为取整数操作。

当qe与qb位于簇同侧时，根据震荡点形成原因，此时的震荡突变点位于障碍物一侧，当ρ(qe，qb)

S=(K-1)×l+∑md+∑ms

(13)

式中，K为未过滤总路径点数，md和ms的计算式为md=ρ(qe，qb)-n×l，ms=l-ρ(qe，qb)。

3 改进蚁群全局规划算法

3.1 经典蚁群算法

(14)

式中，Ak为蚂蚁的下一可选节点集，ηij为节点边权重的倒数，α和β为信息素与ηij关系的调节参数，q0∈(0，1)为给定的识别参数，q∈(0，1)为某随机变量，其服务均匀分布。

信息素的局部更新规则为

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

(15)

式中，ρ为挥发系数，Δτij(t)为蚂蚁经过边(i，j)后的信息素增加量，Δτij(t)=Q/Lk，Q为某给定值，Lk为当前迭代路径长路。

信息素全局更新规则用于对当次迭代所有蚂蚁完成路径搜索后的整体信息素优化更新，以增加优质解对下一路径迭代的贡献度，提高算法收敛速度，其计算式为

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

(16)

其中，当边(i，j)位于当次迭代的最优路径时，Δτij(t)=Q/Lbs，否则Δτij(t)=0。

可以看出，全局更新策略加强了节点的信息素浓度，有利于算法的快速收敛而局部更新策略则削弱浓度，以减少重复访问，增强算法的全局寻优性能。经典蚁群算法在迭代初期，受ηij(t)影响，易限入局部最优，而迭代后期，局部信息素更新增强全局搜索能力，但影响算法的收敛性，为此，对经典蚁群算法进行了改进，以适于机器人全局路径规划。

3.2 挥发因子ρ的自适应设置

挥发因子ρ直接影像不同路径的信息素浓度，进而影响最优路径的质量，较大的ρ值可提高信息素更新效率，从而较快的实现算法的收敛，找到最优解，但较快的迭代收敛会导致边间信息素浓度差异增大，而使算法陷入局部最优；另一方面，较小的ρ值可提高算法的全局搜索性能，但不明显的信息素更新效率，影响了算法的收敛速度，为此，文中提出挥发因子ρ的自适应设置算法。

自适应设置基于算法的迭代次数，当最优解在若干次迭代后，仍无明显改变时，ρ的取值计算式为

(17)

式中，ie与iemax分别为当前迭代次与最大迭代次数，λ为调节因子。根据式(17)，算法在初始迭代时，ρ值较朋以增加算法的收敛速度；而当算法趋于平衡，最优解变化较小时，ρ值将根据式(17)随迭代次数进行动态调整，以增加解空间范围，避免可能存在的局部最优解。

3.3 状态转移函数的改进

经典蚁群算法中对初始信息素浓度采用均匀分配的方式，导致初期搜索的盲目性和较慢的收敛速度，为此，文中首先以改进的APF确定一个较高的信息素浓度初值，然后以虚拟合力确定下一个路径点方向，从而提高规划方向的准确性。加入改进APR在状态转移函数为

(18)

3.3 信息素更新改进

信息素浓度在算法的不同迭瓦片阶段要求不同，经典蚁群算法采用固定的信息素浓度更新策略，影响路径规划的最优解。同时，经典算法中全局信息素更新需要完成当次迭代所有蚂蚁的路径规划后，结合最优解进行全局信息素优化调整，这将导致局部较优解的信息素浓度得到反而被加强，为此，在全局信息素更新策略中增加tanh函数为模型的动态因子σ，提出一种自适应信息素更新算法。

由神经网络模型的相关知识可知，其激励函数f(x)=(ex-e-x)/(ex+e-x)为输出为[-1，1]内的tanh连续函数，经过函数值调整后，可将函数输出取值调整为[0，1]，即

(19)

这样，当次迭代完成后，全局信息素更新规则修改为

τij(t+n)=τij(t)+μσΔτij(t)

(20)

从图2函数图像可以看出中，当局部权值和与其路径均值相差越小，调节因子越接近于1，反之则直接于零，说明路径中局部最优解较小时，该路径全局信息素优化时获得的浓度增加就越多。另外，当x∈[-2，2]时，σ具有对局部解的高敏感性，此时，各迭代次数下获得的最优路径的信息素更新效果会因较小的局部解而表现出较大的差异性，从而加快全局最优路径的筛选，当x>2时，σ的变化较为缓慢，且趋近于1，有利于消除局部最优解信息素浓度的过量增加对最终最优解的影响。

图2 调节因子σ的函数图像

根据上述对经典蚁群算法中挥发因子、转换概率函数和信息素更新策略的改进，文中改进蚁群算法进行全局路径规划计算流程如图3所示。

图3 改进蚁群算法全局路径规划流程

4 仿真验证

为验证文中基于改进人工势场和蚁群算法的联合最优路径规划算法的有效性，以不同复杂程度和障碍物环境作为仿真环境，采用Matlab R2016a开发实验算法，计算机环境为：Windows10，Intel® Xeon® W-10855M @ 2.80G Hz CPU，32G 内存，采用已有改进势场蚁群(简记为Imp-ACPF)算法[7]及零点优化的自适应势场蚁群算法(记为ZaA-ACPF算法)[14]作为实验比较算法，主要参数设置为蚁群数为30，最大迭代次数设置为70，信息素初始值为0.0003，α=2、β=6、ξ=0.2、ε=0.5。

4.1 路径规划结果比较

图4所示为实验所用三种算法的多次路径规划实验结果的平均值，图5为相应的的收敛曲线均值。

图4 简单实验环境实验结果

图5 各算法收束结果

由图4和图5实验结果可以看出，ZaA-ACPF算法的迭代搜索陷入局部最优，主要是其在中间区域第一次避障时，受启发信息误导，其规划路径选择了欧氏距离最小的右边节点，并在后续迭代收敛到该局部解；Imp-ACPF算法与文中算法对蚁群启发信息进行了改进化，引导蚂蚁以较优的初始路径进行迭代，从而有效提高算法的收敛速度和避免局部最优，但Imp-ACPF算法仅采用改进人工势场优化启发信息，其初始路径得到优化，但仍与最优路径存在一定的差别，从而其后续的收敛速度受到影响；文中算法在改进人工势场优化算法初始路径准确性基础上，通过挥发因子自适应设置和全局搜索方法的优化改进，进一步提高了算法对各种障碍物环境的适应性，有利于收敛速度的优化，因而在收敛速率和最优路径均取得较优的实验结果。

表1所示为3种算法的仿真结果，可以看出，文中算法取得最高的收敛速度，其运行时间为0.735 s。

表1 仿真结果

4.2 算法性能比较实验

由于Imp-ACPF算法与文中算法的最优路径搜索结果相近，为进一步分析文中算法的性能优势，将文中算法与Imp-ACPF算法分别应用于不同栅格尺寸的实验环境，分析两种算法的最优路径和收敛时间，其结果如表2所示，表中，实验环境随着栅格尺寸的增加，障碍物也变得更加复杂，且实验结果为多次实验结果的平均值。从表中实验结果可以看出，在环境栅格尺寸较小时，文中算法与Imp-ACPF算法的最优路径长度及算法的平均收敛时间相差不大，但随着栅格尺寸增加及环境复杂性增加，文中算法的最优路径及收敛时间优势逐渐突出，主要因为文中算法通过增加斥力距离值和增设虚拟子目标点优化人工势场的避障性能，通过振荡点消除平滑最优路径，通过挥发因子的自适应设置与全局搜索的改进，优化蚁群算法对不同复杂障碍环境的适应性。

表2 不同栅格尺寸实验结果

如图6所示为两种算法在全局蚁群搜索时的所有中间路径，从实验结果可以看出，两种算法的中间路径具有较好的全局覆盖性能，从而保证了搜索到全局最优路径的准确率，进一步分析根据式(21)两种算法的环境覆盖率φ量化指标，可得两种算法的φ值分别为70.95%和72.59%，说明文中算法具有更好的全局寻优性能。即

图6 两种算法的路径覆盖实验结果

(21)

式中，Npass为算法中间路径栅格数，Nfree为所有可行路径栅格数。

5 总结

针对经典势场与蚁群算法联合机器人路径规划算法，易陷入局部最优、路径震荡且对不同复杂障碍物环境适应性差等等问题，提出了基于改进的势场与蚁群算法的联合机器人路径规划算法。算法在地图环境栅格化基础上，首先利用斥力距离值引入和增设虚拟子目标点改进经典人工势场算法，以优化其目标不可达和局部欠优问题，其次，在改进势场优化蚁群初始路径筛选基础上，通过挥发因子的自适应设置与全局搜索策略的改进，提高蚁群算法对不同复杂障碍环境的适应性和全局最优路径的有效性。实验结果表明，所提算法能够有效避免经典算法的局部最优问题，路径较为平滑，对不同障碍物环境具有较好的适应性，全局搜索能力和收敛速度优于实验采用的已有算法，从而验证了该算法的有效性。