University of Washington Department of Computer Science & Engineering
Mobile Robotics Research Labratory

Project Faculty
    D. Fox
    M. Meila
Graduate students
    C. Kwok

C. Kwok, D. Fox and M. Meila

Real-time particle filters

Technical Report UW-CSE-02-07-01
A shorter version has been accepted for publication at NIPS 2002.



Particle filters estimate the state of dynamical systems from sensor information. In many real time applications of particle filters, however, sensor information arrives at a significantly higher rate than the update rate of the filter. The prevalent approach to dealing with such situations is to update the particle filter as often as possible and to discard sensor information that cannot be processed in time. In this paper we present real-time particle filters, which make use of all sensor information even when the filter update rate is below the update rate of the sensors. This is achieved by distributing samples among the different observations arriving during a filter update. Hence the approach represents posteriors by mixtures of sample sets. The weights of the mixture components are set so as to minimize the approximation error introduced by the mixture representation. Minimization is achieved by gradient descent using efficient Monte Carlo approximation of the gradients. Thereby, our approach focuses computational resources (samples) on valuable sensor information. Experiments using data collected with a mobile robot show that our approach yields strong improvements over other approaches.


Full paper [.ps.gz] (340 kb, 12 pages)


The following animations illustrate how the real time particle filters work.

The environment is an office floor 54x18m2. The robot moves around the loop on the left, which is symmetrical except for a few boxes placed as "landmarks" along the walls. The dots in the animations represent the samples, blue beams represent the laser sensor measurements, and the circle represents the true robot position. All sample sets in an estimation window are shown together in different colors. At the end of each estimation window, the mixture weights of these sets are computed and used for the next estimation window (see report). Typically, the observations detecting the boxes get very high weights, due to their high information content.

  • Fixed window size 6
  • Adaptive window - this animation shows our work-in-progress adaptive window algorithm. In the beginning we start with 12 sample sets in a window, but as time goes by, the robot is more certain about its position and requires less samples to approximate the distribution, hence a smaller window size is required. In the end one sample set is all it needs.

Back to the MCL Home

CSE logo Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to]