Driverless Vehicles Take on the Desert

In the pre-dawn hours of October 8th, the engineers will be out in the desert darkness, lining up their all-terrain vehicles, SUVs, Hummers, and pick-ups, to have a go at the impossible. And after all the sensors and servers, lasers and LIDARs, steer-by-wires and brake-by-wires have been checked and re-checked, and the flag has dropped, they'll have to let go and watch their offspring take off for the nearest sand dune and roll out of sight. Like helpless parents, they'll wait, unable to do anything until they hear that their vehicle has crashed, stalled atop a rock, launched itself into dizzy circles like a dog chasing its tail, or, ultimately, crossed the finish line 175 miles away and earned the $2 million, winner-take-all prize.

Not since the fabled trans-continental races of a century ago have so many engineers, professors, students, corporate teams, and garage tinkerers been drawn to so daunting a task.

On the surface, it seems, well...impossible. Once the race starts, the design teams can do nothing. There's no remote control, no driver. Using stereo cameras, radar, and lasers, the vehicles themselves must check for obstacles, then roll forward at speeds up to 60 mph, across sand dunes, through valleys, along highways, and over rivers, all the while obeying the way-points beamed to them from global positioning satellites.

Like any human driver, they'll have to make decisions. They'll have to determine whether the object in front of them is a brick wall or a cloud of dust, a flying insect or a line of barbed wire. They'll have to spot cattle fences and so-called "tank killers" (lengths of angle iron laid atop the desert floor to stop their progress) and steer around them.

To be sure, the teams have done this before, and fared poorly. None of the vehicles in the first Grand Challenge in 2004 drove more than 7.4 miles. One got hung up on a small rock six miles into the competition. Another inadvertently applied its brakes and quit after traveling just 50 yards. A third, a 10-ton commercial truck, lumbered forward a few feet and stopped like a confused buffalo, overwhelmed by the multitude of sensor signals zipping past its small brain. Scores of other entrants finished in a similarly undistinguished fashion.

Still, the entrants say that this race will be different. "This year you're going to see much better results, in part because the teams have had time to finish their software," notes Brad Chen, senior architect for the Performance Tools Laboratory at Intel Corp., which supports teams from Stanford University and Carnegie Mellon University.

"It's our belief that a number of teams could actually finish this time," adds Bruce Hall, president of Digital Auto Drive, a company that has also fielded a vehicle. "It's going to be a different race this year."

  Choose a StrategyIn map-based detection, terrain maps display obstacles on a grid, with higher values representing bigger obstacles.  In behavior-based detection, computers employ logic to chart a vehicle's course. Map-based path planning  

Behavior-based path planning  

Urgent and Important Indeed, it will be different, if for no other reason, because the engineering teams now understand how difficult this task really is. The concept itself is easily articulated: Build a vehicle that can successfully follow a 175-mile course. But the Defense Advanced Research Projects Agency (DARPA), an arm of the U.S. Department of Defense, has deliberately added obstacles, physical and otherwise. The corridors that the vehicles must follow are mostly off-road, strewn with foreign objects, and yet they must still finish within ten hours, suggesting a non-stop speed of 17.5 mph. Furthermore, DARPA is unyielding about course information, apparently to prevent smart teams from pre-programming their way along the way-points. As of this writing, the agency has said only that the course will "feature demanding desert terrain" somewhere in the southwestern part of the United States, presumably the Mojave desert. There is, of course, a sense of urgency and importance behind all of this. The Department of Defense wants technologies that can aid in the creation of autonomous battlefield vehicles. "If you ask DARPA why they are running this race, you'll hear that they want supply trucks to transport meals, water, and other supplies from Fallujah to Baghdad, without putting soldiers at risk," says Hall of Digital Auto Drive. Moreover, the auto industry is expected to watch the results closely, too. Within the research labs of the big automakers, it's assumed that engineers who have already worked on autonomous lane-keeping and collision avoidance systems will gain from the efforts of the Grand Challenge entrants.  

