Efficient large scale SLAM including data association using the combined filter

Abstract

In this paper we describe the Combined Filter, a judicious combination of Extended Kalman (EKF) and Extended Information filters (EIF) that can be used to execute highly efficient SLAM in large environments. With the CF, filter updates can be executed in as low as O(log n) as compared with other EKF and EIF based algorithms: O(n2) for Map Joining SLAM, O(n) for Divide and Conquer (D&C) SLAM, and O(n1.5) for the Sparse Local Submap Joining Filter (SLSJF). 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, the CF Filter 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, the CF Filter outperforms all other algorithms. In large scale situations, both algorithms based on Extended Information filters, CF and SLSJF, avoid computing the full covariance matrix and thus require less memory, but still the CF Filter is the more 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.