Where's my robot?

January 21, 2009 6:12 AM

How can I determine my robot's location reliably and cheaply?

I've made a wheeled robot which can communicate wirelessly with my computer. I used Arduino boards, XBee radio modules and the Wiring/Processing languages. The robot also has an ultrasonic rangefinder on the front.

Now I'm in 'What next?' mode.

I thought it would be cool if the robot could roam and communicate distance measurements back to Processing, which could then draw a map of the 2d floor space that the Robot finds itself in. Thinking this through, though, the major obstacle is determining where the robot is and which direction it's facing when it takes a range measurement.

It seems that the direction problem is easy to solve with something like this compass module. That leaves the problem of location.

I suppose you could take a mean measurement of the robots speed along with the direction travelled and take everything relative to the starting point. However, it seems to me that, with different floor surfaces and general variation, the robot's calculations will get progressively less accurate over time, and the map might just tend towards mush.

How would you solve this problem in an ideal world? A set of beacons perhaps? How would you solve it on my budget, which precludes anything over £100/$150?

posted by godawful to science & nature (4 comments total)

People have been in situations like yours in the past. A lot of people have worked on this sort of thing, with some pretty neat solutions, but even the best solutions have their weaknesses. Your best bet is to get started with one of the basic text books in the area, or some of the countless lecture notes you can find online.

The jargon for working out your robot's location is "localization". The jargon for working out your robot's location and building a map at the same time is "simultaneous localisation and mapping", or SLAM for short.

There's some pretty good information in this book at around page 182, and around page 88.
posted by Mike1024 at 7:08 AM on January 21

Oh boy! You want to solve SLAM!

Dead reckoning (what you described about measuring speed, etc) is a totally valid method of determining where a robot goes. Often, because one single method of dead reckoning is often inaccurate over time, you use a Kalman filter to basically do a weighted average of more than one dead reckoning input. So say you do an compass/encoder type thing, where you have a cardinal direction from the compass and you measure wheel rotations and circumference and thus you can get distance traveled, and you also use a cheap IMU that knows your angular momentum (turning) and acceleration (forward/backward/sideways). Simplistically, you'd assume that one is more accurate than the other over time -- probably the IMU measurements, for relatively short durations -- and you'd give that a higher weight in your average. This would give you nonzero improvement over your current velocity-based dead reckoning.

There are complicated and highly accurate ways to do this involving lots of statistics and large matrices and lots of processing power that can accommodate for drift and inaccuracy over time, but fundamentally, it's just a weighted average.

Ideally, you also have an external reference to work with too (more sensors = better, to some extent, when doing navigation). GPS is the best, but then again, you're inside. Beacons could work; Evolution Robotics' "North Star" system does this, but it's stupidly expensive. If you have battery-powered IR beacons (which should be cheap and easy to make) that you can stick on the wall, you can triangulate against those and get a position as well. But one way or the other you need an external reference.

So cheapest way to do it? Buy your own gyros, accelerometers, and parts for IR beacons from Digikey, and roll your own INS and IR beacon system. Easier, but a little more expensive, is to buy these sensor systems COTS from a place like Robotshop. I'd go the latter route.
posted by olinerd at 7:10 AM on January 21

Maybe you'll find this article on letsmakerobots.com interesting.
posted by Harald74 at 7:15 AM on January 21

Thanks guys. The SLAM wikipedia article is the perfect jumping off point for a whole load more reading and subsequent robo-tinkering.

Cheers!
posted by godawful at 9:11 AM on January 21