The Future of Driving, Part I: Robots and Grand Challenges

Kirby, meet Stanley

(This article is the first of a three-part series. Click here for part 2 and here for part 3)

Until recently, it was the stuff of Hollywood. Movies from The Love Bug to Minority Report have depicted cars that let passengers just hop in, tell the car where they want to go, and then relax and enjoy the ride. But here in the real world, cars need human drivers.

Then in 2005, a modified Volkswagen, dubbed Stanley, turned science fiction into reality. This technological marvel, developed by a team at Stanford, navigated a course of more than 100 miles of desert terrain completely autonomously. There were no human beings inside the vehicle, and no one was relaying instructions to the vehicle from outside. Stanley finished at the head of a pack of 23 vehicles in a race called the Grand Challenge, which was sponsored by DARPA, the military research agency that also provided early funding for the network that became the Internet.

The robotics community outdid itself once again at DARPA's 2007 Urban Challenge. This contest featured all the challenges of the original Grand Challenge, along with a few new ones: the vehicles navigated a simulated urban environment and were required to interact with human-driven vehicles while obeying all traffic laws. Six teams successfully completed the course, with Boss, a car developed at Carnegie Mellon, claiming the prize.

The Urban Challenge participants line up at the starting gate

There's still a lot of work to be done before these vehicles will be mature enough to be let loose on our streets. Real streets contain significantly more obstacles and complexities than the simplified environment found in the 2007 contest, and the most successful vehicles in the Urban Challenge were not designed to cope with pedestrians, bicyclists, traffic lights, or icy roads. And even when the technology is ready for prime time, a variety of economic and political obstacles could delay widespread adoption of self-driving automotive technologies.

Nonetheless, the success of the Challenge series has made it clear that it is only a question of "when," not "if," self-driving automotive technologies will make their way into car showrooms and onto our streets. It's impossible to know exactly when such will arrive, but it's a good bet that a college student entering the workforce today will have a car that can drive him to work before he retires.

Three-part feature

In this three-part feature, Ars will dig into the present and future of autonomous cars. We'll look at where the technology is now, talk about where it's going, and speculate about what the world will look like when we get there. In part one, we'll focus on the technology as it exists today, starting with a review of the history of DARPA's Grand Challenge competitions and a talk with the engineers at Stanford and Carnegie Mellon who helped build the winning vehicles. We'll also look at technologies already on the market, and we'll examine the remaining obstacles—technical and economic—to the advent of self-driving cars in the commercial market.

In the second part of our series, we'll look at the tremendous promise of autonomous vehicles. Automobiles kill hundreds of thousands of people every year—about 40,000 per year in the United States alone. Many of those deaths are due to driver error. Computers are never drunk, tired, distracted, or reckless, so self-driving technology has the potential to save tens of thousands of lives every year. But the benefits of autonomous cars don't end there. Ars will talk to Brad Templeton, the Electronic Frontier Foundation chairman who has recently become an evangelist for self-driving car technology. He argues that autonomous cars can save the environment, reduce congestion, and revolutionize the retail industry.

In our final installment, Ars will examine the major obstacles to the adoption of autonomous cars, and the challenges society will face when they arrive. Vehicles will need to get the approval of government regulators who may be reluctant to allow bleeding-edge technology onto the public roads. Even if the regulators don't stand in the way, car companies may be wary of liability exposure if their vehicles are involved in accidents. Finally, the advent of autonomous cars will create new kinds of public policy issues, including questions about civil liberties and the freedom to modify car software.

These technical, economic, legal, and social obstacles to the introduction of autonomous cars are formidable, but the potential savings—thousands of lives, tens of billions of hours of productive time not spent behind the wheel, and hundreds of billions of dollars in energy every year—are enormous. When the technology arrives, we need to be ready for it.

DARPA’s Grand Challenge

