Research on using inexpensive and personal-level parallel computing architectures to speed up the implementations of the class of particle filters has been conducted. This study leverages NVIDIA Graphics Processing Units (GPUs) and multi-core CPUs (central processing units) that are quickly becoming commonly available for engineering communities. Parallelization of the unscented Kalman filter and the bootstrap particle filter, with applications in a GPS/INS (global position system/inertial navigation system) integration problem and an orbital determination problem, has been the focus of this research. It has been shown in this research that an 8-times speedup can be achieved for the unscented Kalman filter implementations with an 8-thread CPU, and up to 2 orders of magnitude speedup can be achieved using an M2090 GPU.

The results also show that real-time applications for both unscented Kalman filters and particle filters are feasible for the two benchmark problems considered. The parallelized particle filter for both benchmark problems completes a 1-s filter cycle in under 0.23 s. It also demonstrates that parallel modules can be made as a black box that can interact with third-party serial programs, but require minimum knowledge from the user on how to parallelize a problem or on how to write a parallel program.

This research contributes to upgrading the current fleet of NASA navigation software that heavily relies on the Kalman filter and the Extended Kalman Filter (EKF), which can fail in nonlinear applications with non-Gaussian noise models. Advanced filters, like the sigma point and particle filters, are more accurate than the EKF for nonlinear and non-Gaussian noise models.

One drawback of the particle-based filters is the excessive computational burden if implemented on a serial computer. However, because a majority of the computation can be carried out simultaneously, the particle filters inherently are well suited for parallel computing. The objective of this effort is to leverage GPUs and multi-core CPUs to exploit such parallelism. With the performance of these devices improving at a rapid pace, it is anticipated that they will quickly find their way to onboard avionics. This research paves the way for implementing particle filters in real-time applications. This will bring unprecedented accuracy and applicability of particle filters to aircraft and spacecraft navigation analyses for NASA, and for a wide range of non-NASA applications.

This work was done by Haijun Shen and Christopher D. Karlgaard of Analytical Mechanics Associates, Inc., and Ryan P. Russell, Vivek Vittaldev, and Etienne Pellegrini of The University of Texas, Austin for Glenn Research Center.

Inquiries concerning rights for the commercial use of this invention should be addressed to

NASA Glenn Research Center
Innovative Partnerships Office
Attn: Steven Fedor
Mail Stop 4–8
21000 Brookpark Road
Cleveland
Ohio 44135.

Refer to LEW-19021-1.


NASA Tech Briefs Magazine

This article first appeared in the February, 2014 issue of NASA Tech Briefs Magazine.

Read more articles from this issue here.

Read more articles from the archives here.