• ==1 简介==
• 古典年代（1986-2004）：这一时期，引入了SLAM概率论推导方法，包括基于扩展卡尔曼滤波、粒子滤波和最大似然估计。第一个挑战是效率和数据关联（求解位姿）的鲁棒性问题。
• 算法分析年代（2004-2015）：有许多SLAM基本特性的研究，包括可观测性，收敛性和一致性。研究者们理解了稀疏特征在高效SLAM解决方案中的重要角色，开发了主要开源SLAM库。
• 以下为主要的综述文献：
• 1. 【2006】 《Simultaneous localization and mapping: part I》和《Simultaneous localization and mapping (SLAM): Part II》两篇文献，重点讨论了概率方法和数据关联。
• 1. 【2008】 《The slam problem: A survey》，主要讨论了滤波器方法。
• 1. 【2008】 《Guest editorial special issue on visual slam》，主要讨论了视觉SLAM方法。
• 1. 【2011】 《A tutorial on graph-based slam》，主要讨论了SLAM后端优化。
• 1. 【2011】 《A review of recent developments in simultaneous localization and mapping》，主要讨论了观测、一致性和收敛性。
• 1. 【2012】 《Visual odometry Part I: the first 30 years and fundamentals》和《Visual odometry Part II: Matching, robustness, optimization, and applications》，主要讨论了视觉里程计。
• 1. 【2016】 《Multiplerobot simultaneous localization and mapping: A review》，主要讨论了多机器人SLAM。
• 1. 【2016】 《Visual place recognition: A survey》，主要讨论视觉位置识别。
• **为什么全自动机器人需要SLAM？**SLAM是要构建一个全局一致性的环境表示方法，同时利用自动运动测量和回路闭合。这里的关键词是“回路闭合”：如果我们去掉回路闭合，SLAM就会退化成里程计。但是里程计算法的偏移已经非常小了（小于整个轨迹长度的0.5%），因此这个问题是有意义的。答案分为三个方面：
• 1. 过去10年中，视觉惯性传感器里程计的算法发展代表了最新进展，视觉惯性导航可以看做是一个退化的SLAM系统，其中回环闭合模块功能关闭。相对于航空领域等领域的惯性导航，SLAM要求研究更具有挑战性的配置下（比如，没有GPS，低性能传感器）的传感器融合。
• 1. 回环闭合的优势很清楚：通过查找回环闭合，机器人可以理解环境的真正拓扑关系，可以找到位置间的最短路径，因此SLAM可以得到环境的拓扑关系。
• 1. SLAM是必须的，很多应用都内在或外在地需要一个全局一致性的地图。例如，在许多军事与民生工程应用中机器人的目标是探索环境生成地图，或者检查结构状况（建筑物，桥梁等），在这些例子中需要一个全局一致性3D重构。
• **SLAM有什么作用？**SLAM是一个比较宽泛的话题，可以从以下几个方面来评估一个SLAM问题的成熟度：
• 1. 机器人：运动类型（比如，运动状况，最大速度），可用的传感器（如，分辨率，采用率），可用的计算资源；
• 1. 环境：平面或三维的，自然路标或人工路标，动态元素的数量，对称的数量和感知混淆的风险。这些方面都依赖于传感器与环境的匹配；比如，两个房间对2D激光扫描仪来说看起来可能一样（感知混淆），但相机可以从外观线索上分辨它们；
• 1. 性能要求：机器人状态估计中的期望精度，环境表示的精度和类型（比如，基于路标的或稠密云点），成功的概率（满足精度边界的测试结果的百分比），估计延时，最大运行时间，最大地图面积。
• 比较成熟的情况：
• 1. 构建一个2D室内环境，机器人配备了编码器和激光扫描仪，有足够的精度（<10厘米）和足够的鲁棒性（比如，低失效率），很大程度上可以解决问题。
• 1. 或者一个运行缓慢的机器人采用基于视觉的SLAM（比如，火车探路车，室内机器人），视觉惯性里程计被认为是成熟的研究领域。
• 存在挑战的情况：
• 1. 目前当机器人的运动或环境太过挑战时，SLAM算法很容易失效（比如，机器人快速的运动，高动态环境）
• 1. SLAM算法通常无法满足严苛的性能要求（比如，对快速回环闭合的快速估计）
• **关于SLAM未来要考虑的问题。**SLAM正在进入第三个时代，鲁棒性觉醒的时代，它具有以下特征：
• 1. 鲁棒性能：这一时期SLAM系统在任意环境总运行的失效率较低；系统具有失效保护机制且具有自动调整的功能可以根据应用场景自动选择系统参数；
• 1. 高层次的理解力：SLAM系统已经除了基本的几何重建还能够在更高层次上理解环境信息（比如，语义，可供性，高层几何意义，物理意义）；
• 1. 资源敏感：SLAM系统可以进行裁剪以满足现有传感器和计算资源，也可以根据现有资源调整计算负载；
• 1. 对任务驱动的判断：SLAM系统可以自适应地表示地图，其复杂度可以根据机器人执行的任务而改变。
• ==2 现代SLAM系统解析==
• 从概念上现代SLAM系统可以被分为两个部分：前端与后端。前端负责将传感器的数据转化为用于状态估计的数据模型。后端根据前端生成的数据模型进行推断。
• 采用最大后验（MAP）估计的SLAM后端，（公式推导在SLAM#1笔记本）
• 1. 经过推导，最大后验估计会转化成非线性最小二乘优化问题（这是在假设噪声遵从高斯分布的条件下做出的推导），如果假设噪声遵从拉普拉斯分布就需要将最小二乘的优化目标函数改变为L-1范数。
• 1. 从优化模型上看，SLAM和BA的目标函数很近似，但是SLAM与BA之间存在两个不同的地方：（1）BA只用投影几何模型，而SLAM则能够处理更多的传感器模型。（2）SLAM的优化函数被设计为增量式的。
• 1. 通常使用高斯-牛顿方法或者Levenberg-Marquardt方法（LM方法）来进行求解。
• 1. 求解过程中的雅克比矩阵是稀疏的因此可以进行快速求解。
• 1. 基于最大后验估计的SLAM方法要比传统的基于非线性滤波的方法更为高效和精确。
• 目前可用的SLAM求解库：
• 1. GTSAM, 2012, 《Factor graphs and GTSAM: A hands-on introduction》
• 1. g2o, 2011, 《g2o: A general framework for graph opti- mization》
• 1. Ceres, https://code.google.com/p/ceres-solver/
• 1. iSAM, 2008, 《iSAM: Incremental Smoothing and Mapping》
• 1. SLAM++, 2013, 《Incremental block cholesky factorization for nonlinear least squares in robotics》
• 依赖于传感器的SLAM前端
• 1. 最大后验估计需要使用经过预处理的传感器数据，因此被称为后端，并依赖于传感器的SLAM前端。
• 1. 在机器人的实际应用中，可能很难将传感器测量数据转化成分析函数，因此需要进行预处理。例如，原始传感器数据是图像，很难将每个像素的亮度表示为SLAM状态的函数，在一般性的表示中，可能很难给出一个分析方程将观测值与表示方法的参数进行关联。
• 1. 前端的主要任务是：从传感器数据中提取相关特征。例如，在视觉SLAM中，前端提取环境中少量的特征云点的像素位置；这些云点的像素观测值就很容易在后端部分构建模型。
• 1. 前端部分还负责将观测值和环境中特定的路标关联（比如，3D云点）：这就是所谓的数据关联。
• 1. 前端还可以为非线性优化中的变量提供一个初始估计。
• ==3 完全自动化：鲁棒性==
• SLAM系统会因为出现算法失效和硬件相关的失效而变得脆弱。例如，对于极端动态环境的处理，受到现有SLAM算法的局限而很难实现。另外也会由于传感器和机器老化，使系统变得脆弱。
• 明确地提出失效模式对长期运行非常关键，那样就不会对环境结构有要求。例如，要求大部分是静态环境或者完全依赖板载传感器。
• SLAM系统失效的来源包括：
• 1. 数据关联：是把每次的测量值与对应的状态进行关联。在基于特征的视觉SLAM系统中，它将每个特征和特定的路标关联。可能会出现不同的传感器输入产生相同的传感器信息，导致这个问题非常难解决。如果数据关联构建了错误的测量-状态匹配，后端可能会出现错误估计。
• 1. 如果环境中存在短期或季节变化，而且没有对动态环境构建模型，可能会产生错误的短期或长期的数据关联。通常SLAM系统要求机器人所处的环境是静态的，这个要求在小场景中单一地图构建中是适用的。
• 1. 如果地图构建长时间运行在大场景中，变化就不可避免。昼夜变化，季节变换，例如树叶或环境结构的改变、旧建筑物变成新建筑物，所有这些都会影响SLAM系统的性能。例如，依赖于视觉特征的系统会在剧烈的昼夜变化中失效，当旧建筑消失环境几何方法也会失效。
• 1. 在恶劣的环境中使用SLAM，比如水下环境，由于水下属于可视光有限，且一直在变化，而且一般的传感器无法使用（比如镭射测距仪）。
• 对错误数据的鲁棒性包含以下几个方向：
• 1. 传统方法中，前端用于构建正确的数据关联。短期数据关联是最容易处理的：如果传感器的数据采样率比机器人的运动快，对相同特征的跟踪就比较容易。而中长期数据关联需要回环检测来实现鲁棒性。
• 1. 对于回环检测通常使用词袋模型。词袋模型可以量化特征空间以进行更有效的搜索。词袋模型可以设计成层级式字典树，可以在大范围数据集中有效查找。基于词袋模型的技术在处理单任务闭环回路检测中表现出非常可靠的性能。
• 1. 但是词袋方法会由于剧烈的图像变化，而导致视觉单词无法匹配。因此需要开发新的方法，参见《Visual place recognition: A survey, 2016》。
• 1. 尽管回环检测会使用几何验证（包括RANSAC算法）来确认回环闭合的质量，使得前端的回环检测更具有鲁棒性。但是在直视对齐的情况下，错误的回环闭合会被反馈到后端，并严重损害最大后验估计的质量。
• 动态环境的挑战主要有两方面：
• 1. SLAM系统必须检测，丢掉，跟踪变化。主流的方法都尝试丢掉场景中的动态部分，也有些研究工作将动态元素作为模型的一部分。
• 1. SLAM系统必须构建一个处理永久或半永久变化的模型，建立更新地图的机制。目前的SLAM系统处理动态环境，要么维护同一位置的多个（与时间相关）地图，要么只有一个表示但可以根据时间变动进行调整。
• 研究方向：鲁棒性方面待解决的问题
• 1. **失效保护SLAM和恢复机制：**现有的SLAM方案在出现离群点时仍然比较脆弱。这主要因为鲁棒的SLAM是基于非凸集迭代优化。这样会有两个结果：（1）离群点去除的结果依赖于优化中初始估计的质量；（2）系统天生脆弱：任一一个离群点都会降低估计的质量，它又会反过来降低系统分辨离群点的能力。因此一个理想的SLAM系统应该是具有失效保护和失效侦测的功能，例如：系统必须能检测到即将发生的失效问题（比如：由于离群点或者硬件老化），还要具有恢复机制重建之前的操作任务，现有SLAM系统没有这种功能。
• 1. **针对硬件的鲁棒性：**硬件失效并不是SLAM研究的问题，但这些失效会影响SLAM系统。如果传感器精度由于误操作或老化而降低，传感器的测量（噪声和偏移）质量不能匹配后端的噪声模型，将会导致较差的估计。这就会产生不同的研究问题：我们如何检测不良传感器的运行状态？如何相应地调整传感器噪声数据统计模型（协方差，偏移）？
• 1. **几何度量重定位：**与基于特征方法不同，基于贴图的方法可以在白天和夜晚的图像序列上实现回环闭合，同样也可以对不同的季节实现回环闭合检测。对于几何度量重定位（比如对之前构建的地图估计相对位姿），基于特征的方法可能更规范化，但无法扩展到动态的环境中。（1）对于传感器选择和传感器位置匹配的相关的研究：轨迹匹配中相机的劣势；先用一个相机建图，再在同一个地图中定位另一个相机.（2）另外还要考虑从不对称的拍照角度上得到不同的照片中如何定位，相关的研究包括：在激光地图中的视觉定位问题；如何在Google街景照片的3D纹理地形图上定位无人机；用激光扫描仪实现手绘地图；在2D户型图上用RGB-D定位。
• 1. **时间变化和地图畸变：**主流SLAM方法都假设现实世界是固定不变的，然而真实世界则因为动态环境和物体畸变而并非一成不变。一个理想的SLAM方案应该能够处理环境中的动态因素，包括非固定部分，能够长时间工作生成所有地形地图，并能实时处理这些工作。最近关于非固定运动结构，比如论文《Sequential non-rigid structure from motion using physical priors, 2016》、《Real-time 3d reconstruction of non-rigid shapes with a single moving camera, 2016》、《Visual slam for handheld monocular endoscope, 2014》，限制比较少，但主要应用于小场景。在SLAM领域，《Dynamicfusion: Reconstruction and tracking of nonrigid scenes in real-time, 2015》针对小场景提出了非刚体实例。然而，大场景非刚体地图仍然需要大量研究。
• 1. **自动参数调整：**SLAM系统（特别是数据关联模块）需要很多的参数调整。要在给定的场景中正确地工作，特征匹配的阈值，RANSAC参数，还有决定何时添加新的因子到因子图中，或者何时触发回环闭合算法搜索匹配等参数都需要进行配置。如果SLAM需要跳出受限的环境在任意场景中都适用，那么就需要考虑自动参数调整的方法。
• ==4 完全自动化：尺度==
• 在用于环境监控的海洋探索、城市中7*24小时工作的清洁机器人、高精度的农业机器人等室外大场景长时间工作的应用中，随着运行时间的增加，以及机器人不停地探索新的位置，SLAM的因子图可能是没有边界的。然而在实际当中，由于机器人资源限制、计算时间和存储容量有限，因此设计不受计算时间和存储容量限制的SLAM方法非常重要。
• 现有SLAM算法的尺度
• 1. 直接线性求解器：由于需要维护雅克比矩阵与噪声矩阵，因此其内存消耗会随着变量数量的增加呈几何式增长。
• 1. 线性迭代器（例如，共轭梯度法）：内存变量消耗空间呈线性增长。
• 1. 当在同一个地方多次路过时，节点和边被持续的加入到相同的空间中时，因子图的优化就变得没有效率，还不如采用稀疏图结构。
• 减少因子图优化复杂性的研究现状主要集中在两个方面：（1）稀疏方法，通过损失一些信息来降低内存使用和提高计算效率；（2）并行和多机器人方法，将计算任务分配到多个机器人或处理器上。
• 1. **节点与边的稀疏化：**这类方法通过减少将要添加到图中的节点数量，或者筛选掉具有较少信息的节点和因子，降低问题的规模。

