Autonomy

By the time Thrun’s parents bought him a used NorthStar Horizon personal computer, the young man was able to program simple video games. He wrote a virtual simulation of the Rubik’s Cube. Another feat involved coding the member database for his family’s tennis club. One gets a sense that Thrun roved through his adolescence seeking out challenging problems that he would use to test his programming ability. The same method would predominate in Thrun’s academic and professional life. He enrolled in the computer science department at the University of Bonn. Artificial intelligence attracted him because, in comparison to humans, with their sometimes irrational, inscrutable behavior, Thrun felt he could fully grasp the reasons a software program acted the way it did.

In 1990, the University of Bonn bought a Japanese robotic arm as a research tool. Thrun distinguished himself by using a neural network to teach the robot how to catch a rolling ball. The resultant academic paper was accepted to an American artificial intelligence conference, Neural Information Processing Systems. The trip was a turning point for Thrun, who was then twenty-two. He’d discovered people exactly like him—a whole community of “psychologists and statisticians and computer scientists all working together to understand how to make machines learn.” From that moment on Thrun focused on writing academic papers so he could attend more AI conferences. Through such gatherings, Carnegie Mellon AI legend Alex Waibel became a mentor, as did Thrun’s future thesis adviser, Tom Mitchell. Thrun joined the CMU faculty after he earned his PhD in computer science and statistics from the University of Bonn in 1995.

One of the most interesting projects Thrun worked on in Pittsburgh was the creation of a robot tour guide for museums. In keeping with the kitsch factor the public associated with robots—think the 1986 comedy Short Circuit, the TV show Knight Rider and Data, the well-meaning android on Star Trek: The Next Generation—the tour guide that Thrun constructed, Minerva, included a pair of camera lenses for eyes and a red mouth that could tilt into a frown to indicate displeasure. As a publicity stunt to demonstrate the capabilities of technology, Minerva even provided tours to visitors of Washington’s Smithsonian Museum.

It turned out programming a robot to navigate through a museum was a surprisingly complex challenge. Minerva would share the museum floor with dozens of human tourists—as well as valuable museum exhibits. How to engineer the creature so that it didn’t bump into an exhibit? How to write the code so that it didn’t roll over a child?

Six years before DARPA staged its first Grand Challenge, in 1998, Thrun equipped Minerva with laser-range finders. Then he loaded the robot with a machine-learning algorithm and sent it out on the museum floor at night, without any tourists around. Minerva wandered around the exhibits, sending out laser beams and creating a map of its environment. Then, when the museum was open, with humans sharing the same floor as the robot, Minerva would use this map to locate itself. The map also provided a way for Minerva to avoid running into humans. The robot would assume any new obstacle that hadn’t been on the original map was a human, causing Minerva to stop safely.

The tour guide was a big hit, and Thrun used the acclaim to handle the software side of other projects. For example, Whittaker convinced Thrun to join the team that built the Groundhog robot that aimed to make it safer for Appalachian coal miners to retrieve their underground ore. Maps didn’t exist for older, decommissioned mines in the area, which could cause problems. In 2002, for example, nine workers toiling in Pennsylvania’s Quecreek mine were trapped by water when they breached an adjacent passageway that had been abandoned for years and flooded sometime along the way. The miners escaped after three days, but Whittaker took the accident as a challenge and, in just two months, with Thrun working on the SLAM programming, created a robot that could be dropped into old mines to scan the passageways and create 3-D maps for reference.

DARPA’s series of challenges fascinated Thrun. When Thrun was eighteen, in 1986, his best friend, Harald, was invited for a ride in another friend’s new Audi Quattro. It was an icy day, and the driver was going too fast and ran the Quattro headfirst into a truck. Harald died instantly. The impact was so strong that his seat belt was shredded. The crash would forever haunt the German robotics professor.

