Efficient and Guaranteed Planar Pose Graph optimization Using the Complex Number Representation

In this paper, we present CPL-Sync, a certifiably correct algorithm to solve planar pose graph optimization (PGO) using the complex number representation. We formulate planar PGO as the maximum likelihood estimation (MLE) on the product of unit complex numbers, and relax this nonconvex quadratic complex optimization problem to complex semidefinite programming (SDP). Furthermore, we simplify the corresponding semidefinite programming to Riemannian staircase optimization (RSO) on complex oblique manifolds that can be solved with the Riemannian trust region (RTR) method. In addition, we prove that the SDP relaxation and RSO simplification are tight as long as the noise magnitude is below a certain threshold. The efficacy of this work is validated through comparisons with existing methods as well as applications on planar PGO in simultaneous localization and mapping (SLAM), which indicates that the proposed algorithm is capable of solving planar PGO certifiably, and is more efficient in numerical computation and more robust to measurement noises than existing state-of-the-art methods. The C++ code for CPL-Sync is available at https://github.com/fantaosha/CPL-Sync.

Authors

• Taosha Fan
• Hanlin Wang
• Michael Rubenstein
• Todd D. Murphey

Keywords

• Manifolds
• Maximum likelihood estimation
• Simultaneous localization and mapping
• Semidefinite programming
• Noise
• Urban areas
• Computational efficiency
• Noise measurement
• Optimization
• Intelligent robots
• Complex Numbers
• Pose Graph Optimization
• Number Of Products
• Measurement Noise
• Complex Representations
• Magnitude Of Noise
• C++ Code
• Trust Region Method
• Results Of Experiments
• Rest Of The Paper
• Real Numbers
• Relative Measure
• Global Optimization
• High Noise
• Singular Value Decomposition
• Real Matrices
• Quadratic Programming
• Semidefinite Relaxation
• Matrix Representation
• Noisy Measurements
• Relaxing Solution
• Complex Vector
• Algebraic Structure
• Interior Point Method
• Indicator Matrix
• Positive Semidefinite Matrix
• Large Benchmark