SLAM Algorithm Types Compared: EKF, Particle Filter, Graph-Based, and More

Simultaneous Localization and Mapping (SLAM) algorithms form the computational backbone of autonomous navigation, enabling robots, vehicles, and drones to build spatial models of unknown environments while tracking their own position within those models. The algorithm family spans probabilistic filters, graph optimization methods, and hybrid architectures, each with distinct computational profiles and accuracy characteristics. Understanding the boundary conditions and tradeoffs between these approaches is essential for selecting the correct algorithm class for a given deployment constraint. This page provides a structured comparison of the primary SLAM algorithm types, covering mechanics, classification, tradeoffs, and common misconceptions.

Definition and Scope

SLAM algorithms solve a joint estimation problem: given a sequence of sensor measurements and motion commands, compute the posterior distribution over both the map of an environment and the agent's pose within it. The formal problem was structured in its modern probabilistic form by Smith, Self, and Cheeseman in a 1987 paper that introduced the concept of representing spatial uncertainty through covariance matrices — a foundational framing adopted by subsequent IEEE Robotics and Automation Society literature.

The scope of SLAM algorithm types covers four primary families: filter-based methods (Extended Kalman Filter and Particle Filter variants), graph-based optimization methods, factor graph methods, and learning-augmented methods. Each family makes different assumptions about Gaussian noise, computational scaling, and the structure of the pose graph. The choice of algorithm family has downstream effects on map representation, explored in depth at SLAM Architecture Map Representations, and on real-time performance, analyzed at Real-Time SLAM Architecture Requirements.

Core Mechanics or Structure

Extended Kalman Filter (EKF-SLAM)

EKF-SLAM linearizes nonlinear motion and observation models using first-order Taylor expansion. The state vector encodes the robot pose and all landmark positions simultaneously. The filter maintains a covariance matrix of dimension (3 + 2N) × (3 + 2N), where N is the number of landmarks. Computational cost scales as O(N²) per update step — a hard constraint that limits practical deployment to environments with fewer than roughly 1,000 landmarks before processing latency becomes prohibitive.

Particle Filter (FastSLAM)

FastSLAM, introduced by Montemerlo et al. at Carnegie Mellon University in 2002, decomposes the SLAM posterior using the Rao-Blackwellization theorem. Each particle carries an independent estimate of the robot path and a set of per-landmark Kalman filters. This decomposition reduces per-update complexity to O(M log N), where M is the particle count and N is landmark count. The tradeoff is particle degeneracy in high-dimensional spaces, which causes filter collapse when particle diversity drops below a critical threshold.

Graph-Based SLAM (Pose Graph Optimization)

Graph-based methods separate front-end data association from back-end optimization. The front-end constructs a pose graph where nodes represent robot poses and edges represent spatial constraints derived from sensor measurements or loop closure detections. The back-end solves a nonlinear least-squares problem over the full graph using solvers such as g2o (General Graph Optimization, developed at the University of Freiburg) or GTSAM (Georgia Tech Smoothing and Mapping library). This architecture enables global map consistency correction when loop closures are detected, a process detailed at Loop Closure in SLAM Architecture.

Factor Graph Methods

Factor graphs generalize pose graphs by representing both pose nodes and landmark nodes as variables, connected by factor nodes encoding probabilistic constraints. iSAM2 (Incremental Smoothing and Mapping, Georgia Institute of Technology) performs incremental Bayes tree updates, enabling efficient re-linearization of only the affected subgraph rather than re-solving the entire system. This incremental structure is particularly important for Sensor Fusion in SLAM Architecture, where heterogeneous sensor constraints must be integrated continuously.

Causal Relationships or Drivers

The diversity of SLAM algorithm types emerged from three computable pressures: computational hardware constraints, sensor modality requirements, and environment scale.

Early robotic platforms in the 1990s lacked the processing power for global optimization, making filter-based approaches the only viable option. EKF-SLAM's O(N²) scaling was acceptable in structured indoor environments where landmark counts were low. As outdoor and large-scale deployments became targets — particularly for autonomous vehicles operating in environments with tens of thousands of features — the quadratic scaling made EKF-SLAM impractical.

Particle-filter approaches emerged as a response to nonlinearity. Real sensor models for LiDAR and sonar are not well-approximated by Gaussian distributions, which EKF assumes. Particle filters make no Gaussian assumption, instead representing the posterior as a weighted sample set. The cost is memory and the particle degeneracy problem in high-DOF systems.

Graph-based methods gained dominance after 2005 partly due to the availability of sparse linear algebra solvers (CHOLMOD, CSparse) that could exploit the sparse structure of large pose graphs. The computational complexity of back-end optimization became nearly linear in the number of nodes for sparse graphs, enabling large-scale outdoor mapping. The development ecosystem around ROS (Robot Operating System, Open Robotics Foundation) further accelerated graph-based method adoption by providing standardized interfaces for algorithms like Cartographer (Google) and Hector SLAM.

Classification Boundaries

SLAM algorithms divide along three primary axes:

Temporal processing model: Online (filter-based) vs. batch/incremental (graph-based). Filter methods process measurements sequentially and discard past states; graph methods retain and re-optimize the full trajectory history.

Noise model assumption: Gaussian (EKF) vs. non-parametric (Particle Filter) vs. general least-squares (graph/factor graph). The Gaussian assumption fails when sensor noise distributions have heavy tails or multimodal characteristics.

