Proceedings

Variable Resolution Particle Filter

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 976-983.

© 2003 International Joint Conferences on Artificial Intelligence

Abstract

Particle filters are used extensively for tracking the state of non-linear dynamic systems. This paper presents a new particle filter that maintains samples in the state space at dynamically varying resolution for computational efficiency. Resolution within statespace varies by region, depending on the belief that the true state lies within each region. Where belief is strong, resolution is fine. Where belief is low, resolution is coarse, abstracting multiple similar states together. The resolution of the statespace is dynamically updated as the belief changes. The proposed algorithm makes an explicit bias-variance tradeoff to select between maintaining samples in a biased generalization of a region of state space versus in a high variance specialization at fine resolution. Samples are maintained at a coarser resolution when the bias introduced by the generalization to a coarse resolution is outweighed by the gain in terms of reduction in variance, and at a finer resolution when it is not. Maintaining samples in abstraction prevents potential hypotheses from being eliminated prematurely for lack of a sufficient number of particles. Empirical results show that our variable resolution particle filter requires significantly lower computation for performance comparable to a classical particle filter.

  1. [Behrends, 2000] E. Behrends. Introduction to Markov Chains with Special Emphasis on Rapid Mixing. Vieweg Verlag, 2000.
  2. [Doucet and Crisan, 2002] A. Doucet and D. Crisan. A sur- vey of convergence results on particle filtering for practi- tioners. IEEE Trans. Signal Processing, 2002.
  3. [Doucet et al., 2001] A. Doucet, N. de Freitas, and N.J. Gor- don, editors. Sequential Monte Carlo Methods in Practice. Springer-Verlag, 2001.
  4. PROBABILISTIC INFERENCE [Fox et al., 1999]
  5. D. Fox, W. Burgard, and S. Thrun. Markov localization for mobile robots in dynamic environments. In Journal of Artificial Intelligence, volume 11, pages 391- 427, 1999.
  6. [Gordon et al., 1993] N.J. Gordon, D.J Salmond, and A.F.M Smith. Novel approach to nonliner/non gaussian bayesian state estimation. volume 140 of lEE Proceedings-F. pages 107-113, 1993.
  7. [Isard and Blake, 1998] M. Isard and A. Blake. Conden- sation: conditional density propagation for visual track- ing. International Journal of Computer Vision, 29(1):5- 28, 1998.
  8. [Kanazawa et al., 1995] K. Kanazawa, D. Koller, and S. Russell. Stochastic simulation algorithms for dynamic probabilistic networks. pages 346-351, 1995.
  9. [Koller and Fratkina, 1998] D. Koller and R. Fratkina. Us- ing learning for approximation in stochastic processes. In /CML, 1998.
  10. [Leger, 2000] P.C. Leger. Darwin2K: An Evolutionary Ap- proach to Automated Design for Robotics. Kluwer Aca- demic Publishers, 2000.
  11. N. Metropolis and S. Ulam. The monte carlo method. volume 44 of Journal of the American Statistical Association, 1949.
  12. [Ng et al., 2002] B. Ng, L. Peshkin, and A. Pfeffer. Factored particles for scalable monitoring. In VAl, 2002.
  13. [Rubin, 1988] D. B. Rubin . Using the SIR algorithm to sim- ulate posterior distributions. Oxford University Press, 1988.
  14. [Rubinstein, 1981] R. Y. Rubinstein. Simulation and Monte Carlo method. In John Wiley and Sons, 1981.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards