4
$\begingroup$

Suppose I implement a particle filter with $n$ particles. This is a brief description of my understanding of a particle filter.

For the first step, I throw out $n$ particles some distance from my vehicle. I weight the particles according to some Gaussian distribution:

$$ w_{j,t} = \frac{e^{-X_{j,t}^{2}/2\sigma^{2}}}{\sum_{j=1}^n{e^-{X_{j,t}^{2}/2\sigma^{2}}}} $$

where $X_{j,t}$ is some (noisy) difference between a measurement taken at the vehicle and at the particle taken at time t. I then translate these particles with my vehicle (with some uncertainty) and do the same thing again, and the weights of these particles (the same particle pool) is

$$ w_{j,t+1} = \frac{e^{-X_{j,t+1}^{2}/2\sigma^{2}}}{\sum_{j=1}^n{e^{-X_{j,t+1}^{2}/2\sigma^{2}}}} w_{j,t} $$

We resample if, according to wikipedia, $K = 1/\sum_j{w_{j,t}^2} < thresh$, where thresh is some threshold we pick. Resampling is done according to each particles weight (the probability of being chosen is given by that particle's weight).

My question is thus: if $K<thresh$, that means that some particles are highly weighted. So won't resampling give us a very degenerate list of the highest weighted particles, on average? Suppose this new, resampled population is composed of only n/2 different particles, 2 times each. How do you get n particles back?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Have you taken a look at this answer: robotics.stackexchange.com/questions/479/… ? $\endgroup$
    – daniglezad
    Aug 16, 2018 at 7:24
  • $\begingroup$ Yes, but the top answer doesn't quite answer my question. If my new population - after resampling - contains multiple of the same particle, won't I lose potential variation? If I start with 100 particles, resample, and end up with 99 different particles (one has a duplicate), I will always have at most 99 unique particles. Am I to add noise to these particles so that they aren't in the same spot? $\endgroup$
    – michael zafford
    Aug 16, 2018 at 13:40
  • $\begingroup$ Are you normalizing your weights so they add to 1? $\endgroup$
    – daniglezad
    Aug 16, 2018 at 13:50
  • $\begingroup$ Yes, I am. This is the first equation in the question $\endgroup$
    – michael zafford
    Aug 16, 2018 at 13:51
  • $\begingroup$ Basically my question amounts to how I can have n unique particles at every time step if resampling can force me to choose more than 1 of the same particle. $\endgroup$
    – michael zafford
    Aug 16, 2018 at 13:52

2 Answers 2

Reset to default
1
$\begingroup$

After thinking about the problem, I believe the answer lies in the noise. You translate your particle "batch" every time step, and re weight each time. If $K < thresh$, you resample, with potential degeneracy. However, you don't know the position of your vehicle with infinite precision, and so all particles get moved with some error, and this removes the degeneracy. The previously degenerate particles retain their "influence" because you have more particles in a certain region depending on the degeneracy. The more highly degenerate a particle, the more particles test the next area around where the previously degenerate particle would be without noise to gain even greater precision.

Improve this answer
$\endgroup$
0
$\begingroup$

One of the easiest techniques to get more particles back is to again spread particles all over the workspace (just like you did in the first iteration) and continue the filtering routine normally.

Also, this will help to the overall tracking procedure.

Improve this answer
$\endgroup$

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.