Particle Filtering

A brief introduction on particle filtering – a.k.a stochastic filters.

We will start with our problem statement

In some engineering applications we would like to track the state of a complicated machine whose dynamics evolves with time

. Typical example for such a system would be the tracking of position, speed and acceleration of a motor vehicle or a smart oven with temperature control etc. Depending on the dynamics of the system, there will be a function that defines how the state of the system changes over time. For e.g. if a vehicle is travelling at constant velocity,  for a small duration of time dt the position of the motor vehicle gets updated as

. In general we could assume that for our hypothetical system there exists a function

that takes as input the state of the system at time t-1 represented by

and the system noise at time t-1 represented by

and transform it to state of the system at time t represented by

as

                       (1)

Typically, an engineering systems will have sensors that provide feedback about the system’s current state. For e.g. for a vehicle it would be a speedometer or an accelerometer that measures the instantaneous velocity or acceleration respectively of the vehicle.  Assume that for our hypothetical system these sensor measurements are represented by

. Let  

be the function that relates the current sensor measurement to the current state represented by

and the current measurement noise represented by

then

                                 (2)

This completes our problem setup. Now I will list the some engineering assumptions made for our hypothetical system.

As an engineer, we are supposed to simplify the problem by making some realistic assumptions. For our system, the first equations essentially states that the state at time t depends only on the previous state at time t-1 and the system noise at time t-1. We could have relaxed this assumption and conjure a complicated system where the dynamics depends not just on the state at time t-1 but t-2, t-3 etc. However, that would be for another time. Systems that satisfies our simplified assumption is called a first order markov system.

For the second equation, the assumption is that the sensor measurements depends only on the current state and measurement noise. Again, we could have a complicated system where this relationship might not satisfy. But again we are engineers and not mathematicians and our objective is to realize a practical system using reasonable assumptions.

Now for our hypothetical system we are interested in measuring the state of the system before and after a measurement is made. Specifically we are interested in answering the following questions

1. What is the probability of observing a particular state say

at time t given all the measurements from time T=1 to T=t-1 i.e.

is available?

1.  How would this probability change if we make a measurement

at time t?

In step 1 we are essentially predicting the probability of a particular state and is given by

Applying our assumption from equation 1 i.e. if the state at time t-1 is available then the state at time t is completely defined by it resulting in

. Therefore our state prediction probability is

  (3)

In step 2 we are going to update our initial state prediction probability because we have a measurement

available from the sensor. Now this additional information should change our initial state probabilities.  The updated state prediction probability in light of this added information is given by

Applying our second assumption in equation 2 i.e. if the measurement at time t is fully defined by state at time t then $latex P\left(z_t|x_t,z_{1:t-1}\right) = P\left(z_t|x_t\right)$. Therefore

  (4)

Now we have answered the above questions and we are in a position to apply those answers for our filtering.

The filtering loop is as follows:

1. Generate a set of possible states given the current state or if we are starting for the first time use the initial state supplied by the designer

2. Compute their probability using (3)

3. Make the sensor measurement

4. Update the probability of each state using (4)

5. Choose the state with the highest value for (4) and then that state which will be used to generate possible states in step 1.

6. Go to step 1.

For the system to work properly, we need to know two PDFs

PDF of System Dynamics noise (Sn)

PDF of Measurement noise (Mn)

If the measurement noise and system noise are Gaussian then we have a  simplified optimal particle filter called the Kalman filter.

#posterior #kalman #distribution #filtering #gaussian