Professor Charles Reinholtz's Virginia Tech team has entered two vehicles: "Rocky" uses a map-based obstacle detection technique, and "Cliff" employs a behavior-based method. Not surprisingly, however, the entrants themselves say this is more an exercise in robotics than in automotive engineering. "Everyone sees the driverless racers rolling across the desert," notes Professor William "Red" Whittaker, Fredkin Research Professor of Robotics at Carnegie Mellon University, and team leader for the school's two entries. "But the reality is not so much that they are rolling, but rather, computing their way across the desert." Plotting the Course For most, computing is an extraordinary challenge because it must serve as the underlying foundation for two functions: following the GPS way-points, and avoiding obstacles on the course. Way-point following in itself can be difficult, entrants say, and it can become more so when finicky GPS units fail to send ground data. Then, they say the vehicles must use inertial navigation systems (INS), consisting of a combination of gyroscopes and accelerometers, to determine where they are. The INS accomplishes that by using the accelerometers to provide acceleration information in three axes and the gyroscopes to supply angular velocities. "By integrating the accelerations twice and the angular velocities once, you can pretty easily determine your changes in position and orientation," says Charles Reinholtz, alumni distinguished professor of mechanical engineering at Virginia Tech University, which has two vehicles among the Grand Challenge's final 40. Still, many entrants say that way-point-following is virtual child's play, compared to the complexities of obstacle detection. "A lot of people can't get past square one, which is the way-point following," notes Hall. "But the real challenge is to get enough data, so you can make an accurate terrain map, and make good decisions about the obstacles." For most of the 40 contestants remaining in the competition as of early September, obstacle avoidance consists of one of two strategies: map-based computing or behavior-based computing. In the map-based method, a vehicle employs multiple sensors—stereo cameras, radar sensors, laser sensors, and/or LIDAR (light detecting and ranging) devices—in an effort to obtain different kinds of data to build the so-called "terrain map." Vehicle computers then employ home-grown software to examine the incoming data and identify potential obstacles.  

Eyes, Brains, and Muscles:  Virginia Tech's entry uses laser measurement systems, stereo cameras, and radar sensors as its eyes. Multiple servers act as brains, while electronic motors provide the drive-by-wire muscle. Virginia Tech University's "Rocky" vehicle, for example, creates a software grid resembling a tile floor, with grid spaces representing about one square foot. The vehicle's computer then examines incoming data from a Sick Optic laser measurement system and populates those software spaces with numbers ranging from 0 to 10, with tens depicting the worst kinds of un-traversable obstacles. "If we saw a rock, for example, we'd assign a high number to that grid point, which would tell the vehicle not to go there," Reinholtz says. The system then applies software code, such as Djikstra's algorithm and the A* algorithm, to plot a driving path between the obstacles. "Basically, you start the vehicle at one end of the checkerboard, and the object is to get to the other end of the checkerboard," Reinholtz says. The downside to such dependence on the map-based method, however, is that the vehicle can end up trying to avoid artifacts that are so miniscule as to be non-existent. "If a drop of rain or flake of snow or an insect flies in front of the laser scanner, the system could think there's an obstacle there, and place it on the map," Reinholtz says. "And then you could end up trying to drive around it." To hedge their bets, engineers from Virginia Tech have built a separate vehicle, known as "Cliff," which employs the behavior-based method. Reinholtz says that method, which uses basic logic tasks to determine what the vehicle should do, is computationally less intensive and faster in its decision-making ability. Simple queries—such as, "Is there an obstacle in my way?" or "Is there a road to follow?"—form the logic foundation. "The behavior-based method doesn't require a long-term memory," Reinholtz explains. "It's looking out and saying, 'If there's a road, we want to stay on it.'" Compute-Intensive  

Carnegie Mellon's autonomous "Sandstorm" vehicle (with radar system in blue atop roof) drove 200 miles in seven hours in a 1.5-mile paved race course in July. None of that navigation could effectively take place, however, without a vehicle that's essentially a supercomputer on wheels. Carnegie Mellon's vehicles ("Sandstorm" and "Highlander"), for example, carry Intel NetStructure servers that hold five so-called "blades," each with Pentium M microprocessors. The Pentium M's handle sensor data, planning tasks, and action tasks, such as signaling the drive-by-wire units that propel, steer, and brake the vehicle. To complement the NetStructure server, Carnegie Mellon's vehicles also use a smaller, rack-mount server incorporating a parallel computing architecture containing two Intel Itanium microprocessors. The twin Itaniums, which offer better floating point operation than the Pentium M, take on the more compute-intensive task of turning sensor data into navigation information. Other teams are employing prodigious amounts of computing power, as well. Virginia Tech, Rochester Institute of Technology, University of California-Berkeley, Team Ensco, and Team Axion are all employing various combinations of computers, motion control cards, data acquisition cards, vision systems and LabView software from National Instruments. Meanwhile, Team DAD (headed by Hall of Digital Auto Drive), may be employing as many as 15 Texas Instruments (TI) digital signal processors (DSPs).  

