Looking for ways for a robot to locate itself in the house

Question

I am hacking a vacuum cleaner robot to control it with a microcontroller (Arduino). I want to make it more efficient when cleaning a room. For now, it just go straight and turn when it hits something.

But I have trouble finding the best algorithm or method to use to know its position in the room. I am looking for an idea that stays cheap (less than $100) and not to complex (one that don't require a PhD thesis in computer vision). I can add some discrete markers in the room if necessary.

Right now, my robot has:

• One webcam
• Three proximity sensors (around 1 meter range)
• Compass (no used for now)
• Wi-Fi
• Its speed can vary if the battery is full or nearly empty
• A netbook Eee PC is embedded on the robot

Do you have any idea for doing this? Does any standard method exist for these kind of problems?

Note: if this question belongs on another website, please move it, I couldn't find a better place than Stack Overflow.

Answer 1

The problem of figuring out a robot's position in its environment is called localization. Computer science researchers have been trying to solve this problem for many years, with limited success. One problem is that you need reasonably good sensory input to figure out where you are, and sensory input from webcams (i.e. computer vision) is far from a solved problem.

If that didn't scare you off: one of the approaches to localization that I find easiest to understand is particle filtering. The idea goes something like this:

1. You keep track of a bunch of particles, each of which represents one possible location in the environment.
2. Each particle also has an associated probability that tells you how confident you are that the particle really represents your true location in the environment.
3. When you start off, all of these particles might be distributed uniformly throughout your environment and be given equal probabilities. Here the robot is gray and the particles are green.
4. When your robot moves, you move each particle. You might also degrade each particle's probability to represent the uncertainty in how the motors actually move the robot.
5. When your robot observes something (e.g. a landmark seen with the webcam, a wifi signal, etc.) you can increase the probability of particles that agree with that observation.
6. You might also want to periodically replace the lowest-probability particles with new particles based on observations.
7. To decide where the robot actually is, you can either use the particle with the highest probability, the highest-probability cluster, the weighted average of all particles, etc.

If you search around a bit, you'll find plenty of examples: e.g. a video of a robot using particle filtering to determine its location in a small room.

Particle filtering is nice because it's pretty easy to understand. That makes implementing and tweaking it a little less difficult. There are other similar techniques (like Kalman filters) that are arguably more theoretically sound but can be harder to get your head around.