Skip to main content
The SLAM problem asks: can a robot simultaneously build a map of an unknown environment and estimate its own trajectory within that map?

​
Problem formulation

Given:
  • The robot’s controls u1:tu_{1:t}
  • Observations of nearby features z1:tz_{1:t}
Estimate:
  • The map mm
  • The path x1:tx_{1:t}
Formally, we want the posterior distribution p(x1:t,m∣z1:t,u1:t),p(x_{1:t}, m \mid z_{1:t}, u_{1:t}), which couples both localization and mapping. There are two principal formulations:
  • Full SLAM estimates the entire path and the map: p(x1:t,m∣z1:t,u1:t).p(x_{1:t}, m \mid z_{1:t}, u_{1:t}).
  • Online SLAM estimates only the current pose and the map: p(xt,m∣z1:t,u1:t).p(x_t, m \mid z_{1:t}, u_{1:t}).
Graphical models make the conditional dependencies explicit: the map, robot poses, controls, and observations are jointly dependent.

​
Why SLAM is hard

  1. Coupled uncertainties — errors in robot pose propagate into errors in the map, and vice versa.
  2. Data association — observations must be correctly matched to landmarks. Wrong associations lead to catastrophic map corruption.
  3. Correlation of landmarks — as Dissanayake et al. (2001) showed, in the limit all landmark estimates become fully correlated.

​
Kalman filter for SLAM

The Extended Kalman Filter (EKF) is the classical solution (Smith & Cheesman, 1986). The state vector is: xt=[xtrm],x_t = \begin{bmatrix} x_t^r \\ m \end{bmatrix}, where xtrx_t^r is the robot pose and mm the landmark locations. The update consists of:
  • Prediction — propagate pose using the motion model: x^t=f(xt−1,ut)+ϵt.\hat{x}_t = f(x_{t-1}, u_t) + \epsilon_t.
  • Correction — incorporate the observation: Kt=ΣtHt⊤(HtΣtHt⊤+Qt)−1,K_t = \Sigma_t H_t^\top (H_t \Sigma_t H_t^\top + Q_t)^{-1}, xt←x^t+Kt(zt−h(x^t)),x_t \leftarrow \hat{x}_t + K_t (z_t - h(\hat{x}_t)), Σt←(I−KtHt)Σt.\Sigma_t \leftarrow (I - K_t H_t)\Sigma_t.
The EKF maintains correlations between all landmarks through the covariance matrix.

​
Properties of EKF-SLAM

  • Complexity O(n2)O(n^2) in the number of landmarks
  • Proven convergence for linear cases
  • Diverges if nonlinearities are severe
  • In the limit, landmarks become fully correlated

​
Techniques for consistent maps

  • Scan matching — align consecutive scans by maximizing their likelihood under a relative pose.
  • EKF-SLAM — model the posterior as a joint Gaussian over robot pose and landmarks.
  • FastSLAM — factorize the problem using Rao-Blackwellisation (Montemerlo et al., 2002).
  • Graph-SLAM / SEIFs — represent constraints sparsely in graph or information form.

​
Approximations and alternatives

  • Submaps (Leonard et al., 1999; Bosse et al., 2002) — partition environment into local maps.
  • Sparse links (Lu & Milios, 1997; Guivant & Nebot, 2001) — reduce correlations.
  • SEIF (Sparse Extended Information Filter) — exploit sparsity in the information matrix.
  • FastSLAM (Montemerlo et al., 2002) — factorize into a particle filter over robot trajectories and EKFs for landmarks.

​
Summary

SLAM is fundamentally a Bayesian estimation problem. Classical EKF-SLAM maintains correlations but is quadratic in complexity. FastSLAM and Graph-SLAM exploit structure for efficiency. Data association and uncertainty coupling remain the central challenges.
Edit this page on GitHub or file an issue.