即时定位及地图构建SLAM

1、Simultaneous Localization and Mapping即时定位与地图构建即时定位与地图构建 SLAM指的是机器人在自身位置不指的是机器人在自身位置不确定的条件下确定的条件下,在完全未知环境中在完全未知环境中创建地图创建地图,同时利用地图进行自主同时利用地图进行自主定位和导航。定位和导航。 SLAM问题可以描述为问题可以描述为: 机器机器人在未知环境中从一个未知位置开人在未知环境中从一个未知位置开始移动始移动,在移动过程中根据位置估在移动过程中根据位置估计和传感器数据进行自身定位计和传感器数据进行自身定位,同同时建造增量式地图。时建造增量式地图。SLAM（Simultaneo

2、us Localization And Mapping ）中文称中文称 “同步定位及建图同步定位及建图” 是目前在机器人定位方面的热门研究课题。到目是目前在机器人定位方面的热门研究课题。到目前为止，也取得了不少进展。前为止，也取得了不少进展。定位定位(localization): 机器人必须知道自己在机器人必须知道自己在 环境中位置。环境中位置。建图建图(mapping): 机器人必须记录环境中特机器人必须记录环境中特 征的位置（如果知道自己的位置）征的位置（如果知道自己的位置）SLAM： 机器人在定位的同时建立环境地图机器人在定位的同时建立环境地图其基本原理是运过概率统计的方法，通过多特征其

3、基本原理是运过概率统计的方法，通过多特征匹配来达到定位和减少定位误差的。匹配来达到定位和减少定位误差的。 基本的基本的SLAM应用的应用的kalman filter。 Sk表示传感器测试获取数据，表示传感器测试获取数据，Mk-1表示第表示第K-1时刻的局部地图，时刻的局部地图，Rk表示表示K时刻机器人的位姿。时刻机器人的位姿。SLAM问题包括四个基本方面问题包括四个基本方面1） 如何进行环境描述，即环境地如何进行环境描述，即环境地图的表示方法；图的表示方法；2） 怎样获得环境信息，机器人在怎样获得环境信息，机器人在环境中漫游并记录传感器的感知数环境中漫游并记录传感器的感知数据，这涉及到机器人的

4、定位与环境据，这涉及到机器人的定位与环境特征提取问题；特征提取问题；3） 怎样表示获得的环境信息，并怎样表示获得的环境信息，并根据环境信息更新地图，这需要解根据环境信息更新地图，这需要解决对不确定信息的描述和处理方法；决对不确定信息的描述和处理方法；4） 发展稳定、可靠的发展稳定、可靠的SLAM方法。方法。该领域所涉及的关键性问题可以归结为：该领域所涉及的关键性问题可以归结为：(1) 地图的表示方式地图的表示方式 (大致可分为大致可分为3类类:栅格表示、几何特征表示和拓扑图表示栅格表示、几何特征表示和拓扑图表示)(2) 不确定性信息处理方法不确定性信息处理方法-不确定性信息处理必须解决以下问题

5、：不确定性信息处理必须解决以下问题： 在地图和位置的表示中，如何描述运动和感知信息的不确定性? 在迭代过程中，如何处理旧信息与新信息的关系，连续更新地图与位置? 如何依据不确定的信息进行决策?(3) 数据的关联；数据的关联； (为了获得全局的环境地图和实现定位，还需要将不同时间、不同地 点的感知信息进行匹配和联合，存在局部数据之间的关联问题，也存在局部数据与全局数据的关联与匹配问题)(4) 自定位；自定位； (移动机器人的定位按照有无环境地图可以分为基于地图的定位和无地图的定位)(5) 探索规划探索规划 (主要目的是提高地图创建的效率，使机器人在较短的时间内感知范围覆盖尽可能大的区域，在这方面

6、的研究成果较少)环境的描述环境的描述-地图地图 目前各国研究者已经提出了多种表示法，大致可分为三类：栅格表示、几何信息表示和拓扑图表示，每种方法都有自己的优缺点。 栅格地图表示法即将整个环境分为若干相同大小的栅格，对于每个栅格各指出其中是否存在障碍物。这种方法最早由Elfes和Moravec提出，而后Elfes进行了进一步的研究。优点是(1)创建和维护容易，(2)尽量保留了整个环境的各种信息，(3)借助于该地图，可以方便地进行自定位和路径规划。缺点在于：当栅格数量增大时(在大规模环境或对环境划分比较详细时)，对地图的维护行为将变得困难，同时定位过程中搜索空间很大，如果没有较好的简化算法，实现实

7、时应用比较困难。 几何信息地图表示法是指机器人收集对环境的感知信息，从中提取更为抽象的几何特征，例如线段或曲线，使用这些几何信息描述环境。该表示法更为紧凑，且便于位置估计和目标识别。几何方法利用卡尔曼滤波在局部区域内可获得较高精度，且计算量小，但在广域环境中却难以维持精确的坐标信息。几何信息的提取需要对感知信息作额外处理，且需要一定数量的感知数据才能得到结果。 拓扑地图抽象度高，特别在环境大而简单时。这种方法将环境表示为一张拓扑意义中的图(graph)，图中的节点对应于环境中的一个特征状态、地点。如果节点间存在直接连接的路径则相当于图中连接节点的弧。优点是：(1)有利于进一步的路径和任务规划，

