Implementation and performance analysis of a parallelized particle filter algorithm

Abstract

The ability of a particle filter to accurately estimate both linear and non-linear, Gaussian and non-Gaussian dynamic systems makes it suitable for many localization and tracking applications in robotics. Particle filter solutions have also been proposed in other areas for state estimation, for example – feature tracking in computer vision, fault diagnosis, etc. The accuracy of a particle filter estimate is a function of the number of particles used in the algorithm. However, as the particle set grows in number the computational cost to implement the algorithm also increases, thereby limiting its practical applicability for real-time estimation problems. Thus, there is always a tradeoff between the required accuracy and computational efficiency in using these algorithms. This thesis tries to reduce the above mentioned limitation by a parallelized implementation of the particle filter algorithm for multi-core CPUs, which the sequential version of the algorithm cannot take advantage of. The specific algorithm studied is the Monte Carlo Localization (MCL) technique- a particle filtering method widely used for mobile robot localization. The research focusses on implementing an efficient parallelized version of the MCL, and analyzes the computational performance improvement of the same compared to its traditional sequential version. The limitations on the speedup gained from multi-core processors is also studied. The methodology used in this work can serve as a general framework for similar particle filter algorithms in other hardware platforms and applications.