Discrete-continuous optimization for robot perception via semidefinite relaxation
Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/122515 |
| _version_ | 1826197301965619200 |
|---|---|
| author | Hu, Siyi,S.M.Massachusetts Institute of Technology. |
| author2 | Luca Carlone. |
| author_facet | Luca Carlone. Hu, Siyi,S.M.Massachusetts Institute of Technology. |
| author_sort | Hu, Siyi,S.M.Massachusetts Institute of Technology. |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019 |
| first_indexed | 2024-09-23T10:45:38Z |
| format | Thesis |
| id | mit-1721.1/122515 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:45:38Z |
| publishDate | 2019 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1225152019-11-22T03:27:01Z Discrete-continuous optimization for robot perception via semidefinite relaxation Hu, Siyi,S.M.Massachusetts Institute of Technology. Luca Carlone. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Aeronautics and Astronautics. Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019 Cataloged from PDF version of thesis. Includes bibliographical references (pages 85-90). 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. by Siyi Hu. S.M. S.M. Massachusetts Institute of Technology, Department of Aeronautics and Astronautics 2019-10-11T21:59:49Z 2019-10-11T21:59:49Z 2019 2019 Thesis https://hdl.handle.net/1721.1/122515 1121262889 eng 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. http://dspace.mit.edu/handle/1721.1/7582 90 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Aeronautics and Astronautics. Hu, Siyi,S.M.Massachusetts Institute of Technology. Discrete-continuous optimization for robot perception via semidefinite relaxation |
| title | Discrete-continuous optimization for robot perception via semidefinite relaxation |
| title_full | Discrete-continuous optimization for robot perception via semidefinite relaxation |
| title_fullStr | Discrete-continuous optimization for robot perception via semidefinite relaxation |
| title_full_unstemmed | Discrete-continuous optimization for robot perception via semidefinite relaxation |
| title_short | Discrete-continuous optimization for robot perception via semidefinite relaxation |
| title_sort | discrete continuous optimization for robot perception via semidefinite relaxation |
| topic | Aeronautics and Astronautics. |
| url | https://hdl.handle.net/1721.1/122515 |
| work_keys_str_mv | AT husiyismmassachusettsinstituteoftechnology discretecontinuousoptimizationforrobotperceptionviasemidefiniterelaxation |