This paper presents the first certifiably correct algorithm for distributed 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 Riemannian block coordinate descent (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)第一个经证实正确无误的分布式容貌优化(PGO)算法(PGO),这是现代合作同时进行本地化和绘图(CSLAM)和相机网络本地化(CNL)系统的主干线。我们的方法基于一种稀有的半无限放松,我们证明在中度测量噪音(与最新中央集权方法享有的保障相匹配)下,提供了全球最佳的PGO解决方案,但可以使用低级里曼尼的Staircase框架进行分配优化。为了在分布式环境中实施里曼尼史塔卡,我们开发了里曼尼尼亚区块协调下降(RBCD),这是(当地)最大限度地减少里曼尼马尼亚区成品产品功能的新方法。我们还提出了第一个分布式解决方案核查和套装套装方法,以证明通过RBCD回收的关键点的全球最佳最佳性,并(如有必要)从亚优度临界点下降。我们的方法的所有组成部分本质上是分散的:它们只需要当地通信,提供隐私保护,并且很容易平行地平行地平行地平行地平行地平行地对中和现实世界的替代的代熔化解决方案进行广泛的评价。