一种针对VFH系列算法阈值敏感问题的改进策略

1、一种针对vfh系列算法阈值敏感问题的改进策略庄宇辉，赵成萍，严华(四川大学电子信息学院，成都610065)摘要：针对vfh系列算法的阈值敏感问题，提出了一种新的自适应阈值改进策略.综合考虑移动机器人硬件 特性、运动特性和目标点环境设置初始阈值、确定阈值范围.使用阈值评价函数，对可选范围內的每组阈值与 可通行方向进行综合评价，使得机器人能够实时选取适合当前情况的阈值.最后在ros上实现算法，并使用 eai移动机器人平台进行多次对比实验.实验结果证明，使用自适应阈值改进策略后，机器人能够避免局部死 区，并在目标周围存在障碍物时，以较短的无碰撞平滑路径顺利到达目标位置.关键词：vfh;阈值敏感；自适

2、应阈值；移动机器人；ros中图分类号：tp312文献标识码：aan improved strategy for vfh threshold sensitive problemzhu ang yu-hui, zhao cheng-ping, yan hua(college of electronics and information engineering, sichuan university, chengdu 610065, china)abstract: in view of the threshold sensitive problem of vfh series algorithm,

3、a new adaptive threshold improvement strategy is proposed the initial threshold and the threshold range is determined by the hardware, motion characteristics of the robot and the target environment. a threshold evaluation function is used to comprehensively evaluate each threshold and accessible dir

4、ection in the optional range, so that the robot can get the threshold suitable for the current situation in real time. finally, the algorithm is realized in ros, and several comparative experiments are conducted by using the eai mobile robot platform. the experimental results show that when the impr

5、oved policy with adaptive threshold is applied > the robot can avoid local dead zone and successfully reach the target position in complex environment, especially when the target is surrounded with obstacleskey words: vfh； threshold sensitivity； adaptive threshold； mobile robot； ros1引言随着科技不断发展进步，

6、移动机器人的应用越来 越广泛.有效的自主避障是移动机器人系统必须具备 的一项基本能力，国内外学者对此做了大量研究.目前 比较成熟的理论有bug算法九役人工势场法、删格 法”等，其中不断发展完善的经典算法当属向量场直 方图法 vfh (vector field histogram)vfh 算法源于 johann borenstein 和 yoram koren 对虚拟势场法vff (virtual force field)"容易陷入局 部最小和数据激变等问题的改进随后他们提出了考 虑机器人运动学特性和机器人尺寸的vfh+算法卩为 突破vfh算法局限性，iwan ulrich和johan

7、n borenstein结合a*算法提出了更利于趋向目标的 vfh*算法".andrej babinec 和 frantisek duchon 提 出了结合tdt (time dependent tree)的动态环境下 的vfh*tdt算法.另外，国内很多学者对vfh算 法也做了很多研究并提出了很多改进算法，如针对 直方图构建的改进w和针对转弯策略的改进目前vfh系列算法主要有以下儿点不足： vfh系列算法依赖所用传感器，受环境设备的制约; vfh系列算法容易受某些参数彫响，如阈值； vfh系列算法为局部避障规划算法，具有一定的局 限性.基于ros (robot operating

8、system机器人操作 系统)，针对vfh系列算法的阈值敏感问题，提出 了一种考虑机器人硕件特性、运动特性和目标环境的自适应阈值策略最后通过实验证明，采用该方法, 能够有效解决vfh系列算法的阈值敏感问题,使机器 人以一种较短的无碰撞平滑路径顺利到达目标.2算法设计2.1 vfh算法vfh及其系列算法思想是建立以移动机器人为 中心的极坐标系，将障碍物对机器人的影响量化为各 个角度上的极线障碍物强度值，在障碍物强度值低于 某个确定的阈值的角度范围内选择移动方向.vfh 系列算法的具体实现步骤如下：(1) 对激光雷达数据进行处理，保留机器人正前 方dnklx以内，block角度范围内的数据.(2)

