# Particle Filter Inefficiency

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?

• 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. – Emre Jun 15 '15 at 17:57
• 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. – Curious Monte Carlo Jun 15 '15 at 18:19
• How does size of your grid asymptotically scale in terms of the number of dimensions? – Emre Jun 15 '15 at 18:28
• 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. – Curious Monte Carlo Jun 15 '15 at 19:43
• No, you can fix the number of particles, and they will be distributed as efficiently as possible over your search space. – Emre Jun 15 '15 at 19:56