常见的避障算法介绍

常见避障算法介绍：

实时避障是反映智能移动机器人自动能力的关键问题之一,国内外学者曾做过大量的研究工作，常见的避障算法有如下几种：

（1）可视图法[52]

可视图法将机器人、目标点和多边形障碍物的各顶点进行组合连接，连接的直线视为弧，要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及障碍物顶点与顶点之间的连线均不能穿越障碍物，即直线是可视的。机器人延这些可视线行进直至离开该障碍。使用这种方法时，缺乏灵活性，一般需要机器人停止在障碍前搜集传感器数据，并且它受传感器精度影响较大。

（2）人工势场法[53]

人工势场法是由Khatib 提出的一种虚拟力法，其基本思想是建立一种虚拟力，将机器人在未知环境中的运动视为在人工虚拟力场中的运动，即假设目标对

机器人存在着吸引力t F ，而障碍物对机器人有排斥力r F ，那么引力和斥力的合

力作为机器人运动的加速力，从而计算出机器人的位置和控制机器人的运动方向（如图4-1）。势场法结构简单，便于底层的实时控制；但是也存在若干缺陷，比如：在相近障碍物间不能发现路径；在狭隘的通道中会来回摆动等。

（3）VFH （Vector Field Histogram ）直方图

由于势场法的缺陷，J. Borenstein 完全放弃了势场法，而设计了一种称为V FH 的方法，它将机器人的工作环境分解为一系列具有二值信息的栅格单元，每个矩形栅格中有一个积累值，表示在此处存在障碍物的可信度，高的累计值表示存在障碍物的可信度高。这是因为传感器不断快速的采样环境，存在障碍物的栅格不断被检测的结果。栅格大小的选择直接影响着控制算法的性能。栅格选得小，环境分辨率就高，但是抗干扰性就比较弱，环境信息存储量大，使得决策速度慢；栅格选的大，抗干扰性就比较强，但环境分辨率下降，在密集障碍物环境中发现路径的能力减弱。另外，栅格大小的选取也与传感器的性能有关，若传感器的精度高而且反应速度快，栅格可以选的小些。

由V FH 控制的移动机器人表现出了良好的性能。本研究中就是采用该方法作为机器人的避障策略。其算法思想在下文中具体介绍。

图5-1 势场法思想简图

5.2 VFH避障算法介绍

5.2.1 CV（Certainty Value）值的确定

在VFH算法中用二维的栅格来表征环境。将机器人的工作空间划分为若干连续的二维栅格系列。每个栅格中都包含一个概率值。这个概率值体现了在该栅格中存在障碍物的可信度，CV值越高，表示此处存在障碍物的可能性就越大。它通过一个与所用传感器特性有关的概率方程进行更新。如图5-2，对于声纳传感器而言，它具有椎形视角，返回的是传感器到该锥形区域内最近一物体的距离值。在运行过程中，当机器人接收到传感器读数后，利用该读数值，通过使用概率函数

C更新锥形区域内每个栅格的概率值，从而获得对障碍的最新认识。实x

验表明，离该锥形轴线越近的栅格更新的越快。我们可以这样认为：被检测到的障碍物最可能的位置就是在锥形轴线附近。

由上述可知，机器人每接收到一个传感数据，就要调用一次概率函数。显然这样会使计算复杂度提高，导致反应延时而不利于数据的实时处理。这在机器人运动速度较快时表现更为明显。因此，可以将算法进行如下改动：由于被检测到的障碍物最可能的位置就是在锥形轴线附近，所以我们每次仅仅需要更新位于锥形的轴线上且到传感器距离等于传感器读数的那个栅格即可。在机器人不断的运行、传感器连续采样的过程中，这种方法同样可以获得对障碍物的概率分布。同时注意到声纳传感器有其固有的一些缺点：比如方向性较差，抗干扰能力较低，错误读数多等。在这里我们着重考虑的是因其抗干扰能力低而产生较大噪音的问题。

图 5-2 声纳数据概率

