Doctoral Thesis: Certifiably Correct SLAM

SHARE:

Event Speaker: 

David M. Rosen

Event Location: 

32-G449 (Kiva)

Event Date/Time: 

Friday, August 26, 2016 - 9:30am

Abstract:
 
The ability to construct an accurate model of the environment is an essential capability for mobile autonomous systems, enabling such fundamental functions as planning, navigation, and manipulation. However, the general form of this problem, simultaneous localization and mapping (SLAM), is typically formulated as a maximum-likelihood estimation (MLE) that requires solving a nonconvex nonlinear program, which is computationally hard.  Current state-of-the-art SLAM algorithms address this difficulty by applying fast *local* optimization methods to compute a critical point of the MLE.  While this approach has enabled significant advances in SLAM as a practical technology by admitting the development of fast and scalable estimation methods, it provides *no guarantees* on the quality of the recovered estimates.  This lack of reliability in existing SLAM algorithms in turn presents a serious barrier to the development of robust autonomous systems generally.

Motivated by these considerations, this thesis addresses the problem of developing algorithms for SLAM that preserve the computational speed of existing state-of-the-art techniques while additionally providing *explicit assurances* on the quality of the recovered estimates.  In this defense talk, I will highlight two such contributions for the canonical problem of pose-graph SLAM.

The first contribution addresses the lack of a priori performance guarantees when applying local optimization methods to the nonconvex SLAM MLE by supplying a post-hoc verification method for *computationally certifying* the correctness of a recovered estimate.  The crux of our approach is the development of a (convex) semidefinite relaxation of the SLAM MLE that is frequently *exact* in the low to moderate measurement noise regime.  We show that when exactness holds, it is straightforward to construct an optimal solution lambda* for this relaxation from an optimal solution x* of the SLAM problem; the dual solution lambda* (whose optimality can be verified directly post hoc) then serves as a *certificate of optimality* for the solution x* from which it was constructed.  Extensive evaluation on a variety of simulated and real-world pose-graph SLAM datasets shows that this verification method succeeds in certifying optimal solutions across a broad spectrum of operating conditions, including those typically encountered in application.

Our second contribution is the development of a pose-graph SLAM inference algorithm that employs a fast purpose-built optimization method to *directly solve* the aforementioned semidefinite relaxation, and thereby recover a *certifiably globally optimal* solution of the SLAM MLE whenever exactness holds.  As in the case of our verification technique, empirical evaluation on a variety of simulated and real-world datasets shows that our algorithm is capable of recovering globally optimal pose-graph SLAM solutions across a broad spectrum of operating conditions (including those typically encountered in application), and does so at a computational cost that scales comparably with that of the fast Newton-based local search techniques that form the basis of current state-of-the-art SLAM algorithms.

Thesis committee: John Leonard (Chair), Leslie Kaelbling, and Tomas Lozano-Perez