An algorithm denoted “Gamma-SLAM” performs further processing, in real time, of preprocessed digitized images acquired by a stereoscopic pair of electronic cameras aboard an off-road robotic ground vehicle to build accurate maps of the terrain and determine the location of the vehicle with respect to the maps. Part of the name of the algorithm reflects the fact that the process of building the maps and determining the location with respect to them is denoted “simultaneous localization and mapping” (SLAM). Most prior real-time SLAM algorithms have been limited in applicability to (1) systems equipped with scanning laser range finders as the primary sensors in (2) indoor environments (or relatively simply structured outdoor environments). The few prior vision-based SLAM algorithms have been feature-based and not suitable for real-time applications and, hence, not suitable for autonomous navigation on irregularly structured terrain.

The Gamma-SLAM algorithm incorporates two key innovations:

  • Visual odometry (in contradistinction to wheel odometry) is used to estimate the motion of the vehicle.
  • An elevation variance map (in contradistinction to an occupancy or an elevation map) is used to represent the terrain.

The Gamma-SLAM algorithm makes use of a Rao-Blackwellized particle filter (RBPF) from Bayesian estimation theory for maintaining a distribution over poses and maps. The core idea of the RBPF approach is that the SLAM problem can be factored into two parts: (1) finding the distribution over robot trajectories, and (2) finding the map conditioned on any given trajectory. The factorization involves the use of a particle filter in which each particle encodes both a possible trajectory and a map conditioned on that trajectory. The base estimate of the trajectory is derived from visual odometry, and the map conditioned on that trajectory is a Cartesian grid of elevation variances. In comparison with traditional occupancy or elevation grid maps, the grid elevation variance maps are much better for representing the structure of vegetated or rocky terrain.

This work was done by Andrew B. Howard of Caltech and Tim K. Marks of the University of California San Diego for NASA’s Jet Propulsion Laboratory. For more information, contact This email address is being protected from spambots. You need JavaScript enabled to view it.. NPO-46114

NASA Tech Briefs Magazine

This article first appeared in the January, 2011 issue of NASA Tech Briefs Magazine.

Read more articles from this issue here.

Read more articles from the archives here.