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

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.