Thrun saw self-driving cars as a way to make automobile transportation safer, to avoid crashes like the one that killed his friend. He did some thinking about the problem after the first Grand Challenge. The fact that DARPA created waypoints along the route really simplified the problem, he figured. Programming Minerva to navigate the fast-changing and crowded environment of the Smithsonian Museum rivaled the complexity of the self-driving-car problem. Before he left Carnegie Mellon, he went to Red Whittaker with an offer. “Look,” Thrun told the older robotics legend. “I’ve been recruited from Stanford, but for the next Grand Challenge, I would love to help you.”

“Had he said yes,” Thrun recalls, “I would have happily served on his team and never have started my own team.”

But Whittaker declined Thrun’s offer, presumably because he wanted to keep Red Team exclusive to people associated with Carnegie Mellon. After Montemerlo’s presentation, Thrun considered whether to enter the second challenge himself. Red Team had taken a year to build a robot that went 7.3 miles. If Thrun’s new lab could do better, they’d go a long way toward establishing a national reputation. SLAM would be integral to a successful performance, and Thrun and Montemerlo were two of the world’s leading experts on the topic. Thrun basically figured, why not?

So on August 14, when DARPA staged a conference for potential competitors, Thrun brought Montemerlo and several other members of his team. The conference was held in Anaheim, California. Despite the negative media coverage of the first race, even more competitors came out this time around: more than 500 people from 42 states and 7 different countries attended the 2004 competitors’ conference. Ultimately, 195 teams would register to compete, nearly double the number that signed up for the first race.

Including, of course, the Red Team. The summer after the debacle in the desert, Urmson went off and completed his PhD, then got a job working for Science Applications International Corporation, the government contractor that had sponsored Sandstorm. Urmson’s assignment was to work with Red Whittaker and Red Team on the second DARPA race. Urmson’s hopes were considerably higher for the second challenge. They’d have another eighteen months to perfect Sandstorm’s development. And they’d be doing so with a more professional group, including several engineers from Caterpillar, the construction-equipment manufacturer. The budget was bigger, at $3 million. The atmosphere was different, too. The first time out there was youthful enthusiasm. This time, there was an almost grim determination.

“I signed up to win the Grand Challenge,” Whittaker proclaimed. “This time around, the Red Team will be more like a Red Army.”

It was inevitable that the Stanford and Carnegie Mellon teams would bump into each other at the preliminary conference. Urmson noticed that Montemerlo was carrying a sheaf of papers in his hand that turned out to be the technical paper Urmson had written after the first race. The paper described the most intimate details of Red Team’s approach. Publishing for the rest of the robotics community the secrets of all competitors’ approaches had been one of DARPA’s conditions of entry. It was a good strategy. In the spirit of academia, sharing intelligence meant the whole field progressed faster. But it also made things more difficult for Whittaker and Urmson. As the country’s leading robotics lab they’d had a head start for the first race. Publishing their approach brought everyone else closer to the Red Team’s level. And the defectors, Montemerlo and Thrun, were brilliant people. That they were entering meant the prize was no longer Carnegie Mellon’s to take. Now, heading into the second challenge, Red Team faced its most serious competition yet.

Early on in its preparations, Red Team decided to hedge its bets by entering two robots. (There was a precedent for this. SciAutonics had entered two vehicles in the first race.) Partially, the step was designed to smooth relations between team software lead Kevin Peterson and project manager Chris Urmson, who were apt to butt heads in the latter half of Sandstorm’s development. There was talk of giving each deputy his own vehicle, although years later Whittaker would insist that Peterson and Urmson contributed to both robots in the lead-up to the second race. And partially, the move was pragmatic. After all, thanks to AM General’s donation, Red Team had enough Humvees.

The second vehicle, which became known as H1ghlander, was a 1999 model year, making it thirteen years younger than Sandstorm. The AM General–donated vehicle came with a 6.5-liter turbocharged engine. One of the challenges of autonomous driving involved controlling acceleration and steering. Most vehicles of the era were mechanically controlled. They relied on a human being twisting steering wheels, pushing accelerators, shifting gears, which complicated matters when a computer was supposed to do the driving. There was a margin of error when a digitally controlled actuator pressed against, say, a gas pedal.

