Publication Date:
2022-05-25
Description:
Author Posting. © The Author(s), 2011. This is the author's version of the work. It is posted here by permission of Sage for personal use, not for redistribution. The definitive version was published in International Journal of Robotics Research 31 (2012): 216-235, doi:10.1177/0278364911430419.
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.
Description:
M. Kaess, H. Johannsson and J. Leonard were partially supported
by ONR grants N00014-06-1-0043 and N00014-10-1-0936. F. Dellaert and R. Roberts were partially supported by
NSF, award number 0713162, “RI: Inference in Large-Scale
Graphical Models”. V. Ila has been partially supported by the
Spanish MICINN under the Programa Nacional de Movilidad
de Recursos Humanos de Investigación.
Keywords:
Graphical models
;
Clique tree
;
Junction tree
;
Probabilistic inference
;
Sparse linear algebra
;
Nonlinear optimization
;
Smoothing and mapping
;
SLAM
Repository Name:
Woods Hole Open Access Server
Type:
Preprint
Format:
application/pdf
Permalink
