SLAM in O(log n) with the Combined Kalman - Information filter

In this paper we show that SLAM can be executed in as low as O(log n) per step. Our algorithm, the Combined Filter SLAM, uses a combination of Extended Kalman and Extended Information filters in such a way that the total cost of building a map can be reduced to O(n log n), as compared with O(n³) for standard EKF SLAM, and O(n²) for Divide and Conquer (D&C) SLAM and the Sparse Local Submap Joining Filter (SLSJF). We discuss the computational improvements that have been proposed for Kalman and Information filters, discuss the advantages and limitations of each, and how a judicious combination results in the possibility of reducing the computational cost per step to O(log n).We use simulations and real datasets to show the advantages of the proposed algorithm.