Nesterov Accelerated ADMM for Distributed Pose Graph Optimization in SLAM problems

Nesterov Accelerated ADMM for Distributed Pose Graph Optimization in SLAM problems

Bosland, Liam (TU Delft Mechanical, Maritime and Materials Engineering; TU Delft Delft Center for Systems and Control)

Keviczky, T. (mentor)
Kok, M. (graduation committee)
Kooij, J.F.P. (graduation committee)

Delft University of Technology

Mechanical Engineering | Systems and Control

2021-02-22

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.

SLAM
pose graph
distributed optimization
Nesterov
ADMM

http://resolver.tudelft.nl/uuid:9a389ff4-94da-4d37-8c9b-80843916b8ff

Student theses

master thesis

© 2021 Liam Bosland