Monte Carlo Localization!

In robotics, localization is the task of determining one's location within a known environment, given available sensory data. Theoretically, if a robot knows its starting position and how many times its wheels have rotated, it should be able to calculate its resulting position on a map. Unfortuneately, due to real-world factors like wheel slippage, there is a significant amount of uncertainty in this odometric data, so a robot needs to gather and reason about other sensory information in order to keep better track of its own position.

With HamsterBot, we implemented an algorithm called Monte Carlo Localization, or MCL for short, which lets the robot figure out where it is on a map.

You can read the original paper on MCL at this page, or a short description of it at Wikipedia. The general idea of it is to first guess where the robot is. Then when the robot moves, we take each of these guesses, called particles, and move them through the map in roughly the same way that the odometric data indicates, but with small random variations for each particle. Next we compare the current sensor data from the robot to simulated sensor data for each particle, and assign a probability to the particle based on how close the two sensor readings are. See the post on Motion and Sensing Models for more information on how positions and probabilities were assigned. Finally we resample the particles based on their assigned probabilities, so that high probability particles tend to be multiplied and low probability particles tend to die off. Then the process starts over. In this way, we can get what we hope is a good idea of where the robot is within our map.

Currently, Hamsterbot uses just its bump sensor. In the videos of our demo, you can see the robot bumping into walls, and on the screen, all the yellow particles not touching a wall dissapear, because we know they aren't accurate representations, given the bump we just experienced.

Our MCL algorithm in particular has some cool features to keep the robot on track. Should none of our particles correspond to the sensor data from our robot, then we create all new particles, and spread them across the map, hoping one of them will be close to the actual robot. In the future, we are going to also make sure these all new particles match the current sensor data from the robot...if the robot is bumping something, there's no point in creating particles far away from any walls!

This particular algorithm is something that will likely have many upgrades in the near future, but for now, it's the brains of our Hamsterbot!

Check out Video #0 to see the real HamsterBot and a good example of MCL in action. Below is a movie of a simulated Roomba running MCL. The red dot indicates the actual robot position, the blue dot is the odometric data, and the yellow dots are our MCL particles.