A New Parallel Resampling Algorithm for GPU-Accelerated Particle Filter

Particle filtering is a sequential Monte Carlo method widely used to solve non-linear and non-Gaussian filtering problems. Particle filters represent the posterior distributions as a set of particles, so they demand a sizeable computational load for satisfactory accuracy. In order to accelerate it, there have been many attempts to apply to graphics processing units (GPUs) through parallelization. However, parallelization of the resampling process has several challenges due to its sequential nature and, worse, can cause a bottleneck. Therefore, this paper addresses a new resampling method suitable for parallel computing. We focus on maximizing the number of processes to run independently on each particle and demonstrate the performance in terms of root mean square error (RMSE), the computation times, and Jensen-Shannon divergence (JSD) in an application of terrain referenced navigation (TRN). The results were compared to rejection, Metropolis, and systematic resampling methods.