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? 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: estimate 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: estimate 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.

​
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.
  • Graph-SLAM / SEIFs: Represent constraints sparsely in graph or information form.

​
Kalman Filter for SLAM

The Extended Kalman Filter (EKF) is the classical solution (Smith & Cheesman, 1986).
State vector: 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. Update consists of:
  • Prediction: propagate pose using motion model x^t=f(xt−1,ut)+ϵt.\hat{x}_t = f(x_{t-1}, u_t) + \epsilon_t.
  • Correction: incorporate 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.
  • Approximations (submaps, sparse information filters) reduce complexity.
  • In the limit, landmarks become fully correlated.

​
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 information matrix.
  • FastSLAM (Montemerlo et al., 2002): factorize into particle filter over robot trajectories and EKFs for landmarks.
SLAM is fundamentally a Bayesian estimation problem: p(x1:t,m∣z1:t,u1:t).p(x_{1:t}, m \mid z_{1:t}, u_{1:t}).
  • 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.
Connect these docs to Claude, VSCode, and more via MCP for real-time answers.