（模式识别与智能系统专业论文）非确定环境中鲁棒地图创建方法研究.pdf

摘要 摘要 非确定性环境中的地图创建是一个重要而又没有得以解决的问题。为了提 高非确定性环境中地图创建系统的鲁棒性，本文对同步定位与地图创建( s l a m ： 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 ) 问题的多个角度进行深入讨论和研究。 去除环境的歧义性是提高鲁棒性的关键。本文首先提出了一种针对激光测 距仪的基于h a r r i s 特征点探测法的新方法，这种方法可以在几乎没有先验信息 的情况下从非结构化环境中提取高度稳定和具有高重复度的特征。与传统方法 相比，本文提出的方法可以普遍的适用于几乎所有环境之中，提取出更为丰富 的环境特征，与此同时，探测到的特征具有自身的属性，对特征的基于属性的 选择可以在不显著增加系统负担的前提下提高系统的鲁棒性。 数据关联方法的鲁棒性直接影响着地图创建系统的鲁棒性。本文提出了一 种解耦的联合相容性验证方法。该方法充分利用了观测中距离和角度噪声的独 立性和系统状态预测步骤中不确定性单调递增的性质，通过将预测位姿与匹配 位姿之间的新息引入数据关联过程对数据关联问题进行了分解，从而在保证方 法鲁棒性的同时将数据关联的复杂度从d ( 册2 ) 降低到o ( a 2i i 口) ，此处p ，玎和d 分别表示数据关联对的总量，路标点的总量和环境的维数。 针对动态环境对地图创建系统鲁棒性的巨大影响，本文提出了一种基于 h o p f i e l d 神经网络的s l a m 求解方法。这种方法采用了一种生物激励的策略一 强化记忆和逐渐遗：怎，而不是显示的去区分动态和静态障碍物。这种新策略去 除了传统动态s l a m 方法对动态目标的速度、数量等的要求，提高了对环境的 识别能力，提高了创建地图的一致性，从而极大的增强了地图创建系统的鲁棒 性。 为了应对地图创建过程中可能遇到的不可预测因素对地图创建的影响，如 机器人绑架，本文提出了一种松散耦合的无线传感器网络辅助的s l a m 架构。 该架构在应用对鲁棒性要求极高且不存在全局定位系统的情况下，让机器人在 地图创建的过程中动态布撒无线传感器网络节点并对其定位。这些节点构成的 网络对环境的划分可以降低环境的歧义性，对机器人位姿进行纠错，从而提高 系统抵御不可预测影响的能力。 本文在软件仿真、真实环境和经典数据集中验证了文中所提出的方法的有 效性和效率。这些方法可以单独的应用于地图创建问题的多个方面，同时又是 一个可以用以构建地图创建系统的有机整体。 关键字：同步定位与地图创建，鲁棒性，非确定环境，特征提取，数据关 联，神经网络，无线传感器网络 i a b s t r a c t a b s t r a c t m a p p i n gi n u n c o n s t r u c t e de n v i r o n m e n t si saf u n d a m e n t a la n du n s o l v e d p r o b l e m i no r d e rt oi m p r o v et h er o b u s t n e s so fm a p p i n gs y s t e m si nu n s t r u c t u r e d e n v i r o n m e n t s ，t h et h e s i sd i s c u s s e sa n ds t u d i e ss e v e r a la s p e c t so ft h es l a m ( 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 ) p r o b l e m d i s a m b i g u a t i n ge n v i r o n m e n t si st h ek e yt oi m p r o v et h er o b u s t n e s s t h et h e s i s p r o p o s e san o v e lh a r r i sc o m e rd e t e c t o rb a s e da l g o r i t h ma i m i n ga te x t r a c t i n gh i g h l y s t a b l ea n dr e p e a t a b l ef e a t u r e sf r o ml a s e r a l m o s tn op r i o rk n o w l e d g e c o m p a r i n g s c a n si nu n s t r u c t u r e de n v i r o n m e n t sw i t h w i t ht r a d i t i o n a lm e t h o d s ，t h ep r o p o s e d m e t h o dc a nb eg e n e r a l l ya p p l i e dt oa l le n v i r o n m e n ta n da c h i e v em u c hr i c h e rf e a t u r e s a n d ，a tt h es a m et i m e ，t h ed e t e c t e df e a t u r e sh a v ea t t r i b u t e s a t t r i b u t e sb a s e d s e l e c t i o nt of e a t u r e sc a ni n c r e a s er o b u s t n e s sa n da d da l m o s tn oe x t r ab u r d e n st o m a p p i n gs y s t e m s t h er o b u s t n e s so ft h ed a t aa s s o c i a t i o ns t e pd e ci d e st h e r o b u s t n e s so ft h e m a p p i n gs y s t e m t h et h e s i sp r o p o s e sad e c o u p l e dj o i n tc o m p a t i b i l i t yt e s td a t a a s s o c i a t i o nm e t h o d n o t i c i n gt h ei n d e p e n d e n c eb e t w e e nr a n g ea n da n g l eo b s e r v a t i o n a n dt h em o n o t o n ei n c r e a s eo fp o s eu n c e r t a i n t yi nt i m eu p d a t es t e p s ，a n dt h r o u g h i n t r o d u c i n gt h e i n n o v a t i o nb e t w e e ne s t i m a t e dp o s ea n dt h em a t c h e dp o s e ，t h e p r o p o s e dm e t h o dd e c o u p l e dt h ed a t aa s s o c i a t i o np r o b l e m 。t h e r e f o r e ，t h ep r o p o s e d m e t h o dd e c r e a s e st h ec o m p u t a t i o nc o m p l e x i t yo fd a t aa s s o c i a t i o na l g o r i t h m sf r o m o ( p n 2 ) t oo ( d 2 p ) w i t h o u ti m p a i rt h er o b u s t n e s s ，w h e r ep ，za n dd d e n o t et h e a m o u n to fh y p o t h e s e s ，t h ea m o u n to fl a n d m a r k sa n dt h ed i m e n s i o n a l i t yo ft h e e n v i r o n m e n t ，r e s p e c t i v e l y t od e c r e a s et h ei n f l u e n c ec a m ef r o md y n a m i c so fe n v i r o n m e n t s ，t h et h e s i s p r o p o s e san o v e lh o p f i e l dn e u r a ln e t w o r kb a s e ds l a ms o l u t i o n i ns t e a do f a p p a r e n t l yd i s t i n g u i s hd y n a m i co b j e c t s ，t h ep r o p o s e dm e t h o da d o p t sab i o l o g i c a l l y i n s p i r e ds t r a t e g y ：e n f o r c e dm e m o r ya n dg r a d u a l l yf o r g e t t i n g t h ep r o p o s e dm e t h o d e l i m i n a t e st r a d i t i o n a lr e q u i r e m e n t so nt h ev e l o c i t ya n da m o u n to fd y n a m i co b j e c t s ， i m p r o v e st h ea b i l i t yt od i s t i n g u i s he n v i r o n m e n t ，a n di n c r e a s e st h ec o n s i s t e n c eo f c o n s t r u c t e dm a p s c o n s e q u e n t i a l ly t h er o b u s t n e s s o ft h em a p p i n gs y s t e mi s i n c r e a s e d t od e a lw i t hi m p a c tf r o mu n p r e d i c t a b l ei n f l u e n c e s ，l i k er o b o tk i d n a p p i n g ，t h e a b s t r a c t t h e s i sa l s op r o p o s e sal o o s e l yc o u p l e df r a m e w o r kt h a tu s e dw i r e l e s ss e n s o rn e t w o r k ( w s n ) n o d e sa sa na u x i l i a r yt os l a ms y s t e m i nt h ea p p l i c a t i o nc o n t e x t st h a tt h e r o b u s t n e s si sh i g h l yd e s i r e da n dg l o b a ll o c a l i z a t i o ns y s t e m sa r en o ta v a i l a b l e ；t h e r o b o td y n a m i c a l l ys e t su pa n dl o c a l i z e sw s nn o d e s w h i l ei ti sm a p p i n gt h e e n v i r o n m e n t t h en o d e sa c t u a l l ys e g m e n tt h ee n v i r o n m e n t ，s o ，t h ep o s ec a nb e i m p r o v e d ，a n dt h e r o b u s t n e s si sa l s oi m p r o v e d t h ep r o p o s e dm e t h o d sa r et e s t e di ns i m u l a t e de n v i r o n m e n t s ，r e a le n v i r o n m e n t s a n dc l a s s i c a ld a t as e t st ov a l i d a t et h e ma n dt e s t i f yt h ee f f i c i e n c y t h e s em e t h o d sc a n b ea p p l i e di n d i v i d u a l l yt oa s p e c t so fs l a mp r o b l e m ，a n d ，a tt h es a m et i m e ，t h e yc a n b eu s e dt oc o n s t r u c tac o m p l e t e dm a p p i n gs y s t e m k e yw o r d s ：s l a m ，r o b u s t n e s s ，u n s t r u c t u r e de n v i r o n m e n t ，f e a t u r ed e t e c t i o n ，d a t a a s s o c i a t i o n ，n e u r a ln e t w o r k s ，w i r e l e s ss e n s o rn e t w o r k 1 1 1 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：签字日期：堡丝! 竺：生! 垒 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中 国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 刮从开口保密( 年) 作者签名： 埤 签字日期：丝! ! ：最： 铷躲该奁铷签名：! 继丝 签字日期：2 坦二厶：垒 第1 章绪论 第一章绪论 1 。1论文选题及研究意义 移动机器人必须回答这样的问题：我周围的世界是什么样的? 【l 】在近来的 三十年间，机器人地图创建问题的研究是机器人学及人工智能领域内一个高度 活跃的研究方向，并且对以上问题做出了初步的回答。【l 】 机器人地图创建的研究已经有很长的历史。在二十世纪八十年代和九十年 代初期，地图创建领域的研究主要集中在对地图描述方法的研究上，具体可分 为基于度量地图的方法和基于拓扑地图的方法。度量地图精细的描述了环境的 儿何信息：拓扑地图则着重捕述环境的连通性。度量地图的代表性研究是单元 格地图创建算法( o c c u p a n c yg r i dm a p p i n ga l g o r i t h m ) 【2 1 1 3 1 1 4 1 ，这种方法将环 境细致的划分为状态为空白或山用的单元格。这种算法被广泛的应用于机器人 系统之中。 5 】 6 】【7 】 8 】f 9 】 1 0 】 11 1 1 1 2 】拓扑地图将环境表示为一组连接起来的地 点，研究工作包括 1 3 1 、【1 4 1 和 1 3 1 4 1 1 5 1 1 6 】【1 7 1 1 1 8 】【1 9 】 2 0 】【2 1 】【2 l 】 2 3 1 1 2 4 1 。 事实上，度量地图和拓扑地图之间的区分并不是那么的清晰：真正可用的拓扑 地图中总是需要引入度量信息。 在同一时期，对地图创建系统的第二种分类法是将其分为世界中心地图和 机器人中心地图。世界中心地图是在全局坐标空间内表示地图。机器人- 心地 图在度量空间内描述世界。比较而言，机= 人中心地图容易创建，但是，它有 两个缺点：第一，它难以从已知的观测中推断详尽的观测；第二，如果不同地 点之间非常相似，机器人中心地图系统难以对他们进行区分。所以，在这两种 方法之间，世界中心地图更为常用。 从二十世纪九十年代开始，基于概率方法的机器人学逐渐成为了领域内研 究的主流方法。s m i t h 、s e l f 和c h e e s e m a n 等人的一系列关于利用统计学方法来 同步的解决地图创建问题和定位问题的论文奠定了同步定位与地图创建 ( s l a m ：s i m u l t a n e o u s l o c a l i z a t i o n a n d m a p p i n g ) 问题研究的基础。自此后， s l a m 问题的研究几乎成为了地图创建问题的代名词。 2 5 2 6 】s l a m 问题早 期的研究多数采用了基于卡尔曼滤波算法族的方法。 2 7 2 8 2 9 3 0 3 l 】【3 2 3 3 】 这些方法地图创建的结果通常为一个包含路标点位置和相应不确定度的列表。 随后，基于d e m p s t e r 的极大似然法的方法被引入s l a m 领域来解决所谓的数 据关联问题，也就是决定一组观测和一组路标点是否来源于相同的物理特征的 问题。 3 4 】【2 l 】【3 5 】【3 6 】【3 7 】之后，注意到s l a m 问题的结构与图论之间的相似 】 第l 章绪论 性，学者们提出了一系列基于图论的s l a m 算法。【5 3 s 4 与此同时，学者们发 现了与协方差矩阵不同，s l a m 问题所对应的信息矩阵是天然稀疏的，特别是 在经过一定的预处理后，这种稀疏性更加明显，从而可以极大的简化s l a m 问 题的计算复杂度，所以，s l a m 领域中涌现出了大量的基于信息矩阵的方法。 这些方法的出现，将机器人地图创建问题的研究推到了一个前所未及的顶峰。 【3 8 3 9 4 0 4 1 】 然而，真实世界是复杂的、动态的、充满了杂乱性；机器人的移动是不精 确的，受到环境条件、时间等诸多因素的影响，而观测总是充满噪声的，所以， 地图创建问题是复杂的。如何对真实不确定环境进行地图创建，仍然是一个没 有完全回答，而又一定要去回答的问题。【l 】 本论文的研究来源于两个课题：国家自然科学基金重点项目“月球探测系统 的建模、传感、导航和控制基础理论及关键技术研究”和美国国防部澳大利业 国防科技署联合项目“多自土地面机器人国际竞赛”( m a g i c ：m u l t i a u t o n o m o u sg r o u n d r o b o t i cin t e r n a t i o n a lc h a ll e n g e ) 。 “月球探测系统的建模、传感、导航和控制基础理论及关键技术研究”项目 中，重点研究月球探测器的软着陆控制算法，基于光、电、力传感器和无线传 感器网络技术的月球探测系统定位和导航系统，由远程遥控和局域自主控制相 结合的两级控制策略，月球探测系统的数字模型多媒体仿真以及由仿月面实验 场地和月球车组成的地面仿月面试验基地。我们可以看出，该项目中的研究依 赖于对月面环境的了解。而目前我们对月面的了解还远没有达到可以为机器人 提供导航的程度，所以，我们就需要对非确定环境中地图创建问题的鲁棒性进 行深入的研究。 “多自主地面机器人国际竞赛”项目旨在让移动机器人在动态环境中自主地 完成探测、追踪、消灭等一系列任务。这个动态环境同时包括建筑物内( 人造 环境) 及自然环境，机器人的任务完成高度的依赖与对环境的认知程度，而环 境的地图创建精度本身就是竞赛评分的重要标准之一。所以，成功的让机器人 在较人的工作空间内( 约八十万平方米) 长时间的进行地图创建任务( 约三个 半小时) 也需要对非确定环境中地图创建问题的鲁棒性进行深入的研究。 1 2 同步定位与地图创建问题研究现状及难题 1 2 1 研究现状 s l a m 问题研究了这样一个过程，移动机器人在未知环境中感知环境，将 2 第l 章绪论 感知信息干勾建成地图，并同时根据这个地图对自身进行位置修正。s l a m 问题 被看做通向移动机器人真正自主性的道路因此，s i 。a m 问题的解被看做移动 机器人领域的圣杯。4 2 1 s l a m 问题被模型化为几种不同的形式，冈此，也有基于几种不同理论的 解。s l a m 问题也被应用于不同帆器人平台之中如室内机器人、室外机器人、 水f 机器人及空中机器人等。 ( a ) 室内机器a 4 4o ) 室外机器人【4 5 】 0 ) 水下机器人 4 7 】( 由空中机器人 4 8 】 留l _ 1s 问厦的不同应用颁域 f i g1 1d i f f e r e n ta p p l i c a t i o n so fs l a m 最初的s l a m 问题在】9 8 6 年的j e e e 机器 与自动化大会上被提出。4 9 1 在这次大会上学者们就s l a m 问题的研究意义达成了共识：一致的基于概率 方法的地图创建是机器人领域的基础问题自此，s l a m 问题的研究呀就拉开 了序幕并激起了越来越热烈的讨论。 121l s l a m 问题公式化描述 s l a m 问题描述了卟耦合的过程：机器人利用自身位置和当前观测创建 地图，于此同时，利用创建的地图和当前观测对自身进行定位。在这个过程中， 机器人的轨迹和路标点的位置在没有先验位置知识的情况下在线的进行估计。 第1 苹绪论 4 2 4 3 图12s l a m 问题描述的过程 4 4 f i g12t h ep r o c e s ss l a md e s c r i b e d 考虑机器人在环境中移动并观察到来知路标点的过程如图i2 所示，图中 黑色三角表示机器人的轨迹，红色直线表示轨迹之间形成的关联。所以完整 的s l a m 问题可以用式进行描述。【4 2 p ( x ， jz 。u ，) ( 1 1 ) 其中： o 一。= “，与，耳 表示机器人的轨迹； 一= l u , k ，k 表示观测到的路标点： z o = z o ，= ” 表示得到的观测； u = “，h 2 ，“。) 表不机器人的移动量： o 矗表示机器人的初始位置。 这个概率形式的表述描述了s l a m 系统对状态空间变量进行联合的后验估计的 实质。 第l 章绪论 这个过程中包含了两个重要的模型。第一个模型是观测模型，它描述了当 机器人位置和路标点己知的时候得到对应观测的概率，这个概率描述如式1 2 。 p ( z i 以，脚) ( 1 2 ) 在s l a m 中我们认为，如果机器人位置和路标点位置是确定的，观测之间是条 件独立的。 第二个重要的模型是移动模型。移动模型描述了机器人位姿的状态转移概 率，如式1 3 所示。 尸( 吒l 赡- l u ) ( 1 3 ) 我们可以看出，机器人移动模型被看做是一个马尔科夫过程：机器人的当前位 姿仅依赖于前一时刻的机器人位姿及当前的控制输入，与观测和地图无关。 综合而言，s l a m 算法总是对这两步顺序的执行，也就形成了所谓的时间 更新与观测更新过程，如式1 4 所示。 p ( x ，m iz o ：i ，u ： ，x o ) = l p ( x kl 以- l ) x 尸( 吒1 m iz o ： ，u j ：，x o ) d x k i 讹，朋iz o ：k , u 。：k , x o ) = 型笔箍掣 “4 1 2 1 2 经典s l a m 问题地图优化算法 s l a m 中地图优化问题的研究就是找出对式1 2 及式1 3 的合理描述方法， 进而可以高效的解决式1 4 中所描述的优化过程。继今为止，最常用的表示方 式是将1 2 和1 3 看做一个确定过程加上高斯噪声，这种表示方法也衍生出了继 今为止研究的最多、最为广泛的s l a m 方法：基于卡尔曼滤波的s l a m 地图优 化方法。 a 基于卡尔曼滤波的地图优化方法 基于卡尔曼滤波的s l a m 算法将式1 3 描述为： 户( l 坼_ l 心) 吒= f ( x k i u ) + m ( 1 5 ) 式中：( ) 表示机器人运动学模型；咄表示均值为零且不互相关的运动噪声。 2 7 2 9 3 0 3 3 】 同样的，式1 2 被描述为： e ( z i 吒，m ) 营气= h ( x ，m ) + 。v k ( 1 6 ) 式中：办( ) 表示观测模型；v k 表示均值为零且不互相关的观测噪声。 【2 7 2 9 1 1 3 0 3 3 】 5 第l 章绪论 进而，s l a m 问题可以被捕述为： 毫廊。 = e x k , 小。lz 。】 叫乏厶x m ， “- 则，s l a m 过程包括两步，时间更新，如式1 8 所示，和观测更新，如式1 9 所示。 x kl 一l2 f ( x k i i k - i ，i l k ) ( 1 8 ) 匕川= w 咒删川可+ r 坟= ( ，一k 日) 只i 川 f1q ) k = 只i k - i h ：( 矾只肛。川+ b ) 根据线性化卡尔曼滤波器的方法不同，基于卡尔曼滤波的s l a m 方法又可 以分为基于扩展卡尔曼滤波( e x t e n d e dk a l m a nf i l t e r ) 的方法和基于无迹卡尔曼 滤波的方法( u n c e n t e dk a l m a nf i l t e r ) 。 2 7 2 8 3 0 针对卡尔曼滤波方法族的计 算效率与状态空间中的估计量的平方成正比的特点，学者们还提出了基于拓扑 度量地图和基于子地图的方法以提高计算效率。 5 0 】 b基于r a o - bla c k w ei iis e s 滤波器的地图优化方法 将式1 3 表示为一组粒子而采用蒙特卡洛方法进行求解就衍生出了另外一 类方法：基于粒子滤波器的s l a m 算法，其中的代表就是f a s t s l a m 。这类方 法不要求噪声是加性的高斯噪声，也不要求模型的线性性( 粒子滤波部分) ，因 而也更为通用。【5 1 】 5 2 】 基于粒子滤波的地图优化方法与基于卡尔曼滤波的方法完全不同：这种方 法直接的利用粒子来表示非线性和非高斯的机器人位姿分布。由于s l a m 问题 状态空间的高维数，直接利用粒子滤波器来解决完整的s l a m 问题是不可行的。 但是，在对s l a m 问题r a o b l a c k w e l l i s a t i o n 化后，利用概率方法中的乘法律， s l a m 问题的联合状态就被分解成了两个部分：机器人轨迹的分布估计和基于 机器人轨迹的路标点联合分布。而路标点在机器人轨迹确定的状态下，是相互 独立的，从而，整个s l a m 问题得到了分解，而唯一需要用粒子去模拟其分布 的，就是机器人的位姿。 以上描述的过程可以用概率形式表示为式1 1 0 ： p ( 托 miz o ：女，：i ，x o ) = p ( ml 托 z o ： ) p ( x 姒lz 0 扣x o ) ( 1 io ) 需要注意的是，此处概率分布基于机器人的轨迹x 姒，而不是机器人当前 位姿以，这是因为仅在整个轨迹己知的情况下，状态空间中的路标点之间的相 6 第l 章绪论 关性才能被分解。这种对问题的分解使得f a s t s l a m 方法的计算效率非常高： 其中的地图表示是一组分布独立的路标点，所以对地图更新的计算复杂度是路 标点总数的线性函数。 f a s t s l a m 是基于粒子滤波的地图优化方法的杰出代表。在f a s t s l a m l 0 中，建议分布采用了状态空间模型中的运动模型： “p ( x i ! 。，u 。) ( 1 1 1 ) 进而，粒子的权值由式1 1 2 描述方法进行评估： 以= 皑。p ( z 。i 剐_ ! 2 ，z o ：) ( 1 1 2 ) 在f a s t s l a m 2 0 中，建议分布进行了改进，需求的粒子数量减少，所以， 系统的效率得以提高。 “p ( x kl 三，z o ：t ，) ( 1 1 3 ) 此处：p ( x ki ! 。，z o ：，) = 去尸( 乙i 以，x o ( ：0 h ，z o ：) 尸( l 三，) 。 基于粒子滤波的s l a m 方法给出了求解s l a m 问题的新思路，但是，从统 计学角度来说，由于f a s t s l a m 方法不能忘记历史信息，粒子退化现象是不可 避免的。对状态变量的分解同时也引入了对位姿和观测的历史数据的依赖，所 以，当重采样步骤使历史衰竭后，这种方法就失去的统计意义上的精确性。【4 2 】 c基于信息矩阵f l 勺s l a m 地图优化方法 将1 2 和1 3 以信息矩阵型式进行描述可以得到更稀疏的相关性矩阵，因而 也也衍生出了另外一类重要的s l a m 方法，基于信息矩阵的s l a m 方法。 式1 1 4 描述了信息矩阵方法与基于协方差矩阵方法对s l a m 问题表述上的 不同。 加= 蚴匮船阱险铷 此处：人= p 一，7 = a “。 这种表示上的差异带来了边际化及条件概率的计算上的不同，如表1 1 所 示。 在协方差矩阵表述情况下，协方差矩阵总是稠密的，而在信息矩阵形式的 表述中，通过适当的重排序及忽略状态变量之问的微小的联系，信息矩阵可以 非常稀疏，从而，基于信息矩阵的s l a m 方法的计算效率要比基于协方差矩阵 的高。【3 8 3 9 4 0 41 】 7 第l 章绪沦 表1 1 协方差矩阵形式与信息矩阵型式对高斯分布的边际化及条件概率计算对比 t a b 1 1c o m p a r i s o nt ot h ed i f f e r e n c eo fm a r g i n a l i z a t i o na n dc o n d i t i o n i n g 边际化条件概率 p ( 口) = p ( 口，b ) d b p ( a l b ) = p ( a ，b ) p ( 6 ) p 2 p o= 觞+ 只6 尸：( 6 一心) 协方差形式 p=op = 只。一匕吃吃 r = - a 曲人的- i 7 7 = 一人曲b 信息矩阵形式 人= 人人曲人6 - 6 1 人6 口 人= 人。 d 基于图论i 妁s l a m 地图优化方法 最后，注意到用以描述s l a m 问题的动态贝叶斯网络与图之间天然的相似 性，学者们还提出了基于图论方法的s l a m 算法。 s l a m 问题的贝叶斯网络模型如图3 1 所示。从图中我们可以看出，s l a m 问题中的需要估计的状态变量构成了图中的节点，这些节点之间的转移概率形 成了他们之间的边，由于机器人不断重复观测路标点，这些额外的约束为图中 增加了更多的边，从而，s l a m 问题就演变成了如何优化生成的图而使得图中 的平均误差最小的问题。【5 3 1 1 5 4 1 2 1 2s l a m 问题中的其他重要问题 s l a m 问题中的地图优化仅仅是s l a m 问题的一个部分。在s l a m 研究领 域，还存在特征提取、数据关联等重要问题。 4 2 4 3 】 a 特征提取 基于位姿的地图创建方法和基于特征的地图创建方法是s l a m 领域内的两 个主要分支。基于位姿的地图创建方法直接根据观测对位姿进行比较，进而形 成位姿之间的约束。从方法理论角度进行比较，基于位姿的地图创建方法的效 果等效于将基于特征点方法中的所有特征消去，因而会产生一个稠密的位姿图， 所以计算效率相对较低。【5 5 1 对效率的追求推动了特征提取方法的研究。在实际应用中，机器人可以采 用摄像头，激光雷达，雷达，红外传感器和超声传感器等诸多传感器，每种传 感器都具有自己的特点，相应的特征提取方法也不尽相同。无论采用何种传感 8 笳1 苹绪论 器，刘特征提取方法的要求都是致的：特征重复度高、精度高、速度快、描 述 ! _ 好、能充分去除环境的歧义性。【5 5 1 更具体的对于特征提取方法的讨论可见本义第二章第二节。 b 数据关联 在实用的s l a m 系统实现中数据关联总是最关键的问题。在机器人获取 了感知数据后，系统必须决定新的感知数据是否可以与已知路标点进行关联， 之后才能进行数据融合。旦进行数据融合，这个过程往往就不可逆转了。数 据关联的关键性体现在一次错误的数据关联就可阻导致整个滤波器的发散。而 不幸的是，在不确定性的环境中，数据关联问题口j 以非常复杂。图13 中展示 了个来源于m i td a r p a 数据集的数据关联场景，从图中我们可以大概的了 解数据关联问题的难度。 z f j 0 e 摹：眩 剿： 。：。i f： j：fi 圈l3 数据关联 “ f 1 di 3d a t aa s s o c i a t i o n 对数据关联方法的进一步讨论见本文第三章 嘧 第1 章绪论 1 2 2研究难题 在过去的- - = 十年间，学者们对s l a m 问题有了更深层次的认识，该领域 的研究也取得了长足的进步。 在小范围静态环境中，s l a m 系统运行时间短，环境中未知因素少，先验 知识简单易得，因此，目前s l a m 领域的研究人员普遍认为小范围静态简单环 境的s l a m 问题已经得到了解决。 4 2 1 1 4 3 】 大范围环境对s l a m 问题的挑战体现在三个方面：第一是对算法效率的要 求的提高，第二是对算法鲁棒性要求的提高，第三是轨迹闭合的难度增大。在 大范围环境中，s l a m 系统需要对更多状态变量进行优化，系统的计算复杂度 也就相应的增加了。同时，s l a m 系统运行时间的延长也对系统的鲁棒性提出 了更高的要求。此外，大范围环境中由于需要闭合的轨迹长度增加，相应的不 确定度也得到了增加，环境中出现相似子环境的概率也增加了，所以，轨迹闭 合的难度也相应增加。【5 6 1 1 5 7 动态环境中路标点位置与时间之间的相关性使s l a m 问题的结构更加复 杂。目前已有的方法仍难以解决动态s l a m 问题：基于目标追踪的方法难以完 善解决目标追中中的难题；将动态目标从系统中去除会增大系统的歧义性；发 展适用于动态环境的数据关联方法往往难以满足计算复杂度的要求。如何合理 的解决动态环境中的s l a m 问题，是当前s l a m 领域的研究难题之一。 1 3 本文的主要研究问题及研究成果 1 3 1主要研究问题 为了提高地图创建系统的鲁棒性，针对s l a m 问题中现存的研究难题，本文 主要从以下四个方面对地图创建问题进行了讨论。 1 3 1 1 特征提取方法 基于特征的s l a m 方法的诸多优势推动了对特征提取方法的研究。目前的 特征提取方法往往是针对环境特点的，因而需要一定的环境先验知识，以及根 据这些先验知识对特征提取方法进行调整。 特征点对s l a m 方法的影响是巨大的：过多的特征点会降低地图创建系统 效率，并给数据关联带来更大的难度：过少的特征点不足以对位姿进行修正， 会导致逐渐的滤波发散：不稳定的特征点具有过大的不确定性，对提高位姿精 度的帮助不大：虚假的特征点彳i 但会给系统增加彳i 必要的计算量，还极容易导 10 笳1 章绪论 致数据关联结果错误。要提高地图创建系统的鲁棒性，就要发展具有高重复度 的、高精度的、能提取适量特征的具有普遍适用性的特征提取方法。 1 3 1 2 数据关联方法 数据关联是s l a m 问题中的关键步骤。一方面，数据关联直接影响着滤波 稳定性，另外一个方面，数据关联的计算复杂度也是整个s l a m 方法计算复杂 度的主要组成部分之一。 现有的数据关联方法中，基于联合相容性测试的数据关联方法普遍被认为 是鲁棒性最高、正确性最好的方法。但是这种方法有这样三个问题：l ，它需要 了解完整联合协方差矩阵：2 ，它的计算复杂度比一些地图优化方法还要高：3 ， 由于它将协方差矩阵在估计位姿处进行展开，位姿估计误差极大的影响数据关 联结果。 所以，要提高地图创建系统的鲁棒性，就必须对数据关联方法进行更深入 的研究。 1 3 1 3 动态环境中的s l a m 问题解决 动态环境给s l a m 问题带来了新的挑战，这种新的挑战体现在两个方面。 第一个方面是动态目标增加了系统的复杂度。静态s l a m 问题中路标点的位置 保持卅、= 动，所以每次对路标点做出观测，路标点的不确定性就会降低，而在动 态环境中，如何处理路标点的位置和精度问题，给s l a m 问题增加了难度。第 二个方面表现在动态环境中的数据关联也更加困难。在动态环境中，动态目标 带给了我们更多的可能性，也就扩大了我们需要搜索的可能的求解空间，也同 时扩大了出现错误关联的可能性。 动态环境中的s l a m 问题是复杂的，不幸的是，绝大多数的真实环境都是 动态的。为了提高地图创建系统的鲁棒性，我们就必须对动态环境中的s l a m 问题进行研究。 1 3 1 4 不可预测因素对系统的影响 真实的地图创建工作中总是会存在这样或那样的不可预测的影响因素。要 提高地图创建系统的鲁棒性，就必须能够应对那些会导致系统错误的影响因素。 1 3 2研究成果 本文主要取得了以下研究成果： 提出了一种针对激光雷达测量数据的具有普遍适用性的特征提取方 法，该方法能在不要求环境先验知识的条件下稳定的提取高精度、高 第l 章绪论 重复度且可描述的特征点； 提出了一种快速的基于联合相容性测试的数据关联方法，该方法具有 与j c b b 相似的鲁棒性，但计算复杂度从j c b b 的降低到o ( p n 2 ) 降低 到o ( d 2 p ) ，此处p ，门和d 分别表示数据关联对的总量，路标点的总 量和环境的维数： 提出了- - j f e e 基于h o p f i e l d 神经网络的动态s l a m 解决方法，该方法在 不显示地区分动、静态障碍物的情况下可以有效的产生具有高度一致 性的地图。 提出了一种基于无线传感器网络的松散耦合的辅助地图创建架构，该 架构用于创建个类似与g p s 网络的全局定位系统，以减小地图创建 过程中各种不可预测的影响因素对系统鲁棒性的影响。 1 4 论文的结构 本文的组织结构如下： 第一章讨论了本文的选择地图创建鲁棒性研究作为研究课题的依据及意 义，同步定位与地图创建问题的研究现状及研究难题，以及本文的研究重点和 取得成果。 第二章集中讨论了地图创建系统中的环境去歧义问题，并在对一些经典特 征提取方法进行深入分析、研究的基础上提出了一种新颖的基于h a r r i s 角点探 测器的针对激光雷达数据的特征提取方法，并在经典数据集上对该方法进行了 验证和评估。 第三章重点分析了地图创建方法中的数据关联问题。在对已有数据关联方 法深入分析的基础上，通过对s l a m 问题结构的深入理解，提出了一种高效的 鲁棒的数据关联方法，并在仿真环境和真实环境中对该方法进行了验证。 第四章中，在对动态环境q ，s l a m 算法深入分析的基础上，受到生物处理 地图创建问题的启发，提出了一种基于h o p f i e l d 神经网络的s l a m 方法，并在 仿真环境和真实环境中对该方法进行了验证。 第五章中提出了一种基于无线传感器网络的松散耦合的地图创建系统架 构，以减小地图创建过程中不可预测因素对系统鲁棒性的影响，并利用仿真数 据对提出方法进行了验证和讨论。 最后一章对本文进行了总结，讨论了本文完成的主要工作及下一阶段我们 要做的相关工作。 1 2 第l 章绪论 参考文献 【1 】s t h r u n ，“r o b o t i cm a p p i n g ：as u r v e y ，”i ne x p l o r i n ga r t i f i c i a li n t e l l i g e n c ei nt h en e w m i l l e n i u m ，gl a k e m e y e ra n db n e b e l ，e d s m o r g a nk a u f m a n n ，2 0 0 2 【2 】a e l f e s s o n a r - b a s e dr e a l w o r l dm a p p i n ga n dn a v i g a t i o n i e e ej o u r n a lo fr o b o t i c sa n d a u t o m a t i o n ，r a 一3 ( 3 ) ：2 4 9 - 2 6 5 ，j u n ei9 8 7 【3 】a e l f e s o c c u p a n c yg r i d