8、(2)存储和搜索空间都比较小，计算效率高，(3)可以使用很多现有成熟、高效的搜索和推理算法。缺点在于对拓扑图的使用是建立在对拓扑节点的识别匹配基础上的，如当环境中存在两个很相似的地方时，拓扑图方法将很难确定这是否为同一点。 SLA M中定位与环境特征提取中定位与环境特征提取移动机器人自定位与环境建模问题是紧密相关的。环境模型的准确性依赖于定位精度，而定位的实现又离不开环境模型。在未知环境中，机器人没有什么参照物，只能依靠自己并不十分准确的传感器来获取外界信息，如同一个盲人在一个陌生环境中摸索的情况。这种情况下，定位是比较困难的。有地图的定位和有定位的地图创建都是容易解决的，但无地图的定位和未解

9、决定位的地图创建如同鸡-蛋问题，无从下手。已有的研究中对这类问题的解决方法可分为两类：一类利用自身携带的多种内部传感器(包括里程仪、罗盘、加速度计等)，通过多种传感信息的融合减少定位的误差，使用的融合算法多为基于卡尔曼滤波的方法。这类方法由于没有参考外部信息，在长时间的漫游后误差的积累会比较大。另一类方法在依靠内部传感器估计自身运动的同时，使用外部传感器(如激光测距仪、视觉等)感知环境，对获得的信息进行分析提取环境特征并保存，在下一步通过对环境特征的比较对自身位置进行校正。但这种方法依赖于能够取得环境特征。环境特征提取的方法有：(1)Hough transform是一类基于灰度图探察直线和其他

10、曲线的方法。该方法需要一簇能被搜索的预准备的特定曲线，并根据显示的灰度图中一簇曲线产生曲线参数。(2)Clustering分析是一种数据探测工具，对于未分类样例是有效的，同时，它的目标就是把所针对对象分组成自然类别或基于相似性或距离的簇类。在被提取对象类别未知的情况中，簇技术是一类比Hough Transform更有效的技术。簇类应是以凝聚为中心，而不是支离破碎的、不相交的。而环境特征有时是很难提取出的，例如：环境特征不够明显时；传感器信息比较少，难以从一次感知信息中获得环境特征。 不确定信息的描述和处理方法不确定信息的描述和处理方法 在未知环境中，环境信息的不确定性尤为明显。研究人员已经提出

11、了多种用来处理不确定性的度量方法，如模糊度量、概率度量、信任度量、可能性度量、证据理论度量等等。目前在SLAM中使用较多的主要是模糊度量和概率度量的方法。 以概率描述信息的不确定性，其优点在于：适应不确定模型，对于性能差的传感器也适用，在实际应用中鲁棒性较好，在很多实现中得到应用。缺点是计算量较大，算法建立在一定假设条件上，而假设的合理性有争议。因此，有些学者认为使用模糊度的描述方法更适合于该任务。他们认为模糊逻辑(fuzzy logic)提供了一个关于处理不确定信息更自然的框架，是一个更为鲁棒且有效的工具(尤其对于声纳感知过程引起的不确定性)。同时，在对多种不确定性信息进行建模和融合时有更多

12、的操作符供选择。 几种典型几种典型SLAM方法方法 目前SLAM方法大致可分为两类：一类为基于概率模型的方法，另一类为非概率模型方法。许多基于卡尔曼滤波的SLAM方法如完全SLAM、压缩滤波、FastSLAM就属于概率模型方法。非概率模型方法有SM-SLAM、扫描匹配、数据融合(data association)、基于模糊逻辑等。 在一个未知的室内结构化环境中提出了基于栅格表示的局部模型与基于几何信息表示的全局模型相结合的环境建模方式。环境特征的提取采用了Hough transform与Clustering相结合的方法。感知数据的融合采用了扩展卡尔曼滤波方式。 提出的算法不需任何人为设定的参照

13、物(如路标、灯塔)并且可适用于非多边形及动态环境，同时和基于SLAM的卡尔曼滤波策略比较，其计算复杂度较小、与路标数量、环境大小无关。环境建模策略由3部分构成：(1)收集环境信息；(2)扫描注册；(3)构建栅格地图。在扫描注册中综合使用了几何模式匹配与扫描匹配。环境特征提取采用Hough transform技术。采用HIMM (Histogramic In-Motion Mapping)方法来构建栅格地图。在定位方面，融合使用地图匹配与基于Petri网的离散事件控制策略。 有以下优势：(1)在无任何人工路标的情况下，能创建准确地图；(2)扩展了扫描匹配的应用范围，使其能应用于非多边形的环境；(

14、3)提高了几何模式匹配在多边形环境中的精确度；(4)每次扫描注册精度都将与以前所有局部区域扫描结果进行比较，以保证全局地图的准确性；(5)计算复杂度较小。离散事件控制策略的运用能更好的进行位置估测与对定位错误的处理。 提出了使用SM(Set Membership)方法，解决同种多机器人SLAM问题。在地图融合方面，把2D地图分解为两个1D地图来进行，进一步降低计算复杂度。在SLAM中使用SP-Model(Symmetries and Perturbations Model)，对任何几何元素它提供了一个统一的表示方式，并避免了参数过多的问题。说明：机器人在定位误差随着机器人的移动而增加。说明：机

