Robust Navigation
by
Probabilistic Volumetric Sensing

Carnegie Mellon University
The Robotics Institute
5000 Forbes Avenue
Pittsburgh, PA 15213

Time Period: May 1, 1999 to April 30, 2002

PROPOSAL

1. DARPA ITO Solicitation: BAA #99-09 Mobile Autonomous Robot Software

2. Technical Topic Area: Soft Computing

3. Proposal Title: Robust Navigation by Probabilistic Volumetric Sensing

4. Technical Contact: Hans Moravec
email: hpm@cmu.edu
tel: 412-268-3829 or 412-363-9759
fax: 412-363-9834
postal: Robotics Institute
5000 Forbes Avenue
Carnegie Mellon University
Pittsburgh, PA 15213

The program has since been used by my sabbatical hosts at Daimler-Benz in Berlin to drive a robot around office corridors. It is available on the web, and has been used by several other groups. We ourselves used it to drive a robot short distances, but have made little additional progress because of unrelated demanding commitments. Growing computer power strongly compels us now to bring the work to a practical conclusion in a sustained, concentrated, single-minded effort. We need full-time support for this. We have not found significant funding commercially. Robotics has been a historically unprofitable business, and small companies have no money for long-term efforts, while large companies have other interests. Daimler-Benz, for instance, has only a small internal robotics effort, that competes with other research projects. My hosts were able to offer us only a small gift for our work, which we used for modest equipment purchases.

Year 1 Agenda: Perception Layer

Our first year’s work we will be to implement a lengthy list of intuitively promising improvements to the existing core perception system [A3], which was a first-cut experiment. Among them:

• Adjusting the stereo ray and many other parameters with an automatic learning process to optimize the system performance. For a learning criterion, we will “project” some scene images onto range-sorted occupied cells of a grid to naturally colorize them, then compare other scene images with corresponding views of the colorized grid. The better the match, the better a representation of reality is the grid. By this means we avoid the onerous task of supplying independent “ground truth” to the learning process. The camera images already code such information, even when the robot is in the field. Our first 3D results, illustrated in the preceding image, used ad-hoc settings of all parameters. Learning should provide substantial improvement, evidenced by the following 2D grid example with data from a ring of sonar sensors on a robot traversing a highly specular hallway, where a majority or readings were misleadingly long. The upper left image is a hand-constructed ideal map of the hallway. The upper right is the hallway reconstructed using a sensor model that works well in non-specular settings, but fails here. Lower left is a reconstruction using a model partially trained for these conditions (note prominent door frames, and their specular reflections), and lower right is by a fully trained model [A2]. The learning improvement in our 3D setups will likely be less dramatic, since the initial model is not so bad.

• Augmenting our dead-reckoning by statistically registering grids constructed with partial data. The has worked well in 2D, providing sub-voxel registration (see references in [A3]). It should be even better in 3D, with more pixels. Computational cost is the main concern: we plan to a coarse to fine strategy, and a comparison concentrating on the typically mere 2% of the cells that are occupied to keep this tolerable. In the latter technique, a list of the occupied cells of one grid are mapped under a trial displacement and rotation into the cells of a second grid, and also vice-versa using the inverse translation and rotation, to calculate a goodness of match, which is to be optimized. We also plan to add a six-axis inertial navigation device to provide close initial estimates.

• Replacing monochrome binocular with color trinocular stereoscopy. Doing so will give an error-reducing redundancy to our range measurements, and allow us to detect purely horizontal features. Horizontal edges were lost to matching ambiguity in the original setup, which had two horizontally-displaced cameras. We also plan to illuminate the surroundings with textured infrared light, creating matchable features on uniformly colored surfaces, and to add several camera triplets to widen our field of view, probably to 360°.

• Using a pyramid of image resolutions in the stereoscopic disparity search, allowing it to proceed in equal range steps. Traditionally, stereo searches have been in constant resolution pixel steps, but by stepping through the near field in excessive detail the traditional approach expends a excessive of effort and generates unnecessary numbers of false positive matches at close range, where they cause the most trouble. The latter is especially a problem when an occlusion hides the correct match. Variable resolution matching will be both faster and better, because unavoidable matching errors will be spread uniformly over distance, rather than being concentrated in the robot’s immediate obstacle zone.