Driverless cars have been a subject of international interest for more than two decades. During the 1980s and 1990s, several teams in the United States and Europe built and tested partially autonomous vehicle systems, in which a computer did most of the driving and human beings made occasional course corrections. As early as 1986, a German engineer named Ernst Dickmanns built a car that could stay on an empty, curving road. In 1995, Carnegia Mellon completed a "No Hands across America" tour with a car that traveled across the United States without human intervention 98 percent of the time. Unfortunately, the computer chips available in the mid-1990s simply lacked the horsepower for truly autonomous vehicles. There was not enough memory or CPU power to build fully realistic models of the world and to reason about them correctly in real-time.

The current wave of interest in autonomous cars can be traced to the DARPA Grand Challenge, a series of competitions sponsored by the military research organization that also funded the ARPANET, the first packet-switched network. Reacting to a Congressional mandate that a third of military vehicles be unmanned by 2015, DARPA sought to spur the development of autonomous vehicle technology by announcing its first "Grand Challenge," a driverless vehicle race to be held in 2004.

Not a single vehicle completed that first race. Fifteen vehicles participated, but none of them made it more than 8 miles on the 142-mile course. A variety of mechanical and software problems caused most of the machines to fizzle out within the first mile, and the best performer, a Carnegie Mellon robot called Sandstorm, stalled out at a hairpin turn during mile seven.

Undaunted, DARPA announced plans to repeat the race the following year, and the robotics community redoubled its efforts. This time, 23 vehicles qualified for the final race, and no fewer than five vehicles finished the 132-mile course.

The winner of the 2005 race was a newcomer: a Volkswagen Touareg named Stanley. It was built by a team at Stanford that had not participated in the 2004 race. While the 2004 race had fizzled a few miles from the starting gate, the 2005 race was a real nail-biter. Stanley finished the course in under seven hours, just 11 minutes ahead of CMU's Sandstorm. Carnegie Mellon's other entry, H1ghlander, claimed the bronze medal with a time of 7 hours 14 minutes. PBS did an excellent documentary of the event that's available for viewing online.

Taking it to the streets

In 2007, DARPA upped the ante with an Urban Challenge. This time, instead of driving around in the empty desert, vehicles were required to navigate a simulated urban terrain, complete with intersections and other human-driven vehicles. While navigating urban streets is not a major challenge for a human driver, it's a hard AI problem because it requires building a sophisticated model of the environment around the vehicle, recognizing other vehicles and stationary obstacles, and reasoning about the best way to accomplish objectives without breaking any traffic rules.

Junior

Carnegie Mellon finally achieved its long-overdue victory in the Urban Challenge with Boss, a Chevy Tahoe built by CMU and General Motors, which completed the course in the best time. Stanford's entry took the silver, and vehicles from Virginia Tech, MIT, Penn, and Cornell completed the course behind them.

Together, the three competitions demonstrate the tremendous pace of progress in autonomous vehicle technology. In 2004, not a single vehicle could make it more than 10 miles in mostly-empty desert terrain. Three years later, half a dozen vehicles could not only navigate empty desert, but they knew how to obey traffic laws and interact with other drivers. Problems that computer scientists have struggled with for decades were solved in less than five years of intense effort.

Meet the new Boss

Any story of autonomous car technology in the United States has to start at Carnegie Mellon, where computer scientists have been working on the problem of autonomous driving for more than a decade. Not only did CMU vehicles do the best in the 2004 and 2007 Grand Challenge competitions, but the two leading figures on the Stanford Racing Team had previously spent time at CMU. Sebastian Thrun, the director of Stanford's Artificial Intelligence Laboratory, was at CMU from 1995 to 2003. And Mike Montemerlo, the software lead for the Stanford Racing Team, got his PhD at Carnegie Mellon, studying under Thrun.

Boss

Befitting one of the largest computer science programs in the country, Carnegie Mellon's strategy has been to overwhelm the competition with the scale of its efforts. CMU was the only institution to have two different vehicles complete the 2005 Grand Challenge, and its strategy in that competition was massively labor-intensive: as soon as the race officials provided the route details to the team, CMU had dozens of people ready to go over the route with a fine-toothed comb, marking every pothole and hairpin turn and giving its two vehicles detailed instructions about how to handle each segment of the course.

Perception and reality