为解决这个问题，可以从硬件和软件两方面进行处理。比如可以使用由24个声纳均匀分布而组成的声纳环。每次只触发四个声纳，且必须保证声纳之间均为90度。这样可以减少声纳之间声波的相互干扰。此外，在算法中也对噪音进行处理，削弱其影响。思想如下：

不在每个栅格中分配具体的概率值，而是在其中记录其被声纳“发现”的次数。每检测到一次，赋一个权值。实验中取3（初始值均为0）。比如某栅格被检测到3次，那么其CV 值则为933=?。次数越多，表明该值的可靠性越高。同时在算法中，采用2CV 来加强合理值的影响。比如某一栅格具有合理CV 值1243=?，2CV 值则为144；另一栅格具有噪音CV 值313=?，2CV 值则为9。可以看出，通过CV 值来区分噪音似乎不是太明显，但是通过2CV 来判断的话，效果就好的多。然后可以通过设定阈值将噪音滤掉。

5.2.2 VFH 算法阐述

VFH 算法[54]构架如图5-3所示：

图5-3 VFH 算法构架

任意时刻机器人对外界环境的感知范围是有限的，并取决于所用传感器的有效测量范围。定义某一时刻机器人所能感知的最大范围为活动窗口（图5-4）。它实际上是以机器人为圆心，声纳传感器所测范围为半径的圆形区域。但在本研究中，为方便算法的使用，将其简化为边长为s w 的正方形区域。其中，s w 是声纳传感器所能测的最远距离的两倍。

（一）栅格向量化

将活动窗口内的栅格向量化。该向量大小由下式确定：

()()j

i j i j i bd a c m ,2

*,,-= 而其方向取决于栅格与机器人中心点（VCP ）的相对位置： 0

01,tan x x y y i j j i --=-β 其中：a ，b 是正常数；

*

,j i c 活动窗口内栅格()j i ,的CV 值 j i d , 该栅格到机器人中心点（VCP ）的距离值

00;y x 此刻机器人中心点（VCP ）的绝对位置坐标。

j i y x ; 该栅格的绝对位置坐标

图5-4 活动窗口说明

（二）活动窗口分区

