SLAM in O(logn)O(logn) with the Combined Kalman-Information Filter

In this paper1 we describe the Combined Kalman-Information Filter SLAM algorithm (CF SLAM), a judicious combination of Extended Kalman (EKF) and Extended Information Filters (EIF) that can be used to execute highly efficient SLAM in large environments. CF SLAM is always more efficient than any other EKF or EIF algorithm: filter updates can be executed in as low as O(logn)O(logn) as compared with O(n2)O(n2) for Map Joining SLAM, O(n)O(n) for Divide and Conquer (D&C) SLAM, and the Sparse Local Submap Joining Filter (SLSJF). In the worst cases, updates are executed in O(n)O(n) for CF SLAM as compared with O(n2)O(n2) for all others. We also study an often overlooked problem in computationally efficient SLAM algorithms: data association. In situations in which only uncertain geometrical information is available for data association, CF SLAM is as efficient as D&C SLAM, and much more efficient than Map Joining SLAM or SLSJF. If alternative information is available for data association, such as texture in visual SLAM, CF SLAM outperforms all other algorithms. In large scale situations, both algorithms based on Extended Information filters, CF SLAM and SLSJF, avoid computing the full covariance matrix and thus require less memory, but still CF SLAM is the most computationally efficient. Both simulations and experiments with the Victoria Park dataset, the DLR dataset, and an experiment using visual stereo are used to illustrate the algorithms’ advantages, also with respect to non filtering alternatives such as iSAM, the Treemap and Tectonic SAM.