Subgraph-preconditioned conjugate gradients for large scale SLAM
Open accessThe DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Abstract
In this paper we propose an efficient preconditioned conjugate gradients (PCG) approach to solving large-scale SLAM problems. While direct methods, popular in the literature, exhibit quadratic convergence and can be quite efficient for sparse problems, they typically require a lot of storage and efficient elimination orderings to be found. In contrast, iterative optimization methods only require access to the gradient and have a small memory footprint, but can suffer from poor convergence. Our new method, subgraph preconditioning, is obtained by re-interpreting the method of conjugate gradients in terms of the graphical model representation of the SLAM problem. The main idea is to combine the advantages of direct and iterative methods, by identifying a sub-problem that can be easily solved using direct methods, and solving for the remaining part using PCG. The easy sub-problems correspond to a spanning tree, a planar subgraph, or any other substructure that can be efficiently solved. As such, our approach provides new insights into the performance of state of the art iterative SLAM methods based on re-parameterized stochastic gradient descent. The efficiency of our new algorithm is illustrated on large datasets, both simulated and real.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“When using iterative linear solvers (e.g., the conjugate gradient [62]) the memory consumption grows linearly in the number of variables.”
From Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age (2016) · cites this paper as [62]
Citations
Cites
Methods of conjugate gradients for solving linear systems
Hestenes, M. R., & Stiefel, E. (1952) · Journal of Research of the National Bureau of Standards · doi:10.6028/jres.049.044 · Cited by 8,132 · cited 1×
“The solution is to make each search direction Λ -conjugate with respect to the previous one [19], or This can be done by taking the gradient direction and subtracting out some of the previous search direction d k : As we start with x 0 = 0 we have g 0 = − η = − A T b , and it is easy to show that g…”
MethodThrun, S. (2002) · Communications of the ACM · doi:10.1145/504729.504754 · Cited by 7,994
Numerical Methods for Least Squares Problems
Björck, Å. (1996) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971484 · Cited by 3,257
Numerical methods for least squares problems
(1996) · Choice Reviews Online · doi:10.5860/choice.34-1602 · Cited by 3,007 · cited 2×
“The resulting conjugate gradient (CG) method is listed as Algorithm 1 and is equivalent to the least-squares CG variant (CGLS) described by Björck in [20, page 288].”
MethodBriggs, W. L. (1987) · Cited by 1,868
On the Representation and Estimation of Spatial Uncertainty
Smith, R. C., & Cheeseman, P. (1986) · The International Journal of Robotics Research · doi:10.1177/027836498600500404 · Cited by 1,579 · cited 1×
“However, due to their quadratic memory and computational cost, EKF-based solutions are limited to small areas [1].”
BackgroundSquare 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 · cited 4×
“We follow the statement of the SLAM problem in [5], obtaining the nonlinear least-squares objective function We linearize around a linearization point θ 0 to get a new, linear least-squares problem in x with objective function where A ∈ R m × n is the measurement Jacobian and x an n -dimensional…”
BackgroundMethodInfluentialSelf-citationSimultaneous Localization and Mapping with Sparse Extended Information Filters
Thrun, S., Liu, Y., Koller, D., Ng, A. Y., Ghahramani, Z., & Durrant-Whyte, H. (2004) · The International Journal of Robotics Research · doi:10.1177/0278364904045479 · Cited by 651 · cited 1×
“These were pioneered by [12] and [13], and later also adapted in [14], [15] to relax a sparsified information matrix.”
BackgroundRobust Mapping and Localization in Indoor Environments Using Sonar Data
Tardós, J. D., Neira, J., Newman, P. M., & Leonard, J. J. (2002) · The International Journal of Robotics Research · doi:10.1177/027836402320556340 · Cited by 533 · cited 1×
“In hierarchical mapping [6], [7], [8], [9], [10] the map elements are grouped respect to their spatial distribution by build local submaps that are integrated into a global map.”
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×
“However, the current state of the art in pose-graph relaxation stems from the work by [3] whose main contribution is a parameterization of the global poses in terms of increments along the trajectory.”
BackgroundHierarchical SLAM: real-time accurate mapping of large environments
Estrada, C., Neira, J., & Tardos, J. D. (2005) · IEEE Transactions on Robotics · doi:10.1109/tro.2005.844673 · Cited by 368 · cited 1×
“In hierarchical mapping [6], [7], [8], [9], [10] the map elements are grouped respect to their spatial distribution by build local submaps that are integrated into a global map.”
BackgroundDynamic Maps for Long-Term Operation of Mobile Service Robots
Biber, P., & Duckett, T. (2005) · Robotics: Science and Systems I · doi:10.15607/rss.2005.i.003 · Cited by 334
A counter example to the theory of simultaneous localization and map building
Julier, S. J., & Uhlmann, J. K. (2002) · Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164) · doi:10.1109/robot.2001.933280 · Cited by 317 · cited 1×
“Filtering itself has been shown to be inconsistent when applied to the inherently non-linear SLAM problem [2], i.e., even the average solution taken over a large number of experiments diverges from the true solution.”
BackgroundA multilevel relaxation algorithm for simultaneous localization and mapping
Frese, U., Larsson, P., & Duckett, T. (2005) · IEEE Transactions on Robotics · doi:10.1109/tro.2004.839220 · Cited by 283 · cited 1×
“In [17], Frese et.”
Large-Scale 6-DOF SLAM With Stereo-in-Hand
Paz, L. M., Pinies, P., Tardos, J. D., & Neira, J. (2008) · IEEE Transactions on Robotics · doi:10.1109/tro.2008.2004637 · Cited by 242 · cited 1×
“In hierarchical mapping [6], [7], [8], [9], [10] the map elements are grouped respect to their spatial distribution by build local submaps that are integrated into a global map.”
BackgroundNonlinear Constraint Network Optimization for Efficient Map Learning
Grisetti, G., Stachniss, C., & Burgard, W. (2009) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2009.2026444 · Cited by 222 · cited 1×
“Grisetti [4], [19] adopted this incremental reparameterization as well, but instead defines it on a spanning tree.”
BackgroundA Tree Parameterization for Efficiently Computing Maximum Likelihood Maps using Gradient Descent
Grisetti, G., Stachniss, C., Grzonka, S., & Burgard, W. (2007) · Robotics: Science and Systems III · doi:10.15607/rss.2007.iii.009 · Cited by 216 · cited 3×
“Grisetti [4], [18] adopted this incremental parameterization as well, but instead defines it on a spanning tree.”
BackgroundMethodRelaxation on a mesh: a formalism for generalized localization
Howard, A., Mataric, M. J., & Sukhatme, G. (2002) · Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No.01CH37180) · doi:10.1109/iros.2001.976308 · Cited by 180 · cited 1×
“These were pioneered by [11] and [12], and later also adapted in [13], [14] to relax a sparsified information matrix.”
BackgroundKonolige, K. (2004) · National Conference on Artificial Intelligence · Cited by 140
Learning globally consistent maps by relaxation
Duckett, T., Marsland, S., & Shapiro, J. (2002) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.845330 · Cited by 119 · cited 1×
“These were pioneered by [11] and [12], and later also adapted in [13], [14] to relax a sparsified information matrix.”
BackgroundTectonic SAM: Exact, Out-of-Core, Submap-Based SLAM
Ni, K., Steedly, D., & Dellaert, F. (2007) · Proceedings 2007 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2007.363564 · Cited by 116 · cited 1×
“In hierarchical mapping [6], [7], [8], [9], [10] the map elements are grouped respect to their spatial distribution by build local submaps that are integrated into a global map.”
BackgroundSelf-citationExploiting Locality by Nested Dissection For Square Root Smoothing and Mapping
Krauthausen, P., Dellaert, F., & Kipp, A. (2005) · SMARTech Repository (Georgia Institute of Technology) · Cited by 22
Self-citationExploiting Locality in SLAM by Nested Dissection
Krauthausen, P., Kipp, A., & Dellaert, F. (2006) · doi:10.15607/rss.2006.ii.010 · Cited by 19
Self-citationExact state and covariance sub-matrix recovery for submap based sparse EIF SLAM algorithm
Huang, S., Wang, Z., & Dissanayake, G. (2008) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2008.4543479 · Cited by 14 · cited 1×
“In hierarchical mapping [6], [7], [8], [9], [10] the map elements are grouped respect to their spatial distribution by build local submaps that are integrated into a global map.”
Background
Research works printed but not linked: 1
- thrun, 2003, Multi-robot SLAM with sparse extended information filters, Proceedings of the 11th International Symposium of Robotics Research(ISRR'03)
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
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. D., & Leonard, J. J. (2016) · Zurich Open Repository and Archive (University of Zurich) · doi:10.5167/uzh-138892 · Cited by 3,048
iSAM2: 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-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
“Indeed, there now exist a variety of mature algorithms and software libraries implementing this approach that are able to process special Euclidean synchronization problems involving tens to hundreds of thousands of latent states in real time using only a single thread on a commodity processor (Dellaert et al., 2010;…”
BackgroundLategahn, H., & Stiller, C. (2014) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2014.2298492 · Cited by 132
“The work we present herein is strongly related to simultaneous localization and mapping (SLAM) [5], [6], [9], [10], [14], [19], [21], [26], [30], [35], from which we draw many inspirations, localization in general and map-relative localization [7], [11], [22]–[25], [28], [31], [33] in particular.”
Background
Metadata
- Authors
- Dellaert, F., Carlson, J., Ila, V, Ni, K., & Thorpe, C. E.
- Affiliations
- Georgia Institute of Technology (US)
- Carnegie Mellon University Qatar (QA)
- Venue
- 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems
- Publisher
- IEEE
- Published
- 2010-10
- Pages
- 2566-2571
- ISSN
- 2153-0858 (ISSN-L)
- OpenAlex
- W2056458921
- Cited by
- 58
- References
- 24
- Citations by year
- 2026: 1 · 2025: 2 · 2024: 1 · 2023: 2 · 2022: 2 · 2021: 3 · 2020: 4 · 2019: 1 · 2018: 2 · 2017: 2 · 2016: 7 · 2015: 5 · 2014: 5 · 2013: 5 · 2012: 9
- FWCI
- 13.37
- Type
- conference paper
- Language
- en
- Open access
- green
- hdl.handle.net
- Licence
- cc-by-nc-nd
- Locations
- IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (publishedVersion)
- UPCommons institutional repository (Universitat Politècnica de Catalunya) (publishedVersion, cc-by-nc-nd)
- DIGITAL.CSIC (Spanish National Research Council (CSIC)) (submittedVersion, other-oa)
- RECERCAT (Consorci de Serveis Universitaris de Catalunya) (submittedVersion, cc-by-nc-nd)
- SMARTech Repository (Georgia Institute of Technology) (submittedVersion)
- Funders
- National Science Foundation (0713162, CAREER, 0448111)
- Ministerio de Ciencia e Innovación
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Robotics and Sensor-Based Localization
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Target Tracking and Data Fusion in Sensor Networks
- Keywords
- SLAM, preconditioned conjugate gradient, large-scale optimization, probabilistic graphical models, spanning trees, planar subgraphs, iterative optimization
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.