A convex relaxation for approximate global optimization in simultaneous localization and mapping
Open accessThe DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
Abstract
Modern approaches to simultaneous localization and mapping (SLAM) formulate the inference problem as a high-dimensional but sparse nonconvex M-estimation, and then apply general first- or second-order smooth optimization methods to recover a local minimizer of the objective function. The performance of any such approach depends crucially upon initializing the optimization algorithm near a good solution for the inference problem, a condition that is often difficult or impossible to guarantee in practice. To address this limitation, in this paper we present a formulation of the SLAM M-estimation with the property that, by expanding the feasible set of the estimation program, we obtain a convex relaxation whose solution approximates the globally optimal solution of the SLAM inference problem and can be recovered using a smooth optimization method initialized at any feasible point. Our formulation thus provides a means to obtain a high-quality solution to the SLAM problem without requiring high-quality initialization.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
(2006) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/978-0-387-40065-5 · Cited by 9,008
Thrun, S. (2002) · Communications of the ACM · doi:10.1145/504729.504754 · Cited by 7,994 · cited 2×
“In this section we provide a brief review of the pose-and-landmark SLAM inference problem; interested readers are encouraged to consult [1], [9] for a more detailed presentation.”
BackgroundGolub, G. H., & Loan, C. F. V. (1996) · Johns Hopkins University Press eBooks · Cited by 6,027
Vandenberghe, L., & Boyd, S. (1996) · SIAM Review · doi:10.1137/1038003 · Cited by 4,105 · cited 1×
“it can be expressed as the solution set for a linear matrix inequality [10]).”
BackgroundLeast-squares estimation of transformation parameters between two point patterns
Umeyama, S. (1991) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.88573 · Cited by 2,420 · cited 1×
“…procedures of the form (29) have been studied previously, and there exist straightforward and efficient meth-ods to compute the mapping π R ( · ) (based upon the singular value decomposition [15] of ˜ R ) for the special case in which the norm (cid:107)·(cid:107) in (29) is the Frobenius norm [16].”
BackgroundG2o: A general framework for graph optimization
Kummerle, R., Grisetti, G., Strasdat, H., Konolige, K., & Burgard, W. (2011) · 2011 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2011.5979949 · Cited by 1,982 · cited 2×
“[13], [14], among others) will scale gracefully to problem sizes typical of those addressed by stateof-the-art least-squares methods for SLAM [3]–[5].”
BackgroundMethodiSAM2: Incremental smoothing and mapping using the Bayes tree
Kaess, M., Johannsson, H., Roberts, R., Ila, V., Leonard, J. J., & Dellaert, F. (2012) · The International Journal of Robotics Research · doi:10.1177/0278364911430419 · Cited by 1,362
Self-citationGlobally Consistent Range Scan Alignment for Environment Mapping
Lu, F., & Milios, E. (1997) · Autonomous Robots · doi:10.1023/a:1008854305733 · Cited by 1,304
An interior algorithm for nonlinear optimization that combines line search and trust region steps
Waltz, R. A., Morales, J. L., Nocedal, J., & Orban, D. (2006) · Mathematical Programming · doi:10.1007/s10107-004-0560-5 · Cited by 1,057 · cited 2×
“The convex optimization (28) was implemented in MATLAB using the fmincon interior-point method (which is itself an implementation of KNITRO , a high-quality interior-point trust-region method for large-scale nonlinear programming [13], [14]).”
MethodKnitro: An Integrated Package for Nonlinear Optimization
Byrd, R. H., Nocedal, J., & Waltz, R. A. (2006) · Nonconvex Optimization and Its Applications · doi:10.1007/0-387-30065-1_4 · Cited by 979 · cited 2×
“The convex optimization (28) was implemented in MATLAB using the fmincon interior-point method (which is itself an implementation of KNITRO , a high-quality interior-point trust-region method for large-scale nonlinear programming [13], [14]).”
MethodSquare Root SAM: Simultaneous Localization and Mapping via Square Root Information Smoothing
Dellaert, F., & Kaess, M. (2006) · The International Journal of Robotics Research · doi:10.1177/0278364906072768 · Cited by 922
Interior Methods for Nonlinear Optimization
Forsgren, A., Gill, P. E., & Wright, M. H. (2002) · SIAM Review · doi:10.1137/s0036144502414942 · Cited by 699 · cited 1×
“Interior-point methods are a state-of-the-art class of accurate, high-speed techniques for solving large-scale nonlinear programs, and enjoy excellent global convergence and numerical robustness properties [7], [12].”
BackgroundFast iterative alignment of pose graphs with poor initial estimates
Olson, E., Leonard, J., & Teller, S. (2006) · Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006. · doi:10.1109/robot.2006.1642040 · Cited by 427 · cited 2×
“…we evaluate the two approaches on the City problem, which simulates a robot traversing a 2D “grid world”; like the well-known Manhattan world [19], this problem is designed to be challenging for local optimization methods to solve given poor initial estimates (for example, those obtained by…”
MethodSelf-citationOksanen, T., Tiusanen, J., & Kostamo, J. (2009) · Precision agriculture '09 · doi:10.3920/9789086866649_102 · Cited by 414
Carlone, L., & Censi, A. (2014) · IEEE Transactions on Robotics · doi:10.1109/tro.2013.2291626 · Cited by 79 · cited 1×
“One notable example is [20], which guarantees the recovery of the globally optimal orientation estimates in the 2D pose-graph SLAM problem with high (user-selectable) probability; however, this approach depends upon the identification SO (2) ∼ = R / 2 π Z , and so appears to be limited to the…”
BackgroundOnline constraint network optimization for efficient maximum likelihood map learning
Grisetti, G., Lodi Rizzini, D., Stachniss, C., Olson, E., & Burgard, W. (2008) · 2008 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2008.4543481 · Cited by 69 · cited 4×
“Consequently, SLAM has been the focus of a sustained research effort over the previous three decades, and there now exist a variety of mature algorithms and software libraries to solve this problem in practice (cf. [2]–[5]).”
BackgroundMethodInfluentialRISE: An Incremental Trust-Region Method for Robust Online Sparse Least-Squares Estimation
Rosen, D. M., Kaess, M., & Leonard, J. J. (2014) · IEEE Transactions on Robotics · doi:10.1109/tro.2014.2321852 · Cited by 64 · cited 4×
“Consequently, SLAM has been the focus of a sustained research effort over the previous three decades, and there now exist a variety of mature algorithms and software libraries to solve this problem in practice (cf. [2]–[5]).”
BackgroundMethodInfluentialSelf-citationSemidefinite Descriptions of the Convex Hull of Rotation Matrices
Saunderson, J., Parrilo, P. A., & Willsky, A. S. (2015) · SIAM Journal on Optimization · doi:10.1137/14096339x · Cited by 62 · cited 1×
“Fortunately, a suitable criterion is provided by the following theorem due to Saun-derson, Parrilo and Willsky [11]: Theorem 3 (Spectrahedral description of conv SO ( n ) ) .”
BackgroundSimultaneous localization and mapping with multimodal probability distributions
Pfingsthorn, M. F., & Birk, A. (2012) · The International Journal of Robotics Research · doi:10.1177/0278364912461540 · Cited by 45 · cited 1×
“…of local search methods for optimization in SLAM with respect to poor initialization (e.g. the development of improved initialization procedures [18] or reparameterizations of the state space intended to broaden the basins of attraction of good solutions [2], [19]), ultimately these methods…”
MethodConvex relaxations of SE(2) and SE(3) for visual pose estimation
Horowitz, M. B., Matni, N., & Burdick, J. W. (2014) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2014.6906998 · Cited by 18 · cited 1×
“Another recent method similar to our own is [21], which formulates a specific instance of the convex relaxation (10) to solve the pointcloud registration problem; our approach can be be thought of as an extension of this work from the special case of single-pose estimation based on pose-landmark…”
Method
Research works printed but not linked: 2
- golub, 1996, Matrix Computations
- huber, 2004, Robust Statistics
Cited by
Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I., & Leonard, J. J. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2016.2624754 · Cited by 3,596
“on rotations [35], [211]) has enabled even stronger results.”
Self-citationPast, present, and future of simultaneous localization and mapping: Toward the robust-perception age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I. D., & Leonard, J. J. (2016) · Zurich Open Repository and Archive (University of Zurich) · doi:10.5167/uzh-138892 · Cited by 3,048
Self-citationSE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group
Rosen, D. M., Carlone, L., Bandeira, A. S., & Leonard, J. J. (2019) · The International Journal of Robotics Research · doi:10.1177/0278364918784361 · Cited by 282
“edience comes at the expense of reliability, as their restriction to local search renders these methods vulnerable to convergence to suboptimal critical points, even for relatively small noise levels [15, 36]. This observation, together with the fact that suboptimal critical points usually correspond to egregiously wr…”
Self-citationActive SLAM for Mobile Robots With Area Coverage and Obstacle Avoidance
Chen, Y., Huang, S., & Fitch, R. (2020) · IEEE/ASME Transactions on Mechatronics · doi:10.1109/tmech.2019.2963439 · Cited by 130
“The problem for conv SO ( n ) has been defined [24] π where (cid:13) • (cid:13) F is the Frobenius norm.”
BackgroundConvex Global 3D Registration with Lagrangian Duality
Briales, J., & González-Jiménez, J. (2017) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2017.595 · Cited by 118
“Numerous state-of-the-art SLAM (Simultaneous Localization and Mapping) solutions work with models that include plane and line primitives too [2, 47, 17, 43, 28, 19].”
Background
Metadata
- Authors
- Rosen, D. M., DuHadway, C., & Leonard, J. J.
- Affiliations
- MIT Computer Science and Artificial Intelligence Laboratory (US)
- Google (United States) (US)
- Venue
- 2015 IEEE International Conference on Robotics and Automation (ICRA)
- Publisher
- IEEE
- Published
- 2015-05
- Pages
- 5822-5829
- ISSN
- 1050-4729 (ISSN-L)
- OpenAlex
- W1553966841
- Cited by
- 56
- References
- 21
- Citations by year
- 2026: 1 · 2025: 4 · 2024: 6 · 2023: 2 · 2022: 4 · 2021: 5 · 2020: 5 · 2019: 6 · 2018: 11 · 2017: 4 · 2016: 7 · 2015: 1
- FWCI
- 13.27
- Type
- conference paper
- Language
- en
- Open access
- green
- hdl.handle.net
- Licence
- cc-by-nc-sa
- Locations
- Proceedings - IEEE International Conference on Robotics and Automation/Proceedings (publishedVersion)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc-sa)
- Funders
- Office of Naval Research
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Robotics and Sensor-Based Localization
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Physical Sciences › Computer Science › Artificial Intelligence › Target Tracking and Data Fusion in Sensor Networks
- Keywords
- SLAM, convex relaxation, sparse inference, robot localization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.