I am studying and coding particle filters and I am using the Low variance sampling algorithm suggested in the Probabilistic Robotics book. I understand the procedure for the algorithm. A random number
r is picked from the interval
(0, 1 / M) and a variable
U, calculated based on
r is used to navigate the sample space systematically. A variable
c(cumulative sum) is initialized with the first weight, and incremented by adding weights until it is higher than
U. Once the cumulative sum is higher than
U, it picks the sample corresponding to the weight last added.
The problem that I have is that I don't see how this picks up a good sample set for the next iteration. This seems very random or at least favorable to lower valued weights. If the initial value of
r is very low,
U is also low initially and it may pick a sample whose weight is low, unless weight vector is sorted from high to low (Is it sorted?). However, this video suggests that particles with higher weight have a better chance of getting picked. The algorithm doesn't convey this idea to me. Please help if you have an explanation.