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
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
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
What is the probability of observing a particular state say
How would this probability change if we make a measurement
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
In step 2 we are going to update our initial state prediction probability because we have a measurement
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
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:
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
Compute their probability using (3)
Make the sensor measurement
Update the probability of each state using (4)
Choose the state with the highest value for (4) and then that state which will be used to generate possible states in step 1.
Go to step 1.
For the system to work properly, we need to know two PDFs
If the measurement noise and system noise are Gaussian then we have a simplified optimal particle filter called the Kalman filter.