Bayesian Particle Filtering (BPF) is a modern algorithm for state space tracking that offers robust high-quality multi-modal state estimates for arbitrary models, but at high computational expense. Many implementations of BPF are computationally bottlenecked by a weighted resampling step in the algorithm. Previous resampling approximations remove this bottleneck, but at the expense of verifiable correctness. I have developed a novel efficient resampling method that is apparently also correct, based on the generation of polynomially-distributed random variates.
In this talk, I will (very briefly) sketch BPF, show the application of BPF to a kinematic tracking problem, characterize various resampling methods for BPF, and comment on the generation of random variates using a slight generalization of the Ziggurat Method of Marsaglia and Lee.
Bart Massey (Reed '87, Physics) spent two years doing DSP programming and system software engineering at Tektronix, then did his graduate work in programming language implementation (M.Sc.) and artificial intelligence (Ph.D.) at the University of Oregon. He is currently an Associate Professor of Computer Science at Portland State University, and Faculty Advisor to the Portland State Aerospace Society.