Team DAD will employ up to 15 DSPs, enabling it to do as many as 36 billion pixel "ops" per second. Team DAD, which is using a proprietary technique that involves a spinning drum of multiple laser arrays mounted atop its vehicle, employs a combination of TI C2406 and TI C6000 DSPs because its engineers believe huge volumes of data are needed to create a reliable terrain map. "We're processing an unbelievable amount of data," Hall says. "At one point, we counted that we were doing 36 billion pixel 'ops' per second." Electronics engineers contend that such extraordinary computing lengths will be increasingly necessary as vehicles drive faster, and therefore look farther out onto the horizon. Carnegie Mellon, for example, ultimately wants to look out as far as 50 meters ahead of the vehicle, but can't do so yet because such measures would require more computing power. "Given a typical computing budget, you can only look maybe 20 meters ahead of the vehicle today," says Chen of Intel. "If you look farther out, you collect more data, and the computer is swamped."  

Virginia Tech's vehicles use roll-cage-mounted stereo vision cameras and laser range finders to sense obstacles. Even as engineers consider ways to gather more sensor data, however, they must simultaneously allow for the drive-by-wire components that propel and steer the vehicle. Virtually every vehicle must use some form of drive-by-wire, ranging from simple in-cabin systems that actuate the brake pedal and steering wheel, to more complex units that operate under the hood. Either way, engineers say, the by-wire systems must be computationally tied to the servers that parse commands out to the actuators. Team DAD, for example, uses a TI C2406 DSP to control a 20-hp brushless DC, rare earth steering motor. Similarly, it employs two more TI DSPs for the throttle and brake pedal motor, which sits on a hump between the seats of the team's Toyota Tundra 4 × 4. It also employs another dedicated TI controller for its "way-point playback machine," which takes satellite data from a GPS unit John Deere NavCom Technology, Inc., and turns it into navigation information. Market Possibilities Despite the failures of the first Grand Challenge, most entrants believe the 2005 race will show that autonomous vehicle technology is maturing, and much of it could reach the market soon. "If you start with the military market, there are far less restrictions," Hall says. "There, you don't have legal or cost problems, and people don't care what the technology looks like." The automotive market, meanwhile, is expected to take longer. Cost and litigation issues, as well as concern over potential technology mandates from organizations such as NHTSA (National Highway Traffic Safety Administration), could slow progress of autonomous vehicle components. Still, many engineers believe that Grand Challenge obstacle detection techniques could have profound effects on autonomous collision avoidance systems, which are currently under development by tier-one suppliers. "If you look at this from the perspective of enhancing safety, we're going to see some pretty amazing technology in October," says Chen of Intel. Moreover, some engineers believe the Grand Challenge will prove that autonomous vehicles are on the cusp of technical feasibility, public acceptance issues not withstanding. "There's no looming technical reason why this can't be done," says Hall of Digital Auto Drive. "We're years, not decades, away from legitimate, deployable systems." A Grand Challenge Sampler Although 40 teams are still in contention for the Grand Challenge, only 20 of those will race on October 8th. Here are a few of the 40 remaining teams. TEAM WEBSITE COMMENT Carnegie Mellon http://rbi.ims.ca/4396-570 CMU's has two teams. Its "Sandstorm" vehicle autonomously drove 200 miles around a track in July. Team DAD http://rbi.ims.ca/4396-571 Team DAD, seemingly a sleeper in the competition, was awarded fourth pole position the first race. Its vehicle drove six miles before getting hung up on rock. Team engineers have improved obstacle detection with a unique rotating laser array. Virginia Tech http://rbi.ims.ca/4396-572 Virginia Tech has two teams in the final 40: One uses a map-based navigation technique, while the other employs "behavior-based" navigation. SciAutonics/Auburn http://rbi.ims.ca/4396-573 In the 2004 race, SciAutonics/Auburn traveled 0.75 miles before being sidelined by a faulty computer hard drive. Stanford http://rbi.ims.ca/4396-574 Stanford's "Roadrunner," partially the result of consultation with Intel Corp., places heavy emphasis on computing ability. See a list of all 40 semifinalists. Reach Chuck Murray at [email protected]. Resources - for more info Stereo cameras
Sick Optic laser range finders
IBEO laser sensors
Dijkstra's algorithm
National Instruments data acquisition
Texas Instruments C2406 DSP
John Deere Navcom GPS unit
Intel NetStructure servers
Intel Itanium microprocessors
Intel Pentium M microprocessors