SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group

By David M. Rosen, Luca Carlone, Afonso S. Bandeira, John J. Leonard. Int. J. Robotics Res., 2016

399 citations recorded by the source corpus.

Many important geometric estimation problems naturally take the form of synchronization over the special Euclidean group: estimate the values of a set of unknown group elements x 1 , … , x n ∈ SE ( d ) given noisy measurements of a subset of their pairwise relative transforms x i − 1 x j . Examples of this class include the foundational problems of pose-graph simultaneous localization and mapping (SLAM) (in robotics), camera motion estimation (in computer vision), and sensor network localization (in distributed sensing), among others. This inference problem is typically formulated as a non-convex maximum-likelihood estimation that is computationally hard to solve in general. Nevertheless, in this paper we present an algorithm that is able to efficiently recover certifiably globally optimal solutions of the special Euclidean synchronization problem in a non-adversarial noise regime. The crux of our approach is the development of a semidefinite relaxation of the maximum-likelihood estimation (MLE) whose minimizer provides an exact maximum-likelihood estimate so long as the magnitude of the noise corrupting the available measurements falls below a certain critical threshold; furthermore, whenever exactness obtains, it is possible to verify this fact a posteriori, thereby certifying the optimality of the recovered estimate. We develop a specialized optimization scheme for solving large-scale instances of this semidefinite relaxation by exploiting its low-rank, geometric, and graph-theoretic structure to reduce it to an equivalent optimization problem defined on a low-dimensional Riemannian manifold, and then design a Riemannian truncated-Newton trust-region method to solve this reduction efficiently. Finally, we combine this fast optimization approach with a simple rounding procedure to produce our algorithm, SE-Sync. Experimental evaluation on a variety of simulated and real-world pose-graph SLAM datasets shows that SE-Sync is capable of recovering certifiably globally optimal solutions when the available measurements are corrupted by noise up to an order of magnitude greater than that typically encountered in robotics and computer vision applications, and does so significantly faster than the Gauss–Newton-based approach that forms the basis of current state-of-the-art techniques.

Subfields: Aerospace Engineering, Artificial Intelligence, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/9b06555e79a7e9b3295fc288b3056c1eb7ab77ee

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Kimera-Multi: Robust, Distributed, Dense Metric-Semantic SLAM for Multi-Robot Systems (2021, background): “While in general GNC does not require an initial guess [15], it has been observed that global solvers for 3D SLAM (e.g., SESync [83]) become too slow in the presence of outliers [74].”
Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection (2019, methodology): “Specifically, while closedform solutions are rare [3], Semidefinite Programming (SDP) and Sums-of-Squares (SOS) [4] relaxations have been recently shown to be a powerful tool to obtain certifiably optimal solutions to relevant instances of problem (1), ranging from pose graph optimization [5], [6], ”
Deep Closest Point: Learning Representations for Point Cloud Registration (2019, methodology): “Other methods attempt to identify global optima using Riemannian optimization [36], convex relaxation [27], and mixed-integer programming [21].”
Kimera: From SLAM to spatial perception with 3D dynamic scene graphs (2021, methodology): “With this reparametrization, we are left with a pose graph optimization problem akin to those found in the literature (Cadena et al., 2016; Rosen et al., 2018):”
TEASER: Fast and Certifiable Point Cloud Registration (2020, background): “, an algorithm that attempts to solve an intractable problem and provides checkable conditions on whether it succeeded [21], [22], [23], [24], [25], [26].”
PointNetLK: Robust & Efficient Point Cloud Registration Using PointNet (2019, methodology): “More recently convex relaxation has been used for global pose estimation using Riemannian optimization [30], semidefinite programming [13, 20] and mixed integer programming [14].”
PRNet: Self-Supervised Learning for Partial-to-Partial Registration (2019, methodology): “Another trend is to improve the optimization: [13] applies Levenberg—Marquardt to the ICP objective, while global methods seek a solution using branch-and-bound [14], Riemannian optimization [15], convex relaxation [16], mixed-integer programming [17], and semideﬁnite programming [18].”