This new Humvee, H1ghlander, featured drive-by-wire capability embedded in its controls. It had been designed to be controlled by a computer. The throttle, for example, was operated by a factory-installed engine control module. So instead of rigging up an electric motor and lever to actually push against the gas pedal, as with Sandstorm, the H1ghlander crew could hack into the newer Humvee’s computer system and control the throttle electronically. It all meant less margin of error, which made H1ghlander a better driver.

Another change was that Whittaker and his students had tracked down a different, more accurate location-tracking system. The system used in the first race had a margin of error of about a yard. This new one, from a sponsor named Applanix, featured a margin of error of about twenty-five centimeters, or less than a foot—a big improvement for the second race.

So the Red Team had a lot going for it. But so, too, did Thrun’s team. In his heart, Whittaker was a hardware guy, who came from an era when making robots work involved the precise interplay between actuators and carburetors, electric motors and solar-powered chargers. This was reflected in Red Team’s approach to the first challenge, which saw his charges spending as much time perfecting the e-box and gimbal mechanisms as writing code for the computers. But as computing power improved, robotics was increasingly becoming a software problem, which computer scientists, rather than mechanical engineers, had to solve. Whittaker was an engineer. Thrun’s team was dominated by computer scientists. Very little of the hardware that Stanford used needed to be custom-designed. In contrast to Sandstorm’s gimbal and e-box, which the Carnegie Mellon team had engineered itself, Thrun simply took sensors he found in the marketplace and bolted them to his team’s vehicle, including five LIDAR units, a color camera to aid road detection and two radar sensors designed to identify large obstacles at long distances. The philosophy of the Stanford team was to “treat autonomous navigation as a software problem.”

“My perspective was, you take a human out of a car, and replace it with a robot—there’s a bit of a hardware issue,” Thrun observes. “You have to figure out how to crank the steering wheel and press the brake. But that part is trivial. You put a little motor on the steering wheel. There’s no science … It’s all about artificial intelligence. About making the right decision. So we had this complete focus on making the system smart.”

“Carnegie Mellon was a team—it’s a humongous place, and they have experts in everything,” Montemerlo explains. “We were a much smaller group. We very much were software people. None of us had any mechanical skill whatsoever.”

That said, Thrun had learned a lot from his experiences working for Whittaker. In September of 2004, fresh off the heels of Montemerlo’s presentation, Thrun used Whittaker’s template to begin work on his own entry in the second DARPA Grand Challenge. Just as Whittaker did, Thrun recruited volunteers by asking them to enroll in a university class. Thrun’s was called “Projects in Artificial Intelligence.” At the first meeting of maybe forty students Thrun gave a Red Whittaker–style inspirational speech. “Look, there’s no syllabus, no course outline, no lectures,” Thrun recalls saying. “All we’re going to do is build a robot. A robot car that can drive on the original course.”

Thinking of the way Whittaker motivated his students to work hard by providing them with challenges, Thrun set his class a clear and well-defined objective: By the end of the two-month-long session, they were to have built a car that could travel a single mile of the first DARPA Grand Challenge course. “Red and I have very different personalities,” Thrun says. “But I tried to learn from him. And what I learned from Red was, when you give students a goal, no matter how hard it is, because they haven’t learned that these goals are hard to reach, these students think they can reach it. And eventually, they do reach the goal.”

The class didn’t have a budget to go out and buy a car. Someone contacted Ford to ask the manufacturer to donate one, and the company said yes, but they wanted it back afterward, in the same condition they lent it out. Perhaps thinking of Urmson’s rollover accident, Thrun declined the Ford offer. Luckily, a friend of his named Joseph O’Sullivan, an AI researcher who worked for Google, played soccer with a guy, Cedric Dupont, who worked as an engineer at Volkswagen’s lab in Palo Alto. Dupont arranged to provide Thrun’s team with a 2004 Touareg R5 TDI, as well as the help of VW engineers to access its computer system. “That was like a gift from God,” Thrun says. Like H1ghlander, the Touareg had a drive-by-wire interface, and with VW’s help, Thrun’s team could hack into the computer system relatively easily.

