Diffusion epfl (master) Browse

R2653/writing/computational thinking/slam/slam.txt
8b6191edf8eamaster

slam.txt
View Options

			Before GPS-based navigation system became ubiquitous, if you had to drive to someone's house for the first time you would call them up and get directions to their place in the form of a series of rather vague statements: "after the gas station, turn left at the third intersection; join the main road and then look for a red building on your right, ..." Getting to a destination this way often included some painful backtracking and almost certainly an even more painful argument with your spouse. But, behind the scene (pun intended), a set of very high-level cognitive processes were hard at work to create a mental map of the environment and, at the same time, manage to determine the current position within that map.

			The computational name for these mental processes is called SLAM (Simultaneous Localization and Mapping) and the existence of efficient SLAM algorithms is what makes it possible to build autonomous robots such as the Mars rover or, closer to us, self-driving cars.

			Not all animals navigate their world via internal high-level maps, by the way: try to wave a flying insect out of a window and, most likely, you will end up looking in frustration at the critter's inability to realize that freedom is just a few centimeters away. Yet insects are fully capable of spatial activities such as finding food. It turns out that they do so by a combination of pre-defined exploration patterns and local decision mechanisms based on physical feedback. Interestingly, these strategies are at the heart of the first successful domestic robot ever sold: the Roomba. Place the autonomous vacuum cleaner in a room and you will observe a complex motion pattern, usually starting as a spiral until a wall is bumped against, and then followed by bouts of edge hugging and random zig-zagging. The goal is to cover every point on the floor (the Roomba is a cleaning device, after all) and, although the trajectory is nowhere as efficient as a human's, the insect-inspired biomimicry approach works well and is very economical to implement.

			Self-driving cars, however, need to be able to efficiently navigate a complex terrain full of constantly changing features and therefore we need a SLAM algorithm. To understand how that works, let's pretend you are driving sans GPS, as in the old days, and that your instructions read: "after getting on the main road, drive for about two kilometers and turn left after the red building". You have two imprecise pieces of information (distance and landmark) that you have to map your trajectory to; your strategy will be to perform a series of actions that minimize the error with respect to the instruction. If, for instance, right after joining the main road you immediately see a red building, you will not turn left because that would imply that the distance information is completely wrong. On the other hand, as you get closer to the two-kilometer mark, any red building would be interpreted as the moment to turn and that would reset your uncertainty on your position. In a self-driving car, imprecise positional information is provided by the GPS and by the accelerometers, while visual landmarks are detected by cameras and LIDARs (laser-based ranging devices): the latter are used to improve the precision of the position, while the position is used to choose which landmarks to look for next. This circular refinement is, in a nuthsell, the mode of opeeration of an extremely versatile algorithm called the Kalman filter, which is at the heart of most SLAM methods.

			The first successful self-driving car was designed by a team within Stanford University's Artificial Intelligence Lab, led by Sebastian Thrun (the code that ran the car is actually available online). The design was in response to a public challenge by DARPA, the research branch of the United States Department of Defense. Interestingly, iRobot too, the manufacturer of Roomba, initially developed its technical expertise working for DARPA. Whatever your feeling about it, it seems that our robotic future will have an original debt towards the military...