Map representation coupling: Some algorithms are tightly coupled to specific map types. EKF-SLAM requires a landmark-based (feature map) representation. Occupancy grid maps are natively supported by particle filter variants like GMapping (OpenSLAM project). Graph-based methods are representation-agnostic at the back-end but depend on front-end feature extraction quality.

A fourth axis — learning-augmented vs. model-based — is addressed at Deep Learning in SLAM Architecture, where neural feature extractors replace hand-engineered descriptors in the front-end pipeline.

Tradeoffs and Tensions

Consistency vs. Scalability: EKF-SLAM produces theoretically consistent uncertainty estimates when linearization error is small, but this consistency degrades as environments grow. Graph-based methods scale better but can produce overconfident maps if loop closure constraints are incorrect — a problem called "incorrect loop closure propagation" that corrupts global map geometry.

Computational latency vs. Global accuracy: Particle filters provide real-time performance without global optimization but accumulate linearization-free drift. Graph methods produce globally consistent maps but introduce optimization latency that must be managed through incremental solvers or asynchronous back-end threads. The architecture requirements for managing this tension are covered at SLAM Architecture Edge Computing.

Memory footprint vs. Representation richness: Maintaining a particle population of 500–1,000 particles with per-particle landmark Kalman filters consumes substantial RAM on embedded systems. Graph-based pose graphs grow linearly with trajectory length, reaching sizes that require marginalization (discarding old nodes) for memory-bounded operation.

Robustness vs. Optimality: Maximum likelihood graph optimization is sensitive to outlier constraints. Robust cost functions (Huber loss, Dynamic Covariance Scaling) trade strict optimality for resistance to data association errors, which are frequent in dynamic environments such as those encountered in SLAM Architecture for Autonomous Vehicles.

Common Misconceptions

Misconception 1: EKF-SLAM is obsolete.
EKF-SLAM remains the correct choice in structured environments with a bounded, low landmark count and strict real-time latency requirements. Embedded systems in SLAM Architecture for Robotics applications, particularly manipulator arms operating in fixed workspaces, continue to use EKF-based localization successfully.

Misconception 2: More particles always improve particle filter accuracy.
Beyond a threshold determined by the dimensionality of the state space, additional particles yield diminishing returns and increase computational cost without proportional accuracy gains. Adaptive resampling strategies (KLD-sampling, introduced by Fox at the University of Washington) dynamically adjust particle counts to match estimated posterior complexity.

Misconception 3: Graph-based SLAM eliminates drift.
Graph-based methods correct drift only at loop closure events. Between closures, the front-end odometry still accumulates error. In GPS-denied environments — detailed at SLAM Architecture for GPS-Denied Environments — long traversals without revisited areas produce the same cumulative error as filter-based methods.

Misconception 4: Factor graphs and pose graphs are interchangeable terms.
A pose graph is a special case of a factor graph in which only pose-to-pose constraints appear. Factor graphs are the more general formulation, supporting landmark variables, IMU preintegration factors, and cross-sensor constraints within a single unified graphical model.

Checklist or Steps

The following steps describe the operational sequence common to graph-based SLAM back-end processing:

  1. Front-end sensor processing — Raw sensor data (LiDAR point clouds, camera frames) passes through preprocessing to extract features or generate scan representations.
  2. Odometry estimation — Consecutive scan matching (ICP, NDT) or visual odometry produces an initial relative pose estimate between time steps.
  3. Node creation — A new pose node is added to the graph when displacement or rotation exceeds a defined threshold, preventing graph growth proportional to time rather than motion.
  4. Edge constraint addition — The relative pose estimate and its associated covariance matrix are encoded as a binary edge connecting the new node to the previous node.
  5. Loop closure candidate detection — Candidate revisited locations are identified using place recognition methods (scan-to-map matching, bag-of-words descriptors, NetVLAD descriptors).
  6. Loop closure verification — Candidates passing geometric verification are added as loop closure edges to the graph.
  7. Back-end optimization trigger — New loop closure edges trigger an optimization pass using g2o, GTSAM, or equivalent sparse solver.
  8. Map update — The optimized pose graph drives a map regeneration step, updating the global occupancy grid or point cloud representation.

The evaluation of this pipeline against benchmark datasets is addressed at SLAM Architecture Evaluation and Testing.

Reference Table or Matrix

Algorithm Type Complexity (Update) Noise Model Map Type Loop Closure Primary Limitation
EKF-SLAM O(N²) Gaussian only Feature/landmark Implicit via state Quadratic scaling with landmarks
FastSLAM (Particle) O(M log N) Non-parametric Occupancy grid Via particle resampling Particle degeneracy in high-DOF
Pose Graph (batch) O(N) sparse General Any Explicit constraint Optimization latency at loop closure
iSAM2 (Factor Graph) O(k) incremental General Any Explicit constraint Bayes tree complexity under large re-linearization
Kalman-based Visual SLAM O(N²) Gaussian Sparse feature Implicit Scale ambiguity in monocular setups
LiDAR-Odometry Graph (e.g., LOAM) O(N) amortized Least-squares Dense/feature Optional Requires high-frequency LiDAR (≥10 Hz)

Algorithm selection criteria vary by deployment domain. The foundational overview of how algorithm type interacts with system architecture is available at the SLAM Architecture home reference, with sensor-specific instantiations covered at LiDAR-Based SLAM Architecture and Visual SLAM Architecture.

References