Thrun ended up with about twenty people committed to joining the Stanford team, which he split into smaller units. One group was charged with configuring hardware—actually attaching the sensors to the Toureg, which, in a nod to their school, they gave the nickname Stanley. Another part of the team was in charge of providing the mapping. A third handled navigation.

Two months later, at the end of the term, Thrun took his students out to the Mojave Desert and set up Stanley on the course of the first Grand Challenge. Then they activated the robot and watched: Stanley drove past the class’s one-mile goal, thrilling Thrun, who became even more excited when Stanley passed 7.3 miles, which was how far Carnegie Mellon’s Sandstorm had made it. Some minutes later, at 8.4 miles, Stanley found itself stuck in a deep rut, caused by heavy rain.

Thrun was beside himself. The sort of rut that had stymied his robot would have been smoothed over by DARPA prior to the race. Had this been an official race day, it’s possible Stanley would have proceeded much farther. “That was just unbelievable,” Thrun recalls. “That was the moment it became clear to me, boy, there’s a real possibility it can be done.” If a team of comparative novices could surpass the best Carnegie Mellon team in just two months, Thrun wondered, then what could the same team do in the year leading up to the second race?

Red Team’s strategy this time around amounted to a bigger and better version of the approach they’d intended to execute in the first race.

Truth be told, they felt a little cheated by the way the first race went. The communication out of DARPA had led the team to believe that the robots would have to navigate rough territory and brutal off-road conditions. DARPA’s actual route turned out to have some hairy spots, such as tunnels and narrow fence gates. But there was nothing arduous about the road itself. That had been a smoothly graded desert thoroughfare. Your typical subcompact import could have driven off a car lot and navigated it. Looking back, Red Team had wasted countless hours ensuring their robot would be able to handle off-road conditions. And not just handle them—handle them fast. That’s why they’d used shocks and springs to suspend the electronics box and the gimbal, to ensure the computer equipment would be able to withstand the resulting jars and vibrations. Had Red Team forgotten about testing the robot in the most difficult of conditions, and just concentrated on developing a vehicle that would be able to roll from one GPS waypoint to another, then many team members figured they would have ended up finishing the first race. They could have won.

So this time, Whittaker concentrated on refining the capabilities Red Team had already developed, including the pre-driving approach that it had used in the first challenge. In August 2005, Whittaker moved both Sandstorm and H1ghlander out to Nevada. The robotics engineer figured the federal agency would amp up the difficulty for the second race. Some of the toughest roads in the nation were the M1 Abrams tank courses at the Nevada Automotive Test Center. So that’s where Red Team landed with just three months to go, to put the robots, and the team, through a series of what were in effect dress rehearsals designed to replicate race-day conditions—right down to special costumes worn by DARPA staff stand-ins.

Red Team tended to use two different routes to test its vehicles. One, known as the “Pork Chop,” was a 48-kilometer loop that featured everything from dirt road and pavement to cattle guards, high-voltage power lines and railroad crossings. The Hooten Wells route was an 85-kilometer one-way line that followed the course of the Pony Express and featured a dry lake bed, gravel road and a narrow canyon.

The testing featured its share of disasters. Spiker had a credit card linked to a Carnegie Mellon account and was authorized to spend $100,000 a month, a figure he regularly blew past procuring the spare parts required to repair Sandstorm and H1ghlander after the damage caused on their testing runs. For example, on August 26, just twelve days after they arrived in Nevada, H1ghlander sheered off its front right wheel as it navigated a particularly treacherous off-road trail. On September 15, Sandstorm was clotheslined by a tree, sustaining significant, but nevertheless repairable, damage.

These setbacks aside, the testing was going well.

For the first time, Sandstorm and H1ghlander were completing challenge-length runs that featured some of the toughest terrain the team could throw at the robots. The vehicles drove more than 1,600 kilometers each. Better yet, they were completing these runs in times that would have them finishing the race in under seven hours. Red Team was feeling very good about its chances.

Even so, Whittaker was working his team as hard as he ever had. The 4:00 A.M. wake-ups were taking their toll. The race rehearsals started at 6:30 A.M., just like they would during the actual event, and then, after the course work, the team would take the robots back to their garages, where the coders and the mechanics would work long into the night to make improvements and repairs. The next day, they’d rise at four and do it all over again. It was a grueling routine. “Everyone was scraped raw by exhaustion,” Whittaker recalled.

