Austin I. Eliazar, Ronald Parr
We present an improvement to the DP-SLAM algorithm for simultane- ous localization and mapping (SLAM) that maintains multiple hypothe- ses about densely populated maps (one full map per particle in a par- ticle ﬁlter) in time that is linear in all signiﬁcant algorithm parameters and takes constant (amortized) time per iteration. This means that the asymptotic complexity of the algorithm is no greater than that of a pure localization algorithm using a single map and the same number of parti- cles. We also present a hierarchical extension of DP-SLAM that uses a two level particle ﬁlter which models drift in the particle ﬁltering process itself. The hierarchical approach enables recovery from the inevitable drift that results from using a ﬁnite number of particles in a particle ﬁlter and permits the use of DP-SLAM in more challenging domains, while maintaining linear time asymptotic complexity.