CMU's 2007 entry, Boss, was similarly ambitious. It had 11 laser range-finders (LIDAR), five radar sensors, two cameras, and a GPS sensor. In the back was a rack of 10 Core 2 Duo servers, each with 2 GB of memory, 4 GB of flash-based storage, and a gigabit Ethernet connection to the others.

Boss's software layers

Boss's software was constructed around a four-layer software model described in this paper and illustrated above. The hardware layer is blue, and the software layers are red. At the bottom are the individual sensors, each of which has a corresponding software module responsible for taking the sensor's raw output and transforming it into a set of object hypotheses, i.e., inferences about the obstacles in that sensor's range of vision. These sensor models also make a first attempt to distinguish stationary objects (such as curbs, traffic cones, and parked cars) from moving vehicles.

The sensor models' hypotheses are then passed to the fusion layer, whose job it is to synthesize these hypotheses into a comprehensive model of Boss's surroundings. The fusion model attempts to infer higher-level features of the objects that the sensor modules have detected, such as each object's shape and orientation. It also draws inferences about objects' speed, based on present and past observations. And the fusion layer also keeps track of objects over time, matching currently-detected objects with previously-detected ones, and deleting objects from its model that haven't been observed for a while.

Decision-making

The result of all this programming effort is a crisp, high-level model of the world that is provided to the higher levels of the software stack. Boss's motion planning software is, itself, divided into two layers: a behavioral layer that sets high-level goals for the vehicle ("drive to that intersection," "turn into that parking space," "execute a U-turn"), and a planning layer that translates these high-level goals into a specific sequence of changes to the steering wheel and pedals.

World Model

The planning module works by generating a list of possible trajectories and then evaluating them based on several criteria, including their efficiency and how close they would take Boss to potentially-dangerous objects, such as other vehicles. The planning layer has two possible modes. In the "on road" navigation mode, the vehicle's goal is to stay as close as possible to the center of the appropriate lane while reaching the desired destination. The other mode, known as "zone" navigation, is used in parking lots and other environments without clear lane markings. In these zones, the planning layer has more options, and it focuses on finding routes that accomplish the goal quickly, while staying as far as possible from potentially dangerous situations.

At the top of the software stack, Boss's behavioral layer takes a destination provided by the human operator (such as GPS coordinates) and divides it into smaller steps that can be executed by the planning layer. Technicians will have pre-loaded high-level map data to assist in navigation, but the behavioral layer still needs to detect unexpected roadblocks and plot new paths to circumvent them. The behavioral system has separate modules for driving in lanes and for negotiating intersections. The latter includes knowledge about proper yielding etiquette, so that Boss will know how to wait its turn before entering an intersection.

Perhaps the most important part of the behavioral layer is the ability to detect and recover from error conditions. The vehicles in 2004 failed largely because their software was too brittle: they froze up when they encountered a situation they didn't understand. The teams learned from that experience, and the 2005 and 2007 vehicles were programmed to keep trying new strategies until they found one that worked.

When the behavioral layer detects an unexpected problem, it switches to recovery mode and begins examining alternative courses of action. Each time a course of action proves infeasible, the behavioral layer increments a variable called the "recovery level." At higher recovery levels, Boss will be willing to incur ever-larger costs (in terms of lost time and increased risk) to escape from the problematic situation. For example, if an obstacle is encountered in the road, Boss might first slow down to wait for the obstacle to get out of the way (it might be a pedestrian). If that fails, it might attempt to navigate around the vehicle (it might be a stalled car). If that proves infeasible, Boss might initiate a U-Turn, and plot a new route that avoids the blocked road.

Junior

Carnegie Mellon's most formidable opponent in both the 2005 and 2007 races was the Stanford Racing Team, led by former CMU professor Sebastian Thrun. As we've mentioned, Thrun's team won the 2005 Grand Challenge, and was looking to defend their title in 2007. Their entry was Junior, a modified Volkswagen Passat station wagon (described in detail in this paper). Junior had 13 sensors—eight laser range-finders, five radar sensors, and a GPS unit. Junior and Boss used many of the same sensors, but Boss had a few more sensors than Junior, including two cameras. Junior's software ran on a pair of quad-core Intel CPUs running Linux.

