同时定位与地图构建

**同时定位与地图构建**（，簡稱**SLAM**），又称**同步定位与地图创建**，是机器人学中的一个概念：机器人从未知环境的未知地点出发，在运动过程中通过重复观测到的地图特征（比如，墙角，柱子等）定位自身位置和姿态，再根据自身位置增量式的构建地图，从而达到同时定位和地图构建的目的。

## 歷史
有关于SLAM的一个开创性工作是以R.C. Smith和P. Cheeseman为代表，在1986年作出的对空间不确定性的估测的研究。其他该领域的开拓工作由的研究团队在1990年代初所作出。

由Sebastian Thrun帶領的團隊設計出STANLEY自動駕駛車於2005年勝出了由美國國防高級研究計劃局（DARPA）發起的DARPA無人駕駛車大賽，其後在2007年再設計出另一自動駕駛車JUNIOR勝出了同樣由美國國防高級研究計劃局發起的城市無人駕駛車挑戰賽。當中的同步定位與地圖構建系統引起了全球廣泛注意，現在同步定位與地圖構建已被廣泛應用在機械人吸塵器，例如Neato Robotics的XV11，Google的自動駕駛汽車等。

## 操作性定义

这里说的地图，是用来在环境中定位，以及描述当前环境以便于规划航线的一个概念；它通过记录以某种形式的感知获取的信息，用以和当前的感知结果相比较，以支撑对现实定位的评估。在定位评估方面，地图提供的帮助程度，与感知的精度和质量成反相关。地图通常反映了它被描绘出来的时刻的环境状态，所以它并不一定反映它被使用的时刻的环境状态。

在误差和噪音条件下，定位和地图构建技术上的复杂度不支持两者同时获得连续的解。SLAM是这样一个概念：把两方面的进程都捆绑在一个循环之中，以此支持双方在各自进程中都求得连续解；不同进程中相互迭代的反馈对双方的连续解有改进作用。

地图构建，是研究如何把从一系列传感器收集到的信息，集成到一个一致性的模型上的问题。它可以被描述为“第一核心问题”——“这个世界长什么样？”地图构建的核心部分是环境的表达方式以及传感器数据的解释。

与之相比，定位，是在地图上估测机器人的坐标和姿势形态的问题；换而言之，机器人需要回答这里的“第二核心问题”：“我在哪？”典型的解包含以下两个方面：追踪——通常机器人的初始位置已知；全局定位——通常只给出很少，甚至不给出有关于起始位置环境特征的先验信息。

所以，SLAM被定义为以下问题：在建立新地图模型或者改进已知地图的同时，在该地图模型上定位机器人。实际上，这两个核心问题如果分开解决，将毫无意义；必须同时求解。

在机器人能够根据一系列观测值回答“这个世界长什么样”之前，它需要知道的额外信息很多，比如以下：
* 它自身的运动学特征,
* 信息的自动获得需要什么样的品质, 
* 附加的支持观测值能从哪些源得到。在没有地图或者方向参考的前提下，对机器人的当前位置估测是一个复杂的任务。这里的"位置"可以简单指代机器人的所处方位，也可以包括它的姿势形态。

## 技术上的问题

SLAM可以被看做是一个鸡生蛋蛋生鸡的问题：完美的定位需要用到一个无偏差的地图；但这样的地图又需要精确的位置估测来描绘。这就是一个迭代数学问题解决策略的初始條件。作为对比，原子轨道模型可以被看做一个在不精确的观测条件下说明足够多的结果的经典方法。

再者，由于多个传感器对机器人的相对运动的辨别存在固有的不确定性，上一节提到的两个“核心问题”也不像看起来的那么简单。一般来说，由于技术环境中总会考虑噪声，所以SLAM方法要考虑的不只是数学上的紧凑解，也包括与那些和结果相关的物理概念的相互作用。

如果在地图构建的下一个迭代步骤中，测得的距离和方向有可预知的一系列不精确度——通常由传感器有限的的精确度和外加的环境噪声所引起，那么附加到地图上的所有特征都将会含有相应的误差。随着时间的推移和运动的变化，定位和地图构建的误差累计增加，将会对地图本身和机器人的定位、导航等能力的精度产生很大的扭曲。

有许多技术能补偿这些误差，比如那些能再现某些特征过去的值的方法（也就是说，图像匹配法或者环路闭合检测法），或者对现有的地图进行处理——以融合该特征在不同时间的不同值。此外还有一些用于SLAM统计学的技术可起到作用，包括卡尔曼滤波、粒子濾波器（实际上是一种蒙特卡罗方法）以及扫描匹配的数据范围。

### 地图构建