《Information- based compact pose slam, 2010》，采用信息论的方法添加非冗余节点和高信息含量观测值到图中。
《Temporally scalable visual slam using a reduced pose graph, 2013》，通过为现有节点添加新的约束，来尽可能的避免添加新的节点，这样变量的增长就只和空间大小有关，而与时间无关。
《Efficient information-theoretic graph pruning for graph-based slam with laser range finders, 2011》，采用基于信息的标准来对决定位姿图优化中哪些节点应该被筛掉。
《Generic factor- based node marginalization and edge sparsification for pose-graph slam, 2013》和《Nonlinear factor recovery for long-term slam, 2016》，分别介绍了GLC（Generic Linear Constraint）因子和NGS（NonLinear Graph Sparsification），采用一个筛选节点的马尔科夫链来处理，并计算其近似稀疏。
《Consistent sparsification for graph optimization, 2013》，通过求解L1范式的最小化问题来对Hessian矩阵进行稀疏化。

• 1. **并行SLAM：**SLAM并行算法将因子图的计算放入多个处理核心中进行计算。主要的方法是将因子图分解为几个不同的子图，局部优化每一个子图和一个全局优化，对应的算法通常称为局部构图算法。

《Tectonic SAM: Exact; out-of-core; submap-based SLAM, 2007》，展示了一种精确的局部建图方法，以及通过缓存分解的子图来提高运算速度。
《Multi-level submap based slam using nested dissection, 2010》，将局部图组织为二叉树结构，并使用嵌套分解来降低两个子树之间的依赖程度。
《Linear SLAM: A linear solution to the feature-based and pose graph SLAM based on submap joining, 2013》，提出了一种针对大场景SLAM的近似解决方案，使用最小二乘法来求解一系列的子图，并采用分治的策略来合并子图。
《A multilevel relaxation algorithm for simultaneous localisation and mapping, 2005》，提出了一种多层的松弛法，松弛法通过迭代方法来利用两个低精度数值来计算出一个高精度的结果。
《Hierarchical optimization on manifolds for online 2D and 3D mapping, 2010》，提出了一种层级式的局部图：当得到一个新的观测值时，位于高层的局部图会被立刻修改，但是只有受影响的低层级区域才会更改。
《An Approach to Solving Large-Scale SLAM Problems with a Small Memory Footprint, 2014》，提出了一种基于层次分解的近似SLAM方法。
《Exactly sparse memory efficient slam using the multi-block alternating direction method of multipliers, 2015》，通过交替方向乘子法ADMM来进行并行计算。ADMM算法是机器学习中比较广泛使用的约束问题最优化方法，它是ALM算法的一种延伸，只不过将无约束优化的部分用块坐标下降法（block coordinate descent，或叫做alternating minimization）来分别优化。其中的原理可以参考文献 “Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers”。产生这种方法主要是为了弥补二次惩罚的缺点。在一些问题当中，用二次惩罚来近似约束问题在最优点附近需要惩罚项的系数趋近于无穷，而这种要求会使得海森矩阵很大，因此近似的目标函数很不稳定。为了解决这个问题，引入了线性逼近的部分，通过线性项系数不断的接近最优解（对偶上升），使得在二次惩罚项的系数很小的情况下，也能得到满足要求精度的解。ADMM目前是比较成熟，比较受欢迎的约束问题最优化通用框架。
《Parallel tracking and mapping for small ar workspaces, 2007》，近似的解耦定位与地图，将其放到两个线程中运行。
《Adaptive relative bundle adjustment, 2009》，通过优化局部邻域的参数化来降低计算量。
《Double window optimisation for constant time visual SLAM, 2011》，采用两个步骤，首先优化一个局部的位姿-特征图，然后采用上面的方法完成位姿-位姿图的变换。
《Concurrent filtering and smoothing: A parallel architecture for real-time navi- gation and full smoothing, 2014》，将因子图优化分解为一个快速滤波线程和一个慢速平滑线程，两个线程之间周期性的进行同步。

