Mapping and Localization
Simultaneous Mapping and Localization
|Dead-reckoning is a method of navigation by keeping track of how far you have gone in any particular direction. For example, if I turn right out of my office, take 6 steps, turn left and take 5 steps, I should be at the copy machine. Dead-reckoning can lead to navigation errors if the distance traveled in a direction is wrong. This can happen if the wheels on the robot spin in place when the robot encounters an obstacle. Therefore, it must be bolstered by sensor information from the environment.|
The INL control system uses a technique developed at SRI called Consistent Pose Estimation (CPE) that allows for efficient incorporation of new laser scan information into a growing map. Within this framework, SRI has found a solution to the challenging problem of loop closure: how to optimally register laser information when the robot returns to an area previously explored (and ‘recognize’ that it was there previously). With CPE, it is possible to create high-resolution maps and repeatedly execute the accurate path following necessary for high-level deliberative behavior.
CPE is one method for performing Simultaneous Localization and Mapping (SLAM). It is based on original work by Lu and Milios, who showed that information from the robot’s encoders and laser sensors could be represented as a network of probabilistic constraints linking the successive positions (poses) of the robot. The encoders relate one robot pose to the next via dead-reckoning (see inset); the laser scans are matched to give further constraints between robot poses, including constraints for when a robot returns to a previously-visited area. CPE provides an efficient means of generating a near-optimal solution to the constraint network, and yields high-quality metric maps (see adjacent figure). The work has been further extended to several interesting applications:
- The multi-robot case, in which several robots explore and communicate to cooperatively map an area. A very challenging condition is that the robots may not know their relative start locations and have to determine them by matching their local maps.
- Very large-scale maps, covering up to a hundred thousand scans.
Once a map has been made, it can be used to keep robots localized. SRI has implemented and further developed localization algorithms using a representation of the robot's state space based on Monte Carlo sampling.
One bottleneck in the MCL algorithm is the necessity for checking the posterior probability of each sample against the map, based on the current laser readings. SRI has developed an efficient method for performing this computation, using a correlation technique derived from computer vision algorithms and developed by Konolige.