逃离传统势场法局部稳定点策略∗

耿双乐 罗顺心

（上海理工大学光电信息与计算机工程学院 上海 200082）

1 引言

人工势场法是当前移动机器人路径规划中最常用的算法之一。人工势场法［2］是由Khatib在1986年提出的一种局部路径规划算法。人工势场法无需通过复杂的建立环境模型，只需传感器感知与障碍物信息就可完成避障。人工势场法通过引入物理上势场概念，并通过势场梯度得到引力和斥力。通过梯度下降法求得引力斥力值。由于无需复杂建模过程，并具有良好的避障功能，所以在移动机器人路径规划领域运用广泛。然而传统势场法也存在两种固有的缺陷。一种是复杂环境下或者某区域位置合力为零的情况下会陷入局部最优状态。一种是目标点周围存在障碍物时，又无法到达目标点［3］。

传统势场法在复杂环境中容易陷入局部最优状态。文献［4～6］分别通过SA算法结合、模拟退火算法、自适应过程去解决局部最优问题。此外加入虚拟中间点［7，11］方式也可逃离局部目标点。同时对于动态障碍物环境下的避障［8，12，14］也引入速度势场概念完成动态避障。本文通过利用周期距离检测，结合栅格法局部建模方式完成逃离局部最优点逃离。传统势场法中的目标点不可达问题，最常用是S.S.GE在文献［3］提出的加入相对距离因子方法。此种方法是从数学函数方面进行改进。人工势场在路径规划中将移动机器人当做无约束性质点［15］考虑，无需复杂建模。

2 传统势场原理

势场法将整个运动空间抽象成一个势场，目标点对移动机器人会形成一个引力场，运动空间内所存在的障碍物又会在一定范围内对机器人形成一个斥力场。势场能是人工势场最原始数学模型。通过梯度下降方法，分别求得目标点产生的引力和障碍物产生的斥力。因此机器人所在的空间即为引力场和斥力场所叠加的合力场。

图1 引力势场分布图

图2 斥力势场分布图

机器人始终沿着势场梯度下降的方向运动。将斥力场的负梯度作为斥力虚拟力，引力场的负梯度作为引力虚拟力。因此，移动机器人在空间中运动受到引力和斥力的合力作用。设机器人在运动空间中实时位置为 X=[x，y]，下式（1）、（2）中构建了引力场和斥力场关于机器人位置变化的函数。

其中Uatt表示移动机器人所受到目标位置的引力场，katt是自定义的引力场系数， ||X-XG表示机器人与目标点之间的欧几里得距离。XG表示目标点的位置。η为可自定义的斥力场系数，ρo为自定义的障碍物斥力场影响范围，Xob为障碍物所在的空间位置。那么目标与障碍物所产生的负梯度即引力和斥力如下式（3）、（4）：

传统势场法根据传感器装置不断检测机器人与障碍物和目标点的距离信息，并通过人工势场算法转化为引力和斥力进行规划。人工势场在合力为零或者复制环境中移动机器人可能会陷入局部最优稳定区域无法逃离。本文通过周期距离检测方式，检测局部稳定区域，并结合人工势场参数，建立合适栅格模型运用启发式搜索算法进行逃离。

3 扫描周期距离检测稳定区域

人工势场是根据力的作用导向目标点。因此会存在合力为零状态。常见的陷入局部最优有三种状态如图3～图5所示。

图3 单障碍物陷入局部最优图示

图4 多障碍作用下陷入局部最优状态

图5 复杂障碍物下陷入局部稳定区域

如图3中，由于移动机器人和障碍物、目标点都在同一延长线上，此时会在某一位置下合力为零。图4多障碍物状态下在某一位置区域，多障碍物斥力方向相反可互相抵消，可能发生局部最优。图5中，在多复杂环境下，大型无规则障碍无法看做质点处理。此时在复杂环境中陷入局部震荡区域。

陷入局部最优环境下的移动机器人都是在某一区域范围内停止不前或者震荡。因此可通过时间周期距离检测方式检测。具体过程如下：

1）根据移动机器人移动步长L，设定震荡区域圆半径R=2L；

2）设定平均检测时间t，每隔一段时间周期进行一次局部最优检测观察机器人是否陷入或者逃离局部稳定点；

3）记录移动机器人当前实时坐标位置为Xnow；

4）每隔一段扫描周期后检测移动机器人扫描周期后的更新位置为Xafter。计算扫描周期前后两者位置的距离，与震荡位置区域半径R1进行大小比较。当|Xnow-Xafter|＜R1，表示陷入局部区域。当|Xnow-Xafter| ≥ R1，表示未陷入震荡区域或者已经逃离。

4 栅格法建模

4.1 栅格模型介绍

栅格法是一种全局路径规划的方法。通过对环境建模生成具有二值信息的单元栅格地图。单元栅格选取越大，精确度越低，但环境模型简单计算量较小。单元栅格选取越小，精确度越高，但是计算量较大不利于实时计算。因此在规划中完全运用栅格建模，不太具有可行性。在计算中通常用0和1表示栅格地图。其中一个设置为障碍物，另外一值为自由空间区域。栅格地图如图6所示。

图6 栅格地图

图6 所示黑色表示障碍物，白色区域为自由空间区域。在计算机中存储矩阵信息如图7所示。

