Variable reordering strategies for SLAM

State of the art methods for state estimation and perception make use of least-squares optimization methods to perform efficient inference on noisy sensor data. Much of this efficiency is achieved by using sparse matrix factorization methods. The sparsity structure of the underlying matrix factorization which makes these optimization methods tractable is highly dependent on the choice of variable reordering; but there has been no systematic evaluation of reordering methods in the SLAM community. In this paper we evaluate the performance of various reordering techniques on benchmark SLAM data sets and provide definitive recommendations based on our results. We also compare these state of the art algorithms against our simple and easy to implement algorithm which achieves comparable performance. Finally, we provide empirical evidence that few gains remain with respect to variants of minimum degree ordering.

Authors

• Pratik Agarwal
• Edwin Olson

Keywords

• Simultaneous localization and mapping
• Sparse matrices
• Equations
• Matrix decomposition
• Jacobian matrices
• Approximation methods
• Reordering Of The Variables
• Reordering Strategy
• Sparsity
• Matrix Factorization
• Sparse Matrix
• Minimum Degree
• Minimum Order
• Variables In Order
• Standard Datasets
• Degree Of Approximation
• Cholesky Decomposition
• Graph Partitioning
• Permutation Matrix
• Loop Closure
• Normal Equations
• QR Decomposition
• World Datasets
• Exact Degree