DARPA MARS program research progress

Project Title: Robust Navigation by Probabilistic Volumetric Sensing

Organization: Carnegie Mellon University

Principal Investigator: Hans Moravec

Date: August 5, 1999

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 [A3]. We work to parlay that start into a universally convincing demonstration, just as the requisite computing power arrives.

The work has natural 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.

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.

Recent Accomplishments

Our funding has not arrived as of August 1999, but we have continued our preparatory work, and refined plans for the first new robot testbed.

Graduate student Martin Martin, working towards his thesis about one year away, has integrated monocular vision, using an optical-flow approach, with sonar range sensing and omnidirectional robot control towards a program that evolves high level control behaviors. The work is being conducted using our existing Uranus mobile robot, controlled via a long cable by a desktop dual pentium machine running the Be operating system. Though the details are different, the approach foreshadows the development system we will use for the main work.

We have also begun to develop routines that project 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.

Current Plan

Recent product announcements will allow us to assemble a more attractive initial development system than anticipated in the proposal.

Our new plan is to acquire a small Pioneer II robot base, and equip it with a new Apple iBook. The iBook contains an integrated "AirPort" 11 mb/s wireless spread spectrum LAN (using Lucent Wavelan technology) that communicates (to 150 ft) with a hub that connects to standard ethernet. The robot will also carry three (eventually more) Logitech Quickcam Pro digital cameras, which economically provide true 640x480 color imaging. They will be arranged with wide-angle lenses in a trinocular pattern and connected through a hub to the iBook's USB port. Also on the USB hub will be a serial converter whose output controls the robot. Standard Webcam software may be sufficient for capturing Quickcam images.

The wireless link will connect the robot computer to a larger stationary base computer, probably a 500 MHz Apple G3 machine, which will perform the bulk of the 3D mapping and navigation calculations.

We had planned to simply upload the images to the base computer, and do all processing there. Uploading images would take several seconds. The 500 MHz base computer does not have quite the 1,000 MIPS power we estimate is necessary to process a glimpse in one second. As a result, the first prototype system would not operate in real time, moving instead in foot-long lurches, marked by pauses of several seconds.

However, the iBook itself contains a 300 MHz G3. About 30% of the necessary work in the total program is stereoscopic correlation of image patches. Several thousand patches are processed for each glimpse, and each results in an "evidence ray" to be added to the 3D grid map. Each ray can be described by a short vector giving its direction, range and confidence. In total, they require less than 10% of the bandwidth of the raw images. By doing the stereoscopic processing in the iBook, we not only reduce the communication dramatically, but reduce the computing load on the base computer. With this approach, we may achieve near real-time operation even in the first prototype.

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 and Karcher.


Project Overview
Project Title
Technical Aspects
View of 3D Grid Map
Navigation Head
Factory AGV
Floor Scrubbing Machine
Patrol Robot
Automatic Home Robot Vacuum Cleaner
Robovac Recharging and Regurgitating
Universal Robot
Universal Robot Delivery