（机械电子工程专业论文）基于超声波传感器的移动机器人避障算法研究.pdf

淅江理t 大学坝l 学位论文 文摘 近年来，移动机器人的研究己成为许多人关注的焦点。机器人的研究领域已经不仅仅 限于军用领域中，许多庸用丁军用机器人一卜的成功技术已经使用于l 毛用的机器人中，如环 境建模和电子地图、机器人定位、避障、自主导航等先进技术。 对丁移动机器人来说，机器入导航是实现机器人智能化最重要的核心技术，它主要包 括：环境信息提取、环境建模功能、避障算法实现以及实现自动导航的路径规划算法功能 组成。所谓移动机器人导航系统研究其实也就是针对所处环境选择合适的传感器，然后根 据传感器信息建立合适的环境模型，最后建立面向该模型的避障和路径规划算法。然而， 由于诸如传感器有限的“感知”范州、传感器噪声干扰、机器人车轮打滑、动态的环境、 实时性等“不确定”吲素对机器人学习和使用准确的环境模型带来了约束，所以就目前而 言，要想获得准确的环境模型还是一个有待解决和完善的问题。 环境信息的描述是实现机器人自主式导航的算法基础。现在对环境信息的建模有多 种，但其中比较成功的一种方法就是南密歇根大学j b o r e i l s t e i n 和y k o r e n 提出的矢量场直方图 ( v e c t o rf i e l dh i s t o g m m ，v f h ) 。不过，随着该算法的广泛应用，其缺点也暴露出来。v f h 方法未能很好地解决栅格方法存在的环境分辨率和环境信息存储量的矛盾，它把机器人当 作个点来处理，没有考虑机器人的宽度、动力学和运动学特性，这使得机器人实际上较 难完成v f h 算法计算出来的预定轨线，所以后来又有了它的改进算法v f h + 和v f h + 。然 而，不论是v f h 最老的舨本，还是最新的改进版本，在第一层中都是以机器人能够保持连 续运动为前提并认为超声波的能量土要集中在声纳的轴线上，只考虑声纳中心轴上的栅格 单元。本论文通过实验发现，这种声纳模型由丁过丁简化，也带来了环境信息提取和利用 的一些问题。为了解决这个问题，本论文充分考虑声纳传播的能量分布特性，并结合高斯 概率分布场理论( g a u s s i a np d f ) ，对v f h 算法的第一层做了改进，并在p i o n e e ri i 移动机 器人硬件平台上测试了该避障导航算法的有效性以及相对丁- 最初的v f h 算法的优越性。 关键词：环境信息提取，环境建模型，避障算法，路径规划算法，“不确定”冈素，矢量场 直方图，声纳模型，高斯概率分布场理论 浙江胖t 大学坝忙学位沦史 r e s e a r c ho n0 b s t a c l ea v o i d a n c e a l g o r i t h mf o rm o b i l er o b o tb yu l t r a s o n i cs e n s o r s a b s t r a c t p r e s e m l y ， r e s e a r c ho nm o b l i er o b o th a sb e e no n eo tt h et 0 c u s e s 。i h er e s e a r c h1 sn o1 0 n g e r 1 i m i t e di nm i l h a r y 丘e l d m a n ya d v a n c e dt e c h o l o g i e s ，l i k ee n v i r o n m e n tc o l l e c t i o na n dm 印p i n g 、 m b o tl o c a l i z a t i o n 、o b s t a c i ea v o i d a n c ea n da u t o n o i r l o u s1 1 a v i g a t i o n ，w h i c hh a db e e nu s e di nt h e m i l i t a r yr o b o th a v es u c c e s s 如l l yb e e nt r a n s 凫r r e dt ot h e 行e l do f n o n i l a lm o b i l er o b o t a u t o n o r n 。u sn a v 培a t i o ni st h ek e yt e c l m 0 1 0 9 yt oi m p l e m e n ti n t e h i g e n c eo fm o b i l er o b o ti n t h ef i e l do fm o b i l er o b o t i ti n c l u d e sf o u r 辄b t e c h n o l o g i e s ，t h e ya r ee n v n m e n ti n f o r m a t i o n c o l l e c t i o n 、e n v i o n m e mm o d e l i “g 、o b s t a c l ea v o i d a n c ea k o r i t h ma n dp a t hp h n n i n g a 】g o m h mt o p e r f o r mt h ew h o l ea m o n o m o u sn a v i g a t i o nm i s s i o ni nas e l l s e ，m o b i l er o b o t 衄v i g a t i o nh a st h r e e s t e p st oi i i l p l e m e mt h em i s s i o n f 让s t l y ，i tc o l l e c t se n v l r o n m e n ti 1 1 f o r m a t i o nu s i n ga p p r o p r i a t e s e n s o r s t h e n ，证u s e se n v i r o n m e n tm o d e l i n gt od e p i c tt h ee n v i r o n m e n t f i n a l l yi td e s i g n sf e a s i b l e o b s t a c l ea v o i d a n c ea n dp a t hp l a r m i n ga l g o r i t h m st oc o 玎m l i tt h em i s s i o n h o w e v e r ， s o m e u n c e n a i n t i e sl i k es e n s o r sp e r c 印t u a ll i m i t a t i o n 、s e n s o rn o i s e 、d r mo rs l i p p a g e 、e n v i r o n m e n t a l d y n a m i c sa n dr e a l - t i m er e q u i r e m e n t sb r i l 培m a yr e s t r i c t i o n so nt h ee n v i r o n m e n tc 0 1 l e c t i o na n d m o d e l i n g i nl i 曲to ft h ec u r r e n ts t a t eo fa n ，n ss t i l lv e r yh a r dt oe s t a b l i s hac o m p a r a t i v e l y a c c u r a t ee n v i r o r l 【r l e n tt n o d e l e n v i r o n m e n tm o d e l m gi st h ek e yp a ni na u t o n o m o u sn a v 远a t i o n t h o u g h ，t h e r ea r em a n y e n v i r o n i n e mm o d e l i t 培m e t h o d s 妯t h en a v i g a t i o nf i e l d ，o n l yf e wa r ev i a b l ea n dp o p u l a r i z e d ，a n d v f h ( v e c t o rf i e l dh i s t o 乒a m ) o b s t a c l ea v o i d a n c em e t h o dw h i c hw a sp u tf o n v a r d b yj b o r e n s t e i n a n dy k o r e n 丘o mt h eu n i v e r s n yo fm i c h 瞎a na r eo n eo ft h e m b u tw i t ht h ep o p u l a r i z a t i o no f v f h ，赴sh m i t a t i o n sa r ee x p o s e d i td o e sn o ts o l v et kc o n t r a d i c t i o nb e t w e e n 耵i dr e s o l u t i o na n d e n v i r o n m e n ti n f o r m a t i o ns t o r a g e ，n1 0 0 k sr o b o ta sap o i n tw i t h o u tt a k i i l gr o b o ts i z e 、d y n a m i c s a n dk i n e m a t i c s 访t oa c c o u n t ，w h i c ha sar e s u l tm a k ei th a r dt of o l i o wt h ep a t hc a l c u l a t e db vv f h a k o 血l l i t l ，s ol a t e rc o m e st h ev f h + a n dv f h + a k o r i t l l i i l s h o w e v e ln e t h e rt h eo r i g i n a la l g o r n h mv f ho ri t sd e r i v a t i v ea k o r h h m sv f h + a 蚰dv f h + ， 浙江埋t 人学碰! 十学协沧文 t h e ya l la s s u m er o b o tk c c pm o v i n ga n dh db er e a s o n a b l et oc o n s i d e r 伊i dc e l l sj u s to nt h es o 眦r a x i si 1 1 l i g h to fs o n a re n e 唱yd i s t n b u t i o nf e a t u r e b u tw ef i n di t s n o ta sg o o da sw h a tt h e y e x p e c t e d t h e i ra s s u m p t l o nh a sb e e np r o v e dt oh a v ep r o b k m sw j t he n v i r o n m e n ti n f o f m a t i o n c o l l e c t i o na n dm o d e l i n gmo u re x p e r j n 】e n t sd u et ot h e i rt o om u c hs i m p l es o n a rm o d e l s t os o l v e t h i sp r o b i e m ，w ep r o p o s ea ne n h a n c e dv f h a l g o r i t h m ，c a l l e dp r o b a b i l | s t i cv e c t o r 羁e l dh i s t o 舀a m ， w h i c ht a k e st h ea d v a n t a g eo ft h eg a u s s i a np r o b a b i l i t yd i s t r i b u t i o nf u n c t i o “g a u s s i a np _ d f ) t h e o r yt oi m p t o v et h e 由s tl a y e ro f o f 罾na lv f ha l g o r i t h m so ri l sd e r i v a t i v e s w ei m p l e m e n tt h e p v f ho np i o n e e r1 1d x er o b o tt ot e s tn sv a l i d i t ya n d s u p e r i o r n yo v e rt h e o r i g i n a lv f h a 培o r n h 玎1 so r 王t sd e r i v a t i v e st 1 1 r o u g hc o m p a r i s o n s 抽m a n ye x p e r i i l l e m s k e yw o r d s ：e n v i r o n m e n ti n f o r i m t i o nc o l l e c t i o n ；e n v i r o m e n tm o d e l i n g ；o b s t a c l ea v o i d a n c e a l g o r i t h m ；p a mp h n n i ”ga k o r i t 】1 m ；u n c e r t a i n t i e s ；v e c t o rf i e l d h i s t o g r a m ；s o n a rm o d e l i n g ； g a u s s i a np r o b a b i l l t yd i s t r i b u t i o n 血n c t i o nt h e o r y 浙江埋t 人学碰“学何论文 1 1 移动机器人研究背景 第一章绪论 移动机器人的研究足机器人的重要研究领域。斯坦福研究院( s r j ) 的n 妇n i l s s e n 和 c h a r l e sr o s e n 等人，在1 9 9 6 年至1 9 7 2 年中研制出了s h a k e y 的自主移动机嚣人。目的是研 究应用人丁智能技术，在复杂环境下机器人系统的自主推理、规划汞1 控制。与此同时，最 早的操作步行机器人也研制成功，从i 丽开始了机器人步行机构方面的研究，以解决机器 人在不平整地域内的运动问题，设计并研制了多足步行机器人。其中最著名的足名为 g e n e r 鑫ie l e c t 市锄a d r u p e d 的步行机器人。7 0 年代末，随着机器人的应用和传感技术的发展， 移动机器人的研究义出现了新的高潮，特别是在8 0 年代中期，设计和制造机器人的浪潮席 卷全世界，大批世界著名公司歹| 始研制移动机器入平台，这些移动机器入主要作为大学 实验室及研究结构的移动机器人平台，从而促进了移动机器人学多种研究方向的出现。到 了9 0 年代，机器人研究进入低潮，之后复苏和强劲的发展势头。与以前的机器人研究相比， 现在的机器人研究有两个特点：足对机器人智能的定位有了更加符合实际的标准，也就是 不要求机器人具有像人类一样的高智能，而只是要求机器人在某种程度上具有自主处理问 题的能力：另一个特点是许多新技术及控制方法，比如神经网络、传感器融合、虚拟现实、 高速度的并行处理机等被引入到机器人研究中，研究重点的转变使机器人研究走向了健康 而平衡的发展道路，并不断取得新的研究成果。由于机器人应用从制造业向非制造业的扩 展，以及自主移动机器人在诸如野外作业、深海探测、以及人类本身所不能进入的有毒或 高温环境的作业中有着极其广泛的应用前景，因此近年来机器人研究在多方面都已取得 了很大的进展，研究的成果必将成为各行各业提高生产力的强有力的t 具。移动机器人是 一个集环境感知、动态决策与规划、行为控制与执行等多利t 功能丁一体的综合系统。对其 研究涉及到规划与导航、目标识别与定位、机器视觉、多种传感器信息处理与融合，以及 系统集成等关键技术，而每一项关键技术的解决又涉及到更多的技术细节问题。因此对移 动机器人的研究涉及许多方面1 】| 2 1 。 目前美丽在机器人研究麻用方面处于世界领先水平，“机器人之父”恩格尔伯格创建 的t r c 公司生产的h e l p m a t e 机器人是一种室内智能轮式移动机器人。陔机器人由移动系 统、运动控制器及大量的传感器组成，可在医院内以o 7 米秒左右的速度自主运动于病房 浙江理t 大学锄 学位论文 硐i 医务审之问，分发药品和换洗的农物等。机器人中预装r 医院地幽，在确定h 的地后， 机器人利用推测航行法自土地沿走廊导航。该机器人利用结构光视觉传感器和全方位超卢 波传感器探测静j r 或运动的物体，并对航线进行修正。它的全方位触觉传感器可以 呆证机 器人不会与人或其他物体相碰撞。车轮上的轴编码器可以测量其行驶的距离，实现粗略定 位。在走廊中，机器人u j 以利用墙角等建筑结构，确定自身的位置。在病虏中，机器人可 利用传感器感知灭花板上的人工路标以实现定位口j 。 在机器人的开发应用研究中，值得一提的另一个国家是日本。日本研制机器人的时问 比美国大约晚1 0 年。但日本产业界和政府高度重视机器人的发展，且于1 9 7 1 年( 比美国早 4 年) 成市了日本工业机器人协会。此后，日本t 业机器入技术得到飞速发展，并在年产量 和装机台数上迅速赶卜并大大超过美国，跃居世界首位5 1 。 在国内，清华t h m r v 型智能车是清华大学计算机系智能技术与系统国家重点实验室 研制的新一代移动机器人【6 】。该机器人具有面向高速公路和般道路的功能，其车体采用7 座厢式车改装，装备有彩色摄像机和激光测距仪组成的道路与障碍物检测系统，以及由 g p s 、电子罗盘矛光码盘构成的组合导航与定位系统等。两套计算机系统分别进行视觉图 像处理，完成信息融合、路径规划、行为与决策控制等功能。四台i p c 工控机分别完成激 光测距信息处理、定位信息处理、通讯管理、驾驶控制等功能。高速公路上，其设计车速 为8 0 k m t h ，。般道路上，车速为2 0k “h 。海尔哈尔滨t 业大学机器人技术公司推出的d y 1 型导游服务机器人”l ，由伺服驱动系统，多传感器信息，避障及路径规划系统，语音识别 及语音合成系统组成。可在一定环境下自主行走，并能识别出障碍物是人还是路障，做出 不同的反应。中国科学院自动化所研制的“c a s i a 1 ”智能运动机器人。该机器人的基本 结构包括传感器、控制器和运动结构，传感器由位于机器人底层的十六个触觉红外传感器、 位于机器人中问两层的十六个超声传感器和十六个红外传感器、位于机器人顶部的c c d 传 感器等组成。但是从总体上看，我国在智能机器人方面地研究还比较薄弱。另外，在机器 人的应用方面，我国就显得更为落后。国内自行研制的机器人当中，能真正应用丁生产部 门并具有较高可靠性与良好工作性能的并不多嘲。 1 。2 本论文研究的主要内容 在自主机器人导航中，地图绘制的就是使用机器人传感器从实际环境中提取信息并将 2 浙江碰t 大学碗1 学何| 史 其转换为合适的环境内在表现的一种过程。地图的准确性土理取决丁机器人所在的真实环 境和和地图的一致性程度，冈f 町估测并不断更新机器人的位置成为地斟创建的个重要问 题。假设机器人对环境已有了一定地描绘，同时匀l 道自己的当前位置以及它的目标位置， 那么它必须要搜索整个地图，找出一条在特定标准f 足最优的、能够避丌静态或动态障碍 物的、而目足够宽的能够止机器人通过的路杼= 。为了探索、研究和解决以上的这些在机器 人导航中的基本问题，本课题利用栅格地图易丁表现和构建的特点，结合基丁高斯概率分 布传感器模塑和贝叶斯刷新公式来构建基丁 用枥格的环境地图；然后再利用高斯概率分 布传感器模型得到的局部障碍物分柿，用占用栅格信息作为v f h 算法的数据来源，以改进 v f h 对环境信息反映不足的缺点，实现新的快速局部避障方法p v f h 。 本论文的内容将如下安排： 第一章阐述本文的研究背景，提出研究任务和全文的结构安排： 第二章叙述了移动机器人结构特点并详细分析了当前机器人导航系统中避障 定位、路径规划等基本问题； 第三章分析了移动机器人导航避障系统中常用的超声传感器和超卢测距原理 了在超声测距中所产生的问题以及解决这些问题的方法； 电子地图、 并归纳总结 第四章详细分析了当前比较热门的v f h 避障算法，指出了该算法的缺陷，并洋细阐述了衍 生算法v f h + 和v 脚+ 对该算法所做的改进； 第五章针对v f h 避障算法以及衍生算法v f h + 和v f h 在环境信息提取和利用方面所存在 的缺陷，提出了基- 丁高斯概率分布理论的p v f h 机器人避障新方法； 第六章实验验证p v f h 算法的有效性和优越性： 第七章对本研究工作做了全面的总结，并提出今后继续丌展研究的方向。 第二章移动机器人结构和导航系统研究进展 2 1 移动机器人的典型结构 2 1 。1 移动机器人的一般硬件结构 图2 一l 机器人典型结构 根据研制的目的不同，智能机器人的系统构成不尽一致，比较完整的典型结构可如图 2 - l 所示。由图可见，智能机器人的系统综合运用了多种智能控制技术，其目标是建立起一 个“人”的模型吼 4 2 1 2 移动机器人的软件结构 移动机器人的软件系统如图2 2 所示，实际卜就是人t 智能主要技术对于机器人的综 合运用。 知以库足机器人软什系统的核心。人l 一智能问题中所谓知识，通常是指描述各种客观 环境、对象、条件，组纵成一定结构的“数据”，以及解释、运用这些“数据”，反映有关 领域客观规律或主观判断过程的推理机制”。 图2 - 2 智能机器人的软件系统 2 2 移动机器人的导航系统研究进展 移动机器人导航系统研究主要包括运动机器人避障、机器人电子地图、机器人定位 和路径规划等研究。 2 2 1 移动机器人的避障方法 在状取传感器信息建立环境模型和环境地图之后，要实现自主机器人导航系统，一个 很重要的功能就足避障。它是路径规划的一个莺要部分。在移动机器人路径规划中，如果 机器人发现有障碍物突然出现在原先规划好的路径上，那么机器人如何就应该能够绕过这 个障碣物，并且在绕过之j 五能够回到原来规划的那条路径上? 这个问题就是路径规划中所 要解决的局部避障( 或局部规划) 的问题。对于这个十分重要的问题，国内外学者们已经做了 大量的研究工作，并提出了许多比较可行的方法，比如边缘探测、确信栅法以及潜势场等 浙江删大学坝l 学位| 仑立 方法，但这些方法往往不能实现快速的避障，机器人必须要在障碍物前面稍停j 【刻，等收 集剑足够的环境信息之后，才能作出避障的决策利动作，所以后来义有厂基丁势场思想的 虚力场方法和基丁确信栅格的矢最场直方图方法。 2 2 1 1 边缘检测方法 边缘检测方法是当前一种比较流行的移动机器人避障方法，该方法主要通过探测障碍 物的两个垂直边缘的位置来达到饶过它们避开该障碍物的丑的。这种方法的缺陷就是机器 人不得不在障碍物前方停留片刻以收集一定的障碍物信息，这样就使得机器人的运动不能 保持比较好的连贯性。对于使用超声传感器的机器人避障系统，还存在障碍物方向不确定 性、超声噪声干扰或串扰以及已经镜而反射等缺陷，这些问题会在后面的章节加以概括和 分析】 1 2 1 。 2 2 1 。2 虚拟力场法 v f f 方法使用二维的笛卡尔的南方图栅格( h i s t o g r a mg r i d ) 来表示障碍物环境，这跟 c m u ( c a m e g i em e l l o nu n i v e r s n y ) 的确信栅格( c e r t a i n t yg r i d c v ) 有点相似，不同之处在丁 构建和刷新地图的方式不一样。c m u 的c v 方法，用一个简单的概率模型反映障碍物分布 情况，受影响的栅格单元只在中心轴上。虽然要计算的栅格单元已经比较少，但这对丁一 般的板上电脑( o n - b o a r dc o m p u t e r ) ，还是有点吃不消。在这一点上，v f f 方法仅考虑位于中 心轴与传感器相距为声纳返回距离的一个栅格单元，由丁：设置移动机器人是连续运动着的， 所以它仍然能够较好地描绘障碍物的分布情况，并且在计算效率上较c v 有进一步的提高。 v f f 方法足在势场法( p o t e n t i a ln e i dm e t h o d ，p f m ) 的基础上建立起柬的。该方法认为障 碍物会对机器人施加一定虚拟的排斥力( v i n u a lr e p u l s i v ef o r c e ) ，目标对机器人也会产生一定 的吸引力，这两个力的合力决定机器人的速度和方向。v f f 方法由于p f m 先天的缺陷，在 应用中存在着下面的问题：由丁p f m 会有局部极值，当机器人进入了u 型障碍物内部时， 就会陷在里面：当机器人位丁两个比较靠近的障碍物前面时，如果目标对机器人的吸引力 不足于克服两个障碍对它的排斥力，那么机器人就不能通过这两个障碍物中问的过道；当 机器人比较靠近障碍物或出在一条比较狭窄的过道中时，它会有一定的振荡或摆动的问题。 这些问题往往需要通过全局规划器( g l o b a lp a t hp l a n n e r ) 来解决，也就是说，当机器人受陷时， 6 浙江挫t 大学硕j 学位 殳 用来测试受i 辊的监视程序( p a t hm o n l t o r ) ，激活全j n j 规划程序，使其重新规划路径，这样机 器人才有可能从“陷阱”中脱离出来。 2 2 1 3v f h 避障方法 v f h 方法正是为r 解决v f f 方法存在的一些问题而被提出来的。它采用h i s t o g r a m g r i d 、p o h r h i s t o g r a m 以及v f ha k o r i t h m 三个阶段了来实现数据缩减( d a t ar e d u c t i o n ) 。在 第一阶段，h i s t o 窟r a mg r i d 阶段，通过传感器返叫的采样数据，实时地刷新二维的筒卡尔直 方图栅格( h i s t o 口a mg r i d ) ，这样可以得剑比较全面的环境中的障碍物信息，这环节与v f f 年h 似；在第一阶段，p o i a r h i s t o g r a m 阶段，将整张直方图栅格裂解为一定数目的扇区( s e c t o l ) ， 然后计算再自扇区的极毕标障碍物密度：在第三阶段，v f ha l g o r h h m 阶段，v f h 算法根据 p o d 的分柿情况，计算出机器人运动速度和方向” 【“ 。 v f h 使用上面的三个阶段来缩减数据，克服了由丁v f f 将所有信息爪缩为单个合力所 造成的j 口j 部障碍物有价值信息丢失的缺陷，因此在反映环境的准确性上相比v f f 有所提高， 但是由于v f h 和v f f 同样是局部路径规划方法，所以它不可能找到最优的规划路径f 最优 路径只有在全部环境信息给定时才能找到) ，另外，机器人有可能会陷在“死胡同”m 不来。 这些问题也只能通过全局规划器来解决 1 3 】。 2 2 2 移动机器人电子地图 为了能够在室内环境中执行复杂的任务，自主机器人必须能够获取和维护他们的环境 模型。而获取环境模型的问题很难，目前尚未解决。下面的冈素给机器人学习和使用准确 的地图模型的能力带来了实际的制约作用： 1 ) 物理量传感的局限。传感器通常不能直接测到我们所需要的相关的物理量，比如，摄象 头仅仅测量颜色、亮度和光的饱和度，而对于导航，摄象头则更应该侧重于诸如“机器 人前面有个门”之类的论断。 2 ) 感知范嗣的局限性。人多数传感器( 超声传感器、摄象头c c d ) 的感知范围只局限于一个 i 嗣绕在机器人四周的小范围。为i r 获取全局的信息，机器人不得不积极地探索整个环境。 3 ) 传感器噪声。传感器的测量数据常常混杂着噪声，通常这些噪声的分布都是无法可知的。 4 ) 漂移打滑。机器人运行足准确的，不幸的是机器人运动的路程误差会随着时间累积起 来。即便最小的旋转误差如果f ：加以补偿很u j 能剑后面会带来巨大的影响。 7 5 ) 运动的复杂性。机器人的环境是复杂的，而且是动态的，这使得在理论上小可能维持确 切的实际模型并做出预测。 6 1 实时性的要求。考虑时问的1 1 u j 题，通常需要内存的模型必须简单并容易得到。当机器人 的动作足实时的时候，从复杂审内环境建立的确切模型很可能会不准确。 当前的研究已经产生室内机器人环境建模的两个典型的模型，一个是基于栅格的板模 型，另一个是拓扑模j 以m o r a v e c e 1 f e s 和b o r e n s t e 耐k o r e n 为代表的基于栅格的方法， 通过均匀分稚的栅格来表示环境，符个栅格单元( 见图2 3 曲可能表缸e 障碍物存环境中对应区 域的具体位置：以k u i p e r s 等人为代表的拓扑的方法，通过图表( g r a p h ) 的形式来表现机 器人环境【”1 。图的结点f 见图2 3 b ) 对应于显著的位置、地点或标记( 如门道) 。图与图 的联接通过圆弧来实现( 如果图与图之间存在一条路径的活) 。这两科r 方法建立的机器人地 图均有备臼的优势和弱势。基r 栅格构建的地图在大环境下也容易维持，该方法在个全 局坐标系中使相对丁机器入儿何位置的不同位置点能够明朗化歼来。路程信息、机器人读 取的传感器信息以及机器人本身的位置不断地被刷新，因此，基于栅格的方法，通常需要 使用巨大的传感器数据信息来确定机器人的位置，在一定程度上，移动机器人的位置可以 被准确地跟踪，传感器所测量的不同位置能够被明朗化。当机器人在不同位置返回的传感 器数据相同时，对于基于栅格的地图并不会有什么模棱两可的情况，然而对于基于拓扑的 地图就会产生“歧义”，冈为该方法通过航标或相似的方法来确定其机器人自身的位置。例 如，机器人经过两个相似的地方时基丁拓扑的地图通常很难决定这两点是否相同。另外， 传感器的读入在很大程度上依赖于机器人的“视角”，拓扑方法可能无法辨识附近物体的儿 何外形，这就使得拓扑方法很难构建大地图，特别是当传感器信息不是十分明确的情况下。 在另一方面，栅格方法常常会遇到巨大的时问和空间复杂性的问题，这是因为栅格分辨率 必须足够到能够捕捉环境的每一个细节。而用托扑柬表示的地图的最大优点就在于其紧密 关联性。拓扑方法紧密性，主要体现在允许快速规划，它使的用符号语言来构造界面变得 容易，它能够提供更人性化的界而，比如，给出命令“去找门a ”，机器人就能按照这个指 令找到门a 。由于拓扑方法不需要决定机器人的儿何位置，因此它更好地减少漂移和打滑 的现象，然f 面这些问题在栅格方法中必须被不断地监视和补偿。这两种建立机器入环境地 图的最基本方法的优点和缺点对比如表2 一l 所示。 ；， 塑堡些二奎堂塑= ：! = 兰壁堡兰 一 基于栅格的地图 基丁拓扑的地图 奔易构建，表现和维护( 优点)允影| ：高效规划，底空问复杂性，分辨率丰要取 决与环境的复杂性( 优点) 能够识别的位旯明确，不需要获得机器人确切的位置( 优点) | 1 视点相刈独立( 优点) 计算最短路径比较容易( 优点)可以使用人性化语苦从而界面友好，符号化解 决方案实现方便( 优点) 规划效率低，耗空间，分辨率不取决在大环境下，如果传感器信息不明确，这个地 丁环境的复杂性( 缺点) 图就较难构建和维护( 缺点) 需要确定机器人的准确位置( 缺点)位置辨识较难，对机器人所在视点比较敏感( 缺 点) 界面不友好，符号化解决方案不容易 可能不能产生最优规划路径( 缺点) 实现( 缺点) 表2 一l 栅格地图与拓扑地图的比较 a 。 b 图2 - 3 基于栅格的拓扑地图的形成过程 c s e b a s t i a nt h m n 和a m ob u c k e n 合并这两种构建机器人环境地图的方法来取得全局最 优地图，即基于栅格的拓扑地图( 见图2 3 c ) 。该方法使栅格地图和拓扑地图优势互补。为了构 建基于栅格的机器入电子地图，传感器值通过人神经嘲络被诠释，并对麻刘栅格，与用的 可能性大小。多个传感器诠释通过贝叶斯公式按时间求积，在此基础上，通过将栅格地图 9 分割成连续的小区域以形成更为紧凑的扦i 扑地图，这些地图通过临界线条来划”，l f u 这些 临界线条就成了狭窄的过道，如门道。通过将栅格地l 冬 分割成小数日的区域块，整个新i 扑 地图信息就要比用栅格力法表现的地图少许多倍。冈此，并周这曲种表现方法的优点是单 独使用符自方法所无法氽及的：栅格地图在一般大小利复杂的环境中，容易构建和维护， 并且可以连续地环境建模，使不同位置明确化。拓扑地图能够实现快速规划莆1 人性化的人 机对话界面。不过t l m n 的方法同样也不可避免地沿袭了栅格地图需要更大内存和精确定位 的确定，赢该说是栅格地酗和拓扑地图适当的折中【2 0 l 【川。 2 2 3 移动机器人定位 在下作场景构成的地图中，由于智能机器人的t 作场景基本上可以看作是一个平面， 所以_ ：_ _ i 考虑地面高度的变化，所以机器入自定位最终要求的就是( x ，y ，0 ) 。其中儿x 和y 是机器人在全局地图中的位置，0 是机器人的朝向。 当前的自定位方法主要分为全局自定位、不断更新的丰目对式定位和地阁匹配法。 全局定位顾名思义就是确定当前机器人的绝对方位、在机器人的整个r 作环境上定义 一个全局地图，如果能确定机器人在这个全局地图巾的位置就实现了全局定位。现有的全 局定位方法主要是三角定位和路标汉别两种方法。三角定位的原理和摄像机定标方法很相 似，目前使用的g p s 就是基丁这种方法。在这种方法中需要预先在场景中定义一些参考点， 这些点在全局图中的位置已知，从而相互之间的空间儿何关系已知，当机器人在场景中需 要定位时，就设法获得这样一些点相对于当前机器人的几何信息，然后通过j l 何计算得到 机器入在全局地图中的位置信息拉“。 通常，人们通过光源或其它信号源来实现己知参考点定义，也就是说，需要定位时机 器入在它岗礴检测这些信号源，这种参考点定义方法优点是简单而且能够给机器入快速准 确的提供所需信息，定位的准确程度与机器人与它的参考点之间的距离相关，所以为了提 高定位精度，在场景中需要大量设箕这些参考点。但是对 二普通室内或室外环境是很难实 现的，因为使用者得预先对环境进行改造，而且设备造价昂贵，这使得这利，信号源定义方 法使用很有限。 另一种全局定位的方法是路标法口3 1 。这种方法很像人类定位方法，在一个场景中寻找 自己熟悉的景物，找到的景物越多，越能准确地判断自己当前的方位。经常使用的路标可 分为两类，一种是自然路标，另一种足人_ t 路标。自然路标就是指在场景中固有的那些标 0 浙江理t 大学锄琦9 位沦文 志物，比如室内环境中的门、灯、特殊形状、特殊颜色等等只要是那肚可以代表它所在位 置且存二! ， 以别的物体，都可以充当标志。 标忐法中需要解决的阀题土要是标志定义和标志识别。人眼可以 醍快的把以前见过的 标志从背景中识别出来，这个识别过程至今没有从认知角度完全了觯清楚。目前在定义路 标时只能把传感器易丁检测的特征定义为该物体，比如一个在计算：枕里存储为两条竖直 平行线和位r 上方的一条水平线，当然还可以加进颜已信息。虽然信息越多，检测结果越 可靠，但同时便得检测过程变慢，不宦实时使用。标志识剐的好坏与标志定义的好坏直接 相关。大部分自然路标总是不能很好的被辨识，所以人民一丌始研究的多为人t 路标。人 t 路标是指人为地在场景叶 设置一些路标，这些路标的特点是易r 识别，路标的摆放以能 够最佳的标识当前环境为标准。关于路标的设计和摆放有很多方法。 标志法中机器人识别m 标志届 始定位过程，定位的精度取决丁已识别的标志个数和 识别的精度，以及已识别标志与机器人之间的距离，如果识别的精度很高，那么就可以使 用前而提剑的一角定位法，但是一般来说标志中很难高精度地榆测到标志。近些年很多学 者研究路标法，他们采用的定位算法主要足基丁概率的方法、比如贝叶斯方法、马尔科夫 法等，并且取得一螳成绩。 自然标志和人1 二标志各有优缺点。| j 订者不破坏已有的整体环境，特别是有些场合无法 设置人工标志，比如窜外环境，人类无法到达环境等只能用自然标志。但是自然路标不易 r 检测，提供的位置信息不准确。相对来说，人_ 【路标易于检测孤且可以高效的标汉当前 位箕。自然路标法的优点就是它的缺点，需要人工预先干预工作环境。目前自然路标的研 究是主要潮流，也是路标法发展的主要方向。 以上是全局定位法，另外一种定位方法是不断更新的相对式定位法，即在当前己有定 位结果基础上，每走一步4 i 断更新自己的位置数据。这种方法一般主要依赖! 色程计和惯导。 所谓里程计在移动机器人中主要足在轮子配备光电编码器来纪录轮子转过的陶数，从 而得到行走的距离和速度。当两侧的轮子都有光电编码器时还可以通过转差得到转弯角度， 这样如果在初始时已知了机器人的位置，那么根据里程表得到的数据就呵以不断更新当前 的位置信息口。 惯导在航天、航海中己经有很多的应用。这种不断更新的相对定位法的优点是简单， 所需要的算法效率高，缺点足在行进过程中容易出现积累误差，所阻需要根据其它位置信 息不断更新。通常人们总是结合这种方法与前面的路标法，再用 尔曼滤波器进行融合以 浙江理t 大学 l i li 学位论义 得到准确的位置信息2 ”。 2 2 4 移动机器人路径规划 在机器人导航过程中，路径规划扮演着十分重要的角色，它所要解决就是“w h a ti s t h e b e s t w a v t og e t t h e r e ”的问题，也就是在有障碍物的环境巾找到一条恰当的从给定起点到终 点的运动路径，使机器人在运动过程中能安全、无碰撺地绕过所有的障础物。然而，由丁 在障碍物空间中机器人运动规划的高度复杂性使得这个问题至今未能很好地得以解决。 从某种意义上说，路径规划是寻找到目标的操作序列，本质上就足一个问题求解过程。 传统运筹学理论把规划作为求某种最优解的数值计算来处理，形成了如线形规划、动态规 划等数值计算的方法，并用这些方法解决了f i 少问题、这类方法有严格的理论体系但也 有明显的f i 足。比如要求规划所涉及的约束条件要以数学不等式表示，要求规划的f 标是 某种最优函数的形j = i = ，另外规划所涉及的世界也必须是静止的，需要预先完全准确地知道。 这些部足移动机器入路径规划难以满足的；所以需要采取其它更为有效的方法。另外移动 机器人路径规划的复杂性、多约束、多目标的特点。机器人的变化往往存在很多不定冈素， 环境中动态障碍物的出现也带有随机性；机器人在运动中不仅受到制约其形状的，l 何约束， 丽且由丁机构限制还受到制约其速度的非完整约束；根据任务的不同有时还需要解决多移 动机器人协调操作中的路径规划问题。 目前，因为没有一个可以被普遍接受的关丁机器人导航的一般方法，所以很难分析路径 规划的技术水平。虽然现今的路径规划方法有很多，但都是针对具体机器人，具体的环境， 具体的任务，而且其中很大部分方法要么是理论性的，要么仅仅只在仿真上测试过的， 还有一些只是用来测试具体方法在实际机器人上是否能够达到满意的效果。总之移动机器 入路径规划可以研究的方向很多，还有很多尚未解决的问题。就目前的路径规划方法，根 据环境对环境信息的知道程度可以分为两种类型：环境信息已经完全知道的全局路径规划 和环境信息完全未知或部分末知，但可以通过传感器在线地对机器人的工作环境进行推测， 以扶得障碍物的位置、形状和尺寸等信息的局部路径规划。 全局路径规划包括环境建模和路径搜索策略两个子问题。其中环境建模的土要方法有： 可视图法( v _ o r a p h ) 、自由空间法( f r e es p a c ea p p m a c h ) 和栅格法( g r i d s ) 等。路径搜索策略 主要有：a + 算法、d 4 最优算法等2 “。 局部路径规划的主要方法有：人工势场法( a r t m c i a lp o t e l l t i a lf i e l d ) 、遗传算法( g e n e t i c 2 浙江垭t 入学钡；学位论文 a 1 9 0 r i t h m ) 和模糊逻辑算法( f u z z yl o g i c a l g o r i t h m ) 等。人r 势场法是义一利嘘拟的人t 受力 场中的运动。障得物对机器人产生排斥力，目标点产生吸引力，它们的合力作为机器人的 加速力，来控制机器人的运动力向和计算机器人的位置。该方法结构简单，便于底层的实 时控制，存实时避障和平滑的轨迹控制方面，得到了j 泛的应用，但对存在局部最优解的 问题容易产生死锁现象。冈 面可能是机器人在达到目标点之前就停留在局部最优点。对丁 遗传算法，它是有6 0 年代初j h oj l a n d 提出的，该算法以自然遗传机制和自然选择等生物 进化理论为基础，构造了一类随机化搜索算法。它利用选择、交义和变异来培养控制机构 的计算程序，在某种程度上对生物进化过程做数学方式的模拟。它不要求适麻函数是可导 或连续的，而只要求适应函数为正，同时作为并行算法，它的隐并行性适用于全局搜索。 多数优化算法都是单点搜索算法，很容易陷入局部最优，而遗传算法卸是一个多点搜索算 法，冈而更有呵能搜索到全局最优解。由丁遗传算法的整体搜索策略和优化算法不依赖丁 梯度信息，所以解决了一些其它优化算法无法解决的问题。但遗传算法速度