Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover, Hans Moravec, 1980
<-- Previous  Next -->

Chapter 11: Future Carts

It will be obvious that the current system is very minimal, both in hardware and software. The hardware limitations not only necessitated considerable repair time, which reduced time available for more advanced work, but they also had a direct effect on the performance of the final product.

Strength of Body

Feedback to the program about steering angle and about the number of rotations of the wheels in a forward move would have permitted a much more reliable estimate of the new cart position after a move, and before the vision step. Such a priori estimates would have eliminated the main source of trouble in the flawed outdoor cart run, almost certainly turning it into a success in spite of the poor seeing (in the early steps of this run, the program had correctly located most of the relevant obstacles. As it proceeded forward, moving shadows and the general lack of solid features to track caused increasingly serious mis-estimations of its own position, and later sightings were consequently assigned the wrong positions in the world model, eventually turning it to trash).

The failure of the program to notice the fake tree in the two short abortive indoor runs would not have been fixed by steering and travel distance feedback alone, but could have been saved if the cart also had reporting touch sensors. On running into the tree, the cart would have stopped, and its position would have been noted, along with the position of the touch relative to the body. The position of the touch would have been added to the world model, just like any visually perceived feature. The next path planning step would take it into account, causing suitable backing up of the cart when it moved, probably turning a failed run into a moderate success. Such last ditch physical obstacle detection is no substitute for improving the vision, but it would take the system a step closer to practicality. A proximity sensor could do even better, by detecting an imminent collision, or a near miss, without physical contact.

Sensors of this kind would require two-way data communication between the cart and its controlling computer. Currently the computer commands motions, and the cart transmits pictures only. A small computer onboard the cart would permit a bidirectional, error checked, link. It would also permit down-loading of small control programs which servoed position and speed, and had provision for dealing with unusual circumstances, such as encounters of the touch sensors with obstacles. Doing this remotely through the radio link is risky, because the data rate is not very high, and because the link is subject to noise, which could come at a critical time.

The cart's physical size, about a meter cubed, and weight, about 100 kilograms, created many experimental difficulties. It requires a lot of room to move. The outdoors is too variable an environment for serious work at the present tender stage of the software; besides, running during daylight hours is incompatible with getting many cycles out of a time-shared computer. Thus the cart needs a large indoor arena. We were lucky to have had a suitable room in the D.C. Power building. The new computer science building is not so generously endowed. Other problems with the cart's size involve its repairability; it could not be brought into convenient shop areas since it was too wide to pass through standard size doors, and often had to be worked on in peculiar postures, since it is too heavy to turn on its side (deliberately anyway). Its weight demands large motors and batteries, and associated driver electronics; these are proportionately more expensive than smaller ones, and also harder to obtain. The large components translate to a certain coarseness in mobility and maneuverability; a reasonable itinerary must cover tens of meters. This implies that the radio links must have a useful range of hundreds of meters, to keep signal strengths roughly uniform (and to avoid having to relocate antennas when moving the cart to different nearby environments).

Progress in reducing the size and power consumption of electronic components (particularly the existence of small solid state TV cameras), makes the concept of a much smaller robot rover, perhaps a third to one half a meter in diameter, reasonable. Instead of carrying batteries with a capacity of a thousand watt hours, it could make do with one or two hundred. Its transmitters would broadcast with fractional watts, instead of several watts, and the distances would be a few meters, instead of a few tens. Setting up obstacle courses and running experiments would be much less arduous with such a mini robot, which could be picked up and easily carried from place to place. On the other side of the coin, building some of the components, particularly the onboard transducers and sensors, will require more delicate work than would be required on a bigger vehicle.

A New Cart

Here's a rough description of such a second generation cart. On a platform about 40 centimeters square, made mobile by two slow moving motorized wheels and a freewheeling caster, each equipped with shaft encoders, we have small sealed lead-acid cells with a capacity of about 10 amp hours at 24 volts. By the side or above these are D.C. to D.C. power converters which produce up to five amps of regulated five volts, and a few amps of regulated +24 and about an amp of + and - 12 volts. All power used by the vehicle is drawn from these supplies, insulating it from voltage fluctuations. The overall height of the vehicle is under a meter, with most of the weight being in the batteries and drive motors near the base.