• 1. **分布式多机器人SLAM：**一种处理大型场景的方法就是部署多个机器人执行SLAM，将场景分为多个小的区域分别由不同的机器人来完成。这种方法有两个变体：（1）中心化和（2）去中心化。

中心化的方案指机器人将自己的本地信息传送到中央节点以执行推断计算，下面的文献介绍了中心化方案：
《C-SAM : Multi-robot SLAM using square root information smoothing，2008》
《Decentralised cooperative localisation for heterogeneous teams of mobile robots, 2011》
《Distributed real-time cooperative localization and mapping using an uncertainty-aware expectation maximization approach, 2015》
《Collaborative monocular SLAM with multiple micro aerial vehicles, 2013》
《Multiple relative pose graphs for robust cooperative mapping, 2010》
《Multi-robot SLAM using condensed measurements, 2011》
《Real-time 6-DOF multi-session visual SLAM over large scale environments, 2013》
《C2TAM: A cloud framework for cooperative tracking and mapping, 2014》
去中心化的方案没有中心数据融合，机器人利用局部通信在共同估计上保持一致性，下面的文献讨论了去中心化的方案：
《Distributed maximum a posteriori estimation for multirobot cooperative localization, 2009》，提出了一种基于分布式共轭梯度方法的协作式定位算法。
《Multi-agent localization from noisy relative pose measurements, 2011》和《Distributed centroid estimation from noisy relative mea- surements, 2012》，利用分布式雅克比方法来估计一组二维位姿。
《Distributed consensus on robot networks for dynamically merging feature-based maps, 2012》，基于一致性信息方法进行地图合并。
《Collaborative localization with heterogeneous inter-robot measurements by Riemannian optimization, 2013》，采用分布式梯度下降方法来估计3D位姿。
《DDF-SAM: Fully distributed slam using constrained factor graphs, 2010》和《DDF-SAM 2.0: Consistent distributed smoothing and mapping, 2013》，利用高斯消元法开发了一种称为DDF-SAM的方法，每个机器人通过隔离器（不同机器人之间的共享变量）来交换高斯边缘。
《Multiple-robot simultaneous localization and mapping: A review, 2016》，最近的多机器人SLAM的综述。

• 1. **高斯消元法：**作为被广泛使用的方法存在两个缺点：（1）机器人之间交换的边缘是稠密的，通信的代价与隔离器的数量平方成正比。（2）高斯消元法是分布式多机器人问题的一个线性化解决方案，因此这类的方法（例如DDF-SAM）需要好的线性点和复杂的书签来保证机器人之间线性点的一致性。

《Communication-constrained multi-AUV cooperative SLAM, 2015》，介绍了利用稀疏化技术来减少通信开销。
《Distributed trajectory estimation with privacy and communication constraints: a two-stage distributed gauss-seidel approach, 2015》，提出一种替代高斯消元法的Gaussian-Seidel方法，该方法的通信负担与隔离器数量呈线性相关。

• 待解决的问题尽管有大量减少因子图优化复杂度的工作，但是与长期运行的目标之间存在很大的距离：
• 1. **地图维护：**如何存储地图是一个在长期执行的SLAM中极少被探索的领域。但是即使是在将地图存储于云这种内存没有受限的情况下，原生的点云地图或立体地图会浪费大量的内存。在基于视觉的SLAM方案中所存储的特征描述子，也会快速的变得过于臃肿而难以处理。

《Get out of my lab: Large-scale, real-time visual-inertial localization, 2015》，提出了压缩已知地图的方法。
《Chisel: Real time large scale 3d reconstruction onboard a mobile device using spatially hashed signed distance fields》，提出了内存高效的稠密重建方法。

• 1. **鲁棒的分布式建图：**在单一机器人的情况下，已经提出了很多离群点剔除方法。但是在多机器人领域则完全忽略了离群点剔除的问题。处理错误的测量值是个巨大的挑战，主要因为下述的两个原因：（1）机器人之间没有可能无法共享共同的参考帧，这就使得很难检测并去除错误的回环闭合；（2）机器人只能通过极少的局部信息来检测离群点，这个领域尚未被探索。

《Incremental distributed inference from arbitrary poses and unknown data association: Using collaborating robots to establish a common reference》，是第一篇探讨第一个原因的文献。

• 1. **地图信息的维护与更新：**在长期建图的过程中，存在以下的问题：（1）地图包含的信息更新的频率如何选择？（2）如何判断信息何时过期，然后丢弃？（3）哪些信息可以被丢弃，哪些必须被保留？这些问题很明显都是和任务相关的，目前尚未有文献给出一个绝对的答案。
• 1. **资源受限平台：**另外一个挑战是如何使现有的SLAM算法适应那些计算资源受限的机器人平台。当机器人的尺寸变小的时候，这个问题就极为重要。很多SLAM算法由于运算开销太大而无法运行于手机、微型无人机、机器昆虫这类平台。因此需要一种能够稍微降低精度以降低运算开销的算法。在多机器人场景中，在带宽受限甚至通讯失败的情况下，保证机器人团队可靠的运行。

《Map api - scalable decentralized map building for robots, 2015》，是第一篇在这个方向研究的文献。

• ==5 地图表示：度量方面的讨论==
• 度量表示或度量地图是将环境的几何模型进行编码的符号结构。选择合适的度量表示涉及到长时间导航、与物理环境交互以及人机交互等研究领域。
• 2D情况下的几何模型非常简单，包含两种泛型：（1）基于路标的地图，将环境建模为一个稀疏的路标集合；（2）网格占用地图，将环境离散化为一系列的单元格，并指定每个单元格被占用的概率。用于机器人的2D地图已经由IEEE RAS地图数据表示工作组处理（http://standards.ieee.org/findstds/standard/ 1873-2015.html/）。该标准为平面环境和拓扑地图定义了两种度量表示方法，以便于数据交换、评价和技术转换。
• 3D几何建模的问题更为精巧，如何在构建地图的过程中高效的进行3D几何建模尚处于刚刚起步的阶段。本节从机器人学、机器视觉、计算机辅助设计和计算机图形学的角度来回顾度量地图的表示：
• 1. **基于路标的稀疏表示：**大部分的SLAM方法会把场景表示为一个稀疏的三维路标点集合，这些三维的点对应着环境中可区分的特征（例如线或角点）。这种地图表示在早期的移动机器人定位与建图、机器视觉领域的运动恢复结构中被称为基于路标的表示或基于特征的表示。这种表示有一种隐含的假设：路标是独一无二的，可以被分辨的。也就是说传感器数据是对路标外观的测量，同时提供路标的描述子，用于为每一个测量建立数据关联。同时描述子和路标一一对应。目前，大部分的工作都聚焦于点特征的估计。

《ORB- SLAM: A versatile and accurate monocular SLAM, 2015》，是典型的采用稀疏3D路标来构建地图的工作。
《Visual navigation using heterogeneous landmarks and unsupervised geometric constraints, 2015》，把点特征扩展为更为复杂的几何路标（例如线、弧）。

