Abstract
Simultaneous localization and mapping (SLAM) is the problem of constructing a global model of an environment from local observations of it; this perceptual capability is essential for mobile robots, supporting such core functions as planning, navigation, and control. However, the SLAM problem is typically formalized as a high-dimensional nonconvex maximum likelihood estimation, with many local minima that can entrap the smooth optimization methods commonly applied to solve it. The result is that standard SLAM approaches can easily compute substantially wrong estimates, even if the problem to which they are applied is well-posed.
In this talk, we describe an algorithm that is capable of efficiently recovering certifiably globally optimal SLAM solutions in many practical settings. Our approach is based upon a (convex) semidefinite relaxation of the SLAM problem whose minimizer we prove provides an exact (globally optimal) SLAM solution so long as the noise on the available measurements is not too large; moreover, whenever this situation obtains, it is possible to verify this fact a posteriori, thereby certifying the correctness of the recovered estimate. We exploit the geometric and algebraic structure of this SLAM relaxation to develop a specialized semidefinite optimization method for solving large-scale instances efficiently. Our overall algorithm, SE-Sync, thus preserves the speed of prior techniques while enabling the recovery of certifiably globally optimal SLAM solutions in practice.
