Particle filter

Question 1

Particle Filter

Answer 1

The idea of the particle filter (PF: Particle Filter) is based on Monte Carlo methods, which use particle sets to represent probabilities and can be used in any form of state space model. The core idea is to express its distribution by extracting random state particles from the posterior probability.
* Particle Filters
* One particle represents a possible state matrix xt
* Many particles represent the believe of the robot χt

Question 2

χ

Answer 2

χ is the believe of the robot expressed as the distribution of particles (i.e. a particle matrix)

Question 3

input χt−1 , ut , zt

Answer 3

χt−1 : prior believe, algorithm will produce posterior χt
ut : update matrix (actions with unpredictable effect)
zt : observation matrix (noisy observations)

Question 4

χ̄t = χt = 0

Answer 4

Prepare two empty particle collisions
χ̄t : to store the predicted particles
χt : to store the final result

Question 5

for m = 1 to M do

Answer 5

Iterate over the M particles in χt−1

Question 6

// Control update
[m] [m]
x t ∼ p ( x t | u t , x t −1 )

Answer 6

for particle m:
* calculate probability distribution for state xt given update ut and
[m]
previous state xt−1 )
[m]
* draw one state xt from this distribution

Question 7

// Measurement update van χt !!
[m] [m]
wt = p(zt | xt )

Answer 7

Calculate weight wt for particle m based upon how likely zt is from state xt at particle m.
Based upon the definition of a probability distribution, weights are in [0,1].

Question 8

[m] [m]
χ t = χ t + h x t , wt i

Answer 8

Add the particle and its weight to collection of predictions χ̄t .

Question 9

endfor

Answer 9

End of first loop

Question 10

// Resample the space
for m = 1 to M do

Answer 10

Visit the collection of particle-weight pairs χ̄t M times.

Question 11

[m] [m]
draw xt from χt with probability ∝ wt or draw i with probability ∝ wt

Answer 11

Draw with repetition a particle from χ̄t considering its weight. Store this particle in i.
Many particles with relatively high weights will be drawn several times!
Mind, the image shows two steps at once:
* you see the result of the election (three areas with dense particles).
* you see the effect of the robot moving two meters to the right.

Question 12

// Construeer χt
[m]
χt = χt + xt

Answer 12

Add the selected particles to χt as it weight is no longer needed.

Question 13

endfor
return χt

Answer 13

We’ve done it! return Xt (the final result)