A Parallel Resampling Algorithm for Particle Filtering on Shared-Memory Architectures

Many real-world applications such as positioning, navigation, and target tracking for autonomous vehicles require the estimation of some time-varying states based on noisy measurements made on the system. Particle filters can be used when the system model and the measurement model are not Gaussian or linear. However, the computational complexity of particle filters prevents them from being widely adopted. Parallel implementation will make particle filters more feasible for real-time applications. Effective resampling algorithms like the systematic resampling algorithm are serial. In this paper, we propose the shared-memory systematic resampling (SMSR) algorithm that is easily parallelizable on existing architectures. We verify the performance of SMSR on graphics processing units. Experimental results show that the proposed SMSR algorithm can achieve a significant speedup over the serial particle filter.