武汉科技大学本科毕业设计
1.1 移动机器人定位和地图创建问题
1.1.1 移动机器人国内外发展状况
1950年和1951年，William Grey Walter研制了两个可完成自动避障等智能行为的移动机器人。在20世纪50年代初期，Marvin Minsky等人研制了具有跟踪功能的移动机器人。1956年，在由美国国防部高级研究计划局（DARPA）主办的Dartmouth会议上，正式提出了“人工智能”概念，认为移动机器人应能够执行和学习有意义的任务，一定程度上能够模仿动物或人的能力。1969年，Nilsson等人在斯坦福机器人研究所（SRI）研制了第一个智能移动机器人Shakey，它装备了摄像机、测距仪和接触传感器等设备，并通过无线连接与DEC．PDP 10计算机相连，其任务是自动避障和运动目标跟踪。在20世纪70年代末期，Hans Moravec在SRI研制了CART移动机器人，它能够利用摄像机进行避障，并能利用连续的多幅图像构建二维环境模型，并可以实现路径规划。在20世纪70年代末期，法国的系统分析与架构实验室（LAAS）研制了HILARE机器人，这是欧洲的第一个移动机器人研究项目，HILARE安装了视觉传感器、激光测距仪和超声波传感器等设备，用二维多边形环境模型和全局坐标系统实现导航和路径规划功能。
目前，移动机器人的研究范围已经扩展到水下、空中、地面、甚至太空和行星表面等多种环境，如美国马里兰系统工程实验室（Marine Systems Engineering Laboratory）研制的EAVE III型自主式水下移动机器人，美国海军研制的新型战场准备自主水下航行器（BPAUV）、美国无人车辆协会（the Joint of Unmanned Vehicle）组织开展的自主式航空飞行器的研究，世界著名移动机器人制造商IROBOT公司的金字塔探索者Pyramid Rover、月球车，以及卡耐基-梅隆大学（CMU）研制的CMU-Rover，日本Tsukuba大学的Yamabiko和MELDOG，法国系统分析与结构实验室（LAAS）的Hilare2，德国Karlsruhe大学的KAMRO等。美国航空航天局（NASA）研制的第一代火星探测机器人Sojourner于1997年成功登陆火星，开启了人类利用移动机器人技术进行空间探测和开发的序幕。为了在火星上进行长距离探险，NASA又开始了新一代样机的研制，命名为Rocky7（如图1.2所示），并在Lavic湖的岩溶流上和干枯的湖床上进行了成功的实验。最值得一提的是，2004年1月美国NASA火星探测移动机器人Spirit（如图1.3所示）和Opportunity先后在火星表面顺利登陆。Spirit和Opportunity的成功着陆标志着人类发射的星际探测器自动化程度提升到了前所未有的水平，同时也标志着智能移动机器人的研究工作也已经提高到了一个前所未有的高度，正在为人类的进步发展贡献力量。我国也针对这一趋势制定了以月球为近期目标的空间探测计划。研究和发展我国的月球探测移动机器人技术，不但对于我国在激烈的空间技术和资源竞争中取得有力地位具有关键意义，同时也对包括移动机器人导航控制在内的相关技术的发展有巨大的促进作用。
我国对移动机器人的研究虽然起步较晚，但是越来越受到重视，国家863智能机器人组把智能移动机器人的研究作为今后发展的重点。以中科院自动化研究所、清华大学、
2
武汉科技大学本科毕业设计
国防科技大学、东北大学、上海交通大学、哈尔滨工业大学为代表的我国机器人研究基地，已经取得了令人瞩目的成果。
清华大学研制的THMR系列移动机器人系统；自动化所研制的集多种传感器、视觉、语音识别与会话功能于一体的智能移动机器人CASIA-I[3]；此外，沈阳自动化研究所机器人实验室研制的激光导引AGV、防爆机器人、“海极号”和“探索者号”水下机器人，香港城市大学智能设计、自动化以及制造研究中心的自动导航车和服务机器人，哈尔滨工业大学机器人研究所研制的能在未知、复杂、多变、恶劣的环境下运行的全方位轮式移动机器人平台等都说明了我国移动机器人技术取得的突出成就。但从总体水平上看，我国移动机器人技术比起发达国家还有一定的差距。
1.1.2 移动机器人的地图构建问题
移动机器人通过自身所带的传感器实现对外部环境的感知。由传感器获得的数据经处理后要以某种抽象的形式来对环境空间进行表达，并作为地图信息存储在移动机器人中。移动机器人利用对环境的感知信息实现环境的建模，自动的构建一个地图，利用地图给出的信息在外部环境中运动，并持续感知周围环境，进一步完善和更新地图。在移动机器人导航并自主定位过程中，按照一定的空间表达规则将传感器信息转换成地图的过程是移动机器人导航并自主定位的基础，而空间表达的方法又决定了地图的表达形式。因此，采用何种空间表达方法对移动机器人自主定位和地图的持续更新具有很大影响。目前地图创建方法很多大致可以归为四类:栅格表示法、几何信息表示法、拓扑图表示法和混合表示法。
1. 基于栅格的地图表示法
栅格地图表示法最先是由Moravec和Elfes于1985年提出的。它将机器人工作环境划分为一系列栅格，其中每个栅格都被分配一个概率值。此概率值表示该栅格被障碍物占据的可能性大小。栅格地图的优点在于易于重建和维护，对任何一个栅格的感知信息可以直接与环境中的某个区域相对应，特别适合于处理超声测量数据。但是环境空间的分辨率和栅格大小相关，当需要增加分辨率时就必须缩小栅格的大小，进而增加了运算的时间和空间复杂度。另外，在传统的栅格地图表示法中，每个栅格之间被认为是相互独立的，因此，利用栅格表示的地图和实际环境地图具有很大的不一致性[9]。为改进传统栅格地图表示法的这种缺点，Thrun提出了一种采用期望最大化方法进行环境地图表示的方法，同时还考虑了各个相邻栅格之间的依赖关系。在Bert等人的研究中，对环境采用全局栅格和局部栅格结合的方法进行建模，同时利用霍夫变换对栅格地图中的线段进行抽象描述，并采用卡尔曼滤波器进行位置估计。Stepan等人提出了一种基于单目摄像头和激光测距仪的栅格地图构造方法，对栅格地图的质量利用机器人的历史路径信息进行优劣评估。Noykov等人提出了一种利用声纳传感器数据进行栅格地图构造的方法，利用统计方法对声纳数据概率模型进行建模并结合模糊理论进行声纳数据融合。Grisetti
3
武汉科技大学本科毕业设计
等人采用Rao-Blackwellized粒子滤波器对栅格地图进行估计，采取自适应方法获取粒子数，同时，在粒子采样函数的选取时考虑了最近多次传感器的测量数据。
2. 基于特征的地图表示法
基于特征的地图表示法是指利用可以识别的环境路标进行环境地图的表示，其中每个路标特征都用几何原型进行表示。此种地图表示方法局限于可以进行参数化的路标环境，或者是可建模的对象环境，比如点、线、面等。对特征地图的重建大多都是基于外部传感器对环境的检测数据，然后利用这些检测数据进行环境路标特征的提取。对结构化的室内环境，可以利用一些简单的集合模型进行环境空间的表示，对于室外环境，可以采用曲面进行环境空间的表示。Drumhellor利用线段进行地图构造，并利用激光测距仪的测量数据进行机器人自身定位。Arras等人用激光测距仪数据提取水平直线特征，同时利用视觉系统进行垂直直线特征的提取，最后综合这些直线进行环境地图的构造。Roumeliotis等人针对激光测距仪对环境的检测数据提出了一种分层的路标检测方法，在底层采用两个卡尔曼滤波器分别进行环境拐角和线段等基本特征的检查，在上层再对底层检测到的特征进行较为复杂的路标特征合成，比如墙，门，地面等。Luis Pedraza等人提出利用B-样条的方法进行非结构化环境中的路标描述，然后运用扩展卡尔曼滤波器进行机器人定位。Luis Pedraza等人另外还提出采用B-样条曲线进行环境边界表示的方法，即BS-SLAM算法，BS-SLAM算法的意义在于它是第一个运用参数化方法进行环境曲线特征描述的算法。
3. 基于拓扑的地图表示法
利用拓扑地图进行机器人运行环境描述最先是由Brooks提出的。拓扑地图表示法中的地图是根据实际环境结构，由位置节点和节点之间的连线组成。其中节点表示环境中的特定地点，节点之间的连线表示的是不同地点之间的路径信息。拓扑地图可以组织为层次结构，例如在底层，一个位置可能就是一个房间，但是在更上一层则可能为一个建筑物。为了利用拓扑地图方法进行环境地图的表示，必须有效的识别环境中各个特定的地点。对结构化的环境而言，各个特定的地点可以容易进行识别，但是在非结构化的环境中，节点的识别会非常复杂。利用拓扑地图进行环境表示的关键在于拓扑地图中各个顶点的选取，David等人提出了一种基于声纳数据和视觉信息相结合的拓扑地图顶点选择方法，相对于单独采用声纳数据进行顶点检测，此方法可以得到更加精确的拓扑地图描述。Choset等人提出利用通用Voronoi图（Generalized Voronoi graph，GVG）进行环境地图表示的方法，在GVG地图表示中添加了机器人传感器的一些度量信息，通过对各个GVG图的匹配进行机器人自身定位。Ranganathan等人提出利用GVG图和视觉传感器检测到的路标进行地图表示的方法。另外，为更好地进行环境地图模型的描述，研究者还提出了拓扑地图和尺度地图混合进行环境表示的方法，通过在拓扑地图中加入尺度信息来补偿拓扑地图中的信息丢失。GVG地图表示法已经被用于美国国家航空和宇宙航天局空间站中的机器人三维定位问题研究中，这样的地图表示方法具有拓扑地图的高效性和尺度地图的一致性以及精确性等特点。
4
武汉科技大学本科毕业设计
4. 基于视图的地图表示法
在基于视图的地图表示方法中，对环境并不是利用拓扑形式或者路标特征进行表示，而是采用机器人的一系列历史路径估计信息进行表示。基于视图的地图表示方法首先是由Lu和Milios提出的，在他们的研究中，环境地图是由多次激光扫描数据和各个扫描数据之间的关系组成。Fleischer等人提出了基于视觉的视图地图表示方法，Malauchlan提出了一种基于批处理和迭代处理的三维环境视图表示方法。Eustice等人针对机器人在海底环境运行的特殊性，提出了一种新的地图表示方法VAN（Visually Augmented Navigation），在VAN的机器人定位与地图重建算法中，SLAM的状态向量由机器人在不同时刻的位姿组成。Eustice等人还对基于视图的地图表示方法中的信息矩阵，稀疏扩展信息滤波器（Sparse Extended Information Filter，SEIF）以及稀疏联合树滤波器（Thin Junction Tree，TJT）中的信息矩阵进行了比较，从比较结果可以看出，基于视图的地图表示方法中的信息矩阵相对于SEIF和TJT中的信息矩阵有两个优点，一是信息矩阵的稀疏性要更好，二是它对应信息矩阵的稀疏性是自然的，并不需要像SEIF那样经过强制的信息丢失处理。基于视图的地图表示法适合于那些并不容易进行特征抽象的复杂地图环境。
1.1.3 机器人的定位方法
在自主移动机器人中，无论是局部实时避障还是全局规划，都要精确地获得机器人及障碍物的当前状态，因此对于移动机器人来说，精确地位置估计是实现自主导航的必要内容，对移动机器人定位的研究具有非常重要的意义。目前，移动机器人多采用各种机载传感器进行定位。
1．里程计定位
在移动机器人的两个驱动电机组上均装有里程计，它们是使用最为广泛的导航工具之一，能在短距离内提供精确地定位，但它的误差是随着时间增加而累计增长的，尤其是方向误差。当用来长距离和长时间定位时，由于误差的不断累加，会导致移动机器人在行驶过程中发生很大的偏离，从而影响定位效果[9]。尽管有这个缺点，由于其在短距离内依然能够获得较好的效果。因此绝大多数的研究者还是认为里程计是机器人导航系统中的一个重要组成部分。
2．路标定位
基于人工路标、自然路标或者“灯塔”，一般来说，路标都有固定的已知位
置，机器人自身的传感器能对路标进行识别，参照路标进行相对定位。为了使问题简化，经常假设机器人的当前位置和方向角已经划定，机器人只需要在有限的区域内寻找路标。缺点是需要人工干预，在现场设置路标，这是人为对环境的再结构化，移动机器人的自主性不高。路标对信息的反馈存在一定的误差，这也影响了机器人对于自身位置的确定。
5
武汉科技大学本科毕业设计
3．视觉定位
视觉定位技术主要是利用摄像机获取工作空间的图像，通过图像处理、模式 识别等手段对获取的图片进行分析，提取有用的环境信息，为机器人的定位、路径规划、避障以及创建地图提供数据。其优点是具有很高的空间分辨率。探测范围广、精度高、能够获得场景的大部分信息。缺点是摄像头在使用过程中容易受到光线和环境的影响。且获得的图像提取和识别选用困难，耗费的计算了很大，实时性也不易满足。
4．GPS定位
GPS全球定位技术是一种应用范围较广的绝对定位技术。它利用环绕在地球上空的24颗卫星准确定位出使用者的准确位置。若是已知地面接收器与三个卫星之间的距离，从理论上来讲，就可以计算出接收器的经纬度和高度，单纯利用GPS定位精度还比较低，所以在移动机器人定位和导航中一般还同时融合里程计和其他传感器的数据，其缺点是不适合室内环境、水下环境以及对精度要求较高的移动机器人定位。
5．地图匹配定位
地图构建和匹配算法是基于地图匹配定位的关键，首先要获得机器人工
作环境的全局地图，在进行地图匹配定位时，利用把机器人机载传感器获取其局部地图，将局部地图和先存放在寄存器中的全局地图做比较，如果是匹配的，那么机器人就能确定在这个环境中的全局位置和方向。地图匹配的缺点是它对于机载传感器获得的局部地图要求比较高，地图上要有足够多的与全局特征匹配的特征点，而这些特征点在一般相对简单的环境里还是比较少的。
6．惯性定位
惯性定位是一种不依赖于任何外部信息的自主式定位。惯性传感器是移动机器人常用的一类内部传感器，一般利用陀螺仪计算移动机器人的姿态，利用加速仪计算出移动机器人的位置，将测量结果积分合成得到机器人的位姿。这种方式的优点是不需要外在的参照物，可以自主定位。缺点是惯性传感器数据会随着时间产生偏差，每次积分后原先的位置和方向上的微小误差都会随之放大，且有误差累计效应。
6