（模式识别与智能系统专业论文）移动式机器人自主测绘环境地图的方法研究.pdf

摘要 摘要 自主移动式机器人研究的主要目的是实现机器人自主完成其工作任务，尤其 是在陌生的环境内，保证工作效率。机器人自主移动并工作的主要前提是机器人 对工作环境有详细的了解，能够针对需要完成的任务进行路径规划与任务规划， 实现工作的顺利完成。 本文对自主移动式机器人的环境感知、理解及地图测绘进行研究，力求建立 环境结构在机器人大脑中的映象，并通过移动式机器人易于理解的抽象的和形式 化的图谱表示出来，取得了以下研究结果： 一、针对室内清洁机器人，提出了一种机器人工作环境地图的测绘方法，该 方法基于栅格地图表示环境，对环境地图进行分区，通过自由区域联结图广度优 先搜索及深度优先遍历( w s d c ) 形成方形区域遍历顺序，对机器人探测环境的路 线进行导航。实验研究表明栅格地图表示环境对于区域划分与区域遍历的可行 性，采用w s d c 算法，可以减少机器人的运动距离，提高工作效率。 二、基于自组织特征映射图( s 0 m ) 构建了一种新的结构可增长的自组织 特征映射图建立模型( g s o m ) ，该模型的可增长就是特征映射图的神经元数不 是确定的，它可以根据训练样本的分布情况，实现自身结构的自学习和自组织。 实验表明该模型可以在网络结构自组织增长过程中实现输入空间结构的识别，准 确的实现输入空间的模式聚类和模式分类。 三、提出了一种基于g s o m 的自主移动式机器人环境地图测绘方法，该方 法利用g s o m 的增长特性，实现机器人大脑中环境映象的形成和逐渐发展，可 以在样本数未知情况下，确定描述环境特征的最优s o m 神经元数量，以少数 s o m 图神经元分布描述具有大量特征信息的环境结构，建立更能准确描述环境 的拓扑地图。实验表明基于g s o m 算法建立拓扑地图，可以有效确定拓扑结点 的数目，实现输入数据的压缩与分布结构的识别，便于机器人利用g s o m 地图 进行路径规划。 本研究课题受到国家自然科学基金课题( 6 0 3 7 5 0 1 7 ) ，北京市人才强教计划项 目、高等学校博士学科点专项科研基金( 2 0 0 5 0 0 0 5 0 0 2 ) 的支持，相关论文成果 发表在机器人技术与应用和系统仿真学报( e i 刊源) 杂志上 关键字：自主移动式机器人；路径规划；栅格地图；区域遍历；自组织特征映 射图( s o m ) ；拓扑地图 北京工业大学工学硕士学位论文 a b s t r a c t i nt h er e s e a r c ho f t h ea u t o n o m o u sm o b i l er o b o t , t h ep u r p o s ei st oi e a l i z 七t h a tt h e r o b o t 啪e f f i c i e n t l ya c h e v ei t st a s kb yi t s e l e s p e c i a l l yi nt h eu n k n o w ne n v i r o n m e n t t h ep r e c o n d i t i o no f t h em o v i n ga n dw o r l d n ga u t o n o m o u s l yi st h a tt h er o b o ti sa b l et o k n o wt h ew o r ke n v i r o n m e n ti nd e t a i l , a n dm a k ep a t hp l a n n i n ga n dt a s kp l a n n i n gi n o r d e rt oa c h i e v et h et a s k 蝴f u l l y i nt h ep a p e r , w er e s e a r c ht h ea p p e r c e i v i n ga n dc o m p r e h e n d i n go f t h er o b o tt ot h e w o r ke n v i r o n m e n t , i no r d e rt oe s t a b l i s ht h ei m a g eo ft h ee n v i r o n m e n ti nt h er o b o t s b r a i na n dd e s c r i b ei ti na l le a s i l yu n d e r s t a n d i n gw a y t h em a i no u t p ：) i n ei s 越f o l l o w s ： 一、a i m i n ga t t h ei n d o o rc l e a n i n gr o b o t , w ep r e s e n tam e t h o do fr o b o t a u t o n o m o u s l ym a p p i n g i ti sb a s e do ng r i dm a p ，a n ds u b a r c a si ta n dg a i n st h ef r e e a r e a so r d e ri nt h ew i d t h - f i r s ts e a r c ha n dd e p t h f i r s tc o v e r a g e ( w s d c ) w a y , n a v i g a t e t h er o b o ti nt h ee x p l o r a t i o no ft h ee n v i r o n m e n t t h ee x p e r i m e n tr e s u l ti n d i c a t e st h e f e a s i b i l i t yt h a tt h es u b a r e a i n ga n dc o v e r a g ei nu s i n gg r i dm a p ，u s i n gt h ew s d cw a y c a nr e d u c et h em o v i n gd i s t a n c ea n di m p r o v et h ew o r ke f f i c i e n c yo f t h er e b e l 二、b a s e do nt h es e l f - o r g a n i z i n gm a p ( s o m ) w ec o n s t r u c tan e w g r o w i n g s e l f - o r g e n i z i n gm a p ( o s o m ) i t sg r o w i n gc h a r a c t e r i s t i ci st h a ti t sn e u r o nn u m b e ri s n o tf i x e d , i tc a nc h a n g ea c c o r d i n gt ot h ed i s t r i b u t i o no ft h es a m p l e si no r d e rt oc a r r y o u ti t ss t r u c t u r es e l f - o r g a n i z a t i o na n ds e l f - s t u d y t h ee x p e r i m e n ti n d i c a t e st h eg s o m m o d e li sa b l et or e c o g n i z et h es t r u c t u r eo ft h ei n p u ts p a c ei nt h es e l f - g r o w i n go ft h e m a ps 由l 曲l 托，a n dc l a s s i f ya n dc l u s t e rt h ei n p u ts a m p l ee x a c t l y 三、w er e p r e s e n tan e wm e t h o do f t h ea u t o n o m o u sm o b i l er o b o tm a p p i n g i ti s b a s e d0 1 1t h eg r o w i n gc h a r a c t e r i s t i co ft h eg s o mm o d a lt om a k e 缸u et h ei i i l a g e s h a p i n gg r a d u a l l yi nt h er o b o tb r a i n i t 锄f i n dt h eo p t i m a ls o mn e u r o nn u m b e rf o r d e s c r i b i n gt h ee n v i r o n m e n t , a n du s el e s ss o mn c l n o u sd i s t r i b u t i n gt os h o wt h e e n v i r o n m e n ts 扛u c n 腿e s t a b l i s ht h et o p o l o g i cm a pd e s c r i b i n gm o r ee x a c t l yt h e e n v i r o n m e n lt h ee x p e r i m e n ti n d i c a t e st h et o p o l o g i cm a pb a s i n g0 1 1t h eg s o mg a s e f f e c t i v e l yg a i nt h en u m b e ro ft h et o p o l o g i cn o d e sa n dc a r r yo u tt h ed a t ac o m p r e s s e d a n dd i s t r i b u t i o ni d e n t i f i e dt om a k ei tc o n v e n i e n ti nt h er o b o tp a t hp l a n n i n g t h i sw o r ki ss u p p o r f o db yt h en a t i o n a ln a t u r es c i e n c ef o u n d a t i o no f c h i n a ( 6 0 3 7 5 0 1 n 、f u n d i n gp r o j e c tf o ra c a d e m i ch u m a nr e s o u r c e sd e v e l o p m e n ti n i n s t i t u t i o n so f h i g h 盯l e a r n i n gu n d e rt h ej u r i s d i c t i o no f b 蜘i n gm u n i c i p a l i t y ( p 腿 a b s t r a c t i i _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ 舅量詈曼詈| 曼曼曼曼- 鼍曹_ _ - 皇曼皇皇_ | _ 一 ( i h l b ) ) a n dt h es p e c i a lf o u n d i n gf b rd o c t o r a lp r o s r a m ( 2 0 0 5 0 0 0 5 0 0 2 ) ，a n dt h e r e l a t e dw o r kh a sb e e na p p r o v e df o rt h ej o u r n a lo fr o b o tt e c h n i q u ea n da p p l i c a t i o n a n dj o u r n a lo f s y s t e ms m u l a d o a ( e o k e yw o r d s ：a u t o n o m o u sm o b i l er o b o t ；p a t hp l a n n i n g ；鲥dm a p ；a r e ac o v e r a g e ； s d f - - o r g a n i z i n gm a p ( s o m ) ；t o p o l o g i cm a p i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得a e 立工些太堂或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：蕴丝纽日期：迦五亟：竺 关于论文使用授权的说明 本人完全了解j b 塞王些太兰有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：逸红纽导师签名：2 蚴日期：竺墨! ：竺 第1 章绪论 第1 章绪论 1 1 课题研究背景与意义 本研究课题源于国家自然科学基因项目“基于达尔文自动机和运动神经内膜 理论的运动控制技能进化认知模型与自治机器人a g e n t 的研究( 6 0 3 7 5 0 1 7 ) ”。本 项目的基本出发点是：理解和模拟自然生命或生物系统运动控制技能的认知行 为，并将这种行为赋予机器人主体( r o b o t i ca g e n t ) 。 自然生命或生物系统的诸多技能是生物个体在发育成长过程中渐进地形成 和发展起来的。技能的形成和发展过程是生物系统的认知过程，是自然生命认知 能力的体现。理解和模拟自然生命的认知行为，并将这种行为赋予人工生命或人 工系统是认知科学、人工智能和机器入学的重要课题。 人和动物进入一个新的环境时会通过感知了解环境，其过程类似于测绘。通 过感知或测绘渐渐的在头脑中建立起某种关于环境的映象，类似地图，以便做出 可行性的路径规划。映象地图的形成表现人或动物对环境的理解，理解环境的过 程就是对环境进行表示的过程。我们希望机器人能像人或动物一样理解环境，能 像人或动物一样，在新的环境中，通过感官( 传感器) 感知或测绘环境，建立起 关于环境的映象或地图。机器人因而可以进行路径规划，搜索完成任务的最优路 径。模拟人或动物的行为，研究机器人自主测绘环境并绘制地图，对于机器人路 径规划是极为重要的，是自主移动式机器人运动导航的基础。 按照l e o n a r d 和d u r r a n d t - w h y t e 【l 】，机器人的导航问题就是解决机器人的三 个问题。第一个问题就是移动机器人定位。第二个问题与机器人的具体任务有关， 也即任务规划。第三个问题是路径规划问题，就是要求从机器人当前位置与目标 位置之间寻找到一条合理的路径，保证机器人能够安全地到达目标地点，从而完 成指定的任务。 本文研究的主要内容就是机器人自主识别环境并用某种形式描述环境，即绘 制环境地图，为自主移动式机器人导航的三个问题的解决提供基础。 北京工业大学工学硕士学位论文 1 2 自主移动式机器人 随着人类在生存和工作中对机器人代为劳动的要求不断增长，自主移动式机 器人研究取得了很大发展，我们的目标就是使机器人能够在没有人干预、无需对 环境做任何规定和改变的条件下，有目的的移动和完成相应的任务。本节主要介 绍自主移动式机器人的发展过程与现状，以及自主移动式机器人研究的主要内容 和发展前景。 1 2 1 自主移动式机器人的发展及分类 移动机器人的研究始于6 0 年代末期，斯坦福研究院( s r - 0 的n i l s s e n 和 c h a r l e sr o s e n 等人，在1 9 6 6 年至1 9 7 2 年中研造出了取名s h a l 【e y 【2 1 的自主移动机 器人。目的是研究应用人工智能技术，在复杂环境下机器人系统的自主推理、规 划和控制与此同时，最早的操作式步行机器人也研制成功，从而开始了机器人 步行机构方面的研究，以解决机器人在不平整地域内的运动问题，设计并研制出 了多足步行机器人。其中最著名是名为g e n e r a le l e c t r i cq u a d r u p e d t 3 】的步行机器 人。7 0 年代末，随着计算机的应用和传感技术的发展，移动机器人研究又出现 了新的高潮。特别是在8 0 年代中期，设计和制造机器人的浪潮席卷全世界。一 大批世界著名的公司开始研制移动机器人平台，这些移动机器人主要作为大学实 验室及研究机构的移动机器人实验平台，从而促进了移动机器人学多种研究方向 的出现。9 0 年代以来，以研制高水平的环境信息传感器和信息处理技术，高适应 性的移动机器人控制技术，真实环境下的规划技术为标志，开展了移动机器人更 高层次的研究。 图1 - 1 s h a k e y g 器人 f i g 1 1t h er o b o to f s h a k e y 2 第1 章绪论 i i | 曹置窜置曼量| 皇| 曼曼量置皇曼皇量曼詈| 曼鼍曼鼍鼍詈暑量| 皇鲁一 移动机器人分类 4 】：移动机器人从工作环境来分，可分为室内移动机器人和 室外移动机器人，按移动方式来分：轮式移动机器人、步行移动机器人、蛇形机 器人、履带式移动机器人、爬行机器人等；按控制体系结构来分：功能式( 水平 式) 结构机器人、行为式( 垂直式) 结构机器人和混合式机器人；按功能和用途来 分：医疗机器人、军用机器人、助残机器人、清洁机器人等。按作业空间来分： 陆地移动机器人、水下机器人、无人飞机和空间机器人。 1 2 2 自主移动机器人研究的主要内容和趋势 目前，影响智能移动机器人技术研究的因素主要有：导航与定位、通讯、传 感技术和运动控制策略等。步入2 1 世纪，随着电子技术的飞速发展，机器人用传 感器的不断研制、计算机运算速度显著提高和机器人应用领域的进一步扩大，移 动机器人技术将逐渐地得到完善和发展。移动机器人技术的研究与发展的趋势1 4 】 包括：( 1 ) 导航与定位( 2 ) 仿生学和类人机器人机构与能源方面的研究( 3 ) 多传感器 信息的集成融合( 4 ) 网络机器人随着计算机网络的扩展延伸( 5 ) 多机器人系统目( 回 特种机器人。 1 2 3 自主移动式机器人系统 自主移动式机器人主要具有自主性和移动性，它包括导航系统和运动系统。 它能够检测环境信息，并利用对环境的感知，有目的地，安全地运行。这种有目 的地、安全地运行，很多研究者称作导航。自主移动机器人根据导航信号，控制 运动电机，使得机器人主体向目标点移动，这被称作自主移动。 1 、自主移动机器人导航系统可以分成以下几个子系统： 1 ) 环境感知系统： 为了在一个环境中自主地导航，去完成指定的任务，显然对它周围环境的认 识是必不可少的。机器人利用自身的各种传感器对环境进行主动获取或被动感 知，进而对各种感知信息进行融合【5 】，得到周围环境信息。通过对环境信息的感 知，可以实现定位、构建环境地图，检测障碍等。 2 ) 定位系统 移动机器人实现自定位的能力是自主导航的基本内容，对于一个自主机器人 系统，位置信息是必要的。定位是其它高级导航任务的基础，比如目标搜索，避 障，跟踪等。如果没有位置信息，机器人就很难实现这些导航任务。现代定位方 法是对内部传感器和外部传感器信息的融合，来计算机器人的位置和方向。在机 器人的自主导航中，有两种定位任务，第一个是在给定先前位置估计，融合机器 人本身或外界传感器信息，得到当前机器人的位置估计。也称作局部定位，或位 北京工业大学工学硕士学位论文 置跟踪。第二种情况是，在没有任何先前的位置信息时，仅仅依靠环境地图计算 机器人当前的位置，也称作全局定位或初始定位。 3 ) 规划系统 自主导航的目的是要求机器人能够从起始点安全地行驶到目标点，所以机器 人必须能够基于全局环境地图寻找到一条合理的、安全的路径，能够基于局部环 境信息规划下一时刻的位置和方向。规划系统包括全局路径规划胪】和局部避障规 划【7 】两个部分。全局路径规划是根据先验环境模型，找出从起始点到目的点的符 合一定性能指标的可行或最优路径。常用的路径搜索策略有a 算法、动态规划法。 局部避障规划技术是基于周围环境信息和目标点，计算出相应的控制命令。常用 的局部避障算法有人工势场法【。只埘、道路查找法，v f h ，v f h * 。 4 ) 控制系统 控制系统的主要功能是把具体的规划付诸行动，它根据规划系统规划的机器 人下一时刻位置，计算出相应的控制命令。并由一系列的控制器或伺服装置来执 行命令，从而控制机器人沿着规划的路径运行。 表1 1 电机分类 t a b l c l 1t h es o r to f t h ee l e c t r o m o t o r 2 、自主移动式机器人的运动系统主要包括： 1 ) 驱动系统 驱动方式可分为：a 、气压驱动；b 、液压驱动；e 、电气驱动。电气驱动是 2 0 世纪9 0 年代后机器人系统应用最多的驱动方式。它有结构简单、易于控制、使 用方便、运动精度高、驱动效率高、不污染环境等优点电气驱动系统主要包括 电机、电源和车体三部分电机接受导航系统传输的控制信号，转化为电机的转 第1 章绪论 速或方向轮的转角，使得机器人能够驱动移动系统进行直线移动和转向。电机分 类如表1 - 1 所示。 2 ) 移动系统 按照移动方式分类自主移动式机器人可分为：轮式机器人、履带式机器人、 足式机器人等，目前最普遍的是轮式机器人。按车轮数分类，小车一般有三轮、 四轮或六轮，三轮移动机构是目前应用最多的基本移动机构。移动系统主要指推 进系统，包括车轮、传动轴等，属于电机的随动系统。自主移动式机器人移动系 统根据驱动电机转动差( 两轮驱动) 或者电机转动的方向角( 舵轮) 改变其旋转 方向，是机器人主体能够向前移动或转向。 1 3 机器人绘制地图的发展现状与地图的表示方法 移动机器人的定位和地图创建【l “1 6 】是机器人领域的热点研究问题。对于己知 环境中的机器人自主定位和已知机器人位置的地图创建已经有了一些实用的解 决方法。然而在很多环境中机器人不能利用全局定位系统进行定位，而且事先获 取机器人工作环境的地图很困难，甚至是不可能的。这时机器人需要在自身位置 不确定的条件下，在完全未知环境中创建地图，同时利用地图进行自主定位和导 航【1 7 】。这就是移动机器人的同时定位与地图创建( s l a m ) f 3 题。s l a m 也称为c m l ( c o n c u r r e n tm a p p i n ga n dl o c a l i z a t i o n ) ，最先是由s m i t hs c l f 和c h c c s e m a n 提出来 的。由于其重要的理论与应用价值，被很多学者认为是实现真正全自主移动机器 人的关键。 1 3 1 机器人绘制地图的发展现状 近几年来机器人领域的研究者对s l a m 进行了大量的研究，特别是在降低计 算复杂度、提高鲁棒性等方面取得了很大的进展。但是在以下几个方面还需要更 进一步研究扩展s l a m 的应用环境：目前，s l a m 还局限于2 维静态环境中的研 究与应用，而现实中的环境通常是动态的3 维环境。将s l a m 的研究与应用扩展 到2 维动态环境以及3 维动态环境具有重要的意义。更有效的s l a m 实现方法： s l a m 的各种实现方法都不是很完善，基于多机器人协作的s l a m 的研究还刚 刚起步，可以将人工智能、智能控制等领域的方法引入到s i a m 中。开发更有效 的s l a m 算法。更好的地图表达方式：开发其他更好的地图表示方式，特别是复 杂地形中的地图表达方式是s l a m 中值得研究的问题。 概括来讲，自主移动机器人的s l a m 研究的主要发展趋势可以归纳为以下 几点：1 ) 机器人作业环境由已知的结构化环境向未知的非结构环境拓展；2 ) 环 北京工业大学工学硕士学位论文 境感知方面采用能提供更大信息量的多传感器系统( 如激光雷达和视觉系统等) 和多机器人系统( 也称为分布式可移动感知系统) 【1 8 ”l ；3 ) 更加注重概率、模糊数 学等不确定性处理工具在地图描述和数据关联算法中的应用【t 2 1 】；4 ) 在实验研 究中强调实机途径，开发在真实环境下具有高鲁棒性和高适应能力的实用技术； 5 ) 特种应用和服务业的需求日益迫切。可以预见，面对真实世界的非结构化和 动态特点，为了提高移动机器人的自主能力，高适应性、高鲁棒性、高效率的 s i 。a m 理论、方法与技术将是今后的研究热点。 1 3 2 环境地图的表示方法 由于路径规划和许多定位方法都是基于环境地图，所以构建并维护一个环境 地图也是自主导航中的一个重要内容。机器人利用对环境的感知信息对现实世界 进行建模，自动地构建一个地图。地图的表示方式大致可分为3 类：栅格地图【2 冽、 几何地图瞄】和拓扑地图【2 6 1 。栅格地图以更形象的方法表述环境空间信息及其不 确定性，但它受限于环境的规模。几何地图用一个更简洁的方法表示环境，但对 于非常复杂的环境就难以表示。拓扑地图不需要尺度信息，只依赖于环境中特定 地点，但地图构建过程复杂。 基于栅格的地图表示方法即将整个环境分为若干相同大小的栅格，对于每个 栅格指出其中是否存在障碍物。这种方法已经在许多机器人系统中得到应用，是 使用较为成功的一种方法。栅格地图的缺点是：当栅格数量增大时( 在大规模环境 或对环境划分比较详细时) ，对于地图的维护所占用的内存和c p u 时间迅速增 长，使计算机的实时处理变得很困难，也就是说用栅格表示的环境地图，环境空 间的分辩率与栅格尺寸的大小有关，增加分辨率将要增加运算的时间和空间复杂 度。由于传统的栅格表示方法的复杂性，可以采用更有效的四叉树( q u a d 嘲) 表示方法。 几何地图是基于几何特征的地图表示方法，指机器人收集对环境的感知信 息，从中提取更为抽象的几何特征，例如线段或曲线，使用这些几何信息描述环 境。这种表示方法更为紧凑，且便于位置估计和目标识别。几何特征的提取需要 对感知信息作额外的处理，且需要一定数量的感知数据才能得到结果。几何尺度 地图由一组环境路标特征组成，每一个路标特征用一个几何原型来近似。这种地 图只局限于表示可参数化的环境路标特征或者可建模的对象，如点、线、面。 路标地图的构建方法大都是基于对环境信息的相对观测，然后用这些观测到的环 境路标特征表示环境地图。由于以几何位置关系来表示环境地图，所以为了保证 地图的一致性，要求各观测信息的位置是相对精确的。对于结构化的办公室环境， 用一些几何模型来表示环境空间是可行的。用线段来拟合室内的墙面，用点来拟 第1 章绪论 合墙角、桌子角等。对于室外道路环境，可以用点特征来表示道路两侧的大树位 置。而对于室外越野环境，可以用曲面来拟合路面地形。 拓扑地图也是一种紧凑的地图表示方法，特别在环境大而简单时。这种方法 将环境表示为一张拓扑图( g r a p h ) ，图中的节点对应于环境中的一个特征状态、地 点( 由感知决定) ，如果节点间存在直接连接的路径则相当于图中连接节点的弧。 这种表示方法可以实现快速的路径规划。由于拓扑图通常不需要机器人准确的位 置信息，对于机器人的位置误差也就有了更好的鲁棒性。但当环境中存在两个很 相似的地方时，拓扑图的方法将很难确定这是否为同一节点( 特别是机器人从不 同的路径到达这些节点时) 。拓扑地图对于结构化的环境是一个很有效的表示方 法，这里有更多的特定地点。相反，在非结构化环境中，地点的识别将变得非常 复杂。如果仅仅以拓扑信息进行机器人定位，机器人将很快迷失方向和位置。 目前，为了综合各种地图表示方法的优点，对于不同表示方法的结合已经有 很多人进行研究【2 7 捌j 1 3 3 地图绘制方法 s l a m 算法最开始出现在s m i t hs e l f 和c h a p m a n 的论文中，它以a y h e 和 f a u g e r a s ，c h a t i l a 和l a u m o n d 的工作为基础，采用增广的系统空间，运用e k f 对机 器人位置和路标特征位置进行同时估计。这种方法被许多研究者采用，称作 s l a m 全协方差方案。用于解决s l a m 问题的方法有两种方案。 第一个方案是基于e x t e n d e dk a l m a nf i l t e r ( e k f ) 的滤波估计方法。这种方案 运用e k f 构建一个表示环境空间关系的统计模型，m o u 恤1 i 盯和c i l 蚯l a 运用实际数 据对这种方法进行了实验验证。在s l a m 全协方差方案的基础上，c o m p r e s s e d e x t e n d e dk a l m a nf i l t e r ( c e k f ) 2 9 】通过对e k f 过程进行优化，得到的一个s l a m 优 化方案。e x t e n d e di n f o r m a t i o nf i l t e r ( e ) 【3 0 1 ，也称作i n v e r s ec o v a r i a n c ef i l t e r 是 e k f 的逆形式，运用e i f ，得到一个有效的s l a m 方案。在信息空间中进行滤波 处理，预测过程的时间复杂度是o ( 1 ) ，观测更新过程的时间复杂度是o ( n ) 。但是， 由于雅可比矩阵的计算，要求从信息空间变换到位置状态空间。 另一个方案是基于贝叶斯滤波的方法，它并不运用高斯假设，可以表示任意 的概率密度函数，但是计算量太大，难以得到实际应用。而在 3 1 】中运用高斯和 s u mo fg a u s s i a n ( s o o ) 来表示环境路标特征模型，得到一个f i t l lb a y e s i a ns l a m 方案。其它的贝叶斯滤波方法有基于粒子滤波器的。f a s t s l a m ”d 2 】，能够处理 多峰值的概率密度函数。这种方法的时间和空间复杂度是o ( n l r i p ) ，其中n l 是路 标特征的数量，n p 是粒子的数量。e x p e c t a t i o nm a x i m i z a t i o n ( e m ) p 驯把地图构建 问题归结为约束最大似然函数m a x i m t m l 1 i k e l i h o o d l ) 概率估计问题，包括 北京工业大学工学硕士学位论文 e s t e p 和m - s t e p 估计和最大化两个步骤。 1 4 论文的研究内容与组织结构 自主移动式机器人工作环境的识别是机器人工作的基础，我们针对这一问题 进行研究，主要解决的问题是如何绘制机器人工作环境的表示地图；首先，介绍 的是针对室内清洁机器人的特殊工作环境和工作要求，提出一种基于栅格地图描 述的环境空间划分与遍历算法，实现室内清洁机器人对周围环境的识别和完整地 图的建立；其次，针对自组织特征映射图的自组织字学习和空间结构识别特性， 同时考虑实际问题的需要，提出一种可增长自组织特征映射图算法( g s 0 m ) ， 并对其模型的建立和特性进行细致分析；再次，针对机器人进入新环境后，对新 环境的了解是逐步增长的特点，本文对利用g s o m 模型的增长特性，提出一种基 于g s o m 算法的机器人工作环境拓扑地图建立的新方法。 本文的主要内容包括五个方面：第一部分，绪论部分，主要介绍课题的研究 背景及意义、自主移动式机器人的研究现状和前景及自主移动式机器人的体系结 构和机器人自主绘制地图的现状与前景及环境地图的表示方法；第二部分，是对 针对室内清洁机器人的特殊工作环境提出的基于栅格地图的环境空间划分与遍 历算法以及环境空间描述地图的建立方法的介绍；第三部分，对自组织特征映射 图( s o m ) 算法进行研究，提出新的可增长自组织特征映射图( g s o m ) 模型， 并对该模型的建立和特性分析做出了详细介绍；第四部分，主要是基于第三部分 介绍的可增长自组织特征映射图( g s o m ) 模型，针对自主移动式机器人的工作 的实际问题，详细介绍了一种描述自主移动式机器人工作环境的拓扑地图的建立 方法，并对其优越性做出相应的介绍；第五部分，总结部分，对本文研究的内容 和提出的新方法、新观点做出总结性的介绍，同时明确其应用前景和需要改进的 地方。 第2 章针对室内清洁机器人特殊工作环境的地图绘制方法研究 第2 章针对室内清洁机器人特殊工作环境的地图绘 制方法研究 清洁机器人【蚓作为智能移动机器人实用化发展的先行者，其研究开始于2 0 世纪8 0 年代，到目前为止，已经产生了一些概念样机和产品吸尘机器人的发展， 带动了家庭服务机器人行业的发展，也促进了移动机器人技术、图像和语音识别、 传感器等相关技术的发展。 室内清洁机器人的工作环境主要为普通家庭环境，也可以用于机场候机厅、 展览馆、图书馆等公共场所。环境的共同特征为有限的封闭空间、平整的地板以 及走动的人员，因此可以归结为复杂多变、结构化的动态环境【3 5 1 。所以环境适应 性是对此类机器人的基本要求。 2 1 室内清洁机器人的结构功能介绍 室内清洁机器人系统通常由4 个部分组成：移动机构、感知系统、控制系统 和吸尘系统。随着近年来计算机技术、人工智能技术、传感技术以及移动机器人 技术的迅速发展，吸尘机器人控制系统的研究和开发己具备了坚实的基础和良好 的发展前景。目前发展较快、对吸尘机器人发展影响较大的关键技术是：传感技 术、路径规划技术、吸尘技术。 2 1 1 室内清洁机器人结构描述 对室内清洁机器人的感知、运动与清洁系统进行简单描述，如图2 1 。 主要构成包括： ( 1 ) 距离传感器( 声纳)在机器人的周围共安装了6 个声纳传障碍物 感器，用来探测机器人周围的环境，检测距离 ( 2 ) 接触传感器( 灵敏开关)在前端安装两个灵敏开关，主要为了解 决声纳传感器近距离盲区问题。当机器人清洁到接触上障碍物后，灵 敏开关起作用，输出一个脉冲信号。 ( 3 ) 内部传感器( 编码器、加速度计和陀螺仪等)主要为了检测清洁 机器人的内部状态，如速度、方向、移动距离。 ( 4 ) 雷达系统测量路标距离，实现三视距定位。 ( 5 ) 控制系统实现传感器测量数据融合、雷达定位系统与清洁系统的 北京工业大学工学硕士学位论文 正常工作、抽象地图的绘制及机器人的运动控制与路径规划。 ( 6 ) 驱动轮( 包括伺服电机)左右各一个，保证清洁机器人的前向运 动与转向。安装在机器人的中间，便于利用两个驱动轮反相转动实现 机器人原地转向。 ( 7 ) ( 8 ) 图2 - 1 室内清洁机器人结构简图 f i g 2 - lt h es i m p l e 鲥m l g o , x r eo f o r e i n d o o rc l e a r i n gr o b o t 2 1 2 室内清洁机器人定位 机器人定位技术可分为绝对定位和相对定位技术两类。绝对定位主要采用导 航信标、主动或被动标识、地图匹配或卫星导航技术( g p s ) 进行定位，定位精度 较高。这几种方法中，信标或标识牌的建设和维护成本较高，地图匹配技术处理 速度慢，g p s 只能用于室外，目前精度还很差( 1 0 m - 3 0 m ) 。绝对定位的位置计算 方法包括三视角法、三视距法、模型匹配算法等。相对定位是通过测量机器人相 对于初始位置的距离和方向来确定机器人的当前位置，通常也称为航位推算法。 常用的传感器包括里程计及惯导系统( 速度计、陀螺仪、加速度计等) 。航位推 算法的优点是机器人的位置是自我推算出来的，不需要对外界环境的感知信息， 缺点是漂移误差会随时间累积，不适于精确定位。很显然，绝对定位和相对定位 各有优缺点，具有互补性，将两者结合能形成更加准确可靠的。我们采用绝对定 位与相对定位的结合，实现室内机器人的自主定位；主要采用航位推算法，由于 积累误差的存在，当机器人移动一定的距离时，采用三视距法对机器人的位置进 行纠正。三视距法的实现主要建立在安装在室内的三个固定路标，通过雷达系统 测量清洁机器人与这三个路标的距离计算机器人的当前位置。计算的位置与航位 第2 章针对室内清洁机器人特殊工作环境的地图绘制方法研究 推算的位置进行比较，计算误差，机器人按照误差纠正自己的位置。 2 1 3 室内清洁机器人的环境感知 机器人对环境的感知主要是基于距离传感器和接触传感器，采用绕障碍物行 走来实现。在机器人运动过程中保持左右驱动轮的转速相等使机器人沿直线运 动，利用前端距离传感器事先检测到前方障碍物，尽早给机器人一个减速信号， 防止碰撞。当距离传感器检测到前方障碍物后，机器人会适当减速，但是为了准 确测量到障碍物的位置，速度不会减到零，而是让机器人缓慢碰上障碍物，接触 传感器给一个脉冲信号，此时机器人马上停止，左转，进入障碍物探测程序。障 碍物探测行为包括机器人前向运动行为和传感器检测行为。在前向运动过程中， 机器人的右侧距离传感器的输出具有最高的优先权，即一旦右侧传感器输出为无 障碍物状态，机器人马上右转直到为有障碍物状态为止。当前端距离传感器检测 到机器人前面的障碍物时，机器人减速运动直到接触传感器输出脉冲信号，停止 运动判断转向。转向判断是建立在机器人左侧右侧的距离传感器的基础上的。根 据这两部分传感器的输出信号确定无障碍物的一侧，或者两侧都有，机器人向后 转向，继续沿障碍物行进，直到回到初始检测到障碍物的位置。 2 2 基于栅格地图的环境空间划分与遍历 本节主要介绍机器人环境工作空间的识别与遍历，基于栅格地图描述环境 【垌，采用区域划分，对工作环境空间分区识别，同时为了减少区域间冗余的转移 移动距离，提出了广度优先搜索深度优先遍历法0 v s d c ) ，对空间划分形成的邻 接图进行搜索，得到区域之间的遍历序列，机器人以次顺序进行区域间二次搜索， 最终达到自由空间的完全识别与遍历。 2 2 1 基于栅格地图的环境描述 通过对室内环境进行观察可以看出，室内物体大部分为方形的，至少可也看 成近似方形物体；本文对环境进行二维空间建模，把室内环境地图用二维数组 m a p 表示，在障碍物占有区域内的坐标点上用“”标定，表示此坐标与相邻的标 有“”的坐标之间的区域为障碍物区域，未标定区域为自由区域，它可以分割为 一个方形区域，用n x 2 2 的三维数组庙，龆，庙，【七，：，：】表示分割出的的k 个方 形自由区域，它存储的是方形区域的左下和右上顶点的坐标；如图2 - 2 ，区域 a b f h 所围的区域为障碍物区域，区域b c i d g e h f 所围的区域为自由区域，它 可以分割为三个方形区域2 、3 和4 ，其中f a r e a 1 ，：，：】_ 【a ( f ，力i ( i ，朋表示第 北京工业大学工学硕士学位论文 一个方形自由区域( 区域2 ) 。用二位数组n a m a 表示各个方形自由区域的相邻区 域，用直观方法表示就是联结图。最终环境地图的符号表示： e m = 利用栅格描述的环境中的一些重要的转折点实现自由空间的划分，提出一种 较优的路径规划方法，实现区域间的高效转移。 e g - 。3 4 h f - + + 1 + + + 。 2 d - i b c 图2 - 2 区域确定 f i g 2 - 2t h ed e m a r c a t i o no f t h ea r e a 2 2 2 自由空间划分及合并算法 栅格地图描述的环境的中物体的顶点在四个方向上的延长线总会有交点，这 些交点及顶点的集合q 统一用来确定剩余自由区域。在确定各个区域的过程中， 我们通过确定集合q 中的各个点在右、上、右上方的最近临近点并保证在这四 个点包含的区域内没有已标示出的障碍物点。如图2 - 2 ，这九个点可以确定四个 不重叠的区域( 1 、2 、3 、4 ) 。区域划分标定算法可以描述如下：( 假设从点a ( u ) 开始) a d ( 区域划分标定) 算法： s t e p l ：取集合q 中的第一个点a ( f ，- f ) 。 s t e p 2 ：在m a p 上搜索( f ，) 、( 件1 ，) 、( i + 1 ，产1 ) 、( i ，产i ) 四个点，确定 是否全已设定为障碍物点，是，g ot os t y 6 ；若不全是，则g ot os t e p 3 。 s t e p 3 ：判断( f + l ，) 是否在集合q 中；不在，则继续沿x 轴搜索判断( 什2 ， ，) 直到x 的m a x - x ，g o t o s t e p 6 ：或者找到点( z 2 ，) 在集合q 中 s t e p 4 ：沿y 轴搜索( 垃，产1 ) 卢尹l ，直到y 轴的最大值m a x - ) , ，g ot 0s t e p 3 ： 或者找到( 忍，口) 属于集合q ，然后判断( f ，皿) 是否在集合q 中， 第2 章针对室内清洁机器人特殊工作环境的地图绘制方法研究 若属于， g ot 0s t e p s ；若不属于集合q ，则g ot om - p 4 。 s t e p s ：f a r e a ( k , ：，：户【( f ，力；( f 2 ，j 2 ) t c = k + l ： s t e p 6 - 判断q 中的点是否作为基准点全部搜索一遍；不是，则取出集合q 中的下一个点，g ot os t e p 2 是，则s t o p 。 例如图2 - 2 中，从a ( i ，力点开始，因为( 升1 ，f ) 、( 抖l ，产1 ) 、( 升1 ，力、( f ， ，) 全为障碍物点，转到搜索b ( ，力，因为在( i + 1 ，j ) 不是障碍物点，所以继续 搜索到c ( t 2 ，) 属于集合q ，接着沿y 轴搜索到i ( z 2 ，口) 点并且点f ( f ，皿) 属于集合q ，此时可以确定区域2 如此下去直到集合q 中