Nesterov Accelerated ADMM for Distributed Pose Graph Optimization in SLAM problems

Abstract

A common problem in robotics is the simultaneous localization and mapping (SLAM) problem. Here, a robot needs to create a map of its surroundings while simultaneously localizing itself in this map. An unknown environment is assumed. Traditionally, it has been approached through filtering solutions. This paradigm has shifted to pose graph optimization (PGO). This method scales well with large maps and is fast and accurate. Furthermore, it is especially suited to the distributed SLAM problem as existing distributed optimization methods can be leveraged. One such method is the alternating direction method of multipliers (ADMM), which has been used in distributed PGO. ADMM has a simple implementation and can achieve high accuracies in distributed PGO. A solution of good quality can be acquired in a few iterations with ADMM. However, ADMM is slow to converge to high accuracies. This thesis introduces an algorithm which implements Nesterov acceleration in the ADMM algorithm for distributed PGO in SLAM problems. Such an implementation will be novel. To create the proposed Nesterov accelerated ADMM (N-ADMM) algorithm, the current literature is adapted and extended based on the choices made in this thesis. The main research question is how to make these choices. The proposed N-ADMM algorithm is implemented in C++ and compared with unaccelerated ADMM and the state of the art. N-ADMM has shown better performance in some scenarios. To further research what these scenarios are characterized by, two models are introduced to create new datasets of which the parameters can be controlled. The effects of graph size and bad initial guesses are investigated.