一种局部动态环境下的避障算法.pdf

黧鬻：哿未。盏。教。未。蔷。j。黧，。老。戳篇器2oo3 年3 爿c o m p“t l“g r e c h n o l o g yn n dA u【o】a t l o n”“。文章编号：1 0 0 3 6 1 9 9(2 0 0 3)0 1 0 1 2 0 5一种局部动态环境下的避障算法章苏书，吴敏，曹卫华(中南大学信息科学与工程学院长沙4 1 0 0 8 3)摘要：提出一种基于传统v F H 避障算法的增强形式，称为V F H#算法。这种算法对v F H 算法第一层进行局部环境预测，重新确定静态动态栅格，为后几层的最优选择提供准确的参数。利用这种方法，机器人能在局部动态环境下选择较优的行进方向。关键词：v F H#算法；局部动态环境；避障；栅格中图分类号：T P 3 0 16文献标识码：AA no b s t a c l eA v o i d a n c eA l g o r i t h mi nI 脱a lD y n a m i cE n V i r o 姗e n t sZ H A N CS u s h u，W UM i n。C A OW c i _ h u a(s c h o o lo fI n f or I I l a t】o ns d e n c ea n dE 1 1 9 j n e e r i“g，c e n t r 出s o u t hu n i v e r s i y，c l l a“9 5 h a4】0 0 8 3)A b s t r a c t：T h i 8p 8 p。p r c s e n t sa ne n h a n c e m e n tb a s e do nt h ee a r l i e rV e n o rF i e l dH i s t o g r a ma l g o“t h mw h i c hi sc a l l e dV F H#a l g o“【h m I ti m p。o v e dt h en r s t1 8 y e ro fV F Ha l g o“t h mi“p ar【i c u l a r T h el o c a le n V ir o n m e n ti 8p r e d i c l e d，8 n ds t a t i ca n da c t l v ec e】l sa r ed e t e r m i n e do v e r8 9 a i ni nt h en l s tI a y e l o fV F Ha l g or“h m T h i 8p r o v i d e sm o r ep r e c i s ep 8 r a n l c【c r st o【h eo p t j I T l a ls e k cL i o ni nf o l l o w i“g1 8 y c r s B y“s i“gi 1 1 bw 8 yr o b o t sc a ns c l c c am o r e8 p p m p。i ac cs e e l i“g8“g l ei nl o c a ld y“a m i ce n V r o n m e n t s K e y w o r d s：V F H#a l g o r i l h m；1 0 c a ld y n a m i ce n v i r o n m e n t s；o b s l a c l ea V o i d a n c e；g r j d s1引言随着科技的发展，避障技术应用越来越广泛。例如，无人驾驶的汽车，盲人用的导航机器人，恶劣环境下的自主机器人导航系统等，都要求系统自动躲避障碍物。如果避障做得不好，会导致系统无法完成预定任务，损坏机器，甚至危及人身安全。提高避障技术成为科学工作者们越来越关注的问题。1 9 8 5 年，K 1 a f i b 提出了作用于机器人上假想力的思想，即最初的势力场法。障碍物表现为对机器人的斥力，目标表现为对机器人的引力。随后，B r o o k s 和A r k i n 采用势力场法进行移动机器人避障实验。这也是第一次通过处理真实传感数据来测试避障方法。但是，早期的势力场法不能在线生成机器人轨线，不适合机器人在动态环境下躲避障碍。几乎同时，卡内基梅降大学提出一种避障方法，即栅格法，是用一种栅格形状的物理模型(c e 一一t a i n t vG r i d)表示障碍出现的可能性。每个栅格包括一个确定值(c y)，表示一个障碍物存在于一个网格中的可能性。通过栅格法，机器人可以静态环境中实现准确导航，作出有效避障动作。然而，栅格法汁算量太大，不利于实时动态环境下的避障。8 0 年代末期B o r e n se e i n 和K o r e n 结合栅格法和势力场法提出了一种v F F 算法，又称为墟力场法。实验表明这种方法简单，可以使机器人在动态环境下快速、连续、光滑的运动。不过，v F F 贷：法存在陷阱区域，机器人在相近障碍物问不易找到路径，收稿日锅：2 0 慢一、I 一规基金项目：阿家“十五”8 6 3 计划项(2 0 0 l A “2 2 2 0 0)作者简介：章苏1(1 9 7 9 一)女，硕E 研究生，研究川目：模式识别与智能系统，瓢j 譬嚣。?i；：瓣。溅萋蠢巍熬&万方数据第2 2 卷第l 圳幸书等：一种局部动态环境下的潞障算?上1 3容易在障碍物前振荡，在狭窄通道中摆动。为了克服这些缺点1 9 9 1 年B o r c n 8 I e i n 提出了一种向量场直方图法，就是现在应用广泛的v F H 法。这种方法使科【器人可以在多障碍物环境中穿行，无拌动的穿过狭窄通道，r 具有V F F 方法的优点。由于这些优点，v F H 算法越来越受到人们的欢迎。随着广泛的应用，其缺点也暴露了出来。v F H 方法把机器人当作一个点来处理，没有考虑机器人的宽度、动力学和运动学特性，这使得机器人实际上较难完成v F H 算法计算出来的预定轨线。1 9 9 8 年，1 w a I l 和J o h a n n 对v F H 方法的这些缺点做出改进，提出v r H+方法”J。这种方法充分考虑了机器人宽度和轨线，机器人能逐步转向预定角度，满足了机器人动力运动学性能要求。但是，人们又发现v F H+方法只是一种纯局部避障算法，彳；可避免的存在一些局部特性，较难选择较优角度，容易在多个障碍物中迷失方向。于是，I w a n 和J o h a n n 在v F H+算法中加进预测，形成v F H*算法川，即预测以下几个周期机器人的位置和周围环境的关系，在几个可能角度之|1 i I 进行优化选择，使得机器人能在局部范围找到一个较优运动方向。使用v F H*算法，不仅保持了v 1 H+方法的优点，而且能选择出最优运动方向，避免机器人陷入陷目 区域。虽然v F H*算法比V F H+算法更完善，不再是种完全局部避障算法，但是它本质上仍是一种局部避障算法。并且，它对v F H+的前两层没有做出改进，没有考虑到周围障碍物的速度，它选择出一运动方向就有可能不是最优的，并且运用该算法时存在执行时间和预测准确性之间的矛盾。本文揭示了v F H*方法作为一种局部静态环境避障算法的局限性，然后针对这些局限性提出一种局部动态避障方法，称为v F H#算法。这种算法对周围环境进行了预测，使得机器人能找到最优最安全的运动方向。在本文第2 节详细阐述了v F H*算法的局限性，第3 节提出了v F H#避障算法，第4节详细陈述了v F H#算法，第5 节给出仿真结果，笫6 节给出结论。2 局部静态环境避障由于没有整个环境的信息数据，v F H*方法有时并不能做出最优的选择，即使是局部避障，L n 不能选择最优角度。以下例子说明了这一点。图l表示在机器人在一个甬道中移动，行进方向上有两个障碍物。黑体部分表示障杯物，周围的灰色部分表示v F H*算法定义的配置空闻。障碍物都沿一定速度移动，箭头表示其速度方向。机器人要在躲避障碍物的情况下通过甬道。图lv F I *算法不能找到最优角度的情况在图I 中，大虚线圈表示机器人触发避障行为的大致范围。机器人侦测到两个无危险方向，若机器人往左，则滑轨线A 行进，若机器人往右则沿轨线B 行进。由于v F H*算法没有考虑障碍物的速度，所以机器人通过预测会优化选择向有方向前进即轨线B，从而很容易陷入被障碍物堵住的尴尬境地。实际上，因为圆形障碍物与机器人速度方向同向，矩形障碍物向右移动，机器人向左才是此时的最佳选择。v F H*方法预测了机器人的轨线，并考虑了由此导致的结果，但是它并没有对环境进行预测，所以机器人在局部静态环境下沿预测轨线移动而导致的结果是较准确的，而在动态环境下就不一定准确了。因此，在对机器人运行轨线进行预测的同时也要预测周丽的局部环境，这样就可以进n 一步优化机器人的运行方向。|司时，v F H*算法要用到A*寻优算法来寻找机器人的较优运行方向。搜索节点越多，在静态环境中预测越准确，但是算法执行时间越长，不符合实时性要求；搜索节点越少，预测准确性降低算法执行时间越短。所以有必要降低v F H*算法第一层向量直方图的信息量，从而降低这个矛盾，使得预测比较准确。本文中提出的v F H#算法对环境进行预测，可以克服v F H*算法的局限性。它考虑了障碍物的速度，并预测机器人沿某方向前进所会遇到的现场环境，作为机器人选择最优行进方向的重要因蠹鑫瑟卷藏越：曩 万方数据】4计算技术与自动化2 3 年3 月_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _-_ _ _-_ _ _ _ _ _ _ _ _ _ _ _ _-_，_ _ _ _ _ _ _ _ _ _ _ _ _-_ _ H _-_ 一素。v F H#算法不再是一种局部静态环境下的避障算法，而是适用于局部动态环境的避障算法。3v F H#算法建立系统环境坐标系J 如图2 所示设机器人为R o b。矩形障碍物为0，三角形障碍物为o：，机器人在环境下的位姿表示为($，y，日)。y，y o，y D 分别是O，D 2 的当前速度，其矢量形式为(u，y)。u 表示速度大小，y 表示速度方向。先设定栅格的大小，然后将传感器检测到的障碍信息映射到环境坐标系中。根据传感器的检测角度，在机器人四周建立动态窗口，窗口中心可以简单的选为机器人的几何中心。(00)图2 局部环境坐标系图3V F H*算法从动态栅格到直方区间的映射图3 为根据v F H*算法做出的从动态栅格到直方区间的映射图。假设动态窗口如图3 所示，在动态窗口中分出n 个角度为a 的扇面，分表标号为 扇面(=o，1，2，n 1)，把栅格映射到所在扇面中。设栅格e e l l(i，i)在窗口坐标系中的坐标为(h)，由公式(1)可以计算出序号的值。k：，r(竺塑喇1(1 1比较而言，v F H#算法考虑了障碍物的速度和机器人的运动速度，将v F H*算法的第一层进行改进，使机器人对环境信息认识得更透彻，从而作出优化选择。v F H#算法根据机器人在该时刻的速度方向等因素选取被激活的栅格。如图2 所示，O z 的速度矢量关于机器人速度矢量方向的分量大于机器人速度值，D 2 位置的栅格可以认为静态栅格，没有被激活。而f)，的速度矢量和机器人速度矢量相对，D 将向着R o b 移动，所以从o，位置沿着其速度方向的一部分栅格应该被激活，根据v F H#算法画出的映射图如图4 所示。图4V F H#算法动态栅格到直方区间的映射这样，在算法第二层中机器人的预定方向也有了变化，在以后几层中做出的优化选择就能选到更优的机器人运行方向。4 静态栅格和动态栅格的确定V F H#算法中最关键的部分就是考虑环境因素确认栅格的动态和静态属性，即激活和不激活状态。下面详细介绍V F H#算法是怎么确定静态栅格和动态栅格。采用二维笛卡尔矩形栅格表示环境，每个矩形栅格有一个累积值c 矿，表示在此方位中存在障碍物的可信度。传感器不断快速采样环境，存在障碍物的栅格将会不断地被检测到，从而被激活，导致高的c y 值。机器人的速度矢量y，可以由机器人上几个周期发出的速度指令计算得出，或者根据机器人意图获得。机器人保存时刻前n 个周期的环境信息，n=l，2，根据前n 个周期的环境信息，可以计算出障碍物在t 时刻的速度。具体方法如下。区门|万方数据第2 2 卷第l 期章苏书等：一种局部动态环境下的避障算法假设现在n=l，并且f l 时刻机器人保存的环境信息如图3 所示，f 时刻所保存的环境信息如图5 所示，其中机器人的坐标值不变，环境坐标随机器人实际位置变化而变换。图5时刻存储在机器人中的环境信对照图3 和图5，环境信息中的栅格权值有偏移，取一l 时刻权值比较高的栅格集的中心作为障碍物盼重心，从图中可以找到两个这样的重心，分别称为，同样在#时刻图3 中取障碍物重心知l、Z。2，因为取的n 不大，所以即使障碍物速度比较大，重心偏移距离也不远。当两点距离小于某个常量时，便认为是同一障碍物。得到如，d。，障碍物D 1 的速度为：y 旷争幢其中y 的方向为指向磊的方向，r 为采样时问，障碍物0 2 的速度同样可得。当然，当存储的周期n 2 时，用最小二乘法或者其它预测方法可以获取障碍物的速度矢量。瓠。时r 嚣队幽纂当v o o 时V 旷V R不激活(3)V o V R D d i 8 t 激活V 7 0 V R D 三d i s t 不激活以机器人几何中心为原点，其速度矢量方向为y 轴正方向建立一个坐标系，设障碍物在该坐标系中的x、y 方向分量分别为V o、v o，障碍物在该坐标系中的位置为(z7 0，。)，d 新为活动窗口的半径。D 为障碍物和机器人之间的距离。根据式(3)来选择被激活的栅格。在每个被激活的栅格中(如图4 所示)，存在障碍物的权值可以由下式计算得到。m。，-(c。f)2(一6 也，f 2)(4)c f，表示被激活栅格的C y 值，口和6 都是正常量，d。表示c e 肌(i，i)到动态窗口中心的距离。对于每个扇面，栅格障碍密度可以表示为：联=二i m。，f(5)v F H#算法后几层的计算和v F H*一样，但是提供给后几层的数据不一样。由v F H#算法计算而得的栅格障碍密度函数和局部动态环境结合，为以后几层中选择最优提供了有利的参数，进而简化了v F H*方法中由于没有考虑动态环境而带来的多种角度的选择问题。v F H*算法只预测了机器人运动情况，而v F H#算法记录了环境的动态信息，同时对环境和机器人进行预测，使机器人选择最优行进角度。5 仿真(a)v F H+算法(b)v F H 岸算法图6 机器人避障仿真轨迹图采用v F H*算法和v F H#算法对自主型移动机器人避障部分进行仿真，得到如图6 所示甬道中机器人运动轨迹图。黑点表示机器人运行的轨迹，虚线组分别表示圆形和矩形障碍物移动的轨迹。由图6 可以看出，运用v F H*算法，机器人有多余动作，机器人容易和障碍物相撞。而运用V F H#算法，机器人可以找到最优的避障路径，避障轨迹也比较平滑，避障效果良好。实验表明，v F H#算法是一种适用于局部动态环境的避障方法，运行良好。6 结论V F H#算法对V F H*算法的第一层数据表示作了改进。V F H#算法不再是静态环境下避障算法，而是一种局部动态环境下的避障算法。o。谨甄)万方数据1 6计算技术自动化2 0 0 3 年3J】v F H#方法可以用于服务型机器人的避障，例如轮椅式机器人，还可以用于危险的动态环境下的机器人避障。参考文献f1 JB 删5 e m，YK r h eV c c t o rF f d dI l i 自t o g r a m _ 乜tu b s t a-c l eA v o i d a n c ef o rM 0 b l k b o 州J 1 E E EJ do fR o b o t i c 8帅dA u t o m 8 I l o n 1 9 9 1，7(3)：2 7 8 2 8 8 2 w 曲U l d c h，J o h 蚰nB o【e mV F【I 十：R d i 幽l eO b 日t c l eA v o i(k T l c en r a s lM o K l el o b o t s J P m c e e d i“萨o f I h e1 9 9 8儿：E EI n I P r n 小i o n 柚C o n k 洲R o【I t I t 沁dA u t h u n 1 9 9 8 5：l5 7 2 一l5 7 7 3 11 w nu l 血h，J o L n nB o 硼1 s I e【n V F H*：L o c d0 b s【地】oA v o i d 一曲I I hl(m k A h e u dv e n“衄t】o n lJ jP r 忡d 岫蚪o f 由eI E E EI n t e r n I l I 出C l f；r 呲，nR d】o I n dm I t 删“o n 2 0 0 0 4：2 5 0 5 2 5 1 14 马兆表，袁曾任基于栅格方法的话动机器人实时导航和避障 J 机器人，1 9 9 6，1 8(6)：3“一3 4 8 万方数据一种局部动态环境下的避障算法一种局部动态环境下的避障算法作者：章苏书，吴敏，曹卫华作者单位：中南大学信息科学与工程学院,长沙,410083刊名：计算技术与自动化英文刊名：COMPUTING TECHNOLOGY AND AUTOMATION年，卷(期)：2003,22(1)被引用次数：6次 参考文献(4条)参考文献(4条)1.马兆表;袁曾任 基于栅格方法的移动机器人实时导航和避障 1996(06)2.Iwan Ulrich;Johann Borenstein VFH*:Local Obstacle Avoidance with Look-Ahead Verification 20003.Wan Ulrich;Johann Borenstein VFH+:Reliable Obstacle Avoidance for Fast Mobile Robots 19984.J Borenstein;Y Koren The Vector Field Histogram-Fast Obstacle Avoidance for Mobile Robots外文期刊 1991(03)本文读者也读过(7条)本文读者也读过(7条)1.李冠.吴卫国 自主移动式机器人对未知环境的避障研究会议论文-19982.韩庆珏.刘少军.金燕.HAN Qing-jue.LIU Shao-jun.JIN Yan 海底采矿移动机器人的避障研究期刊论文-机电工程技术2006,35(1)3.廖小翔.胡旭东.武传宇 基于高斯概率分布场的VFH避障方法研究期刊论文-机械设计与研究2005,21(1)4.李吉功.冯宜伟.郭戈 基于栅格地图的通用机器人避障算法会议论文-20065.吴海彬.朱世强.马翔 自主吸尘机器人的一种避障算法期刊论文-机床与液压2001,1(1)6.张幼明.尹怡欣.ZHANG You-ming.YIN Yi-xin 基于非线性函数的移动机器人模糊避障算法期刊论文-计算机应用研究2007,24(11)7.张捍东.王丽华.岑豫皖.ZHANG Han-dong.WANG Li-hua.CEN Yu-wan 基于势场的移动机器人自主导航研究综述期刊论文-自动化与仪表2007,22(4)引证文献(6条)引证文献(6条)1.宋颖丽.李彩虹 移动机器人漫游行为的研究期刊论文-山东理工大学学报（自然科学版）2010(4)2.张捍东.王丽华.岑豫皖 基于势场的移动机器人自主导航研究综述期刊论文-自动化与仪表 2007(4)3.祖丽楠.田彦涛.梅昊 大规模多移动机器人合作任务的分布自主协作系统期刊论文-机器人 2006(5)4.廖小翔.胡旭东.武传宇 基于高斯概率分布场的VFH避障方法研究期刊论文-机械设计与研究 2005(1)5.龚德文 深海集矿机行驶智能控制研究学位论文硕士 20056.姜延柏 吸尘机器人系统的开发与避障问题的研究学位论文硕士 2005 本文链接：http:/