9、 将block大小的扫描区域分成斤个扇区， 按正前方从左往右0到n-1进行编号.其中为正整 数，兀< block / resolution (激光雷达分辨率).(3) 求取每个扇区的障碍物强度值厲，构建向 量场直方图，障碍物强度值耳与障碍物距离出的计 算关系为：hi = ca-bdr)(1)其屮cv,a,b均为常数，ci、b满足a = bd賦.hi越大 表示障碍物强度越大.(4) 设距离阈值川对应的障碍物强度值为m, 对向量场直方图进行二值化，若h.<m则令比=0, 若h>m则令h严m .由此可得到可通行扇区直方 图.例如取 bloc=k27t, “ = 270, cv =

10、1(), 必址=4, b = 2.5, dth = 2得到如图1所示的向量场 直方图和可通行扇区直方图.3000呈 200010000图l vfh立方图fig.l vfh histogram对可通行扇区直方图中扇区宽度大于一定值的扇 区取中间值作为候选方向，对所有候选方向ki使用代 价函数进行代价计算，找到代价最小的仏作为运动方 向kb , kb的初始值为0,代价函数如下：(2)式中，(?,©为可选方向与目标方向的夹角；(c,b)为可选方向与机器人当前运动方向的夹角； a(c,z_/w)表示at选方向与上一次运动方向的夹 角.c为可选方向ki, kr为机器人当前运动方向， kb_ p

11、re为机器人上一次运动方向.“1,“2,“3均为常 数且满足“i > “2 + “3.2. 2 vfh系列算法的缺陷由2节可以看出，代价函数的作用是从可通行 扇区直方图得岀的诸多候选方向屮选取最优可通 行扇区直方图是方向选择的基础与前提，而可通行 扇区直方图的构造与阈值h的取值密切相关，因此 阈值，的选取对vfh系列算法至关重要.对图1中的向量场直方图分别取dlh = 2(m =3000 )和 dth = 1 ( m = 3750 ),得出可通 行扇区直方图如图2所示.100150200250用区图2可通行扇区直方图fig.2 the histogram of accessible se

12、ctor由图可知不同阈值dih对应的可通行扇区直方 图、扇区(空白部分)宽度和数量不一致.假设此时机 器人的目标方向与运动方向都住扇区100,150内.使用dtft = 2时，机器人将在下一刻进行转向， 提前避开障碍物，偏离目标方向行驶，此时机器人 可能无法到达目标位置.使用旳=1时，机器人将在下一刻继续向前行 驶，无法提前避开障碍物，若此时机器人行驶速度 较大则极有可能与障碍物碰撞.结合文献12、文献13与上述分析，阈值巾大 小对机器人避障规划结果有如下影响： 使用较大阈值岀力，机器人可以提前发现可行 通道和障碍物，及时调整运动策略；但容易使机器 人忽略一些可行通道，导致丧失到达目标点的能力

13、. 使用较小的阈值d川，机器人可以发现更多可 行方向，利于找到更接近目标的方向，但容易使机 器人陷入局部"死区”.因此，使用合理阈值策略是移动机器人避障规 划的关键.2. 3阈值策略分析针对2.2节提出的阈值敏感问题，一般使用以下 三种应对策略. 根据实际情况凭经验选择一个较为合理的阈值. 这是大多数研究者最常用的一种方法经验阈值在给 定情况下可用，但若机器人周围环境或者机器人运行 速度发生改变，则经验阈值就不再适用. 按一定步长对给定范围内的阈值逐个计算可行 方向，选取接近目标方向中阈值最大的可行方向作为 机器人行驶方向12.该策略存在两个问题，一是其始 终把可行方向接近目标方向作

14、为前提，当目标方向上 存在障碍物时，机器人无法找到可行方向.二是英算法 分析都是基于一种特殊的廊道坏境，限制了机器人偏 离目标行驶的可能性. 以目标距离作为最大阈值，当环境屮存在障碍 物时，若障碍物在目标方向上，则使用较大阈值，否 则使用较小阈值何文献13只对最大阈值设置进行 了简要描述而并未说明机器人具体运行过程中的调整 阈值.且使用该算法会出现航向剧变问题3.为使机器人口适应调整阈值，首先要确定阈值的 可调整范围，影响机器人阈值调整范围的主要因素有： 机器人硬件特性假设机器人中心点到边缘的最长距离为/?”，则 阈值需满足血> r-机器人使用的激光雷达传感器 具有一定的扫描范围，假设其

15、最大扫描距离为厶"亦和 最小扫描距离lniin ,则阈值需满足linux > dth > lttiin 机器人运动特性假设机器人运动的线速度大小为p，减速运动时 的最大加速度q，则其从减速运动到停止运动的缓冲 距离d为:d = （3）2a一般d> 5,故结合机器人硬件特性则有： linuxdih '久（d + rrf）（ 4 ）其中久为大于1的常数，称z为安全放大系数. 目标环境如图3所示环境，目标方向与机器人行驶方向一 致，冃标周围存在障碍物，虚线表示阈值范阖.当机器 人接近目标位置时，若要使机器人顺利到达目标其阈 值要逐渐减小，才能保证机器人向目标方向行

16、驶.图3 种目标环境示意图fig.3 schematic diagram for a target environment假设目标距离为旳，则阈值為应满足dtk<dr.2. 4 一种考虑全局的自适应阈值策略通过2.3节的分析，提出一种考虑机器人硬件特 性、运动特性和fi标环境的全局自适应阈值调整策 略，算法基本结构如下：algorithm 1 adaptive thresholdfunction: initial dth01： di h = dtlmicix02: if dihmictr && dthmcix>dr03: dth = dr04: end if05:

17、if dthmui> dr06： dih = dthmin07: end if0& return dihfunction: find kbcst01: repeat02: direction_counl<find_all_direction( dih)03: if direction_count>0 then04:kb <find_suitable_direction(direction_count)05：cost < f(dthi.kbi)06:add ( cltkkicost ) toset07: end if08:dih = dth/dth09： u

18、ntil dih< dlhmin10: if set.length > 111: i <get the minimum cost group number in set12: kbesi < scti .kh13: end if14: return kbcst 设置初始阈值，其中dtlunax和clthmin为满足阈 值条件的最大阈值和最小阈值.一般取d加x略小于 lnkix y 取 dihmin = a（z） + rn） 力为目标距离，设目标点坐标为（畑“ ygoai）, 机器人即时坐标为xtcnip, ytemp）,则有：dt = j（xgoal xtetnp +

19、（ygoal伽甲）（ 5 ） 以一定步长皿,对区间dthrnin , dlhs 内所有 dih = dths - i * dth | i = 0,1,2- ,求取可行方向, 若该阈值下的可行方向数不为零，则用式（2）计算 出代价最小的可行方向作为0八并将皿好代入式（6）计算代价值cos%,并将cu.b.cost）存入集合.j （d心 kbi） = codthnxix dth） + （&仞）（ 6）式中odthnxa - dthi）为阈值权重项，69为阈值权重 系数，做dm-弘加）越小表示阈值越大（安全）.q取 值与当前机器人的运动状态有关，机器人行驶速度 越大越容易发生碰撞，则取值越大

20、，表示与更接近目标相比机器人此时更注重安全性.（也- q称为方向权重项，其屮匕为目标方向, a（fe - kj越小表示転越接近目标方向. 若集合长度大于1,则取最小代价值对应的kb 为最终的参考行驶方向称z为层西，若集合长度为零 则表示使用区间加湖,d加内的所有阈值都找不到 可行方向，此时机器人不再朝前行驶，进行自转.理论上在所有dkin屮，取函数值最小的一组 即为最优解.但对区间内的所有阈值逐个遍历 并不利于算法实时性，尤其在激光雷达传感器数据更 新较慢且机器人运行速度较大时容易引起误差.因此, 当机器人行驶速度较快时可以适当增大步长 皿或 者当遍历到/（血，尬）小于某个值时，即认为该阈值

21、找出的方向接近目标方向，满足机器人当前运动的要 求，不再继续遍历文献12认为参考行驶方向与目标 方向之差小于45。表示接近目标方向./（血，也）小于 某个值的意义在于接近目标方向的判定与阈值有关， 例如60= 10时，dm = 3m和ch = m参考行驶方向接 近目标方向的判定标准相差20° .3实验为验证本文算法的有效性和可靠性，将本文算法 移植到在ubuntu 14.04搭载的ros上，在实际环境中 进行实验.实验平台是eai科技有限公司的双轮差动 驱动式机器人底盘dashgo d1.激光雷达传感器为 slamtec公司制造的rplidar a1.实物如图4所 示，其两个差动驱动

22、轮分布在机器人左右两侧，前后 各一个万向轮保持平衡.使用ros消息订阅和发布的 处理机制可以实时处理传感器数据、发布机器人运动 控制指令.机器人线速度和角速度都不为冬时,机器人 进行转弯，转弯圆弧半径为两者之商；角速度为零时, 机器人直线行驶：线速度为零时，机器人做零半径转 向运动；角速度线速度都为零时机器人停止运动.图4 eai移动机器人平台fig.4 eai mobile robot platform机器人底盘dashgo di的参数为：rn = 0.2m , vmax = 0.1m/ s , g>nax - 3.5%d / $ ;激光雷达的扫描 速率为5.5hz,扫描角度范围为03

23、60。，扫描距离 范围为0.15m 6m.实验首先在一种典型栅格环境下进行，设置机器 人起点为（0,0）,目标点为（5,2.4） .vfh算法各参 数 为：block = 270 , n = 270 , cv = 10 , d”心=4, b = 2.5.自适应阈值调整算法各参数为： 2 = 1.5 , dthmin 1/zz , cltluriax 3m , dth = 0.2/77 , = 10.机器人直线行速度设置为0.25m/5 ；转弯 行驶线速度设置为0.15/72/5;转弯半径统一设置为 0.5m.当机器人与目标距离小于0.3加时，认为机器 人顺利到达目标.实验环境及不同阈值策略机器

24、人 轨迹如图5所示，图中黑色为障碍物，边框为墙壁, 中间栅格由纸盒拼接而成.3 4.2 10 12tanjel o345 gdth*1m图5避障结果示意图（1）fig.5 result of obstacle avoidance （ 1）上图实验结果表明，使用自适应阈值策略，机 器人顺利到达目标位置.山 in时，机器人在离第 一个障碍物很近时，才进行转弯，从而陷入局部死 区，无法顺利到达目标点；dth = 2m和弘=3加时, 机器人没有顺利到达目标点.为验证阈值对机器人 的影响，绘制机器人起点和距离终点约0.7m某点的 直方图，如图6所示：如乂图6避障结果分析立方图fig.6 result o

25、f obstacle avoidance histogram图6左右两边强度值为满值的扇区角度为图4 所示机器人的支架.对图6的直方图分别取阈值为 m和3m ,得到如图7所示的可通行扇区直方图.祕砂呻呷力际如叫畑半业空迪g匹50 ico 1w 2co 2500501001502c0 2wdtk = 2m时，因采用固定半径转弯，使得机器人靠 近目标点时，不能以更短路径转向目标.为消除支柱影响，当可通行扇区直方图与图8 (左上)一致时，令4,=応，并在目标距离小于 阈值时，以目标距离的一半为机器人转弯半径.修改 后，在相同条件下重复图8和图5的实验，其结果 如图9和图10所示：urgcl图7避障结

26、果分析可通行扇区图fig.7 the histogram of accessible sector of result 机器人在起点时，幻约为160。对应扇区编号为 160,由图6、7可知，dth = im吋计算出的紘约为 135° : dth = 2m和必=3加时计算出血约为190° . 根据2.4代价计算公式，将心=160,力=10以及 上面三组值分别代入公式(6),得出：/(3,190) = 30、 .£(2,190) = 40、/(1,135) = 45,按照自适应阈值策 略，此吋选取血=3m对应的怎.终点附近障碍物强度 较高，如图6、图7中所描述的终点附

27、近某点，该点 目标角度约140° ,算法在该点时选取dth = m, b = 17于.为验证提出的自适应阈值策略对vfh系列算法 改进的有效性，在一种障碍物更少，目标点更易到达 的环境中，重复前文实验.设置机器人目标点坐标为 (0,0),终点坐标为(4,2),其不同阈值策略的避障 规划结果如图8所示.x(m)图9避障结果示意图(3)fig.9 result of obstacle avoidance (3)ditvmmdth=2mdthlex(<n)dth=2mdth=3<n刈g-1012345dth=3m图8避障结果示意图(2)fig.8 result of obsta

28、cle avoidance (2)由图8可知，该环境下dth = 2m , dth = 3m时机 器人都能有效避开障碍物，顺利到达目标点.血=im 时，机器人由于无法探知较远障碍物，并受机器人支 柱影响，导致其可通行扇区直方图大部分时候与图7 (左上)一致即恳为135° ,所以机器人总是朝正前 方行驶从而错过目标.使用自适应阈值策略和图10避障结呆示意图(4)fig0 result of obstacle avoidance (4)由上图结果可知，消除支柱影响后，机器人在 简单环境下都能顺利到达目标.在栅格坏境下， 血=1刃时，机器人顺利通过栅格并到达目标,但轨 迹较弯曲；使用自适应

29、阈值策略时，机器人则以较 短的平滑路径到达目标.而在其他阈值下机器人均 不能到达目标.为进一步验证自适应阈值策略的nj靠性与稳定 性，证明提出算法的优越性，在其他条件不变的情 况下，使图10屮的栅格环境的栅格通道更窄，上方 矩形障碍物更长.自适应阈值策略与各固定阈值策 略的避障规划结果如图11所示图12为使用自适应 阈值策略的实验过程中方向、阈值变化情况.图13朴)2mm)dlh-3m为分别使用文献12和文献13提出的阈值策略的机 器人行驶路径与方向变化情况.设置文献13策略中 的较大阈值为2.6m ,较小阈值为1.6加.图13中参考 行驶方向为零表示机器人没有找到参考行驶方向.4 is响qd

