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:
- 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.
- Get the range finding distance readings for the robot.
- 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.
- 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
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.
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.
- 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?