Lagrangian Duality in Complex Pose Graph Optimization

Giuseppe C. Calafiore (), Luca Carlone () and Frank Dellaert ()
Additional contact information
Giuseppe C. Calafiore: Politecnico di Torino
Luca Carlone: Massachusetts Institute of Technology
Frank Dellaert: Georgia Institute of Technology

A chapter in Optimization and Its Applications in Control and Data Sciences, 2016, pp 139-184 from Springer

Abstract: Abstract Pose Graph Optimization (PGO) is the problem of estimating a set of poses from pairwise relative measurements. PGO is a nonconvex problem, and currently no known technique can guarantee the efficient computation of a global optimal solution. In this paper, we show that Lagrangian duality allows computing a globally optimal solution, under certain conditions that are satisfied in many practical cases. Our first contribution is to frame the PGO problem in the complex domain. This makes analysis easier and allows drawing connections with the recent literature on unit gain graphs. Exploiting this connection we prove nontrival results about the spectrum of the matrix underlying the problem. The second contribution is to formulate and analyze the properties of the Lagrangian dual problem in the complex domain. The dual problem is a semidefinite program (SDP). Our analysis shows that the duality gap is connected to the number of eigenvalues of the penalized pose graph matrix, which arises from the solution of the SDP. We prove that if this matrix has a single eigenvalue in zero, then (1) the duality gap is zero, (2) the primal PGO problem has a unique solution, and (3) the primal solution can be computed by scaling an eigenvector of the penalized pose graph matrix. The third contribution is algorithmic: we exploit the dual problem and propose an algorithm that computes a guaranteed optimal solution for PGO when the penalized pose graph matrix satisfies the Single Zero Eigenvalue Property (SZEP). We also propose a variant that deals with the case in which the SZEP is not satisfied. This variant, while possibly suboptimal, provides a very good estimate for PGO in practice. The fourth contribution is a numerical analysis. Empirical evidence shows that in the vast majority of cases (100 % of the tests under noise regimes of practical robotics applications) the penalized pose graph matrix does satisfy the SZEP, hence our approach allows computing the global optimal solution. Finally, we report simple counterexamples in which the duality gap is nonzero, and discuss open problems.

Keywords: Maximum likelihood estimation; Mobile robots; Motion estimation; Position measurement; Rotation measurement; Simultaneous localization and mapping; Duality (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-42056-1_5

Ordering information: This item can be ordered from
http://www.springer.com/9783319420561

DOI: 10.1007/978-3-319-42056-1_5

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().