A Markov-Chain Monte Carlo Approach to Simultaneous Localization and Mapping.

Péter Torma, András György, Csaba SzepesváriAISTATS 2010 · OpenReview

Abstract

Simultaneous Localization and Mapping (SLAM) is a cornerstone of autonomous robotics, yet traditional methods like Extended Kalman Filters (EKF) and FastSLAM often struggle with non-linear dynamics or the "particle deprivation" problem during loop closure. This paper presents MCMC-SLAM, a novel algorithm that reframes SLAM as an inference problem on a graph. By employing a specialized Markov-Chain Monte Carlo (MCMC) sampling strategy based on spanning trees and label-preserving transformations, the proposed method achieves provable consistency for general dynamical and observation models. Experimental results demonstrate that MCMC-SLAM significantly outperforms existing techniques in accuracy, particularly in challenging loop-closing scenarios.

Introduction: The SLAM Challenge

Simultaneous Localization and Mapping (SLAM) is often described as a "chicken-and-egg" problem: a robot requires a map to determine its location, but it needs accurate localization to construct that map. Historically, the field has been dominated by two paradigms:

  1. Extended Kalman Filters (EKF): These are computationally efficient but rely on linearizations and Gaussian noise assumptions. In environments with complex sensors or non-linear motion, EKF-based SLAM frequently fails to maintain consistency.
  2. FastSLAM (Particle Filtering): This approach uses a set of "particles" to represent potential trajectories. While more flexible than EKF, it suffers from particle deprivation. During "loop closure"—when a robot returns to a previously visited location—the true state may occupy a very small region of the state space. If no particles are present in that specific region, the filter collapses, leading to inconsistent maps.

The MCMC-SLAM Framework

MCMC-SLAM addresses these limitations by treating the entire trajectory and map as a single inference graph. In this graph, vertices represent robot poses and landmark positions, while edges represent motion and observation constraints.

Spanning Tree Sampling

The core innovation is a specialized MCMC move designed to navigate the high-dimensional manifold of consistent SLAM states. The algorithm defines a spanning tree over the inference graph. A "move" consists of:

  • Selecting an edge within the spanning tree.
  • Modifying its relative transformation (the "label").
  • Propagating this change through the tree to maintain global consistency.

Computational Efficiency

To make this approach feasible, the authors introduce label-preserving transformations. This technique allows the algorithm to update only the affected portions of the map rather than recomputing the entire history. This optimization reduces the complexity to approximately $O(n^2)$ for $n$ time steps, making it a viable alternative for batch processing.

Experimental Evaluation

The authors evaluated MCMC-SLAM against EKF-SLAM and FastSLAM 2.0 using simulated benchmarks. A particularly challenging "Large" problem was used, featuring a robot following a circular path through a grid of landmarks, necessitating a massive loop closure.

EKF-SLAM trajectory drift

Key Results and Insights

The experiments revealed a stark contrast in performance between the iterative MCMC approach and traditional filters:

  • Superior Accuracy: In the large-scale simulation, MCMC-SLAM (with 100 proposals) achieved a landmark error of 18.33, whereas FastSLAM 2.0 struggled with an error of 29.46, even when using 10,000 particles.
  • Robust Loop Closure: Qualitatively, MCMC-SLAM produced "tighter" and more accurate maps. While EKF and FastSLAM exhibited drifted trajectories and blurred landmark clusters after completing a loop, MCMC-SLAM successfully "snapped" the map into a precise state.
  • Provable Consistency: Unlike particle filters, which can lose the true path permanently, MCMC is guaranteed to converge to the true posterior distribution given sufficient samples.
MCMC-SLAM accuracy

Conclusion and Future Work

MCMC-SLAM provides the first provably consistent solution for SLAM under general models. While its computational cost is higher than EKF—taking significantly longer to process the same data—it offers a level of reliability and accuracy that traditional filters cannot match in non-Gaussian or high-uncertainty environments.

Future research directions include:

  • Hybrid Approaches: Combining MCMC with particle filters to leverage the speed of filters for local updates and the robustness of MCMC for global loop closures.
  • Adaptive Sampling: Focusing MCMC moves on high-uncertainty regions of the graph to improve convergence speed.
  • Online Implementation: Optimizing the algorithm for real-time performance in long-duration missions.

Summary updated

Abstract

A Markov-Chain Monte Carlo based algorithm is provided to solve the simultaneous localization and mapping (SLAM) problem with general dynamical and observation models under open-loop control and pr...
BibTeX
@inproceedings{torma2010markov,
  author = {Péter Torma and András György and Csaba Szepesvári},
  title = {{A Markov-Chain Monte Carlo Approach to Simultaneous Localization and Mapping.}},
  booktitle = {AISTATS},
  year = {2010},
  url = {https://openreview.net/forum?id=_snB_L5PVjkj},
}
Figure