1、 （申请工学硕士学位论文）未 知 环 境 下 基 于 SLAM的 移 动机 器 人 导 航 算 法 研 究培 养 单 位 ：物 流 工 程 学 院学 科 专 业 ：机 械 制 造 及 自 动 化研 究 生 ：韩 锐指 导 教 师 ：李 文 锋 教 授2006 年 5 月分类号 密 级 UDC 学校代码 10497 学 位 论 文中文题目：未知环境下基于 SLAM 的移动机器人导航算法研究 英文题目： A Research to the SLAM-based Navigation Algorithm for Mobile Robots in Unknown Environments 研究生姓名：
2、 韩 锐 指导教师：姓名 李文锋 职称 教授 学位 博士 单位名称 物流工程学院 邮编 430063 申请学位级别 硕 士 学科专业名称 机械制造及自动化 论文提交日期 2006.4 论文答辩日期 2006.5 学位授予单位 武汉理工大学 学位授予日期 答辩委员会主席 评阅人 武汉理工大学硕士学位论文- II - - - 2006 年 5 月武汉理工大学硕士学位论文- I - - - 摘 要智能移动机器人是一种在复杂的环境下工作的具有自规划、自组织、自适应能力的机器人。导航算法的研究是智能机器人研究领域的一个热点话题。智能导航的目的就是在没有人干预下使机器人有目的地移动并完成特定任务，进行特定
3、操作。本文旨在结合国家自然科学基金和湖北省青年杰出人才基金项目的需求，研究移动机器人同时定位与制图（Simultaneous Localization and Mapping，SLAM）问题，并在此基础上，研究机器人导航算法，使得机器人在完全未知结构化环境中实现“完全自主” 。文章首先回顾了导航技术的发展，对导航技术中的核心问题：定位与制图进行了详细分析，指出了机器人定位与制图研究中存在的问题，包括制图复杂度、数据匹配难度以及定位制图关联度等；在此基础上引出了本研究的重点：移动机器人同时定位与制图（SLAM）算法，并对其算法构架、属性、以及分类等相关内容进行了介绍。针对基于点特征的同时定位与制
4、图算法中存在的计算复杂度与信息丰富度之间的矛盾，本文提出了一种基于线特征的同时定位与制图算法。文章对基于线特征的 SLAM 算法进行了详细的阐述，给出了包括机器人运动模型、观测模型的建立、数据匹配、状态更新、地图建立、地图管理等方面的相关公式；并通过仿真实验证实了本算法的正确性与可靠性。针对导航算法中对路径规划的要求，本研究中着重考虑了机器人的局部规划即：避障；并对避障算法 VFH/VFH进行了剖析。根据 VFH/VFH算法与SLAM 算法的特点，将二者相结合，形成了一种新的机器人导航算法。该导航算法较基于 VFH/VFH的导航算法而言，使用范围更广，导航效果更佳。关键词：导航，同时定位与制图
5、，VFH/VFH 武汉理工大学硕士学位论文- II - - - AbstractIntelligent robots are a kind of robots that are able to work in complex environments with the capacities of self-organizing and self-planning. Navigation problem is a hot issue concerned in researching on such kind of robots. Its aim is to move purposely and
6、do the job without aids. With supports of the project of National Natural Science Foundation of China and the project of Excellent Youth Fund in Hubei province, this paper aims to develop a new algorithm for navigating based on the Simultaneous Localization and Mapping (SLAM) algorithm to make the r
7、obots totally autonomous in the unknown but structured environments.The navigation techniques are firstly reviewed in this paper and then the Simultaneous Localization and Mapping (SLAM) problem is introduced, based on the analysis of the localization problem and the map building problem which are t
8、wo key points in the navigation techniques, including its structure, characteristics, categories and so on. As there is a conflict between the requirements of computational complexity and information-richness within the point-feature based SLAM algorithm, a line-feature based SLAM algorithm is well
9、presented in this paper. All operations required for building and maintaining this map，such as model-setting, data association, and state-updating are described and formulated. This approach has been programmed and successfully tested in the simulation work To meet the need of path planning in navig
10、ation, here we mainly concern the local planning, that is, obstacle avoiding. We introduce the VFH/VFH+, an algorithm for obstacle avoidance, in detail in the paper. What is more, in our work, we combine VFH and SLAM together to develop a new way for navigation, which has more applications and behav
11、es better than the one based merely on VFH does.Key words: navigation, SLAM, VFH/VFH武汉理工大学硕士学位论文- III - - - 目 录第 1 章 绪 论 11.1 课题研究的目的与意义 11.2 课题研究的内容 21.3 论文组织结构 2第 2 章 移动机器人导航技术 42.1 机器人导航概述 42.2 移动机器人导航方式 42.3 移动机器人的定位问题 62.4 移动机器人的制图问题 72.4.1 地图的类型 72.4.2 机器人制图存在的问题 82.4.3 同时定位与制图问题 92.5 本章小结 10第
12、 3 章 同时定位与制图（SLAM）算法 113.1 同时定位与制图算法介绍 113.1.1 SLAM 算法性质 113.1.2 SLAM 算法分类 123.2 基于特征 SLAM 算法构架简介 143.3 传感器的选择及特征提取 153.3.1 传感器选择 153.3.2 特征提取 173.4 噪音模型建立 173.5 滤波技术简介 173.6 卡尔曼滤波简介 183.6.1 线性卡尔曼滤波简介 193.6.2 扩展卡尔曼滤波（EKF）简介 213.7 本章小结 22第 4 章 一种基于线特征 SLAM 算法研究 244.1 过程模型建立 244.2 观测模型的建立 264.3 算法的实施
13、26武汉理工大学硕士学位论文- IV - - - 4.3.1 机器人运动初始化 264.3.2 数据匹配 274.3.3 状态更新 304.3.4 新信息处理 314.3.5 地图管理 324.4 SLAM 算法仿真 334.4.1 仿真环境的创建 334.4.2 SLAM 算法示例 354.5 本章小结 37第 5 章 机器人避障算法 385.1 常见的避障算法介绍 385.2 VFH 避障算法介绍 395.2.1 CV（Certainty Value）值的确定 395.2.2 VFH 算法阐述 415.2.3 VFH+ 算法阐述 435.3 VFH+算法仿真 475.3.1 仿真环境的创建
14、 475.3.2 仿真结果说明 495.4 本章小结 51第 6 章 基于 SLAM 的导航算法 526.1 基于 SLAM 的导航算法介绍 526.2 基于 SLAM 的导航算法特点 536.3 导航新算法的仿真 546.4 本章小结 55第 7 章 全文总结及展望 567.1 全文总结 567.2 本文主要贡献 577.3 未来研究方向 57参考文献 58致 谢 62作者攻读硕士期间参与项目及发表的论文 63武汉理工大学硕士学位论文- 1 - - - 第 1章 绪 论机器人的诞生和机器人学的建立和发展是 20 世纪自动控制最具说服力的成就，是 20 世界人类科学技术进步的重大成果，而作为机
15、器人中重要分支之一的移动机器人更是给人们带来了无限的惊喜。移动机器人的研究始于 20 世纪 60 年代末期。斯坦福研究所（SRI）的 Nils NVILSSEN 和 Charles Rosen 等人，在 1966 年至 1972 年中研制出了取名 Shakey 的自主移动机器人，其目的是研究、应用人工智能技术以及在复杂环境下机器人系统的自主推理、规划和控制；20 世纪 70 年代末，随着计算机的应用和传感器技术的发展，移动机器人研究又出现了新的高潮；20 世纪 90 年代以来，以研制高水平的环境信息传感器和信息处理技术，高适应性的移动机器人控制技术、真实环境下的规划技术为标志，开展了移动机器人
16、更高层次的研究 1。目前，移动机器人正向着具有自组织、自学习、自适应的智能化方向发展，导航能力的高低是移动机器人智能化水平的重要体现。随着移动机器人应用领域的日益增加，对移动机器人导航研究不断提出新的课题，使移动机器人的导航研究不断深入和发展 234。1.1 课题研究的目的与意义智能移动机器人是一种在复杂的环境下工作的具有自规划、自组织、自适应能力的机器人。智能导航研究的目标就是在没有人干预下使机器人有目的地移动并完成特定任务，进行特定操作。机器人通过装配的信息获取设备来获得外部环境信息，判定自身状态，实现自我定位，规划并执行下一步动作。 在移动机器人导航控制理论和方法研究中，确定性环境的导航
17、控制方法已经取得了大量的研究和应用成果。对未知环境中的导航控制也开展了一些研究，并提出了若干方法，但是尚未形成统一和完善的体系结构，还有许多关键理论和技术问题有待解决与完善。这些问题包括环境的建模、定位、导航控制器的学习与优化、故障诊断以及路径规划等。未知环境中的移动机器人只具有较少的先验知识，其导航控制方法涉及环境认知、优化策略、知识表示与获取等多武汉理工大学硕士学位论文- 2 - - - 项关键问题。对移动机器人在未知环境中导航理论和方法的研究，将推动认知科学、模式识别、非线性控制等前沿学科的研究，带动航天、海洋、军事、建筑、交通、工业和服务业等领域移动机器人导航控制系统的研究开发，为无人
18、勘探车、无人排险车和无人运输车等用于航天、军事、深海作业和核工业领域的移动机器人系统的应用奠定理论和技术基础。具体来看比如：在民用方面，可以将其用于物流自动化仓库中的 AGV、AHV 小车，以提高物流自动化程度；在军事方面，可以有助于实现机器人智能侦察与作战等。.1.2课题研究的内容本课题在国家自然科学基金（60475031）和湖北省青年杰出人才基金项目（2005ABB021）的资助下，研究在未知环境中，移动机器人自主的建立环境地图并根据该地图实现定位、避障与导航的算法。主要针对静态的、结构化的未知环境进行研究。研究的主要内容包括以下几方面：（1） 避障策略的拟订；机器人在运动之前都应进行障碍
19、物检测，合理的避障算法对于成功的导航而言显得尤为重要。本研究中将对避障算法 VFH（ Vector Field Histogram）进行分析与应用。（2） 定位方法的设计；本文主要研究的是移动机器人在自身位置信息与环境信息均不确定的情况下，通过传感器了解环境来自我定位，同时根据自身位置信息绘制环境地图，并根据该地图实现导航目的。因此，本论文将采用同时定位与制图（SLAM）算法对机器人进行定位。论文将会对本研究中提出的基于线特征 SLAM 算法进行详细的剖析。（3） 导航新算法的提出；在研究避障算法 VFH 以及定位算法 SLAM 的基础上，找出两者结合的可能性以及优越性，构造新的导航算法。1.
20、3论文组织结构由于机器人自主导航的最重要内容就是机器人的定位问题，所以本文的研武汉理工大学硕士学位论文- 3 - - - 究工作也就围绕机器人的自主定位进行。在综述国内外研究的基础上，深入研究了基于线特征的机器人同时定位与制图算法；详细介绍了避障算法VFH/VFH，并将两者结合构造了一种新的导航算法。论文主要分为七章：第一章为绪论，主要介绍了本论文所研究的目的与意义以及研究的主要内容及要处理的关键问题；并对论文的组织结构进行概括说明。第二章中主要对移动机器人导航技术进行了概述，包括移动机器人的导航方式以及机器人导航中的两个主要问题：机器人定位与制图；并追踪概述了相关技术的国内外发展现状与发展趋
21、势。第三章对移动机器人同时定位与制图（SLAM）算法，特别是基于特征的SLAM 算法进行了详细的剖析，包括算法的属性、分类，构架等。第四章介绍了本研究中提出的一种基于线特征的 SLAM 新算法，详细分析了实现算法所需要的各个步骤；并通过仿真实验证实了该新算法的正确性与可靠性。第五章对主要研究了机器人避障算法 VFH 以及 VFH，包括：算法的构架以及实现算法的各个步骤等；并对算法进行了仿真实验。在第六章中，首先介绍了同时定位与制图算法与避障算法 VFH/VFH+结合、产生新导航算法的可能性以及新算法的优越性；然后在对导航新算法进行说明的同时，通过仿真实验证实了其正确性与鲁棒性。第七章为全文的总结以及对今后工作的展望。文章结构框架如图 1-1 所示。其中星号标示处为本研究的创新点。图 1-1 全文结构框架