A control board carries a CMOS microprocessor, with interfaces for the shaft encoders and other sensors. It has spare digital and analog channels for sensors that might possibly be added later. It talks to its fixed large computer through UARTs and high power pulsed infrared LED's and photodiodes; this greatly reduces the problems of electrical interference and works well within the confines of a single room \ref{S1}. The effect on optical proximity detectors remains to be assessed. This problem too may be evaded by using an ultrasonic ranger. Polaroid offers the very effective one available with their cameras in an inexpensive kit.

The video system consists of a solid state camera mounted on a three degree of freedom pan/tilt/slide mechanism, precisely controlled by the microprocessor, powered perhaps by stepping motors. The picture from the camera is broadcast with a power of about half a watt in the UHF band to a nearby receiver connected to the mainframe computer through a digitizer.

Communication between the microprocessor and the mainframe is through an arpanet-like error corrected packet protocol further secured by checksumming and retransmission of packets in the absence of acknowledgements. Rod Brooks has done some work on this problem \ref{B3}.

Strength of Mind

As important as the physical vehicle, is the large processor that does its thinking. Even the level of performance of my current system taxes the DEC KL10 it runs on. The program is so slow that improvements in performance gotten by reducing the speed are just about out of the question.

Not only is the processing power taxed, but the memory limits are as well. Many of the components of the program work best when considerable amounts of data are directly accessible, from several pictures and subwindows in the vision part of the code, to distance matrices and arc lengths in the path planning. A widely available large address space machine like the DEC VAX solves the space problem (for a while), but does little (or nothing) about the speed.

About one third of the runtime in my program is devoted to extracting good pictures from a rather poor digitizing system. A modern digitizer such as can be provided with new Grinnel display systems, makes the process almost instantaneous.

Perhaps half of the remaining time is spent doing array type operations such as convolutions, array summing and peak detections. A fast array processor which can be interfaced to a VAX could obviate most of that.

Some of the remaining time can be eliminated by using the address space to good effect, simple coding efficiency improvements would also give a factor two or more in some of the later code (which I've spent less time optimizing).

Combined, these techniques might speed things up by a factor of five, which would give considerable breathing room for new experiments and extensions. Farther in the future faster VAXes and multiprocessors could do arbitrarily much more.

What Then?

How does one use an improved cart connected to an improved computer? Experimenting in the effect on performance of various alternative approaches and algorithms is important, if unspectacular, work. A newly created version of the obstacle avoider would surely deserve some of that.

There are many subtle improvements possible. Determining the position of the ground by observing the 3D path of the cart is a relatively easy extension not in the current program. The long term navigational accuracy of the system is poor, depending as it does on a chain of only approximately correct co-ordinate transforms deduced from the vision. Some sort of long term landmark identification would be a great improvement. A by-product of such improvements would be fairly good maps of the vicinity of territory traversed.

The cart now sees by tracking patches of image from one picture to another taken from a different position. It has no means of inferring the existence of featureless obstructions such as clean walls (and the interior of smooth cardboard trees and rocks!). Others have attempted to build systems that infer the existence of extended objects from a coarse sampling of their surfaces, or from their edges. Presently the “blocks world” systems are too restrictive, and those that work in more nearly the “real world” are too slow. Improving them, or developing better substitutes, is a worthy project. Requiring them run a real robot is an excellent way to keep the work honest.

Other “fun” projects involve programming the robot to notice holes, trenches and cliffs (inevitable disaster can be avoided by covering such hazards with glass). Much harder is a learning mode where the system could be trained to recognize objects of particular kinds, like rocks. The training might consist simply of a description given in a specially designed recognition language. Such a capability would be a great asset in a semi-autonomous planetary explorer, which would stop and ask for assistance from afar only when it encountered something new

<-- Previous  Next -->