人工势场法局部极小值优化方法研究

Study on Local Minimum Optimization Method of Artificial Potential Field Method

摘要: 人工势场法是目前路径规划常用的算法之一，但其存在的局部最小值问题会导致智能移动机器人无法到达目标点。本文针对人工势场法局部最小值优化的三种算法展开研究。文章选择了算法运行平均时间和成功到达目标点的成功率作为研究对象，通过设置三种优化算法在不同障碍物下运行，观察不同设置情景下算法运行时间和成功率的变化，得到这三种优化算法的各自适合的障碍物环境。文章为这三种优化算法的应用提供了参考依据。

Abstract: Artificial potential field method is one of the commonly used algorithms for path planning, but its local minimum problem will cause the intelligent mobile robot to fail to reach the target point. In this paper, three algorithms for local minimum optimization of artificial potential field method are studied. In this paper, the average running time of the algorithm and the success rate of successfully reaching the target point are selected as the research objects. By setting three optimization algorithms to run under different obstacles, the changes of the running time and success rate of these algorithms under different setting scenarios are observed, and the obstacle environment suitable for each of the three optimization algorithms is obtained. This paper provides a reference for the application of these three optimization algorithms.

1. 引言

随着自主机器人技术的迅速发展，路径规划问题一直是一个备受关注的领域。自主机器人，包括自主车辆、机器人和无人机，需要在各种环境中进行自主导航，从而实现任务如搜索救援、自动驾驶和勘探。自主机器人除了在硬件方面需要不断的完善，它在路径规划方面也在不断发展。目前路径规划主要有图搜索算法比如A*算法 [1] [2] ，文献1和2所提方法通过对A*算法分析及仿真实验结果可知，传统A*算法原理简洁，便于理解操作，同时在进行路径规划时具有搜索路径简单，快捷的特点。采样法比如快速探索随机树法 [3] ，文献所提方法利用RRT算法的随机拓展特性逃离人工势场中的局部极小值问题，逃离速率受到扩展树的扩展速度与随机性的影响。路径规划还有比如遗传算法和模拟退火算法 [4] [5] [6] 文献4所提方法当航路点陷入威胁区时利用模拟退火算法求解总势场强度更小的点，直至惩罚势函数为零，使航路点成功跳出威胁区，避免了标准方法中参数取值对航路点逃离威胁区的影响，该改进方法易于实现且收敛快速。目前路径规划用的最多的方法就是人工势场法 [7] [8] [9] 。人工势场法是一种常用于路径规划的方法，通过模拟物体在势场中运动的方式来规划路径。在这个方法中，目标点被视为吸引物，而障碍物则被视为斥力物。机器或机器人受到目标的引力和障碍物的斥力的影响，最终沿着势场梯度移动，找到路径。这种方法简单直观，易于理解和实现。

然而，人工势场法也有一些问题，例如可能陷入局部最小值，导致路径不够优化，因此需要对人工势场法进行改进。如文献 [9] 利用人工势场法对机器人在特定环境中进行路径规划，并针对传统人工势场法存在的局部极小点问题，引入沿墙走行为 [9] ，运用改进的人工势场法有效地克服了机器人在障碍物附近出现的反复震荡或停止不前等问题。文献 [10] 针对传统人工势场法无人船路径规划中无法到达目标点、局部极小值、路径振荡的问题，提出了一种改进人工势场法。修改斥力函数，解决无人船无法到达目标点问题；施加艏向角限制，增加随机扰动 [10] ，解决无人船存在的两种局部极小值问题。文献 [11] [12] [13] 提出采用填平势场 [11] [12] [13] 与模拟退火算法相结合的解决策略，求解势场强度的最小值作为下一行走目标，多个序列目标构成优化路径，引导机器人脱离局部极小点，绕过障碍物到达目标点。人工势场法有很多种改进的方法，本文就使用最多的方法如沿墙走，随机扰动以及填平势场这三种方法进行追踪研究，来给读者展示这三种方法的利弊。

2. 人工势场法在机器人路径规划中的应用

2.1. 传统人工势场法