• 1. 低级原生稠密表示：与基于路标的表示不同，稠密表示试图提供一个高分辨率的3D几何模型。在机器人学中，稠密表示更适合用于避障和路径规划，以及可视化和展现。稠密表示中的原生表示方法利用庞大的的点云或多边形集来表示三维几何结构。利用所有图像像素的强度值来直接估计机器人的轨迹和三维模型的方法叫做直接方法。在单目视觉中，使用直接方法时通常会使用点云或多边形集的表示方法。这些表现方法视觉效果很好，但是因为要存储大量的数据而过于臃肿。此外，这种表示方法只给出了低抽象级的几何描述，而忽视了障碍物的拓扑结构。

《Interpolating and approximating implicit surfaces from polygon soup, 2004》，利用多边形集合来描述三维几何结构。
《3D robotic mapping: the simultaneous localization and mapping problem with six degrees of freedom, 2009》，在基于双目、RGBD、3D激光扫描仪的SLAM中，通常使用点云的方法。
《Multi-frame optical flow estimation using subspace constraints, 1999》，《DTAM: Dense tracking and mapping in real-time, 2011》，《REMODE: Probabilistic, monocular dense reconstruction in real time, 2014》，采用单目视觉的直接方法中，通常使用原生的稠密表示方法。
《ElasticFusion: Dense SLAM without a pose graph, 2015》，使用了稍微复杂一点的面元地图（surfels, SURFace ELmentS），这种表示更适合用于非刚体的环境。

• 3.a **边界稠密表示：**边界表示法利用三维物体的表面边界来表示该物体。比较通用的方法包括：基于曲线的表示、表面网格方法（互相连接的多边形几何）和隐式表面表示方法。

《Towards simultaneous recognition, localization and mapping for hand-held and wearable cameras, 2007》、《Simultaneous localization and mapping with infinite planes, 2015》和《Visual navigation using heterogeneous landmarks and unsupervised geometric constraints, 2015》，采用的基于水平面模型的边界表示方法用于建图。
《Introduction to Implicit Surfaces, 1997》，介绍了隐式表面表示方法，该方法把固体表面指定为一个定义于三维空间的函数与0的交点。
《Reconstruction and representation of 3D objects with radial basis functions, 2001》，采用了radial-basis函数。
《A volumetric method for building complex models from range images, 1996》，采用了signed-distance函数。
《A globally optimal algorithm for robust TV-L1 range image integration, 2007》，使用了截断的signed-distance函数（TSDF），在机器人视觉SLAM领域非常流行。
《Kintinuous: Spatially extended Kinect-Fusion, 2012》，《ElasticFusion: Dense SLAM without a pose graph, 2015》，使用了网格表面表示方法。

• 3.b **空间划分稠密表示：**空间划分在图形学中非常重要（例如k-d树之类的结构），可以用于降低计算的复杂度，这种表示方法把三维空间的物体表示为连续无交叉原始点的集合。最流行的空间分割表示方法是空间占用表，这种方法把空间划分为一个个三维像素，较为高效的形式包括：八叉树、多边形映射八叉树和二分空间分割树。

《Real-time SLAM with octree evidence grids for exploration in underwater tunnels, 2007》，使用了八叉树表示方法来进行三维建图，在使用网格占用地图的情况下，八叉树表示可以看成是空间分割表示方法的概率变体。
《Stereo-vision based obstacle mapping for indoor/outdoor slam, 2014》，在没有悬挂障碍的环境中，使用了2.5纬度的海拔地图。

• 1. **稀疏表示（基于特征）、稠密表示与直接方法的比较：**哪种方法更好，取决于任务以及时间、精度、错误率等性能。基于特征的方法主要缺点就是依赖于特征的类型，而且依赖于大量的检测与匹配的阈值；在处理不正确的匹配关系的时候，鲁棒估计技术是必需的；而事实上大部分的特征检测器优化的关注点是速度而不是精度。稠密与直接方法利用了图像中的所有信息，包括变化幅度很小的区域，因此要比基于特征的方法更适合处理缺乏纹理、散焦和动态模糊的场景；然后，稠密方法需要高算力（GPU）才能完成实时运算；此外，对稠密结构和运动进行联合估计尚未解决。为了避免基于特征方法的缺陷，目前有两种替代方案：Semi-dense和Semi-direct。

《currently they can be only be estimated subsequently to one another, 2014》，对Semi-dense进行了介绍。半稠密方法只利用具有强变化的像素（边）来，克服了稠密方法对高运算能力的需求。
《SVO: Fast Semi-Direct Monocular Visual Odometry, 2014》，《Svo 2.0: Semi-direct visual odometry for monocular and multi-camera systems, 2016》，《A semi-direct approach to structure from motion, 2003》，Semi-direct方法直接利用了稀疏的特征和直接方法，被证实非常高效。由于这种方法依赖于稀疏的特征，因此可以对结构与运动进行联合估计。

• 1. **基于高抽象级别物体的表示：**包含物体、固体形状的高抽象级别的表示，在未来的SLAM中会扮演重要的角色。固体表示法将真实的物体的信息编码为三维的，而不是一维（点）或二维（面）的。将物体建模为固体形状可以为每一个物体关联诸如体积和质量之类的物理属性，这对于不得不与物理世界交互的机器人非常重要。幸运的是：现有的CAD和计算机图形学已经有了一些方法为这类方法铺平的道路。例如下述的固体表示方法：

a. **Parameterized Primitive Instancing：**这种方法依赖于定义一系列的物体类别（例如圆柱、半球）。对于每个类别都通过制定一系列的参数（半径、高度）来唯一的标示一个成员。目前尚无SLAM方法可以生成一个这样的表示。
b. **Sweep representations：**这种方法把一个固体定义为一个二维或三维的固体在空间中的移动轨迹，常见的包括平移和旋转两种运动轨迹。例如，一个圆柱可以表示为一个圆沿着垂直于本身的轴进行平移，在计算机视觉中对利用二维截面运动定义的圆柱被称为广义圆柱体，已经被用于机器人抓取当中。这种表示方式也尚未在SLAM领域出现。
c. **Constructive solid geometry：**这种方法将复杂的固体表示为一些元体的布尔运算。物体被存储于一颗树中，叶子节点是元体，边表示布尔运算。这种方法也没有出现在SLAM领域。
《SLAM++: Simultaneous Localisation and Mapping at the Level of Objects, 2013》，《Towards semantic SLAM using a monocular camera, 2011》，《Dense reconstruction using 3d object shape priors, 2013》，包含了对基于物体表示方法的论证。
《Parametric and Feature-Based CAD/CAM: Concepts, Techniques, and Applications, 1995》，介绍了在CAD中基于特征的模型。
《Shape2Pose: Human-centric shape analysis, 2014》，介绍了affordance-based模型。
《Model synthesis: A general procedural modeling algorithm, 2010》，介绍了generative and procedural模型。
《Image retrieval using scene graphs, 2015》，介绍了场景图模型。
《Hierarchical sparse coded surface models, 2014》和《Towards robust and effective shape modeling: Sparse shape composition, 2012》，使用了基于字典的表示，这种表示方法把把固体定义为字典中原子的组合。这两篇文献中字典是从数据中习得。
《Object recognition in 3D point clouds using web data and domain adaptation, 2010》和《Parsing IKEA objects: Fine pose estimation, 2013》，这两篇文献中的字典基于现存的数据仓库。

