Scribd
Upload
25 views2 pages

Rao-Blackwell Particle Filtering Tutorial

This tutorial describes Rao-Blackwellised Particle Filtering (RBPF) using a dynamic Bayesian network model of a space probe. The model has 3 variables that change over time: position, velocity, and acceleration, with acceleration depending on an unobserved variable representing mechanical glitches. Exact computation is intractable as the number of possibilities grows exponentially over time. Particle filtering reduces computations by combining particles into weights, resampling from the weighted particles. RBPF further improves efficiency by identifying variables like position and velocity that can be determined by sampling just acceleration, reducing the dimensionality of each sample.

Uploaded by

jai_haas06
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
25 views2 pages

Rao-Blackwell Particle Filtering Tutorial

This tutorial describes Rao-Blackwellised Particle Filtering (RBPF) using a dynamic Bayesian network model of a space probe. The model has 3 variables that change over time: position, velocity, and acceleration, with acceleration depending on an unobserved variable representing mechanical glitches. Exact computation is intractable as the number of possibilities grows exponentially over time. Particle filtering reduces computations by combining particles into weights, resampling from the weighted particles. RBPF further improves efficiency by identifying variables like position and velocity that can be determined by sampling just acceleration, reducing the dimensionality of each sample.

Uploaded by

jai_haas06
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

John Bevilacqua / Brenda Ng

Tutorial: Rao-Blackwell Particle Filtering


Introduction
This tutorial describes how to apply Rao-Blackwellised Particle Filtering (RBPF) to a
dynamic Bayesian network (DBN). It will use a model of a space probes state in order
to provide several examples of concepts.

The model:

We model the probes state using a DBN consisting of 3 variables that can be sampled:
position (P), velocity (V), and acceleration (A). In this system, time (T) is an observed
variable. The system has the following dependencies:

At+1=f(At, q)
Vt+1=f(Vt, At)
Pt+1 = f(Pt, Vt) = f(Pt, At)

Where q is a variable that can only be analyzed probabilistically (eg. a possible


undetected mechanical glitch, undetected collision with an object, etc.)

If we attempt to keep track of the probes position taking all possibilities into account, the
number of possible predictions will increase exponentially with time.

Methods for analyzing this system

Exact Computation:

Exact computation will perform a projection on every sample. If there are X possible
outcomes, each sample will generate X possibilities. This will result in there being Xt
samples. The computational cost of any system will increases exponentially with the
complexity of the system, making the problem quickly computationally intractable.
Particle Filtering:

One way to reduce the computational cost of the problem is to reduce the number of
samples that we analyze. Particle filtering essentially combines the particles at a
particular position into a single particle, giving that particle a weight to reflect the
number of particles that were combined to form it. This eliminates the need to perform
redundant computations without skewing the probability distribution. Particle filtering
accomplishes this by sampling the system to create N particles, then comparing the
samples with each other to generate an importance weight. After normalizing the
weights, it resamples N particles from the system using these weights. This process
greatly reduces the number of particles that must be sampled, making the system much
less computationally intensive.

Rao-Blackwellised Particle Filtering:

An additional way to improve our computational efficiency is to reduce the complexity of


each sample. If we sample 2 variables instead of 3, then we will reduce the number of
dimensions in the system. RBPF reduces the number of variables that must be sampled
by identifying variables that do not need to be sampled to be computed. In the case of the
model proposed above, RBPF would marginalize out P and V because they can be
determined by sampling A. This optimization enables RBPF to perform significantly
better than simple PF for a particular computational cost. The more that a network can be
broken down into subnetworks, the greater performance increase will be.

References:

A Simple Tutorial on RBPF for DBNs


Arnaud Doucet, Nando de Freitas, Kevin Murphy, & Stuart Russel
Tutorial provided with UAI2000 paper

Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks


Arnaud Doucet, Nando de Freitas, Kevin Murphy, & Stuart Russel
Technical Report(2000)

You might also like