基于椭圆模型人工势场法的移动机器人路径规划研究

颜海彬，刘冉冉，臧传涛

（江苏理工学院 汽车与交通工程学院，江苏 常州 213001）

作为移动机器人（MR）研究的重要技术之一，路径规划在人工智能的各个方面均有所体现。路径规划是从起始位置到目标位置，寻找一条最合适快捷的路线[1]，其常用方法有遗传算法（GA）、快速搜索随机树算法（RRT）、人工势场法（APF）等。

RRT算法是以采样为基础的，在进行路径规划的时候需要对空间环境进行采样，通过搜索树向空白空间不断扩展，形成完整状态空间模型，以避免对状态空间的建模。由于该算法使用均匀的采样策略，因此，导致计算量大、算法运行较慢；且最邻近点的选择只考虑了离随机树中间节点的距离，因而在一定程度上影响了算法的搜索结果[2]。GA算法属于一种进化算法，它寻找最优解的方式类似于自然界物种的遗传与进化机理。GA算法具备较高的搜索效率，同时，易与其他算法相结合使用；但实现较为复杂，需要先对所求解的问题编码，解算出来后再对问题进行解码[3]。APF算法是一种根据梯度下降法求最优解的方法，其结构简单、程序易于实现，能够快速规划出一条安全的平滑路径；因此，广泛应用于规避障碍物控制和平滑轨迹方面[4]。APF算法将环境函数分成引力场和斥力场，机器人在两种不同势场共同作用下从高势场点位置运动到终点位置来计算路线。但是，在复杂环境中，容易出现斥力、引力平衡和在目标点附近斥力远大于引力的情况，造成局部极小值和目标点不可达的难题。为此，Saeid等人[5]针对障碍物周围终点不能到达的问题，提出了沿墙跟踪的方法。Lee等人[6]针对路径规划的局部平衡问题，采用设置虚拟障碍物的方法来跳出局部平衡，此方法在规划前考虑到机器人的自身尺寸，在MR协力最大点设置一个虚拟障碍物，从而改变当下机器人所处的势场，进而改变MR下一步的移动方向；然而，这种逃逸局部平衡问题的方法，需要根据不同的MR形态建立不同的模型，移植性低。2020年，刘玉等人[7]提出具有随机可达集的人工势场算法，从而提高了在动态环境中路径规划的成功率，由于该方法是在采样基础上进行的，因此规划出的路线平滑度较低。魏智红[8]在研究多机器人的编队问题时，就APF算法规划路径出现局部平衡的难题，提出了全局势力最小点的范围，在该范围中，以MR位置与终点位置连线的正交线方向作为MR下一步的移动方向，从而绕过局部平衡点的位置，解决陷入局部平衡的问题；但是，该方法在面对两边对称的通道时，无法从中间通过，因此，跳出局部平衡的路线并非最优。

本文在传统APF算法的基础上，采用修改斥力函数和建立椭圆模型设置虚拟目标点的方法，以解决势场法在规划路径过程中可能遇到的无法到达目标点和陷入局部平衡的问题。该算法通过增加终点位置到障碍物位置的距离作为修改斥力势场函数的因子，从而解决MR运动到障碍物附近时，因所受引力小于斥力而造成的无法向终点位置靠近的问题；通过构建椭圆模型设置虚拟目标点，改变原有的势场分布，从而改变MR的受力情况，使MR离开局部最小点的位置；最后，对算法进行仿真验证，得到一条从起始点到终点位置的安全、有效路线。

1 传统人工势场法

20世纪80年代后期，Khatib根据物理学中的思想提出了APF算法[9]。该方法最初用于机械臂抓取物体时防止与其他物体存在干涉。假设机械臂的工作环境是一个虚拟力场，需要抓取的物体周围存在虚拟的引力，则其他物体周围存在虚拟的斥力场，机械臂在引力和斥力的共同作用下产生运动。APF就是利用物理中的力学理论来形容人类思维的方式[10]。随后，研究者们发现，该方法在移动机器人的路径规划中有不错的效果，使得到的运动曲线相对平滑了许多。

MR在有障碍物的环境中进行路径规划时，假设在各个障碍物四周都存在一个一定范围的排斥力场，在终点位置四周存在一个吸引力场，机器人沿着势场函数下降的方向寻找终点，完成路径规划。如图1所示，为MR在环境中的受力分布。

图1 MR在环境中的受力分布

斥力是由障碍物指向MR方向的力，从MR指向终点位置的力是引力方向，根据力学理论，合并两个力即得到机器人的下一步移动方向。为得到排斥力和吸引力，需要先设置引力势场和斥力势场函数，以距离作为力场函数的因变量。设置：MR的位置X=(x,y)；引力势场函数Uatt(X)；斥力势场函数Urep(X)；两者的合力势场函数Ftotal(X)。

引力场函数表示为：

式中：Xg表示目标点的位置(xg,yg)；λ1表示引力常数；ρ(X,Xg)是MR当前位置和终点位置的几何距离。

对引力势力函数中的距离求一阶导数所得到的即为引力：

同理，斥力势函数为：

斥力函数对距离求一阶导数即为斥力：

所以，MR在空间中所受到的合力Ftotal(X)为：

就环境中的障碍点而言，这些障碍物对机器人形成了排斥力场。当机器人往障碍物方向移动时，MR所受到的斥力会慢慢变大；同样，当MR向远离障碍物方向移动时，其所受到的斥力会逐渐减小；而当MR驶离障碍物的影响范围后，其所受到的斥力不存在。

2 改进人工势场法

2.1 无法到达终点的难题及解决方案

在庞杂环境中，MR、障碍物和终点的特殊位置会导致规划路径失败。例如：在一个狭窄的过道里，MR会来回抖动陷入势场局部平衡的状况；当障碍物到终点的距离小于障碍物的影响范围时，MR将难以找到终点位置；当障碍物处于终点位置附近，MR尚未进入障碍物的影响范围时，若MR继续向障碍物位置前进，障碍物将产生对机器人的斥力，而随着MR不断接近，此时势场中产生的斥力远大于引力，MR向远离目标点的方向运动，之后继续受到引力影响向目标点位置靠近，如此反复，MR将无法准确地到达目标点位置。

通过传统APF算法的斥力和引力函数可知，引力随机器人与终点坐标距离的增大而增大，斥力随机器人到障碍物间距的增大而减小[11]。如图2所示，当终点位置即目标点附近存在障碍物时，机器人所受到的斥力大于引力，致使MR无法成功抵达目标点的位置，在目标点周围抖动。

目标点位置无法抵达的问题是由于MR在目标点周围的障碍物所产生的斥力大于目标点的引力；因此，在传统的斥力函数基础上，引入当前点到目标点之间的距离ρ( )X,Xg，根据不同的情形降低斥力值的大小。

2.2 局部最小值问题及解决方法

在较为复杂的环境中，有可能出现MR在未抵达终点位置时，其所受到的引力和斥力大小相等、方向相反、合力为0的情况，这将导致MR在目前位置的来回振荡[12]。常见的局部最小情况如图3所示。

图3 MR在局部平衡问题下的分布

近年来，研究人员提出了多种办法解决局部平衡的问题。如图4所示，裴以建等人[13]先确定造成局部最小点的障碍物位置信息，判断机器人与终点位置构成直线左右两边障碍物的数目，在较少障碍物的一侧，算出每个障碍物与平衡点的连线与地图坐标系X轴所构成的夹角θi以及终点位置与该平衡点的连线与地图坐标系X轴正方向的夹角θ，通过对比大小，拟定虚拟目标点的大体位置。由于该方法计算量过于庞大，导致MR跳出局部最小区域的时间过大，并且生成的路径并不一定是最优的。邓永娣等人[14]采用一种简便的局部极小值的跳出方案，设定MR陷入局部最小区域时，将沿着机器人到目标的正交方向移动，实际上，相当于在正交方向上设置了一个固定的虚拟目标点。该方法虽然可以跳出局部最小区域，但是，在面对狭长的通道时，MR做了无用的避障且路线不一定是最佳的。理论上，增加一个适当的虚拟势场可以有效解决局部平衡的难题。鉴于以上方法存在计算量大、路径不是最优等问题，本文提出建立椭圆模型来设置虚拟目标点的方法。

图4 局部平衡比较夹角法

如图5所示，针对障碍物对称分布在MR与终点位置连线两侧的情况，用椭圆模型来确定虚拟目标点的最佳位置。虚拟目标点产生的引力将改变机器人在局部最小值的状态，通过在椭圆模型上不断修正虚拟目标点的位置，从而使MR跳出局部平衡区域。

图5 椭圆模型建立虚拟目标点

根据人工势场法原理，MR距离终点位置越远，产生的引力就越大；因此，在面对上述情况时，设置的虚拟目标点给机器人带来的引力要大于实际目标所施加的引力，并且方向保持不变。MR在障碍物和虚拟目标点的势场下，斥力大小和方向不变，引力增大，原来的平衡力被打破，此时机器人向虚拟的终点移动。

在图5坐标系中，假设机器人陷入局部平衡的坐标为Pmin(xmin,ymin)，终点位置坐标为Pgoal(xgoal,ygoal)，则这两点的中点坐标位置Pb为：

以Pmin和Pgoal两点的连线作为新轴X，，以Pb为原点，建立过原点垂直于X，的轴Y，，新的坐标系是由原坐标系经过旋转平移得到的，则：

