On the Structure of Nonlinearities in Pose Graph
Open accessThe DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Abstract
Pose graphs have become an attractive representation for solving Simultaneous Localization and Mapping (SLAM) problems.In this paper, we analyze the structure of the nonlinearities in the 2D SLAM problem formulated as the optimizing of a pose graph.First, we prove that finding the optimal configuration of a very basic pose graph with 3 nodes (poses) and 3 edges (relative pose constraints) with spherical covariance matrices, which can be formulated as a six dimensional least squares optimization problem, is equivalent to solving a one dimensional optimization problem.Then we show that the same result can be extended to the optimizing of a pose graph with "two anchor nodes" where every edge is connecting to one of the two anchor nodes.Furthermore, we prove that the global minimum of the resulting one dimensional optimization problem must belong to a certain interval and there are at most 3 minima in that interval.Thus the globally optimal pose configuration of the pose graph can be obtained very easily through the bisection method and closed-form formulas.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Least-Squares Fitting of Two 3-D Point Sets
Arun, K. S., Huang, T. S., & Blostein, S. D. (1987) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1987.4767965 · Cited by 3,952 · cited 1×
“The pose graph optimization problem considered in Theorem 2 has some similarity with the problem of estimating the relative transformation between two coordinate frames given two corresponding point sets [11].”
BackgroundGlobally Consistent Range Scan Alignment for Environment Mapping
Lu, F., & Milios, E. (1997) · Autonomous Robots · doi:10.1023/a:1008854305733 · Cited by 1,304
Nonlinear 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 3×
“Can we further exploit the special structure of the nonlinearity in pose graph SLAM such that more efficient algorithms can be developed? Or, has this structure already been implicitly used in the existing algorithms? For example, SGD is proposed in [3][6] to be used to solve the pose graph SLAM problems.”
BackgroundMethodInformation-Based Compact Pose SLAM
Ila, V., Porta, J. M., & Andrade-Cetto, J. (2010) · IEEE Transactions on Robotics · doi:10.1109/tro.2009.2034435 · Cited by 183 · cited 1×
“In pose graph SLAM, the property that the Jacobian and information matrix are exactly sparse [14] has been exploited in most of the recent efficient pose graph SLAM algorithms.”
MethodSubgraph-preconditioned conjugate gradients for large scale SLAM
Dellaert, F., Carlson, J., Ila, V, Ni, K., & Thorpe, C. E. (2010) · 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems · doi:10.1109/iros.2010.5650422 · Cited by 58 · cited 2×
“The work includes multi-level relaxation [2], stochastic gradient descent (SGD) [3], sparse Pose Adjustment (SPA) [4], preconditioned conjugate gradient and subgraph strategy [5].”
BackgroundMethodOn the number of local minima to the point feature based SLAM problem
Huang, S., Wang, H., Frese, U., & Dissanayake, G. (2012) · 2012 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2012.6224876 · Cited by 28
Self-citation
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. D., & Leonard, J. J. (2016) · Zurich Open Repository and Archive (University of Zurich) · doi:10.5167/uzh-138892 · Cited by 3,048
SE-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
Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions
Carlone, L., Rosen, D. M., Calafiore, G., Leonard, J. J., & Dellaert, F. (2015) · 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2015.7353364 · Cited by 95
Carlone, L., & Censi, A. (2014) · IEEE Transactions on Robotics · doi:10.1109/tro.2013.2291626 · Cited by 79
Duality-based verification techniques for 2D SLAM
Carlone, L., & Dellaert, F. (2015) · 2015 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra.2015.7139835 · Cited by 49
A convex optimization based approach for pose SLAM problems
Liu, M., Huang, S., Dissanayake, G., & Wang, H. (2012) · 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems · doi:10.1109/iros.2012.6385742 · Cited by 26
“Exploiting the special structure of the nonlinearity of the problem [20] in the convex optimization techniques and the extension of this work to 3D SLAM is also our future research work.”
BackgroundSelf-citationExploiting the Separable Structure of SLAM
Khosoussi, K., Huang, S., & Dissanayake, G. (2015) · Robotics: Science and Systems XI · doi:10.15607/rss.2015.xi.023 · Cited by 14
“For instance in [27, 28] we analyze the number of local minima is in some small special cases using this idea.”
MethodSelf-citation
Metadata
- Authors
- Wang, H., Hu, G., Huang, S., & Dissanayake, G.
- Venue
- Robotics: Science and Systems VIII
- Published
- 2012-07-09
- OpenAlex
- W1161662587
- Cited by
- 31
- References
- 6
- FWCI
- 7.17
- Type
- conference paper
- Language
- en
- Open access
- gold
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.