To refresh everyone, to ensure his team was sharp and fully rested come race day, Red set a week’s vacation before the national qualifying event, which began September 28, 2005, at the California Speedway. There, forty-three teams would be evaluated by DARPA, competing to become one of twenty-three finalists to qualify for the actual race on October 8, 2005.

The final day of testing was September 19. Whittaker’s culminating goal had Sandstorm and H1ghlander navigating 10 laps of a 30-mile-long course, to accumulate 300 miles in total, about double what the robots would have to do on race day. Once they achieved the distance, the team would freeze the software, store the robots and disperse to their own chosen habitats for the pre-race rest.

By the afternoon of the nineteenth, Sandstorm was ready for the race but for a last-minute tire and oil change. Meanwhile, H1ghlander was nearing the final laps of its last test session. Following behind in AM General’s second donated Humvee was Peterson in the passenger seat and software engineer Jason Ziglar behind the wheel. Ziglar was doing his darnedest to keep up with H1ghlander, whipping the steering wheel this way and that, his foot jammed on the accelerator. With H1ghlander about to start its final lap, having already gone 270 miles, Peterson called Red in Pittsburgh, where he was handling some last-minute details. “The vehicle is driving really well,” Peterson told him. “But we’re really beating up on it.” What if something happened? Peterson recommended to Red that they call off the final lap. “It felt like we’d learned everything we were going to learn,” Peterson recalls.

Giving up before the team had completed a goal wasn’t in Whittaker’s DNA. He made the call—finish the route. So they kept going. Moments later, H1ghlander was kicking up its usual dust cloud. From the passenger seat in the chase vehicle, Peterson couldn’t see the robot, but thanks to his laptop’s Wi-Fi connection, he could see what H1ghlander could see on the monitor. Approaching a leftward curve, the robot slowed down, the way its algorithms specified, and then accelerated into the curve. Except it swayed just a little bit to the right, off the path—and Peterson’s whole display went red. When the dust cleared, Peterson saw a dirt formation on the right side of the road that looked like the sort of thing a stunt driver would use to shoot a car up into a two-wheeled drive. In this case, the stunt jump had sent H1ghlander over on its side, and ultimately, onto its roof. The robot had caught the right wheels on the ramp at 30 mph and launched itself into the air.

Another rollover.

Having been through this before, the team leapt into action. No one broke down in tears over this one—Spiker was prepared. Many of the extra parts required to repair H1ghlander lay in the mechanics shed at the Nevada Automotive Test Center base. The rest, Spiker arranged to have shipped from Pittsburgh to Nevada.

And that week’s worth of vacation everybody was supposed to go on the next day? Gone. Instead it turned into the biggest work session the Red Team had ever faced.

Once Stanford’s AI class conducted its 8.4-mile test run, Thrun winnowed his team down to four key people. Thrun himself and Carnegie Mellon alum Mike Montemerlo were the first two. Among those who had taken his robot class, Thrun discovered a fellow German, a computer-vision expert and programming whiz named Hendrik Dahlkamp. The fourth was a grad student named David Stavens.

A quartet was appropriate to the task because that’s how many occupants the Touareg comfortably fit. For a week at a time, Thrun and the other three would head out into the Mojave Desert and drive the trails. At first, they’d set the vehicle on a trail, watch it navigate itself, and eventually the robot would encounter something it couldn’t handle. Then someone would code a fix. As the process repeated itself dozens, and eventually hundreds, of times, the robot became sophisticated enough that it began to teach itself. In this phase, Thrun would drive Stanley through the desert, manning the controls, slowing down when the road became rough or steep, accelerating on smooth straightaways. After several days of this, Thrun would go back to the university, and Stanley, working overnight, would retroactively look at the data to engage in its own learning. Confronted with this terrain, Stanley would think, Sebastian chose to drive here—and I will do the same. “The robot would basically spend the night sorting through the data and bring order from chaos,” Thrun said.