Complexity Analysis and Efficient Measurement Selection Primitives for High-Rate Graph SLAM
© 2018 IEEE. Sparsity has been widely recognized as crucial for efficient optimization in graph-based SLAM. Because the sparsity and structure of the SLAM graph reflect the set of incorporated measurements, many methods for sparsification have been proposed in hopes of reducing computation. These me...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137882 |
| _version_ | 1811086267147878400 |
|---|---|
| author | Frey, Kristoffer M. Steiner, Ted J. How, Jonathan P. |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Frey, Kristoffer M. Steiner, Ted J. How, Jonathan P. |
| author_sort | Frey, Kristoffer M. |
| collection | MIT |
| description | © 2018 IEEE. Sparsity has been widely recognized as crucial for efficient optimization in graph-based SLAM. Because the sparsity and structure of the SLAM graph reflect the set of incorporated measurements, many methods for sparsification have been proposed in hopes of reducing computation. These methods often focus narrowly on reducing edge count without regard for structure at a global level. Such structurally-naïve techniques can fail to produce significant computational savings, even after aggressive pruning. In contrast, simple heuristics such as measurement decimation and keyframing are known empirically to produce significant computation reductions. To demonstrate why, we propose a quantitative metric called elimination complexity (EC) that bridges the existing analytic gap between graph structure and computation. EC quantifies the complexity of the primary computational bottleneck: the factorization step of a Gauss-Newton iteration. Using this metric, we show rigorously that decimation and keyframing impose favorable global structures and therefore achieve computation reductions on the order of r2/9 and r3, respectively, where r is the pruning rate. We additionally present numerical results showing EC provides a good approximation of computation in both batch and incremental (iSAM2) optimization and demonstrate that pruning methods promoting globally-efficient structure outperform those that do not. |
| first_indexed | 2024-09-23T13:23:30Z |
| format | Article |
| id | mit-1721.1/137882 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:23:30Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1378822023-02-03T21:45:43Z Complexity Analysis and Efficient Measurement Selection Primitives for High-Rate Graph SLAM Frey, Kristoffer M. Steiner, Ted J. How, Jonathan P. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics © 2018 IEEE. Sparsity has been widely recognized as crucial for efficient optimization in graph-based SLAM. Because the sparsity and structure of the SLAM graph reflect the set of incorporated measurements, many methods for sparsification have been proposed in hopes of reducing computation. These methods often focus narrowly on reducing edge count without regard for structure at a global level. Such structurally-naïve techniques can fail to produce significant computational savings, even after aggressive pruning. In contrast, simple heuristics such as measurement decimation and keyframing are known empirically to produce significant computation reductions. To demonstrate why, we propose a quantitative metric called elimination complexity (EC) that bridges the existing analytic gap between graph structure and computation. EC quantifies the complexity of the primary computational bottleneck: the factorization step of a Gauss-Newton iteration. Using this metric, we show rigorously that decimation and keyframing impose favorable global structures and therefore achieve computation reductions on the order of r2/9 and r3, respectively, where r is the pruning rate. We additionally present numerical results showing EC provides a good approximation of computation in both batch and incremental (iSAM2) optimization and demonstrate that pruning methods promoting globally-efficient structure outperform those that do not. 2021-11-09T14:30:28Z 2021-11-09T14:30:28Z 2018-03 2019-10-28T15:01:15Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137882 Frey, Kristoffer M., Steiner, Ted J. and How, Jonathan P. 2018. "Complexity Analysis and Efficient Measurement Selection Primitives for High-Rate Graph SLAM." en 10.1109/ICRA.2018.8460708 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Frey, Kristoffer M. Steiner, Ted J. How, Jonathan P. Complexity Analysis and Efficient Measurement Selection Primitives for High-Rate Graph SLAM |
| title | Complexity Analysis and Efficient Measurement Selection Primitives for High-Rate Graph SLAM |
| title_full | Complexity Analysis and Efficient Measurement Selection Primitives for High-Rate Graph SLAM |
| title_fullStr | Complexity Analysis and Efficient Measurement Selection Primitives for High-Rate Graph SLAM |
| title_full_unstemmed | Complexity Analysis and Efficient Measurement Selection Primitives for High-Rate Graph SLAM |
| title_short | Complexity Analysis and Efficient Measurement Selection Primitives for High-Rate Graph SLAM |
| title_sort | complexity analysis and efficient measurement selection primitives for high rate graph slam |
| url | https://hdl.handle.net/1721.1/137882 |
| work_keys_str_mv | AT freykristofferm complexityanalysisandefficientmeasurementselectionprimitivesforhighrategraphslam AT steinertedj complexityanalysisandefficientmeasurementselectionprimitivesforhighrategraphslam AT howjonathanp complexityanalysisandefficientmeasurementselectionprimitivesforhighrategraphslam |