Heard at Hot Chips: Driving cars that drive themselves

The Monday keynote at Hot Chips this year was in the very capable hands of Sebastain Thrun, Stanford University professor of computer science and electrical engineering, director of the Artificial Intelligence Lab, and not coincidentally, leader of the Stanford teams in the DARPA Challenges. He described the control system architecture that has enabled three generations of autonomous vehicles to complete these events, winning first place in the Grand Challenge and second place in the Urban Challenge.

Thrun’s story started with a series of failures. The original idea for the Grand Challenge, Thrun said, came from a US Defense Department frustrated that enormous sums of R/D money invested in the traditional military contractor network had failed to produce a useful autonomous vehicle. The contest, the DoD hoped, would generate some new ideas. It did that, but the first event in 2004 did not produce successful ideas: no vehicle completed more than 5 percent of the course.

Thrun’s analysis of the failures indicated that most of the vehicles abandoned a perfectly serviceable road at some point in the course, subsequently getting into trouble from which they could not extract themselves. Accordingly, Thrun focused his team’s work on sensors and algorithms that could identify the best path along the course, not misled by phantom obstacles.

This turned out to be a challenge in its own right, Thrun said. Initially, Stanford’s vehicle sensed the road with a combination of GPS, an inertial motion sensor bank, and an optical sensor. The optical system included a laser beam deflected by a rotating mirror. The beam scanned the ground in a series of concentric circles, detecting the presence and range of objects by time-domain reflectometry. Software integrated the reflected-signal data into a moving map of the terrain ahead of and beside the vehicle.

As it turned out, this system had two fatal flaws. First, if the vehicle pitched or rolled by too small an amount–or at too high a rate–for the inertial sensor to track, the laser would scan an area different from the one the computers thought it was scanning. This would result in phantom objects, as the software assigned the wrong azimuth and angle to correctly-ranged data—creating, for example, a purely imaginary obstruction across the road. The solution to this problem was to use probabilistic techniques to reduce the data: a Markov model that would assign a probability to each object identified by the laser system. By changing the algorithm to only respond to objects that had a high probability of being real, the team was able to reduce false positives from 12.5 percent of objects to 0.02 percent.

Second, the range of the laser system was 25 meters. That was only adequate for very low speeds. The team concluded that a visual system with longer range—at least 50 meters–would have to augment the laser rangefinder. So they added a camera and image-processing software. But the image processing turned out to be more difficult that anticipated. "We found that not only was the problem of general object recognition essentially unsolved, but we couldn’t find anything off the shelf that could reliably identify a road in the desert," Thrun said. So the team undertook that task.

The first effort, Thrun said, was to try something simple: identify the road by color. Unfortunately, in on the Challenge course there were paved roads and dirt roads, and varying colors of off-road terrain. Color failed. Next, a more clever approach: define the road as the area of the visual field with the smallest change in color between pixels. Unfortunately, Thrun reported, the area with the most uniform color turned out to be the sky.

Finally the team settled on an adaptive approach. They used the laser system to locate a portion of the road immediately in front of the vehicle. Then they used that area to continuously train an object-recognition algorithm to identify the road further out—for example, by identifying what color and texture to search for. This algorithm that fused the laser and camera data proved quite successful at locating the road under a variety of changing conditions.

Then there was the matter of speed. Like a road rally, the Challenge specified a maximum speed for each segment of the course, and the winner was the fastest car under the assigned speeds. So simply crawling along the course was not an option. Nor was excessive speed, which turned out to be just as dangerous for robots as for teenaged human drivers. In the end, the team developed an algorithm that fused path information, road conditions, and z-axis acceleration, and then trained the algorithm using human drivers. Thrun, who admits to having a somewhat German approach to driving speed, eventually lost patience with his students and drove the test course himself to train the algorithm. This set of sensors and algorithms drove the Volkswagen Tuareg that won the Grand Challenge.

For the Urban Challenge, Thrun said, the major differences were, first, that the team had a great deal more money, and lavished a portion of it on a 64-beam laser sensor system that produces about a megasample per second of data. The new system was so sensitive that, after software reduction algorithms, it could resolve a two-inch curb along the side of the road. Second, since the Urban Challenge involved interacting with moving vehicles, considerable work went into software to categorize and track the objects that the existing algorithms had merely identified and avoided.

An interesting additional problem in this Challenge involved interpreting lawful behavior. Under a literal reading of California traffic law—as many frustrated California drivers will happily attest–there are deadlocks: everyday situations in which all the vehicles become stuck, and no one can legally move. So the vehicle program had to include what one might call judicious rule-breaking to avoid deadlocks in traffic situations. Debate over this algorithm reached the point, Thrun said, of calls to California Highway Patrol officials to ask for interpretations of the law. The police dutifully explained that in some situations, any reasonable person would carefully ignore the law.

Thrun’s team finished a commendable second in the Urban Challenge, essentially proving the concept that autonomous vehicles can operate in populated urban environments without behaving like battle tanks in someone else’s city. But Thrun said there is still a long ways to go in fulfilling the promise of the technology.

Interestingly enough, according to Thrun, the critical paths in autonomous vehicle design do not involve computing power. The Stanford vehicle uses only about half the cycles on a pair of quad-core CPUs—essentially, a pair of high-end laptop computers in the trunk. "The problem is finding the algorithms, not finding the compute power," Thrun said. "The real world happens at a very low rate—you have time for the computing."