Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions
Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions
复制标题
DOI：
10.1109/iros.2015.7353364
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
L. Carlone;David M. Rosen;G. Calafiore;J. Leonard;F. Dellaert
中科院分区：
文献类型：
--
作者：
L. Carlone;David M. Rosen;G. Calafiore;J. Leonard;F. Dellaert
用于同时定位和映射（SLAM）的现有技术采用迭代非线性优化方法来计算机器人姿态的估计。虽然这些技术在实践中通常工作得很好，但它们不能保证估计的质量。本文表明，拉格朗日对偶是一个强大的工具，以评估给定的候选解决方案的质量。我们的贡献是三方面的。首先，我们讨论了一个修订制定的SLAM推理问题。我们表明，这种提法是概率接地，并具有导致二次目标的优化问题的优势。第二个贡献是相应的拉格朗日对偶问题的推导。SLAM对偶问题是一个（凸）半定规划，可以通过现成的求解器可靠地和全局地求解。第三个贡献是讨论了原SLAM问题与其对偶问题之间的关系。我们表明，从对偶问题，人们可以评估质量（即，次优性间隙），并最终提供最优性证书。此外，当对偶间隙为零时，可以从对偶问题计算保证的最优SLAM解，从而避开非凸优化。我们提出了广泛的（真实的和模拟）实验支持我们的主张，并讨论了实际的相关性和开放的问题。
State-of-the-art techniques for simultaneous localization and mapping (SLAM) employ iterative nonlinear optimization methods to compute an estimate for robot poses. While these techniques often work well in practice, they do not provide guarantees on the quality of the estimate. This paper shows that Lagrangian duality is a powerful tool to assess the quality of a given candidate solution. Our contribution is threefold. First, we discuss a revised formulation of the SLAM inference problem. We show that this formulation is probabilistically grounded and has the advantage of leading to an optimization problem with quadratic objective. The second contribution is the derivation of the corresponding Lagrangian dual problem. The SLAM dual problem is a (convex) semidefinite program, which can be solved reliably and globally by off-the-shelf solvers. The third contribution is to discuss the relation between the original SLAM problem and its dual. We show that from the dual problem, one can evaluate the quality (i.e., the suboptimality gap) of a candidate SLAM solution, and ultimately provide a certificate of optimality. Moreover, when the duality gap is zero, one can compute a guaranteed optimal SLAM solution from the dual problem, circumventing non-convex optimization. We present extensive (real and simulated) experiments supporting our claims and discuss practical relevance and open problems.