DARPA MARS program research progress

Project Title: Robust Navigation by Probabilistic Volumetric Sensing

Organization: Carnegie Mellon University

Principal Investigator: Hans Moravec

Date: June 1, 2000

Technical Report


We are engaged in a 100% effort to develop laboratory prototype sensor-based software for utility mobile robots for industrial transport, floor maintenance, security etc., that matches the months-between-error reliability of existing industrial robots without requiring their expensive worksite preparation or site-specific programming. Our machines will navigate employing a dense 3D awareness of their surroundings, be tolerant of route surprises, and be easily placed by ordinary workers in entirely new routes or work areas. The long-elusive combination of easy installation and reliability should greatly expand cost-effective niches for mobile robots, and make possible a growing market that can itself sustain further development.


Our system is being built around 3D grids of spatial occupancy evidence, a technique we have been developing for two decades [A2]. 2D versions of the approach found favor in many successful research mobile robots [A0], but seem short of commercial reliability. 3D, with 1,000 times as much world data, was computationally infeasible until 1992, when when we combined increased computer power with 100x speedup from representational, organizational and coding innovations. In 1996 we wrote a preliminary stereoscopic front end for our fast 3D code, and the gratifying results convinced us of the practicability of the approach, given about 1,000 MIPS of computer power (See overview figure). We work to parlay that start into a universally convincing demonstration, just as the requisite computing power arrives.

The work has three stages: completion and improvement of the basic perception code; creation of an identification layer for navigation and recognition of architectural features; finally, sample application programs that orchestrate the other abilities into practical behaviors like patrol, delivery and cleaning. We need both capability and efficiency. The existing code allows one-second time resolution with 1,000 MIPS, but our 3D maps have millions of cells, and straightforward implementations of path planning, localization, object matching, etc. would be much slower. We will combine techniques like coarse-to-fine matching, selective sampling and alternate representations to get the desired results at sufficient speed.

Accomplishments for June 2000

We implemented a first version of "learning through coloring", whose purpose is to optimize sensor models and other parameters that affect the quality of the gridmaps derived from sense data. Early runs of the program with a minimal set of learned parameters on archived stereo images have already led us to significantly better results, and suggested an improved overall approach, wherein intermittent coloring is used as an integral part of grid map building, not just as an offline system optimizer. In related work, Martin Martin reported new results on his Ph.D. research, which is excellently equipped to present both his own brand-new results on genetic learning for robot perception and my latest on projecting real scene colors into 3D grid maps to close a learning loop. The two thus-far relatively independent projects will converge this summer in a complete self-tuning navigating system (which will be the testbed for the next year's recognition-focussed work). and tested it with archived stereo images of an office and a laboratory. The number parameters being learned is very limited at this preliminary stage, nevertheless the program made consisting of just three:
CorWt an exponential coefficient that controls the translation of stereo correlation values into evidence-ray probabilities, a t

Current Plan

Ideas awaiting evaluation include variable resolution trinocular stereoscopic matching optimization of sensor evidence profiles and other system parameters using robot images of the scene to first naturally colorize the occupied cells in a grid, then to check its faithfulness, to close the learning loop; randomly textured light to improve stereo of uniform surfaces; coarse-to-fine path finding; occupied-cell-list matching of grids for fast localization and feature identification; and others. Ongoing work will lead us to more. We are now developing a first version of the code that projects color from stereoscopic images onto the occupied cells of 3D occupancy grids derived from the same images. This is a first step towards an automatic learning process that will automatically optimize the various parameters in the system. Other camera images will be compared with corresponding views of such colorized grids to estimate the quality of the grids. The goal of the learning is to maximize this quality.  We will report the results at the next meeting.

At that time, or perhaps the following meeting, we will also be able to report on genetic algorithm learning of strategies for combining sensor and control techniques for more effective control of robot mobility.  This is the thesis work of Martin Martin.

Technology Transition

Over the three years of the project we plan to produce a prototype for self-navigating robots that can be used in large numbers for transport, floor cleaning, patrol and other applications. The work at present is developmental only, though we have had informal discussions about future cooperative commercial work with companies such as Cybermotion, Karcher iRobot and Probotics.