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

Award Information
Agency: Department of Defense
Branch: Air Force
Contract: FA9302-10-M-0014
Agency Tracking Number: F093-221-2394
Amount: $99,999.00
Phase: Phase I
Program: SBIR
Awards Year: 2010
Solicitation Year: 2009
Solicitation Topic Code: AF093-221
Solicitation Number: 2009.3
Small Business Information
95 First Street, Suite 240, Los Altos, CA, 94022
DUNS: 829385509
HUBZone Owned: N
Woman Owned: N
Socially and Economically Disadvantaged: N
Principal Investigator
 Monish Tandale
 Research Scientist
 (650) 559-8585
Business Contact
 P. Menon
Title: President
Phone: (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
Environmental Protection Agency logo
National Aeronautics and Space Administration logo
National Science Foundation logo
US Flag An Official Website of the United States Government