Particle Filter Inefficiency

Question

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?

Answer 1

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.

Answer 2

This question is a bit similar to Why use Monte Carlo method instead of a simple grid?

You are (partly) right, if the particles/randomness was nothing more than a simple way to do a grid search on a static grid generated by a random method rather than an evenly distributed grid, then the random method would indeed not be efficiënt.

The inefficiency would be because while you will be filling the space reasonably homogeneously, there are still regions with relatively lower/higher density on a small scale.

However, with the random/particles method it is more easy to make the grid adaptive. You can change the concentration of particles based on new information, and by doing this you can easily generate a random 'grid' that is more fluid and is not computing everywhere with the same density (which is not efficiënt) but instead directs focus to the places where it matters. (So the property that it is not homogeneously filling the space, is now an advantage)

You can see this in the video. The particles do not remain static, but instead are adapting their location and become more focused. This algorithm is running several times creating a very fluid grid. You could do this (maybe) with your regular grid method as well, but it becomes much more difficult to program the fluid adaptive property.

Answer 3

It'll be a little late answer but, I guess it is the exact reason why the choice of importance distribution is so important. What you described in the question is the bootstrap pf which uses prior distribution as an importance distribution. If you consider using "optimal importance sampling" you might obtain the same performance with only 50 particles, when compared with prior sampling and 50.000 particles.

I think the point here is that approaching the problem with the right solution. No algorithm can be the right choice for every problem.