A method of determining the location and the uncertainty in the location of a mobile robot to subpixel resolution on a map grid has been devised. The method is applicable to a robot equipped with stereoscopic vision equipment for mapping the local terrain and with sensors for determining its orientation. The method involves fitting a parameterized surface (usually a normal distribution) to the peak of a likelihood function in the space of possible positions.

This method is built upon the method described in "Localization by Maximum-Likelihood Matching of Range Maps" (NPO-20392) NASA Tech Briefs, Vol. 22, No. 10 (October 1998), page 86. The localization problem is formulated as one of seeking a maximum-likelihood match of two maps: (1) a local range map generated by processing of images of the terrain in the immediate vicinity acquired by stereoscopic video cameras mounted on the platform and (2) a previously generated map of a larger surrounding terrain area (a "global" map). The global map could have been generated either by use of panoramic imagery from the robot or by combining the information from previously generated local maps. The points on the local range map are binned in a three-dimensional occupancy-grid representation of the surroundings, at a known orientation with respect to the global-map coordinates. In a subprocess that amounts to high-pass filtering of vertical-position data, the local average of the heights in each bin is subtracted from each cell. This subprocess reduces the computation time needed for localization by eliminating the need to search over vertical translations; in other words, as a result of this subprocess, it suffices to search over horizontal coordinates only.

The degree of matching between the global map and the local occupancy map is quantified by use of a likelihood function defined by the equation

where Di is the distance from the ith occupied cell in the local map to the closest occupied cell in the global map, X is the trial position of the robot (expressed as the trial position of the local map) relative to the global map, p(DiX) is a probability distribution function (PDF), and n is the number of occupied cells. The most likely position of the local map relative to the global map [that is, the position, X, that maximizes L(X)] is taken to be the position of the robot. The search for this position is started on a relatively coarse grid, from a position that has been estimated, for example, by deductive reckoning. The estimate of position is then refined in a subprocess that involves recursive division of the search space into smaller cells and pruning of cells that cannot pass the maximum-likelihood test.

As described thus far, this method is nearly identical to the method described in the noted prior article. The distinct aspect of this method lies in the provision for both subpixel localization and characterization of uncertainty in the localization. Inasmuch as the likelihood function expresses the probability that each position in the pose space (the space of possible positions) is the actual robot position, the uncertainty in the localization is quantified by the magnitude of the decrease of the likelihood function with distance from the peak. Subpixel localization in the discretized pose space can be performed by fitting a parameterized surface to the peak that occurs at the most likely robot position.

For the purpose of this fitting, it is assumed that in the vicinity of its peak, the likelihood function can be approximated and parameterized as a normal distribution. The fitting then yields both the subpixel estimate of position (namely, the center of the normal distribution) and an estimate of uncertainty (namely, the standard deviation of the normal distribution) centered at the nominal peak location.

The uncertainty is further characterized by a probability that a qualitative failure has occurred. Such a failure could occur, for example, in an environment in which recognizable landmarks are sparse and consequently many locations appear very similar to the robot. The probability of qualitative failure is estimated by comparing the likelihood scores under the tallest peak with the likelihood scores in the rest of the pose space.

This work was done by Clark F. Olson of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.nasatech.com/tsp under the Information Sciences category. NPO-20657