（计算机应用技术专业论文）动态环境下移动机器人同时定位与建图研究.pdf

摘要移动机器人同时定位与建图( s l a m ) 问题是移动机器人研究领域的基本问题与研究热点，也是移动机器人真正实现自主的最重要的条件之一。所谓同时定位与建图，是指机器人在移动过程中根据位姿估计和传感器数据进行自身定位，同时建造增量式地图。当前提出的很多s l a m 问题的解决方法是面向静态环境的，然而机器人真实的工作环境往往是动态的，因此对于动态环境下移动机器人s l a m 技术的研究有着十分重要的意义。移动机器人在动态环境下的同时定位与建图主要涉及三个问题：s l a m 解决方法、数据关联和动态目标的处理。本文针对这三个问题展开了深入的研究，最后建立和实现了s l a m i d e 系统，并在自行研制的移动机器人平台m o r c s i 上测试成功。本文在研究中取得了以下成果：针对扩展卡尔曼滤波s l a m 方法在路标增加时协方差计算量倍增的问题，提出了一种基于局部地图的扩展卡尔曼滤波同时定位和建图的方法。该方法周期性地以机器人所在位姿为原点建立局部坐标系，进行局部s l a m ，然后根据局部地图范围对全局地图更新。由于无需每次更新全局地图，因此减少了计算复杂度，且由于局部地图的独立性，因此该方法累积误差少，同时还会减少计算量。将粒子群优化的思想引入到粒子滤波s l a m 中，提出了一种基于粒子群优化的同时定位与建图方法。该方法既可发挥粒子滤波适用任意非线性系统的优点，还可通过增加考虑个体粒子和群体粒子的影响，改善s l a m 预测过程的粒子采样，从而提高采样效率。在保证s l a m 的精度和粒子的收敛性的同时，减少粒子集中时所使用的粒子数。针对经典的单匹配最近邻和联合匹配方法中关联假设一旦确定就不能修改的不足，将数据关联问题转换成离散优化问题，提出了一种基于粒子滤波的多假设数据关联方法。其核心是利用多个粒子来维持多种数据关联假设，通过计算关联代价来获得粒子权重，用基本剪枝技术在粒子重采样过程中滤除错误的数据关联假设。该方法实际上是在一定时间以后才获得真正最优或次优的关联结果，通过实验分析和比较发现，该方法能获得更正确的数据关联结果和更高的定位精度。由于动态环境下声纳传感器无法正确检测动态目标从而降低地图创建的精度的问题，本文提出了一种声纳和视觉传感器结合的动态环境地图创建方法。为保持地图信息的完整性，该方法分别建立了动、静态栅格地图，利用前一时刻的静态地图、当前声纳观测信息和摄像头检测的动态目标信息的比较来更新，并给出了地图更新模型。视觉信息能成功的解决地图中某些动态目标被当成静态目标的错误，从而建立正确的地图。设计并实现了动态环境下移动机器人同时定位与建图系统s l a m i d e ( s l a mi nd y n a m i ce n v i r o n m e n t s ) ，为动态环境下移动机器人s l a m 给出了一个整体结构和实现方法。该系统将观测数据利用缸近邻聚类后，构建统一的目标模型，综合前面研究的数据关联、动态目标检测和s l a m 解决方法，引入局部地图思想，将移动机器人运行环境中的动态目标、静态目标和移动机器人位姿同时进行估计，最终实现了在动态环境下移动机器人的同时定位与建图。实验结果表明该系统能够在比较平坦的室内动态环境下实现准确的动态目标检测、地图创建以及机器人位姿估计。关键词动态环境，移动机器人，同时定位与建图，数据关联，动态目标检测，扩展卡尔曼滤波，粒子滤波，粒子群优化i ia b s t r a c ts i m u l t a n e o u sl o c a l i z a t i o na n dm a p p i n g ( s l a m ) i saf u n d a m e n t a la n dh o tp r o b l e mi nm o b i l er o b o t i c s i ti so n eo ft h em o s ti m p o r t a n tq u a l i f i c a t i o n sf o rm o b i l er o b o tt or e a l i z ea u t o n o m y s l a mi st h ep r o c e s st h a tar o b o tl o c a t e si t s e l fw i t hs e n s i n ga n de s t i m a t i o n w h i l ei n c r e m e n t a l l yb u i l d st h ee n v i r o n m e n tm a p n o w , m o s to ft h es l 砧m e t h o d sa r eb a s e do nt h ea s s u m p t i o nt h a tt h ee n v i r o n m e n t sa r es t a t i c s i n c et h er e a lw o r l da r ed y n a m i c i ti sn e c e s s a r yt or e s e a r c h 也em o b i l er o b o ts l a ma p p r o a c h e si nd y n a m i ce n v i r o n m e n t s t h e r ea r et h r e es u b p r o b l e m si n v o l v e di nm o b i l er o b o ts l a mi nd y n a m i ce n v i r o n m e n t s ：s l a ms o l u t i o n s 。d a t aa s s o c i a t i o na n dd y n a m i co b j e c t sd i s p o s a l d e d i c a t e dt ot h et h r e es u b - p r o b l e m st h et h e s i sd e v e l o p sad e e pr e s e a r c h ，a n df i n a l l yc o n s t r u c t sa n dr e a l i z e sas l a ms y s t e mi nd y n a m i ce n v i r o n m e n tw h i c hi si m p l e m e n t e ds u c c e s s f u l l yi nt h em o b i l er o b o tm o r c s i t h em a i nc o n t r i b u t i o n so ft h et h e s i s i nr e s e a r c ha r es h o w na sf o l l o w i n g ：a na p p r o a c ho fs i m u l t a n e o u sl o c a l i z a t i o na n dm a p p i n gb a s e do nl o c a lm a p si sp r e s e n t e d al o c a lf r a m eo fr e f e r e n c ew i l lb ee s t a b l i s h e dp e r i o d i c a l l ya tt h ep o s i t i o no ft h er o b o t ，a n dt h el o c a lm a pi st h e nf u s e di n t ot h eg l o b a lm a pa c c o r d i n gt ot h er a n g eo ft h el o c a lm a pt ou p d a t et h eg l o b a lm a pe s t i m a t e t h i sa p p r o a c ht ot h es l a mp r o b l e ma l l o w st h el e s sc o m p u t a t i o nc o m p l e x i t yb e c a u s eo fn o tu p d a t i n gg l o b a lm a pe a c ht i m e ，a n db e c a u s eo ft h ei n d e p e n d e n c eo ft h el o c a lm a p st h ea p p r o a c hw i l ln o tc u m u l a t et h ee s t i m a t i o na n dc a l c u l a t i o ne r r o r s ap a r t i c l es w a r mo p t i m i z e ds i m u l t a n e o u sl o c a l i z a t i o na n dm a p p i n gm e t h o di sp r e s e n t e db yi n t r o d u c i n gp a r t i c l es w a r mo p t i m i z a t i o ni n t ot h es l a mp r o c e s s ，a i m e da tt h ep r o b l e mo fn e e d i n gal a r g es a m p l es i z e t h em e t h o de x e r t st h ea d v a n t a g e so ft h ep a r t i c l ef i l t e rw h i c hi sa p p l i c a b l et oa n yn o n 1 i n e a rs y s t e m b yc o n s i d e r i n gt h ee f f e c t i o no ft h ei n d i v i d u a la n ds w o r mp a r t i c l e s ，t h em e t h o dc a na l s oi m p r o v et h ee f f i c i e n c yo ft h es a m p l ep r o c e s s ，a sw e l la sr e d u c et h ep a r t i c l en u m b e rw h i l eg u a r a n t e et h ea c c u r a c yo ft h es l a ma n dt h ep a r t i c l e sc o n v e r g e n c ea tt h es a m et i m e i i ii no r d e rt or e s o l v et h ep r o b l e mt h a tt h ec l a s s i ci c nna n dj c b bm e t h o dc a nn o tm o d i f yt h ep r e v i o u sa s s o c i a t i o nh y p o t h e s i s ，t h ed a t aa s s o c i a t i o np r o b l e mi st r a n s f o r m e da st h ed i s c r e t eo p t i m i z a t i o na n dan e wm u l t i p l eh y p o t h e s e sd a t aa s s o c i a t i o nm e t h o db a s e do nt h ep a r t i c l ef i l t e ri sp r e s e n t e d m u l t i p l ep a r t i c l e sa r eu s e dt om a i n t a i nt h em u l t i p l ed a t aa s s o c i a t i o nh y p o t h e s e s ，a n de v e r yp a r t i c l e sw e i g h ti sc a l c u l a t e db ya s s o c i a t i o nc o s t d u r i n gt h er e s a m p l e ，t h ew r o n gh y p o t h e s e sa r ed i s c a r d e dt h r o u g hb a s i cb r a n c ha n db o u n da p p r o a c h t h er e a lo p t i m i z a t i o no rs u b o p t i m i z a t i o na s s o c i a t i o nr e s u l t sa r eo b t a i n e da f t e rap e r i o d b ye x p e r i m e n tr e s u l t sa n a l y s i sa n dc o m p a r i s o n ，t h en e wm e t h o dc a nr e a c hm o r ec o r r e c td a t aa s s o c i a t i o nr e s u l t sa n dh i g h e rl o c a t i o np r e s i c i o n a na p p r o a c hf o rm o b i l er o b o t si ss u g g e s t e di nt h i sp a p e rt om a pd y n a m i ce n v i r o n m e n t su s i n gs o n a ra n dv i s i o ns e n s o r s ，a i m i n ga tt h ep r o b l e mo ft h el o wm a p p i n ga c c u r a c yc a u s e db yt h ef a c tt h a tt h es o n a rc a nn o td e t e c td y n a m i co b je c t sc o r r e c t l y i no r d e rt om a i n t a i nm o r ec o m p l e t em a p p i n gi n f o r m a t i o n ，t h ea p p r o a c hb u i l d ss t a t i ca n dd y n a m i cg r i dm a p sr e s p e c t i v e l y t h et w ot y p e so fo c c u p a n c yg r i dm a p sa r eu p d a t e db yt h ep r e v i o u ss t a t i cm a p sa n dt h es o n a ro b s e r v a t i o n sa n dt h ed e t e c t e dd y n a m i co b je c t su s i n gm o n o c u l a rc a m e r a t h em a pu p d a t em o d e li sg i v e n t h ev i s i o ni n f o r m a t i o nc a ng e tr i do ft h em i s t a k e st h a ts o m ed y n a m i co b je c t sa r ec o n s i d e r e da ss t a t i co n e sa n dh e l pb u i l dt h em a pc o r r e c t l y as l a m i d e ( s l a mi nd y n a m i ce n v i r o n m e n t s ) s y s t e mi sd e s i g n e da n dr e a l i z e di nt h et h e s i s ，w h i c hs u p p l y sah o l i s t i cs t r u c t u r ea n das e r i e so fi m p l e m e n t a t i o nm e t h o d sf o rm o b i l er o b o ts l a mi nd y n a m i ce n v i r o n m e n t s i ns l a m i d es y s t e m ，t h eo b s e r v a t i o n sa r ek - n e i g h b o u rc l u s t e r e df i r s t l y , a n dau n i f o r mt a r g e tm o d e li sc o n s t r u c t e d t h ed y n a m i co b j e c t sa n ds t i l lo b j e c t sa n dt h em o b i l er o b o tp o s ea r ee s t i m a t e ds i m u l t a n e o u s l y , b ys y n t h e s i z e dt h ea b o v er e s e a r c ha b o u td a t aa s s o c i a t i o na n dd y n a m i co b je c t sd e t e c t i o na n ds l a ms o l u t i o na n dl o c a lm a p s f i n a l l y , t h er e s u l t so ft h ee x p e r i m e n t a lt e s tp r o v et h a tt h es l a m i d es y s t e mc a nr e a l i z ed y n a m i co b je c t sd e t e c t i o na n dm a p p i n ga n dl o c a t i o nc o r r e c t l y i vk e yw o r d sd y n a m i ce n v i r o n m e n t s ，m o b i l er o b o t ，s i m u l t a n e o u sl o c a l i z a t i o na n dm a p p i n g ，d a t aa s s o c i a t i o n ，d y n a m i co b j e c td e t e c t i o n ，e x t e n d e dk a l m a nf i l t e r , p a r t i c l ef i l t e r , p a r t i c l es w a r mo p t i m i z a t i o nv原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。作者签名：亡堡堕皇生日期：_ 三二l 年月上日学位论文版权使用授权书本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。作者签名：立塾皇土乡导师签名缸量日期：竺卫年月兰日中南大学博士学位论文第一章绪论1 1 课题来源与研究背景第一章绪论本论文来源于国家自然科学基金重点项目“未知环境中移动机器人导航控制的理论与方法研究 ( 6 0 2 3 4 0 3 0 ) 和国家基础科研项目“多移动体的协同技术的基础研究 ( a 1 4 2 0 0 6 0 1 5 9 ) ，属于其子任务“环境建模与定位”的研究方向。1 2 移动机器人同时定位与建图的研究意义环境建模与定位是移动机器人导航领域的基本问题与研究热点【l 】，也是移动机器人真正实现自主的最重要的条件之一1 2 】。所谓环境建模( m a p p i n g ) 是建立机器人所工作环境的各种物体如障碍、路标等的准确的空间位置描述，即空间模型或地图。而定位( l o c a l i z a t i o n ) 则意味着机器人必须确定自身在该工作环境中的精确位置。精确的环境模型( 地图) 及机器人定位有助于高效地路径规划和决策，是保证机器人安全导航的基础。移动机器人的环境建模需要定位，而定位又依赖于环境地图，定位和建图问题是一个“鸡和蛋的问题，为克服这个问题一些研究者提出了同时定位与地图构建的可能性。机器人构建一个环境地图，并同时运用这个地图进行机器人定位，称作同时定位与建图( s i m u l t a n e o u sl o c a l i z a t i o na n dm a p p i n g ，s l a m ) 或并发定位与建图( c o n c u r r e n tl o c a l i z a t i o na n dm a p p i n g ，c l m ) 【3 ，4 ，5 1 。由于其重要的理论和应用价值，被认为是实现真正全自主移动机器人的关键而引起了移动机器人研究人员的极大兴趣【6 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ，1 4 ，1 5 1 。近些年s l a m 已经渐渐受到研究者的重视，涌现大量的相关研究的文献，不仅是s l a m 理论技术上，对各种不同环境下的s l a m 技术的应用也进行了研究，如图1 1 所示。然而，目前大部分对s l a m 的研究都是建立在静态环境的假设下，而真实环境却是动态变化的，如人的走动、门的开闭、环境的变化等，都会给建模和定位带来无法预测的噪声，因此现有算法并不能很好的适用于动态环境。动态环境建模问题是目前环境建模领域的一个充满挑战的开放问题【2 j 。因此，本课题针对动态环境下移动机器人同时定位与建图领域存在的若干问中南大学博学位论文第章绪论题，研究无先验信息仅依赖自然路标的s l a m 方法及其改进，数据关联方法、动态障碍物的检测技术以及动态环境下的s l a m 技术。目的在于减小s l a m 的计算量、提商建立地图的准确性和移动机器人机器人定位精度，从而提升移动机器人在动态环境叶1 长时间生存能力。( 曲室外越野藤水下( c ) 采矿机器人卅) u a v国l 一1 不同环境s l a m 应用实例t3 国内外研究现状分析131 移动机器人定位定位( w h e r e 帅i ? ) 作为移动机器人实现自主能力的最基本问题【旧，其目的就是确定移动机器人在运行环境中相对于世界坐标系的位置及其本身的姿态。现有移动机器人的定位方法可以分为三类l i ：相对定位：又称航迹推测( d e a dr e c k o n i n g ，d r ) ，主要依靠里程计( o d o m e t r y ) 、陀螺仪( 0 y m s c o p e s ) 等内部本体感受传感器，给定初始位姿，通过测量机器人相对于初始位姿的距离和方向来确定机器人的当前位姿。绝对定位：主要采用导航信标( l a n d m a r kn a v i g a t i o n ) 、主动或被动标识中南大学博士学位论文第一章绪论( a c t i v eo rp a s s i v eb e a c o n s ) 、地图匹配( m a pm a t c h i n g ) 或全球定位系统( g l o b a lp o s i t i o n i n gs y s t e m ，g p s ) 进行定位。位置计算方法包括三边测量法( t r i l a t e r a t i o n ) 、三角测量法( t r i a n g u l a t i o n ) 、模型匹配算法( m o d e lm a t c h i n g ) 等。组合定位：相对定位方法具有自包含的优点，能够依据运动学模型自我推测机器人的航迹。但是这种方法不可避免地存在随时间距离增加而增加的累积航迹误差。绝对定位方法中，信标或标识牌的建设和维护成本较高，地图匹配技术处理速度较慢，g p s 只能用于室外。由于单一定位方法的不足，移动机器人定位依旧是基于航迹推测与绝对信息矫正相结合的方法。1 3 2 移动机器人建图研究时间与空间约束下的环境知识表示以及它们的性质，将传感器感知到的离散的、片面的、非完整的空间信息形成可应用研究于决策规划的知识形式，是环境认知的重要方法论【l 引。环境模型表示是解决环境建模问题的第一步。环境建模的本质属于环境特征提取与知识表示方法的范畴，决定了系统如何存储、利用和获取知识，即怎样获取环境信息、怎样表示环境地图、怎样构建环境地图。创建地图的目的是供机器人进行路径规划，因此地图必须便于机器理解和计算，而且当探测到新环境信息时，应该能够方便地添加到地图中。典型的地图表示方法有尺度地图、拓扑地图和混合地图【1 9 2 0 , 2 1 1 。尺度地图又分为栅格地图和几何特征地图。地图表示方法不同，适用场合和作用也就不一样。尺度地图表示环境的几何属性。为了构建地图，移动机器人必须处理从传感器( 激光雷达、声纳、摄像机等) 获取的外部环境信息和自身的运动姿态。由于这些数据来源不是很准确，因而在构建地图时需要对这些不确定性信息进行处理。概率理论和方法能够很好地处理不确定性信息，在移动机器人的地图构建中得到了广泛的应用。栅格地图最早由h p m o r a v e c 和a e l f e s 于1 9 8 5 年提出【2 2 】，其思想是把环境空间分解为局部单元并用它们是否被障碍占据来进行状态描述。这种方法采用概率值表示模型的不确定性，而且能够提供较精确的度量信息，形成的地图非常容易理解和处理，并且便于多传感器信息的融合，因此在大量移动机器人系统中得到应用，直到现在仍保持着活跃的生命力。但是，度量信息的准确性严重倚赖里程计精度以及传感器的不确定性处理程度，存储和维护的数据量大，大范围环境中沉重的计算负担将难以满足实时要求【2 3 ，2 4 1 。图1 2 ( a ) 显示了基于二维传感器构建的栅格地图模型。几何特征地酬乃z 6 j 由一组环境路标特征组成，每一个路标特征用一个几何中南大学博学位论文第一章绪论原型，如：点、线、面等来近似，如图1 2 ( b ) 。由于既能提供定位所需要的度量信息且存储量相对较小，有利于位置估计和目标识别，近年有很多s l a m 研究采用几何特征地图。该类方法的难点主要包括如何从机器人收集的环境感知信息中提取出抽象的几何特征，以及定位与模型更新时如何根据观测到的路标在地图中寻找对应的匹配，即数据关联问题。而且提取特征需要对感知信息作额外的处理，需要一定数量的感知数据才能得到结果口”。在室内环境中，可以将环境定义为更加抽象化的几何特征，如面、角、边的集合或者墙壁、走廊、门、房间等。一般来说，室外环境的特征提取比较困难，特征地图比较适合于室内结构化的环境描述。c o ) 特征地图( c 1 拓扑地囤图1 - 2 基于二维传感器掏建的地图模型第二种地图表示形式是拓扑地图，如图1 - 2 r c l 。拓扑地图最开始由b r o o k s ，m a t a r i c 等研究者提出，用顶点和边来描述空间中各种物体之间或不同环境之间的关系，并没有一个明显的尺度概念。拓扑地图通常用图表表示，需要的存储空问小利用其进行路径规划效率很高，适合于大规模环境下的应用。然而由于无中南大学博士学位论文第一章绪论精确的尺度信息，因此并不适合机器人的定位【2 7 】。当环境中存在两个很相似的地方时，拓扑图的方法将很难确定这是否为同一节点( 特别是移动机器人从不同的路径到达这些节点时) 。广义v o r o n o i 图f 2 8 , 2 9 ( g e n e r a l i z e dv o r o n o ig r a p h ，g v g )是用得比较多的拓扑地图表示方法，常用来表示路标之间的联系( 路径) 。第三种地图表示方法综合了度量地图和拓扑地图各自的优点。t h r u n 提出了一种从全局度量地图中提取拓扑特征的方法【3 0 1 ，在机器人导航过程中，采用声纳传感器的距离信息建立反映环境特征的节点，将定位与环境拓扑的生成同时进行1 3 。y e a p 提出一种从局部度量地图中提取全局拓扑结构图的方法【3 2 】，即局部地图采用占用栅格地图表示，在路径规划中采用局部的与全局的二个层次规划，即把规划分为基于占用栅格的区域规划与基于拓扑连接关系的全局规划。这种混合方法在全局空间采取拓扑描述以保证全局连续性，而在具体局部环境中则采用几何表述有利于发挥移动机器人精确定位的优势【3 3 1 ，但是这种方法一般只适合表示室内环境。动态未知环境中由于运动障碍的存在，提取路标时容易出现问题。1 3 3 移动机器人同时定位与建图移动机器人同时定位与建图( s i m u l t a n e o u sl o c a l i z a t i o na n dm a pb u i l d i n g ，s l 削) 问题可以描述为：移动机器人从一个未知的位置出发，在不断运动过程中根据自身位姿估计和传感器对环境的感知构建增量式地图，同时利用该地图更新自己的定位。定位与增量式建图融为一体，而不是独立的两个阶段。s m i t hr 、s e l f m 、c h e e s e m a np 于1 9 8 6 年提出基于e k f ( e x t e n d e dk a l m a nf i l t e r ) 的s t o c h a s t i cm a p p i n g 方法1 3 引，揭开了s l a m 研究的序幕。在以后的十几年中，研究范围不断扩大：从有人工路标到完全自主、从户内到户外，出现许多s l a m 方法。由于自主机器人固有的特点( 缺乏自身位置和环境的先验信息；靠外部和内部传感器获得知识；环境、传感器信息及机器人运动本身具有不确定性) ，各种s l a m 方法归纳起来都是一个“估计一校正 的过程。应用运动模型和观测模型，基于e k f 的建图与定位可以归纳为一个循环迭代的估计一校正过程。首先通过运动模型估计机器人的新位置，并通过观测模型估计可能观测的环境特征，然后计算实际观测和估计观测间的误差，综合系统协方差计算卡尔曼滤波参数，并用其对前面估计的机器人位置进行校正，最后将新观测的环境特征加入地图。机器人移动过程中循环不断地估计一校正，尽量消除累积误差，得到尽可能准确的定位和地图信息。e k f 算法在处理不确定信息方面有独到之处，因此受到机器人导航领域的广泛欢迎。自诞生以来，针对各种传感器的e k f 研究层出不穷，e k f 成为事实中南大学博士学位论文第一章绪论上最流行的s l a m 方法【3 5 3 6 ，3 7 ，3 8 , 3 9 1 ，并相继在室内、结构化道路、水下、小范围室外等环境取得成功。但由于e k f 在地图中包含了机器人和环境特征状态之间的协方差阵，为消除累积误差，每次估计和校正都要处理该矩阵，计算复杂度达到伙矿) ( 刀是环境特征的个数) ，严重制约了该方法应用于大规模环境。近几年很多研究致力于缩减e k f 的计算规模，可以将复杂度下降到o ( n 2 ) 。然而，随着环境特征的持续增加，计算资源仍然将不可避免地被耗尽。为使算法能运行更持久，可以在每个预测阶段只对局部区域计算，并计算一个代价，继而当机器人从一个区域运动到另一个区域时利用此局部地图和代价去更新全局地图【4 0 - 。该算法复杂度可下降到0 ( 菥) ，其中阳是子地图中环境特征的个数。最大相似性( m a x i m u ml i k e l i h o o de s t i m a t i o n ，m l e ) 方法是一种非常有效的系统估计算法【4 1 1 ，基于这种方法的机器人建图与定位问题可看作是机器人位置与环境特征位置的最大相似性估计问题。该算法包括两步：e s t e p ( e x p e c t a t i o n )和m s t e p ( m a x i m i z a t i o n ) 。定位过程首先利用运动模型估计在假定当前地图确定情况下，给定控制作用下机器人可能移动的新位置( e s t e p ) ：然后计算机器人在此位置形成的环境地图中每个环境特征同以往地图相比出现的频率( 作为最大相似性估计器) 。经过计算，较准确存在的环境特征在地图中的概率值增加了，而较准确不存在的环境特征在地图中的概率值降低了( m s t e p ) 。m l e 算法通过爬山算法在各时间步产生的所有地图中搜索最相似的地图，由于并不依赖某次观察的准确性，因此即使是环境特征无法清晰辨认的大规模环境m l e 也有能力建立一致性的地图，并且绕过数据相关性的问题。实际上，m l e 是目前解决数据关联问题的最佳方案。由此带来的问题是，m l e 必须花费大量的时间维护和搜索若干步子地图，因而无法像k f 那样增量式建立地图，不适合在线应用。针对e k f 不适合多模分布的实际问题及m l e 实现较困难等问题，t h r u n 等提出能够适应任意噪声分布、易实现的m o n t ec a r l o 定位，也称粒子滤波器定位1 4 2 ，4 3 , 4 4 , 4 5 , 4 6 1 ，基本思想是用一组滤波器来估计机器人的可能位置( 处于该位置的概率) ，每个滤波器对应一个位置，利用观测对每个滤波器进行加权传播，从而使最有可能的位置的概率越来越高。它很容易实现，而且不象e k f 那样受限于噪声高斯分布，在很多定位问题中，如位置跟踪、全局定位甚至绑架( k i d n a pp r o b l e m ) 4 7 】问题，都取得较好的应用。基于粒子滤波器的s l a m 有一个重要的前提，即环境特征的观测只与机器人当前位置有关。在此前提下，可以将s l a m 问题分解成两个相对独立的问题：机器人定位问题和基于机器人估计位置的环境特征估计问题【4 8 , 4 9 1 。文献【5 0 】使用类似标准s l a m 的算法，但处理环境特征时采用了不同的方法。每个粒子滤波器不管是否真正存在k 个特征，都产生k 个粒子滤波器表示环境特征。这些粒子6中南大学博士学位论文第一章绪论滤波器的状态在一定时间步保留，当机器人经过若干步的估计更新获得了一个理想的环境特征位置估计后可以将相关粒子抛弃。文献【5 l 】使用r a o b l a c k w e l l i s e d滤波器作为粒子滤波器，估计机器人的移动路径。由于r a o - b l a c k w e l l i s e d 滤波器计算简便，因此减少了算法的计算量，并取得较好的效果。1 3 4 动态环境下s l a m 技术所谓动态环境是指移动机器人的工作环境中除了有静止不动的物体外，还存在动态障碍物，如行人、办公室中桌椅的临时变动、门的开关、垃圾箱的移位等。动态障碍物的存在势必影响移动机器人传感器的读数，产生不准确的环境地图。动态环境中移动机器人的地图构建涉及到的问题有传感器的选择、动态障碍物的辨识、地图的表示、机器人的定位、动态障碍物的跟踪、数据关联、地图的更新和不确定性的处理等。此外，移动机器人还面临着稳定性一可塑性两难 s 2 i ( s t a b i l i t y - p l a s t i c i t yd i l e m m a ) i 廿- 题，即移动机器人不仅需要保留原有环境信息，而且还要适应新环境的变化。目前对动态环境中移动机器人地图构建研究较多的主要有美国的卡耐基梅隆大学( c a r n e g i em e l l o nu n i v e r s i t y , c m u ) 、南加州大学( u n i v e r s i t yo fs o u t hc a l i f o m i a ，u s c ) 、斯坦福大学( s t a n f o r du n i v e r s i t y ，s u ) 以及德国的波恩大学( u n i v e r s i t yo f b o n n ，u b ) 、弗赖堡大学( u n i v e r s i t yo f f r e i b u r g ，u f ) 等。由于动态环境中移动机器人的地图构建涉及的问题多而复杂，目前对这个问题的研究还没有系统性的理论和方法。现有的处理方法是在s l a m 技术的基础上，结合检测、跟踪运动障碍物或直接过滤动态目标来实现移动机器人的地图构建，地图表示大部分选用占用栅格，将静态环境中的s l a m 技术扩展到动态环境 5 3 , 5 4 , 5 5 , 5 6 , 5 7 , 5 8 , 5 9 。对检测到的动态障碍物的处理主要分为两大类型：一是将动态障碍物当作噪声处理1 5 4 , 5 6 , 5 7 , 5 8 , 6 0 ，只对环境中的静态实体创建地图；二是将动态障碍物看作环境的一部分，同时对环境的动态部分和静态部分构建地图 5 3 , 5 5 , 5 9 ，力图提供整个环境的全面信息。a n d r a d e c e t t o ，7 】提出了一种在室内动态环境中进行并发定位与建图的方法。该方法基于扩展卡尔曼滤波器，结合传感器的读数、动作指令和当前地图的状态，在构建地图时估计移动机器人的位置。不同于基于栅格的技术，该方法具有伸缩不变性，对路标的分布不作任何的假设，但只能对适度变化的室内动态环境有效。h i i l l _ n e l 教授等人【5 8 】提出了一种在行人走动频繁的动态环境中建立地图的方法。应用基于样本的联合概率数据关联滤波器( s a m p l e b a s e dj o i n tp r o b a b i l i s t i ed a t a a s s o c i a t i o nf i l t e r s ，s j p d a f s ) 方法跟踪环境中频繁走动的人，把跟踪的结果7中南大学博士学位论文第一章绪论集成到扫描匹配和地图生成的过程中，但该方法不能区分慢速走动的行人。文献【6 1 ，6 2 】采用离线期望最大化算法( e x p e c t a t i o n - m a x i m i z a t i o n a l g o r i t h m ，e m a ) 来区分静态物体和动态物体。在e s t e p 阶段，估计观测数据中哪些数据可能对应于环境中的静态物体。在m s t e p 阶段，使用e s t e p 得到的估计结果确定机器人的位姿。该算法能够去掉环境中的动态干扰部分，环境建图的质量大大提高，但实时性不强。c m u 大学w a n g 等人【5 4 j 首次提出结合同时定位与建图( s l a m ) 和运动物体检测与跟踪( d e t e c t i o na n dt r a c k i n gm o v i n go b j e c t s ，d a t m o ) 的思想，利用了s l a m 和d a t m o 各自的优点。其核心思想是建立两个局部栅格地图，一个静态物体的栅格地图，一个动态物体的栅格地图，此外建立一个动态物体的链表。在其自行设计的移动驾驶车n a v l a b l l 上进行了多次实验，证实了该方法的可行性。w a n g 等人1 5 州随后推出了该方法的贝叶斯公式，使之具有坚实的理论基础。该贝叶斯公式的推导基于两个假设：一是机器人传感器的观测信息可以分解为静态观测信息和动态观测信息；二是忽略由于环境中运动障碍物的存在对地图和机器人的位姿估计所造成的影响。然而，这两个假设条件并非总是成立。以上几种处理方式并不能在地图上表示动态障碍物，只对环境中的静态部分建立地图，因而适用场合比较窄，应用受限。如何同时对环境中的静态部分和动态部分建图，这个问题引起了研究者的广泛关注。b i s w a s 等人1 6 0 j 提出了一种在非静态环境中进行地图构建的机器人对象建图方法( r o b o t o b j e c t m a p p i n g a l g o r i t h m ，r o m a ) 。该方法用局部占用栅格地图对动态物体建立模型，采用地图差分技术检测环境的动态变化，应用期望最大化算法来学习动态物体的模型，估计动态物体的数目应用了贝叶斯复杂性度量方法( b a y e s i a nc o m p l e x i t ym e a s u r e ) 。r o m a 方法能够很好地学习动态物体的模型，然而非静态物体的移动速度必须足够慢，物体不能靠的太近而且在预处理阶段必须容易分割。受办公室环境中许多物体具有相似性的启发，文献 6 3 】提出了一种建立非静态环境下分层对象( h i e r a r c h i c a lo b j e c t s ) 地图的方法。非静态对象的生成层次模型具有两层：上层是用来描述物体的通用形状特征的类模板，下层则对应于不同形状的物体对象。这种分层对象地图方法能够很好地学习类似物体的模型，但仅学习物体的形状特征，如果是在不规则物体的非结构化的室外复杂环境中，类模板的使用受到了很大的限制。m o n t e s a n o t 删在w a n g 等人工作的基础上，对s l a m d a t m o 做了一些改进，引入了二元分类变量，在估计阶段加入了区分障碍物性质的功能，移动机器人构建地图的性能得到了提高。南加利福尼亚大学的w b l f 等人1 5 3 j 提出用两个占用栅格地图对环境中的静态中南大学博士学位论文第一章绪论物体和动态物体分别建模。采用基于物体大小的分类器检测和跟踪运动障碍物，但是定位是已知的，且障碍物的大小必须明显不同。w o l f 等人随后改进了上述方法，增加了基于特征定位的功能，提出了一种在线同时定位和建图的算法【6 】，但仍然是使用已知定位信息。2 0 0 5 年，w o l f 等人又对上述算法进行