• 待解决的问题
• 1. **高抽象层、具有表达能力的表现方式：**目前机器人社区对于三维几何结构都聚焦于点云或TSDF方法，但是这些表示方法有两个主要的缺点：（1）这些方法都存在或多或少的浪费，例如那怕是编码像空房间这样的简单环境，也要使用非常多的参数（点、立体像素）；（2）这些方法都没有提供对三维几何结构的高抽象级别的理解，例如一个机器人需要指出自己进入的是一个房间还是走廊；点云无法提供关于环境类型的可用信息，而另一方面，很多成熟的模型（Parameterized Primitive Instancing）可以提供简单的方法来分辨两个场景（通过定义原体的参数）。高抽象层表示存在三个方面的好处：（1）使用更紧凑的表示方法可以为大规模建图压缩提供天然的工具；（2）高抽象层级别的表示可以提供对于物体几何结构的高抽象级别的描述，对数据关联、位置识别和语义理解提供了便利的工具；这种描述还会影响人机交互（机器人可以像人一样对几何结构进行推理），这种描述还允许包含物理属性（重量、动能）以改进推理和建图的过程。（3）使用具有更多信息的三维表示，可以与现代建筑的建设与管理互相促进。但是目前SLAM技术尚无超越点云、网格模型、表面元素模型和TSDFs的高抽象级别的表示方法。
• 1. **最佳表示方法：**大量的工作都聚焦于三维几何结构的表示方法，但是少有研究聚焦于如何选择表示方式的准则。从直觉上讲，对于简单的室内环境用参数化原型的方法只需要几个参数就可以描述三维几何结构；而复杂的室外环境，则使用网格表示方法更为合适。如何比较不同的表示方法，以及选择最优的表示方法，就需要一系列的准则。可以用下列属性来比较不同的表示方法：（1）表达域（可以表示的真实物体集合）；（2）简洁性（存储于传输一个表示的容量）；（3）易于创建性（在机器人学中指建立表示所需的推断时间）；（4）在应用上下文中的效率（依赖于具体的任务）。因此，最理想的表示方式应该在可以执行给定任务的同时，具有简洁性并易于创建；因此最理想的表示方式就是能够执行任务，且只有最少充分的统计信息，同时对于异常情况具有最大的不变性。为一个任务选择最好的表示方法的框架是一个待解决的问题。
• 1. **自动化、自适应的表示方式：**传统情况下，表现方式的选择由机器人专家在设计系统的时候决定，这样做有两个主要的缺点：（1）设计一个适合的表示方法需要一个专家进行旷日持久的工作；（2）缺乏灵活性，一旦系统设计完成表示方法就不能改变。理想情况下，我们希望机器人能够根据任务和外部环境的复杂度来提高或降低表示方法的复杂程序。自动化选择最优的表示方法对于长期导航会带来巨大的影响。
• ==6 地图表示：语义方面的讨论==
• 语义建图在于将语义概念与机器人周边的几何实体进行关联。最近，纯粹的几何结构地图的局限性受到关注，并展开了大量环境语义建图的研究：（1）增强了机器人的自动化程度和鲁棒性；（2）为执行更复杂的任务提供便利（例如，自动驾驶的时候避开泥泞的道路）；（3）将路径规划转变为任务规划；（4）进行更为高级的人机交互。

《Semantic structure from motion with points, regions, and objects, 2012》
《A fast, modular scene understanding system using context-aware object detection, 2015》
《Semantic parsing of street scenes from video, 2012》
《Supervised semantic labeling of places using information extracted from sensor data, 2007》
《Semantic object maps for robotic housework - representation, acquisition and use, 2012》
《Multi-modal semantic place classification, 2009》
《SLAM++: Simultaneous localisation and mapping at the level of objects, 2013》
《Hierarchical semantic labeling for task-relevant rgb-d perception, 2014》

• 这些研究导致出现了大量的针对不同数量和类型的语义概念的方法，和关联环境不同部分的手段。例如《Large-scale semantic mapping and reasoning with heterogeneous modalities, 2012》中标记了不同的房间，而《Monocular slam supported object recognition, 2015》在地图上分割了几个已知的物体。大部分方法中，语义解析仅仅是最基础的层次，语义解析被公式化为分类问题。
• 语义 vs 拓扑：拓扑建图抛弃了度量信息，而仅仅利用识别出的位置来构建图（graph），节点表示可区分的位置，而边表示位置之间是否可达。要注意的是，拓扑建图和语义建图从根本上是完全不同的。前者需要识别出一个之前见过的位置（而不在乎这个位置是厨房还是走廊），后者的兴趣则是根据语义标签对位置进行分类。

《Visual place recognition: A survey, 2016》，对基于视觉的拓扑SLAM做了综述，第三部分讨论了拓扑地图中具有挑战性的问题。

• **语义SLAM：概念的结构与细节程度：**语义表达考虑下述两个方面：（1）语义概念的级别或细节程度，例如命令机器人从A房间到B房间，则只需要粗粒度的概念分类（房间、走廊、门）；而让机器人拿一只茶杯则需要一个细颗粒度的分类（桌子、茶、茶杯、镜子）。（2）语义概念的组织结构，由于语义概念不具有排他性，甚至一个实体可以有不受限制的属性或概念；例如椅子“可以搬动”和“可以坐”，而桌子则“可以搬动”和“不能坐”，作为家具，桌子和椅子共享“可以搬动”属性，但是具有不同的可用性。因此不得不设计一个扁平或层级结构，来处理概念的多样性。
• **简要回顾：**有三种处理语义建图、关联语义概念与数据的方法：
• 1. **SLAM促进语义：**第一个关于语义建图的研究采用了直接对SLAM系统产生的度量地图进行语义分割的方法。

《Supervised semantic labeling of places using information extracted from sensor data, 2007》是一项早期的工作，首先利用2D激光扫描建立了几何度量地图，然后以离线的方式通过关联马尔科夫网络对每个机器人位姿进行语义位置分类，然后融合到地图当中。
《Large-scale semantic mapping and reasoning with heterogeneous modalities, 2012》和《Multi-modal semantic place classification, 2009》，提出了在线的语义建图方法，使用激光与摄像机采集的环境数据，进行三层推断（传感器层、目录分类层和位置层）来产生语义地图。
《A fast, modular scene understanding system using context-aware object detection, 2015》，利用运动估计以及多个物体检测器来对地图进行粗粒度的语义分割。
《Monocular slam supported object recognition, 2015》，使用了一个单目SLAM系统来提高识别视频中物体的系统性能。

• 1. **语义促进SLAM：**第一个语义地图出现后，利用已知的语义类别或物体的趋势出现了。如果可以在地图中识别出某个语义分类或物体，就可以利用它们的几何先验知识来改善对地图的估计。

《Towards simultaneous recognition, localization and mapping for hand-held and wearable cameras, 2007》，是第一个小规模的尝试。
《Towards semantic SLAM using a monocular camera, 2011》，采用了基于稀疏特征的单目SLAM。
《Dense reconstruction using 3d object shape priors, 2013》，使用了稠密地图表示形式。
《SLAM++: Simultaneous localisation and mapping at the level of objects, 2013》，利用了RGBD的优点，提出了一个基于全部已知物体和地板平面的SLAM系统。

• 1. **SLAM与语义联合推断：**基于计算机视觉和机器人学的专业知识，已经有研究使用SLAM和语义相结合的方式实现了单目SLAM和地图分割。

《Manhattan scene understanding using monocular, stereo, and 3d features, 2011》,利用了Manhattan world assumption对室内场景地图中的主平面进行了分割。
《Semantic structure from motion with points, regions, and objects, 2012》，提出了第一个利用场景中几何与语义属性对相机参数、场景中的点和物体的标签进行联合估计。在这篇文献的工作中，作者展示了对物体识别的性能和鲁棒性的改进，每个图像对需要20分钟的运行时间以及对物体目录数量的限制使得该方法很难应用于在线的机器人操作。
《Joint 3d scene reconstruction and class segmentation, 2013》，解决了一个用于室外场景的更为特殊的依赖类的优化问题。
《Joint semantic segmentation and 3d recon- struction from monocular video, 2014》，采用推迟融合语义划分与度量地图的方法降低了实现语义地图的复杂度。
《Semantic octree: Unifying recognition, reconstruction and representation via an octree constrained higher order mrf, 2015》，与上一篇文献类似，这项工作是基于双目相机的，这两项工作仅仅聚焦于建图的部分，而没有对之前计算出来的位姿进行优化。
《Incremental dense semantic stereo fusion for large-scale semantic scene reconstruction, 2015》，是近期一个有前途的在线方法，使用了双目视觉和稠密地图表示。

• 待解决的问题
• 1. 语义地图不仅仅是一个分类问题。语义的概念需要发展以拥有更多的特殊信息，例如地图中实体的情景支持和可操控性，以及环境中具有主动性的代理（或机器人）之间的可能的互动。如何表示这些属性以及相互之间的关系，是高抽象层人机交互需要解决的问题。

《The ecological approach to visual perception: classic edition, 2014》，这本书中给出了情景支持（Affordances）和可操控性（Actionability）的定义。情景支持指的是一个特定机器人（Agent）对给定物体或环境能够进行可能的行为的集合，可操控性则包含了利用这些行为的预期。