• Higher resolution grids, which we have observed to improve performance. With careful algorithm choice, the main cost of modest resolution increases is in required memory.

• Adding data from other sensors. Most of our robots carry sonar and contact transducers, and the grid representation allows evidence from all sources to be combined.

• Many subtle improvements in matching functions, search strategies, data representations, etc. For instance, we have recently discovered that cross entropy has superior properties for matching than the similar log probability formula we had been using.

Year 2 Agenda: Recognition Layer

In the second year we will build a layer of recognition software that uses the data collected in the grid to navigate and locate important world features. In this group will be procedures to:

• Plan and execute obstacle-avoiding paths in grid spaces. Grids are very good for this purpose, because they provide positive indications of empty regions. We have already written an A* path planner, which works, but is several times too slow. The following image is an example of a path from this program operating in a robot-height slab of the office grid shown in the first illustration. A coarse-to-fine strategy or other approximations should allow us to .

• Store away and retrieve 3D map snapshots of the surroundings in a compressed form, and to volumetrically register a current map against a stored map. This technique can be orchestrated into a route-learning program, in which a trail of snapshots is stored on a training run, against which to position the robot when it travels autonomously. Differencing of maps registered by large-scale features could be used to locate smaller objects that have moved. Computational efficiency is major concern.

• Extract geometric architectural features, for instance to identify open floor area, walls, doors, corridors and rooms.

• Match smaller scale volumes, for identifying furniture-scale objects, including people, using techniques probably similar to map matching but optimized for smaller volumes and articulated parts.

• Build long-range topological maps by piecing together local geometric grids with approximate transforms.

• Generate paths in topological maps that minimize travel, sweep the ground, or provide best vantage points, as needed by anticipated applications.

Year 3 Agenda: Application Layer (Extension Option)

The first two years of the project are naturally capped by a third during which we would tune up and orchestrate basic perception and identification abilities into complete useful applications. Since the BAA solicited a 24 month effort, we propose this third year as an optional extension.

In the third year we would construct several demonstration applications in a third layer of code. The idea is to use the powerful lower layers to create task-specific but location-independent programs. For instance, a point-to point delivery program will be constructed to learn any route by saving a trail of map snapshots in a training run. A floor cleaning program will identify the boundaries and obstacles in any environment, and plan a covering route. A security program may be built to explore a network and plan a randomized route that leaves no area unvisited for very long. These programs may be quite straightforward themselves, but their success on the reliability of the 3D maps produced by the perception layer, and the identifications extracted by the identification layer. It is certain that extended application trials will uncover subtle weaknesses in the lower layers, and we expect to spend much time in the third year dealing with such foundational issues.

Testbeds

Our robot-controlling computing platforms should be updated on an approximately annual basis, to take advantage of increasing available performance. We presently are using a dual-processor Pentium-II Dell PC that provides about 700 MIPS, and running a realtime BE Inc. operating system. By the third-year period we expect to have about 3,000 MIPS available, and may have changed operating systems more than once. Our robot code is written in C and C++ and is quite portable, and has made transitions between systems several times. We plan to have more computing power than we expect in a final commercial product to allow us to quickly test and perhaps reject new ideas without the onus of immediately optimizing every implementation for speed.

For mobile robot platforms, we are presently using the Uranus mobile robot, which we constructed ten years ago, and also retain the option of using our even older machine, Neptune. Uranus is aging, slow-moving, short on battery stamina, often unreliable, and uses difficult-to-maintain obsolete components. Neptune is simpler and more reliable, but tethered and thus usable only for very short-range experiments. To avoid expending excessive effort on robot maintenance, we think it is necessary for the success of the first years’ work to upgrade to a modern smaller yet more capable and reliable robot platform.

Test Robots: The Uranus mobile Robot, left, with trinocular cameras and sonar ring. The Neptune robot is seen at the right.

