势场改进蚁群算法优化机器人路径规划

刘师良，杜改丽，黄武峰

（1.河南医学高等专科学校，河南 郑州 451191；2.广西科技大学自动化学院，广西 柳州 545616）

1 引言

路径规划能够根据时间、能耗等相关要求，在障碍环境中为移动机器人规划一条符合要求的最优路径，已成为机器人控制领域的研究热点［1］，目前，根据环境中障碍物的已知情况，已有路径规划算法通常分为局部规划和全局规划，并取得显著成果，如遗传算法及其改进、启发搜索算法［2］、粒子群算法［3］、改进蚁群算法［4］及各种人工势场优化算法［5］等。

蚁群算法是一种通过模拟蚂蚁觅食过程构建的全局搜索算法，具有较好的鲁棒性和环境表达优势，作为一种群体智能算法，蚁群算法以其较强的全局搜索性能适用于存在障碍物环境下的机器人最优路径规划［4］，但经典算法效率低且易陷入“早熟”和局部最优，为此，文献［5］以粒子群算法优化蚁群参数，并能过栅格地图改进蚁群算法对U型陷阱的适应性，但算法迭代收敛时间较少；文献［6］对蚁群算法的相关参数进行自适应优化，以实现算法初期的快速收敛和后期的稳定局部搜索能力，但仍未解决局部最优局限；文献［7］基于双向A*启发改进经典蚁群算法，有效提高算法的收敛速度和全局最优能力，但其局部搜索能力需要进一步提高。

人工势场在移动机器人路径规划中具有较为成熟的应用，其计算量较小且结构简单，可以实现路径的快速计算，但在障碍物环境容易限入局部震荡，为此，文献［8］将人工势场作用力引入到蚁群算法的状态转移函数中，以优化算法的初始值设置，实验结果验证了改进算法在迭代耗时、收敛速度和规划精度上的有效性；文献［9］采用快速函数改进人工势场，并通过虚拟引力斥力全力优化蚁群的搜索启发信息，以提高算法的全局搜索能力，从而避免经典算法中启发信息引起的局部最优；文献［10］以势场力改进蚁群启发信息，避免局部最优和障碍物停滞，构建局部扩散信息素，改进蚁群算法对具有高适应值的目标空间的搜索能力。

在已有研究基础上，提出了基于改进人工势场优化蚁群算法的障碍物环境机器人路径规划算法，算法通过斥力改进和虚拟力点设置改进人工势场算法的U 形障碍物避免能力，并通过改进势场优化蚁群算法的启发函数、信息素更新和状态转移函数，以调节信息素的自适应更新，从而平衡算法的收敛速度与全局搜索能力。

2 虚拟引力优化人工势场

人工势场（APF）以引力场和斥力场组成的虚拟势“场”的形式模拟障碍环境，移动机器人根据目标点生成的引力场逐渐移向目标，同时根据障碍物生成的斥力场避开障碍物，从而获得到达既定目标的最优路径。

但传统人工势场算法通常存在较多局限，（1）当障碍中的目标点与障碍物在互相影响范围之内时，引力与斥力作用会使用机器人在目标点附近徘徊而无法抵达目标点；（2）在目标点引力作用方向上同时存在相反方向的障碍物斥力，易造成引力与斥力相互抵消而停止前移，为此，需要对传统人工势场算法进行改进。

针对目标不可达问题，由机器人当前位置X和目标位置Xa可得两者之间的欧氏距离da，将其引入到斥力函数中得：

式中：db—机器人与障碍物之间距离；dm—障碍物影响半径；d0—障碍物安全距离，式（1）在db≤dm条件下，当db＞dm时，取值Ur=0；t—da对斥力的影响系数。

当机器人靠近目标时，此时，为减少障碍物斥力影响，将式（1）进一步分解为障碍物指向机器人及机器人指向目标，两个斥力分量Fr1和Fr2，其计算式为：

当在障碍物附近时，Fr1使机器人远离障碍物，而Fr2使机器人同时向目标方向运动，当目标点在某障碍物影响半径内造成移动机器人震荡时，根据式（3），目标在移动向目标点时，da逐渐减少，则障碍物斥力被强制减少，而机器人与目标之间的引力逐渐增大，从而避免出现在目标点附近震荡。

2.1 有效障碍物识别

当初始规划路径即机器人与目标点之间的连线上存在障碍物时，该障碍物即为影响路径规划的有效障碍，在路径优化时，需要对其进行避碰处理，以第一个有效障碍物中心点作为临时目标点，当障碍物为U形区域时，机器人易陷入局部极小值而无法跳出障碍物区域，如图1所示。障碍物影响半径设置为r，其中，心坐标为(a1，a2)，机器人中心坐标为(x0，y0)，其与障碍物影响圆之间的切点坐标为(x1，y1)，(x，y)为虚拟牵引力点，其位于切线延长线且与切点之间的距离为d，虚拟牵引力点用于在机器人遇到U形障碍物时，将机器人向自身位置索引，当机器人到达(x，y)位置后，虚拟力点及其牵引力自动取消，机器人引力受力情况变换为原有引力。

图1 U形障碍物内受力分析Fig.1 Analysis of Internal Forces in U-shaped Obstacles

根据图1所示三角关系，切点坐标(x1，y1)可以表示为：

由切点坐标(x1，y1)和机器人当前位置(x0，y0)可建立求解虚拟牵引力点位置坐标(x，y)的方程为：