Junior's trunk

Boss and Junior were also similar in the division of labor among their software modules. Junior's software has a dedicated software module for each of its sensors. These modules feed the data acquired into a perception module that performs a function similar to Boss's fusion layer. Junior's perception module combines the inputs of the various sensors and produces a comprehensive and stable high-level model of the outside world for Junior's motion planning algorithms.

Junior's state graph

The big differences between Boss and Junior can be found at the motion-planning layer of the software. Junior's software was not divided into clear planning and behavior layers. Instead, at the highest level, Junior's navigation layer is a finite state machine (illustrated above), with states for ordinary road driving, waiting at stop signs, crossing intersections, driving in parking lots, and so on.

Within each of these states, Junior employs a planning algorithm based on probabilistic reasoning. Junior's planning software represented its options as a graph of states and transitions between them. Each transition was assigned a cost and a probability of success. The cost was typically the time it would take to complete the transition, but an additional penalty would be added for transitions, such as left turns, that were potentially hazardous.

Like Boss, Junior can recover from unexpected obstacles. If Junior's planning software determines that it is failing to make progress toward its goal, it considers a number of alternatives, including crossing into the opposite lane (after making sure the coast is clear), performing a U-turn, or (if all else fails) abandoning an assigned waypoint and moving on to the next one.

Unsolved problems

CMU narrowly beat Stanford in the 2007 Urban Challenge, but both teams solved what had, until recently, been regarded as an intractable problem: both vehicles were able to avoid obstacles, stay on the road, obey traffic laws, and recover from unexpected situations.

Despite their spectacular successes, representatives from both teams are quick to concede that their vehicles are far from ready to be unleashed on our streets. Jason Ziglar, an engineer who worked on Boss's perception software, told Ars that real streets are significantly more complex and unpredictable than the artificial urban environment that DARPA painstakingly erected for the Urban Challenge.

Pedestrians are the biggest wild card. "Cars can turn, but for the most part, they drive forward. They're all approximately the same shape," Ziglar said. In contrast, "a person can turn literally on a dime and walk in a random direction. People can bend over to tie their shoes. They can be walking arm-in-arm with someone. They're incredibly complicated objects to detect and understand."

Ziglar pointed out that dealing with pedestrians was particularly difficult because of the importance of eye contact in interactions between drivers and pedestrians: "If someone's near the side of the road, you'll make eye contact with them, and you'll see that they recognize you and you recognize them, and that they're not going to leap out in front of you." Robots obviously can't make eye contact, so self-driving vehicles will need to find other ways to deal with pedestrians.

Mike Montemerlo of the Stanford Racing Team told Ars that pedestrians are far from the only type of obstacles that a self-driving car would have to worry about on real streets. There are also bicycles, animals, parked cars (which might pull into the road at any moment), potholes, stalled vehicles, emergency vehicles, and so forth. Navigating successfully around each of these types of obstacles, safely and effectively, requires a lot of knowledge that may be obvious to human drivers but may be difficult to capture programmatically. For example, Stanford researchers are currently working on recognizing and interpreting stop lights, something Junior was not equipped to do.

An urban street

Ziglar said that more work was needed to develop robust road-detection algorithms. The lanes in the Urban Challenge were well-marked, but, as anyone who's driven through a construction zone or on a dirt road can tell you, this isn't always true of real roads.

"You may have ruts in the road, you may have no painted lines, or the lines may be painted wrong, or not be visible; there's a lot of variability in actual roads." Navigational databases can help, but that data isn't always accurate, so a real autonomous vehicle will need the ability to independently verify the accuracy of the data provided to it.

Boss and Junior are also likely to have difficulty with the complexity of high-congestion environments. Montemerlo said that Junior was a very courteous driver, assuming other drivers will follow the rules, and yielding to them when they don't. In real city streets, where human drivers roll through stop signs, speed, cut each other off, and squeeze into tight spaces on the highway, Junior's conservatism could cause it to drive slowly, and perhaps even dangerously.