若选择角分辨率α，则分区后得到的区间总数α360=n 。对于任意区间)1,,2,1,0(,-=n k k ，有??

? ??=αβj i k ,in t 。其障碍密度k h 可以由下式得出： ∑=j i j i k m h ,,。在本研究中 5=α。

由于CV 值的离散性，可能导致障碍密度的过于稀散。因此要对其进行平滑处理：

()122121121'-++-++++=

+-+++-+-l h h h l lh h h h l k l k k k l k l k k （5-1） （三）确定运动方向θ 通过式5-1可以得到活动窗口中每个分区的障碍密度。给定某一阈值τ，障碍密度低于该值的区域，称为“候选区”。当有连续max S （实验中max S =18）个候选区存在时，称它们为“宽谷”；否则称之为“窄道”。将这些连续候选区中最左边的一个区记为l k ，最右边的一个区记为r k ，则运动方向可以由下式子得出：()r l k k +=2

1θ 5.2.3 VFH+ 算法阐述

VFH ＋算法是在VFH 算法基础上发展起来的[55]，它充分考虑了机器人的大

小尺寸对算法结果的影响。如图5-5所示，在VFH+中将栅格放大r r ，r r 取决于机器人的尺寸。为了进一步加强机器人运行的安全性，还要将机器人与障碍可以保持不碰撞的最短距离s d 考虑在内。所以对于任意待研究的栅格其实际上被放大了s r r +，s r s r d r r +=+。

这样，扩大角ij γ满足：ij

s r ij d r +=arcsin

γ。对于任意分区k ，其在极坐标下的障碍密度为：∑∈?=

a C j i ij ij p k h m H ,'。 当满足条件[]ij ij ij ij k γβγβα+-∈?,时1'.=j i h ；否则，0'.=j i h 。为了使机器人得到平滑的运动轨迹，像VFH 中那样使用单一阈值τ来决定安全区域是不够的。在VFH ＋中，将采用low τ与high τ两个阈值。具体操作如下：

若 high p i k H τ>, ，则 1,=b i k H ；

若 low p i k H τ<, ，则 0,=b i k H ；

其他情况 则 b i k b i k H H 1,,-=。

图5-5 障碍扩大示意图

在VFH+算法中，为了动态分析机器人的运动，将其轨迹分解成运动方向不变时的直线与方向改变时的弧线。该弧线取决于机器人的转动半径，与机器人的速度密切相关，速度越快，其旋转半径越大。如图5-6所示，假设机器人向左旋转时的转向半径为left r ，右转时的转向半径为right r 。A ，B 为两个障碍栅格。按上述方法将A,B 扩大，假定A 与机器人的左转向圆有重叠交叉，那么A 与左转向圆覆盖的所有区域被认为是禁止通行区（blocked ）；B 与转向圆无交叉现象所以只有其自身覆盖的区域为禁止通行区。在图5-6所示情况下，机器人将右转。

具体算法如下：

1） 确定转向圆的圆心

θs i n ?=?r r r x θcos ?=?r r r y

θsin ?-=?l l r x θcos ?-=?l l r y

2） 计算障碍栅格j i C ,到两转向圆心的距离

()()()()2

22i y y j x x d r r r ?-?+?-?= ()()()()2

22i y y j x x d l l l ?-?+?-?= 3） 条件判断

若 22)(s r r r r r d ++<， 机器人右方被阻；

若 22)(s r l l r r d ++<， 机器人左方被阻。

图5-6 算法示意图

通过对上述条件的对照比较可以得到两个极限角度，分布在机器人左右两侧。分别记为l ?及r ?。同时定义πθ?+=b ，表示机器人当前运动方向的反向。初始时刻令b r l ???==。对于活动窗口中任意栅格j i C ,，在其CV 值满足τ

通常情况下，我们可以得到若干符合0=m k H 的()l r ??,组合。对于每个组合，

记其左右边界分别为：l k 和r k 。若l k 和r k 间包含了max S 以上个区间（max S 为常量，本实验中取10），则称该区域为“宽域”；否则称之为“窄域”。窄域只提供一个候选方向n c 且2

l r n k k c +=，转化为角度后为n n c ?=α?。而宽域可以提供三个候选方向：r c ，l c 以及t c 。

2max S k c r r +

=，转化成角度为r r c ?=α?； 2

max S k c l l -=，转化成角度为l l c ?=α?； 此外，当目标方向t k 满足[]l r t c c k ,∈时有t t k c =，转化成角度为t t c ?=α?。 为选出最合适的运动方向c ，建立以下代价函数：

()()()1,321,,,-??+??

? ????+??=i n i t k c c k c c g μαθμμ，其中： (){}n c c n c c c c c c +----=?21212121,,min ,，是用来计算两个区间1c 和2c 绝对角度差的函数。比如()t k c ,?表示的是候选方向与目标方向间的差角，其值

越大，机器人运动时偏离目标就越远，到达目的地的代价也就越高。??

? ???αθi c ,表示的是候选方向与机器人行进方向间的角度差，该值越大，机器人转向变化越大。()1,,-?i n k c 表示的是当前候选方向与前次所选方向间的角度变化，值越大，车轮转向变化越大，运动震荡越大。

所以权衡系数1μ，2μ及3μ的选择至关重要，它们直接决定了算法的优越性。一般情况下应满足：321μμμ+>。在本研究中，51=μ，232==μμ。 注意到在上述讨论中主要是针对点障碍的。但是在有些场合下线特征更容易被提取，此时就需要考虑线状障碍。这样，在用VFH ＋算法时就应该做一些改动。

假定VFH ＋算法的主体思想不变，只是在对障碍物进行放大处理的时候做如下简单变动：

图5-7 线障碍的扩大处理方式

如图5-7所示，将线障碍的端点看作时两个点障碍并按照原始的VFH ＋算法进行

放大s r r +；然后整体考虑障碍将其放大s r s r r l r +++=2

1'。其中l 为该线障碍的长度。