• 1. **无知、认识与调节。**给定一些先验知识，机器人可以推理出新的概念和它们的语义表达，也就是说，可以发现环境中新的物体和类别。通过与人或其他机器人进行主动的交互，利用交互的结果可以学习到新的属性。随着时间的流逝来调整地图表示，来表示环境缓慢或突然的改变。例如，一个轮式机器人需要对某种地形是否可以驾驶通过进行分类，以通知它的导航系统。如果机器人发现路上了泥地，而这种地形之前被分类为可驾驶的，机器人就可以依赖于通过泥地的困难度来学习一个新的分类，或者当其他车辆被卡在泥地中的时候调整它的分类器。
• 1. **基于语义的推理。**与人类相似，语言表达允许我们压缩和加速对环境的推理。目前在机器人领域并没有这样的例子，机器人可以处理（染色的）度量表达，但是并没有真的利用语义概念。机器人目前尚不能利用语义概念（目录分类，关系和属性）进行有效、高效的定位与持续性的建图。例如，当检测到一辆汽车，机器人可以推断出车下面存在一个平面的地面（即使地面被汽车阻塞），当汽车移动的时候地图更新的工作可以仅仅利用新的传感器输入来细化被干扰的区域。甚至，汽车的全局位姿可以被看成是一个独立的整体，这会比利用三维网格更为高效。
• ==7 适用于SLAM算法的新技术==
• 本小节讨论保障SLAM算法性能方面的进展，理论分析对于SLAM非常重要，其原因在于：（1）SLAM算法与实现通常只在很少的问题实例上进行测试，理解如何将相应的结果推广到新的实例上非常的困难；（2）理论结果展示了问题的本质属性，在基于经验主义的评价过程中，很多本质属性是反直觉的；（3）对问题结构的真正理解可以允许推动算法的应用范围，可以解决很多真实世界的SLAM实例。
• 早期的SLAM算法的理论分析是基于扩展卡尔曼滤波的，但是目前研究聚焦于因子图优化方法。因子图方法除了具有精度和效率等实践性优点，还提供了一个更优雅的框架来进行更经得起检验的分析。
• 在缺乏先验知识的情况下，最大后验估计退化为最大似然估计。因此，缺乏先验知识的SLAM继承了最大似然估计的所有属性：最大后验估计具有一致性、对于欧式空间的变换具有不变性。但是缺乏了先验知识，这种估计方法会失去不变性。
• 在这种情况下，我们对算法的属性更为关注：一个给定的算法是否能够收敛到MAP估计？如何改善或检测其收敛性？在出现错误的测量的情况下，故障点是什么？
• **简要回顾：**大部分SLAM算法都是基于迭代的非线性优化方法。

《Square Root SAM: Si- multaneous localization and mapping via square root information smoothing, 2006》
《Non-linear constraint network optimization for efficient map learning, 2009》
《Incremental block cholesky factorization for nonlinear least squares in robotics, 2013》
《iSAM: Incremental Smoothing and Mapping, 2008》
《iSAM2: Incremental smooth- ing and mapping using the bayes tree, 2012》
《Fast iterative alignment of pose graphs with poor initial estimates, 2006》，上述论文都是基于迭代式非线性优化方法。

• 当一个算法收敛到一个局部最小点时，经常会返回一个完全错误、无法用于导航的估计。目前常用迭代式求解器在相当小的噪声级别下，无法收敛到一个全局最小值。

《From angular manifolds to the integer lattice: Guaranteed orientation estimation with application to pose graph optimization, 2014》和《Initialization techniques for 3D SLAM: a survey on ro- tation estimation and its use in pose graph optimization, 2015》，讨论上面的问题。

• 迭代方法收敛的失败，触发了对深入了解SLAM问题的努力：

《How far is SLAM from a linear least squares problem?, 2010》和《On the structure of nonlinearities in pose graph SLAM, 2012》，是研究这一问题的先驱，这些初步工作讨论了SLAM中的非凸性的性质。
《On the number of local minima to the point feature based SLAM problem, 2012》，讨论了在小的位姿图优化问题中最小点的数量。
《Error growth in position estimation from noisy relative pose measurements, 2013》，研究了在缺乏闭环检测的情况下误差的增长情况。
《Convergence analysis of pose graph optimization via Gauss-Newton methods, 2013》，讨论了采用高斯-牛顿法对收敛盆底的估计。
《From angular manifolds to the integer lattice: Guaranteed orientation estimation with application to pose graph optimization, 2014》，展示了2D情况下对旋转的估计可以用闭式解求解，并指出对应的估计是唯一的。
《Duality-based verification techniques for 2D SLAM, 2015》和《A convex relaxation for approximate global optimization in simultaneous localization and mapping, 2015》，假设旋转是Von Mises噪声，并提出了替代性的最大似然估计形式，可以得到更为健壮的结果。
《Planar pose graph optimization: Duality, optimal solutions, and verification, 2015》和《Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions, 2015》，在某些经常在实践中会遇到的强对偶情况下，最大似然估计是唯一的，位姿图优化可以通过（凸）半正定规划（SDP）来求解。

• 通常理论分析是设计更好的算法的第一步，除了采用对偶SDP方法之外，另外一些作者提出了基于凸松弛的方法，来避免收敛到局部最小值。

《A convex optimization based approach for pose SLAM problems, 2012》和《A convex relaxation for approximate global optimization in simultaneous localization and mapping, 2015》，采用凸松弛的方法。

• 另外一个成功的改进收敛性的策略是：为迭代式非线性优化计算一个更适合的初始值。首先求解旋转，然后利用估计结果来辅助非线性迭代，在实践中展示了其有效性。

《Keypoint design and evaluation for place recognition in 2D lidar maps, 2009》
《From angular manifolds to the integer lattice: Guaranteed orientation estimation with application to pose graph optimization, 2014》
《A linear approximation for graph-based simultaneous localization and mapping, 2011》
《A fast and accurate approximation for planar pose graph optimization, 2014》
《Initialization techniques for 3D SLAM: a survey on rotation estimation and its use in pose graph optimization, 2015》
《Exploiting the separable structure of SLAM, 2015》，则利用（近似的）分离平移与旋转来加速优化。

• 最近在使用对偶拉格朗日算子的SLAM系统中的理论结论可以用于设计验证技术：这些技术可以判断一个给定的SLAM估计是否是最优化的。确定SLAM解决方案结果的质量对于那些安全性高的应用中，设计故障检测与恢复策略是非常重要的。

《Planar pose graph optimization: Duality, optimal solutions, and verification, 2015》和《Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions, 2015》，能够通过求解一个稀疏的线性系统来执行验证，当出现强对偶时，可以提供对正确答案的保证。

• 在机器人领域，这些结果在其他社区取得了不少有用的相关工作：

《Wide-sense estimation on the special orthogonal group, 2008》，《Sensor network localization on the group of 3D displacements, 2015》，《On frame and orientation localization for relative sensing networks, 2013》，《Intrinsic consensus on SO(3) with almost global convergence, 2012》，《Exact and stable recovery of rotations for robust synchronization, 2013》，属于多代理（Agent）系统的定位领域。
《Simultaneous multiple rotation averaging using lagrangian duality, 2012》，《Combining two-view constraints for motion estimation, 2001》，《Rotation averaging, 2013》，《Robust rotation and transla- tion estimation in multiview reconstruction, 2007》，属于机器视觉中运动恢复结构领域。
《Angular synchronization by eigenvectors and semidefinite programming, 2010》和《Three-dimensional struc- ture determination from common lines in Cryo-EM by eigenvectors and semidefinite programming, 2011》，是电子冷沉淀显微技术领域的文献。

• 待解决的问题尽管近年来有着空前的发展，但是仍有一些理论问题尚未挑战。
• 1. **泛化、保障和验证：**目前大部分的全局最优解和验证技术都是基于位姿图优化领域的，这些结果是否可以推广到任意的因子图？
• 1. **弱对偶与强对偶：**具有强对偶约束的SLAM可以进行全局求解，在实践应用中大部分的例子都具有强对偶约束。尚未解决的问题是，建立一个对问题是否强对偶约束的先验条件，就可以回答诸如“给定一组传感器（已经对应的测量噪声的统计信息）和一个因子图结构，该问题是否具有强对偶约束？”回答这样的问题的能力，可以让我们定义能够计算全局解决方案的SLAM应用领域。这项理论研究还可以提供对传感器和主动SLAM设计的帮助。
• 1. **离群值恢复：**目前的研究结果对位姿图提供强有力的保证，但是如果出现了离群值，这些方法都不可用。尽管有很多在鲁棒性SLAM方面的工作，和针对非高斯噪声的模型工具，设计能够恢复离群值的全局优化技术，以及在出现离群值的情况下验证估计是否正确的技术，尚未解决。

《Robust incremental online inference over sparse factor graphs: Beyond the gaussian case, 2013》，提出了针对非高斯噪声的模型。

• ==8 主动SLAM==
• 迄今为止，我们把SLAM描述为一个由机器人被动执行的估计问题，也就是说机器人利用给定的传感器数据来执行SLAM，而不是刻意去收集数据。主动SLAM研究的是如何利用机器人的运动来改进定位与建图的结果。定义：控制机器人的运动以最小化地图表达和定位的不确定问题被称为主动SLAM。（也被称为同时规划、定位与建图，SPLAM）。

《Active Perception, 1988》和《Probabilistic Robotics, 2005》，这两本书是该定义的起源，前者提出了主动感知，后者提出了机器人探索范型。

