True, Alvinn and Eddie were at the controls the entire time. But they’re not licensed drivers. They’re not even alive. They’re computer programs. This half-mile excursion--including the arranged appearance of the careless child--was a road test of their skills. Alvinn, or Autonomous Land Vehicle in a Neural Network, is a unique steering method that keeps the van on the road and in the proper lane. Eddie is a communications coordinator that receives Alvinn’s instructions, along with the perceptions of a laser range finder, a computerized road atlas, and other onboard sensing mechanisms. Also known as the Efficient Decentralized Database and Interface Experiment, Eddie then translates them all into commands that tell hydraulic systems to move the van’s pedals and a belt- driven motor to turn the steering wheel. Together, the pair makes up the mind of Navlab I, a van that drives itself.
Sending a child to dash out in front of a driverless van may seem less than responsible, but it’s a measure of just how much confidence Charles Thorpe has in Navlab’s ability. Thorpe is the computer scientist who manages Carnegie-Mellon University’s Navlab (short for Navigation Laboratory) project, and the child is Thorpe’s son Leland, who was four years old at the time. Leland thought it was great, Thorpe says, laughing off comparisons to William Tell. Thorpe himself had been the voluntary obstacle in the van’s path during countless other tests. Besides, he adds, we always conduct our experiments with a human backup driver behind the wheel. He’s always ready to mash on the brake pedal if the computers fail.
After six years of tests over an array of roads and open country, two Navlab vehicles have compiled impressive résumés. Navlab I, a 1985 Chevy van, can drive in reverse as well as forward and can follow a road precisely in pitch darkness. Navlab II is an Army truck that once cruised-- under Alvinn and Eddie’s control--more than 21 miles on a four-lane highway at speeds up to 55 miles an hour.
The truck is on loan from the Department of Defense, which has funded most of the Navlab development. Understandably, the Pentagon is intrigued by the cost-saving potential of driverless convoys as well as by the life-saving potential of unmanned attack or reconnaissance vehicles and battlefield ambulances. But the Carnegie-Mellon researchers are also tinkering with control programs that could guide a truck along a garbage route, hunt forgotten land mines after wars, or reconnoiter toxic-waste dumps.
Perhaps the most remarkable thing about Navlab is that it’s actually out on the road. Engineers have been dreaming of robot cars for decades. The major contribution of the Carnegie group is they don’t just simulate things, says Norman Griswold, an electrical engineer and specialist in robotic vision at Texas A&M; University. When you simulate theoretical ideas in robotics or artificial intelligence, they can look wonderful. But when you actually put them in a machine or a vehicle, they might not work at all. If you want to see if your ideas work, you have to try them on a physical machine.
The physical machine that is Navlab II, the most up-to-date model, has a video camera atop the cab that scouts the ground ahead to locate the road and lane dividers, as well as a laser range finder that scans the forward terrain. Its beam of reflecting invisible light, working much as radio waves do in radar, serves two functions. First, the amount of time it takes for the beam to bounce back from an object--a tree, say, or a wall--tells the range finder how far away that object is. Second, the amount of light reflected back, as well as the pattern of the reflection, indicates the shape and type of the object. A parked car, for example, reflects more light than does a lawn. Navlab can then be warned to either swerve around obstacles or stop before hitting them. The reflected silhouettes can even be matched with landmarks noted on digital maps stored in the van’s computers, helping Navlab to figure out where it is along a given route. The van’s guidance and control systems can also be taught that some specific shapes are meaningful--that, for example, a small eight-sided object atop another, very narrow, object at the roadside means the van should come to a full stop alongside that pattern.
The truck also houses an inertial guidance system borrowed from a surplus Army howitzer. The system, which is slightly larger than a shoe box, uses a trio of accelerometers--instruments that measure changes in speed--to determine how fast and how far Navlab has gone. It also uses gyroscopes to help Navlab keep track of when it turns left or right.
All this information is processed in Navlab’s equivalent of a cerebral cortex. The Army truck, for example, carries three workstations, and within them sits Navlab’s chief navigator, the neural network called Alvinn.
A neural network differs from standard computer processes in a fundamental way. Generally computers rely on linear, either-or reasoning that proceeds one bit of information at a time. Such computers can’t generalize; they need to be told what to do in every eventuality. For some tasks--recognizing every possible written version of the letter w, for example, or knowing in advance every possible visual signal that might help to identify a roadway or traffic lane--this necessitates instructions of near-impossible volume and complexity. (In fact, a German research group has taken just such an approach in building a robot car that has done 60 miles an hour on the notorious autobahns. But the German project requires highly specialized computers that can’t make the intellectual leap from a ten-lane superhighway to a small country road.)
A neural network, though, is designed to deal with data arrayed in patterns, much as the human brain does. When you learn how to write the letter w, for example, your brain stores the information as a unique and complex electrical pattern among millions of nerve cells, or neurons. When you see other w’s on a piece of paper, a large part of that neuronal pattern is activated, even though those w’s may not be identical to the first w you saw. Over time and through experience, your brain learns to recognize the essential features of a w, no matter what its size or exact shape.
A computer-simulated neural network employs the same basic strategy. Think of a dozen people all writing the letter w, each version on top of another, on the same square inch of paper with the same ballpoint pen. Some of the script lines will wander off on their own and fail to match the trail of others. But many will track quite closely the lines left by previous writers. If you then turn the paper over, the most prominent grooves you see will represent the generalized pattern drawn from all the specific examples of the written letter--in effect, a generic w. A neural network learns in the same way. As it absorbs examples, the basic pattern common among those specific instances becomes more vivid among the network’s electronic library of experiences. When the network again sees the pattern it has generalized from those examples, a unique configuration of neurons in the network fires. After seeing enough examples of a single pattern, a neural network can even make educated guesses about whether an incomplete or deformed specimen is an example of the pattern it’s learned.
As a neural network, Alvinn learns to steer by example--in this case, by noting the steering decisions a human driver makes on the road. Through the video camera, Alvinn watches what the driver does so it can learn which features in the image are important, explains Alvinn’s inventor, computer scientist Dean Pomerleau. Maybe it’s the edge of the road or the yellow line painted down the center. It sees which of these features indicate steering boundaries and learns to keep the vehicle inside them. You let Alvinn watch for about five minutes, then it takes over.
Alvinn begins its education by fracturing the front-mounted video camera’s image into a grid of 960 small squares, or pixels. Each pixel is connected to a small part of the computer’s memory called, not surprisingly, a neuron. These neurons respond to the intensity of the light from a pixel by translating it into a numerical value on a 2,560-point scale. If the pixel sees black--a portion of an asphalt road, for instance- -that value is low. If the pixel sees white--part of a white center line-- that value is high. The 960 input neurons send these values on to a second, intermediate layer of four processing neurons, which evaluate this information in deciding which way to go.
Eventually they do this by treating some of the values as more important than others. But when a human driver first takes Alvinn for a ride, these decisions are made at random. The processing neurons can’t yet tell the road from any other point on the landscape. A neuron that thinks a particular pattern of light and dark crossing its portion of the video display is roadway will pass its steering recommendation on to the network’s array of 30 outermost neurons. These output neurons represent a spectrum of possible steering directions, ranging from a sharp left turn to a sharp right one, which Navlab’s onboard video display screen represents as a horizontal line.
The output neurons highlight the points along that line that the four intermediate neurons find most enticing--in other words, the directions in which the neurons think the vehicle could prudently steer. Of course, it’s never prudent to try to steer a vehicle in more than one direction at a time. When Alvinn sees more than one way to go, it makes its final decision logically: it plots on a bell-shaped curve the numerical strengths of the points highlighted on its artificial horizon. It then lays in a course toward the point on its horizon that represents the peak of that curve, reasoning it to have been voted most likely to be the road by a majority of the input neurons.
At first, this is just a random choice across the visual field. But when Alvinn is taking driver’s education, it compares the excitement levels of the points along its artificial horizon with a similar horizon and plot denoting the human driver’s actual decisions. For example, a human driver might be steering straight ahead while Alvinn-in-training thinks that Navlab should curve to the left. When Alvinn compares the centermost points on the two output arrays, it sees that the driver’s centermost output neuron is active while its own isn’t. Because it’s been programmed to mimic the driver’s responses to visual patterns, it recognizes that it’s making a mistake.
In a case like that, Pomerleau explains, Alvinn sends a message back down to the intermediate neurons that says, ‘When the visual image looks like this, you should maximize the numerical value of your excitement in a way that points to the centermost output neuron.’ Alvinn learns by realigning the weights of excitement among its neurons to deliver the same response as the human driver does to a given visual pattern.
After a few minutes, Alvinn has amassed enough comparisons in its memory to know which shade of gray most likely represents the roadway and which lines of contrast along the sides of the video image represent lane markers or road boundaries that the vehicle shouldn’t cross. After the training trip, Alvinn retains the images and becomes a specialist for the roadway.
Eddie supplies the judgments and reflexes that translate Alvinn’s judgments, various road maps stored in the computer’s memory, and the range finder’s obstacle information into a trip to the store.
Eddie gets involved at the beginning of a trip to make sure the various systems are communicating and working together, Thorpe says. Once he’s done that, he gives the systems each other’s addresses and then steps out of the way. En route Eddie simply monitors messages; it gets involved only when it sees a need for action. We call it priority arbitration, Pomerleau says. For instance, when the obstacle-avoidance system tells Eddie to drive straight ahead, Eddie is programmed to give it a low priority because it’s not seeing anything unusual. But if something darts into the vehicle’s path, the obstacle-avoidance system sends out a signal that Eddie then will give the highest priority to.
When Navlab arrives at an intersection, for example, Alvinn might not be able to decide which stretch of road to follow: both have curbs and lanes, and both look equally valid. At least two diverse steering points on Alvinn’s horizon are equally excited. So Alvinn signals Eddie that it’s confused about what to do. Eddie relieves Alvinn of steering duties and turns control of the van over to the mapping and inertial guidance systems. In a similar fashion, if the laser range finder spots an obstacle that doesn’t show up on Alvinn’s view of the road, then Eddie tells the vehicle- control system to swerve or hit the brakes.
Before Navlab’s 1990 suburban jaunt, Thorpe drove the van through the neighborhood, letting the range finder and guidance system note the location of curves, intersections, and landmarks. When the trip was to begin, he indicated on the resulting computerized map of the area the route the van was to take and the house it was to stop in front of.
On the journey Alvinn kept nicely to its lane. When the van confronted intersections, Eddie gave control to the range finder and inertial guidance system. The laser spotted landmarks while the guidance system used its record of how far the van had traveled and where it had turned to place Navlab along the indicated route. Once through the intersection, Alvinn took the wheel again. The van didn’t run stop signs or clip parked cars; it didn’t mow down children or pets nor earn traffic citations for reckless driving.
Deft as they are, though, the Navlabs are far from flawless. On a test drive last January the Army truck embarrassed a group of graduate students who had brought it to a gravelly field in east Pittsburgh. The students had come to gauge Navlab’s ability to drive on roadless ground and to dodge the single obstacle--the standpipe of a cistern--that rose above the cleared plain. The structure resembled a two-tiered wedding cake: a concrete throat, perhaps four feet across, rose about two feet from the dirt, with an iron manhole cover rising another six inches above its surface.
The laser range finder scanned the terrain as far ahead as it could see--about 60 feet--and then the truck was under way. It wove among bumps and ruts as it approached the standpipe, then lurched to the left to avoid it. But it ended the maneuver too soon. The truck cut back sharply to the right almost instantly, scraping its undercarriage along the edge of the concrete. A few seconds later, it was beached completely on the edge, its rear tire spinning helplessly in the air.
The Navlab was avoiding the manhole cover, but not the concrete throat, fellow traveler Barry Brumitt determined after several minutes of tapping on a computer keyboard in the truck’s cargo bay, reconstructing the Navlab’s decisions at each point during the exercise. The manhole cover is high enough for the range finder to see. The throat is low enough that the range finder wasn’t able to distinguish it from the ‘noise,’ or static, created by its own processing. The lanky, bespectacled engineer shook his head. That’s going to be a tough one to solve.
If the researchers set the range finder’s sights low enough to pick up the concrete throat, it would also pick up all the ruts and bumps, causing Navlab to swerve needlessly around them. But the implications of not making the adjustment aren’t easy to contemplate, either. If you’re standing in the street, the Navlab will veer around you or stop. But if your toddler is sitting in front of the curb or your dog is napping in the driveway, Navlab won’t distinguish them from bumps in the asphalt. Part of the answer is a more sophisticated sensor, which we should be getting soon, Brumitt says. But part of it is in the software. We’ll just have to go in and fix it.
That’s not the only pothole in Navlab’s path. There’s still a lot to do before we’ll be ready to put this on the street and let it go, Pomerleau admits. We’ll need to show thousands of hours on the road without even a minor glitch, and right now we’re a long way from achieving that kind of reliability. For one thing, the laser’s limited visual range won’t let it see oncoming cars far enough away to give Navlab time to react. Basically, Navlab has to trust other cars to stay in their own lanes, Thorpe says, noting that a more farsighted scanner, due soon, should ease the problem.
Another immediate challenge is to wean Navlab from its dependence on computerized maps. The suburban trip was very successful largely because Chuck had driven the van through the neighborhood first to map it, says Jay Gowdy, Eddie’s programmer. But you don’t want to have to drive from Pittsburgh to Chicago in order to be able to drive from Pittsburgh to Chicago. You want to be able to tell the Navlab, ‘Take Interstate 12 to exit 35,’ and turn it loose. It’ll be a few years before we’ll be ready to do that.
Thorpe and his team had better get cracking. Navlab’s descendants have some serious expectations to meet. Obviously, the military is interested, he says. They’d like to get a pair of eyeballs over the next hill to see if the enemy’s there. Instead of sending your least favorite person to do it, you could send a self-driving vehicle with sensors and a camera. The Pentagon isn’t the only potential Navlab user with imagination, though. This kind of vehicle could drive around hazardous- waste sites and pick up samples, explore the surface of Mars, or retrieve something lost on the bottom of the ocean, Thorpe adds. It could do anything that’s too dangerous, too expensive, or impractical for a person to do.
However, he’s quick to point out that the current technology could be more easily and quickly applied to the less dramatic tasks of sweeping streets, picking up garbage, or delivering mail. These would be repetitive routes, so a vehicle could be shown it once and then do it every day, he says. It could even do these chores at night when there isn’t much traffic, so it could travel at slow speeds.
The CMU team is making progress. Three months ago, after some intensive software tweaking, Navlab II successfully picked its way among several obstacles similar to the cistern that had foiled its earlier attempt. And the researchers have ordered a new infrared camera to augment the vehicle’s senses. The camera detects heat, allowing Navlab to drive with blithe accuracy in complete darkness. Pavement absorbs heat all day and releases it at night, so the road just booms back at the sensors after dark, Thorpe explains.
But not all the obstacles that Navlab must face--and circumvent-- are in the roadway. One of the toughest, the designers admit, is public acceptance. When we were testing it in the suburbs, we made people nervous, Thorpe says. The van had all this equipment mounted on the top, and we were running around in the back wearing headphones, and the generators were making a lot of racket. Some people called the police. They thought we were the bomb squad.
Skydrivers
The next time you grind to a crawl on the freeway, look to the sky and think kindly of Steven Crow, who is working to relieve your frustration. Crow, a professor of aerospace and mechanical engineering at the University of Arizona, is laying the groundwork for an airborne road system. In the Crow’s-eye view of the future, your car gets fitted with wings, you climb inside, punch a destination code into a computer console, sit back, and soar off into that great highway in the sky.
Flight of fancy? Perhaps. One actual flying automobile, called the Aerocar, was built during the late 1950s and still soars in Florida. But you need a pilot’s license to operate it, and the mental demands of aviation would vapor-lock the average motorist.
Though Crow admits he’s years from lofting his first flying machine, he’s found a way around the vapor lock. His grounded prototype, a white Dodge Caravan called Starcar 2, is already driving itself around a Tucson sports track. You see, Crow’s cars won’t just fly--they’ll fly themselves.
Starcar’s approach to autonomous navigation steers clear of the image-sensor-driven course taken by Navlab. Sensors are clutter-limited: they have to discriminate objects of importance from the background, Crow explains. That’s a computationally intensive process. What we’ll do is determine position and velocity with a trivial computer load.
The key is the Global Positioning System (GPS), the flock of military satellites that broadcast exquisitely timed signals worldwide. After bringing in these signals, receivers on ships, planes, and tanks can reckon their location, altitude, and speed with an incredible degree of precision. Users outside the military can also tap into these signals and have now devised mathematical tricks that push the devices to an accuracy far beyond what the Pentagon originally intended for civilians.
Like Starcar 2, Crow’s flying machines will carry GPS receivers and use the information to guide themselves along electronically prescribed routes. They’ll also continually radio their own position and velocity to other vehicles nearby. From those few pieces of information, says Crow, each onboard computer can construct a collision-avoidance strategy. Just like at an intersection, where you decide which guy goes first, everybody shares the same set of rules.
Crow is not the only one with his head in the clouds. Other researchers are also hoping to harness GPS for hands-off flying. At NASA’s Ames and Langley research centers, for example, engineers are testing the system’s precision for blind approach and landing at airports. You can do a lot of things if you know where you are accurately, says David McNally of Ames. It’s certainly feasible to use GPS for collision avoidance.
True, it’s one giant leap from autonomous aviation to an aviating auto. But only when he’s sure that his vehicles will exercise self-control will Crow tackle the big hurdle--building Starcar 3, the next generation, an electric car with add-on wings and gas-turbine engine. His performance goals are a top speed of 300 miles per hour, a flight ceiling of 14,000 feet, with a maximum cruising range of 800 miles.
Meanwhile, Crow’s used to hearing every kind of reaction to his flying cars. If I’m talking to an old-time engineer, it’s ‘You’re a nut, Crow.’ If I’m talking to anyone else, it’s ‘When can I buy one?’ --Gregory T. Pope