In the first two years, the an ideal platform would be a robot just big enough to carry cameras, inertial system, communications and sensor and effector controlling computer and wireless ethernet. We could then use an offboard large desktop machine for the heavy computation and display, shipping digital images and other data over the ethernet link. The robot would be small enough to extricate by hand when it gets into trouble. One suitable machine is the Nomadics Scout II, weighing 25 kg and costing about $5,000. Others, slightly less attractive, are the RWI Mach 5 and microATRV costing about $7,000 each:

Nomadics Scout II         RWI Mach 5             RWI microATRV  

The navigation head would contain 360 degrees of stereoscopic cameras and other sensors, an inexpensive inertial navigation system to inform it about small motions without depending on accurate odometry from robot wheels, 1,000 MIPS of computational power, software for basic navigation, and software hooks for applications specific programming and hardware interfaces for vehicle controls, probably through a standard connector installed into the vehicles. Offered as a retrofit for existing factory transport machines, self-powered floor cleaners and others, it could quite possibly expand the market for robotic vehicles tenfold from the current tens of thousands, and might reach millions if it could be programmed to be a safety assist or autonomous controller for forklifts.

After some years of development, we imagine the technique’s costs will fall and the performance rise enough to permit the design of truly mass-market products. A possible first product with mass-market potential might be a small robot vacuum cleaner, which can reliably and systematically keep clean designated rooms in a home following a simple introduction to the location, keeping itself charged, and delivering dust to a base collecting station.

The simple vacuum cleaner may be followed by larger and smarter utility robots with dusting arms. Mobile robots with dexterous arms, vision and touch sensors will be be able to do various tasks. With proper programming and minor accessories, such machines could pick up clutter, retrieve and deliver articles, take inventory, guard homes, open doors, mow lawns or play games. New applications will expand the market and spur further advancements, when existing robots fall short in acuity, precision, strength, reach, dexterity or processing power. Capability, numbers sold, engineering and manufacturing quality, and cost effectiveness should increase in a mutually reinforcing spiral. Ultimately the process could result in “universal robots” which can be do many different tasks, orchestrated by applications-specific programs.

/users/hpm/hpm.cv.html

Martin C. Martin

Martin joined the Mobile Robot Laboratory and became as a PhD student in 1993, having already done noted undergraduate work in vision-based robotics at the University of Toronto. He quickly proved his skills by modifying a sensor model learning program to efficiently use a conjugate-gradient hill climbing strategy and learn 100 times faster than the original implementation. He also put together a first front end for the 3D grid program, and restored and conducted navigation experiments with the Lab’s aging Uranus Mobile robot, as well as being a valuable participant in a half-dozen other robotics efforts not directly related to this proposal. Recently, towards completing his thesis, Martin did all the planning, hardware, firmware, systems work and high-level programming necessary to assemble the system described elsewhere in this proposal, that uses an off-board dual-processor Dell computer to control the Uranus robot. His system serves as a prototype model for the testbeds we propose. Martin’s thesis topic, to automatically evolve effective high level organizations to integrate lower-level sensing and control techniques into maximally-effective overall robot controllers, is tangential to the exact focus of this proposal, but his participation has been an essential part of the work so far, and will continue to be so until he graduates. He is likely to graduate within the contract period, in which case another student or perhaps additional fractional effort from regular engineering employees will be needed to fill the void.
Martin’s full CV is at

/users/mcm/cv

25% Engineering Support

In addition to the full-time participants, there is often a need for specialized mechanical, electronic or software expertise in our work. It is time-consuming, inefficient and distracting for the researchers to always become skilled in every relevant facet of building and keeping the robot system operational, and we often feel to need to contract out some of the necessary work. The quality of the work is usually superior when we do. Our work volume does not warrant a full-time person, but we easily generate several month-long projects a year, for things like building interface hardware and writing device drivers, building cables and test stands, interfacing to university networks, managing software upgrades and the like. Fortunately there are many skilled individuals in the university and nearby whose assistance we can contract as necessary.