TravisDeyle.com

I'd like to pose a question: "How can you know the location of a robot when you don't have GPS?" Obviously, absolute position would be extremely difficult. Even if you had the stars to navigate (like sailors), your resolution is not so good. Further, not all environments have stars visible (indoors, subterranean, etc). SLAM to the rescue...

One solution is to keep track of your relative displacement using an inertial measurement unit (IMU), such as the one pictured (a low-res MEMS IMU from Cloud Cap Technologies). These devices measure acceleration and rotation in all three axes. You can fuse the sensor data using a Kalman filter to give your displacement and heading. Of course, the measurements are noisy, and thus (even if sitting still) your perceived location will drift from your actual location over time. One possible solution to this problem is Simultaneous Localization and Mapping (or SLAM).

Dr. John Leonard of MIT does some very cool work in Simultaneous Localization and Mapping (SLAM). To quote his website:

The problem of SLAM is stated as follows: starting from an initial position, a mobile robot travels through a sequence of positions and obtains a set of sensor measurements at each position. The goal is for the mobile robot to process the sensor data to produce an estimate of its position while concurrently building a map of the environment. While the problem of SLAM is deceptively easy to state, it presents many theoretical challenges. The problem is also of great practical importance; if a robust, general-purpose solution to SLAM can be found, then many new applications of mobile robotics will become possible.

So not only do you know your location, but you're left with an internal map -- a good thing for us humans who use robots to explore remote or isolated environments. I always think the concepts are best explained by a video. Notice how the robot uses dead reckoning to estimate its position. When a loop is completed, SLAM automatically corrects the internal map by "recognizing" familiar terrain. It is a very powerful algorithm. If you'd like more details, here is a good article that describes the algorithm. Of course, most of the time the algorithm is applied in 2-dimensions, as computation complexity increases very rapidly in 3-dimensions.

NOTE:  This post originally appeared on Hizook.com, which has been transformed into a robotics-centric website.  To preserve all of my original posts, I've transferred the content to my new homepage TravisDeyle.com.  I also encourage you to scope out the new Hizook!