同时定位与地图构建

同步定位与地图构建 (SLAM) 是构建或更新未知环境地图同时跟踪代理在其中的位置的计算问题。 虽然这最初看起来是一个先有鸡还是先有蛋的问题，但有几种已知的算法可以在某些环境下至少大约在易于处理的时间内解决它。 流行的近似求解方法包括粒子滤波器、扩展卡尔曼滤波器、协方差交集和 GraphSLAM。 SLAM 算法基于计算几何和计算机视觉中的概念，并用于虚拟现实或增强现实的机器人导航、机器人映射和里程计。

SLAM 算法是根据可用资源量身定制的，并非以完美为目标，而是以操作合规性为目标。 已发表的方法被用于自动驾驶汽车、无人驾驶飞行器、自主水下航行器、行星漫游车、新型家用机器人甚至人体内部。

给定一系列控制 u t {\displaystyle u_{t}} 和传感器观测值 o t {\displaystyle o_{t}} 在离散时间步长 t {\displaystyle t} 上，SLAM 问题是计算 智能体的状态 x t {\displaystyle x_{t}} 和环境地图 m t {\displaystyle m_{t}} 。 所有数量通常都是概率性的，因此目标是计算：

P ( m t + 1 , x t + 1 | o 1 : t + 1 , u 1 : t ) {\displaystyle P(m_{t+1},x_{t+1}|o_{1:t+1} ,u_{1:t})}

应用贝叶斯规则给出了一个框架，用于顺序更新位置后验，给定地图和转换函数 P ( x t | x t − 1 ) {\displaystyle P(x_{t}|x_{t-1})} ，

P ( x t | o 1 : t , u 1 : t , m t ) = ∑ m t − 1 P ( o t | x t , m t , u 1 : t ) ∑ x t − 1 P ( x t | x t − 1 ) P ( x t − 1 | m t , o 1 : t − 1 , u 1 : t ) / Z {\displaystyle P(x_{t}|o_{1:t},u_{1:t},m_{t})= sum _{m_{t-1}}P(o_{t}|x_{t},m_{t},u_{1:t})\sum _{x_{t-1}}P(x_ {t}|x_{t-1})P(x_{t-1}|m_{t},o_{1:t-1},u_{1:t})/Z}

同样，地图可以按顺序更新

P ( m t | x t , o 1 : t , u 1 : t ) = ∑ x t ∑ m t P ( m t | x t , m t − 1 , o t , u 1 : t ) P ( m t − 1 , x t | o 1 : t − 1 , m t − 1 , u 1 : t ) {\displaystyle P(m_{t}|x_{t},o_{1:t},u_{1:t})=\sum _{x_{ t}}\sum _{m_{t}}P(m_{t}|x_{t},m_{t-1},o_{t},u_{1:t})P(m_{t- 1},x_{t}|o_{1:t-1},m_{t-1},u_{1:t})}

与许多推理问题一样，通过以期望最大化算法的形式交替更新两个信念，可以找到将两个变量一起推理到局部最优解的解。

用于近似上述方程的统计技术包括卡尔曼滤波器和粒子滤波器。 它们为机器人的姿态和地图的参数提供了后验概率分布的估计。 使用协方差交集保守地近似上述模型的方法能够避免依赖统计独立性假设以降低大规模应用的算法复杂性。 其他近似方法通过使用不确定性的简单有界区域表示来提高计算效率。

集合成员技术主要基于区间约束传播。 他们提供了一个包含机器人姿态的集合和地图的集合近似值。 束调整，更普遍的是xxx后验估计 (MAP)，是使用图像数据的 SLAM 的另一种流行技术，它联合估计姿势和地标位置，提高地图保真度，并用于商业化的 SLAM 系统，例如 Google 的 ARCore 这取代了他们之前的增强现实项目“探戈”。 MAP 估计器根据传感器数据计算机器人姿势和地图的最可能解释，而不是试图估计整个后验概率。

新的 SLAM 算法仍然是一个活跃的研究领域，并且通常受到对地图、传感器和模型类型的不同要求和假设的驱动，如下所述。 许多 SLAM 系统可以被视为来自这些方面的选择的组合。

拓扑图是一种环境表示方法，它捕获环境的连通性（即拓扑）而不是创建几何精确的地图。 拓扑 SLAM 方法已用于在度量 SLAM 算法中强制执行全局一致性。

相比之下，网格地图使用离散单元阵列（通常为正方形或六边形）来表示拓扑世界，并推断哪些单元被占用。 通常假设单元格在统计上是独立的，以简化计算。 在这样的假设下，如果 新地图的单元格与位置 x t {\displaystyle x_{t}} 处的观察 o t {\displaystyle o_{t}} 一致。