4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you clarify what the problem is? Are you saying that the range sensors are inaccurate, thus leading to the wrong particles getting a higher weight? If the external sensors measure the distance to the robot, then the particles along the circle surrounding the sensor are where the robot could be located, therefore they should be weighted higher $\endgroup$ – BarbalatsDilemma Aug 9 '16 at 17:56
  • $\begingroup$ The reflections caused by the objects in the vicinity cause the external sensors to give an higher estimate of the range. My understanding is that, though the incorrect particles get higher weight because of this problem, eventually the right particles will be weighted more when you get more ranges. However, since my observation model is peaked (sensor noise = 0.02), the incorrect particles gets higher weights and the correct particle gets negligible weights during the first few iterations. The resampling then removes the correct ones. $\endgroup$ – ZincFur Aug 9 '16 at 19:49
  • $\begingroup$ your sensor noise is not 0.02 if the measurements do not measure your state with 0.02 of uncertainty. your sensor noise is off. $\endgroup$ – holmeski Nov 2 '16 at 0:32
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Welcome to Robotics, P.Geurts! Always great to see an expert appear in threads like this. For this particular question, OP had asked about ways to address the perceived problem of sample impoverishment. It looks like your suggestion was to ditch the particle filter and move to a different filtering scheme, but it didn't look like you had addressed the original problem (sample impoverishment). Is there anything OP could do to improve the impoverished sampling problem, or is the best route really to change filtering schemes? $\endgroup$ – Chuck Dec 7 '16 at 20:07
  • 1
    $\begingroup$ Thanks, Chuck. I do know my answer is not directly what OP was looking for. However, Jacob has already provided a good answer by linking to the other question. One of the answers there links to this paper, which nicely explains various resampling methods and their advantages. $\endgroup$ – P. Geurts Dec 9 '16 at 14:32
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The range information from the sensors are being sent at different frequencies and so waiting for all the data might cause some delay in the posterior estimation. Also, I am not sure about accumulating the weights between multiple range information since I need to assume that my observation model is a pdf. One idea might be to use the multiple range information and then triangulate the position before assigning weights. However, the obstacle reflections induces range errors and I might need a more sophisticated algorithm to triangulate which defeats the use of Particle Filter. $\endgroup$ – ZincFur Aug 4 '16 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.