iSAM2: Incremental smoothing and mapping using the Bayes tree
We present a novel data structure, the Bayes tree, that provides an algorithmic foundation enabling a better understanding of existing graphical model inference algorithms and their connection to sparse matrix factorization methods. Similar to a clique tree, a Bayes tree encodes a factored probabili...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Sage Publications
2013
|
| Online Access: | http://hdl.handle.net/1721.1/78894 https://orcid.org/0000-0002-8863-6550 |
| _version_ | 1826189522170281984 |
|---|---|
| author | Kaess, Michael Johannsson, Hordur Roberts, Richard Ila, Viorela Leonard, John Joseph Dellaert, Frank |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kaess, Michael Johannsson, Hordur Roberts, Richard Ila, Viorela Leonard, John Joseph Dellaert, Frank |
| author_sort | Kaess, Michael |
| collection | MIT |
| description | We present a novel data structure, the Bayes tree, that provides an algorithmic foundation enabling a better understanding of existing graphical model inference algorithms and their connection to sparse matrix factorization methods. Similar to a clique tree, a Bayes tree encodes a factored probability density, but unlike the clique tree it is directed and maps more naturally to the square root information matrix of the simultaneous localization and mapping (SLAM) problem. In this paper, we highlight three insights provided by our new data structure. First, the Bayes tree provides a better understanding of the matrix factorization in terms of probability densities. Second, we show how the fairly abstract updates to a matrix factorization translate to a simple editing of the Bayes tree and its conditional densities. Third, we apply the Bayes tree to obtain a completely novel algorithm for sparse nonlinear incremental optimization, named iSAM2, which achieves improvements in efficiency through incremental variable re-ordering and fluid relinearization, eliminating the need for periodic batch steps. We analyze various properties of iSAM2 in detail, and show on a range of real and simulated datasets that our algorithm compares favorably with other recent mapping algorithms in both quality and efficiency. |
| first_indexed | 2024-09-23T08:16:11Z |
| format | Article |
| id | mit-1721.1/78894 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:16:11Z |
| publishDate | 2013 |
| publisher | Sage Publications |
| record_format | dspace |
| spelling | mit-1721.1/788942022-09-30T08:43:06Z iSAM2: Incremental smoothing and mapping using the Bayes tree Kaess, Michael Johannsson, Hordur Roberts, Richard Ila, Viorela Leonard, John Joseph Dellaert, Frank Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mechanical Engineering Kaess, Michael Johannsson, Hordur Leonard, John Joseph We present a novel data structure, the Bayes tree, that provides an algorithmic foundation enabling a better understanding of existing graphical model inference algorithms and their connection to sparse matrix factorization methods. Similar to a clique tree, a Bayes tree encodes a factored probability density, but unlike the clique tree it is directed and maps more naturally to the square root information matrix of the simultaneous localization and mapping (SLAM) problem. In this paper, we highlight three insights provided by our new data structure. First, the Bayes tree provides a better understanding of the matrix factorization in terms of probability densities. Second, we show how the fairly abstract updates to a matrix factorization translate to a simple editing of the Bayes tree and its conditional densities. Third, we apply the Bayes tree to obtain a completely novel algorithm for sparse nonlinear incremental optimization, named iSAM2, which achieves improvements in efficiency through incremental variable re-ordering and fluid relinearization, eliminating the need for periodic batch steps. We analyze various properties of iSAM2 in detail, and show on a range of real and simulated datasets that our algorithm compares favorably with other recent mapping algorithms in both quality and efficiency. United States. Office of Naval Research (Grant N00014-06-1-0043) United States. Office of Naval Research (Grant N00014-10-1-0936) 2013-05-14T20:17:26Z 2013-05-14T20:17:26Z 2011-12 Article http://purl.org/eprint/type/JournalArticle 0278-3649 1741-3176 http://hdl.handle.net/1721.1/78894 Kaess, M. et al. “iSAM2: Incremental Smoothing and Mapping Using the Bayes Tree.” The International Journal of Robotics Research 31.2 (2011): 216–235. https://orcid.org/0000-0002-8863-6550 en_US http://dx.doi.org/10.1177/0278364911430419 International Journal of Robotics Research Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Sage Publications MIT web domain |
| spellingShingle | Kaess, Michael Johannsson, Hordur Roberts, Richard Ila, Viorela Leonard, John Joseph Dellaert, Frank iSAM2: Incremental smoothing and mapping using the Bayes tree |
| title | iSAM2: Incremental smoothing and mapping using the Bayes tree |
| title_full | iSAM2: Incremental smoothing and mapping using the Bayes tree |
| title_fullStr | iSAM2: Incremental smoothing and mapping using the Bayes tree |
| title_full_unstemmed | iSAM2: Incremental smoothing and mapping using the Bayes tree |
| title_short | iSAM2: Incremental smoothing and mapping using the Bayes tree |
| title_sort | isam2 incremental smoothing and mapping using the bayes tree |
| url | http://hdl.handle.net/1721.1/78894 https://orcid.org/0000-0002-8863-6550 |
| work_keys_str_mv | AT kaessmichael isam2incrementalsmoothingandmappingusingthebayestree AT johannssonhordur isam2incrementalsmoothingandmappingusingthebayestree AT robertsrichard isam2incrementalsmoothingandmappingusingthebayestree AT ilaviorela isam2incrementalsmoothingandmappingusingthebayestree AT leonardjohnjoseph isam2incrementalsmoothingandmappingusingthebayestree AT dellaertfrank isam2incrementalsmoothingandmappingusingthebayestree |