• 简要回顾：

《Simultaneous Stochastic Mapping and Localization, 1999》和《Adaptive Mobile Robot Navigation and Mapping, 1999》，第一个提出并实现主动SLAM算法的工作可以追述到这两篇文献。
《Active SLAM using Model Predictive Control and Attractor Based Exploration, 2006》，则提出了主动SLAM（Active SLAM）这个术语。
《Goal seeking components for adaptive intelligence: An initial assessment, 1981》，主动SLAM的根本思想来自于人工智能和机器人探索。
《Active Exploration in Dy- namic Environments, 1992》和《Exploration in Active Learning, 1995》，推断解决探索与开采困境（exploration-exploitation dilemma），在访问新位置（探索）和访问已知区域以减少不确定性（开采）之间寻找一个平衡点。这两篇文献提供了一个更有高效的方案以替代随机探索与单纯的开采。

• 主动SLAM是一个决策制定问题，有一些决策制定通用框架可以作为探索与开采决策的支柱。

《Fast Minimum Uncertainty Search on a Graph Map Repre- sentation, 2012》和《On the Comparison of Uncertainty Criteria for Active SLAM, 2012》，采用了《Foundations of Optimum Experimental Design, 1986》提出的最优实验设计理论（TOED）。
《Autonomous Robotic Exploration Using Occupancy Grid Maps and Graph SLAM Based on Shannon and Re ́nyiEntropy, 2015》和《Robotic Mapping and Exploration, 2009》，则提出了采用《Information Theory, Inference & Learning Algorithms, 2002》和《On Measures Of Entropy And Information, 1960》两篇文献提出的信息理论。在这种情况下，决策制定由信息增益的概念来指导。
《Active SLAM using Model Predictive Control and Attractor Based Exploration, 2006》和《Planning Under Uncertainty using Model Predictive Control for Information Gathering, 2006》，使用模型预测控制的控制理论方法。
《Planning and acting in partially observable stochastic domains, 1998》，采用了部分可观察马尔科夫决策过程，这种方法是难以计算的。
《A Bayesian Exploration- exploitation Approach for Optimal Online Sensing and Planning with a Visually Guided Mobile Robot, 2009》，采用了贝叶斯优化来近似部分可观察马尔科夫决策过程，使得主动SLAM易于计算。

• 一种流行的主动SLAM框架，在一个有限的集合中选择最好的未来行为，这个主动SLAM算法类执行三个主要步骤：（1）机器人在当前对地图的估计中，确定要去探索或开采的位置（例如，优势点）；（2）机器人计算访问每一个优势点的功效，然后选择功效最高的行为；（3）机器人执行选中的行为，并决定是否有必要继续执行任务或终止任务。

《A Novel Measure of Uncertainty for Mobile Robot SLAM with RaoBlackwellized Particle Filters, 2008》
《Active SLAM and Exploration with Particle Filters Using Kullback-Leibler Divergence, 2014》
《An Experiment in Integrated Exploration, 2002》

• 1. 选择优势点：

《Coordinated Multi-robot Exploration, 2005》和《A Bayesian Exploration-exploitation Approach for Optimal Online Sensing and Planning with a Visually Guided Mobile Robot》，理想状态下，机器人执行主动SLAM算法应该评估对机器人和地图空间中所有的可能行为进行评估，但是这种评估的计算复杂度会依照搜索空间的增加呈指数增长。这两篇文献中，证明了这在实际应用中是难以计算的。
《Efficient frontier detection for robot exploration, 2014》和《A Frontier-based Approach for Autonomous Exploration, 1997》，使用诸如边界探索技术来来选取地图中位置的一个小的子集，
《Motion Planning Under Uncertainty Using Iterative Local Op- timization in Belief Space, 2012》和《Planning in the continuous domain: A generalized belief space approach for autonomous navigation in unknown environments, 2015》，提出了在非确定环境下的连续空间规划可以用于主动SLAM。目前这些方法只能保证收敛到一个局部最优策略。
另一项最近的用于主动SLAM算法使用位势场，《Potential information fields for mobile robot exploration, 2015》使用了卷积技术来计算熵来选择机器人的行为。《Ouroboros: Using potential field in unexplored regions to close loops, 2015》则采用了边值问题的解决方案。

• 1. 计算行为的功效

《Information Based Adaptive Robotic Exploration, 2002》和《Information Gain-based Exploration Using Rao-Blackwellized Particle Filters, 2005》，在理想状况下，要计算机器人给定行为的功效，需要通过机器人位姿和地图来推导执行该动作后的变化，这需要考虑未来的可控行为和未知测量。如果未来的状况已知，就可以用信息理论函数作为信息增益来对不同的行为进行评价。
《Active SLAM and Exploration with Particle Filters Using Kullback-Leibler Divergence, 2014》、《Active SLAM and Loop Prediction with the Segmented Map Using Simplified Models, 2010》和《Information Gain-based Exploration Using Rao-Blackwellized Particle Filters, 2005》，指出通常情况下，这种联合概率分析是难以计算的，因此需要采用近似值的方法来解决。
对于地图与机器人的不确定性，《Active Pose SLAM, 2012》认为它们之间是独立的，《Information Gain-based Exploration Using Rao-Blackwellized Particle Filters, 2005》则将其考虑为条件独立的。
《A Novel Measure of Uncertainty for Mobile Robot SLAM with RaoBlackwellized Particle Filters, 2008》、《Information Based Adaptive Robotic Exploration, 2002》、《An Application of Kullback-Leibler Divergence to Active SLAM and Exploration with Particle Filters, 2010》和《Perception-driven Navigation: Active visual SLAM for Robotic Area Coverage, 2013》，大部分的方法令功效等于对机器人和地图不确定性量化度量结果的一个线性组合。这种方法的缺点是两种不确定值的数值大小是无法比较的，通常地图的不确定性的数量级大于机器人的不确定性，因此需要手工调整来进行修正。
《Active SLAM and Exploration with Particle Filters Using Kullback-Leibler Divergence, 2014》、《A Novel Measure of Uncertainty for Mobile Robot SLAM with RaoBlackwellized Particle Filters, 2008》和《Autonomous Robotic Exploration Using Occupancy Grid Maps and Graph SLAM Based on Shannon and Renyi Entropy, 2015》，提出了解决上述问题的解决方案，前两者是基于粒子滤波的，第三篇则是基于位置图优化的。
《On the Comparison of Uncertainty Criteria for Active SLAM, 2012》和《On the Monotonicity of Optimality Criteria during Exploration in Active SLAM, 2014》，优化实验设计理论（TOED）也可以用来计算执行行为的功效，在TOED中，每个行为被看成是一个随机的设计，采用所谓的最优化标准（A-opt, D-opt, E-opt）使用关联协方差矩阵来进行比较。这两篇文献在主动SLAM中使用了最优化标准。

• 1. **执行行为或终止探索：**执行一个行为通常是一个简单的任务，可以使用已经建立好的运动规划方法。但是探索任务是否已经完成依然是一个尚未解决的问题。
• 待解决的问题
• 1. **对未来状态快速和精确的预测：**主动SLAM中的每一个行为应该有助于减少地图的不确定性，并增进定位的精确度。为了实现这个目的，机器人必须能够预测未来行为对地图和机器人定位的影响。这个预测应该足够快以支持任意时间上的约束，并足够精确以支持决策过程。

《A discussion of simultaneous localization and mapping, 2006》，讨论了闭环检测对于降低地图不确定性与获得更高的定位与建图精确度方面的重要性。
《Planning in the continuous domain: A generalized belief space approach for autonomous navigation in unknown environments, 2015》和《A Bayesian Exploration- exploitation Approach for Optimal Online Sensing and Planning with a Visually Guided Mobile Robot《 2009》，尽管如此，高效的预测方法以及闭环的效果，还没有在主动SLAM领域被设计出来。
《Hilbert space embeddings of hidden Markov models, 2010》和《Learning deep dynamical models from image pixels, 2015》，最近的预测未来机器人状态的方法可以被发现于机器学习文献，前者涉及使用了光谱技术，后者则使用了深度学习。

• 1. **够用就足够了：何时停止主动SLAM?**主动SLAM是一个计算昂贵的任务，因此一个自然的问题就是：我们何时可以停止主动SLAM，并将资源投入到其他任务当中。由于在大部分的真实任务中，主动SLAM仅仅是达成一个预期目标的手段，因此平衡主动SLAM决策与外源性任务是决定性的。此外，拥有一个停止标准是非常重要的，由于在某些情况下更多的信息导致两个问题：（1）会降低信息的效果；（2）如果出现矛盾的信息，会产生一个无法恢复的状态（例如，几个错误的闭环）。

