（控制科学与工程专业论文）室内未知环境线段特征地图构建.pdf

浙江大学博士学位论文摘要 摘要 未知环境地图构建是机器人和人工智能研究领域的一个重要课题，是移 动机器人在未知环境中自主完成侦察、勘探、搜索、救援、导航等各项工作 的基础，对提高机器人的智能性、促进机器人进入人类日常生活、为人类服 务具有重要的研究意义和应用价值。 未知环境地图构建问题面临着同时定位与地图构建( 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 na n dm a p p i n g ) 方法、高维数据、数据对应、环境的动态特性和环 形特性、以及自主探测规划等多方面的挑战。结合室内环境结构性特点，本 文采用描述障碍物轮廓的线段为特征，通过对信息处理、同时定位与地图构 建和探测规划问题的深入研究，建立了一套相对完整的线段特征地图构建方 法。同时，为了提高地图构建机器人快速运动能力和在窄小空间中的灵活运 动能力，本文研究了四轮全方位移动机器人的运动建模与控制问题，为后续 研发奠定了基础。 本文主要研究工作包括： 1 ) 提出了结合哈夫变换、同线性判断和最小二乘法的混合线段拟合方法。该 方法可有效提高拟合精度，实现对环境信息精确而简洁的描述。 ( 2 ) 2 提出了寻找测量数据与线段特征最佳相合的增量式同时定位与地图构建 方法。该方法将s l a m 分解为局部地图构建、机器人位姿估计和地图合 并三个循环步骤。在地图估计步骤，利用最小二乘法迭代寻找当前测量数 据与已构建地图中线段特征的最佳相合实现机器人位姿估计，并通过去除 不当匹配和引入加权矩阵来减j , 澳u 量误差、特征拟合误差和已构建地图中 的不确定性对位姿估计的影响。在地图合并步骤，根据所估计位姿，合并 当前观测得到的局部线段特征地图和已构建全局线段特征地图实现地图 的更新。该方法避免了高斯噪声假设，降低了对数据关联错误的敏感性， 具有较小的匹配运算量，可以在线实时构建线段特征地图。在较复杂的实 浙江大学博士学位论文 摘要 验室环境和较大的楼道环境中的实验证明了算法的有效性和鲁棒性。 ( 3 ) 提出了基于点线相合和粒子滤波的f a s t l i n e s l a m 方法。该方法采用粒子 实现机器人路径的多假设，在粒子中采用基于点线相合的增量式s l a m 方法进行地图的更新估计。在粒子采样过程中，利用点线相合的位姿估计 方法缩小采样空间；通过基于相合关系的粒子权重更新方法降低计算复杂 度；通过选择性重采样抑制粒子滤波常见的退化现象和采样枯竭问题。实 验结果证明该算法解决了点线相合s l a m 方法存在残差累积、后期难以 校正的问题，可良好解决环形环境和动态环境下的室内地图构建，克服了 传统粒子滤波s l a m 方法存在存储空间负荷高、计算量大的缺陷，所需 粒子数和存储空间均较少。 ( 4 ) 提出了一种基于线段特征方向引导的探测规划算法。在利用线段特征生成 候选视点的同时，赋予候选视点继承线段特征的方向属性；通过定义具有 起始位置和探测方向属性的探测区域，将探测环境表示为具有递进关系的 探测区域树；根据候选视点与探测区域的隶属关系，通过探测区域的方向 引导或者候选视点的观测方向引导启发式地搜索下一步最佳探测位姿。实 验表明，所提方法可有效确保候选视点的可定位性，提高搜索效率，减少 来回往复的运动现象。 ( 5 ) 研究了实时动态环境中四轮全方位移动机器人的运动控制和轨迹规划。通 过对机器人运动学和动力学特性的分析，给出了四轮全方位移动机器人的 控制模型，并根据方程特性对其进行了合理的简化，使得计算量有效减少。 同时采用b a n g b a n g 控制规划出时间最优的机器人运动轨迹。通过轨迹规 划和控制模型的结合达到了实时控制的效果。实验证明了模型的正确性和 算法的有效性。 关键词室内未知环境；地图构建；s l a m ；探测规划；运动控制 浙江大学博士学位论文 a b s t r - d c t a b s t r a c t r o b o t i cm a p p i n gi sa l le s s e n t i a li s s u ei nr o b o t i c sa n da r t i f i c i a li n t e l l i g e n t i ta c t s a st h eb a s eo fr e c o n n a i s s a n c e ，s e a r c h ，r e s c u e ，n a v i g a t i o ne ta lf o rm o b i l er o b o t w o r k i n gi nu n k n o w ne n v i r o n m e n t t h u si t sr e s e a r c ha n da p p l i c a t i o ni sm u c h s i g n i f i c a n tt oi m p r o v et h ei n t e l l i g e n c eo fr o b o ta n dp r o m o t et h ep r o c e s st h a t r o b o t ss e r v i c ef o rh u m a ni nd a i l yl i f e t h em a i nc h a l l e n g e so fr o b o t i cm a p p i n ge x i s to ns 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 na n dm a p p i n g ) ，h i g hd i m e n s i o n a l i t y , d a t aa s s o c i a t i o n , d y n a m i ca n d l o o pf e a t u r e si n e n v i r o n m e n ta n da u t o n o m o u se x p l o r a t i o n t h i sd i s s e r t a t i o n a d d r e s s e st or o b o t i cm a p p i n gi nu n k n o w ni n d o o re n v i r o n m e n t s c o n s i d e r i n gt h e s t r u c t u r ec h a r a c t e r i s t i co fi n d o o re n v i r o n m e n t ，w ea d o p tl i n et h a td e s c r i b e st h e p r o f i l eo fo b s t a c l ea sf e a t u r e w i t i lt h er e s e a r c ho ni n f o r m a t i o np r o c e s s ，s l a m a n de x p l o r a t i o n ，a ni n t e g r a t e dm a pb u i l d i n ga p p r o a c hi se s t a b l i s h e d i na d d i t i o n , t ob o o s tt h em o b i l i t yo ft h er o b o tf o rm a pb i l d i n gi nt h en a r r o we n v i r o n m e n t ，t h e m o t i o nm o d e l i n ga n do p t i m a lc o n t r o lo fo m n i - d i r e c t i o n a lm o b i l er o b o t si s s t u d i e d ， w h i c hp r o v i d e sab a s ef o rf u t u r ew o r k t h ew h o l ep a p e ri n c l u d e st h ef o l l o w i n g d e t a i l ： ( 1 ) ac o m b i n i n gm e t h o do fh o u g ht r a n s f o r m ，c o i n c i d e d l i n ed e t e c t i n ga n dl e a s t s q u a r ei sp r e s e n t e da n du s e dt o f i tl i n es e g m e n tf r o mm e a s u r e m e n t t h i s m e t h o db o o s t st h ef i t t i n gp r e c i s i o n ，t h u st h ee n v i r o n m e n tc a nb ed e s c r i b e d a c c u r a t e l ya n ds u c c i n c t l y ( 2 ) w ep r o p o s e da ni n c r e m e n t a ls l a ma p p r o a c hb a s e do nt h eb e s tc o n g r u e n c e b e t w e e nd o td a t ai nt h ec u r r e n tm e a s u r e m e n ta n dl i n es e g m e n t si nt h e p r e v i o u s l y - b u i l tm a p e a c hi t e r a t i o no fs l a m c o n s i s t so f3s t a g e s ：l o c a lm a p b u i l d i n g ，r o b o tp o s ee s t i m a t i n g ，a n dm a pi n t e g r a t i n g i np o s ee s t i m a t i n g ，l e a s t s q u a r em e t h o di su s e di t e r a t i v e l yt o o b t a i nt h eb e s tc o r r e s p o n d e n c eb e t w e e n t h em e a s u r e m e n ta n dt h eh a l f - b a k e dm a p r e m o v i n gi m p r o p e rm a t c ha n d d e f i n i n gw e i g h t e dm a t r i xa r eb o t hi m p l e m e n t e dt o r e d u c et h ee r r o r so f v 浙江大学博士学位论文 a b s t r d c t m e a s u r e m e n t , l i n ef i t t i n ga n dp r e v i o u s l y b u i rm a p 。i nm a pi n t e g r a t i n g ，w i t h t h ep o s ee s t i m a t e d ，t h em a pi su p d a t e db yf u s i n gt h el o c a lm a pb u i l tf r o m c u r r e n tm e 龇e m e ma n dt h ep r e v i o u s l y b u i l tm a p t h i sm e t h o da v o i d st h e h y p o t h e s i so fg a u s sn o i s ea se f k s l a ma n dr e d u c e st h es e n s i t i v i t yt ot h e e r r o ro fd a t ac o r r e s p o n d i n g i tc a l lw o r ko n l i n ew i t hal o wc o m p u t a t i o nl o a di n m a t c h e x p e r i m e n t a lr e s u l t s w i t hr e a ld a t ad e m o n s t r a t et h ea p p r o a c hi s e f f e c t i v ea n dr o b u s tf o ri n d o o re n v i r o n m e n tm a p p i n g ( 3 ) w ef u r t h e rp r o p o s e da na p p r o a c hc a l l e df a s t l i n e s l a mb yi n t r o d u c i n gt h e i n c r e m e n t a ls l a m a l g o r i t h mb a s e do nd o t - l i n ec o n g r u e n c ei n t op a r t i c l ef i l t e r i nt h ea p p r o a c h ，e a c hp a r t i c l ec a r r i e sa na s s u m p t i o no nr o b o tp a t ha n d e m p l o y st h es l a ma l g o r i t h mb a s e do nd o t - l i n ec o n g r u e n c et ou p d a t et h em a p b o t ht h em o t i o na n dt h eo b s e r v a t i o ni n f o r m a t i o na l ec o n s i d e r e di nt h e i m p o r t a n c ef u n c t i o nb yu s i n gt h ed o t l i n ec o n g r u e n c em e t h o dt oe s t i m a t et h e p o s eo fr o b o t t h ew e i g h to ft h ep a r t i c l e i s u p d a t e da c c o r d i n gt o t h e c o n g r u e n c e b e t w e e nc u r r e n tm e a s u r e m e n ta n d s e g m e n t f e a t u r e si n p r e v i o u s l y b u i l tm a p t h ew r o n gp a r t i c l e sr e s u l t e df r o mm i s - m a t c h i n go re r r o r a c c u m u l a t i o na l ef i l t e r e dw i t hs e l e c t i v er e s a m p l i n g e x p e r i m e n t a lr e s u l t s 、杭t l l r e a ld a t ad e m o n s t r a t et h ea p p r o a c hi se f f e c t i v ea n dr o b u s tf o rm a p p i n g d y n a m i ca n dl o o pi n d o o re n v i r o n m e n tb ys o l v i n gt h er e s i d u a le r r o re x i s t i n gi n t h ei n c r e m e n t a ls l a ma l g o r i t h mb a s e do nd o t - l i n ec o n g r u e n c e b o t ho ft h e p a r t i c l en u m b e ra n dm e m o r ya r eq u i t el o w e rt h a nt h ee x i s t i n gm a p p i n g m e t h o d su s i n gp a n i c l ef i l t e r ( 4 ) w ep r e s e n t e dal i n e - f e a t u r e - g u i d e de x p l o r a t i o na p p r o a c ht of i n dt h en e x tb e s t p o s eo fv i e w t h ec a n d i d a t e so fv i e wa r en o to n l yg e n e r a t e df r o ml i n ef e a t u r e s b u ta l s oi n h e r i t e dt h eo r i e n t a t i o np r o p e r t yo fl i n ef e a t u r e s ，w h i c hi su s e dt o g u i d et h ee x p l o r a t i o n t h ee n v i r o n m e n ti s d i v i d e di n t oas e q u e n c eo f e x p l o r a t i o ns p a c ew h i c hi sd e f i n e da sas u b s p a c ew i t ha ne x p l o r a t i o nd i r e c t i o n a n das t a r t p o s i t i o n a c c o r d i n gt o a f f i l i a t i o nb e t w e e nc a n d i d a t e sa n d e x p l o r a t i o ns p a c e s ，a nh e u r i s t i cn b v s e a r c hi si m p l e m e n t e db yo b e y i n gt h e d i r e c t i o ng u i d eo f b o t ht h ec a n d i d a t ea n dt h ee x p l o r a t i o ns p a c e e x p e r i m e n t a l 浙江大学博士学位论文a b s t 阳c t r e s u l t sd e m o n s t r a t et h ep r o p o s e da p p r o a c he n s u r e st h el o c a l i z a t i o no f c a n d i d a t e so fv i e wa n di se f f i c i e n tf o ra c t i v e m a pb u i l d i n g i ni n d o o r e n v i r o n m e n tt og e tag o o dc o m p l e t ec o v e r a g ew i t hf e we r i s s - e r o s s i n gm o t i o n ( 5 ) w es t u d i e dt h em o t i o nc o n t r o la n dp a t hp l a n n i n go ft h e o m n i d i r e c t i o n a l m o b i l er o b o t t h r o u g h a n a l y s i st h ec h a r a c t e r i s t i co ft h ek i n e m a t i c sa n d d y n a m i c so ft h eo m n i - d i r e c t i o n a lr o b o tw h i c he q u i p p e df o u ro m n i d i r e c t i o n a l w h e e l s ，i t sm o t i o nc o n t r o lm o d e li sp r o v i d e d t h e nt h em o d e li ss i m p l i f i e d r a t i o n a l l ya c c o r d i n gt ot h ef e a t u r eo fm o d e le q u a t i o n s ，w h i c hr e d u c e st h ec o s t o fc o m p u t a t i o ne f f e c t i v e l y u s i n gb a n g - b a n g c o n t r o l ，t i m e o p t i m a lt r a j e c t o r y g e n e r a t i o nm e t h o da l s o i sc a r r i e do u ta n dp r o d u c e dar e a l - t i m ee f f e c t i n t e g r a t e d 、椭t l lt h em o t i o nc o n t r o lm o d e l t h ee f f e c t i v e n e s so ft h em e t h o dh a s b e e nd e m o n s t r a t e db ye x p e r i m e n t s k e y w o r d s u n k n o w ni n d o o re n v i r o n m e n t ；m a pb u i l d i n g ；s l a m ；e x p l o r a t i o n ； m o t i o nc o n t r 0 1 v i 浙江大学博士学位论文图目录 图目录 图1 1 自定位与地图构建之间的关系一4 图1 2 系统框架2 2 图2 1 直线方程参数示意图2 7 图2 2p i o n e e r 2 d x 8 3 2 图2 3 激光测距仪测量得到的三个数据点集例子3 4 图2 4 不同网格尺寸下的哈夫变换拟合效果3 7 图2 5 基于本文方法的拟合效果3 7 图3 1 基于点线相合的增量式s l a m 算法流程4 2 图3 ，2 特征不确定性示例4 4 图3 3 机器人质心运动模型4 8 图3 4 位姿变化量计算方法4 9 图3 5 可见区域定义5 0 图3 6 位姿计算实例6 0 图3 7 伪相合问题示例6 1 图3 8 根据里程计数据直接合并测距仪数据得到的实验室环境地图6 2 图3 9 不考虑数据和模板不确定性得到的实验室环境地图6 4 图3 1 0 滤除不当匹配、不考虑加权时得到的实验室环境地图一6 5 图3 1 l 利用本文方法得到的实验室环境地图。6 7 图3 1 2 位姿估计匹配残差比较6 7 图3 1 3 根据里程计数据直接合并测距仪数据得到的楼道环境地图6 8 图3 1 4 利用本文方法得到的走廊环境地图。6 9 图4 1 里程计运动模型7 7 图4 2 射线模型概率计算示意图8 2 图4 3 基于里程计数据得到的原始地图8 5 图4 4 基于点线相合的s l a m 算法构建得到的地图8 6 图4 5f a s tl i n e s l a m 构建得到的地图8 7 图4 6g r i d sl a m 和g m a p p i n g 算法对第一组数据的构建效果8 9 图4 7g r i d sl a m 和g m a p p i n g 算法对第二组数据的构建效果9 0 图4 8 地图构建成功率比较9 l 图5 1 基于探测区域的环境分解和树结构示意图9 5 图5 2 探测规划算法流程9 6 图5 3 候选视点生成示意图9 8 图5 4 g 不在形空间内的图示1 0 0 图5 5 探测规划过程及结果1 0 7 图5 6 贪婪搜索策略下的探测规划和地图构建结果1 0 9 图5 7 不考虑可定位信息收益下的探测规划和地图构建结果。1 0 9 浙江大学博士学位论文 图目录 图6 1 全方位移动机器人及全方位轮1 1 2 图6 2 车轮排布1 13 图6 3 轮子的运动学分析11 4 图6 4p ( o ) + u ( ，) 的三维图1 2 1 图6 5 约束空间三维图1 2 2 图6 6 实验机器人1 2 5 图6 7 实时规划轨迹与实际轨迹比较1 2 6 i v 浙江大学博士学位论文表目录 表目录 表2 1 激光测距仪s i c kl m s 2 0 0 主要技术参数。3 3 表2 2 线段特征地图构建实验统计3 8 表4 1 算法粒子数和存储量需求比较9 l 表4 2 算法运行时间比较9 l 表5 1 探测规划算法流程符号说明9 7 表5 2 线段引导的探测规划和贪婪搜索规划实验结果比较1 0 9 表5 3 考虑定位效益和不考虑定位效益的实验结果比较1 1 0 表6 1 规划效果1 2 6 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得盘婆盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文 中作了明确的说明并表示谢意。 学位论文作者签 婵醐：一引们日 学位论文版权使用授权书 本学位论文作者完全了解 逝鎏盘鲎 有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘堂 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日期：7 阳书6 月8 日 i 4 导师签名 签字日期：7 秽产月扩日 浙江大学博士学位论文致谢 致谢 在此论文完成之际，衷心感谢导师褚健教授长期以来对我学习工作的关 心和指导，他把握研究方向和研究问题的高屋建瓴、勇于迎接挑战的创新精 神、活跃的思维和求实的作风都使我受益匪浅。感谢吴俊教授对我研究工作 的帮助，感谢他对我论文的细致修改和有益探讨感谢浙江大学智能系统与 控制研究所机器人小组王文斐博士、张翮硕士和吴永海博士对相关研究问题 的良好合作，感谢刘勇博士后、王立博士、唐亮博士、汤卿博士、杜鑫峰博 士等各位同学的支持。感谢我的家人对我学习和工作的大力支持，以及生活 上无微不至的关怀 最后，感谢所有曾经帮助过我的师长、同事、同学和朋友。 熊蓉 2 0 0 9 年2 月于求是园 浙江大学博士学位论文 1 绪论 1 绪论 1 1 研究背景 随着科学技术日新月异发展、人民生活水平不断提高、生命得到更多尊 重、老龄化社会问题日趋严峻，机器人走向社会和家庭已成为必然趋势。2 0 0 6 年，韩国信息通信部制定了到2 0 2 0 年前韩国每个家庭都能拥有一台机器人的 发展目标2 0 0 7 年，美国微软公司的比尔盖茨在第1 期科学美国人上撰 文：“家家都有机器人” 3 7 1 他预言，机器人即将重复个人电脑崛起的道路， 将与个人电脑一样，彻底改变这个时代的生活方式这标志在未来2 0 一5 0 年的时间内，机器人将从少数专业人士使用的高端研究设备走向民间的广泛 应用，逐步走入人类的日常生活，适应人类生活环境，与人类友好共处，成 为人类不可或缺的亲密朋友和帮手 智能移动机器人是机器人家族中的一个重要分支，也是走进社会和家庭 的主要机器人类型它被定义为“是一种能够从环境中提取信息，并利用环境 知识进行规划决策，实现在环境中有意义、有目标地安全移动的机器”1 1 1 可 以看到，环境知识是智能移动机器人规划决策和安全移动的必要基础。与在 已知环境中限定作业范围内进行作业的传统工业机器人相比，智能移动机器 人的作业空间是变化的，存在着各种动态性和不确定性，机器人必须具备获 取环境信息和认知的能力，并根据所获取的环境信息和认知知识进行运动规 划和控制。 目前研究人员已经开发了多种移动机器人样机或产品，例如用于火星探 测的勇气号和机遇号机器人1 5 , 5 1 1 ，用于探测海洋资源的自动水下机器人 ( a u t o n o m o u su n d e r w a t e rv e h i c l e ，a u v s ) t 1 0 6 1 ，用于物料搬运的自动导航车 ( a u t o n o m o u sg u i d e dv e h i c l e ，a g v ) 2 5 1 ，用于建筑物搜索和救援的城市机器人 9 1 ，用于服务的助老助残机器人【7 3 1 ，博物馆导游机器) x j 7 a 1 1 ，等等。 然而，现有的大部分智能移动机器人采用预先存储环境地图的方式。显 浙江大学博士学位论文 1 绪论 然，人工构建地图是一件烦琐的工作，而且无法随着环境的动态变化自动更 新。一些运用于未知环境和危险环境的智能移动机器人则不得不或多或少地 借助于人的干涉【2 4 】，例如自动导航车a g v 是通过特殊放置的陆标或感应带 来引导机器人；而进行火星探测的机器人则是将所拍摄得到的照片发送回地 球，由人分析规划后进行远程遥控因此，未知环境中移动机器人自主地图 构建被认为是实现真正的智能移动机器人的最重要的问题之一，是智能移动 机器人进入人类日常生活的必要基础，也成为近年来机器人和人工智能领域 中一个非常活跃的研究热点。 所谓未知环境地图构建是指机器人根据传感器测量信息构建其所探测环 境的空间模型它能够有效提高机器人的智能性，是机器人进入人类日常生 活为人类服务、以及在未知环境中自主完成侦察、勘探、搜索、救援、导航 等各项工作的基础【1 1 4 1 。随着移动机器人应用环境日趋复杂，该问题也成为自 主移动机器人急需解决的重要基础性难题【1 4 3 1 在过去二十多年的发展过程中，未知环境地图构建研究领域已经取得了 丰硕的研究成果，但仍然面临着种种重大挑战由于数据维度、数据对应、 计算复杂性等问题，目前已有的各种鲁棒方法主要面向于静态的、结构的、 有限空间，主要构建得到占用栅格地图和陆标特征地图，更为有效的地图表 示方法、面向动态的、环形的、非结构的和大范围环境的同时定位与地图构 建方法、以及更为高效的探测规划方法是研究人员正在探索的问题。 本文在此背景下，结合国家自然科学基金项目，研究移动机器人对具有 环形特性和动态特性的室内未知环境的地图构建问题。 1 2 地图构建问题描述 1 2 1 核心问题 未知环境地图构建的最大挑战在于它是一个同时定位与地图构建问题， 称为 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 na n d m a p p i n g ) 1 8 , 2 0 , 2 6 或 浙江大学博士学位论文 l 绪论 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 s , 1 0 9 1 问题来源于传感器存在系 统性的测量噪声，且在机器人地图构建中，这种测量误差表现为统计上相关 i n 4 1 系统性的测量误差使根据里程计得到的机器人位姿和根据测距传感器构 建的地图中均存在不确定信息这两种不确定信息相互关联、相互影响，形 成统计上相关的特性。一方面，在机器人对未知环境进行地图构建时，需要 根据各个时刻机器人的位姿来合成观测信息如果机器人的位姿是确定的， 那么很容易合成得到一致性地图。然而由于轮子打滑等原因，里程计测量数 据中存在一定的误差，并且由于运动积分使误差随着时间而累积。另一方面， 机器人在确定自己位姿时需要利用已有的环境知识和当前的感知信息在环 境地图已知的情况下，机器人定位问题已能够解决然而在未知环境下，并 没有一个已知的确定地图可用，机器人只能依赖于局部构建的、存在观测噪 声的非完整地图。因此，在未知环境地图构建中需要同时解决自定位和地图 构建问题，它们之间具有鸡与蛋的关系特性图1 1 描述了未知环境地图构 建中自定位和地图构建之间的相互依赖、相互影响的关系特性【2 4 1 。 1 2 2 主要挑战 除了传感器测量噪声之外，同时定位与地图构建问题还面临着以下难点 i f 4 , 1 1 9 , 1 5 5 1 1 ) 高维数据问题高维数据问题产生于环境地图表示需要大量的数据从 统计的角度来看，每个数据是估计问题中的一个维度，从而使得关于地 图所有可能性的假设空间是巨大的当地图被定义在连续空间上时，地 图的空间是无限多维的。即使采用栅格地图进行离散近似，地图空间维 数仍非常大假设栅格地图中的栅格单元数为1 0 ，0 0 0 ，则可能的地图空 间数为2 1 0 一。对于大型环境、海量环境或者用三维地图表示环境时，所 涉及的数据维度更大因此，未知环境地图构建中需要选择恰当的环境 地图表示法，以控制或者降低数据维度。 2 ) 数据对应问题。数据对应问题( c o r r e s p o n d e n c ep r o b l e m ) ，也称为数据关联 问题( d a t aa s s o c i a t i o np r o b l e m ) ，是确定在不同时间不同点上记录的传感器 浙江大学博士学位论文1 绪论 z 、 环境地图| 桃器入能姿； x 二7 图1 1 目定位与地图构建之间的关系 测量数据是否对应于真实世界中的同一物理实体，对应的正确与否直接 关系到地图学习和机器人自定位的准确性。 3 ) 环形环境问题。如果机器人仅仅沿着走廊来回，那么当它往回走时，可 以根据前面构建的局部地图逐渐地校正里程计误差。而环形环境使机器 人通过不同的路径回到原来的位置，当环形闭合时，累积的里程计误差 可能会变得非常大，从而使机器人无法判断是回到了原来的位置还是一 个新的位置。 4 ) 动态环境问题。真实世界是动态的，并且存在着多种多样的动态变化， 包括人的走动、物体状态的变化和环境的调整，因此面向动态环境的地 图构建是机器人在实际应用中必须要考虑的一个问题。环境动态变化特 性的主要影响在于，当环境随着时间变化而变化时，传感器测量的解释 也随之增加例如当机器人面对着一个原来建模为开着的而现在关闭的 门时，可以有两种解释，门的状态改变了，或者机器人并不在它所认为 的地方。这种解释的增加极大地增加了同时定位与地图构建的求解难度。 5 ) 探测规划问题。探测规划的目标是使机器人能够自主地完成未知环境地 图构建，其困难在于规划算法所面对的是局部和不完全的环境地图，而 规划结果却将直接影响到地图学习和机器人自定位的可行性、鲁棒性和 精确性，以及任务实现的高效性。 4 浙江大学博士学位论文l 绪论 1 3 地图构建研究发展综述 1 3 1 早期的地图构建和自定位问题研究 在上个世纪8 0 年代和9 0 年代早期，地图构建与自定位是两个相互分离 的问题早期的地图构建研究中，假设机器人移动过程中的所有位姿可以由 里程计获得，是确定的。在此前提下，研究人员提出了多种将距离传感器测 量信息转化为地图的方法，如e l f e s 2 7 1 于1 9 8 7 年提出了基于声纳的栅格地图 构建法，c h a t i l a 和l a u m o n d 【屹1 于1 9 8 5 年提出采用简单的几何形状表示环境 地图，k u i p e r s 和b y u n t 5 5 1 于1 9 9 1 年提出了拓扑地图构建法， c h o s e t 和 b u r d i c k t l 3 】于1 9 9 7 年提出了基于声纳信息构建推广分层v o r o n o i 图( h g v g h i e r a r c h i c a lg e n e r a l i z e dv o r o n o ig r a p h ) 的方法。这些方法为后期研究同时定位 与地图构建问题奠定了基础，相对应的栅格地图表示法、几何特征地图表示 法和拓扑地图表示法也成为目前经典的地图表示法。 自定位问题通常也称为位姿估计问题，是指在给定环境地图的条件下， 根据传感器感知数据和机器人的运动控制估计机器人相对于环境地图的位 姿。根据机器人在定位过程中已知信息的不同，自定位问题可分为路径跟踪 问题、全局定位问题和机器人绑架问题。代表性方法有c o x 提出的基于图像 与模板匹配的位姿估计法【1 7 】、f o x 等提出的m a r k o v 定位法【3 1 1 和t h r u n 等提 出的m o n t ec a r l o 定位法【1 1 舶c o x 提出的位姿估计方法简单，但要求初始位 置已知，只适用于路径跟踪问题m a r k o v 定位法和m o n t ec a r l o 定位法适用 于初始位置未知的全局定位问题。其中，m a r k o v 定位法成功应用于自主移动 机器人r h i n o 和m i n e r v a ，在波恩的德意志博物馆和华盛顿的美国历史国家 博物馆中进行了基于自定位的导航实验验谢7 ，1 1 1 1 m a r k o v 定位法的主要缺点 是计算量和内存要求都相当的大，而且栅格尺寸和表示状态的精度是预先固 定的。m o n t ec a r l o 定位法将粒子滤波与机器人的感知概率模型和运动概率模 型相结合，通过维持一组样本集合表示位置的不确定性，而不是通过概率密 度函数表示。动态环境下的自定位和绑架问题是目前自定位领域的主要难点 浙江大学博士学位论文 1 绪论 1 3 2 同时定位与地图构建研究的起源与发展 随着未知环境地图构建研究的深入，研究人员发现，里程计测量误差对 一致性地图构建有着重要影响1 9 8 7 年，s m i t h ，s e l f 和c h e e s e m a n 提出了同 时估计机器人位姿和地图陆标位置的重要性，并给出了基于扩展卡尔曼滤波 进行机器人位姿和陆标位置估计的概率求解方法【9 8 一o o l 。2 0 世纪9 0 年代中后 期开始，机器人未知环境地图构建被确定为是同时定位与地图构建问题 ( s l a m 或c m l ) ，并迅速成为国际研究热点国外著名研究机构卡耐基梅陇 大学机器人研究所、麻省理工学院、悉尼野外机器人研究中心、德国t h e u n i v e r s i t y o f f r e i b u r g 等研究机构先后开展这一方面的研究。国际著名机器入 学术会议i c r a ( i n t e m a t i o n a lc o n f e ：r e n c eo fr o b o t i c s a n da u t o m a t i o n ) 和 i r o s ( i e e e r s ji n t e r n a t i o n a lc o n f e r e n c eo ni n t e l l i g e mr o b o t sa n ds y s t e m s ) 每 年设立s l a m 方面的专题讨论会。国内中科院自动化研究所、上海交通大学、 哈尔滨工业大学、浙江大学、北京大学等科研机构和院校也致力于这一方向 的研究。 在过去二十年的发展中，研究人员结合室内、室外，水下、地下、太空 等各种环境，在s l a m 方法、以及与之密切相关的环境地图表示、探测规划 等方面开展了广泛而深入的研究，取得了一系列重要进展。 1 3 3 地图表示方法研究进展 1 3 3 1 栅格地图表示法 栅格地图也称为占用栅格地图，由m o r a v e c 和e l f e s 在1 9 8 5 年提出【7 8 1 。 其基本思想是将环境分解成一系列离散栅格，每个栅格有一个值，表示该栅 格被障碍物占用的情况。一般采用布尔贝叶斯滤波法根