A procedure for determining the location of an instrumentation platform on natural terrain is based on a concept of maximum-likelihood matching of two range 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 range map of a larger surrounding terrain area (a "global" map) in a known frame of reference. The procedure, which is still undergoing testing and refinement, was developed primarily to aid the autonomous navigation of exploratory robotic vehicles on distant planets. The procedure might also be adaptable to similar applications on Earth and to such related applications as enabling blind persons to determine their locations in previously mapped natural and artificial environments.

Once the local range map has been computed from the stereoscopic imagery, it is converted to a volume-cell (voxel) representation (see figure). Optionally, if the orientation of the robotic vehicle or other instrumentation platform is known from a gyrocompass, Sun sensor, or other independent sensor, then the conversion to the voxel representation can include rotation into the orientation of the global map to facilitate matching.

A Three-Dimensional Local Map of the local terrain was generated from images acquired by stereoscopic cameras in the Sojourner vehicle. In a test of the procedure described in the text of this article, the local map was then matched with a "global" map generated from images acquired by stereoscopic cameras in the Mars Pathfinder lander, from which the Sojourner had been deployed.

The range points in the local map are binned in a three-dimensional occupancy map of the surroundings at some specified scale. In a subprocess that amounts to high-pass filtering of vertical-position data, the local average of the terrain height is subtracted from each cell; this subprocess is not strictly necessary and it reduces the ability to determine changes in the height of the platform, but, advantageously, it reduces the computation time needed for localization by eliminating the need to search over vertical translations. Each cell in the occupancy map is said to be occupied or unoccupied, according to whether it contains or does not contain, respectively, a range pixel.

The degree of matching between the global map and the local occupancy map is quantified by use of conventional image-matching measure based on the Hausdorff distance and reformulated in probabilistic terms according to the principle of maximum-likelihood estimation. The likelihood function is given by

where Di is the distance from the ith occupied voxel in the local map to the closest voxel in the global map, X is the trial position of the local map relative to the global map, p(Di;X)is a probability distribution function (PDF), and n is the number of occupied voxels. To some extent, the PDF can be chosen arbitrarily: One suitable choice is a simple two-value PDF that yields a measure equivalent to the Hausdorff fraction commonly used in matching images; a better (albeit more complex) choice is a normal distribution function with an additive term.

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 platform. The search for this position can be started from a position that has been either assumed or estimated by an independent navigation technique. The estimate of position is then progressively refined by use of efficient search techniques that provide for the recursive division of the search space into smaller cells and pruning of cells that cannot contain a position superior to the best known position.

This work was done by Clark F. Olson of Caltech for NASA's Jet Propulsion Laboratory. NPO-20392