Discrete-continuous optimization for robot perception via semidefinite relaxation

In this thesis, we propose polynomial-time algorithms based on semidefinite programming (SDP) relaxation to find approximate solutions to nonconvex problems arising in two fields of robot perception, semantic segmentation and robust pose graph optimization. Compared with other inference techniques, SDP relaxation have shown to provide accurate estimate with provable sub-optimality guarantees without relying on an initial guess for optimization. On the downside, general SDP solvers scale poorly in terms of time and memory with the problem size. However, for problems admitting low-rank solutions, low-rank solvers and smooth Riemannian optimization can speed up computation significantly. Along this direction, the first contribution is two fast and scalable techniques for inference in Markov Random Fields (MRFs). MRFs are a popular model for several pattern recognition and reconstruction problems in robotics and computer vision, but are intractable to solve in general. The first technique, named Dual Ascent Riemannian Staircase (DARS), is able to solve large problem instances in seconds. The second technique, named Fast Unconstrained SEmidefinite Solver (FUSES), utilizes a novel SDP relaxation and is able to solve similar problems in milliseconds. We benchmark both techniques in multi-class image segmentation problems against state-of-the-art MRF solvers and show that both techniques achieves comparable accuracy with the best existing solver while FUSES is much faster. Building on top of MRF models, our second contribution is a Discrete-Continuous Graphical Model (DC-GM) that combines discrete binary labeling with standard least-square pose graph optimization to identify and reject spurious measurements for Simultaneous Localization and Mapping (SLAM). We then perform inference in the DC-GM via semidefinite relaxation. Experiment results on synthetic and real benchmarking datasets show that the proposed approach compares favorably with state-of-the-art methods.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Aeronautics and Astronautics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Hu, Siyi,S.M.Massachusetts Institute of Technology.

Advisor dc:contributor.advisor

• Luca Carlone.

• Aeronautics and Astronautics.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/122515

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/122515