Tian Yulun, Khosoussi Kasra, Rosen David M, How Jonathan P
Laboratory for Information and Decision Systems (LIDS), Massachusetts Institute of Technology, Cambridge, MA.
IEEE Trans Robot. 2021 Dec;37(6):2137-2156. doi: 10.1109/tro.2021.3072346. Epub 2021 May 7.
This paper presents the first algorithm for pose-graph optimization (PGO), the backbone of modern collaborative simultaneous localization and mapping (CSLAM) and camera network localization (CNL) systems. Our method is based upon a sparse semidefinite relaxation that we prove provides globally-optimal PGO solutions under moderate measurement noise (matching the guarantees enjoyed by state-of-the-art centralized methods), but is amenable to distributed optimization using the low-rank Riemannian Staircase framework. To implement the Riemannian Staircase in the distributed setting, we develop (RBCD), a novel method for (locally) minimizing a function over a product of Riemannian manifolds. We also propose the first distributed solution verification and saddle escape methods to certify the global optimality of critical points recovered via RBCD, and to descend from suboptimal critical points (if necessary). All components of our approach are inherently decentralized: they require only local communication, provide privacy protection, and are easily parallelizable. Extensive evaluations on synthetic and real-world datasets demonstrate that the proposed method correctly recovers globally optimal solutions under moderate noise, and outperforms alternative distributed techniques in terms of solution precision and convergence speed.
本文提出了首个用于位姿图优化（PGO）的算法，位姿图优化是现代协同同步定位与建图（CSLAM）及相机网络定位（CNL）系统的核心。我们的方法基于一种稀疏半定松弛，我们证明在适度测量噪声下该方法能提供全局最优的PGO解（与最先进的集中式方法所具有的保证相匹配），并且适用于使用低秩黎曼阶梯框架进行分布式优化。为了在分布式环境中实现黎曼阶梯，我们开发了黎曼块坐标下降法（RBCD），这是一种在黎曼流形乘积上（局部）最小化函数的新方法。我们还提出了首个分布式解验证和鞍点逃逸方法，以验证通过RBCD恢复的临界点的全局最优性，并（如有必要）从次优临界点下降。我们方法的所有组件本质上都是去中心化的：它们只需要局部通信，提供隐私保护，并且易于并行化。在合成数据集和真实世界数据集上的广泛评估表明，所提出的方法在适度噪声下能正确恢复全局最优解，并且在解精度和收敛速度方面优于其他分布式技术。
