Robotics: Science and Systems III

Data Association in O(n) for Divide and Conquer SLAM

Lina María Paz, José Guivant, Juan D. Tardós, and José Neira

Abstract: In this paper we show that {\em all} processes associated to the move-sense-update cycle of EKF SLAM can be carried out in time {\em linear} in the number of map features. We describe Divide and Conquer SLAM, an EKF SLAM algorithm where the computational complexity per step is reduced from O(n^2) to O(n); the total cost of SLAM is reduced from O(n^3) to O(n^2). In addition, the resulting vehicle and map estimates have better consistency properties than standard EKF SLAM in the sense that the computed state covariance more adequately represents the real error in the estimation. Both simulated experiments and the Victoria Park Dataset are used to provide evidence of the advantages of this algorithm.

Download:

Bibtex:

@INPROCEEDINGS{ Paz-RSS-07,
    AUTHOR    = {L. Paz and J. Guivant and J. Tardós and J. Neira},
    TITLE     = {Data Association in O(n) for Divide and Conquer SLAM},
    BOOKTITLE = {Proceedings of Robotics: Science and Systems},
    YEAR      = {2007},
    ADDRESS   = {Atlanta, GA, USA},
    MONTH     = {June},
    DOI       = {10.15607/RSS.2007.III.036} 
}