Sparser Relative Bundle Adjustment (SRBA): Constant-time maintenance and local optimization of arbitrarily large maps

In this paper we defend the superior scalability of the Relative Bundle Adjustment (RBA) framework for tackling with the SLAM problem. Although such a statement was already done with the introduction of the sliding window (SW) solution to RBA [16], we claim that the map extension that can be maintained locally consistent for some fixed computational cost critically depends on the specific pattern in which new keyframes are connected to previous ones. By rethinking from scratch what we call loop closures in relative coordinates we will show the unexploited flexibility of the RBA framework, which allows us a continuum of strategies from pure relative BA to hybrid submapping with local maps. In this work we derive a systematic way of constructing the problem graph which lies close to submapping and which generates graphs that can be solved more efficiently than those built as previously reported in the literature. As a necessary tool we also present an algorithm for incrementally updating all the spanning-trees demanded by any efficient solution to RBA. Under weak assumptions on the map, and implemented on carefully designed data structures, it is demonstrated to run in bounded time, no matter how large the map becomes. We also present experiments with a synthetic dataset of 55K keyframes in a world of 4.3M landmarks. Our C++ implementation has been released as open source.

I. Introduction

Most recent proposals that deal with the simultaneous estimation of a robot path and the unknown location of all observed landmarks use a graph model where nodes are the unknowns (poses and landmarks) and edges represent constraints (e.g. observations, odometry). Robot poses are then typically called keyframes (KFs) when working with imaging sensors. Under the assumption of all observation errors being Gaussians it is easily demonstrated [7] that a least-squares minimization of the mismatch between observations and predictions from the estimated model becomes the maximum likelihood estimator for the problem. Typically, sparse algebra approaches are employed to exploit the inherent sparsity of the systems of linear equations that appear during this process. In the computer vision community such methods are dubbed Bundle Adjustment (BA) [19], while similar methods in mobile robotics, which may estimate only the robot path or both the path and the landmarks, receive the names of Graph-SLAM [9] or view-based SLAM [6].