SLAM: Simultaneous Localization and Mapping

The SLAM problem is to build a map of an unknown environment while estimating the robot’s 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 localization and mapping. SLAM has two standard 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 show the conditional dependencies among the map, robot poses, controls, and observations.

​

Challenges in SLAM

1. Coupled uncertainties: Errors in the robot pose propagate into the map, and errors in the map affect the robot pose.
2. Data association: Each observation must be matched to the correct landmark. Incorrect associations can corrupt the map.
3. Landmark correlation: Dissanayake et al. (2001) showed that all landmark estimates become fully correlated in the limit.

​

Kalman filter for SLAM

The Extended Kalman Filter (EKF) is a standard SLAM method (Smith & Cheesman, 1986). Its 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 has two steps:

• Prediction: Propagate the 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 the robot pose and landmarks.
• FastSLAM: Factorize the problem using Rao-Blackwellization (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 the environment into local maps.
• Sparse links (Lu & Milios, 1997; Guivant & Nebot, 2001): Reduce correlations.
• SEIF (Sparse Extended Information Filter): Use sparsity in the information matrix.
• FastSLAM (Montemerlo et al., 2002): Factorize the posterior into a particle filter over robot trajectories and EKFs for landmarks.

​

SLAM methods and challenges

SLAM is a Bayesian estimation problem. EKF-SLAM maintains correlations with quadratic complexity. FastSLAM and Graph-SLAM use problem structure to reduce computation. Data association and coupled uncertainty remain the main challenges.

---