/The Bayes Tree: An Algorithmic Foundation for Probabilistic Robot Mapping

The Bayes Tree: An Algorithmic Foundation for Probabilistic Robot Mapping

Michael Kaess, Viorela Ila, Richard Roberts and Frank Dellaert
Conference Paper, Intl. Workshop on the Algorithmic Foundations of Robotics, WAFR, pp. 157-173, December, 2010

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


We present a novel data structure, the Bayes tree, that provides an al- gorithmic 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 in- formation 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 batch matrix factorization in terms of probability densities. Second, we show how the fairly abstract updates to a ma- trix 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, that combines incremental updates with fluid relinearization of a reduced set of variables for efficiency, combined with fast convergence to the exact solution. We also present a novel strategy for incremental variable reordering to retain sparsity. We evaluate our algorithm on standard datasets in both landmark and pose SLAM settings.

BibTeX Reference
author = {Michael Kaess and Viorela Ila and Richard Roberts and Frank Dellaert},
title = {The Bayes Tree: An Algorithmic Foundation for Probabilistic Robot Mapping},
booktitle = {Intl. Workshop on the Algorithmic Foundations of Robotics, WAFR},
year = {2010},
month = {December},
pages = {157-173},
keywords = {graphical models, clique tree, probabilistic inference, sparse linear algebra, nonlinear optimization, smoothing and mapping, SLAM, iSAM},