据此，椭圆模型进一步确定虚拟目标点的可行位置，以椭圆与X，轴的正交点为初始的虚拟目标点，机器人按此虚拟目标点行走；若检测到再次陷入局部平衡时，则构建新的椭圆模型，寻找新的虚拟目标点。对规划后的路径再进行二次优化，从起点开始依次检测路径节点，判断是否能够直线到达。若能直线到达，则删除起点到该节点的路径；若不能直线到达，则将该节点位置当作起点位置继续做能否直线到达的判断，从而简化路径。

如图6所示，为改进势场法（APF-N）流程。

图6 路径规划APF-N算法流程图

3 仿真结果及分析

如图7所示，将传统APF算法与改进后的方法进行仿真对比分析，构建12×12的环境地图来验证改进算法在处理目标点不可达问题中的可行性。环境参数如表1所示。通过仿真对比分析可以看到：改进后的人工势场法和传统势场法规划出来的路线略有不同，在目标点附近，传统人工势场法的红色路线并没有准确到达终点位置，而改进后的势场法蓝色路线成功到达了终点位置。

表1 处理目标点不可达问题的环境参数

图7 人工势场法改进前后的对比

如表2所示，为路径规划代价值。虽然，改进后的人工势场法很好地解决了无法到达终点的难题，但是从仿真的时间和迭代次数来看，改进后的人工势场法在速度和节点的搜索次数上都是有明显劣势的。如图8改进势场法合力图中显示，合力在起点的时候处于最大值，原因在于目标点距离起点很远，引力远远大于斥力，而起始点到最近障碍物的距离大于一个单位，斥力较小。此时，根据梯度下降法寻找合力函数的局部最小值，搜索到目标点后停止迭代搜索，在目标点处合力达到局部最小值，完成路径规划。

表2 路径规划代价值

图8 改进势场法合力

针对局部最小值的情况，传统人工势场法会造成陷入一点无法移动，目前常用的方法是设置中间虚拟目标点来跳出局部最小值。本文通过局部最小值点和目标点构建椭圆模型，设置虚拟目标点来解决全局最小值的问题，再对规划后的路线进行优化，简化路线，去掉不必要的位置信息。环境参数如表3所示。

表3 处理局部最小问题的环境参数

如图9所示，为采用传统人工势场法在该地图环境中规划路径时的效果。可以看出，该方法在规划的初始阶段便陷入了局部平衡的状态，无法继续规划路径。文献[13]中采取夹角比较的方法，如图10所示，为对该方法进行仿真得到的规划路线。比较图9和图10可以看出，后者成功解决了局部最小值问题。如表4所示，为夹角设置法与APF-N法的参数对比。

表4 夹角设置法与APF-N法的参数对比

图9 APF算法在庞杂环境下搜索路径

图10 夹角比较路径规划

如图11所示，为采用椭圆模型设置虚拟目标点的方法对该环境进行规划仿真，并对规划出的路线进行优化。绿色点处是APF-N方法在规划路径的过程中出现局部平衡的位置，蓝色线是该方法规划出的路线。可以看出，规划出的路径并不是最优的，其多次出现棱角。通过路径优化方法，删除不必要的节点，简化路径，可以得到一条从起始点到目标点的简化路线。优化路线参数如表5所示。

表5 优化路线参数

图11 椭圆模型势场法路径规划及曲线优化

仿真实验数据显示，采用APF-N法规划路径的时间明显较短，且规划出的路径距离基本一致。优化路线的算法虽然由于在APF-N算法执行的过程中加入了优化程序，使规划时间多出了0.116 0 s；但是，从规划出的路径来看，距离相对于初始APF-N算法节省了11.19 m，大大减少了路径规划的长度。

4 结论

针对在移动机器人路径规划中，传统人工势场法存在终点位置无法准确到达和容易陷入局部平衡的问题，本文采用完善斥力函数和建立椭圆模型确定虚拟目标点的方法加以解决。（1）根据移动机器人位置与障碍物之间的距离，在0到障碍物影响范围上限值的一半、障碍物影响范围的一半到上限值、超出上限值三种情况，增设当前点到目标点的距离因子，构建斥力势场函数，从而保证MR能够安全到达终点位置。（2）通过构建椭圆模型确定虚拟目标点的位置，增大目标点的引力，打破平衡，从而克服局部平衡问题。

仿真分析显示，上述改进算法成功地解决了无法到达终点和局部平衡的问题，并且该方法在路径规划用时上，比夹角设置法节约了近5倍时间，大大降低了计算成本；同时，优化路线在保障安全的前提下缩短了约11 m。改进算法不仅可以应用到扫地机器人、机械臂等复杂环境下的路径规划问题，而且还可以拓展到智能车路径规划的参考算法。然而，该方法也存在一定不足，如：模型仅考虑单个质点机器人的路径规划，忽略了机器人的自身尺寸对整个环境的影响；仅考虑静态环境中的路径规划，而忽略了在动态环境中的相关因素。在实际的路径规划中，许多动态不确定因素都是潜在的，从而影响到规划结果的准确性，在以后的研究中，应对此加以关注。