A Fully Parallel Particle Filter Architecture for FPGAs

详细信息    查看全文

• 作者：Fynn Schwiegelshohn (17)
  Eugen Ossovski (17)
  Michael H眉bner (17)
  
  17. Embedded Systems for Information Technology ; Ruhr-Universit盲t-Bochum ; Bochum ; Nord-Rhein-Westfalen ; Germany
  
• 关键词：Particle filter ; FPGA ; Resampling ; Parallelization ; Robotics ; Localization ; Sensor update ; Motion update ; FPGA optimized resampling
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9040
• 期：1
• 页码：91-102
• 全文大小：478 KB
• 参考文献：1. Arulampalam, M, Maskell, S, Gordon, N, Clapp, T (2002) A tutorial on particle filters for online nonlinear/non-gaussian bayesian tracking. IEEE Transactions on Signal Processing 50: pp. 174-188 CrossRef
  2. Carlin, BP, Polson, NG, Stoffer, DS (1992) A monte carlo approach to nonnormal and nonlinear state-space modeling. Journal of the American Statistical Association 87: pp. 493-500 21459.1992.10475231" target="_blank" title="It opens in new window">CrossRef
  3. Choppala, P., Teal, P., Frean, M.: Particle filter parallelisation using random network based resampling. In: 2014 17th International Conference on Information Fusion (FUSION), pp. 1鈥? (July 2014)
  4. Gong, P., Basciftci, Y., Ozguner, F.: A parallel resampling algorithm for particle filtering on shared-memory architectures. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops PhD Forum (IPDPSW), pp. 1477鈥?483 (May 2012)
  5. Inc., X.: Zynq 7000 all programmable soc. Tech. rep.. (http://www.xilinx.com/products/silicon-devices/soc/zynq-7000.html)
  6. Miao, L., Zhang, J., Chakrabarti, C., Papandreou-Suppappola, A.: A new parallel implementation for particle filters and its application to adaptive waveform design. In: 2010 IEEE Workshop on Signal Processing Systems (SIPS), pp. 19鈥?4 (October 2010)
  7. Mountney, J., Silage, D., Obeid, I.: Parallel field programmable gate array particle filtering architecture for real-time neural signal processing. In: 2010 Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), pp. 2674鈥?677 (August 2010)
  8. Schwiegelshohn, F., Huebner, M.: An application scenario for dynamically reconfigurable fpgas. In: 2014 9th International Symposium on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC), pp. 1鈥? (May 2014)
  9. Thrun, S., Burgard, W., Fox, D.: Probabilistic Robotics, chap. Chapter 4.3 The Particle Filter, pp. 96鈥?12. Intelligent Robotics and Autonomous Agents series, The MIT Press (2006)
  
• 作者单位：Applied Reconfigurable Computing
• 丛书名：978-3-319-16213-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

The particle filter is a nonparametric filter which approximates the posterior system state through a finite number of state samples i.e. particles drawn from a probability distribution. It consists of three steps which are motion update, sensor update and resampling. The first two steps are easily parallelized since the calculations do not depend on other particles. The resampling step however requires all particles to determine the particle set for the next iteration of the particle filter. In this paper, we introduce a novel FPGA optimized resampling (FO-resampling) approach to solve the parallelization problem of the resampling step by introducing virtual particles. Compared to multinomial resampling, FO-resampling achieves similar results with the added benefit of being able to completely parallelize all the steps of the particle filter. Additional to evaluating our approach with simulations, we implement a particle filter with FO-resampling on an FPGA.