SLAM: Simultaneous Localization and Mapping

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 $u_{1:t}$
• Observations of nearby features $z_{1:t}$

Estimate:

• The map $m$
• The path $x_{1:t}$

Formally, we want the posterior distribution $$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(x_{1:t}, m \mid z_{1:t}, u_{1:t}).$$
• Online SLAM estimates only the current pose and the map: $$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: $$x_t = \begin{bmatrix} x_t^r \\ m \end{bmatrix},$$ where $x_t^r$ is the robot pose and $m$ the landmark locations. The update consists of:

• Prediction, propagate pose using the motion model: $$\hat{x}_t = f(x_{t-1}, u_t) + \epsilon_t.$$
• Correction, incorporate the observation: $$K_t = \Sigma_t H_t^\top (H_t \Sigma_t H_t^\top + Q_t)^{-1},$$ $$x_t \leftarrow \hat{x}_t + K_t (z_t - h(\hat{x}_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(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.

---