式中，相关变量值，如图1所示。根据式（5）可以计算虚拟牵引力点坐标(x，y)的值。在虚拟引力值作用下，机器人可以加速向虚拟点移动并跳出U形障碍物范围，为快速增加虚拟力值以提高跳出障碍物作用范围的效率，改进虚拟引力值为：

式中：c、d—虚拟力点坐标值与机器人当前坐标，由式（5）计算，a1＞1—指数函数系数；f(t)—开关函数，当∇l≤S时，f(t)=1，反之，f(t)=0，∇l—机器人受牵引力作用下的移动速度，S—预测阈值。

改进算法通过中间目标点优化各局部路径的规划，由于经过有效障碍物搜索，中间目标点内无新障碍物和中间点存在，因而有效避免经典算法的死锁现象，同时，由于不考虑接近时斥力，机器人可紧贴近障碍物移动，使得局部路径更优。

3 改进蚁群全局规划算法

3.1 自适应启发信息的改进

传统算法的路径搜索通常需要对节点进行遍历，而在算法初期，信息素在各节点的浓度较为均匀，原始启发函数无法引导蚁群进入下一个节点。通常在路径规划时，以当前节点到终点的直线作为最短的路径，因此可以将改进人工势场法引入到算法的启发函数中，改进后的启发函数为：

式中：ξ∈(0，1]—诱导因子，用以削弱启发函数在算法的迭代后期所民挥的作用。

当机器人所处的障碍环境规模较大时，改进后的式（10）的值在不同栅格下的差值较小，因而仍存在较大的随机初始路径选择，另一方面，在目标点附近，式（10）的值在不同栅格下的差值又较大，使得机器人在该区域内的路径选择较为单一，为此，引入改进人工势场计算的当前位置与目标位置的距离值，设计参数自适应启发函数，即：

可以看出，改进后的启发函数，不会随着机器人的位置变化而出现较大的变化值，从而避免算法迭代前期的选择随机性和后期选择的单一性。

3.2 信息素更新方法的改进

传统算法的最小蚂蚁信息素更新策略会产生误导，为平衡在收敛与搜索上的性能优势，这里采用自适应部分信息素更新策略，即在一次迭代完成后，对路径进行排序，仅对排序靠前的路径对应的蚂蚁进行信息系自适应更新，设这些蚂蚁的信息素变化量为，则有：

式中：lgbest—全局最优值；lbest、lworst—当前迭代搜索到的最优与最差值；ε=k/Kmax—进化率；k、Kmax—当前迭代值与最大迭代次数。为增加算法后期搜索能力，需要对信息素更新策略进行扰动，当连续多次未产生新路径时，对各路径对应的信息素增加挥发系数，即：

3.3 改进转移函数

经典蚁群算法的初始信息素浓度可能会较低，从而导致初始迭代收敛速度较慢，从而影响整个算法的收敛速度，为此，将改进的人工势场虚拟合力引入到算法的状态转移函数中，以提高路径规划初期的信息素浓度。虚拟合力主要用于判断蚁群最优路径的方向，引导蚁群算法的初始阶段快速收敛，为避免其对后期算法的影响，还需要对其进行约束，加入势场合力的状态转移函数修正为：

式中：ηij，d—两节点之间的距离，γ—势场启发因子；ε—以目标点为参考的引力系数；k、kmax—当前迭代次数及最大迭代次数；f—势场的虚拟合力；α＞1—某调节函数；θ—单虚拟力值与合力之间的夹角，θ值越小相对较大，从而使得蚁群向夹角小的路径偏移。

4 仿真实验验证及分析

为验证文中所提算法的最优路径规划有效性，构建图2所示的（20×20）的复杂栅格障碍环境作为机器人路径规划实验仿真环境，采用已有文献中的势场改进自适应蚁群算法［10］作为实验比较算法。针对环境中的U形障碍物，两种算法的实验仿真结果，如图2所示。可以看出，势场改进自适应蚁群算法虽然也采用人工势场对蚁群算法进行改进，但没有针对U 形障碍物进行跳出操作，因而路径规划进，机器人在U形障碍物内多次徘徊，而文中算法通过虚拟牵引力点的设置，较好的避免移动机器人在U形障碍物内的徘徊，从而取得最优的路径规划结果。

图2 对U形障碍物处理实验结果Fig.2 Experimental Results on the Treatment of U-Shaped Obstacles

两种算法的最优路径规划实验结果，如图3 所示。可以看出，复杂格栅环境中，势场改进自适应蚁群算法的最优路径仍陷入局部最优，而文中算法较好的避免了局部最优并取得全局最优路径，且文中算法通过构建迭代相关的信息素负反馈通道，有效缓解迭代波动，从而提高收敛速度。

图3 简单实验环境实验结果Fig.3 Experimental Results in Complex Simple Experimental Environment

5 总结

针对传统蚁群算法易陷入局部最优、收敛较慢等问题，提出了基于改进人工势场优化蚁群算法的障碍物环境机器人路径规划算法，算法通过斥力改进和虚拟力点设置改进人工势场算法的U 形障碍物避免能力，并通过改进势场优化蚁群算法的启发函数、信息素更新和状态转移函数，以调节信息素的自适应更新，从而平衡算法的收敛速度与全局搜索能力。仿真实验结果表明，所提算法具有较好的全局搜索能力和对U形障碍物的规避能力，收敛速度和搜索能力优于实验采用的已有改进蚁群算法。