Abstract
The Metropolis-Hastings (MH) algorithm is a flexible method to generate samples from a target distribution, a key problem in probabilistic inference. In this paper, we propose a variation of the MH algorithm that utilizes group transformations as proposal moves. By exploiting the natural symmetries inherent in complex problems—specifically in Simultaneous Localization and Mapping (SLAM)—we develop a sampler capable of navigating distant, high-probability regions of the state space that traditional random-walk samplers often fail to reach.
Introduction: The Challenge of Multi-modality
Standard Markov Chain Monte Carlo (MCMC) algorithms, such as the textbook Metropolis-Hastings, frequently struggle when faced with complex, multi-modal distributions. When high-probability peaks are separated by wide regions of low probability, a standard sampler taking small, local steps can become trapped in a single mode indefinitely.
While manual reparameterization (e.g., switching to polar coordinates) can sometimes exploit known symmetries, it is often mathematically cumbersome and highly problem-specific. Furthermore, standard MH theory requires measures to have densities with respect to a common reference, which can complicate techniques like Gibbs sampling in continuous spaces. This work provides a rigorous mathematical framework for using group transformations to navigate these spaces efficiently without requiring manual coordinate transformations.
Methodology: Group Transformations and Symmetry
The proposed framework leverages topological group theory to generalize the MH algorithm. Instead of the traditional additive noise proposal ($x' = x + \epsilon$), the algorithm proposes a transformation $g$ from a group $G$ (such as rotations or translations) and applies it to the current state ($w' = gw$).
Key technical contributions include:
- Modified Acceptance Probability: A new formula for the MH acceptance ratio is derived using Haar measures and modular characters. This ensures the sampler maintains detailed balance even when transformations alter the "volume" of the state space.
- Mixtures of Group Moves: The framework allows for combining multiple groups (e.g., robot movement vs. landmark shifts) into a single, coherent sampling algorithm.
- Symmetry Exploitation: If a proposal group aligns with a symmetry of a factor in the target distribution, that factor cancels out of the acceptance ratio. This enables large, "invisible" moves that significantly accelerate convergence.
Experimental Evaluation: Range-Only SLAM
The authors evaluated the "MCMC-SLAM" algorithm using two real-world robotics datasets: Plaza 1 (a 1.9 km trajectory with 3,529 range observations) and Plaza 2 (a 1.3 km trajectory with 1,816 observations).
Range-only SLAM is particularly challenging because distance measurements define circular constraints around beacons, leading to highly non-Gaussian and multi-modal uncertainty. The inherent symmetry of the problem—where rotating the entire map and trajectory preserves sensor readings—makes it an ideal candidate for group-move updates.
Results and Performance
The MCMC-SLAM approach was compared against Spectral SLAM, a leading non-iterative method.
As shown in the results, MCMC-SLAM achieved significantly lower Root Mean Square (RMS) errors. In the Plaza 1 dataset, MCMC reduced the error to approximately 0.32m, compared to 0.79m for Spectral SLAM. Beyond accuracy, the MCMC approach demonstrated superior robustness to missing observations and provided a full posterior distribution rather than a single point estimate.
Conclusion
By providing a rigorous theoretical foundation for group-move updates, this work enables the construction of more efficient samplers for symmetric problems. While MCMC is computationally more intensive than one-shot spectral methods, the gains in accuracy and the ability to represent full uncertainty make it a powerful tool for complex inference tasks like range-only SLAM. Future work will focus on automating the discovery of these symmetries and addressing biases in complex noise models.
Summary updated