Helping Mobot navigate

In order for Mobot to scan a space by itself, it needs to do three things: get a map of the space, locate itself within the space, and plan a path to accomplish its task.

The first two are often referred to together as simultaneous location and mapping, or SLAM. In other words, the robot must simultaneously map an unknown space and figure out where it is in that space. This is a hard problem. In his Ph.D. thesis, Niko Sünderhauf reminds us how hard with an enlightening example:

SLAM is a hard problem for a robot and it used to be a hard problem for human explorers in the past. These explorers set out on their ships into the unknown and mapped the foreign coasts and islands they discovered. Just like the human explorers in the past, robots performing SLAM have to know where they are in order to draw what they see at the proper position onto the map. Sailors in the past used so called chip logs to estimate their velocity and extrapolated this velocity over time to calculate their position. This dead reckoning process inevitably leads to gross positioning errors over time and has therefore always been supported by using landmarks for navigation. Polaris, the North Star has served countless sailors as an important landmark. It enables one to determine the direction of geographic north but also the latitude of the ship’s position. If that landmark was unobservable for several days due to overcast skies, the navigator had to rely solely on dead reckoning. This way, the uncertainty of the navigator’s position estimate grew from day to day, and gross errors were very likely. When the sky was clear again, or a known coast was reached, the ship’s assumed position could suddenly be corrected and determined with high certainty again. The same process happens in SLAM for robots. When the robot re-enters an area with known landmarks, it can correct its position estimate. This is called a loop closure.

However, the mere sighting of a landmark is not sufficient. The observed landmark has to be associated with one of the landmarks in the map. The question therefore is which among the presumably many landmarks in the map has just been observed. This problem is called data association and was well known to the navigators on the ancient sail ships. The worst data association error in the history of mankind can probably be credited to Christopher Columbus when in the morning hours of October 12th 1492 he erroneously associated the coast of the Bahamas with Asia. This is what happens when the position of the landmarks in your map and your own position are only vaguely known. On the other side, the largest possible loop closure was successfully performed by the expedition of Ferdinand Magellan when his ships re-entered the realm of the Philippine and Maluku islands from the east in the spring of 1521 when these islands had only been reached from the west by Europeans before.

Our current approach is a bit of a gamble. Our end goal is to produce a high-quality three-dimensional scan of a space. What if we could also use that scan as the map for the robot? Unfortunately, producing that high-quality scan is considered computationally expensive and in order for the scan to be useful to Mobot, we have to constantly update it in real time!

One solution is to split our system to address the two problems--helping Mobot navigate and reconstructing the space we want Mobot to capture--separately. We could dumb down the navigation system to collect and process the bare minimum data to guide Mobot around. The more complex system could then run on a really powerful cluster once Mobot is done collecting data. But how does Mobot know it has collected all the data it needs to for the more powerful system without doing the work on the powerful system? Struggles.

There are many ways to approach this problem and each has trade-offs. We have a couple of ideas of how to do everything in one go, but right now, nothing is working (see the barf below). I'll talk about what's going on here tomorrow.