上一篇,我们讲完了RRT,这回我们来讲运动规划入门系列的最后一个算法——人工势场法。回想当时我第一次听说人工势场法的时候,不明觉厉,感觉这似乎是一个十分高大上的规划算法,但是当我真正了解以后才发现,其实人工势场法的思路反而是这个系列五个算法中最好理解,最符合直觉的。在这篇博文中,我将为小伙伴们揭开人工势场法神秘的面纱。

1. 人工势场的原理详解

物理学的势(potential),也称做“位”,是一种能量概念。在保守场里,把一个单位质点(如重力场中的单位质量,静电场中的单位正电荷)从场中的某一点A移到参考点,场力所作的功是一个定值。也就是说,在保守场中,单位质点在A点与参考点的势能之差是一定的,人们把这个势能差定义为保守场中A点的“势”。
高中知识会学到电场和磁场,一个处于电场中的电荷会受到电场力的作用,从而做功。而人工势场的思路于其十分的相似,我们人工地在障碍物地图的基础上添加一个特殊的场,这个场会引领机器人从起点运动到终点。 而人工势场法的重点就落在了以下两个问题上:
  1. 如何构建这样的一个人工势场?
  2. 如何利用人工势场进行运动规划?

    1.1 引力势场(Attractive Potential Field)

    人工势场这个特殊的势场并不是一个单一的场,其实它是由两个场叠加组合而成的,一个是引力场,一个是斥力场。 顾名思义引力势场是具有吸引的性质,会将机器人从起点处朝着终点处吸引,所以引力场的存在使得机器人获得了运动的大方向。 在实际的工程中,其实有很多种方法可以构建这样的一个引力势场,最简单而且也是最常用的方式就是直接对地图自由空间的每个点都相对终点计算出欧氏距离的平方,并乘上一个缩放系数ε fa(x, y)便是所谓的引力势场函数,它会构建一个离终点越远引力越大的特殊势场,在Matlab中可以非常直观地看到这个引力势场。

    1.2 斥力势场(Repulsive Potential Field)

    当然仅仅只有引力势场是不够的,我们还需要让机器人懂得避开地图中的障碍物,这时斥力势场便有用武之地了,斥力势场的会构建一个距离障碍物越近,斥力越大的特殊势场。 这个过程其实非常好理解,引力势场负责吸引机器人从起点朝着终点运动,斥力势场负责规避地图中的障碍。 通常我们会用下面这个函数来构建斥力势场: 其中ρ(x, y)是一个特殊的函数,它会计算出离当前点(x,y)最近的障碍物的距离,而d0是一个距离阈值,当当前点到最近障碍物的距离大于d0时不产生斥力。η同样是一个简单的缩放系数。 在Matlab中可以直观地看到这个斥力势场的样子,离障碍物越近的点所具备的斥力值越大,离障碍物越远斥力值越小,甚至为0。 我们生成了引力势场和斥力势场这两个特殊势场之后,只要将两个势场进行简单的叠加组合之后就得到了最终的人工势场。 在Matlab中可以直观地看到这个叠加的结果如下,其实相信看到这里小伙伴们应该有点感觉了,当我们每个人工势场都是根据特定的终点而特定生成的,在地图不变的情况下,改变终点的位置便会改变人工势场。终点的位置总是人工势场中势能最低的地方,想象一下,现实中存在一个长得和人工势场一样的曲面,现在我们拿着一个小球放在曲面的高处,那么在重力的作用下,小球自然而然地就会顺着曲面滚到最低点。如果你成功地想象出这个画面,那么恭喜你,你已经领悟了人工势场的核心思想了。

    1.3 梯度下降

    相信只要是学过高数的小伙伴一定知道梯度的概念,如果你忘记了,那么赶紧回去复习。梯度下降法在寻找最优点的问题上被十分广泛地运用,但其实这也是一个听名字很高大上,说穿了很直观的方法。 我还是和各路前辈一样使用山坡为例,来说说明梯度下降法的核心思想。假设你一觉醒来被空投到一个未知的山坡上,现在要求你尽全力下山,也就是说要你找到最低的点。那么这时候你该怎么办呢?非常简单,第一步:环顾你的四周找到一个坡度最陡峭的地方;第二步:朝着最陡峭的方向迈出一步;就这样重复执行第一步、第二步,直到你到达一个位置,在这个位置的四周都比它高,也就是说这是一个你能找到的最低的点。 在数学中,梯度的方向就是函数位于当前某一点(x0,y0时,增长速度最快的方向。那么反过来,将函数添加上负号,再求梯度,便可以找到函数减少最快的方向。 所以这便回答了方才提出的“如何利用人工势场进行运动规划”这一问题,我们采用梯度下降法配合人工势场进行运动规划。

    2. 人工势场法的Matlab实现

    2.1 引力势场函数

    首先我们需要生成一个和地图同样大小的meshgrid 然后引力势场函数的实现相对比较简单,就是计算meshgrid中每个点相对于终点的欧氏距离的平方,乘以一个缩放系数。对,就是这么简单。

    2.2 斥力势场函数

    斥力势场函数在实现中比较麻烦的点在于ρ(x,y)函数,但是各位不要担心,万能的Matlab已经有现成的函数可以实现这个功能,这个函数就是bwdist() bwdist()的描述中我们可以得知,这个函数其实是一个图像处理函数,他会计算出一张二值图片中所有像素点相对其最近的非零像素点的距离。这就正合我们意了,我们的障碍物地图恰好就是一张二值图片,0表示自由空间,1表示障碍物。那么这个函数就会计算出地图中每个点相对最近障碍物的距离值,当然如果当前点恰好是个障碍物,那么最近的障碍物就是它自己,所以得到的距离结果就是0。 如下图的代码所示,influence就是表达式中的d0即距离阈值,这里将bwdist()的结果除以100再加1,首先是除以100是为了将距离值缩放到一个合理的范围,其次加1是为了规避前面说过障碍物结果为0的情况。 最终将两个生成的势场简单地相加就可以得到最终的人工势场了。

    2.3 梯度规划器

    Matlab将梯度显示出来以后我们可以看到如下图所示,图中各个小箭头就是代表当位置的梯度大小和方向,其中远离障碍物的位置的梯度明显指向黄色的终点,越靠近终点处的梯度值越小;靠近障碍物的地方的梯度明显呈现排斥的趋势,而且越靠近障碍物排斥力越大。 梯度规划器核心代码如下所示,可以看到在每轮迭代中都会沿着当前梯度的方向前进单位距离,直到到达终点,即梯度下降收敛。

    2.4 最终运行效果

    最终的运行结果如下,可以看到最终规划出的是一条沿着梯度方向走的光滑路径 为了更加直观地看到效果,我另外用一个小球代表机器人制作了下面这个动画,这回是不是就特别好懂了。这就是为什么我在开头的时候说人工势场是这个系列五个算法中最好理解,最符合直觉的。

    3. 人工势场的不足

    人工势场法其实也不是完美无缺的规划算法,它也是有缺点的,比如在某些情况下会陷入局部最优解,而导致规划失败,比如当我们设置起点和终点如下。 那么这种情况是会陷入局部最优解的,具体情况如下图所示,我们可以看到路径在梯度下降的过程中卡在了死胡同里,最终导致规划失败。 再比如,我们将起点和终点设置如下,让我们来看看会怎么样? 从下图的结果可以看出,这会导致另一种情况:终点的位置距离障碍物太近,规划路径难以接近终点的位置,只能停在终点附近,最终规划失败。

尾声和我的暂别:

从4月份到现在,当初答应你们的5个运动规划入门算法已经悉数奉上,那么本系列就可以暂告一段落了。希望笔者这粗糙的讲解可以帮到你们些许。 由于笔者精力实在是有限,只能每月一更,这个更新速度确实是挺慢的,所以非常感谢各位这几个月以来的包容和支持。同样也是笔者个人的精力原因,我需要暂时停更一段时间,2020年恐怕是不会再更新了,当然你们的评论我还是会尽力答复的。 那么各位,来年春天再见!