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.