改进人工势场法的移动机器人局部路径规划

王迪，李彩虹，郭娜，高腾腾，刘国名

(山东理工大学 计算机科学与技术学院,山东 淄博 255049)

路径规划是移动机器人领域的重要组成部分，主要分为全局路径规划和局部路径规划。全局路径规划是机器人在环境信息已知的情况下进行路径规划，可以找到最优解，但一般是离线规划，不能实时执行；局部路径规划是机器人在环境信息未知或部分可知的情况下，在移动过程中利用传感器、红外线等检测环境信息进行的实时路径规划。由于缺乏全局环境信息，传感器的检测范围也有限，因此规划的路径可能不是最优的，甚至找不到可行路径。在大场景的运行区域里，通常是将全局路径规划和局部路径规划结合起来使用。常用的路径规划算法有蚁群算法[1]、神经网络[2]、遗传算法[3]、人工势场法、A*算法[4]、模糊控制[5]等等，其中人工势场法具有计算量小、结构简单、路径平滑的特点，得到了广泛应用。但人工势场法存在局部极小点的缺陷，即移动机器人在障碍物前因受力平衡而静止不动或在某一范围内震荡，从而无法到达目标点[6]。为了解决这一问题，国内外学者提出了很多解决方法。Chen等[7]加入混沌优化算法，将势场函数作为混沌优化的目标函数，通过混沌搜索实现了机器人相应的运动步长和运动方向；魏先勇等[8]构造了新斥力势场函数消除局部极小点，并用量子遗传算法对最优或次优个体进行选择，进行路径优化；Abdalla等[9]将人工势场法与模糊控制相结合，利用粒子群算法对模糊逻辑控制器的隶属度函数进行了优化，并将其用于移动机器人的运动控制，克服了局部极小点问题；Zhang等[10]将人工势场法与滚动窗法相结合，解决局部极小点问题；温素芳等[11]提出障碍物影响范围分层的思想；He等[12]提出动态椭圆影响区域，建立了危险区域模型；贾丙佳等[13]将邻近障碍物整体化，避免机器人进入局部极小点区域[13]；张鹏彬等[14]在障碍物一侧设置中间目标点；徐飞[15]在改进的人工势场法中采用扇区划分建立虚拟目标点的方法；纪迪[16]采用多方向沿墙走的方法，从五个方向中选出合适的方向跳出局部极小点陷阱；Lee等[17]在无障碍物的环境中设置虚拟目标点来克服局部极小点和路径无效率问题；韩知玖等[18]通过添加虚拟力解决局部极小点问题。这些方法能够解决某种程度上的局部极小点问题，但大多只适用于简单环境下。

本文针对局部极小点陷阱导致机器人无法到达目标点的问题，提出了基于虚拟目标点和环境判断参数的改进人工势场法。在该方法中，加入近似封闭障碍物环境的判断，在机器人即将逃出局部极小点而陷入死循环时设置虚拟目标点，引导机器人逃出近似封闭的障碍物环境，避免机器人陷入陷阱区域，顺利到达目标点。

1 人工势场法

基于人工势场的移动机器人路径规划算法是Khatib提出的[19]。基本思想是在机器人工作的环境中建立一个人工势场，目标点对机器人产生引力，障碍物对机器人产生斥力，由引力和斥力叠加起来的合力对机器人产生引导作用，使机器人到达目标点。为了解决路径规划过程中的目标不可达问题，本文采取添加目标点与机器人距离的改进斥力势场[20]，使目标点处的势场为全局最小点。人工势场定义为

U=Uatt+Urep，

(1)

式中：U为势场和；Uatt为目标点对机器人产生的引力场；Urep为障碍物对机器人产生的斥力场。定义目标点对机器人的引力和障碍物对机器人的斥力分别对应引力场和斥力场的负梯度，根据偏导得出人工势场对机器人的作用力F为

F=Fatt+Frep，

(2)

式中：F为合力；Fatt为目标点对机器人产生的引力；Frep为障碍物对机器人产生的斥力。

引力势场函数定义为

(3)

式中：Xg=(xg,yg)为目标点的坐标;X=(x,y)为机器人的坐标；Uatt为目标点对机器人产生的引力场；k为引力增益系数，‖X-Xg‖为机器人到目标点的欧几里得距离。目标点对机器人的引力为引力势场函数的负梯度：

Fatt=-k‖X-Xg‖。

(4)

斥力势场函数定义为

(5)

式中：m为斥力增益系数；d为机器人与障碍物的距离；d0为障碍物影响距离；da为机器人与目标点之间的距离。障碍物对机器人的斥力为

(6)

(7)

(8)

式中：分量Frep1由障碍物指向机器人；分量Frep2由机器人指向目标点。添加目标点与机器人距离，从力的角度上，增强了引力，避免目标点附近有障碍物时，斥力过大，机器人无法到达目标点的情况。人工势场法受力分析如图1所示。

图1 人工势场法受力分析Fig.1 Force diagram of the artificial potential method

引力势场和斥力势场构成的人工势场等势图如图2所示。在势场的作用下，机器人沿着梯度下降的方向移动。目标点处的势场为0，是全局最小点。

图2 人工势场法势场图Fig.2 The potential field diagram of the artificial potential field method

2 改进策略

2.1 虚拟目标点法

利用人工势场法进行路径规划，当机器人所受的引力和斥力和为0时，存在局部极小点问题，导致机器人在某一区域内震荡或静止不动，陷于陷阱区域，无法到达目标点。本文通过设置虚拟目标点和环境判断参数来解决这个问题。

当机器人在移动过程中进入陷阱区域，采取设置虚拟目标点的策略，即在机器人所受斥力分量Frep1左转90°的方向上的合适位置，设置虚拟目标点。忽略目标点产生的引力和障碍物产生的斥力，在虚拟目标点的引导下，使机器人向前移动一步，移动后撤销虚拟目标点，计算当前步骤下的合力及下一步坐标。重复以上步骤，直到机器人逃出局部极小点区域。

采用虚拟目标点法逃出局部极小点的示意图如图3所示。图3中箭头表示机器人下一步的移动方向。当前机器人所处位置为点A，因为引力与斥力的合力两者方向相反导致震荡，陷入局部极小点。机器人在所受斥力分量Frep1左转90°方向上的点B处，设置虚拟目标点，经虚拟目标点牵引到达点B。在点B处，机器人在合力的作用下，将往点A方向移动。经判定，机器人陷入了局部极小点陷阱，在点A和点B之间发生震荡。根据改进措施，在点B处机器人所受斥力分量Frep1左转90°方向上的点C处，设置虚拟目标点。经虚拟目标点的引导，机器人到达C处。重复此步骤，直到机器人逃出局部极小点区域，最终到达目标点。

图3 虚拟目标点法示意图Fig.3 Schematic diagram of the virtual target method

在斥力分量Frep1左转90°的方向上设置虚拟目标点，是本文解决局部极小点问题、逃离陷阱区域的中心思想。这种方法可以解决机器人在一字型障碍物、U型障碍物环境下进行路径规划时陷入的局部极小点情况，但是在近似封闭的障碍物环境下，机器人仍然无法逃出局部极小点区域。

2.2 近似封闭环境的判断

在近似封闭的障碍物环境下，在设置虚拟目标的基础上，加入环境判断参数：避障阈值、虚拟目标标志位和距离阈值。判断参数见表1。假设机器人移动了j步，此时的位置坐标为(xj,yj)，则机器人移动了j-2步和j-1步的位置坐标分别为(xj-2,yj-2)、(xj-1,yj-1)。

当机器人陷入局部极小点区域时，启用局部极小点策略，即设置虚拟目标点。对连续采用虚拟目标点法的次数进行统计，并且记录机器人当前所在位置的前两步路径规划设置虚拟目标点的情况。判断机器人是否进入近似封闭的障碍物环境的步骤如下：

1)判断连续设置虚拟目标点避障的次数是否超过避障阈值Nmin，否则转到第4步；

表1 近似封闭环境的判断参数Tab.1 The judgment parameter of approximately closed environment

2)判断机器人是否在上一步移动时设置了虚拟目标点，而下一步移动时没用，若不符合此情况，转到第4步；

3)判断机器人与障碍物的距离是否小于dmin。若小于则在上一步设置虚拟目标点的方向上的合适位置设置虚拟目标点，机器人只受虚拟目标点的影响；

4)根据实际运行情况更新Fl、Fp、Fn的状态；

5)根据合力计算机器人的下一步移动位置；

6)如果设置了虚拟目标点，则撤销虚拟目标点；

7)重复以上步骤。

如果满足前3个步骤的条件，则判定机器人陷入近似封闭的障碍物环境中。此外，设置避障阈值是为了区分是否是简单的局部极小点情况；设置虚拟目标点的状态是检测移动机器人是否即将退出局部极小点策略；设置机器人与障碍物的距离阈值dmin是判断机器人在退出局部极小点策略时是否避开障碍物，同时为了逃出近似封闭的障碍物环境时，及时调整策略，避免机器人绕行。机器人在近似封闭的障碍物环境下逃出局部极小点区域的示意图如图4所示。

图4 近似封闭环境下的机器人逃出局部极小点区域示意图Fig.4 Schematic diagram of a robot escaping from a local minima in an approximately enclosed environment

