The Bayes Tree: An Algorithmic Foundation for Probabilistic Robot Mapping

TitleThe Bayes Tree: An Algorithmic Foundation for Probabilistic Robot Mapping
Publication TypeConference Paper
Year of Publication2010
AuthorsKaess M, Ila V, Roberts R, Dellaert F
Conference NameIntl Workshop on the Algorithmic Foundations of Robotics, WAFR
Conference LocationSingapore

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 batch 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, 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 sparsityWe evaluate our algorithm on standard datasets in both landmark and pose SLAM settings