自動的に強化された半正定値緩和による大域的最適状態推定
Toward Globally Optimal State Estimation Using Automatically Tightened Semidefinite Relaxations
半正定値緩和において、手動で見つけていた冗長制約を自動的に発見し、大域的最適性を達成する手法を提案。
著者: Frederike Dümbgen, Connor Holmes, Ben Agro, Timothy D. Barfoot
分類: cs.RO
原文アブストラクト
In recent years, semidefinite relaxations of common optimization problems in robotics have attracted growing attention due to their ability to provide globally optimal solutions. In many cases, it was shown that specific handcrafted redundant constraints are required to obtain tight relaxations and thus global optimality. These constraints are formulation-dependent and typically identified through a lengthy manual process. Instead, the present paper suggests an automatic method to find a set of sufficient redundant constraints to obtain tightness, if they exist. We first propose an efficient feasibility check to determine if a given set of variables can lead to a tight formulation. Secondly, we show how to scale the method to problems of bigger size. At no point of the process do we have to find redundant constraints manually. We showcase the effectiveness of the approach, in simulation and on real datasets, for range-based localization and stereo-based pose estimation. Finally, we reproduce semidefinite relaxations presented in recent literature and show that our automatic method always finds a smaller set of constraints sufficient for tightness than previously considered.