Khatib首先提出人工势场法 [14] 的基本思想，其基本思想的主要内容是：见图1机器人在自主行进的过程中，遇见障碍物的话，障碍物周围会生成斥力场，对机器人产生排斥力；同时目标点周围会生成引力场，对机器人产生吸引力。机器人在运动过程中所受合力的方向是其提供运动的所需方向，机器人沿着该方向逐渐向目标点移动的过程中避开障碍物，最终到达目标点。

2.2. 引力场

引力场的方向 [15] 由机器人指向目标点，大小如式(1)所示。

$=\frac{1}{2}\delta {\rho }^2\left(q,\right)$ (1)

$\rho \left(q,q_{goal}\right)=\sqrt{{\left(x_3-x_1\right)}^2+{\left(y_3-y_1\right)}^2}$ (2)

其中 $U_{att}$ 为目标点的引力场； $\delta$ 为大于0的引力势场增益系数； $\rho \left(q,q_{goal}\right)$ 为机器人当前位置和目标点的欧氏距离；机器人的当前位置 $q\left(x_1,y_1\right)$ ；目标点的位置 $\left(x_3,y_3\right)$ 。

引力为引力势场的负梯度，因此得到引力公式为：

$F_{att}=-\nabla U_{att}=\delta \rho \left(q,q_{goal}\right)$ (3)

引力与目标之间的距离成反比，即距离越远引力越弱。

2.3. 斥力场

斥力场的方向 [15] 由障碍物指向机器人，大小如式(4)所示。

