（计算机应用技术专业论文）在动态环境中基于视觉的定位研究.pdf

摘要 摘要 “定位”，从广义上说，就是确定物体在某个特定环境中相对于其他参照物的 位置的过程。近年来，随着传感器技术、计算机技术的进步，定位问题越来越成 为了一个研究的热点问题。各种定位方法被广泛的应用于许多领域，比如机器 人学、移动机器人导航、计算机视觉、普适计算、无线( 传感器) 网络等。机器人 的定位问题甚至被认为是机器人导航问题中最基本的问题之一。 基于视觉的定位利用光学传感器的感知信息，将相对位置测量方法和绝对 位置测量方法结合起来使用。在动态环境中，传感器信息中包含很多不确定性， 需要一种概率化的方法去解决这样的问题。贝叶斯滤波就是这样的一个统计工 具，而卡尔曼滤波器和粒子滤波器都是属于其中。 本文提出了一种基于视觉的定位方法，蒙特卡罗扩展卡尔曼定位( m c l e k f ) 。这种方法是蒙特卡罗定位和扩展卡尔曼滤波器的结合，分别利用了人工 地标和自然地标的高噪声的传感器信息，结合无反馈的里程计信息来完成自身 定位。我们首先给出了蒙特卡罗定位的一个具体实现，融合多标志物的信息，并 提出新的计算权重和样本重采样方法，以适应动态不确定的环境中的问题( 例 如绑架的机器人问题) 。其次我们为地标建立卡尔曼滤波器，这样可以建立一个 实时的环境模型，这个实时环境中的信息会用m c l 的传感器模型中。另外，本 系统还对于自然地标的不唯一性做了特殊处理，对于传感器模型中处理单个或 者两个人工地标的方法做了阐释。 为了验证方法的有效性，本文在真实机器人( a i b oe r s 7 ) 上面设计了多 个实验，分别是针对使用线段进行定位的测试、对稳定性和降低传感器误差的测 试、对准确性的测试、对恢复能力的测试和在实际r o b o c u p 比赛的应用实验结 果表明，在高噪声的信息输入下，本定位系统能够减少传感器误差，获得准确、 稳定的定位结果，同时有较好的自我恢复能力。 关键词： 定位贝叶斯滤波器卡尔曼滤波器蒙特卡罗定位移动机器人 a b s t r a c t a b s t r a c t l o c a l i z a t i o n ”，g e n e r a l l ys p e a k i n g ，i st h ep r o b l e mo f f i n d i n go u to b j e c t s l o c a t i o n r e l a t i v et oac e r t a i ne n v i r o n m e n t r e c e n t l y ，t h el o c a l i z a t i o np r o b l e mh a sb e c o m ea f o c u so f r e s e a r c hd u et ot h ep r o g r e s so f s e n s o ra n dc o m p u t e rt e c h n o l o g y , l o c a l i z a t i o n m e t h o d sh a v eb e e nw i d e l yu s e di nd i f f e r e n ta r e a s ，s u c ha sr o b o t i c s ，m o b i l er o b o t n a v i g a t i o n ，c o m p u t e rv i s i o n ，p e r v a s i v ec o m p u t i n g ，w i r e l e s s ( s e n s o r ) n e t w o r k sa n d s oo n m o r e o v e r ，l o c a l i z a t i o np r o b l e mi sc o n s i d e r e do n eo f t h ef u n d a m e n t a lp r o b l e m s i nm o b i l er o b o tn a v i g a t i o n ， v i s i o n b a s e dl o c a l i z a t i o nr e l i e so ni n f o r m a t i o nf r o mo p t i c a ls e n s o r , a n du s u a l l y c o m b i n et h er e l a t i v ea n da b s o l u t ep o s i t i o nm e a s u r e m e n t t e c h n i q u e i nad y n a m i ce n v i r o n m e n tw h e r et h e r ee x i s tm a n yu n c e r t a i n t i e si ns e n s o rr e a d i n g s ，w en e e ds o m e p r o b a b i l i s t i cm e t h o d st od e a lw i t hs u c hap r o b l e m b a y e sf i l t e ri st h a ts t a t i s t i c a lt 0 0 1 k a l m a nf i l t e r sa n dm o n t ec a r l of i l t e r sb o t hb e l o n gt ob a y e sf i l t e r s i nt h i sp a p e r , w ep r e s e n tav i s i o n b a s e dl o c a l i z a t i o nm e t h o dc a l l e dm o n t ec a r l o k a l m a nl o c a l i z a t i o n ( m c l e k e ) t h i sm e t h o di sac o m b i n a t i o no f m o n t ec a r l ol o - c a l i z a t i o n ( m c l ) a n dt h ee x t e n d e dk a l m a nf i l t e r ( e k f ) e n h a n c e m e n t ，m a k i n gu s e o fh i g h n o i s e ds e n s o rd a t ao fa r t i f i c i a ll a n d m a r k sa n dn a t u r a ll a n d m a r k s ，a l o n gw i t h o d o m e t r yd a t aw i t h o u tf e e d b a c k w ef i r s t l yg i v ead e t a i l e di m p l e m e n t a t i o no fm c l w i t ht h ee m p h a s i z eo f d e a l i n gw i t hm u l t i p l et y p e so fp e r c e p t u a li n f o r m a t i o na n dt h e p r o b l e m si nad y n a m i ce n v i r o n m e n t ( e g r o b o tk i d n a p p i n g ) n e x t ，w ee s t a b l i s he k f s o ni a n d m a r k st ob u i l dar e a l ，t i m ee n v i r o n m e n ta r o u n dt h er o b o t i n f o r m a t i o nf r o mt h i s r e a l t i m ee n v i r o n m e n tw i l lb eu t i l i z e db yt h ep e r c e p t i o nm o d e lo f m c l w ea l s oe l a b o r a t eo no u rm e t h o d so fd e a l i n gw i t hs i m i l a r n a t u r a ll a n d m a r k s ，a n dt h o s eo fc o p i n g w i t ha s i n g l eo rt w ol a n d m a r k si np e r c e p t i o nm o d e l f o re x p e r i m e n t s ，w ec a r r yo u ta l lo ft h e mo nr e a lr o b o t s ( a i b oe r s 7 ) w ed e s i g n e ds e v e r a lt y p e so fe x p e r i m e n t si n c l u d i n gt e s to i ll o c a l i z a t i o nu s i n gl i n es e g m e n t s ， t e s to ns t a b i l i t y r e d u c t i o no fp e r c e p t u a le r r o r s ，t e s to np r e c i s i o n ，t e s to na b i l i t yo f i i a b s t r a c t r e c o v e r y , a n da p p l i c a t i o n si nr o b o c u pc o m p e t i t i o n s r e s u l t ss h o wt h a tt h em c l - e k f r e d u c e sp e r c e p t u a le r r o r s ，i n c r e a s e sp r e c i s i o na n ds t a b i l i t ya n ds t i l lk e e pag o o da b i l i t y o f r e c o v e r y k e yw o r d s ：l o c a l i z a t i o n ；b e y e s i a nf i l t e r i n g ；e x t e n d e dk a l m a nf i l t e r ；m o n t e c a r l ol o c a l i z a t i o n ；m o b i l er o b o t s i i i 插图 插图 1 1 基于视觉的定位的一般流程 2 1 贝叶斯定位的一个简单一维过程， 3 1 对于非高斯分布的近似方法， 3 2 扩展的卡尔曼滤波器算法 4 1 对单地标做更新时能得到的信息 4 2 对双地标做更新时能得到的信息 4 3 机器人能看到线段的概率和线段与摄像头夹角的关系 4 4 m c l e k f 的模块流程， 5 1 s o n y 公司的四腿机器人a i b o e r s 2 1 0 5 2 s o n y 公司的四腿机器人a i b oe r s 7 5 3 a b o 机器人比赛场景 5 4 四腿机器人足球比赛的场地 5 5 有腿自主机器人系统结构 5 6 地标识别的误差分布， 5 7 针对利用线段进行定位的实验结果 5 8 用于实验的行走路径模式 5 9 定位过程的图形化描述 v i i i ， h m 凹 弘” 勰 舛郇蛎钾如妮舛 表格 表格 5 i 国际象棋和r o b o c u p l 司题比较 5 2 稳定性实验的结果 5 3 准确性实验的结果 5 4 阻挡模拟的结果 5 5 外力移动模拟的结果 i x 4 2 5 l 5 2 5 3 5 3 第1 章引言与背景介绍 第1 章引言与背景介绍 “定位”，从广义上说，就是确定物体在某个特定环境中相对于其他参 照物的位置的过程。定位问题在在不同的领域有不同的称法，例如“位置 估计”( l o c a t i o ne s t i m a t i o n ) ，“协同配位”( c o o r d i n a t i o n ) ，“物体跟踪”( o b j e c t t r a c k i n g ) ，“摆放”( p l a c e m e n t ) 和“定位”( p o s i t i o n i n g ，l o c a l i z a t i o n ) 。近年来，随 着传感器技术、计算机技术的进步，定位问题越来越成为了一个研究的热点 问题。各种定位方法被广泛的应用于许多领域，比如机器人学( 单多机器人定 位，移动机器人导航【2 1 ) ，计算机视觉( 物体跟踪 3 、人物跟踪【4 】) ，普适计 算 5 ，无线( 传感器) 网络【6 】等。虽然每个领域面临的具体问题互相不同，但是 这些方法终归都是为了回答这样一个问题：“我( 它) 在哪里? ”，如果不能精确 的回答，那么这个问题就变成：“我( 它) 有可能在哪里? ”。 1 1 自主移动机器人 “机器人”( r o b o t ) 这个词语第一次出现在k a r e lc a p e k 在1 9 2 0 写的一个剧本 r u r ( r o s s u m s u n i v e r s a lr o b o t s ) 7 中他描绘了一个未来的场景，工厂里面 所有的工人都是自动化的机器人，他甚至预言这些工人有可能由自己的意识。这 个剧本的成功演绎使得“机器人”这个新词语风靡世界。 从那对开始，关于机器人的研究已经取得了非常大的进展但是机器人还远 远不能有自己的意识。当然，对比于初始的静态、非自主机器人，现在的机器人 已经发展到自主移动的机器人。 移动性( m o b i l i t y ) ：顾名思义，移动性是指机器人可以在何种程度上自由地 在世界中移动。最初的机器人操纵器、机械手等( m a n i p u l a t o r s ) 1 8 只 能反复重复地做一些动作，它们比人力更快速、准确、低廉，通常用来制造像汽 车这样的产品。它们通常包含固定在地面上、可以在一个固定点周围移动的机 器手臂。但是它们无法完全自由地移动，也就是说，它们还没有具备足够的移动 性。 如果我们需要机器人进行一些其它的工作，比如在日常生活中的清洁、投 第1 章引言与背景介绍 递邮件任务，在灾难救助中的自动寻找、救助受难人，甚至让机器人去进行足球 比赛，它们就需要更加具有移动性，也就是说，需要在执行任务的时候可以在环 境中自由的移动。 自主性( a u t o n o m y ) ：自主性取决于在何种程度上一个机器人依赖于它可 能获得的前验知识和关于环境的信息。具体的可以分为非自主、半自主和全自 主三种。全自主机器人可以在完全没有外界( 人力) 引导操作的情况下，完成一 些智能的行动和动作。一般来说，对于全自主机器人，我们并不能指定它每一步 做出什么样的行为，而是指定给他一个目标，并且告诉它通过何种途径可以达到 这种目标，剩下的工作则有机器人本身来完成。 随着科学技术的发展，人类的研究和活动领域已由陆地扩展到了海洋和空 间。利用移动机器人进行空间探测和开发，已经成为2 1 世纪世界各主要科技发 达国家开发空间资源的主要手段之一。在未知的环境，动态的不可以预测的环 境中移动的机器人的控制理论和方法的研究是机器人学和智能控制的一个重要 研究领域【9 】。 动态不可预测的环境，包括高危险环境，外太空环境等人类无法涉足的环 境，在这些环境下自主机器人有着独特的应用优势。f 1 0 1 q = 甚至提出了通过私人 赞助来游览月球，他们希望那些没有经验的人通过控制在月球上的机器人，来获 得这种特殊的经历。既便对于在办公室中移动完成一些日常事务的机器人，由 于办公室的环境具有一定的复杂性，而且由于经常有人员走动，或者是办公室 重新布置，使得这个环境也具有动态性，这就要求机器人除了应该具有建模，定 位，规划，运动等基本能力外，还应能够处理各种突发情况，能够逐渐适应环境， 提高工作效率。也就是说，在动态的不可预测环境中移动的机器人必须具有相 当的自主性。 半自主的，全自主的机器人是现代机器人研究的前沿方向，要求人类的设定 和干预越来越少，机器人自身的自主性要求越来越高，研究的内容囊括机器人体 系结构，路径规划，环境建模和定位等诸多方面的内容。 1 2 机器人定位 移动机器人定位研究的就是如何去一个机器人的角度去回答第一个问题。 2 第l 章引言与背景介绍 这里的“位置”通常包括机器人在绝对坐标系中的x ，y 坐标和自身朝向。机器人定 位在很多自主机器人系统中都是关键的部分 2 ，1 0 , 1 1 】，有的学者甚至将定位问题 称为是赋予一个机器人自主性的“最基本的问题” 1 2 1 。 1 _ 2 1 机器人导航的三个问题 简要的说，机器人导航的任务就是将自己从一个位置安全地移动到另外一 个位置。机器人导航划分成为三个最基本任务( 问题) 【l 】： 我在哪里? 机器人必须知道自己当前的位置，有了当前的方位信息，才能帮 助下一步做出正确的决定。机器人定位( 1 0 c a l i z a t i o n ) 的目的就是找到机器人的 行踪。 我将要去哪里? 为了完成自己的任务，机器人必须知道它将要去何处。通 常来说，它需要识别一个目的地( 目标) ，那么这类问题就是目标识别( g o a l r e c o g n i t i o n ) a 我如何才能到达那里? 一旦机器人明确了前面的两个问题，它就会决定如 何才能达到那里。路径规划( p a t hp l a n n i n g ) 就是帮助机器人找到达到目标的方 法。 1 2 2 定位问题的分类 定位问题可以大致分为几类： 最基本的问题是路径跟踪( p o s i t i o n t r a c k i n g ) ，路径跟踪的目的是在机器人 进行移动的时候对其路径进行记录。通常来说初始位置都是己知的，难度在于机 器人的里程计信息( o d o m e t r y ) 会随着时间的延长，产生越来越大的累积误差。 如何去处理这些误差就是跟踪算法1 1 3 】需要处理的问题了。 苏醒的机器人问题( w a k e u pr o b o tp r o b l e m ) 或者全局定位( g l o b a lp o s i t i o n i n g ) o o 】【1 3 】贝0 更加有难度一些。由于机器人不知道自己的初始位置，它必须在一 无所知的情况下开始定位，所要面临的误差也要大得多。而且它应该可以处理 关于自身位置的多个不同的预测( 信念) 。 一个更加困难的问题就是绑架的机器人问题( k i d n a p p e dr o b o t p r o b l e m ) 。这 类问题中，机器人本来很好地确知自身的位置，但是在它不知情的情况下，它被 移动到别的未知的位置。它必须能够快速地意识到自己已经被“绑架”了，而且能 第1 章引言与背景介绍 够重新定位( r e l o c a t e ) 出自己的最新位置。其实重定位的技术也可以被用在苏醒 的机器人问题上，因为它就是绑架的机器人问题的一个特例。这类问题通常用 来测试机器人对于灾难性的定位错误的恢复能力 1 4 。 上述的定位问题在动态不确定环境中都会变得更加复杂。因为正在定位的 机器人可能并不是环境中唯一运动的物体。其他环境中的物体可能对正在定位 的机器人造成很大的影响。这样的具体例子包括机器人周围的人物影响 1 月，机 器人比赛中对手和队友的影响 1 6 l ，等等。 1 2 3 定位方法的分类 已有的定位方法从性质上面来看，可分为两类【2 】：相对位置测量方法和绝对 位置测量方法。在实际研究中，通常都是从两类方法中各自选择一种，然后再结 合起来使用。 1 2 3 1 相对位置测量方法 相对位置测量方法有的时候也是指航位推测法( d e a dr o c k o n i n g ) ，主要用于 飞机或者轮船长途行程的时候，通过通过某个已知地点时候的行程的速度、方向 和时间，来推测当前的位置。因为这类方法依赖于先前的已知位置，所以误差会 随着时间的增加而累积。在机器人领域的应用中，主要有两种方法。 里程计信息( o d o m e t r y ) 这个词语来自于希腊语，大意是道路测量【1 7 】，这个 词语在用于定位的技术方法中被广泛的应用。通常来说，这种方法通过测量( 轮 式机器人的) 轮子的转动速度来测量自身前进的长度和方向，在其他机器人( 如 腿式、步行机器人) 中，也有不同的定义方法1 1 8 。里程计信息相关方法的优点在 于，它是完全独立的，能给提供短程的相对准确信息，而且花销较少 1 9 ，2 0 】；缺点 在于误差会没有限制的积累增加，需要一些独立的参照物来阶段性的进行修正。 惯性导航法( i n e r t i a ln a v i g a t i o n ) 【2 】通常使用陀螺仪和加速器来计算机器人 的角速度和加速度。陀螺仪可以测量在方向上面的很小的变化，精度很高，但是 造价昂贵，光纤陀螺仪( 激光陀螺仪) 相对较低的价格使得它们可以在机器人领 域得到应用。加速器可以测量机器人的x ，y 方向的微小加速度，但是他们对于地 面不平带来的垂直方向的变化同样很敏感。 4 第l 章引言与背景介绍 1 2 3 2 绝对位置测量方法 相对位置测量方法般是通过测量与机器人完全独立的外在标志物来计算 其位置，整个计算过程与机器人的历史的( 之前的) 位置毫无关系，也就避免了 误差的累积。当然，这类方法的准确与否跟标志物的摆放格局、标志物识别的频 率、准确度和采用的具体计算方法息息相关。 主动的灯塔( a c t i v eb e a c o n s ) 方法可以通过同时测量三个或者更多的主动发 射信号的标志物( 比如灯塔) 的信息，来计算机器人的实际位置，同时，这些主 动光学或者无线电发射信号的标志物必须处在已知的位置上。三角定位法1 2 1 】被 广泛应用在这里，具体的说，就是利用机器人到三个以上的标志物之间的距离或 者( 和) 角度，通过类似几何运算的技术来计算机器人当前的位置和方向。全球 定位系统( g p s ) 就是采用这种方法来计算精度、纬度和高度。 人工自然地标识别法都可以归结为被动的地标识别( p a s s i v el a n d m a r k s ) 方 法。它们的特点就是机器人必须主动去寻找这些固定的地标，而不能能像上述主 动的灯塔中那样接受标志物发来的信号。机器人寻找到地标以后，还要能够通 过传感器来识别地标和计算与地标之间距离、角度，定位的结果很大程度上取 决于采用的传感器类型和采用的传感器识别方法。比如在本文重点讨论的基于 视觉的定位中，机器人必须采用图像处理的特殊方法去识别图片中的地标，摄 像头采集的图片质量和图像处理的方法很大程度上影响着最终的定位误差。 人工地标( a r t i f i c i a ll a n d m a r k s ) 是一些有着唯一独特特征的地标它们被特 意摆放在环境中的已知位置上，并且制造成容易被机器人的传感器所感知，目的 就是供机器人识别并利用它们来定位。举例来说它们可以是不同颜色块、不同 几何形状的图片的组合。这类方法的优点在于可以降低对识别能力的要求( 主 动的灯塔方法中，需要得到至少三个标志物的信号) ，而且由于采用了可以特制 的地标，误差也可以限制在一定范围内。缺点主要集中在传感器识别上面，因为 随着跟地标的距离的加长，传感器识别误差会增加；传感器对环境也有一定的 要求，比如摄像头对环境中的光学条件比较敏感；另外，不同的识别方法也会产 生不同的时间复杂度，影响到处理传感器信息的总体效率。 自然地标( n a t u r a ll a n d m a r k s ) 也同样在环境中有着一定的独特性，但是它 们是环境的一部分，在环境中有着自己的功能，而并不是专门为了机器人定位 第1 章引言与背景介绍 来制造的。在一个室内环境中，典型的自然地标是比如门、窗户、天花板、墙角、 墙边线等等；在室外环境中，典型的自然地标是马路、树木、交通标志等等，室 外环境的自然地标要更复杂一些，因为不像室内环境中的那样具有几何特征( 包 含线、矩形、直角等) 。因为这些自然地标不是专门为机器人定位所制造，所以 它们不具有人工地标的唯一性，通常机器人会识别出很多相似、相同的自然地 标，需要特殊的方法来进行辨别 1 8 , 2 2 】。 模型匹配( m o d e lm a t c h i n g ) 又称作基于地图的方法眠利用传感器获得信 息与环境的地图或者世界模型进行匹配，进而确定机器人的位置。这类方法通 常可以通过新的传感器感知来改进己知的地图，同时可以把本地地图融合到全 局地图中以便对没有到达的区域做出补充。几何形状的地图和拓扑的地图都可 以用在这里，几何形状的地图通过全局坐标系来表示整个环境，而拓扑的地图则 利用节点和弧组成的网络来表达整个世界。 1 2 3 3 基于视觉的定位 基于视觉的定位利用光学传感器的感知信息，而不是超声的、基于惯性的 传感器，一般常用的光学传感器包括激光的测距仪和c c d c m o s 的光学摄像机。 基于视觉的感知可以提供大量的信息，往往是其他传感器所不能比拟的。虽然 视觉感知信息非常丰富，但是从这些信息中提取视觉特征，以及如何将它们用于 定位则不是一件容易的事情。这类定位系统通常包含一些基本的组成部分：对 环境的表示形式；传感器模型；相关的定位算法。 基于视觉的定位需要将相对位置测量方法和绝对位置测量方法结合起来使 用，相对位置测量方法提供机器人在自身坐标系中的位置偏移和方向变化，而 绝对位置测量方法则是通过从传感器模型中处理得到的传感器信息来对机器人 人在全局坐标系中的位置和朝向进行修正。环境的几何信息可以通过二维或者 三维的地标、物体模型或者地图来表示。这些地标、物体模型或者地图要能够提 供足够的空间几何信息，以便单独或者多个视觉传感器可以用来进行图片采集、 分析和匹配。 就像1 2 3 2 中提到的那样，地标需要有一些独特的特征，让机器人可以从视 觉传感器信息中将它们识别出来，同时地标的位置也需要是固定和已知的( 相 对于机器人自身来说) 。为了提供明显的特征，基于视觉的定位所用的地标一般 6 第1 章引言与背景介绍 得到视觉传感器 输入 从图片中识别和 分离地标等标志 物 通过三角定位或 者其他定位方法 计算机器人的位 置。 图1 1 基于视觉的定位的一般流程 将识别出来的传 感器数据和自身 存储的环境的几 何模型做匹配。 都能够提供跟背景环境差异较大的特征，比如颜色、几何形状等。图1 1 1 3 多主体系统 主体( a g e n t ) 2 3 是一种处于一定环境下包装的计算机系统，它能在所处环 境下灵活地、自主地活动，达到预定的设计目的。主体能持续自主地运行，具有 自学习、自增长的能力，同时又可以和别的主体进行协商与协作，以便完成任 务。多主体系统( m u l t ia g e n ts y s t e m ，m a s ) 2 4 就是由这样一组彼此间存在着 协调、协作或竞争关系的主体组成的系统。由于多主体系统更能体现人类的社 会智能，具有更大的灵活性和适应性，更加适合开放、动态的世界环境，因而受 到越来越多人的重视。 多主体系统的特性具有连贯性( c o h e r e n c e ) ，协同性( c o o r d i n a t i o n ) 和协作 性( c o o p e r a t i o n ) 。连贯性指多主体系统作为一个整体如何协同行动，使全局目标 及求解过程中的各项性能指标更为合理。协同性指一组智能主体进行集体行动 时发生相互作用的性质，它表明各主体在实现主要目标的过程中避免有害的相 互作用和无关的活动的能力。协作性指各主体为了一个共同的全局目标而进行 合作的性质，它比协同性更为广泛地反映多主体之间的相互作用特性。目前对 主体和多主体系统的研究主要集中在以下几个方面：主体和多主体的理论、主 体的体系结构和组织、主体语言、主体问的协作和协调、通信和交互技术、多主 体学习以及多主体系统应用等。关于智能主体、多主体系统的研究己成为人工 第1 章引言与背景介绍 智能和计算机科学的研究热点。 1 4 本文内容与组织 在动态环境中，传感器信息中包含很多不确定性，需要一种概率化的方法去 解决这样的问题。贝叶斯滤波就是这样的一个统计工具，而粒子滤波器和卡尔 曼滤波器都是属于其中。 蒙特卡罗定位( m c l ) 1 2 5 是粒子滤波器的一种，是一种鲁棒性较强的概率 化的定位方法，特别是在动态不确定环境中【b 】，去解决“绑架的机器人”问题。 在g u t m a n n 的论文 2 6 , 2 7 】中提到，蒙特卡罗定位在很多情况下没有其他的定位方 法( 比如比较扩展卡尔曼定位等) 能够提供准确的定位结果。在我们的实验环境 中，存在大量传感器误差和其他不确定性( 见第五章) ，但是同时需要很高的定 位精度和稳定度，我们发现只用蒙特卡罗定位很难完成这个任务。 对蒙特卡罗定位的大多数现有研究【1 3 , 1 4 , 2 5 1 以轮式机器人为应用背景，利用 声纳或者雷达传感器获取环境信息。声纳和雷达使用高精度的3 6 0 。传感器信息， 而本文使用的传感器信息来自于机器人局部视觉。同时，轮式机器人的运动模 型往往是可预测、连续变化的，而步行机器人的步幅是非连续变化的，因而带来 相对更大的里程计信息噪声。仅在最近的一些文献中【2 8 ，2 9 ，步行机器人上的视 觉传感器信息被用于蒙特卡罗定位。这些工作都使用同一种计算最终样本点权 重和样本集重采样的方法，不足之处是这种方法不能有效利用同一帧内多个标 志物( 如地标等) 的信息，而且在应对“绑架的机器人”问题时，样本点发散速度 有限，造成自定位结果不能很快地收敛。 以上这类工作大多基于地标识别来进行定位。针对自然地标，r o f e r 等 人 2 9 】利用直线上的点进行传感器模型的更新。为了降低计算复杂度，只从每 条直线上随机取一个点，但这样会造成直线的信息对最终结果的影响有限，甚 至没有影响，或者由于测量误差造成错误的影响。针对人工地标，s r i d h a r a n 等 人 3 0 1 提出了一种根据地标距离进行更新的修正方法，主要是希望通过一些离线 的训练方法来逼近在真实环境中的传感器数据，通过这种方法来减少误差的影 响。这种方法非常依赖于一个固定的环境( 例如灯光条件必须没有变化) ，而且 稳定度就是指机器人在到达目的地以后，定位结果能够稳定的停留在目的地附近的这种性质。 8 第1 章引言与背景介绍 不能在线实时地对地标的感知信息进行适应。 扩展的卡尔曼滤波器 3 1 】是一种可以估计动态系统状态的递归循环的数据处 理算法。它的非常广泛的应用当中就包括移动机器人定位。它在用于机器人定 位的时候也同样存在问题，就是难以应对前文所述的“苏醒的机器人问题”和“绑 架的机器人问题”。这方面大多数以前的研究1 2 0 , 2 6 , 3 2 都集中在对机器人自身的跟 踪和预测上面，而只有很少的研究希望用它来为环境建模并且跟其它的定位方 法进行结合。 本文结合相对位置测量方法( 里程计法) 和绝对位置测量方法( 地标识别 法) ，提出一种基于视觉的定位方法，蒙特卡罗一扩展卡尔曼定位方法( m c l e k f ) 。我们希望为环境建立扩展的卡尔曼滤波器，来减少传感器信息中的噪声， 然后再将这些已经过滤过的传感器信息融入m c l 中。这样我们可以继承m c l 的 优点( 鲁棒性、绑架后的快速恢复) ，同时也能够继承e k f 的一些特性( 比如增 加准确度和稳定度) 。同时我们还给出了新的计算权重和样本重采样方法，对自 然地标的不唯一性所做的特殊处理，以及传感器模型中处理单个或者两个人工 地标的方法。 下面的章节中，我们利用第二章概括介绍了贝叶斯滤波器的原理，以及由之 产生的一个概率化的定位框架。在这个框架基础上，在第三章具体介绍粒子滤 波器和蒙特卡罗定位，线性卡尔曼滤波器以及扩展的卡尔曼滤波器，给出了公式 推导的细节和算法流程。在第四章分别说明蒙特卡罗一卡尔曼定位方法的各个组 成部分。在第五章我们进行了实验背景、环境、采用方法的介绍，并且给出了实 验结果与讨论。我们在最后一章进行了对本文的总结和展望。 9 第2 章贝叶斯滤波 第2 章贝叶斯滤波 “t h e p r o b a b i l i t yo f a n ye v e n ti sf pr a t i ob e t w e e nt h ev a l u ea tw h i c hd 玎e x p e c t a t i o nd e p e n d i n go nt h eh a p p e n i n go f f 施e v e n to u g h tt ob ec o m p u t e d , a n dt h ev a l u eo f t h et m n ge x p e c t e du p o ni t sh a p p e n i n g ” t h o m a sb a y e s ( 1 7 0 2 - 1 7 6 1 ) ，【3 3 】 贝叶斯理论( 【3 4 】等) 是一类概率论理论，可以用来描绘世界模型中的不确 定性，而且可以通过融合先验知识和观测数据来得到有意义的结果。 贝叶斯滤波器( b a y e sf i l t e r s ) 3 5 】运用贝叶斯统计和贝叶斯定理来解决概率 性的推导问题，特别是随机滤波问题。 3 6 q b 最早提到了递归的贝叶斯滤波，并 讨论了连续状态估计问题的原理，特别是将卡尔曼滤波作为一个特例提出。 贝叶斯滤波器可以从高噪声的观察数据中来概率化的估计一个动态系统的 状态，在定位问题中，这个系统状态就是人、机器人或者其他物体的位置，而定 位传感器则提供关于状态的观测数据。在用于机器人定位的时候，机器人对自 己所处的位置有一个信念，任何时刻都不只考虑一个可能的位置，而是所有可能 的位置所处的状态空间。这样，机器人可以相信自己以一定的可能性处在某一 个位置，这类定位问题可以估计整个状态空间中的概率分布。下面来具体说明 各种定义和计算推导的过程。 2 1 信念 信念的定义 b e l ( x ) = p ( x t l d o ) 在时间t 的时候，给定所有的数据面- ，机器人在位置搬的概率。 先验与后验信念 l o ( 2 一1 ) 第2 章贝叶斯滤波 先验信念b p 广k ) ，在第k 时间段已经融入最新的相对位置信息，但是还没 有融入绝对位置信息的时候，机器人的信念。 后验信念f + k ) ，在第七时间段已经融入最新的相对位置信息和绝对位置 信息的时候，机器人的信念。 2 1 1 概率化的动作模型和传感器模型 这里的动作模型指处理以上提到的相对位置信息的模型，而传感器模型则 是处理绝对测量信息的模型，我们将分别为两者定义一个概率化的模型。 动作模型 p ( x t x k - h a k 1 ) ：表示在第k 一1 时间段，机器人在z k 一1 位置，接着它执行了 动作a k l ，并且在第k 时间段达到位置。这是所谓的转换密度，由于它描述了 机器人如何通过动作来改变其自身位置，所以也称作动作模型。动作模型是与 时间无关的，所以我们经常省略其下标k 。 传感器模型 p ( s k l x i ) ：表示在时间段k ，传感器从位置x k 观察n s k 的概率，也称作传感器 模型。可能计算器起来有难度，因为传感器的信息有可自t e l z 艮多，因此需要定义特 征向量： 仃：s z ：表示从原始传感器信息s n 低维的向量z 的特征转换，这样上面 的概率就可以在z 的状态空间中计算。举例：比如基于地标的定位中，特征可以 是地标的存在与否。 2 2 定位公式 2 2 1 初始信念 初始信念表示为b e l 一( x o ) ，即时间段0 的先验概率。如果机器人预先知道自 身的初始位置，月j j b e l 一( x o ) 表现为以其初始位置为峰值的分布，这类定位问题称 为位置跟踪问题。如果机器人不能预先知道自身的初始位置，j j b e l 一( x o ) 是均匀 分布，这类定位问题称为是全局定位问题，或者是”苏醒的机器人”问题。如果机 器人预先知道自身位置，但是事实上它并没有在那个地方，则这是”绑架的机器 人”问题。 第2 章贝叶斯滤波 2 2 2 修正1 言念 这里重新表示先验概率和后验概率。 在执行动作a k i 以后可以得到： b e l 一( ) = p ( x k l z l ，a l ，z 2 ，a 2 ，g k 一1 a k1 )( 2 - 2 ) 在收到传感器信息巩以后可以得到 b e l + ( 船) = e ( x k l = l ，a l ，z 2 ，a 2 ，一，盈竹ia ki ，z k ) ( 2 - 3 ) 2 2 3 加入动作信息 ( 全概率公式) 删弧) = 上尸( x k l x k “z l 口1 ) 忍，咐一，训 ( 2 _ 4 ) x p ( x 一l l g l 】日i ，z 2 ，a 2 ，z k 一1 ，a k 1 ) d x k 一1 = 上p ( 靴阻l 同，z k - l ，a k - 1 ) b “+ 嘛1 ) d x k l ( 2 - 5 ) ( x k 一1 - 与a k 一1 无关) = f p ( x k l x k t ，卿一t ) b e ，+ ( 船 ( m a r k o v 假定：给定当前状态，过去的状态与将来无关。) 2 2 4 加入传感器信息 b e l + ( x k l = ( 贝叶斯公式) p ( z k l x k ，z l ，d l ，- 一，z k 竹1a k1 ) p 1 。1 ，a l b e l + ( x k ) e ( z k z l ，a l ，一，z k l ，a k 一1 ) p ( z k l x k ，z l ，a l ，t ，2 t 。1 , f l k1 ) b e l 一( x k ) ( 2 - 6 ) ( 2 7 ) p ( z 掣k z ，。1 一, 、g k _ l ，) ( 2 - 8 ) p ( z k i x k ) b e i 一( 船) p ( 珊k l ，a l ，z k 。ia k1 ) 1 2 第2 章贝叶斯滤波 ( m a r k o v 假定：推论出传感器信息只跟当前状态有关，不受机器人历史的位置和 状态的影响。) ( 其中p ( 硌l z l ，a l ，z k 一1 a k1 ) = 止尸i ) xb e l 一) 弧是一个用来用来 标准化的常量) 2 2 5 最终结果 最后，引n b e l 一( 取) 的定义，可以得到 删= 意措筠 e ( 2 k l x k ) f z p ( x k l x k 。1a k1 ) b e l + ( x k x ) d x k p ( z k l z l ，a l ，- = r l k p ( z k l x k ) 上p ( 船阻- 其中m = p ( z l , i z l ，0 1 ，- - ，g k “口一1 ) - 。，是一个标准化常量 ( 2 - 9 ) 2 3 关于参数的说明和图示 为了能够顺利的利用公式得到我们需要的信念，我们必须确定三种概率： 1 动作模型：p ( 讯i x k 一1 a k1 ) 2 传感器模型：p ( 敏i x k ) 3 初始信念：b e l 一( x o ) ，即时间段0 的先验概率。 有了以上三者，我们就可以循环地利用上面得到的公式将相对位置信息和 绝对位置测量信息融入机器人的信念中。 以上介绍的公式是当前很多概率化定位方法的基础，不同的方法对其有不 同的应用。 图( 2 1 ) 给出了一个贝叶斯定位的简单一维过程。 呶扣乍 。删 稚 “订 m 睢 第2 章贝叶斯滤波 图2 1 贝叶斯定位的个简单一维过程 这里假定一个人带有一个可以识别房问门的摄像头，但是不能分辨不同的门。图 中的每一个子图标明了人物的位置和与之对应的当前信念肌“般) 。而( b ) 和( d ) 中同时标明了传感器模型p ( z i z ) 的情况，具体的说就是能够观察到房间门的概率 分布。( a ) 人物的位置是完全未知的。( b ) 传感器发回“发现房间门”的信号。( c ) 人物开始移动。( d ) 传感器再一次识别出房间门。( e ) 人物再次移动。 1 4 第3 章概率化的定位方法 第3 章概率化的定位方法 3 1 蒙特卡罗定位 3 1 1 粒子滤波与蒙特卡罗滤波 蒙特卡罗方法最早的想法可以追溯到1 7 7 7 年，当时b u f f o n 为了近似计算7 c 而 想到了这种方法。而这种方法最早出现在统计学中则是1 9 4 0 年代的事情【3 1 。近 年来，蒙特卡罗方法在多个领域找到了用武之地，尤其是物理学、统计学和工程 学。粗略的说，蒙特卡罗方法可以通过生成随机样本的方法来解决一些复杂系 统里面难以解决的问题。 蒙特卡罗滤波最早由k i t a g a w a 提出1 3 8 1 。在这种方法中，可能性分布被这个 分布上的一些实际值来进行近似的表示。这些实际值称为样本( s a m p l e ) 或者粒 子( p a r t i