Variable Resolution Particle Filter
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.
- [Behrends, 2000] E. Behrends. Introduction to Markov Chains with Special Emphasis on Rapid Mixing. Vieweg Verlag, 2000.
- [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.
- [Doucet et al., 2001] A. Doucet, N. de Freitas, and N.J. Gor- don, editors. Sequential Monte Carlo Methods in Practice. Springer-Verlag, 2001.
- PROBABILISTIC INFERENCE [Fox et al., 1999]
- 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.
- [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.
- [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.
- [Kanazawa et al., 1995] K. Kanazawa, D. Koller, and S. Russell. Stochastic simulation algorithms for dynamic probabilistic networks. pages 346-351, 1995.
- [Koller and Fratkina, 1998] D. Koller and R. Fratkina. Us- ing learning for approximation in stochastic processes. In /CML, 1998.
- [Leger, 2000] P.C. Leger. Darwin2K: An Evolutionary Ap- proach to Automated Design for Robotics. Kluwer Aca- demic Publishers, 2000.
- N. Metropolis and S. Ulam. The monte carlo method. volume 44 of Journal of the American Statistical Association, 1949.
- [Ng et al., 2002] B. Ng, L. Peshkin, and A. Pfeffer. Factored particles for scalable monitoring. In VAl, 2002.
- [Rubin, 1988] D. B. Rubin . Using the SIR algorithm to sim- ulate posterior distributions. Oxford University Press, 1988.
- [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.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
A number of problems in AI and robotics require estima tion of the state of a system as it changes over time from a sequence of measurements of the system that provide noisy (partial) information about the state. Particle filters have been extensively used for Bayesian state estimation in nonlinear systems with noisy measurements [Isard and Blake, 1998; Fox eta!., 1999; Doucet eta/., 2001]. The Bayesian approach to dynamic state estimation computes a posterior probability distribution over the states based on the sequence of measure ments. Probabilistic models of the change in state over time (state transition model) and relationship between the mea surements and the state capture the noise inherent in these domains. Computing the full posterior in real time is often intractable. Particle filters approximate the posterior distri bution over the states with a set of particles drawn from the posterior. The particle approximation converges to the true
Variable Resolution Particle Filter
Vandi Verma, Sebastian Thrun and Reid Simmons
Carnegie Mellon University 5000 Forbes Ave. Pittsbugh PA 15217 { vandi, thrun, reids} @cs.cmu.edu
Bayesian posterior in the limit as the number of samples go to infinity. For real-time state estimation it is impractical to have an infinitely large number of particles. With a small number of particles, the variance of the particle based estimate can be high, particularly when there are a large number of possible state transitions.
This paper presents a new particle filter, the variable res olution particle filter (VRPF), for tracking large state spaces efficiently with low computation. The basic idea is to rep resent a set of states 1 rather than a single state with a single particle and thus increase the number of states (or hypothe ses) that may be tracked with the same number of particles. This makes it possible to track a larger number of states for the same computation, but results in a loss of information that differentiates between the states that are lumped together and tracked in abstraction. We formalize this tradeoff in terms of bias and variance. Tracking in abstraction at a coarser res olution introduces a bias over tracking at a finer resolution, but it reduces the variance of the estimator given a limited number of samples. By dynamically varying the resolution in different parts of the state space to minimize the bias-variance error, a finite set of samples are used in a highly efficient man ner. Initial experimental results support our analysis and show that the bias is more than compensated for by the reduction in variance from not eliminating potential hypotheses prema turely for lack of a sufficient number of particles.
2 Bayesian Filtering
We denote the multivariate state at time t as Xt and measure ments or observations as Ot. As is commonly the case, we concentrate on the discrete time, first order Markov formu lation of the dynamic state estimation problem. Hence, the state at time t is a sufficient statistic of the history of mea surements, i.e. p(XtiXo:t-1) = p(XtiXt-1) and the obser vations depend only on the current state, i.e. p(OtiXo:t) = p(OtiXt). In the Bayesian framework, the posterior distribu tion at timet, p(Xo:tiOl:t), includes all the available infor mation upto time t and provides the optimal solution to the state estimation problem. In this paper we are interested in estimating recursively in time a marginal of this distribution, the filtering distribution, p( Xt I 0 1 :t), as the measurements become available. Based on the Markovian assumption, the re cursive filter is derived as follows:
1 or regions of a continuous state space
This process is known as Bayesian filtering, optimal filter ing or stochastic filtering and may be characterized by three distributions: (1) a transition model p(XtiXt-1), (2) an ob servation model p(OtiXt). and, (3) an initial prior distribu tion, p(X0 ). In a number of applications, the state space is too large to compute the posterior in a reasonable time. Par ticle filters are a popular method for computing tractable ap proximations to this posterior.
2.1 Classical Particle Filter
A Particle filter (PF) [Metropolis and Ulam, 1949; Gordon et al., 1993; Kanazawa et al., 1995] is a Monte Carlo ap proximation of the posterior in a Bayes filter. PFs are non parametric and can represent arbitrary distributions. PFs ap proximate the posterior with a set of N fully instantiated state samples or particles, Pt = { xP1 ... x~N]} as follows:
where o(.) denotes the Dirac delta function. It can be shown that as N ---+ oo the approximation in (2) approaches the true posterior density [Doucet and Crisan, 2002]. In general it is difficult to draw samples from, p(XtiOI:t); instead, sam ples are drawn from a more tractable distribution, q(.), called the proposal or importance distribution. Each particle is as signed a weight, wli] to account for the fact that the sam ples were drawn from a different distribution [Rubin, 1988; Rubinstein, 1981]. There are a large number of possible choices for the proposal distribution, the only condition be ing that its support must include that of the posterior. The common practice is to sample from the transition probability, p(Xt1Xt_1), in which case the importance weight is equal to the likelihood, p(Ot IXt). The experiments in this paper were performed using this proposal distribution. The PF algorithm is:
| 1 | set Pt = Plux = 0 |
| 2 | for i = 1 to N do |
| 3 | pick the i-th sample x~~ 1 E Pt-1 |
| 4 | draw x~i] ,...., p(Xtlx~~1 ) |
| 5 | set w~i] = p( Ot lx~i]) |
| 6 | add (x[i] w[i]) to paux t , t t |
| 7 | end |
| 8 | for i = 1 to N do |
| 9 | draw x[i] from paux t t with probability proportional to w~i] |
| 10 | add ~i] to Pt |
| 11 | end |
3 Variable Resolution Particle Filter
A well known problem with particle filters is that a large num ber of particles are often needed to obtain a reasonable ap proximation of the posterior distribution. For real-time state estimation maintaining such a large number of particles is typically not practical. However, the variance of the particle based estimate can be high with a limited number of samples, particularly when the process is not very stochastic and parts of the state space transition to other parts with very low, or zero, probability. Consider the problem of diagnosing loco motion faults on a robot. The probability of a stalled motor is low and wheels on the same side generate similar observa tions. Motors on any of the wheels may stall at any time. A particle filter that produces an estimate with a high variance is likely to result in identifying some arbitrary wheel fault on the same side, rather than identifying the correct fault.
The variable resolution particle filter introduces the notion of an abstract particle, in which particles may represent in dividual states or sets of states. With this method a single abstract particle simultaneously tracks multiple states. A lim ited number of samples are therefore sufficient for represent ing large state spaces. A bias-variance tradeoff is made to dynamically refine and abstract states to change the resolu tion, thereby abstracting a set of states and generalizing the samples or specializing the samples in the state into the indi vidual states that it represents. As a result reasonable poste rior estimates can be obtained with a relatively small number of samples. In the example above, with the VRPF the wheel faults on the same side of the rover would be aggregated to gether into an abstract fault. Given a fault, the abstract state representing the side on which the fault occurs would have high likelihood. The samples in this state would be assigned a high importance weight. This would result in multiple copies of these samples on resampling proportional to weight. Once there are sufficient particles to populate all the refined states represented by the abstract state, the resolution of the state would be changed to the states representing the individual wheel faults. At this stage, the correct hypothesis is likely to be included in this particle based approximation at the level of the individual states and hence the correct fault is likely to be detected.
For the variable resolution particle filter we need: (1) A variable resolution state space model that defines the relation ship between states at different resolutions, (2) an algorithm for state estimation given a fixed resolution of the state space, (3) a basis for evaluating resolutions of the state space model, and (4) and algorithm for dynamically altering the resolution of the state space.
3.1 Variable resolution state space model
We could use a directed acyclic graph (DAG) to represent the variable resolution state space model, which would consider every possible combination of the (abstract)states to aggre gate or split. But this would make our state space exponen tially large. We must therefore constrain the possible com binations of states that we consider. There are a number of ways to do this. For the experiments in this paper we use a multi-layered hierarchy where each physical (non-abstract) state only exists along a single branch. Sets of states with similar state transition and observation models are aggregated together at each level in the hierarchy. In addition to the phys ical state set {Xk}, the variable resolution model , M consists of a set of abstract states { Sj} that represent sets of states and or other abstract states.
Figure 1(a) shows an arbitrary Markov model and figure 1(b) shows an arbitrary variable resolution model for 1(a). Figure 1 (c) shows the model in 1 (b) at a different resolution.
We denote the measurement at time t as Zt and the se quence of measurement z1 ... Zt as zt. From the dynamics, p(xtiXt-1), and measurement probabilitiesp(ztlxt), we com pute the stationary distribution (Markov chain invariant distri bution) of the physical states 1r(xk) [Behrends, 2000].
3.2 Belief state estimation at a fixed resolution
This section describes the algorithm for estimating a distri bution over the state space, given a fixed resolution for each state, where different states may be at different fixed resolu tions. For each particle in a physical state, a sample is drawn from the predictive model for that state p( Xt lxt-d . It is then assigned a weight proportional to the likelihood of the mea surement given the prediction, p(ztlxt)· For each particle in an abstract state, Sj, one of the physical states, Xt·, that it represents in abstraction is selected proportional to the prob ability of the physical state under the stationary distribution, 7r(Xt). The predictive and measurement models for this phys ical state are then used to obtain a weighted posterior sample. The particles are then resampled proportional to their weight. Based on the number of resulting particles in each physical state a Bayes estimate with a Dirichlet(!) prior is obtained as follows:
where, n(xt) represents the number of samples in the physi cal state Xt and I Nt I represents the total number of particles in the particle filter. The distribution over an abstract state Sj at time t is estimated as:
3.3 Bias-variance tradeoff
The loss l, from a particle based approximation p(xtl zt), of the true distribution p(xt lzt) is:
where, b(p(xtl zt)) is the bias and v(p(xtl zt)) is the variance.
The posterior belief state estimate from tracking states at the resolution of physical states introduces no bias. But the variance of this estimate can be high, specially with small sample sizes. An approximation of the sample variance at the resolution of the physical states may be computed as follows:
The loss of an abstract state Sj, is computed as the weighted sum of the loss of the physical states Xt E Sj, as follows 2 :
The generalization to abstract states biases the distribution over the physical states to the stationary distribution. In other words, the abstract state has no information about the relative posterior likelihood, given the data, of the states that it repre sents in abstraction. Instead it uses the stationary distribution to project its posterior into the physical layer. The projection of the posterior distribution p( Sj I zt), of abstract state Sj , to the resolution of the physical layer p(xtlzt), is computed as follows:
where, 1r(Sj) = LxES; 1r(x).
As a consequence of the algorithm for computing the pos terior distribution over abstract states described in section 3.2, an unbiased posterior over physical states Xt is available at no extra computation, as shown in equation (4). The bias b(Sj ), introduced by representing the set of physical states Xt E Sj , in abstraction as Sj is approximated as follows:
It is the weighed sum of the squared difference between the unbiased posterior p(xt lzt), computed at the resolution of the physical states and the biased posterior p( x t I zt), computed at the resolution of abstract state Sj.
An approximation of the variance of abstract state Sj is computed as a weighted sum of the projection to the physical states as follows:
2 The relative importance/cost of the physical states may also be included in the weight

The loss from tracking a set of states Xt E Sj, at the resolu tion of the physical states is thus:
The loss from tracking the same set of states in abstraction as Sj is:
There is a gain in terms of reduction in variance from gener alizing and tracking in abstraction, but it results in an increase in bias. Here, a tradeoff between bias and variance refers to the process of accepting a certain increase in one term for a larger reduction in the other and hence in the total error.
3.4 Dynamically varying resolution
The variable resolution particle filter uses a bias-variance tradeoff to make a decision to vary the resolution of the state space. A decision to abstract to the coarser resolution of ab stract state Sj, is made if the state space is currently at the resolution of states Si. and the combination of bias and vari ance in abstract state Sj, is less than the combination of bias an variance of all its children si. as shown below:
On the other hand if the state space is currently at the reso lution of abstract state Sj, and the reverse of equation (14) is true, then a decision to refine to the finer resolution of states Si is made. The resolution of a state is left unaltered if its bias-variance combination is less than its parent and its chil dren. To avoid hysteresis, all abstraction decisions are con sidered before any refinement decisions.
Each time a new measurement is obtained the distribution of particles over the state space is updated. Since this alters the bias and variance tradeoff, the states explicitly represented at the current resolution of the state space are each evaluated for gain from abstraction or refinement. Any change in the current resolution of the state space is recursively evaluated for further change in the same direction.
4 Experimental results
The problem domain for our experiments involves diagnos ing locomotion faults in a physics based simulation of a six wheel rover. Figure 2(a) shows a snapshot of the rover in the Darwin2K [Leger, 2000] simulator.
The experiment is formulated in terms of estimating dis crete fault and operational modes of the robot from contin uous control inputs and noisy sensor readings. The discrete state, Xt, represents the particular fault or operational mode. The continuous variables, Zt, provide noisy measurements of the change in rover position and orientation. The particle set Pt therefore consists of N particles, where each particle x~i) is a hypothesis about the current state of the system. In other words, there are a number of discrete fault and operational states that a particle may transition to based on the transition model. Each discrete fault state has a different observation and predictive model for the continuous dynamics. The prob ability of a state is determined by the density of samples in that state.
The Markov model representing the discrete state transi tions consists of 7 states. As shown in figure 2(c) the normal driving (ND) state may transition back to the normal driv ing state or to any one of six fault states: right front (RF), right middle (RM), right rear (RR), left front (LF), left mid dle (LM) and left rear (LR) wheel stuck. Each of these faults cause a change in the rover dynamics, but the faults on each side (right and left), have similar dynamics.
Given that the three wheels on each side of the rover have similar dynamics, we constructed a hierarchy that clusters the fault states on each side together. Figure 2(d) shows this hier archical model, where the abstract states right side fault (RS), and left side fault (LS) represent sets of states {RF, RM, RR} and {LF, LM, LR} respectively. The highest level of abstrac tion therefore consists of nodes {ND, RS, LS}. Figure 2(e) shows how the state space in figure 2(d) would be refined if the bias in the abstract state RS given the number of parti cles outweighs the reduction in variance over the specialized states RF, RM and RR at a finer resolution.
When particle filtering is performed with the variable reso lution particle filter, the particles are initialized at the highest level in the abstraction hierarchy,i.e. in the abstract states ND, RS and LS. Say a RF fault occurs, this is likely to result in a high likelihood of samples in RS. These samples will mul tiply which may then result in the bias in RS exceeding the reduction in variance in RS over RF, RM and RR thus favor ing tracking at the finer resolution. Additional observations should then assign a high likelihood to RF.