30、lh-lm畑图11避障结果示意图(5)fig. 11 result of obstacle avoidance (5)图12方向与阈值变化图fig.l 2 diagram of direction and threshold change2345 c0200 w wo boo 1000图13避障结果示意图(6)figj3 result of obstacle avoidance (6)图11 > 12表明，dth = m , clh = 2m时机器人陷 入局部死区，而无法顺利到达h标.dtf. = 3m ,机器人 错过了目标.自适应阈值策略下，前期血=3加，路径 与固定阈值3加时一致，机

31、器人顺利通过栅格，后期 阈值逐渐减小直至最小阈值，机器人顺利达到目标.图13上方两图说明，机器人不能保证每次都能 找到接近冃标方向的参考行驶方向，文献12的阈值 策略具有一定缺陷.当找不到参考行驶方向时，机器 人进行自转运动，如图13 (右上)所示，此吋机器 人的目标方向在周期性改变.图13下方两图表明， 机器人无法到达目标，结合图12可知，此时的较小 阈值1.6加还是不够小，导致机器人错过目标，说明 文献13的策略自适应程度不够，存在一定局限.进一步分析不同阈值顺利到达日标的路径情况. 消除支柱影响后的不同阈值策略顺利到达目标时的 路径点数如表1所示.路径点数为“-”表示机器人 未到达目标，

32、路径点数越少表示路径越短.表1算法效果对比表table 1 comparison of algorithm effect场墩自适应血=m= 2m皿=3m图9184192328227图1()228240表1表明，使用自适应阈值策略的机器人能以 更短的路径到达目标.4结束语针对vfh系列算法的阈值敏感问题，提出了一 种新的口适应阈值策略，分析了阈值及机器人硬件 特性和转弯策略对机器人避障规划结杲的影响.并 通过多次实验对提出算法与三种固定阈值、两种动 态阈值策略进行分析比较.结果证明在不同环境下， 使用提出的自适应阈值策略，机器人都能够有效解 决阈值敏感问题，并能以更短的无碰撞平滑路径顺 利到达目

33、标.参考文献：1 lumclsky v j, stepanov a a. path-planning strategics for a point mobile automaton moving amidst unknown obstacles of arbitrary shapej. algorithmica, 1987, 2(1-4):403.2 谭志斌，赵祚喜，赵汝祺，等.非360。探测范围四轮 导航车辆的平滑路径避障算法j.机器人，2013, 35(5) :527.3 khatib 0 real-time obstacle avoidance for manipulators and mobile robotsc/ ieee intcrnational conference on robotics and automation. proceedings. ieee, 2003:90|4j sharir, micha robot motion planning j | communications on pure & applied mathematics, 2010, 48(9): 1173.5 borenstcin j, koren y. the vect