in the "Secret Sauce"
Winning Strategies at the DARPA Grand Challenge
by Mark Helmlinger
coverage of the race:
National Qualifying Event in Fontana, California by Mark Sedenquist
2005 DARPA Grand Challenge in Primm, Nevada by Mark Sedenquist
Race Reminiscences by Megan Edwards
What did it take to win the toughest robot race of all time? Practice, practice, practice! The five finishers of the DARPA Grand Challenge all put major development miles on their bots. Stories of desert escapades involving chase vehicles were common in the pits. The single factoid that indicated a winner might have been how many chase vehicles a team had ruined. In fact, the member of the Carnegie-Mellon team responsible for renting cars was black-listed by the car rental company!
The winning strategy was to allow for sufficient development time. The winning outfit, Stanford, had several identical plug-and-play vehicles, each with its own team intent on a specific approach. These parallel development activities were then merged into Stanley and further tested, integrated, and tweaked. Instead of running only one of their development vehicles, the Red teams entered both. Even the tow-crane that Team TerraMax was asked by DARPA to bring with them (evidently DARPA has not upgraded their AAA roadside assistance plan to include military transports) had cameras and other sensors on it. The Gray team was the exception in this regard, but they did log many desert miles.
IT'S ALL IN THE "SECRET SAUCE"
DARPA Director Tony Tether said it at the first press conference at the National Qualifying Event: the software is the Secret Sauce. Five teams were able to cook up sensor packages and control routines that had just the right ingredients of finesse, caution, and accuracy to guide their bots to the finish line. To shine some highbeams on what worked and what didn't, let's back up a bit
Robots follow simple sequential instructions (code) that in aggregate (algorithms) can manifest in apparently sophisticated behavior. The Grand Challenge bots typically were controlled by algorithms made of tens of thousands of lines of code, each typed in via keyboard by hand. That's lots of beef jerky and Mountain Dew (preferred fuel of programmers everywhere).
The overall function of these control algorithms can be described as Sense, Decide, and Act, repeated ad infinitum. The faster this fundamental loop executes, the faster the bot can go, and the more computation can be devoted to the Decide part (the real secret of the Secret Sauce). Let's take a look at each step:
Most bots had similar sensing packages, all with common elements. What was seen at the Grand Challenge was an example of parallel evolution converging on a single solution. Engineering tradeoffs are the heart of any development effort, cost vs. effectiveness. In this case, the cost was primarily measured by the amount of computational time needed to interpret sensor inputs.
The race course was defined by GPS coordinates.
Differential GPS is much more accurate than plain GPS - it's
accurate to about four inches. Other navigations inputs allowed
independent knowledge of location, direction, and attitude.
Those inputs are sufficient to drive the Grand Challenge course
blind, and do not represent a heavy computational challenge,
but that is not a winning strategy in a changing world.
LADAR sensors (think of radars that use infrared lasers instead of radio beams) were conspicuously mounted on nearly every entry. LADARS provide a computer-ready list of distances and directions to reflective surfaces in the field of regard. These pointilistic inputs are quickly transformed into a digital "map" of the surrounding terrain with a moderate computational hit, depending on the number of points per scan. There's an example of a tradeoff right there - how small of an object that can be mapped versus how quickly the map can be made.
Some LADAR systems scanned, just like a bar code reader at the grocery store. (Those big silver balls on top of H1ghlander and Sandstorm are LADAR systems.) Others relied on the motion of the vehicle to build up 3-D knowledge of surroundings. (Cajunbot did this, bouncing and jouncing all over the place!) The limitation of LADARs is distance, and that can limit the bot's speed. However, LADAR was the most common sensor by far. Many vehicles had a handful mounted on them, pointed every-which-way.
Radar sensors have more distance but much less resolution than LADARS. Their radio beams bounce off of metal and objects with water in them much better than dry brush. However, the measurement is very fast. Sonar can only tell you how far from a large object you are -- kind of like a glorified curb-feeler. Its range is limited, but a few teams had them.
Video comes in two kinds, mono color and stereo. Stereo uses parallax between two cameras to determine distances. Some bots, like TerraMax, have cameras at different baseline separations that optimize depth of field. Video in general requires the most processing of all sensors to interpret, and this is why many bots carried more computational power than a small country.
October 16, 2005