采用虚拟目标点和环境判断参数，对人工势场法进行改进，使机器人进行路径规划时能够逃出大部分的陷阱区域。算法流程如图5所示。

图5 改进人工势场法流程Fig.5 The flow chart of the improved artificial potential field method

3 仿真与分析

基于MATLABR2016a平台，在能够发生局部极小点陷阱区域的障碍物环境下，利用改进的人工势场法对移动机器人局部路径规划进行了仿真。每种环境都加入了虚拟目标点，并分别利用环境判断参数进行运行情况的对比。仿真图中等势线由目标点产生的引力场与障碍物产生的斥力场叠加构成，红色标志为遇到局部极小点情况设置的虚拟目标点，紫色标志为近似封闭的障碍物环境下设置的虚拟目标点。

1)一字型障碍物环境下的路径规划仿真

机器人在一字型障碍物环境下的局部路径规划仿真如图6所示。由图6可以看出，无论是否加入近似封闭的障碍物环境判断，机器人都可以逃离陷阱区域，解决局部极小值问题。在图6(b)中加入环境判断参数，并没有检测到近似封闭的障碍物环境，因此规划路径与图6(a)基本类似。

(a)未加入环境判断 (b) 加入环境判断图6 一字型障碍物环境下的路径规划Fig.6 Path planning in linear obstacle environment

2)U型障碍物环境下的路径规划仿真

机器人在U型障碍物环境下的局部路径规划仿真如图7所示。由图7可以看出，未加入环境判断和加入环境判断的改进的人工势场法，在虚拟目标点的牵引下都可以逃离陷阱区域。尽管图7(b)加入环境判断后会把环境误判断为近似封闭的环境，但是路径规划效果与图7(a)没有明显差别。

(a)未加入环境判断 (b) 加入环境判断图7 U型障碍物环境下的路径规划Fig.7 Path planning in the U-shaped obstacle environment

3)近似封闭的障碍物环境下的路径规划仿真

机器人在近似封闭的障碍物环境下的局部路径规划仿真如图8和图9所示。在图8(a)中，仅仅采用虚拟目标点法，未加入环境参数判断，机器人无法在近似封闭的障碍物环境下逃出局部极小点；而在图8(b)中，加入近似封闭障碍物环境判断以后，机器人可以顺利到达目标点。图8(a)中，机器人在M处的合力基本指向目标点，在位置变化上不确认为局部极小点，退出局部极小点策略。在合力的作用下，机器人移动至点N处，在引力与斥力合力的引导下移动至点L处。经判断，机器人在点L处陷入局部极小点陷阱，启用了虚拟目标点法，在障碍物环境内部按此路线绕圈，无法到达目标点。而采用了加入近似封闭的障碍物环境判断的虚拟目标点法，在点M处判定机器人在合力的引导下退出局部极小点策略，但是经过判断，点M处属于近似封闭的障碍物环境，故在未退出局部极小点策略时在设置虚拟目标点的方向继续设置虚拟目标点，从而在虚拟目标点的引领下逃出局部极小点区域，顺利到达目标点，路径规划效果如图8(b)所示。图9展示了另一种近似封闭的障碍物环境下的运行情况，利用改进的人工势场法进行局部路径规划，可以得出与图8中相同的结论。

(a)未加入环境判断 (b) 加入环境判断图8 近似封闭环境下的路径规划Fig.8 Path planning in approximately closed environment

(a)未加入环境判断 (b) 加入环境判断图9 5字型障碍物环境下的路径规划Fig.9 Path planning in the environment of 5-shaped obstacles

4)混合障碍物环境下的路径规划仿真

机器人在两种混合障碍物环境下的路径规划仿真如图10所示。混合障碍物的运行环境包括离散的障碍物、近似封闭的障碍物、一字型障碍物，在运行环境里，改进的人工势场法同时运用了虚拟目标点法和近似封闭环境判断。从图10可以看出，尽管加入环境判断后，机器人有时不能准确地判断环境，但是仍然可以在多种形状的障碍物构成的复杂环境下成功到达目标点，而且路径比较平滑。

(a)环境1 (b) 环境2图10 混合障碍物环境下的路径规划Fig.10 Path planning in mixed obstacle environment

4 结束语

1)基于虚拟目标点的改进人工势场法的移动机器人局部路径规划，可以判断移动机器人是否进入近似封闭的复杂障碍物环境中。

2)本文算法设置的虚拟目标点给予了机器人逃离局部极小点时的方向引导，解决了部分因障碍物环境复杂而陷入局部极小点、无法到达目标点的问题。

3)尽管一定程度上本文算法会将障碍物环境误判断成近似封闭的障碍物环境，使得计算量增加，但是路径规划的成功率得到了提高。