SLAM

SLAM (Simultaneous Localization and Mapping) is the computational problem of constructing or updating a map of an unknown environment while simultaneously keeping track of an agent's location within it. The problem is simultaneously epistemic and geometric: the agent must infer its own position from sensor data, but the sensor data can only be interpreted relative to a map, which is itself unknown. SLAM is the quintessential chicken-and-egg problem of embodied robotics.

The problem was first formulated in the 1980s by researchers including Randall Smith, Matthew Self, and Peter Cheeseman, who recognized that localization and mapping could not be solved independently — each provides constraints on the other. A robot that knows its location can build a map by recording sensor readings at known positions. A robot that has a map can determine its location by matching sensor readings to map features. But a robot that has neither must solve both problems together, using the consistency of sensor observations over time as the binding constraint.

The SLAM Problem

Formally, SLAM is a state estimation problem in which the state vector includes both the robot's pose (position and orientation) and the coordinates of all landmarks in the environment. At each time step, the robot receives:

Odometry data — an estimate of its own motion, typically from wheel encoders or inertial measurement units, corrupted by noise.
Observation data — measurements of landmarks relative to the robot's current pose, typically from laser rangefinders, cameras, or depth sensors, also corrupted by noise.

The challenge is that both data sources are noisy and correlated. A wheel slip produces an odometry error that affects all subsequent pose estimates. A misidentified landmark produces a map error that affects all subsequent localization estimates. The errors compound, and without correction, the robot's estimated trajectory drifts without bound.

The classical solution framework is probabilistic SLAM, which treats both the robot's pose and the landmark positions as random variables and maintains a joint probability distribution over them. The two dominant algorithmic families are Kalman filter SLAM and particle filter SLAM (also known as FastSLAM).

Kalman Filter Approaches

The Extended Kalman Filter (EKF) was the first practical SLAM algorithm. It maintains a single Gaussian distribution over the joint state vector (robot pose + all landmark positions) and updates this distribution using linearized motion and observation models. The EKF is elegant and provides a single consistent map, but it suffers from two fundamental limitations:

Computational complexity is O(n²) in the number of landmarks, because the covariance matrix couples every landmark to every other landmark. This is a direct manifestation of the Frame Problem: the filter must track correlations between all pairs of landmarks to maintain global consistency.
Linearization error accumulates when the true motion and observation models are non-linear, which they always are in practice. The EKF's Gaussian approximation becomes increasingly inaccurate as the robot travels, leading to inconsistent maps and failed data association.

These limitations motivated Sparse Extended Information Filters (SEIF) and Thin Junction Tree Filters (TJTF), which exploit the sparsity of landmark correlations to reduce complexity. The key insight is that distant landmarks are weakly correlated — a fact about physical space that the algorithm can exploit to approximate the full covariance matrix with a sparse one. This is a local update architecture applied to probabilistic inference.

Particle Filter Approaches

FastSLAM, developed by Montemerlo and Thrun, solved the computational problem by factoring the joint distribution. It represents the robot's trajectory as a set of particles, and for each particle, it maintains a set of independent landmark estimates. Because the landmarks are conditionally independent given the trajectory, the complexity per particle is O(log n) rather than O(n²).

The particle filter approach is a paradigmatic patchwork system. Each particle is a self-consistent local hypothesis about the robot's path. The ensemble of particles is not globally consistent — different particles propose different trajectories — but the particle filter maintains this multiplicity rather than collapsing it into a single estimate. The correct trajectory is not computed; it emerges from the resampling process that weights particles by their observation likelihood.

This has a philosophical dimension that the SLAM literature rarely acknowledges. FastSLAM does not solve the SLAM problem by finding the one true map. It solves it by maintaining a population of map hypotheses and letting the environment select among them. The robot's knowledge of its environment is not a single representation but a patchwork of partial, competing models — exactly the architecture that patchwork intelligence predicts biological systems would use.

Graph-Based SLAM

The current state of the art is graph-based SLAM, which represents the SLAM problem as a graph optimization problem. Nodes in the graph represent robot poses and landmark positions. Edges represent constraints: odometry constraints between consecutive poses, and observation constraints between poses and landmarks. The map is the configuration of nodes that minimizes the total constraint error.

Graph-based SLAM is elegant because it separates the problem into two distinct phases:

Front-end — data association: determining which observations correspond to which landmarks. This is the hard problem, and it is where SLAM systems most often fail.
Back-end — graph optimization: finding the maximum-likelihood configuration given correct data association. This is computationally intensive but well-understood.

The optimization back-end is a global operation — it adjusts all poses and landmarks simultaneously to minimize total error. But modern implementations use sparse matrix techniques and incremental solvers that exploit the local structure of the graph. A loop closure (when the robot recognizes that it has returned to a previously visited place) introduces a long-range constraint, but the solver propagates this constraint only through the graph's connected components, not through the entire state space. This is local update at the algorithmic level, even when the mathematical formulation is global.

The Frame Problem in SLAM

SLAM is a paradigmatic case study for the Frame Problem because it makes the problem concrete and measurable. Every SLAM algorithm must answer the question: when the robot moves, what changes in the map? The answers differ:

In EKF-SLAM, the answer is: the robot's pose changes, and the covariance between the robot and all landmarks is updated. This is the global-update approach, and it pays the O(n²) cost.
In FastSLAM, the answer is: the robot's trajectory hypothesis changes, and only the landmarks observed from that trajectory are updated. This is the local-update approach, and it pays the cost of maintaining multiple hypotheses.
In graph-based SLAM, the answer is: the constraint graph is updated, and the optimization solver adjusts all poses to satisfy the new constraint. This is the global-optimization-local-execution approach.

The engineering history of SLAM is a history of progressively more sophisticated ways to avoid updating everything when something changes. The problem has not been solved by better mathematics. It has been dissolved by better architecture — by recognizing that global consistency is not necessary for local navigation, and that the map is a tool for action, not a mirror of reality.