15、器人在定位误差随着机器人的移动而增加。 说明：机器人在定位误差随着机器人的移动而增加，但是由于有了路标的纠正，其误差相对就小了很多。说明：机器人在定位误差随着机器人的移动而增加，但是由于有了路标的纠正，其误差相对就小了很多。说明：通过说明：通过2次对路标的测定，其定位误差已经大大减少次对路标的测定，其定位误差已经大大减少 说明：经过说明：经过3次误差校正，其定位精度已经很好了，但是随着路标位置的丢失，其定位误差又一次的扩大了。次误差校正，其定位精度已经很好了，但是随着路标位置的丢失，其定位误差又一次的扩大了。基于霍夫曼方法的基于霍夫曼方法的SLAM的基本过程为：的基本过程为： 1）使用）使用e

16、xtend kalman filter （EKF) 进行定位进行定位 2）获取所有的路标和机器人的位置信息作为先决条件）获取所有的路标和机器人的位置信息作为先决条件 3）使用矢量方程来存储路标和机器人的位置）使用矢量方程来存储路标和机器人的位置4）通过循环迭代来减少每次的误差量）通过循环迭代来减少每次的误差量状态估计是卡尔曼滤波的重要组成部分。一般来说，根据观测数据状态估计是卡尔曼滤波的重要组成部分。一般来说，根据观测数据对随机量进行定量推断就是估计问题，特别是对动态行为的状态估对随机量进行定量推断就是估计问题，特别是对动态行为的状态估计，它能实现实时运行状态的估计和预测功能。比如对飞行器状态

17、计，它能实现实时运行状态的估计和预测功能。比如对飞行器状态估计。状态估计对于了解和控制一个系统具有重要意义，所应用的估计。状态估计对于了解和控制一个系统具有重要意义，所应用的方法属于统计学中的估计理论。最常用的是最小二乘估计，线性最方法属于统计学中的估计理论。最常用的是最小二乘估计，线性最小方差估计、最小方差估计、递推最小二乘估计等。其他如风险准小方差估计、最小方差估计、递推最小二乘估计等。其他如风险准则的贝叶斯估计、最大似然估计、随机逼近等方法也都有应用。则的贝叶斯估计、最大似然估计、随机逼近等方法也都有应用。 受噪声干扰的状态量是个随机量，不可能测得精确值，但可对受噪声干扰的状态量是个随机

18、量，不可能测得精确值，但可对它进行一系列观测，并依据一组观测值，按某种统计观点对它进行它进行一系列观测，并依据一组观测值，按某种统计观点对它进行估计。使估计值尽可能准确地接近真实值，这就是最优估计。真实估计。使估计值尽可能准确地接近真实值，这就是最优估计。真实值与估计值之差称为估计误差。若估计值的数学期望与真实值相等，值与估计值之差称为估计误差。若估计值的数学期望与真实值相等，这种估计称为无偏估计。卡尔曼提出的递推最优估计理论，采用状这种估计称为无偏估计。卡尔曼提出的递推最优估计理论，采用状态空间描述法，在算法采用递推形式，卡尔曼滤波能处理多维和非态空间描述法，在算法采用递推形式，卡尔曼滤波能

19、处理多维和非平稳的随机过程。平稳的随机过程。 卡尔曼滤波理论的提出，克服了威纳滤波理论的局限性使其在卡尔曼滤波理论的提出，克服了威纳滤波理论的局限性使其在工程上得到了广泛的应用，尤其在控制、制导、导航、通讯等现代工程上得到了广泛的应用，尤其在控制、制导、导航、通讯等现代工程方面。工程方面。 图图1：初始位置：初始位置（由于机器人相对于路标（由于机器人相对于路标A的位置为估计值，所以路标的位置为估计值，所以路标A用圆圈表示用圆圈表示A的实际的可能值在圆圈内）的实际的可能值在圆圈内）图图2：机器人移动到新位置：机器人移动到新位置（在新的位置，机器人相对于（在新的位置，机器人相对于A的真实值可能落在

20、圈内）的真实值可能落在圈内）图图3：路标：路标C被观测到被观测到（在新的位置，路标（在新的位置，路标C被观测到，路标被观测到，路标C的相对于的相对于A的位置也是一个估计值（更大的圈）的位置也是一个估计值（更大的圈）图图4：路标：路标B被观测到被观测到图图5：机器人返回到初始位置：机器人返回到初始位置（此时机器人的位置相对于没有移动前更加不确定，一个超大的椭圆表示了其可能的真实位置值范围）（此时机器人的位置相对于没有移动前更加不确定，一个超大的椭圆表示了其可能的真实位置值范围）图图6：对：对A点的重新测量点的重新测量（通过对（通过对A的重新测量，图的重新测量，图4中的超大椭圆值被大大的缩小了，其位置真值落入了一个比较小的范围内