Variable Resolution Particle Filter

Vandi Verma, Sebastian Thrun, and Reid Simmons
In Proceedings of International Joint Conference on Artificial Intelligence, August, 2003.


Download
  • Adobe portable document format (pdf) (227KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Keywords
Fault diagnosis, particle filters, abstraction

Notes
Associated Center(s) / Consortia: Field Robotics Center
Associated Lab(s) / Group(s): Robot Learning Lab and Reliable Autonomous Systems Lab

Text Reference
Vandi Verma, Sebastian Thrun, and Reid Simmons, "Variable Resolution Particle Filter," In Proceedings of International Joint Conference on Artificial Intelligence, August, 2003.

BibTeX Reference
@inproceedings{Verma_2003_4566,
   author = "Vandi Verma and Sebastian Thrun and Reid Simmons",
   title = "Variable Resolution Particle Filter",
   booktitle = "In Proceedings of International Joint Conference on Artificial Intelligence",
   publisher = "AAAI",
   month = "August",
   year = "2003",
}