Particle filters: a literature survey Essay

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

How to cite this essay: