Addressing the sample impoverishment in particle filter

Question

I have implemented a particle filter algorithm for the state estimation of a mobile robot.

There are several external range sensors(transmitters) in the environment which gives information on the distance (radius) of the robot based on the time taken for the receiver on the robot to send back its acknowledgement. So, using three or more such transmitters it will be possible to triangulate the position of the robot.

The particle filter is initialized with 15000 particles and the sensor noise is relatively low (0.02m).

Update Phase: At each iteration a range information from an external sensor is received. This assigns higher weights to the particles along the radius of the external sensor. Not all the particles are equally weighted since the process noise is low. Hence in most of the cases, the particle relatively closer to the robot gets lower weight than an incorrect one that happens to be along the radius. The weight is a pdf.

Resampling Phase: At this stage, the lower weighted particle(the correct one) that has negligible weight gets lost because the higher weighted particle gets picked up.

All this happens at the first iteration and so when the range information from another sensor arrives, the robot is already kidnapped.

Googling around, said that this problem is called as sample impoverishment and the most common approach is to resample only when the particle variance is low. (Effective Sample Size < number of particles / 2)

But, when the particles are assigned negligible weights and there are relatively very few particles with higher weights, the diversity of the particles are lost at resampling phase. So, when the variance is higher resampling is done which removes the lower weighted particle and hence the diversity of the particles is lost. Isnt this completely the opposite of the above idea of ESS?

Is my understanding of sample impoverishment correct? Is there a way this issue can be fixed?

Any pointers or help would be highly appreciated.

Answer 1

Your description of sample impoverishment and the way to fix it seems about right. Resampling only when the variance gets low is doing exactly what you are asking for when you say the measurements come in asynchronously. You can also improve matters by selecting the right resampling strategy. Using e.g. stratified resampling you can make sure that your higher than average weight particles won't get eliminated by chance. And yes, after resampling the particles are less diverse. That is the nature of the resampling process. Since you eliminate some particles, and copy others, the diversity after resampling is lower. You "smear" out e.g. increase diversity during the updating steps.

This can of course still lead to situations, where the bulk of your particles get deleted, and only a single particle is left (multiple times over) after resampling, because the weight before was so high. In this case its more likely that your update and measurement models don't fit very well.

Particle filters work very well with non-linearities in the regions where the probability density function of the prior is high. They don't do so well in the other regions and need tricks to make them work there.

Answer 2

As said by Jacob, sample impoverishment is inherit to the Sampling-Importance-Resampling family of particle filters.

An alternative solution which does require some extra effort is to switch to a Markov Chain Monte Carlo (MCMC) particle filter. MCMC relies on constructing a Markov chain that has a stationary distribution which is equal to the distribution you want to sample from. Meaning that if you draw samples from this Markov chain long enough, as $n\rightarrow\infty$, you will sample $x_n\sim P$, where P is the distribution you want to sample from.

The construction of such a Markov chain is often done through the Metropolis-Hastings algorithm. Here, a proposal state $x_k^*$ is generated from the current state $x_k$, which is most often done by a Gaussian around the current state: $x_k^*\sim N(x_k,1)$. After this, the likelihood of both the initial state (seed) and proposal are calculated. Based on the likelihood ratio, the proposal is accepted with some probability. A simple introduction to MCMC and the M-H algorithm is given here.

In a particle filtering context, generating proposals around an initial seed means that the diversity in particles will never diminish, as long as the proposals are generated such that at least some of them are accepted.

EDIT: There do exist other types of SIR-like particle filters which have their own way to combat degeneracy/sample impoverishment. I suggest looking at Auxiliary Particle Filtering, where an auxiliary variable is introduced during sampling. This variable selects particles based on their goodness-of-fit to current observations. This helps to better model the tails of the density (which is the weak point with sample degeneracy).

Answer 3

I'm not familiar with particle filtering, but if applying the weights between each sensor read is causing issues, why not accumulate weights to be applied between sensor calls and apply them in bulk after all sensors have been read?

For example, it sounds like you're doing:

[Read 1]-< apply weights >-[Read 2]-< apply weights >-[Read 3]-< apply weights >

What I'm suggesting:

[R1]-< accumulate weights >-[R2]-< accumulate >-[R3]-< accumulate >-< apply all weights >

I would imagine, in the scenario above, the particles that got the biggest accumulated weight would be the ones that are "seen" by all of the sensors. Those would be the ones you would want to keep, right?