Whats the logic to implement a particle filter for a robot with range sensor?

Question

I am trying to implement a particle filter for a robot in Java. This robot is having a range sensor. The world has 6 obstacles - 3 in the top and 3 in bottom. I am calculating the distance of the robot from each obstacle's center and then performing the same activity for each particle. Then, i calculate the difference between the robot and particles. The particles for which the difference with robot measured distance are small, i give them higher probability in resampling.

But, the problem with this approach as told by my friend is that I am assuming that I already know the locations of the obstacles, which make this all process useless. How should I approach it rather in a sense that I don't know the obstacles. How can the particle filter be implemented then? How will the particle filter work in case i don't know the obstacles location? An example of process would be great help. Thanks

Answer 1

Your question addresses three very different problems, all of which are hard with complicated research-type algorithms.

1. Localization: When you have a known map of the environment and an unknown robot position. The most common algorithm for this is Monte Carlo Localizataion. This is a particle filter exactly like what you're describing.
2. Mapping: When the robot wakes up in an unknown environment and has to build a map. Usually mapping algorithms assume that you know the location of the robot, ie from GPS or similar. I've never done pure mapping so I don't know any algorithms, but a quick google should find them.
3. SLAM: When you combine the two problems, an unknown environment and an unknown location the problem is called simultaneous localization and mapping (SLAM). This is very hard. There are good algorithms and good software packages to do it, but they are all still experimental and only work for certain types of environments / sensors. I highly highly recommend that you use an existing package rather than implementing SLAM yourself because it can take months of research work to tune all the parameters. I have no idea if there are SLAM packages for Java, but openslam.org has a great list of state-of-the-art SLAM algorithms. Personally I've used GMapping quite a bit and I trust it not to crash my $25k robot. Be aware that you are treading in research waters.

Sorry for giving you such a long answer to a short question. My suggestion would be to assume that you know the locations of the obstacles and do a simple Monte Carlo Particle Filter.

Answer 2

If you don't know the location of the obstacles and want to apply your filter, I see two solutions:

1. • Do a quick mapping using a simple algorithm easy to implement like the Occupancy Grid Algorithm (with this you localize the obstacles relatively to your robot)
   • Apply your particles filter
   • Move the robot
   • Relocalize your robot using odometry
   • Correct odometry errors by using another sensor measurements if possible

2. Using a SLAM algorithm to simultaneously Localize and Map obstacles. The SLAM algorithms are more robust to sensors and odometry errors than the Occupancy Grid Algorithm but are more difficult to implement and need generally more CPU consumption.

N.B: you must understand that there is no "optimal" solution since this problem still a very active research domain in robotics, the two solutions have advantages and drawbacks. Consider also the speed of your processor or microcontroller.