It wasn’t a perfectly brief moment like the Wright Brothers’ takeoff at Kitty Hawk, when the autonomous vehicle dubbed “Stanley” arrived back at Buffalo Bill’s Hotel in Primm, Nevadait was seven hours in the making. Nevertheless, Stanley, a modified Volkswagen Touareg, made history when it completed the 2005 DARPA Grand Challenge in a winning time of 6 hours, 53 minutes. The Challenge, a desert race for fully-autonomous vehicles with a $2 million prize, had never been won before. But last October 8, a team of 30 Stanford University engineering faculty and students just stood by and watched while their creation navigated 132 miles of desert and found its own way across the finish line.
What a difference a year makes
DARPA, the Defense Advanced Research Projects Agency, is the central research and development agency for the Department of Defense. Because of a congressional mandate to accelerate the development of autonomous military vehicles, DARPA sponsored its first Challenge in 2004, hoping to spur new breakthroughs in autonomous vehicle technology. The first race, begun in Barstow, CA, yielded no such breakthroughs. After three hours, 11 of the 15 entrants had broken down. The best performance was 7.36 miles, less than 5% of the 150-mile course. Every car failed within sight of the starting line.
When the 2005 Challenge was announced, it was clear there was much work to do. The Stanford team recognized that most of last year’s problems had been software failures, but they had limits as to how well they could address them due to the complexity of Stanley’s systems. Stanley is based on a stock, diesel-powered Touareg R5, with added skid plates and a reinforced front bumper, and operates on a drive-by-wire system developed by Volkswagen of America’s Electronic Research Lab. The car is equipped with five forward-facing laser range finders, a radar system for long-range “sight,” a pair of stereo cameras, and a monocular vision system. These are complemented by Global Positioning System (GPS) measurements, a 6-degree-of-freedom inertial measurement unit, LIDAR (laser radar) measurements, and wheel speed measurementall taken between 10 and 100 times a second.
Even more complex than Stanley’s hardware arrangement, though, is the software needed to connect it all and process the sensor input using seven onboard Pentium M computers. There are six custom software modules for acquiring and interpreting data and three artificial intelligence (AI) modules charged with processing this information to understand the road ahead. The three AI modules consist of a data acquisition module, which arranges incoming data; a planning module, which charts a path based on data passed to it; and a “world model,” which incorporates real-world driving physics. Stanley’s software contains approximately 100,000 lines of code written by the team, and when incorporating all the external libraries used, the number of lines climbs into the millions.
Alex Aiken, a theoretical computer science professor at Stanford and advisor to the Stanley team, contacted me for Coverity’s help in identifying problems in their C and C++ source code. Coverity is a source code analysis company whose developers use advanced techniques to debug software in ways that traditional testing and human inspection cannot.
After running the Stanley source code through our Analysis Engine, which identified 68 defects in the software that could cause poor performance, and, in other cases, crash the system. Out of the bugs we found, though, the Stanford team chose only to fix eight resource leaks and three potential crash conditions, which underscores a common problem in the development of any piece of complex software: a shortage of resources. Fixing bugs is often extremely time-consuming, and when a team is working under deadline, the more convoluted bugs and those located in external libraries can’t always be addressed; there’s simply not enough time to read through and understand that much code. Fixing the bugs without a proper understanding of their context is even more dangerous and can make things worse.
The problem of too little time is not specific to Stanley, nor is it specific to software development. However, writing code for a system like Stanley’s presents unique challenges. The first is that Stanley integrates a variety of hardware and software systems, so the team’s engineers were forced to learn new application programming interfaces (APIs) and spend much of their effort on system integration. Harmonizing across different systems, especially when they come from different sources, is a particularly difficult task. “There are bizarre combinations of events that can lead to system failure. They seem impossible, but when you bring together that many parts, a coincidence like that becomes a very real possibility,” said Mike Montemerlo, the software lead for the project. The ability to prevent such an occurrence over the course of seven hours, let alone seven years, of use requires tremendously robust engineering.
As DARPA Grand Challenge Deputy Program Manager Tom Strat pointed out in 2004, “Some of the vehicles were able to follow the GPS waypoints very accurately; but were not able to sense obstacles ahead ... Other vehicles were very good at sensing obstacles, but had difficulty following waypoints or were scared of their own shadow, ‘hallucinating’ obstacles when they weren't there.” In other words, it’s not necessarily daunting to get a car like Stanley to do a given task well, the problem lies in engineering proper cooperation between modules, of which there are many.
There is no way to truly validate third-party software without reading the code, so there is always a risk of unpredictable behavior when it is expected to interact with other components. Even Stanley’s bottom-layer, a “blackboard system” that handles messaging between modules, is an off-the-shelf library. If there is unanticipated behavior at that level, the system can be paralyzed.