Parallel resampling algorithm for GPU-accelerated particle filter

Abstract

This thesis proposes a parallel resampling algorithm for GPU to accelerate particle filter. Particle filters have been influential filters to offer the solution of estimation problems dealing with nonlinear, non-Gaussian system. Even they work very well on the case that the nonlinearity is very massive. The particle filters have been actively researched in nonlinear filtering problem due to the simplicity and generality. However, enough particle population should be given in order to outperform other estimation solutions which leads to the weakness of the particle filter. Accordingly, the drawback has been overcome by the development of parallel processing device. Particle filter consists of propagation, update, and resampling. Most of the particle filter process is straightforward to parallelize, but the resampling step has complicated operations such as prefix sum and sorting the random number. The purpose of resampling is to overcome the degeneracy problem of SIS algorithm, and the basic principle of resampling is to duplicate high weighted particles and eliminate low weighted particles. Therefore, this thesis proposes novel resampling method well-suited to parallel algorithm. The resampling step is converted to run independently on each particle focusing on the purpose and the basic principle. In order to evaluate the proposed method, Monte-Carlo simulation is implemented in terrain referenced navigation, and the performance is evaluated under various conditions by changing the number of particles and the terrain roughness. It presents the computation time and the performance of particle filter, and these results are compared with the proposed resampling, rejection resampling, Metropolis resampling, and systematic resampling. The rejection and Metropolis resampling are proved to be effective in parallel processing. Furthermore, the proposed method shows similar or slightly better performance in terms of root mean square error, and performs faster than other resampling methods. Especially, when the number of particles is 16384, the time ratio is about 10 times for systematic resampling and about 3 times for other parallel resampling methods. As the number of particles is larger, the time ratio will increase. In addition to terrain referenced navigation, another particle filter with high computational load is expected to be efficient.