ON A rugged grass runway just outside Sydney, four autonomous aircraft took off on an unusual maiden flight in December last year. Unlike conventional drones, these robotic craft were flying with no map, no access to GPS, and no conventional navigation aids on board. Their designers, Hugh Durrant-Whyte of the University of Sydney and Phil Greenway of BAE Systems in Bristol, UK, were nervous as hell. 鈥淣o one else anywhere in the world is flying four vehicles in formation,鈥� says Greenway.
The flight, which ended successfully after the planes described a few circuits and landed safely, was the first airborne demonstration of a radically new approach to navigation. The reason Greenway and Durrant-Whyte鈥檚 drones don鈥檛 need maps is that they make their own. Just as medieval explorers had to carefully chart their environment to avoid getting lost, the drones use video and radar images to build up a map of the terrain beneath. Later this year, the drones will map a 10-kilometre swathe of the dry Australian outback, and swap data in flight to build up a more detailed map than one alone could manage. 鈥淚t鈥檚 a bit nerve-racking,鈥� says Durrant-Whyte. 鈥淲e just have to hope that more than one aircraft doesn鈥檛 go wrong at the same time.鈥�
Durrant-Whyte and an increasing number of other researchers are following a bold new approach to one of the most important problems in robotics. Today鈥檚 robots can trundle across the surface of Mars, dive beneath the Arctic icecap and enter collapsed buildings or fly over hostile territory to spy. Yet they do this only by switching between independent navigational aids such as GPS and human remote control. To be truly autonomous, a robot has to be able to find its own way around, at least to some extent. And that means using data on its environment to build a map of that environment, and using that map to find its way. In the jargon of the field, this strategy is called simultaneous location and mapping, or SLAM. Until recently, roboticists had very little clue how to make it work. But recent work suggests that a solution is within reach.
Advertisement
The incentive to develop SLAM is huge. With a technology that maps as well as navigates, robots could explore and survey environments too hazardous or time-consuming for humans to venture into, such as contaminated industrial sites, collapsed buildings, minefields or dense jungle. For the military, map-making robots promise to get around the problem of GPS jamming, when enemy action or poor weather conditions make it impossible to receive signals from navigation satellites. Getting SLAM to work promises to help human explorers who are still constantly outwitted by complex three-dimensional environments such as underground caves, mines and underwater reefs.
It sounds simple, but make no mistake, SLAM is an extraordinarily tough challenge. For years roboticists shied away from tackling it head on. Instead they broke the problem into two. Some worked on developing robots that could accurately map their environments as long as they knew their location. Others worked on making robots that could follow maps. Both lines of research have run into very different problems.
Dead reckoning
Most conventional autonomous vehicles rely heavily on lists of directions pre-programmed by a human with access to an existing map, for example. All the vehicle has to do is turn accurately and measure the distance it travels. Finding its way back is simply a matter of performing the motions in reverse. But dead reckoning, as this process is known, is notoriously inaccurate. Wheeled vehicles measure their distance by counting wheel revolutions, but in practice the wheels tend to slip, leading to cumulative errors that rapidly spiral out of control. Similar problems affect aircraft and ship navigation systems, and human pilots often become completely lost when navigating this way.
The failure of dead reckoning makes it impossible for a robot to follow directions reliably, but it also makes it impossible for it to navigate from a map 鈥� if it cannot follow its own position accurately enough, the map is no use. But the robot stands even less chance of making its own map when it doesn鈥檛 know where it is relative to its starting point, and can鈥檛 measure the position of features relative to itself with absolute precision?
You might think GPS would be the answer. Nowadays people have such ready access to the satellite positioning system that it is easy to think the problem of navigation has been solved. But while undoubtedly useful, GPS has severe limitations. It is imprecise and does not work underground or indoors, beneath foliage or in big cities where the satellite signals can be blocked by tall buildings. And GPS jammers 鈥� which interfere with the satellite signals 鈥� are a huge problem for the military.
And there鈥檚 a more fundamental reason why GPS isn鈥檛 the answer to navigation in the real world: knowing your coordinates won鈥檛 help you to pick your way through an uncharted environment or tell you the best way from A to B. Even with a map and GPS, people in unfamiliar environments still have problems. 鈥淥ften the maps are out of date or don鈥檛 have all the features you鈥檇 like on them,鈥� says Greenway.
By the early 1990s, many researchers were beginning to lose faith. It seemed that a robot needed a GPS-like system to be able to make good maps, but a GPS-like system was no use without a map. 鈥淚t鈥檚 like a chicken-and-egg problem,鈥� says Sebastian Thrun, a leading SLAM researcher at Carnegie Mellon University in Pittsburgh.
Then, with a subtle difference in thinking, everything changed. The new approach came from Peter Cheeseman at the NASA Ames Research Center in Moffett Field, California, and his colleagues Randall Smith and Matthew Self, then at the research lab SRI International in Menlo Park, California. They reasoned that if the two halves of the problem were so inextricably entwined, why not tackle them both at once? This is the new SLAM strategy: solving the mapping problem at the same time as working out your position in the map you are making.
In a theoretical paper, Cheeseman and colleagues showed that navigation and mapping would be far more tractable if a robot attempted both at the same time. Map-making robots build up a picture of their surroundings by means of a program, or algorithm, that turns data on the environment around them 鈥� for example, the distances measured between features 鈥� into a map. The crucial part is making the map self-consistent, so that closed loops meet up and features appear only once, for example. Cheeseman and colleagues showed that to do this, the algorithm needed to take account of not just the relative locations of external features, but also the possible errors in the position of the robot as it moved about in the environment. Only then did the map stand a chance of being self-consistent.
This breakthrough rekindled interest in SLAM, and one beneficiary of the renaissance is B21, a wheeled bot designed by John Leonard at the Massachusetts Institute of Technology. B21鈥檚 mission is to navigate without a map round a closed loop in MIT鈥檚 campus corridor system. Like Durrant-Whyte and Greenway鈥檚 drones, B21 maps its environment as it goes. In its case, it does so by bouncing a laser beam off walls and doors, to measure how far away they are.
The corridors within the building are straight and form a closed loop 鈥� you can walk round the rectangular circuit in a few minutes. Leonard鈥檚 hope was that if B21 could build up enough data by taking snapshots of its environment, it would be able to piece them together into a map. But in practice, the robot couldn鈥檛 distinguish between the same corner measured twice, each time with a slight error, and two different, but similar corners. In the first maps produced by B21, using a relatively basic algorithm, the corridors are wiggly, as though drawn by an unsteady hand, and the angles they make with each other are larger than 90掳, so the beginning and end don鈥檛 meet. The robot鈥檚 鈥渞ectangle鈥� never closes, and if it isn鈥檛 stopped, it will go round the same loop dozens of times without recognising corners and doors that it has already passed (see Graphic).
However, by having B21 run a program inspired by SLAM, Leonard is now making some progress. At each step, B21 builds up a plan of the area it can see and then moves a metre or so to get another point of view. It carefully measures the distance it moves and the direction it takes. With this information safely stored, it repeats the snapshot process.
For example, suppose in the first snapshot the robot sees a corner 3 metres away at 45掳 to its line of sight. It moves 1 metre forwards and repeats the measurement, this time seeing a corner at a distance of 2.5 metres and at an angle of 70掳. Is this the same corner?
If the measurements were perfect, the robot could quickly work out whether it is the same corner with some straightforward triangulation. But because there are always errors in the measurements, the SLAM program instead assigns a probability that the two features it has seen are actually the same, and then stores the information. This strategy goes further than straightforward mapping because the robot鈥檚 map algorithm incorporates errors in its measurement of its own motion rather than considering only the errors in the distances to features it sees.
Every new measurement of a feature is compared to the set of others. If it is inconsistent, the robot assigns a small possibility that it has seen a new feature. If it is consistent, the robot becomes more confident about the location of the feature. As the analysis continues, the features it is most confident about begin to form a map.
Although there are still inaccuracies in its measurements of corridor lengths and angles, the robot manages to close loops, although not necessarily on the first time around. But then, a first-time human visitor lost in MIT鈥檚 corridor system might not realise straightaway that they were caught in a loop, either.
Suddenly, the mapping half of the SLAM goal seems within our grasp. Even better, the other half 鈥� positioning 鈥� follows immediately. As the robot鈥檚 strategy makes no distinction between errors in measurements of features and errors in measurements of its own position, it becomes more confident of its position on the route it is mapping.
Since the Cheeseman paper, other researchers have also been attempting to put SLAM into practice. A few months ago, Thrun unveiled a highly detailed 3D map of part of a coal mine in Pennsylvania. The map covers a tunnel system stretching for hundreds of metres and was compiled by a robot fitted with laser rangefinding devices and a wheel encoder to determine the robot鈥檚 approximate position. With centimetre resolution and unprecedented accuracy, the 2D plan view of the mine is remarkably similar to a map of the mine made by humans 鈥� there are very few corner distortions and even when these exist, loops within the mine still link up.
More impressive still is the 3D map, a kind of virtual mine with far richer detail. Maps like these could save lives. In July last year, nine miners in Pennsylvania almost drowned when they accidentally drilled into an abandoned, water-filled mine they did not realise lay close by. Thrun is now working on a more robust mine-mapping robot that could be used commercially.
While Durrant-Whyte and Greenway work on airborne systems and Thrun beavers away at his earth-bound approach, Leonard is hoping to apply his insights from B21 to developing autonomous under-water vehicles. The only way to measure distances under water is with sonar, which produces notoriously noisy data. This represents a huge problem not only for under-water autonomous vehicles but also for deep-water human divers. Sonar signals can help divers navigate in a simple ocean or lake, but in complex 3D environments, like under-water caves or minefields, or shipwrecks, touch becomes almost the only reliable way of finding one鈥檚 way around, and mapping by memory is incredibly confusing.
Hall of mirrors
Lit by acoustic sonar, everything looks very different. Imagine a world in which all surfaces are mirrored and you navigate with a flashlight strapped to your head. It鈥檚 a place filled with reflections, sometimes of the same object many times over. The hope is that SLAM technology can help, because it focuses on identifying different views of the same feature and putting them together.
Last year Leonard put B21鈥檚 strategy into practice using an autonomous under-water vehicle called Caribou, which he launched off the coast of Italy. Caribou performed well for an under-water navigator, but still far less well than a surface vehicle using straightforward laser rangefinding.
Leonard has also tried B21 with sonar, but still has problems getting the program to recognise closed loops. SLAM processing means it is possible for the robot to map correctly, but not all the time: there are still possible measurement errors that could pile up and ruin the map.
To try and improve Caribou and other SLAM systems, some researchers are now looking at incorporating more sophisticated methods of handling errors in measurements. The errors in distance measurements are random, like background noise, so with more measurements they tend to cancel out. But the position measurements are cumulative, so the further the navigator goes, the bigger the error can become.
One way to try and deal with these problems is to take hints from the way humans navigate. 鈥淲e have a notion of landmarks as places,鈥� says Leonard. So to handle the cumulative errors, a robot could try to recognise objects as distinctive landmarks.
Object recognition is a different challenge entirely, with its own set of complex problems, and the field is still relatively embryonic. But if robots do get better at object recognition and learn to cope with more subtle landmarks, it should also help them deal with another problem dogging SLAM systems: moving objects such as people, which appear fleetingly in a robot鈥檚 field of view and then disappear. A robot might then be able to distinguish between this kind of data and fixed features such as corners and doors.
Despite the problems, many roboticists remain upbeat. Although this year鈥檚 demo is still to come, Durrant-Whyte has already claimed that SLAM, and with it the problem of navigation, has been solved 鈥� at least in the two dimensions his drones handle, and quite possibly in three. Others are more cautious, but there鈥檚 no doubt robotic explorers are reaching the point where they can compete with humans in specific environments. Within just a few years, intrepid explorer robots will return safely from the jungle, or from underground mines and coral reefs, with a decent map to show for it.