在机器人技术社区中，SLAM的地图构建通常指的是建立与环境几何一致的地图。而一般算法中建立的拓扑地图只反映了环境中的各点连接关系，并不能构建几何一致的地图。因此，这些拓扑算法不能被用于SLAM。

在实用中，SLAM通常要被剪裁至适应可获得的资源，于是可以看出它的目标不是完美，而是操作实用性。已经发布的SLAM方法已被应用于无人机、无人潜艇、行星探测车、最近大热的、甚至人体内部。

学界大致都认为，SLAM问题的“正在得到解决”是过去十年间机器人研究领域的最重大成果之一。
该领域中仍有许多有待解决的难题，比如图像匹配和计算复杂度等方面的相关问题。

基于SLAM文献的最新研究进展中，有一条值得注意，就是对SLAM的概率论基础进行重新估测。这个充满了冒险家特质的方法大意如下：通过引入随机有限集的、多目标的贝叶斯滤波器，使得基于特征的SLAM算法获得卓越的性能，以此跳过对图像匹配的依赖；但作为代价，测量中的假警报率和漏检率都会被提升。
这里面的算法是基于概率假设密度滤波的方法来改进的。

### 传感

SLAM研究中经常使用许多不同型号的传感器来获得地图数据。这些数据带有统计独立的误差。这个统计独立是解决度量偏差和检测中的噪声的强制需求。简单来说，就是任何一个东西都很难测的准确。比如一根1米长的棍子，你第一次测量的时候可能是1.02米，第二次测量时1.05米，...。总之测量的时候多多少少都会有一些误差在里面，因此SLAM算法本身必须要有效的处理这些测量误差。

这些传感器可以是光学的，比如1D的（单波束）或者2D的（扫描）激光测距仪、3D Flash LIDAR、2D或3D声呐传感器以及一个或多个2D摄像头。从2005年开始，使用可视化传感器（摄像头）对SLAM的研究（可视化SLAM）如火如荼地展开，因为从那时起摄像头开始普及（比如说手机普遍带有摄像头）。

新近的方法使用了准光学的无线测距法，同时把三角测距法等几何方法应用于SLAM中，用以消除微弱无线信号对测量的影响。

一种为走路者设计的SLAM应用使用了一个装在鞋头的惯性测量单元作为主要传感器，该设计依赖于走路者能自动规避墙体这一假设。这个名为FootSLAM的设计可被用于自动建立建筑物的楼面布置图，从而方便建立该建筑的室内定位系统。

此外，通过聚众收集多个用户的手机信号强度与加速度数据，iFrame系统可以合成二维室内地图。并且随着用户数的增加，来逐步加强地图的精度。

### 定位

传感器的结果会作为定位算法的输入。由几何知识可知，对于n维的定位问题，任何传感输出必须包含至少一个和n+1个判别方程。为了算出结果，有关于在绝对或相对的循环和镜像坐标系统下得到的结果的先验知识也是必要的。

### 建模

以上结果对地图构建的贡献，可以在“2D建模并分别表示”或者在“3D建模并在2D上投影表示”中工作得一样出色。作为建模的一部分，机器人本身的运动学特征也要被考虑进去，用以提高在固有背景噪声下的传感精度。构建的动态模型需平衡不同传感器、不同局部误差模型给出来的贡献值，并最终包含一个基于地图本身的锐利的可视化描述，这包括机器人的位置和方向等云概率信息。地图构建就是这样一个动态模型的最终运算结果。

## 参见

* 卡尔曼滤波
* 蒙特卡洛定位法
* 粒子滤波
* Stanley：DARPA地面无人车挑战赛冠军，一辆成功使用了SLAM技术的无人车
* 深度图像的图像配准
* 移动机器人编程工具包项目：一组开源、跨平台的SLAM资料库。
* Multi Autonomous Ground-国际机器人竞赛：一项160万美元的国际竞赛，要求参赛者让多台无人车合作给一大片区域绘制地图。

## 参考资料

## 外部链接
* [Probabilistic Robotics by [Sebastian Thrun], Wolfram Burgard and Dieter Fox with a clear overview of SLAM.]  
* SLAM For Dummies (A Tutorial Approach to Simultaneous Localization and Mapping).
* Andrew Davison  research page at Imperial College London about SLAM using vision.
* Autonomous and Perceptive Systems  research page at University of Groningen about visual SLAM.
* openslam.org  A good collection of open source code and explanations of SLAM.
* Matlab Toolbox of Kalman Filtering applied to Simultaneous Localization and Mapping  Vehicle moving in 1D, 2D and 3D.
* SLAM Example using Processing.js of Feature-Based Navigation.
* FootSLAM research page at DLR including the related Wifi SLAM and PlaceSLAM approaches.