$=\{\begin{array}{c}\frac{m}{2}\ast {\left(\left(\frac{1}{\rho \left(\text{q},q_{obs}\right)}\right)-\frac{1}{{\rho }_0}\right)}^2,\rho \left(\text{q},q_{obs}\right)\le {\text{ρ}}_0\\ 0,\rho \left(\text{q},q_{obs}\right)\le \text{ρ}\end{array}$ (4)

$\left(q,q_{obs}\right)=\sqrt{{\left(x_2-x_1\right)}^2+{\left(y_2-y_1\right)}^2}$ (5)

其中， $U_{rep}$ 为障碍物的斥力势场；m为斥力场系数因子； $\rho \left(q,q_{obs}\right)$ 为机器人当前位置到障碍物的欧式距离；障碍物的坐标 $\left(x_2,y_2\right)$ ； ${\rho }_0$ 为安全范围半径。

斥力为斥力场的负梯度，因此得到斥力公式如式(6)所示。

$=-\nabla grad=\{\begin{array}{c}m\left(\frac{1}{{\rho }_0}-\frac{1}{\rho \left(q,q_{obs}\right)}\right),\rho \left(q,q_{obs}\right)\le {\rho }_0\\ 0,\rho \left(q,q_{obs}\right)>{\rho }_0\end{array}$ (6)

斥力与障碍物之间的距离成正比，即距离越近，斥力越强。

2.4. 牵引力

牵引力大小 [15] 为引力和斥力之和，假设机器人周围存在s个障碍物，机器人受到的合力为

$F_{total}=F_{att}+{\displaystyle {\sum }_{i=1}^s{F}_{repi}}$ (7)

机器人受到的合力方向就是移动的方向，随着合力的变化最终得到一条到达目标点的路径，当

$F_{att}+{\displaystyle {\sum }_{i=1}^s{F}_{repi}}=0$ 时，机器人就会陷入局部最小值。

注：F_att为起点对小车的吸引力，F_rep为障碍物对小车的斥力，通过力的合成得出小车的行驶方向为F_合的方向。

Figure 1. Direction of tractive force under potential field

图1. 势场作用下牵引力方向

3. 传统人工势场法局部极小值问题

局部极小值是指在势场中的某个点，其势能值比其周围的点低，但并不一定是全局最低点。机器人在局部极小值点附近可能会停滞，因为它看不到更低的势能值，而这个点附近的斜率都为零。这意味着机器人可能会陷入一个局部最小值附近的无法继续前进的状态，而没有找到通往目标的路径。传统的人工势场法有可能会陷入局部极小值而导致机器人来回徘徊无法跳出极小值点。当机器人在工作环境中受到的合力为0 [16] 时，就会停止在这一位置，或者在此处徘徊。合力为0的情况 [16] 可以分为以下两种(见图2)：一是机器人、目标点、障碍物在同一直线上；二是多个障碍物斥力的合力与引力大小相等、方向相反时。具体地讲，当满足以下两式 [16] 时，就进入了局部最小值区域。

$\{\begin{array}{c}\frac{F_{att}-{{\displaystyle \sum }}_{i=1}^k{F}_{repi}}{F_{att}}\\ -1\le \cos \left(\angle F_{att}-\angle F_{rep}\right)\le 0\end{array}<$ |є| → 0 (8)

$-1\le \cos \left(\angle F_{att}-\angle F_{rep}\right)\le 0$ 的意思是当机器人受到的牵引力的角度在90˚~180˚之间时，机器人受到的斥力比吸引力大而导致机器人会向远离目标点的方向前进，从而导致机器人陷入局部最小。

注：图2为整齐排布的局部最小值，局部最小值可能会不止一个，图2中的局部最小值只有一个。

Figure 2. Two stress situations with resultant force of 0

图2. 合力为0的两个受力情形

人工势场法陷入局部最小

如图3所示机器人在朝向目标点运动的过程中被一个障碍物阻碍导致机器人来回徘徊最终陷入局部最小点。下图中障碍物的坐标为(5, 5)，(5, 9)，(7, 7)，(9, 5)，起点坐标(0, 0)，目标点坐标(10, 10)，机器人陷入局部最小点的坐标为(4.6, 4.6)，引力势场增益系数为1，斥力场系数因子为1，安全距离半经为1.5。

注：图3通过仿真实验展示了障碍物整齐排列下局部最小值存在的情况。

Figure 3. The artificial potential field method falls into local minima

图3. 人工势场法陷入局部最小

运用上文中的公式(3)和公式(6)可得： $F_{att}=0$ ； $F_{repi}=0$ ； $F_{att}+{\displaystyle {\sum }_{i=1}^s{F}_{repi}=0}$ 所以陷入局部最小。

4. 优化与分析

4.1. 三种算法原理

(1) 沿墙走改进人工势场见图4，它通过模拟沿着环境的墙壁移动来实现路径规划。这个方法的思想是，机器人受到来自墙壁的排斥力，从而沿着墙壁行进，从而避免与墙壁碰撞。

(2) 随机扰动改善人工势场法见图4，随机扰动是指在路径规划的过程中引入一定程度的外界刺激去改变算法在每一次迭代过程中的行为从而增加每一次路径规划的多样性和适应性。

(3) 填平势场法见图4，它是通过引入一个平滑势场，改变填平势场增益来更剧烈的推动机器人运动避免陷入局部极小值，通过应用梯度下降，机器人被引导沿着势场进行移动，从而调整初始路径。梯度下降的方向是势场的梯度方向，使得机器人在势场中受到的合力最小。

Figure 4. Obstacle avoidance by different algorithms

图4. 不同算法避障

4.2. 仿真实验及分析对比

4.2.1. 三种优化算法时间对比

为了充分验证三种算法的有效性和对比三种算法的差异性，选取了10组随机障碍物，三种算法在相同的随机障碍物的情形下运行100次，随机障碍物的个数分别为10个，20个，30个，40个，50个，60个，70个，80个，90个，100个。智能小车的起点为(0, 0)，终点为(10, 10)，障碍物都放在10 * 10的地图内，通过算法尽可能保证障碍物的合理分布，使得智能小车可以成功到达目标点，对比三种算法在不同障碍物的情况下成功到达目标点的时间。

Figure 5. Time diagram of different obstacles successfully reaching the target point by three algorithms

图5. 三种算法不同障碍物成功到达目标点时间图

Figure 6. Average time for different obstacles to successfully reach the target point

图6. 不同障碍物成功到达目标点平均时间图

Figure 7. Is a supplementary figure for the reasons for the occurrence of Qiyi points along the wall

图7. 针对沿墙走出现奇艺点原因补充图

由图5图6可知，随着障碍物个数的不断增加，沿墙走算法的弊端也越来越明显，沿墙走算法成功到达目标点的时间随着障碍物的增加不断变大，由图6可以清楚的看出在障碍物70个的时候，沿墙走算法的平均时间增幅特别的大，由此可以看出沿墙走算法并不适合障碍物密集的情况。而随机扰动平均时间走势稍有波动，影响不大。填平势场法平均时间走势最为平稳。

针对图5中沿墙走上出现的个别的奇异点的现象，做了图7的补充实验，主要是把图5中出现异常的点的障碍物单独拿出来放进沿墙走算法里面单独跑一遍。由图7可以看出造成沿墙走算法会出现个别奇艺点的原因主要是有一下两点(1) 虽然障碍物的分布是做过限制的，但是偶尔还是会出现障碍物的排布造成智能小车来回徘徊不前的点，这样一来就大大增加了算法的运行时间。(2) 障碍物的排布太过密集，障碍物对智能小车的斥力太大而走了障碍物的外围从而造成了时间花费太多。

4.2.2. 三种优化算法成功率对比

本次实验设置6组随机障碍物，每组随机障碍物在相同情况下运行100次，6组随机障碍物的个数分别为10个，30个，50个，80个，100个，200个。设置两个地图对比，地图为10 * 10，起点为(0, 0)，终点为(10, 10)。本实验对三种算法能否到达目标点不设置限制，对比三种算法在不同障碍物下的成功率。

Table 1. Comparison of the minimum success rate of the three artificial potential field methods

表1. 三种人工势场法最小值成功率对比方法

由表1可以看出随机扰动的成功率最高，效果显著，填平势场法的成功率最低。通过对比三种算法的成功率不难看出，随着障碍物密度越来越密集，沿墙走受到的影响最大，说明沿墙走对于障碍物比较多的情况不适用，随机扰动的优化方法对于障碍物多的情况明显由于其他两个优化方法。

4.2.3. 实验数据分析

(1) 通过对三种优化方法进行Matlab实验，研究者设置起点和目标点的时候要和小车保持一个安全距离，否则会出斥力或者吸引力太大的情况，从而导致实验失效。

(2) 设置障碍物的时候要避免障碍物绕着目标点。

(3) 综合来看，从时间看上，在保证小车可以顺利到达目标点的情况下，随着障碍物的个数的增加，以设置60个障碍物作为分水岭，在障碍物小于等于60的时候，三种优化算法的时间变化都很平缓，在障碍物大于60个以后沿墙走的时间突然增加，随机扰动稍有变化，但是总体时间依旧很短，填平势场法时间最短，最为平稳。从成功率上看，在小车能否到达目标点不确定的情况下，随机扰动的成功率最高，填平势场法的成功率最低。对比两种情况的实验，可以得出随机扰动的优化方法不仅时间短，成功率还高。

5. 结论

本文通过仿真实验说明人工势场法局部最小值存在的原因和三种优化算法解决局部最小值的原理；再设置两种仿真实验来进一步说明三种优化算法哪一种更优，设置的两种仿真实验分别是在保证小车能够顺利到达目标点的情况下，通过改变障碍物的个数来看三种优化算法的运行时间和在不保证小车能够顺利到达目标点的情况下，通过改变障碍物的个数来看小车成功到达目标点的成功率。在前一个实验中，沿墙走算法不适用于障碍物多的条件，障碍物的增加会导致在该算法下小车不断地沿墙走但是始终走不出来的情况从而导致小车运行的时间变长。后一个实验，随着障碍物越来越密集，随机扰动算法的成功率最高且成功率的下降幅度最小，而填平势场法的成功率在三种算法中是最低的。综合这两种实验来看，随机扰动算法不管是在时间上还是成功率上表现俱佳。本文为后期更好的改善局部最小值优化算法的研究提供参考。

基金项目

南京工程学院校级科研基金项目资助，项目号：CKJB202208。