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.
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
This Brief includes a Technical Support Package (TSP).
Localization by maximum-likeihood matching of range maps
(reference NPO20392) is currently available for download from the TSP library.
Don't have an account?
Overview
The document discusses a novel technique for localization of robotic vehicles, particularly in the context of extraterrestrial missions, developed by Clark F. Olson at NASA's Jet Propulsion Laboratory. The method focuses on maximum-likelihood matching of range maps to determine the position of a robotic platform on natural terrain. This approach contrasts with previous work that primarily addressed rough localization over large areas, achieving an average error of 91 meters. In contrast, the new technique aims for fine localization within smaller areas, achieving errors of less than a meter.
The localization process involves two key components: a local range map generated from images captured by stereoscopic cameras mounted on the robotic vehicle, and a global range map of a larger surrounding area, which serves as a reference. The local map is created by processing the terrain imagery, and it is converted into a three-dimensional occupancy map, where each cell is classified as occupied or unoccupied based on the presence of range pixels.
To quantify the degree of matching between the local and global maps, the document describes the use of the Hausdorff distance, reformulated in probabilistic terms through maximum-likelihood estimation. The likelihood function is derived from the distances between occupied voxels in the local map and the closest voxels in the global map. The position that maximizes this likelihood function is considered the most probable position of the robotic platform.
The technique is particularly beneficial for missions on Mars, where it can be applied in areas with multiple science targets, such as around landers. The document also notes that while the method is primarily designed for extraterrestrial applications, it could be adapted for use on Earth, including aiding visually impaired individuals in navigating previously mapped environments.
Overall, this research represents a significant advancement in the field of autonomous navigation for robotic vehicles, providing a robust framework for precise localization in challenging terrains. The ongoing testing and refinement of this procedure highlight its potential for future Mars missions and other exploratory endeavors.
