A computational efficient SLAM algorithm based on logarithmic-map partitioning

Abstract

Simultaneous localization and map building (SLAM) is a fundamental and complex problem in mobile robot research. In SLAM, Kalman-filter-like implementations are widely adopted to localize a mobile robot and build a map simultaneously and incrementally. However, this approach requires extensive computations of order O(N/sup 2/), where N is the total number of landmarks. To make the computations more manageable, we propose a logarithmic map partitioning algorithm that partitions the global map into one local region and several sub-maps. The size of each sub-map is based on its distance from the mobile robot, and in each sub-map, a centroid landmark is selected to represent all the landmarks in the sub-map for SLAM computations. With this logarithmic-map partitioning, it maintains correlation updates with each sub-map and provides an efficient suboptimal solution to the SLAM problem. The number of landmarks reduces from N to a logarithm-based function of N, and the computational requirement reduces from O(N/sup 3/) to O(N/sup 2/), where N/sub L/ is the number of local landmarks. Furthermore, utilizing the compressed extended Kalman filter, the real-time computational complexity reduces to O(N/sub L//sup 2/). Computer simulation results showed that the proposed algorithm is consistent and efficient for a large number of landmarks.