Trajectory Reconstruction for Nonlinear Non-Gaussian Models Using Particle Smoothing on Graphics Processing Units

Award Information
Department of Defense
Air Force
Award Year:
Phase I
Agency Tracking Number:
Solicitation Year:
Solicitation Topic Code:
AF 09-221
Solicitation Number:
Small Business Information
Optimal Synthesis Inc.
95 First Street, Suite 240, Los Altos, CA, 94022
Hubzone Owned:
Minority Owned:
Woman Owned:
Principal Investigator:
Monish Tandale
Research Scientist
(650) 559-8585
Business Contact:
P. Menon
(650) 559-8585
Research Institution:
The problem of Trajectory Reconstruction is referred to in estimation literature as the Smoothing Problem. It involves determination of the time history of the states using entire history of measurements from on board sensors such as the IMU and GPS, and ground based Radar tracking stations. Particle smoothing algorithms that are based on propagating a cloud of multiple particles, do not rely on local linearizations or any crude functional approximations and the models can be nonlinear, multi-modal or non-stationary. This flexibility comes at the price of computational complexity which had rendered particle smoothers impractical until now. The particle smoothing algorithms have a computational complexity of , where N is the large number of particles required to achieve good estimation accuracy. This research proposes to tame the computational complexity by taking advantage of the emerging computational power of the Graphics Processing Units (GPUs), to achieve near-real time performance. The research effort will implement 2 particle smoothing algorithms on GPUs intended for High Performance Computing. The feasibility of implementing trajectory reconstruction for a nonlinear 6 degree-of-freedom flight vehicle model in near-real time will be demonstrated. The estimation accuracy will be compared to a baseline Extended Kalman Filter (EKF) based smoothing algorithm and the acceleration in run-time achieved by the GPU implementation will be documented. BENEFIT: The implemented trajectory smoothing algorithm will enable better accuracy as compared to the existing methods as it uses nonlinear, non-Gaussian models without any need for linearizations or any crude approximations. The implementation of the particle smoothing algorithm on Graphics Processing Units will lead to significant reduction in execution times. In previous DOD and NASA SBIRs, Optimal Synthesis has demonstrated run time acceleration of 10 to 250 times and similar acceleration factors are projected for this application. This will significantly reduce or eliminate post processing mission delays in reconstructing aircraft flight trajectories. Particle filtering/smoothing has found numerous applications in belief inference, target tracking in diverse areas such as computer graphics, machine vision, computational finance and robotics. Computational acceleration of particle filtering/smoothing will enable real-time performance in all these areas.

* information listed above is at the time of submission.

Agency Micro-sites

SBA logo

Department of Agriculture logo

Department of Commerce logo

Department of Defense logo

Department of Education logo

Department of Energy logo

Department of Health and Human Services logo

Department of Homeland Security logo

Department of Transportation logo

Enviromental Protection Agency logo

National Aeronautics and Space Administration logo

National Science Foundation logo
US Flag An Official Website of the United States Government