Particle Filters: A literature survey
Shreyash Palande (4842766), Vishwas Iyer (4815874), Raoul Mink (4207491), Adarsh Pattanayak (4784553)
Knowledge based control systems (SC42050)
Group 34
Abstract—During the last two decades there has been a
significantly growing interest in Particle Filtering (PF). This
paper provides a literature survey on particle filters, various
particle filtering methods, their properties and their applications.
We start off by knowing abut the developments over time and
the various applications and regions particle filters are used in. A
detailed discussion on the basic particle filter algorithm follows.
One of the main outlines of this paper is the the trade off
between the problem of degeneracy and particle impoverishment.
Various methods that were used to overcome them have been
discussed and emphasis has been laid on the dynamic resampling
approach. A Sampling Importance Resampling (SIR) filter is
later implemented for a dynamical robot equation discussing the
importance of parameters like kernel density, kernel bandwidth
and a slight insight into Regularized Particle Filter (RPF).
Index Terms—Particle filters, SIR filters. SIS filters, RPF
particle filter",sequential Monte Carlo, tracking.
I. INTRODUCTION
One of the key developments in robotics has been the
adoption of probabilistic techniques, which is a huge leap
from the paradigm of model-based approaches. Earlier, re-
searchers focused on control problems under the assumption
of fully modeled, deterministic robots and robot environments.
Since the mid-1990s, robotics has shifted its focused towards
techniques that utilize imperfect models and that incorporate
imperfect sensor data. An important paradigm since the mid-
1990s whose origin can easily be traced back to the 1960s is
that of probabilistic robotics. Probabilistic robotics integrates
imperfect models and imperfect sensors through probabilistic
laws, the prominent one being Bayes rule [1]. With this came
the concept of Bayes Filter. The Bayes filter is a general
algorithm for estimating a belief given control commands and
observations.
In Bayesian approach to dynamic state estimation attempts
are made to construct the posterior probability density function
(pdf) of the state based on all the information available which
also includes the set of measurements from the sensors. Since
the pdf embodies all the statistical information it is a complete
solution to state estimation problem. For many problems an es-
timate is required every time that a measurement is received. In
this case, a recursive filter is a convenient solution. A recursive
filtering approach means that received data can be processed
sequentially rather than as a batch so that it is not necessary
to store the complete data set nor to reprocess existing data if
a new measurement becomes available. Such approach needs
two stages: prediction and update. The prediction stage uses
the system model to predict the state pdf of one time step
ahead. Due to unknown disturbance and random noise the
certainty reduces and the variance of the pdf increases. The
update stage uses the latest measurements to modify the state
prediction pdf. This is achieved using Bayes rule. This paper
focuses on the particle filter - its working and applications.
The particle filter is an implementation of the Bayes filter.
In recent years with the rise in autonomous robot technology
the main problem arises is to localize them in the unknown
environment. The particle filters were used to solve problems
like global localization and kidnapped robot problem. With a
given map of the environment it is possible to recover the
robot pose which led to increase in robustness of mobile
robots. Other methods are also present like Kalman filtering",
but when the probability distribution is non Gaussian and
non linear, particle filters are used to solve the problem of
state estimation. Particle filters are now used to solve higher
dimension problems. One such example is the simultaneous
localization and mapping problem (SLAM), which is a state
estimation problem of mobile robots for variable number of
dimension. FastSLAM which uses particle filter algorithm
has been able to solve problems with more than 100",000
dimensions in real time [4]. Other techniques have been
developed for robustly tracking moving entities such as people
in the proximity of robot [5] [6].
There have been several developments in Reconstructing 3D
Video Using Particle Filtering by universities like University
of Michigan, Carnegie Mellon University. Also research and
developments have been made by the University of South
China in the field of improved object tracking [17]. Formula
student team Delft driverless and teams from other universities
like ETH Zurich, MIT are using FastSLAM approach for
simultaneous localization and mapping of autonomous race
vehicles. [18]. Hybridization techniques are used for integra-
tion of the Global Positioning System (GPS) and the inertial
navigation systems (INS) to increase navigation performance.
Researchers from IRIT-ENSEEIHT, France are using an im-
proved regularized particle filter for GPS/INS integration [19].
II. THE PARTICLE FILTER
Like the Bayes filter, the particle filter allows for main-
taining a probability distribution that is updated based on the
commands that are executed by the robot and based on the
observations that the robot acquires. The particle filter is a non-
parametric Bayes filter as it presents the belief not in closed
form but using a finite number of parameters. It models the
belief by samples, which represent possible states the system
might be in [2].
The key idea of the particle filter is to represent the posterior
bel(xk) by a set of random state samples drawn from this
posterior. Particle filters represent a distribution by a set of
samples drawn from this distribution. The particle filter allows
us to recursively estimate the particle set Xk based on the
estimate Xk−1 of the previous time step. Ideally, the likelihood
for a state hypothesis xk to be included in the particle set Xk
shall be proportional to its Bayes filter posterior bel(xk):
x
[m]
k ∼ p(xk|z1:k, u1:k) (1)
The input of the above is the particle set Xk−1, along with
the most recent control uk and the most recent measurement
zk. The denser a sub-region of the state space is populated
by samples, the more likely it is that the true state falls into
this region [7]. Let us consider p(x) and π(x) as the target
distribution and proposal distribution respectively. In general",
the target probability distribution p(x) for sampling particles
is not known or not in a suitable form for sampling. It is",
however, possible to draw the samples from a distribution
π(x) that is different from the distribution p(x) that we
want to approximate. This can be achieved by Importance
Sampling. There obviously will be differences between the two
distributions and hence weights are assigned to each sample
that considers the difference between π and p. This step is
known as Importance Weighting. The importance weighting
step accounts for the fact that one draws from the proposal π
by setting the weight of each particle to:
w
[i]
k = η
p(x
[i]
k )
q(x
[i]
k )
(2)
where η is a normalizer that ensures that the weights sum up
to 1. The samples are re-weighed to consider the differences
between p and π.
Fig. 1. Sample degeneracy and impoverishment
The problem faced if the filter stops here is the problem
of degeneracy. This means that after a few iterations, all
particles except one will have negligible weight. It has been
shown [8] that variance of importance weights can only be
increased over time which makes it impossible to avoid the
degeneracy problem [9]. The degeneracy means that a large
amount of computation is required to update the particles
whose contributions to the approximation p(xk|z1:k) is al-
most zero. To solve the degeneracy problem, Resampling is
introduced. Resampling refers to drawing N samples from the
weighted sample set with replacement and resetting all weights
in the new sample set to 1/N. Particles with less weights do
not contribute significantly to the approximation p(xk|z1:k).
Resampling casts out such particles and hence reduces di-
versity. This however, gives rise to a new problem which is
particle impoverishment. Fig.1 shows Sample degeneracy and
impoverishment in 1-dimensional state space.
Sample degeneracy is result of particles being distributed
too widely while the sample impoverishment can be viewed
as a particle being over concentrated. The degeneracy leads to
impoverishment as a result of resampling. Sample degeneracy
and impoverishment are a pair of contradictions that can
be collectively described as a trade-off between the need of
diversity and the need of focus in, as a problem in managing
the spread of the particle set in the state space to balance
conflicting requirements in, or in another perspective, as the
computing resource converging prematurely either by weight
or by state in.
Several methods have been mentioned which tend to make
a trade of between degeneracy and particle impoverishment by
using additional Markov Chain Monte Carlo [11], evolutionary
algorithms were incorporated into PF to prevent the particle
impoverishment [12]. The auxiliary PF (APF) improves the
qualities of particles by introducing the current measurement
information in the weights before resampling [13]. However, if
the process noise is large, the use of APF tends to degrade the
performance. To the best of our knowledge, all the existing
resampling algorithms perform resampling operation on all
the particles, and the resulting particle set only contains the
new-born particles. Hence, these resampling strategies are
referred to as total resampling [10]. It is necessary to perform
resampling procedure for PF, but the traditional resampling
algorithms overdo it. To improve the estimation accuracy, re-
sampling can be done dynamically i.e resampling is performed
only on part of the particles whose number is dynamically
determined online. The resulting particle set contains not only
the new-born particles brought by resampling operation, but
also the father particles, that is, the resampling-free particles.
Thus, a trade-off between the particle degeneracy and particle
impoverishment can be achieved. A comparison between the
traditional resampling approaches and the dynamic resampling
approach is given in Fig.2
III. PARTICLE FILTERING METHODS
A. Sequential Importance Sampling (SIS) Algorithm
The Sequential Importance Sampling (SIS) algorithm which
is based on the Monte Carlo (MC) method forms the basis of
most sequential MC filters developed. Depending upon the
choice of importance sampling density (proposal distribution)
and re sampling step various special cases can be derived from
SIS algorithm.
1) sampling importance resampling (SIR) filter
Fig. 2. Comparison of the traditional resampling strategy and Dynamic
Resampling strategy
2) auxiliary sampling importance resampling (ASIR) filter
3) regularized particle filter (RPF).
In this paper, a SIR filter is designed for a dynamical system
of a robot as follows:
xk+1 = f(xk, uk) + wk
zk = h(xk) + vk (3)
The assumptions required to use the SIR filter are very weak.
The state dynamics and measurement functions f(·, ·)and h(·)
respectively in (3) need to be known, and it is required to be
able to sample realizations from the process noise distribution
of and from the prior. Lastly, the likelihood function p(zk|xk)
needs to be available for point wise evaluation up to a certain
proportionality at least [9]. The SIR algorithm can be easily
derived from the SIS algorithm by an appropriate choice of 1)
the importance density, where q(xk|xk−1, z1:k) is chosen to be
the prior density p(xk|xk−1) and 2) the resampling step, which
is to be applied at every time index. This choice of importance
density implies that we need samples from p(xk|xk−1). A
sample xk ∼ p(xk|xk−1) can be generated by first generating
the process noise sample wk−1 ∼ pw(wk−1) and setting xk =
fk(xk−1, wk−1), where pw is the pdf of wk−1.
The weighted approximate to the density p(·) is given by
p(x) ≈
Ns∑
i=1
wiδ(x− xi) (4)
where
wi ∝ π(x
i)
q(xi)
(5)
is the normalised weight for ith particle and δ(·) is the Dirac
delta function.Where, the Dirac delta function is a function
that is zero everywhere except one point and at that point
it has an infinite value. It is similar to impulse function at
ith location and zero elsewhere, If the importance density is
chosen to factorize such that
q(x0:k|z1:k) = q(xk|x0:k−1, z1:k)q(x0:k−1|z1:k−1) (6)
p(xk|z1:k) =
p(zk|x0:k|z1:k−1)p(x0:k|z1:k−1)
p(zk|z1:k−1)
=
p(zk|x0:k|z1:k−1)p(xk|x0:k−1|z1:k−1)
p(zk|z1:k−1)
× p(x0:k−1|z1:k−1)
(7)
=
p(zk|xk)p(xk|xk−1)
p(zk|z1:k−1)
× p(x0:k−1|z1:k−1) (8)
By substituting (6) and (8) into (5), the weight equation is
obtained as follows:
wi ∝
p(zk|xik)p(xi|xik−1)p(xi0:k−1|z1:k−1)
q(xik|xi0:k−1, z1:k)q(xi0:k−1|z1:k−1)
wi ∝ wik−1
p(zk|xik)p(xik|xik−1)
q(xik|xi0:k−1, z1:k)
(9)
Furthermore, if q(xik|xi0:k−1, z1:k) = q(xik|xik−1, zk) then
the importance density becomes only dependent on xk−1 and
zk.
Now for sampling importance resampling (SIR) filter",
q(xik|xik−1, zk) = p(xik|xik−1)
Substituting this in (9) we get the weights as
wi ∝ w1k−1p(zk|xik) (10)
However, noting that resampling is applied at every time
index, we have wik−1 = 1/N ; ∀i � N , therefore
wi ∝ (zk|xik) (11)
The weights given by the proportionality in (11) are nor-
malized before the resampling stage. The importance sampling
density for the SIR filter is independent of measurements
zk, the state space is explored without the knowledge of
the observations. The SIR method does have the advantage
that the importance weights are easily evaluated and that the
importance density can be easily sampled.
The basic idea of resampling is to eliminate the particles
having smaller weights and concentrate on the particles with
larger weights since they have more impact on the approxi-
mation of the posterior and reduces degeneracy. Resampling
involves generating new particles from an approximate discrete
representation of p(xk|z1:k) given by
p(xk|z1:k) ∝
Ns∑
i=1
wikδ(xk − xik) (12)
where δ(.) is Dirac delta function.
(12) gives the distribution of the particles with the correspond-
ing weights. The particles with lower weights will be discarded
in the next resampling step. This causes the particles with
higher weights to appear at same locations after resampling
which can be seen in Fig:2. If the problem is not solved it
may lead to particle collapse where all Ns particles occupy
same location in the state space after few iterations. A modified
particle filter known as the regularized particle filter (RPF) was
proposed [15] as a potential solution to the above problem. It
is similar to the SIR filter except for the resampling step. The
RPF resamples from a continuous approximation of a posterior
as opposed to a discrete posterior approximation in SIR filter.
RPF are drawn from the approximation
p(xk|z1:k ∝
Ns∑
i=1
wikKh(xk − xik)) (13)
where:
Kh(x) =
1
hnx
K(
x
h
) (14)
is the rescaled Kernel density K(·), h > 0 is the Kernel
bandwidth, nx is the dimension of the state vector x and
wik, i = 1, ...., Ns are normalized weights. The Kernel density
is a symmetric probability density function such that∫
xK(x)dx = 0",
∫
||x||2K(x)dx