《A theoretical look at information-driven sensor management criteria, 2011》，《On Task-oriented Criteria for Configurations Selection in Robot Calibration, 2013》和《Sensor management: Past, present, and future, 2011》，与难以在系统之间进行比较的基于信息理论的度量，由TOED生成的面向任务的不确定性度量更有希望作为停止标准。

• 1. **性能许可：**另一个重要的问题是需要寻找对主动SLAM和近似最优策略的数学保证。由于精确的求解是很难处理的，因此需要一个具有清晰性能边界的近似算法。

《Adaptive submodularity: Theory and applications in active learning and stochastic optimization, 2011》，是在主动传感器放置领域的工作，该文献使用了子模性（submdularity）。

• ==9 可应用于SLAM的新型传感器==
• SLAM领域（通用移动机器人领域）的发展除了包含设计新的算法，还经常被可用的新奇的传感器所促进。例如引入二维激光测距仪，使创造非常鲁棒的SLAM系统成为可能。而三维雷达则是对诸如自动驾驶汽车等领域最主要的推动原力。在过去的五年间，大量的研究都贡献在视觉传感器方面，产生了很多成功的应用，例如增强现实和基于视觉的导航。标准的视觉传感器竟成为近期、中期的关键技术，尤其对于由于负载和能源受限设备（例如微型飞行器），而无法使用沉重或高耗能的传感器（例如激光测距仪）。因此就产生了这样一个问题：哪一种传感器技术将会驱动未来长期的SLAM研究？为了最好的使用这些新的传感器，哪些算法会被需要。
• 我们讨论这个问题的原因之一就是我们目前还没有在敏捷性和可操作性方面能与昆虫或动物（猎豹和鸟）相同的机器人。我们依然在使用高延迟、时间离散化的标准计算机视觉传感器架构。延迟是捕获图像与处理图像的时间之和，时间离散值是需要等待下一帧到达的时间。计算机视觉流水线的平均延迟时间是50-200ms，时间离散值出于5到100毫秒之间，由相机的帧率与曝光时间决定。高延迟与长时间离散值束缚了机器人平台的最大敏捷度。例如，考虑一个中型无人机的执行机构需要大约30毫秒，当缩小无人机的尺寸之后能够快速的降到一毫秒以内。因此要实现敏捷的运动，我们需要更快的传感器和低延迟的处理。基于事件的相机是替换现有视觉传感器的完美替代品。
• 基于事件的传感器：

《A 128×128 120 dB 15 μs latency asynchronous temporal contrast vision sensor, 2008》，DVS（Dynamic Vision Sensor）
《An asynchronous time-based image sensor, 2008》，ATIS（Asynchronous Time based Image Sensor）

• DVS和ATIS改变了基于视觉感知的领域。与按照固定帧率发送完整图像的标准基于帧的相机不同，事件相机仅仅发送由于场景运动而产生变化的局部区域。当一个像素的强度变化大于阈值时，时间被触发（对于DVS，当对数强度变化大于10%-20%时，触发事件。人眼灵敏到可以观察到1%的变化。）。因此它的输出是分辨率到达毫秒级的异步事件序列。每个时间都是一个四元组（包含了时间戳，发生变化像素的坐标，与触发的事件，事件通常用二进制的值来表示亮度变化的符号）。
• 与标准的基于帧的摄像机相比，基于事件的摄像机具有以下五个优点：（1）延迟时间1毫秒；（2）测量速率提高到1MHz；（3）动态范围提高到140dB（标准摄像机大约是60-70dB之间）；（4）耗电为20mW（标准相机1.5W）；（5）极低的传输带宽（对于一般的运动传输带宽为KB/s级别，而标准相机是MB/s级别）。
• 这些特性使得基于事件的相机的算法可以完成很多具有挑战性的工作。例如在月光下追踪一个棒球，或者开发一个像苍蝇一样灵活的自主机器人，或者去挑战具有极端光照条件或高速环境下的定位与建图。然而这些优点是有开销的：由于事件相机的输出由一个异步事件序列构成，因此传统的基于帧的计算机视觉算法将无法使用。从传统的计算机视觉方法的范型迁移到视觉相机可能需要五十年的时间。
• 简要回顾
• 由于基于事件的相机出现于2008年，目前使用这种相机来实现算法的文献数量较少，不到100篇。

《A 128�128 120 dB 15 �s latency asynchronous temporal contrast vision sensor, 2008》，是第一篇介绍基于事件相机的文献。
《Asynchronous event-based corner detection and matching, 2015》，讨论了适应基于事件的特征检测与跟踪算法。
《Low-latency localization by active LED markers tracking using a dynamic vision sensor, 2013》，进行了LED跟踪。
《Asynchronous event-based Hebbian epipolar geometry, 2011》，讨论了基于事件相机的对极几何。
《Simultaneous optical flow and intensity estimation from an event camera, 2016》、《Asynchronous frameless event-based optical flow, 2012》、《Interacting maps for fast visual interpretation, 2011》和《Simultaneous mosaicing and tracking with an event camera, 2014》，讨论了利用基于事件的相机进行图像重建、运动估计和光流法。
《Event-based 3D reconstruction from neuromorphic retinas, 2013》，讨论了使用基于事件相机的三维重建。
《Asynchronous event-based visual shape tracking for stable haptic feedback in microrobotics, 2012》，提出了基于事件相机的ICP算法。

• 下面这些文献所涉及算法的涉及目标为：每一个事件都可以异步的改变系统的估计状态。

《Low-latency event-based visual odometry, 2014》，提出了基于事件相机的视觉里程计。
《Continuous-time trajectory estimation for event-based vision sensors, 2015》、《Event-based, 6-DOF pose tracking for high-speed maneuvers, 2014》和《Event-based particle filtering for robot self-localization, 2012》，讨论了基于事件相机的定位话题。
《Simultaneous localization and mapping for event-based vision systems, 2013》和《Event-based 3d slam with a depthaugmented dynamic vision sensor, 2014》，实现了基于事件相机的SLAM算法。
《A pencil balancing robot using a pair of AER dynamic vision sensors, 2009》和《Lowlatency heading feedback control with neuromorphic vision sensors using efficient approximated incremental inference, 2015》，提出了保存基于事件的性质，并支持设计一个高速的反应系统。
《A hybrid SLAM representation for dynamic marine environments, 2010》和《Continuous-time batch estimation using temporal basis functions, 2012》以及《Continuous-time trajectory estimation for event-based vision sensors, 2015》，等文献指出连续时间的轨迹估计非常适合基于事件的相机：由于DVS平均每秒钟产生10万个事件，而每个事件又无法携带足够进行状态估计的信息，由于用于表示所有相机位姿的向量会随着事件的产生快速的增长尺寸，因此利用离散时间方法来估计位姿的计算会非常棘手。使用连续时间的框架，DVS的位姿轨迹就可以被近似为一条位于刚体运动空间的光滑曲线（该曲线由基本函数构成，例如三次样条函数），并利用根据观测的事件对其进行优化。

• 待解决的问题
• 1. **建模、灵敏度和分辨率：**事件相机包含了一个复杂的模拟电路（该电路的非线性与偏移会改变像素的灵敏度）以及其他动态属性（这些动态属性很不幸容易收到噪声的影响）。目前还没有这类传感器噪声的完整属性，因此距离利用事件相机来解决SLAM问题依然需要很长的时间。
• 由于事件是由亮度变化触发的，因此事件的产生对应着场景中的边。然而，大部分提出的事件流水线都是针对具有较强变化的梯度，当出现光滑边界的时候这些方法会失败。
• 基于事件的相机尽管时间分辨率很高（1微秒），但是空间分辨率却很低（128*128像素）。这方面也有很多的努力：ATIS可以发送像素级别的亮度大小；DAVIS可以同时输出帧图像和事件（可能是吧基于帧的传感器和DVS嵌入到了同一个像素阵列）。

《A 240x180 130dB 3us latency global shutter spatiotemporal vision sensor, 2014》

• 1. 基于事件和标准相机，哪一个最适合SLAM？

《Steps Towards a Theory of Visual Information: Active Perception, Signal-to-Symbol Conversion and the Interplay Between Sensing and Control, 2011》，指出解决SLAM问题的传感器-算法对的性能，取决于传感器和算法的参数，以及环境。
《A power-performance approach to comparing sensor families, with application to comparing neuromorphic to traditional vision sensors, 2015》，尽管对如何选择算法和传感器来达到最佳性能尚无定论，这篇文献做出了初步的研究。研究表示给定任务的性能还依赖于可用于传感器的能耗，该文献建议最理想的传感架构应该拥有多种传感器，并可以依据性能的需求级别来瞬时开关。