Particle Filters in Non-parametric Systems
undefined
Non-parametric Filters: Particle Filters
10/1/2024
1
Particle Filter
10/1/2024
2
Kalman-like filter – all densities are Gaussian
histogram filter – represent density as histogram over the
entire domain of the state
particle filter – represent density as a (large) set of samples
drawn from the density
samples are called particles
each particle is a concrete instantiation of the state
at time
t
Particle Filter
10/1/2024
3
Particle Filter Localization
10/1/2024
4
consider a robot moving down a hall equipped with a sensor
that measures the presence of a door beside the robot
the pose of the robot is simply its location on a line down the
middle of the hall
the robot starts out having no idea how far down the hallway it is
located
robot has a map of the hallway showing it where the doors are
very similar (and very well done) example here:
https://www.youtube.com/watch?v=aUkBa1zMKv4
Particle Filter Localization
10/1/2024
5
the robot starts out having no idea how far down the hallway
it is located
particles
with equal weights
are randomly drawn from a uniform state
density
•
height of particle is proportional to its weight
•
the weights are called
importance weights
Particle Filter Localization
10/1/2024
6
because the robot is beside a door, it has a measurement
it can incorporate this measurement into its state estimate
particles are reweighted based on how consistent each particle is
with the measurement
low weight
low weight
low weight
Particle Filter Localization
10/1/2024
7
the existing particles are resampled with replacement where
the probability of drawing a particle is proportional to its
importance weight
•
resampling produces a set of particles with equal importance weights that
approximates the density
•
the resampled set usually contains many duplicate particles (those with high
importance weights)
•
the resampled set will be missing many particles from the original set (those
with low importance weights)
Particle Filter Localization
10/1/2024
8
the particles are projected forward in time using the motion
model
Particle Filter Localization
10/1/2024
9
because the robot is beside a door, it has a measurement
it can incorporate this measurement into its state estimate
particles are reweighted based on how consistent each particle is
with the measurement
Particle Filter Localization
10/1/2024
10
the existing particles are resampled with replacement where
the probability of drawing a particle is proportional to its
importance weight
Particle Filter Localization
10/1/2024
11
the particles are projected forward in time using the motion
model
Particle Filter Localization Algorithm
10/1/2024
12
1.
algorithm pf_localization( )
2.
empty set
3.
for
m
= 1
to
M
4.
sample_motion_model( )
5.
measurement_model( )
6.
7.
endfor
8.
resample ( )
9.
return
set of particles
control input
measurement
map
Resampling Algorithm
10/1/2024
13
1.
algorithm resample( )
2.
for
m
= 1
to
M
3.
draw
i
with probability
4.
add to
5.
endfor
6.
return
Drawing Particles
10/1/2024
14
compute this
then this
then generate
M
random number uniformly distributed between
0
and
1
Drawing Particles
10/1/2024
15
find the first normalized sum
entry that this is less than
•
this algorithm is known as “roulette wheel sampling/selection”
•
inefficient as it requires generating M random numbers and M binary searches
•
“stochastic universal sampling” is often used instead
Sampling Variance
10/1/2024
16
an important source of error in the particle filter is the
variation caused by random sampling
whenever a finite number of samples is drawn from a
probability density, the statistics extracted from the samples
will differ slightly from the statistics of the original density
e.g., if you draw 2 samples from a 1D Gaussian and compute the
mean and variance you will probably get a different mean and
variance from the original probability density
however, if you draw 100 samples then the mean and variance will probably
be very close to the correct values
Sampling Variance
10/1/2024
17
Resampling Issues
10/1/2024
18
there are many issues related to resampling and how to
perform good resampling
notice that resampling as we have described it causes some
particles to be eliminated and some to be duplicated
continuous resampling will eventually cause all of the particles to be
duplicates of a small number of states
some PF implementations will add a small amount of noise to the
particles so that they are not exact duplicates
Particle Deprivation
10/1/2024
19
it may happen that there are no particles near the correct
state
this can happen because of the variance in random sampling
an unlucky series of random numbers can wipe out all of the particles near
the correct state
when this occurs the filter estimate can become arbitrarily incorrect
occurs mostly when the number of particles is too small for
the dimensionality of the state
Particle filters, also known as non-parametric filters, are a powerful tool for state estimation in dynamic systems. These filters represent density using a set of samples drawn from the density, known as particles. Through resampling and reweighting, particle filters track the state of a system over time, making them especially useful for localization tasks where uncertainties exist. By incorporating measurements and adjusting particle weights, these filters help in estimating the state of a system accurately.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Non-parametric Filters: Particle Filters 1 10/1/2024
Particle Filter Kalman-like filter all densities are Gaussian histogram filter represent density as histogram over the entire domain of the state particle filter represent density as a (large) set of samples drawn from the density samples are called particles = ] 1 [ t x ] 2 [ t [ t ] M : , , ..., x x t [ t ] xm 1 , , m M each particle is a concrete instantiation of the state at time t 2 10/1/2024
Particle Filter 3 10/1/2024
Particle Filter Localization consider a robot moving down a hall equipped with a sensor that measures the presence of a door beside the robot the pose of the robot is simply its location on a line down the middle of the hall the robot starts out having no idea how far down the hallway it is located robot has a map of the hallway showing it where the doors are very similar (and very well done) example here: https://www.youtube.com/watch?v=aUkBa1zMKv4 4 10/1/2024
Particle Filter Localization the robot starts out having no idea how far down the hallway it is located particles with equal weights are randomly drawn from a uniform state density height of particle is proportional to its weight the weights are called importance weights 5 10/1/2024
Particle Filter Localization because the robot is beside a door, it has a measurement it can incorporate this measurement into its state estimate particles are reweighted based on how consistent each particle is with the measurement low weight low weight low weight 6 10/1/2024
Particle Filter Localization the existing particles are resampled with replacement where the probability of drawing a particle is proportional to its importance weight resampling produces a set of particles with equal importance weights that approximates the density the resampled set usually contains many duplicate particles (those with high importance weights) the resampled set will be missing many particles from the original set (those with low importance weights) 7 10/1/2024
Particle Filter Localization the particles are projected forward in time using the motion model 8 10/1/2024
Particle Filter Localization because the robot is beside a door, it has a measurement it can incorporate this measurement into its state estimate particles are reweighted based on how consistent each particle is with the measurement 9 10/1/2024
Particle Filter Localization the existing particles are resampled with replacement where the probability of drawing a particle is proportional to its importance weight 10 10/1/2024
Particle Filter Localization the particles are projected forward in time using the motion model 11 10/1/2024
Particle Filter Localization Algorithm algorithm pf_localization( ) empty set for m = 1 toM sample_motion_model( ) measurement_model( ) endfor resample ( ) return , , , u z m 1. 1 t t t = = 2. t t 3. = [m ] tx [ t ] m , , u tx x t 4. 1 m [ ] m = [m ] , z t w 5. t = + [, t x ] [ t ] m m w 6. t t 7. t set of particles t = t 8. u control input t t 9. z measurement t m map 12 10/1/2024
Resampling Algorithm algorithm resample( ) for m = 1 toM draw i with probability add to endfor return 1. 2. [m ] w 3. [i ] x 4. 5. 6. 13 10/1/2024
Drawing Particles compute this then this i importance weights cumulative sum normalized sum 1 2 3 4 5 6 7 8 9 0.0846 0.0769 0.0895 0.4486 0.9505 0.6019 0.1720 0.2853 0.0301 0.8567 0.0846 0.1615 0.2510 0.6995 1.6500 2.2519 2.4239 2.7092 2.7393 3.5960 0.0235 0.0449 0.0698 0.1945 0.4588 0.6262 0.6740 0.7534 0.7618 1.0000 10 then generate M random number uniformly distributed between 0 and 1 14 10/1/2024
Drawing Particles find the first normalized sum entry that this is less than i importance weights cumulative sum normalized sum random numbers particle 1 2 3 4 5 6 7 8 9 0.0846 0.0769 0.0895 0.4486 0.9505 0.6019 0.1720 0.2853 0.0301 0.8567 0.0846 0.1615 0.2510 0.6995 1.6500 2.2519 2.4239 2.7092 2.7393 3.5960 0.0235 0.0449 0.0698 0.1945 0.4588 0.6262 0.6740 0.7534 0.7618 1.0000 0.5261 0.5154 0.8847 0.0286 0.3836 0.5928 0.4528 0.3306 0.5034 0.7134 6 6 10 2 5 6 5 5 6 8 10 this algorithm is known as roulette wheel sampling/selection inefficient as it requires generating M random numbers and M binary searches stochastic universal sampling is often used instead 15 10/1/2024
Sampling Variance an important source of error in the particle filter is the variation caused by random sampling whenever a finite number of samples is drawn from a probability density, the statistics extracted from the samples will differ slightly from the statistics of the original density e.g., if you draw 2 samples from a 1D Gaussian and compute the mean and variance you will probably get a different mean and variance from the original probability density however, if you draw 100 samples then the mean and variance will probably be very close to the correct values 16 10/1/2024
Sampling Variance 17 10/1/2024
Resampling Issues there are many issues related to resampling and how to perform good resampling notice that resampling as we have described it causes some particles to be eliminated and some to be duplicated continuous resampling will eventually cause all of the particles to be duplicates of a small number of states some PF implementations will add a small amount of noise to the particles so that they are not exact duplicates 18 10/1/2024
Particle Deprivation it may happen that there are no particles near the correct state this can happen because of the variance in random sampling an unlucky series of random numbers can wipe out all of the particles near the correct state when this occurs the filter estimate can become arbitrarily incorrect occurs mostly when the number of particles is too small for the dimensionality of the state 19 10/1/2024
