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

Award Information
Agency:
Department of Defense
Branch
Air Force
Amount:
$99,999.00
Award Year:
2010
Program:
SBIR
Phase:
Phase I
Contract:
FA9302-10-M-0014
Award Id:
97537
Agency Tracking Number:
F093-221-2394
Solicitation Year:
n/a
Solicitation Topic Code:
AF 09-221
Solicitation Number:
n/a
Small Business Information
95 First Street, Suite 240, Los Altos, CA, 94022
Hubzone Owned:
N
Minority Owned:
N
Woman Owned:
N
Duns:
829385509
Principal Investigator:
Monish Tandale
Research Scientist
(650) 559-8585
monish@optisyn.com
Business Contact:
P. Menon
President
(650) 559-8585
menon@optisyn.com
Research Institution:
n/a
Abstract
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