（模式识别与智能系统专业论文）室内环境下移动机器人定位和建图研究.pdf

中文摘要 中文摘要 本文以室内环境下移动机器人的导航为研究背景，面向实际应用，以 p i o n e e r - 3 d x 移动机器人为实验平台，利用里程计、声纳作为主要传感器，分别 针对室内环境下移动机器人自定位问题及同时定位和建图问题( s i m u l t a n e o u s l o c a l i z a t i o na n dm a p p i n g ，s l a m ) 展开研究。围绕上述问题，本文主要进行以下 三个方面的研究： ( 1 ) 基于蒙特卡洛方法提出一种实用的移动机器人自定位技术。针对声纳传 感器的特点，设计一种有效的粒子权重的更新方法，该方法通过对声纳数据进 行分类和多声纳数据的融合提高权重的计算精度，在实现时采用查表的方法保 证算法的实时性；通过重采样和发散操作，确保滤波器中粒子群的收敛度和有 效性，有效地降低滤波器的退化和匮乏效应，并最终解决移动机器人定位过程 中的“绑架”问题。 ( 2 ) 开展基于遗传算法的移动机器人自定位研究，将移动机器人定位问题转 化为一个状态估计问题，利用遗传算法优越的全局搜索能力寻找机器人当前位 姿的优化估计。针对定位问题，设计一种基于位置相似度的种群适应度计算方 法；利用实时性较高的实值编码方式实现种群的交叉、变异；将发散算子引入 常规遗传算法，减小“绑架 发生时种群的匮乏效应；在此基础上，利用机器 人运动模型更新种群状态实现机器人的连续定位。 ( 3 ) 以里程计、声纳分别作为航迹推测和环境感知传感器，提出一种室内环 境下基于二维线段特征的s l a m 技术方案。具体而言，设计了一种实用的s l a m 系统框架；提出基于混合霍夫变换和最小二乘的线段特征提取算法，同时，为 了提高该算法的实时性，设计了基于滑动窗口的高效的实现方法；通过设计基 于齐次坐标变换的机器人运动模型及基于二维线段特征的观测模型，将常规 s l a m 算法扩展到二维线段模型下；最后，展开对数据关联策略的初步研究。 关键字 移动机器人；自定位；同时定位与建图；蒙特卡洛方法；遗传算法；扩展卡 尔曼滤波器 a b s t r a c t a b s t r a c t f o rp r a c t i c a li n d o o rn a v i g a t i o no fm o b i l er o b o t s ，t h i sd i s s e r t a t i o nd e s c r i b e st h e d e s i g na n di m p l e m e n t a t i o no fa u t o n o m o u sl o c a l i z a t i o na l g o r i t h m sa n ds i m u l t a n e o u s l o c a l i z a t i o na n dm a p p i n g ( s l a m ) t e c h n o l o g yb a s e do np i o n e e r 3 - d xm o b i l er o b o t ， w h i c hi sm a i n l ye q u i p p e dw i t ho d o m e t r ya n ds o n a rs e n s o r s t h em a i nc o n t e n t so ft h i s d i s s e r t a t i o nc a nb es u m m a r i z e da sf o l l o w s ： ( 1 ) ap r a c t i c a ls e l f - l o c a l i z a t i o nt e c h n o l o g yf o rm o b i l er o b o t si sp r o p o s e da n d i m p l e m e n t e db yu t i l i z i n gs o n a rs e n s o r s s p e c i f i c a l l y , t h el o c a l i z a t i o np r o b l e mi s s o l v e db ye m p l o y i n gm o n t ec a r l om e t h o d ；a l le f f i c i e n tm e c h a n i s mi s p r o p o s e dt o c a l c u l a t et h es a m p l e s w e i g h t s ，i nw h i c hs o n a rd a t ai sc l a s s i f i e dt oi m p r o v et h e a c c u r a c ya n dat a b l el o o k u pm e t h o di su t i l i z e dt om e a tt h er e a l t i m er e q u i r e m e n t ； t h ec o n v e r g e n c ea n dv e r a c i t yo ft h es a m p l es e ta r eg u a r a n t e e db yt h ed e s i g n e d r e s a m p l i n ga n ds c a t t e r i n gp r o c e s s ，w h i c hl a r g e l ya l l e v i a t e st h ed e g e n e r a t i o na n d i m p o v e r i s h m e n to fp a r t i c l ef i l t e ra n dt h e nl e a d st oas a t i s f a c t o r ys o l u t i o nf o rt h e k i d n a p p e dp r o b l e m e x p e r i m e n t a lr e s u l t sa r ea l s og i v e nt oi l l u s t r a t et h ep e r f o r m a n c e o ft h ep r o p o s e d t e c h n o l o g y ( 2 ) as e l f - l o c a l i z a t i o ns t r a t e g yb a s e do ng e n e t i ca l g o r i t h mi sp r o p o s e df o r m o b i l er o b o t s b yu t i l i z i n gt h es u p e r i o rg l o b a ls e a r c hc a p a b i l i t yo f g e n e t i ca l g o r i t h m ， t h eo p t i m a le s t i m a t i o no fr o b o tp o s ei so b t a i n e d s p e c i a l l y , af i t n e s sf u n c t i o ni s d e s i g n e db a s e do nt h es i m i l a r i t yo fp o s i t i o n ；r e a l - c o d e dm e t h o di su s e di nt h e c r o s s o v e ra n dm u t a t i o ns t e p st oi m p r o v et h er e a l - t i m ea b i l i t yo ft h ea l g o r i t h m ；a s c a t t e r i n ga l g o r i t h mi si n t r o d u c e dt oa l l e v i a t et h ep o p u l a t i o ni m p o v e r i s h m e n tw h e n k i d n a p p e dp r o b l e mh a p p e n s ；s u b s e q u e n t l y , t h ep o p u l a t i o ns t a t ei su p d a t e dw i t ht h e k i n e m a t i cm o d e lt oa c h i e v ec o n t i n b o u sl o c a l i z a t i o no fm o b i l er o b o t s s o m e e x p e r i m e n tr e s u l t sa r ea l s op r o v i d e dt od e m o n s t r a t et h ev a l i d i t yo ft h ep r o p o s e d l o c a l i z a t i o ns t r a t e g y ( 3 ) ap r a c t i c a l2 d l i n e - b a s e ds l a mi sp r o p o s e df o ra p p l i c a t i o n su n d e ri n d o o r e n v i r o n m e n tu s i n gs o n a ra n do d o m e t r yd a t a f i r s t ，af e a s i b l es y s t e ma r c h i t e c t u r ei s a b s t r a c t p r o p o s e d t h e n ，l i n ef e a t u r e sa r ee x t r a c t e df r o mg r o u p so fs o n a rd a t au s i n gh y b r i d h o u g ht r a n s f o r ma n dl e a s ts q u a r e ( h t l s ) a l g o r i t h m t om e e tt h er e a l t i m e r e q u i r e m e n t ，a ne f f i c i e n ti m p l e m e n t a t i o no fh t l sa l g o r i t h mb a s e do ns l i d ew i n d o w i si n t r o d u c e d b e s i d e s t h es t a n d a r df o r m u l a t i o no fe k f s l a mi se x t e n d e dt o 2 d - l i n ec a s ew h e r et h ep r a c t i c a lp l a n ta n do b s e r v a t i o nm o d e li sc o n s t r u c t e da n dt h e n e m p l o y e d f i n a l l y , t h ed a t aa s s o c i a t i o ns t r a t e g yi sa l s op r e l i m i n a r i l yd e v e l o p e d t o i l l u s t r a t et h ep e r f o r m a n c eo ft h ep r o p o s e da l g o r i t h m ，b o t hs i m u l a t i o na n de x p e r i m e n t r e s u l t sa r ep r o v i d e d k e yw o r d s m o b i l er o b o t ；s e l f - 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 ； m o n t ec a r l om e t h o d ；g e n e t i ca l g o r i t h m ；e x t e n d e dk a l m a nf i l t e r 内容目录 图目录 图2 1 栅格地图1 2 图2 2 声纳测量模型1 2 图2 3 声纳数据分类1 4 图2 4 距离表三维视图15 图2 5 实验环境。2 1 图2 6 移动机器人运动轨迹( m c l ) 。2l 图2 7 粒子分布示意图。2 2 图2 8m c l 定位误差统计2 4 图2 9n c s 、n e s 变化曲线图2 5 图3 1g a l 算法框图2 8 图3 2 移动机器人运动轨迹( g a l ) 3 5 图3 3g a l 定位实验结果3 6 图4 1s l a m 系统框图3 9 图4 2 二维线段模型4 0 图4 3 基于滑动窗口的实现框架4 6 v i l 内容目录 图4 4 线段特征提取结果4 7 图4 5 仿真用地图及建图结果5 2 图4 6 移动机器人位姿估计误差( 仿真) 5 3 图4 7 特征参数估计误差( 仿真) 5 3 图4 8 建图及机器人轨迹估计结果( 实验) 5 5 图4 9 移动机器人位姿估计误差( 实验) 5 5 图4 1o 南开大学伯苓楼二层走廊示意图。5 6 图4 1 1 里程计原始定位信息及建图结果5 7 图4 1 2 基于线段特征的e k f s l a m 定位及建图结果5 7 v i l l 内容目录 表目录 表2 1m c l 重采样操作1 9 表2 2m c l 自定位算法流程2 0 表3 1g a l 选择算子3 1 i x 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：力鳓 2 邢年s 月2 c 7 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：乃黼 2 肋吕年s 胄冯日 第一章绪论 第一章绪论 第一节引言 中国科学院、中国工程院两院院士宋健在国际自动控制联合会第1 4 届大会 报告中曾指出：“机器人学的进步和应用是本世纪自动控制最有说服力的成就， 是当代最高意义上的自动化。 作为机器人的一个重要分支，移动机器人是一类能够通过传感器感知周围 环境和自身状态，实现在障碍物环境中自主运动，完成一定作业任务的机器人 系统。经过多年的研究和发展，移动机器人已逐步走向实用化，在星球探测、 海洋开发、军事反恐、灾难救助、危险品处理以及家庭服务等领域发挥着日益 重要的作用。 众所周知，具备自主导航能力是移动机器人实用化的前提，导航过程主要 包括路径规划、定位和目标识别等步骤【2 1 。为了实现导航的基本任务，移动机 器人需要依靠本体携带的传感器实现对自身位姿和外部环境信息的感知，即定 位和建图过程，只有准确地知道以上信息，移动机器人才能通过目标识别、路 径规划等操作实现有效安全的自主运动。因而，移动机器人的定位和建图研究 引起众多研究人员的关注，已成为机器人领域的研究热点问题【3 j 。 本文以室内环境下的移动机器人导航为研究背景，面向实际应用，以 p i o n e e r 3 d x 移动机器人为实验平台，重点围绕移动机器人的定位和建图问题展 开研究：基于蒙特卡洛定位算法，提出了一种实用的基于声纳传感器的移动机 器人自定位技术，以期解决移动机器人定位中的位姿跟踪、全局定位及“绑架” 三类问题；将移动机器人定位问题转化为一个状态估计问题，设计了一种基于 遗传算法的移动机器人自定位技术，利用遗传算法优越的全局搜索能力寻找机 器人当前位姿的优化估计；针对未知环境下移动机器人导航问题，研究并提出 了一种基于线段特征的移动机器人同时定位和建图算法，力图仅使用里程计和 声纳作为主要传感器，实现室内环境下机器人位姿序列的估计及环境的建图。 本文的研究将为室内移动机器人的导航任务提供坚实的理论方法和丰富的 实验结果，并能有力地推动移动机器人在实用化的进程中迈出重要的一步，因 第一章绪论 此本文的研究具有重要的意义和广泛的应用前景。 第二节移动机器人定位和建图研究现状 1 2 1 国内外研究现状 1 2 1 1 定位问题及方法 定位作为移动机器人研究领域最基本的问题之一，其目的就是使机器人借 助于携带的各种传感器或者环境信息来确定自身的位姿，即解决“我在哪? ” 的问题，只有实现了定位，机器人才能解决“我去哪? ”，“怎么去? ”等其它 导航问题。现有的移动机器人定位方法可以分为以下三类【4 ： 相对定位：主要依靠里程计、陀螺仪等机器人内部传感器，通过测量机 器人位姿相对于初始位姿在距离和方向上的变化实现机器人的定位【5 】【6 1 。该类方 法存在误差累积的问题，随着机器人的运动，定位误差会逐渐增加。 绝对定位：主要通过导航信标、主动或被动标识、地图匹配或全球定位 系统( g l o b a lp o s i t i o n i n gs y s t e m ，g p s ) 【刀【8 】等进行定位。位姿计算方法包括：三 角测量法( t r i a n g u l a t i o n ) 【9 】【10 1 、三边测量法( t r i l a t e r a t i o n ) 1 1 】【12 1 、模型匹配算 法( m o d e lm a t c h i n g ) 1 3 】【1 4 】等。 混合定位：相对定位方法具有自包含的优点，能够依据运动模型自我推 测机器人的运动轨迹，但该方法存在不可避免的累积误差。绝对定位方法不存 在累积误差，但信标的建设和维护成本高，地图匹配技术处理速度慢，g p s 只 能用于室外。由于单一方法的不足，现在的移动机器人定位常采用两者方法相 结合的混合定位方法。 经典移动机器人定位方法主要包括扩展卡尔曼滤波器方法( e x t e n d e d k a l m a nf i l t e r , e k f ) i s 】，马尔可夫方法( m a r k o vl o c a l i z a t i o n ) 1 6 】【17 和蒙特卡洛 方法( m o n t ec a r l ol o c a l i z a t i o n ，m c l ) i s 】【1 9 】等。 扩展卡尔曼滤波器方法：扩展卡尔曼滤波器是卡尔曼滤波器在非线性系 统中的推广，它假设机器人运动模型和感知模型符合高斯噪声模型，系统状态 服从高斯分布，通过预测、观测和更新三个步骤对机器人位姿进行递推计算， 从而获得最小二乘意义下的最优位姿估计。当噪声模型或系统模型误差过大时， 第一章绪论 e k f 定位容易造成不可恢复的定位失败。 马尔可夫方法：与扩展卡尔曼滤波器方法不同，马尔可夫定位方法不使 用高斯分布表示概率分布，而是将整个状态空间离散化，直接以每个离散化后 的空间单元的概率密度来表示机器人位姿状态的分布。由于这种方法需要记录 整个状态空间的概率分布，因而它需要消耗大量的内存资源和计算代价。 蒙特卡洛方法：蒙特卡洛定位方法的核心是加权采样，即通过在机器人 位姿空间进行随机采样，并根据样本与状态的实际概率分布之间的差别大小赋 予样本不同的权重，从而以有限的离散样本逼近连续状态的概率分布。m c l 定 位具有计算简单，不局限于高斯分布假设的特点，但该算法存在样本退化等问 题。 1 2 1 2 建图方法 环境建图是移动机器人利用自身携带的外部传感器，如测距传感器、视觉 传感器等，感知周围环境，建立环境信息的过程。按照环境表示方式的不同， 机器人建立的环境地图通常可分为栅格地图、特征地图、拓扑地图、混合地图 在占 寸o 栅格地图：e l f e s 在 2 0 中提出了在已知移动机器人位姿情况下基于栅格 地图的环境建图方法。栅格地图将环境划分为大小相等的独立栅格，机器人在 运动中利用传感器观测信息确定栅格是否为空或被障碍物占据。由于处理简便， 栅格地图被广泛应用于移动机器人定位和建图中1 2 1 1 ，并得到了理想的效果，但 该方法由于涉及到大量栅格的计算，地图的更新等操作时间复杂度高，地图存 储所需空间较大。 几何特征地图：几何特征地图同样被广泛应用于建图研究中【2 2 】【2 3 】，它通 常将环境表示为点、线段、角、面等几何特征的集合，机器人在建图过程中通 过视觉、激光等传感器探测环境，从中提取点、线段、角等几何特征，用以描 述环境的基本组成单元。这种环境表示方法无论在时间上还是空间上都具有较 高的效率，但由于涉及几何特征的提取，对传感器数据的质量及数量要求较高， 需要相应的特征提取技术作配合。 拓扑地图：拓扑地图是一种紧凑的无尺度的地图表示方式，特别适用于 大规模环境的建图f 2 4 】。拓扑图将环境表示为节点和边的组合，节点对应环境中 的一片特征区域，边对应环境中连接特征区域的路径。构建拓扑地图或利用拓 第一章绪论 扑地图导航通常不需要机器人的精确的位姿信息，因此对机器人定位误差具有 较强的鲁棒性，但该方法有时难以区分环境中的相似区域是否为同一节点，因 此会给机器人导航路径的选择带来困难。 混合地图：混合地图是两种或多种地图表示方式的组合，实现不同地图 表示方式之间的优势互补【2 5 1 1 2 6 1 。混合地图通常包括栅格地图和几何特征地图的 混合、栅格地图和拓扑地图的混合以及拓扑地图和几何特征地图的混合等形式。 混合地图通常具有局部地图信息丰富以及全局地图鲁棒的特点，因此适用于对 大规模环境的建图。但混合地图由于包含多种地图表示元素，因此其计算复杂 度较高。 1 2 1 3s l a m 技术 机器人在未知环境下执行导航任务时，由于缺少已知的环境地图信息，移 动机器人很难利用地图信息进行定位，同时为了建立环境的地图信息，机器人 必须能够准确地确定自身位姿，从而通过传感器获得的机器人与环境特征的相 对位置关系确定环境特征的准确位置，在这种情况下，环境地图的准确性依赖 于机器人定位的精度，而定位的实现又离不开环境地图，定位与建图相互依赖、 相互决定、相互耦合，形成了“鸡生蛋，蛋生鸡”的问题【2 丌。解决该问题的关 键在于如何利用定位和建图二者之间的相互制约关系，使二者同时在线完成， 即同时定位与建图( 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 ) 。 目前，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 ) 1 2 8 1 1 2 9 1 的方法，基于粒子滤波 器( p a r t i c l ef i l t e r , p f ) 1 3 0 1 的方法，期望最大化方法( e x p e c t a t i o nm a x i m i z a t i o n ，e m ) 1 3i j 和增量方法，以下分别予以介绍。 e k _ f s l a m ：e k f s l a m 将机器人位姿和环境中特征( 或路标) 统一起 来作为系统状态，并假设它们服从高斯分布，然后将系统运动模型和传感器观 测模型线性化，使用卡尔曼滤波过程进行递推计算，从而得到机器人位姿和环 境特征位置的联合概率估计，即计算出系统状态的均值及相应的协方差矩阵。 e k f 方法是目前使用最广泛的s l a m 方法，但该方法计算复杂度为o ( n 2 、) ，n 为地图特征数目，这决定了该方法能够处理的特征数目不能太大；同时，e k f 对环境特征的观测值与预测量之间的数据关联非常敏感，如果关联错误则e k f 滤波器容易发散。 4 第一苹绪论 p f s l a m ：粒子滤波器是实现机器人定位的重要方法，又称蒙特卡洛方 法。p f 采用加权采样的方式计算机器人位姿的后验概率分布，可以处理服从任 意分布的机器人位姿状态的估计。对于高维状态的s l a m 问题，一般采用改进 的r a o b l a c k w e l l i z e d 粒子滤波器( r a o b l a c k w e l l i z e dp a r t i c l ef i l t e r , r b p f ) ，它 通常将s l a m 问题分解为对机器人运动轨迹的估计和在机器人运动轨迹已知的 条件下对环境特征( 或陆标) 的估计，而此时对环境特征的估计是相互独立的， 因此r b p f 与e k f 相比具有计算简单的特点，其计算复杂度为o ( m l o g n ) ，其 中聊为粒子数目，n 为地图特征数目。m o n t e m e r l o 等人提出的f a s t s l a m 算法 是r b p f 的一个实例，f a s t s l a m 包含两部分，一部分是用粒子滤波估计机器人 的轨迹，另一部分是在位姿估计的基础上，利用n 个独立的e k f 对环境特征进 行估计，以为地图特征数目。f a s t s l a m 方法融合了p f 和e k f 的优点，降低了 计算复杂度，同时具有较好的鲁棒性，在已知和未知数据关联的情况下都可以 得到较好的s l a m 结果，是目前研究中的热点。 e m s l a m ：期望最大化方法将s l a m 看作机器人位姿和环境特征的最 大似然估计问题，分两步完成s l a m 过程，即e ( 期望) 步和m ( 最大化) 步。 在e 步中根据当前极大似然地图计算机器人的位姿估计，在m 步基于e 步的机 器人位姿估计结果计算新的极大似然地图，e 步和m 步交替进行，不断更新机 器人的位姿估计和极大似然地图。e m 算法通常能够克服错误的数据关联，因而 具有较高的鲁棒性，但是该算法需要处理重复相同的数据以获得极大似然地图， 运动过于复杂，很难满足s l a m 的实时性要求。 增量方法：基于增量方法的s l a m 假设某一时刻机器人位姿和局部地图 给定，采用增量极大似然方法计算下一时刻机器人的位姿，然后利用该位姿信 息构造环境的增量地图，同时通过粒子滤波计算机器人的位姿的后验概率，当 这两种方法计算出的位姿相差足够大时，对地图进行校正，确保建图精度。增 量方法本质上可以看成是e m 方法和p f 方法相结合的混合方法，通过p f 方法 的估计结果校正增量的极大似然估计。 1 2 2 现存主要问题 目前，相关研究人员在移动机器人的定位和建图这一研究领域已经取得了 一些研究成果，但就该技术的研究与实际应用而言，尚存在一些亟待解决的问 第一苹绪论 题，以下对这些问题进行具体分析。 1 2 2 1 移动机器人自定位技术 所谓自定位就是移动机器人能够自主地确定自身的位姿，它是目前移动机 器人自主化研究中的重要课题【3 2 j 【3 3 】【3 4 】。特别是针对室内环境下的移动机器人导 航问题，由于g p s 信号的缺失，以及人工信标的维护成本较大，使得利用绝对 定位技术实现机器人的定位的可能性变小，这时就需要机器人具备自定位能力， 利用携带的传感器准确地确定自身位姿。与传统的相对定位技术不同，移动机 器人自定位技术将机器人定位问题分为以下三类子问题进行研究【3 5 】： 位姿跟踪问题：机器人的初始位姿己知，利用航迹推测的方法，通过传 感器测量机器人位姿的相对变化实现机器人的定位，由于航迹推测存在误差的 累积，所以要求定位算法能够实现对累积误差的校正。 全局定位问题：与位姿跟踪问题不同，全局定位要求在机器人初始位姿 未知的情况下实现定位，这就要求定位算法能够较好地处理由于初始位姿不确 定导致的定位误差。 机器人“绑架 问题：在移动过程中，机器人经常在未被告知的情况下 从一个位置转移到另一个的位置，或者由于轮胎打滑、里程计数据丢失等原因 造成严重失步，此时认为机器人遭遇“绑架”。“绑架 问题在机器人定位中属 于最复杂的一种情况，与全局定位问题不同，机器人在遭遇“绑架 时，仍然 依据以前的定位信息来推算当前的位置与姿态( 位姿) ，因此将造成很大的定位 误差。在这种情况下，定位算法必须具备很强的判断和误差处理能力才能使机 器人逐渐计算出正确的位姿信息，实现机器人的重定位。 1 2 2 2 室内环境下移动机器人s l a m 技术 家庭服务是移动机器人广阔应用前景中的一条重要分支，室内应用这一特 殊领域对移动机器人的s l a m 技术提出了诸多亟待解决的问题【3 6 】【3 7 1 3 引。例如， 如何利用室内环境自身的特点设计高效的环境表示方法? 特别是针对服务行 业，建图结果要有较好的可读性；如何在确保性能的前提下降低s l a m 系统的 成本? 高昂的成本目前已成为阻碍s l a m 研究成果实用化的瓶颈；如何提高 s l a m 算法的实时性? 在s l a m 中，由于需要在线处理机器人位姿估计、地图 更新、数据关联、特征提取等问题，导致算法计算复杂度较高，同样严重影响 6 第一章绪论 了s l a m 的实用化。 1 2 2 3 移动机器人定位和建图的其它难点 近年来，对复杂地形下的移动机器人定位研究逐渐活跃起来【39 1 ，在复杂地 形下，移动机器人航迹推测的累积误差相比较室内环境增长更迅速，系统的不 确定性也更明显，如何解决这一问题是移动机器人定位研究中的难点之一；另 外，真实环境往往是动态变化的，这会给建图带来无法预测的噪声，如何分辨 动态障碍物与静态障碍物，建立更加准确的环境地图成为另一个研究难点【4 叫； 同时，随着s l a m 技术水平的不断提高，s l a m 研究涌现出了一些新的发展趋 势，包括利用视觉和三维激光传感器对环境的三维空间建图【3 9 】以及采用多机 器人协作方式展开大规模环境的建图【4 2 】【4 3 j 哗1 等。 综上所述，定位和建图是当前移动机器人导航领域的核心问题，有关该问 题的研究尚存在诸多方面的不足，而这些不足严重影响了定位和建图技术的实 用化，因此本文有必要针对移动机器人的定位和建图问题展开进一步的研究。 第三节研究内容及章节安排 本文以室内环境下的移动机器人导航作为研究背景，以p i o n e e r 3 d x 室内移 动机器人作为研究、实验平台，展开了针对移动机器人定位和建图技术的研究。 围绕上述目标，本文具体研究内容包括： ( 1 ) 针对移动机器人定位问题中的位姿跟踪、全局定位和“绑架问题，研 究了一种实用的基于声纳传感器和蒙特卡洛方法的移动机器人自定位技术。 ( 2 ) 将机器人定位问题转化为状态估计问题，研究了一种基于实值编码遗传 算法的移动机器人自定位技术。 ( 3 ) 研究了室内环境下基于线段特征的移动机器人同时定位和建图技术，包 括s l a m 系统的建模，特征提取算法的设计，以及数据关联的策略等。 基于以上内容，本文共分为五章，各章节的安排如下： 第一章绪论，介绍移动机器人定位和建图问题的研究现状，概括本文的研 究内容及方法。 第二章基于蒙特卡洛方法的移动机器人自定位研究，针对移动机器人定位 问题中的位姿跟踪、全局定位和“绑架 问题，以声纳作为环境感知的传感器， 7 第一章绪论 提出一种基于蒙特卡洛方法的移动机器人自定位技术。针对声纳传感器的特点， 设计一种有效的计算粒子权重的机制；针对机器人遭遇“绑架 时容易出现的 粒子匮乏现象，重新设计重采样和发散操作。 第三章基于遗传算法的移动机器人自定位研究，将移动机器人定位问题转 化成一个状态估计问题，利用遗传算法优越的全局搜索能力在机器人位姿可能 分布的状态空间中，寻找机器人当前位姿的优化估计。设计一种基于位置相似 度的种群适应度计算方法；利用实时性较高的实值编码方式实现种群的交叉、 变异；将发散算子引入常规遗传算法，减小“绑架发生时种群的匮乏效应； 在此基础上，利用机器人运动模型更新种群状态实现机器人的连续定位。 第四章室内环境下移动机器人同时定位和建图研究，以声纳作为环境感知 传感器，设计一种基于线段特征的s l a m 技术。提出一种实用的s l a m 系统框 架：设计基于混合霍夫变换和最小二乘方法的线段特征提取技术，并介绍该技 术基于滑动窗口的高效实现方法；为e k f s l a m 设计基于齐次坐标变换的机器 人运动模型以及基于二维线段的观测模型；同时，展开对s l a m 中数据关联策 略的研究。 第五章结论与展望，对本文研究进行总结，并对有待进一步研究的问题进 行分析与展望。 第二章基于蒙特卡洛方法的移动机器人自定位研究 第二章基于蒙特卡洛方法的移动机器人自定位研究 第一节问题的提出 定位是实现移动机器人导航任务的前提，是移动机器人研究领域的基本问 题。近年来，针对移动机器人定位问题中的初始位姿已知的位姿跟踪、初始位 姿未知的全局定位及机器人“绑架 三类子问题【3 引，研究人员提出了多种有效 的定位算法，其中的经典算法包括：基于扩展卡尔曼滤波器( e x t e n d e dk a l m a n f i l t e r ，e k f ) 的定位【45 1 ，马尔可夫( m a r k o v ) 定位【4 6 】和蒙特卡洛定位( m o n t ec a r l o l o c a l i z a t i o n ，m c l ) 4 7 1 。e k f 定位能够有效地解决移动机器人位姿跟踪问题， 但其一阶泰勒近似限制了它在高噪声环境下的应用，并且该算法仍无法有效地 解决移动机器人全局定位和“绑架问题。m a r k o v 定位通过计算机器人在环境 中分布的概率密度可以有效地解决全局定位等问题，但由于该方法计算复杂度 高，它在实际应用中很难得到推广。 m c l 定位是基于贝叶斯理论的概率定位算法，是粒子滤波器( p a r t i c l ef i l t e r ) 在机器人定位领域的一种应用。该方法使用一组离散的带权粒子模拟机器人位 姿的后验分布，并重复执行状态预测、更新权重和重采样等步骤完成滤波，实 现机器人的定位。它最主要的优点是不拘泥于线性系统和高噪声环境，易于实 现，并且可以有效地处理全局定位和机器人定位失步等问题，甚至在解决机器 人“绑架问题时也有较好的表现。近年来，m c l 定位算法因其卓越的性能引 起了研究者们广泛的关注，随着m c l 定位算法的发展，一些精确传感器，如激 光传感器【4 8 】【4 9 1 、视觉传感裂5 0 】【5 1 】【5 2 】等，被应用于定位过程中。这些传感器的应 用，显著提高了m c l 的定位性能，但同时也不可避免地提高了定位系统的成本。 在选择传感器实现机器人定位时，成本和精确度是两个主要的性能指标。 声纳作为一种距离传感器，具有体积小，价格低廉，应用方便等特点，因此它 在移动机器人定位领域获得了广泛应用。其中，l e o n a r d 和d u r r a n t 、：v h y t e t 5 3 1 利用 旋转声纳扫描仪扫描周围环境，提取r c d ( r e g i o no f c o n s t a n td e p t h ) 特征信息 实现了机器人的定位。w i k 和c h r i s t e n s e n i ”】设计了基于t b f ( t r i a n g u l a t i o n - b a s e d f u s i o n ) 的声纳数据融合算法，并在此基础上利用e k f 实现了移动机器人定位。 9 第二章基于蒙特卡洛方法的移动机器人自定位研究 值得指出的是，这些算法尽管在一定程度上降低了由于声纳数据的不确定度带 来的定位误差，但同时也不可避免地增加了定位系统的复杂度，影响了算法的 实时性。 综合考虑m c l 定位和声纳传感器的优点，本章提出了一种实用的低成本的 移动机器人自定位技术。该定位技术利用声纳作为传感器，结合蒙特卡洛方法 实现了移动机器自定位，解决了定位过程中的位姿跟踪、全局定位和“绑架” 三类问题。归纳起来，该技术主要贡献有如下两个方面：针对声纳传感器的特 点，为粒子滤波器设计了一种有效的粒子权重计算方法，该方法具有较高的精 度和实时性；采用我们设计的重采样和发散步骤，确保了粒子群的收敛度和有 效性，有效地避免了机器人遭遇“绑架时粒子的匮乏效应，并最终解决了机 器人“绑架问题。 下面将首先给出m c l 定位的基本原理，然后详细介绍基于蒙特卡洛方法的 移动机器人自定位解决方案，最后给出实验结果与分析。 第二节蒙特卡洛定位基本原理 根据贝叶斯理论，机器人定位问题可描述为： p ( x j i i z l = ) = p ( z | lx t ) p ( x tlz ) p ( z iz l ：) ( 2 1 ) 其中，x 女= ，虬，皖】。为机器人位姿状态，z 为观察量。要实现机器人定位， 即要求解式( 2 1 ) ，然而对于非高斯、非线性系统，该式的解析解并不存在。 粒子滤波器利用离散概率推演的方法求解式( 2 1 ) ，为此基于蒙特卡洛原理， 采用一组带权随机采样的粒子群： s = i 江1 ，2 ，3 ，) ( 2 2 ) 来表征后验概率密度函数p ( x tlz ) ，其中x k ( i = o ，1 ，2 ，) 是一组支撑粒 子，w ：( f = o ，1 ，2 ，) 为其对应的权值。当粒子总数趋近无穷大时，被估状 态的后验概率分布近似等于： 上 p ( x 。lz m ) w ；8 ( x t x ：) ( 2 3 ) i = l 在定位过程中，m c l 定位通过重复迭代进行状态预测、更新权值和重采样 l o 第二章基于蒙特卡洛方法的移动机器人自定位研究 完成滤波，实现机器人定位，各步骤介绍如下。 状态预测：当机器人运动时，依据机器人概率运动模型p ( x tlx 川，a ) 更新表示机器人位姿分布的粒子群状态，其中x ，x t 分布表示第k 一1 和第k 时刻机器人的位姿状态，口是第k 一1 和第k 时刻之间的运动动作，包括机器 人的旋转和平移运动。 更新权值：更新粒子权值时，通常依据声纳模型评估粒子的可靠度： ， 吨= r l p ( z klx ：) ( 2 4 ) 其中，p ( z 女lx ：) 表示声纳观测模型，r l 为归一化因子。在实现时，通常利用一 幅事先构建好的先验地图来辅助计算粒子权重，而声纳观测模型则一般由一个评 估函数来代替。 重采样：粒子滤波器的一个普遍问题是退化现象，即迭代过程中可能出 现除少数粒子外，其它所有粒子权值几乎为零，此时权值小的粒子对滤波的贡献 几乎可以忽略，但它们却浪费着大量的计算资源。解决退化问题的方法主要是重 采样算法，它的基本思想是在统计意义上重复拷贝那些权值较大的粒子，形成新 的种群，而直接抛弃权值很小的粒子，但该方法会衍生粒子匮乏现象，即粒子的 分散度减小，可能产生过收敛的问题，这不利于实现机器人的正确定位，特别是 当“绑架”现象发生时，在机器人真实位姿附近几乎没有粒子生存，这通常最终 会导致定位失败。 第三节声纳测量模型及权重更新设计 m c l 通过计算粒子的权重来评估粒子的准确度，我们利用一幅机器人工作 环境的栅格地图辅助计算粒子权重，与其它形式的地图( 如几何地图、拓扑地 图) 相比较，栅格地图更易于构造和应用。图2 1 是实验环境的二值栅格地图 ( b i n a r yg r i dm a p ) ，地图大小为8 6 6 1 ，栅格分辨率为o 1 m o 1 m ，每个栅格 取值为1 ( 占据栅格) 或1 ( 空白栅格) ，分别代表该区域被障碍物覆盖或无障 碍物，图中黑色的部分为占据栅格，白色的部分为空白。当对该定位技术进一 步扩展时，也可利用非二值栅格地图等辅助实现机器人定位。 第二章基于蒙特卡洛方法的移动机器人自定位研究 2 3 1 声纳测量模型 图2 1 栅格地图 声纳固定在移动机器人上，它是一种高噪声的距离传感裂们，能够探测前方 类似圆锥形的一片空间，并返回该区域内最近的物体的距离信息。声纳的测量 模型如图2 2 所示，图