As I understand it, Particle Filters are a Monte Carlo method to narrow down a search space and find a posterior through a survival-of-the-fittest type method.

The particular application of Particle Filters to robot localization is described in this Udacity video: https://youtu.be/4S-sx5_cmLU?t=83

I understand how the robot is using the Particle Filter to localize, but I find that approach inefficient and am wondering why this approach would be used over my approach. Below I describe my understanding of the particle filter approach, and my approach.

Particle Filter Approach:

  1. Create thousands (let's say 50,000) of particles randomly distributed across the search space. You might implement this by creating a "Particle" class in Java and creating thousands of isntances of this object.
  2. Get the range finding distance readings for the robot.
  3. Loop through all 50,000 Particle objects and for each Particle Object:
    • Get the distances of the particle from the walls
    • Compare these distances with the distances from the robots range finder
    • With some probability, keep the particle in the list based on how likely the particle distances match the robots, if it is super unlikely the particle will most likely be thrown out.
  4. Iterate until particles localize on a single area.

This is how I would approach it if I didn't know about particle filters:

My approach

  1. Discretize the search space. Every 3 inches in the x dimension and every 3 inches in the y dimension would be considered a discrete point. So if the search space was 500 inches by 500 inches, (3in,3in) is considered a discrete point as well as (3in, 6in)...etc.

  2. Loop through all discrete points (3,3)->(3,6)->(3,9) by incrementing by 3:

    • Get the distances from that point to the the walls
    • Compare these distances with the distances from the robots range finder
    • With some probability, eliminate this point from consideration based on how likely the particle distances match the robots, if it is super unlikely the point will be likely not considered in the future.
  3. Iterate until the points your are considering localize.

Now they are pretty much the same with two differences:

My implementation probably uses less memory as you don't need to "store" particle objects in memory, rather you just go point to point by keeping two variable at the current coordinate currX and currY and do currX += 3 or currY += 3.

Second my implementation picks points using a discretization instead of randomly selecting over the space.

It seems my approach is better, so I'm having a hard time understanding why someone would create thousands and thousands of points in memory and how that could possibly be faster than what I'm doing. Could someone explain why particle filters are used in practice versus what I'm doing. Perhaps there are statistical benefits? Or maybe particle filters are simply a statistical model and in code they would be implemented more efficiently than how they are theoretically described?

  • $\begingroup$ Your approach does not scale. What would you do if wanted to find the posterior over many variables, and hence dimensions? Particle filters apportion resources intelligently. It is randomized, but not uniform. $\endgroup$ – Emre Jun 15 '15 at 17:57
  • $\begingroup$ How is it more scalable than mine? I don't understand that. To me discretizing the space and iterating over all discretized points (even in high dimensional space) seems more effcient than keeping particles in the high dimensional space in memory. $\endgroup$ – Curious Monte Carlo Jun 15 '15 at 18:19
  • $\begingroup$ How does size of your grid asymptotically scale in terms of the number of dimensions? $\endgroup$ – Emre Jun 15 '15 at 18:28
  • $\begingroup$ So it would scale exponentially. (increment size) ^ N where N is the number of dimensions. But doesn't the number of particles scale exponentially as well? So in terms of scaling I feel they are the same. $\endgroup$ – Curious Monte Carlo Jun 15 '15 at 19:43
  • $\begingroup$ No, you can fix the number of particles, and they will be distributed as efficiently as possible over your search space. $\endgroup$ – Emre Jun 15 '15 at 19:56

You have only described half of the particle filter. Before the particle weights are calculated, each particle is moved according to some control information. It goes: initialize particles, move particles, calculate probability of each particle, resample particles, move particles, ...

A word to the resample step. You just write, kick out unlikely particles (in step 3). It is in fact drawing with replacement. So, if you have 100 particles, you will also draw 100 particles. The particles with higher probability are drawn multiple times and the ones with lower probability are less likely to be drawn. So the particle filter concentrates on the regions, where the robot has a high likelihood to be. Then, there the search is continued (with the same energy (same number of particles)) as in the first iteration. So it is possible to localize with a higher precision. While your approach only is able to localize with the precision of the resolution of the grid.

I think global localization may not be the best example for a particle filter. I think tracking is much better. There, Most particles are in regions with a high probability anre there the search is more intense. With your approach, all areas are searched with the same effort. So you will not be that precise.

You are also missing the orientation. You should not only sample in x and y but also in a third dimension (some angle). Then you will need N^3 instead of N^2 samples. with 100 steps each dimension, you will have more than 50.000 particles.

But, I do not agree with the comment on scalability. Particle filters scale badly with the dimensionality of the problem. Also does your approach.


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.