A Spectral Learning Approach to Range-Only SLAM

Byron Boots, Geoffrey J. Gordon

Abstract

We present a novel spectral learning algorithm for simultaneous localization and mapping (SLAM) from range data with known correspondences. This algorithm is an instance of a general spectral system identification framework, from which it inherits several desirable properties, including statistical consistency and no local optima. Compared with popular batch optimization or multiple-hypothesis tracking (MHT) methods for range-only SLAM, our spectral approach offers guaranteed low computational requirements and good tracking performance. Compared with popular extended Kalman filter (EKF) or extended information filter (EIF) approaches, and many MHT ones, our approach does not need to linearize a transition or measurement model; such linearizations can cause severe errors in EKFs and EIFs, and to a lesser extent MHT, particularly for the highly non-Gaussian posteriors encountered in range-only SLAM. We provide a theoretical analysis of our method, including finite-sample error bounds. Finally, we demonstrate on a real-world robotic SLAM problem that our algorithm is not only theoretically justified, but works well in practice: in a comparison of multiple methods, the lowest errors come from a combination of our algorithm with batch optimization, but our method alone produces nearly as good a result at far lower computational cost.

Introduction

Simultaneous Localization and Mapping (SLAM) is often described as the "chicken and egg" problem of robotics: a robot needs a map to know where it is, but it needs to know its location to build an accurate map. In Range-Only SLAM, the robot only receives distance measurements to fixed landmarks (such as radio beacons), without any bearing or angle information.

This task is exceptionally difficult because the relationship between a robot's position and a landmark is highly non-linear. Standard tools like the Extended Kalman Filter (EKF) often fail because they attempt to linearize this geometry, leading to catastrophic errors. While batch optimization methods can find more accurate solutions, they are computationally expensive and frequently get stuck in "local optima"—mathematical dead-ends that do not represent the true physical environment.

The Spectral Approach

The key insight of this research is that while the distance $d$ is non-linear, the squared distance $d^2$ can be rewritten as a linear combination of features in a higher-dimensional space. By expanding the state vector—for example, including terms like $x^2 + y^2$ alongside the standard $(x, y)$ coordinates—the non-linear range geometry is transformed into a linear algebra problem.

Specifically, the authors construct a matrix $Y$ of squared ranges that can be factored into $Y = CX$, where $C$ contains landmark positions and $X$ contains robot poses.

Equation (7) defining the matrix of squared ranges Y, which serves as the basis for the spectral factorization.

By using Singular Value Decomposition (SVD) to factor this matrix, the algorithm identifies a global solution that avoids the local minima common in optimization heuristics. Because SVD is a well-understood global operation, the method is "statistically consistent," meaning the estimate is guaranteed to converge to the true map as more data is collected.

Experimental Results

The algorithm was evaluated using both synthetic data and real-world datasets (Plaza 1 and Plaza 2) collected from an autonomous lawnmower equipped with radio ranging nodes. These real-world scenarios are challenging due to sparse data and significant odometry errors.

Qualitative and quantitative results: (A) shows the estimated path and landmarks closely tracking the ground truth; (B) demonstrates the statistical consistency and convergence of the measurement model.

Key Findings:

  • Massive Speedup: On the Plaza 1 dataset, the spectral approach took roughly 0.7 seconds, compared to over 2.5 hours (9,264 seconds) for traditional batch optimization. This represents a 3-4 order of magnitude improvement in efficiency.
  • Superior Accuracy: The spectral method significantly outperformed EKF-based methods (like ROP-EKF and FastSLAM).
  • Hybrid Performance: The authors found that using the spectral method to provide an initial estimate for a traditional batch optimizer yielded the lowest Root Mean Squared Error (RMSE) across all tests (e.g., 0.69m on Plaza 1).

Limitations and Future Work

While powerful, the current spectral method requires a complete range matrix. In practice, sensors often miss readings, necessitating interpolation or more robust "matrix completion" techniques. Additionally, the algorithm currently assumes known correspondences (the robot knows which landmark it is talking to). Future work will focus on extending the framework to handle unknown data associations and implementing "Online SVD" algorithms to enable real-time processing as the robot moves.

Summary updated

Abstract

We present a novel spectral learning algorithm for simultaneous localization and mapping (SLAM) from range data with known correspondences. This algorithm is an instance of a general spectral system identification framework, from which it inherits several desirable properties, including statistical consistency and no local optima. Compared with popular batch optimization or multiple-hypothesis tracking (MHT) methods for range-only SLAM, our spectral approach offers guaranteed low computational requirements and good tracking performance. Compared with popular extended Kalman filter (EKF) or extended information filter (EIF) approaches, and many MHT ones, our approach does not need to linearize a transition or measurement model; such linearizations can cause severe errors in EKFs and EIFs, and to a lesser extent MHT, particularly for the highly non-Gaussian posteriors encountered in range-only SLAM. We provide a theoretical analysis of our method, including finite-sample error bounds. Finally, we demonstrate on a real-world robotic SLAM problem that our algorithm is not only theoretically justified, but works well in practice: in a comparison of multiple methods, the lowest errors come from a combination of our algorithm with batch optimization, but our method alone produces nearly as good a result at far lower computational cost.
BibTeX
@inproceedings{boots2013spectral,
  author = {Byron Boots and Geoffrey J. Gordon},
  title = {{A Spectral Learning Approach to Range-Only SLAM}},
  booktitle = {International Conference on Machine Learning},
  year = {2013},
  url = {https://openreview.net/forum?id=S1-ozh-uWH},
}
Figure