图7 地图存储信息矩阵

4.2 栅格法处理复杂障碍物

移动机器人在实际运行环境中会存在大量无规则形状。因此通过栅格法环境建模时，需要对无规则障碍物进行“膨化”处理。“膨化处理”分为两种情况：一种是障碍物的面积大小小于栅格大小；一种是障碍物面积大于栅格大小。如果障碍物面积小于单元方格面积，此时单元方格内非完全障碍物。此时通过“膨化处理”，将整个单元格都作为障碍物方格。如果障碍物面积大于单个栅格面积，此时栅格地图将障碍物分为多个栅格，对剩余栅格继续做“膨化”处理。两种情况下的“膨化”处理过程，如图8～图10所示。

图8 障碍物面积小于单元栅格面积膨化处理图

图9 障碍物面积大于单元栅格面积未“膨化”处理

图10 障碍物面积大于单元栅格面积“膨化”处理

4.3 启发式算法在栅格模型下搜索路径

启发式算法是一种利用估价函数进行搜索路径的算法。估价函数通常分为真带代价函数和预估代价函数。代价函数表示如下表示：

g(n)是当前位置到达一下节点的真实代价，h(n)表示当前位置点到目标点的预估代价值。路径规划中，代价在栅格地图中表示为距离代价。通过栅格建模地图下，可通过启发式算法搜索路径，路径搜索原理如下：

1）初始化两张状态列表，一张是open列表，一张为closed列表。两张表一般记录位置信息。初始路径时，将起点加入open列表当中去。此时closed列表为空，不记录任何信息；

2）查看起始点位置相邻的方格，并可行路径栅格和可能到达目标点的栅格放入open列表当中去（栅格地图每一位置会存在四个行驶方向，或者加对角线可行路径为八个方向）。同时将上一栅格地点作为当前节点的父节点，称作parent。父节点用来寻求最终行驶路径。

3）此时将起始位置点从open列表中移除，并加入closed列表中。加入closed列表表明此栅格节点不在作为后续路径选择节点。

4）从open列表中选取下个位置的栅格节点。此时通过计算估价函数，分别计算出实际代价值和估计代价值之和。最后选取估计函数值最小节点，作为下一节点。同时将此节点从open列表中删除，放入closed列表中，表示此栅格节点不在作为下一路径节点选项。

5）不断重复以上过程，最终会将目标点加入到open列表中去。

在栅格环境中，启发式搜索算法是通过估价函数进行路径搜索，并不会陷入局部最优状态。在全局路径规划上，用栅格建模下采用启发式算法搜索路径计算量较大。因此可通过人工势场法先规划，并通过时间距离检测方法实时检测移动机器人是否陷入局部最优点。当路径规划完成时未检测到移动机器人陷入局部最优，此时通过人工势场正常完成规划。当检测到移动机器人陷入局部最优点，此时根据检测到实时位置，生成二维栅格地图，并利用启发式搜索算法完成路径搜索。基本原理流程如图11所示。

图11 混合算法流程图

4.4 局部最优状态下仿真分析

人工势场在三种常陷入局部最优状态时，通过栅格建模运用启发式搜索算法进行路径搜索到达目标点。如图12～图14所示，以下三种障碍物情形下，通过传统人工势场法无法完成规划，都存在合力为零，或者环境过于复杂陷入局部稳定震荡区域。

图12 单障碍物情况下陷入局部最优

图13 多障碍物情况下陷入局部最优

图14 多障碍物情况下陷入局部最优

图12 状态下由于移动机器人和障碍物、目标点均处于同一延长线上，因此当传统势场法引力和斥力都处于同一方向延长线，因此在接近障碍物时，移动机器人所受合力为零，陷入局部最优。在图13状态下，由于受到多种障碍物，并且存在合力为零的情况，因此也会陷入局部最优点。图14是常见的U星障碍物情况下，移动机器人陷入局部震荡无法逃离。

因此在移动机器人通过周期时间距离检测到陷入局部最优时，此时生成二维栅格地图，在栅格模型下运用启发式搜索算法搜索路径到达目标点。栅格地图下启发式搜索结果如图15～图18所示。

传统势场法由于无法掌握全局环境信息，在受单一数学模型下的虚拟力控制时很容易陷入局部最优。局部最优状况在实际应用场景中较少出现。人工势场由于无需复杂建模，并且具有较好的避障结果。因此整体路径规划下，采用人工势场法。实时通过时间周期距离检测是否陷入局部最优。当未检测到局部最优时，即整个规划过程都是通过人工势场完成规划。当陷入局部最优状态时，此时通过生成栅格地图运用启发式搜索算法到达目标点。此混合规划，可避免单一运用人工势场法无法完成整体规划。

图15 单障碍物局部最优下到达目标点

图16 多障碍物局部最优下到达目标点

图17 U型障碍物下陷入局部震荡区域到达目标点

图18 复杂环境下到达目标点

5 结语

本文提出在传统传统势场在可能存在几种障碍物情，通过时间周期距离检测方法实时检测移动机器人是否现在局部最优点，当未检测到移动机器人陷入局部最优时，则通过人工势场法完成路径规划。当检测出移动机器人陷入局部最优时，则在局部最优区域生成栅格地图，通过启发式搜索算法完成路径规划。