Montemerlo is optimistic that these challenges can be overcome. He pointed out that at the time the Grand Challenge was announced in 2003, most people overestimated the difficulty of the task, believing that it would require years of work before cars could drive fully autonomously. Yet solutions were devised within two years. "People tend to overestimate the complexity of reasoning that's required." Montemerlo told Ars. "What I'd like to do is continue making things a little more complicated: give Junior a slightly more complicated understanding of the world and see how far that gets us." Fully autonomous vehicles are "definitely a solvable problem," he said.

Autonomy today

Montemerlo thinks that the advent of fully autonomous vehicles is probably more than two decades away. However, he said that "We're going to have to have this period where we introduce autonomy into cars so that cars become a little bit more autonomous every year." Indeed, we're already starting to see that happen, he noted. "Adaptive cruise control is a simple form of autonomy, where the car is taking over the brake for you to adjust your speed and adapt to the speed of the car in front of you on the highway." Many high-end car models offer adaptive cruise control as an option; it's available for around $2000 on the Jaguar XF and the 2009 Mercedes-Benz SL550.

The Infiniti M45X not only offers adaptive cruise control, but it also offers a lane-departure warning system. If the driver begins to drift out of his lane without first turning on his turn signal, the car will produce an audio warning. If the vehicle continues to drift into the adjacent lane, it will automatically engage the brakes on the opposite side, which has the effect of nudging the vehicle back into the lane. The system can be overridden with the steering wheel or by using a turn signal before changing lanes. Similar technology is available on the Audi A8 L W12 and the Volvo S80 T6. The Volvo also includes a collision avoidance system. When the system calculates that it is approaching the car in front of it too fast, it will first display a warning light. If the driver doesn't slow down, the Volvo will take matters into its own hands, slamming on the brakes, and hopefully averting a full-speed collision.

Another smart driving technology is parking assistance. A good example of this is the Lexus LS 600h, which offers both adaptive cruise control and an intelligent parking system. When the driver pulls up alongside a parking space of the appropriate size, a screen displays the parking spot, highlighted with a green rectangle. The driver adjusts this rectangle to the desired location and then tells the car to go. The driver still controls the car's speed with the pedals, but the car controls the steering wheel.

The emergence of self-driving technologies

Of course, none of these technologies come close to a full-fledged self-driving car. But it's easy to see how fully self-driving technologies could emerge from incremental improvements to these technologies. Existing cars already know how to keep speed with cars in front of them and stay in their lanes. It's not much of a leap to imagine cars that allow the driver to get the vehicle on the freeway before going into autonomous mode so that the car can drive itself until it gets close to the desired exit.

Another likely near-term improvement will be more sophisticated collision avoidance systems. Volvo's primitive collision detection system merely applies the brakes in order to avoid vehicles directly ahead, a tactic that will avoid accidents in some situations, but may not help in others. More sophisticated collision avoidance could take over the gas pedal and steering wheel, as well as the brake, if the situation requires it. For example, if a driver unexpectedly swerves in front of the vehicle from the left, a collision-avoidance system might jerk the wheel to the right. A human driver would need to first look over her shoulder to make sure there were no vehicles in that direction, but a software system could react almost instantaneously, because it would already have sensors monitoring that side of the vehicle.

Cars could provide similar safety features at intersections. A vehicle could refuse to move forward if the driver tries to accelerate into the path of an onrushing car. Conversely, a car could engage the gas (and swerve, if necessary) if it detected that a car was approaching from the side at an unsafe speed.

These features would likely be marketed as safety technologies, not "self-driving" technologies, as such. In day-to-day driving, such cars would behave much like the vehicles on the market today. The difference would only become apparent when the car rescues its occupants from what would otherwise have been a serious accident. But the hardware and software for sophisticated collision-avoidance systems would be very similar to what is required for a full-scale self-driving vehicle. In order to predict and avoid crashes, a car would need a detailed model of the world and a robust capacity to reason about it. So, as automakers build ever-more sophisticated collision avoidance systems, they will incidentally be laying the foundation for the self-driving future.