The model is based on the real-world and is not very stochastic. It does not allow transitions from most fault states to other fault states. For example, the RF fault does not tran sition to the RM fault. This does not exclude transitions to multiple fault states and if the model included multiple faults, it could still transition to a "RF and RM" fault, which is dif ferent from a RM fault. Hence, if there are no samples in the actual fault state, samples that end up in fault states with dynamics that are similar to the actual fault state may end up being identified as the fault state. The hierarchical approach tracks the state at an abstract level and does not commit to identifying any particular specialized fault state until there is sufficient evidence. Hence it is more likely to identify the correct fault state.
Figure 3(a) shows a comparison of the error from moni toring the state using a classical particle filter that tracks the full state space, and the VRPF that varies the resolution of the state space. The X axis shows the number of particles used, the Y axis shows the KL divergence from an approxi mation of the true posterior computed using a large number of samples. 1000 samples were used to compute an approxima tion to the true distribution. The KL divergence is computed over the entire length of the data sequence and is averaged over multiple runs over the same data set 3 . The data set in cluded normal operation and each of the six faults. Figure 3(a) demonstrates that the performance of the VRPF is superior to that of the classical filter for small sample sizes. In addition figure 3(b) shows the Kl-divergence along theY axis and wall clock time along the X axis. Both filters were coded in matlab and share as many functions as possible.
3 The results are an average over 50 to 5 runs with repetitions decreasing as the sample size was increased.
5 Discussion and Future Work
This paper presents a novel approach for state abstraction in particle filters that allows efficient tracking of large discrete, continuous or hybrid state spaces. The advantage of this ap proach is that it makes efficient use of the available computa tion by selecting the resolution of the state space based on an explicit bias-variance tradeoff. It performs no worse than a classical particle filter with an infinite number of particles 4 . But with limited particles we show that its performance is considerably superior. The VRPF does not prematurely elim inate potential hypotheses for lack of a sufficient number of particles. It maintains particles in abstraction until there are a sufficient number of particles to provide a low variance esti mate at a lower resolution.
The VRPF generalizes from current samples to unsampled regions of the state space. Regions of the state space that had no samples at time t may acquire samples at time t + 1 on abstraction. This provides additional robustness to noise that may have resulted in eliminating a likely hypothesis. [Koller and Fratkina, 1998] addresses this by using the time t sam ples as input to a density estimation algorithm that learns a distribution over the states at timet. Samples at timet+ 1 are then generated using this generalized distribution. [Ng et al., 2002] uses a factored representation to allow a similar mix ing of particles. The VRPF uses a bias-variance tradeoff to generalize more selectively and efficiently.
We have presented the variable resolution particle filter for a discrete state space. We plan to extend it to a continuous state space where regions of state space, rather than sets of states are maintained at different resolutions. A density tree may be used for efficiently learning the variable resolution state space model with abstract states composed of finitely many sub-regions.
4 There is a minor overhead in terms of evaluating the resolution of the state space

The VRPF makes efficient use of available computation and can provide significantly improved posterior estimates given a small number of samples. However, it should not be expected to solve all problems associated with particle im poverishment. For example, it assumes that different regions of the state space are important at different times. We have generally found this to be the case, but the VRPF does not im prove performance if it is not. Another situation is when the transition and observation models of all the states are highly dissimilar and there is no possibility for state aggregation.
6 Acknowledgments
We would like to thank Geoff Gordon, Tom Minka and the anonymous reviewers.
@inproceedings{ijcai2003p140,
title = {Variable Resolution Particle Filter},
author = {Verma, Vandi and Thrun, Sebastian and Simmons, Reid G.},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob and Toby Walsh},
pages = {976--983},
year = {2003},
url = {https://ijcai.org/proceedings/2003/140},
}
TY - CPAPER TI - Variable Resolution Particle Filter AU - Verma, Vandi AU - Thrun, Sebastian AU - Simmons, Reid G. T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 976 EP - 983 UR - https://ijcai.org/proceedings/2003/140 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: