The DARPA Grand Challenge 2005

150 miles
across the Mojave Desert

10 hours

No driver

$2,000,000 prize

(but you knew that)

The DARPA Grand Challenge

The rules

Totally autonomous. No radio communication with vehicle.

DARPA controls remote emergency stop.

Route announced 2 hours before race.

DARPA distributes CD-ROM at 0430 hrs

Start at 0630 hrs.

Route is ~3000 GPS waypoints.

Width of route varies from 10 feet to 1 mile.

Drivable in a 4x4 pickup truck.

The terrain – not quite this hard

2004 Grand Challenge Results

106 entrants filled out DARPA form.

20 at starting line

7 made it out of starting area

3 made it to mile 6

0 made it to mile 8

Why did everyone fail?

CMU had three crashes on the course. They hit a rock, hit a fence, then went off the road.

Lesson: Manual preplanning won't work.

CMU's Sandstorm,

plowing through a fence

Why did everyone fail?

Team DAD got to mile 6 just by following waypoints. Paused so wrecker could pull Sandstorm out of the way, and didn't restart properly.

Lesson: Restart/recovery matters.

Team DAD, unable to restart.

Why did everyone fail?

SciAutonics 2 made it to mile 7 before ending up like this.

Lesson: Serious terrain evaluation necessary

SciAutonics 2, stuck on an embankment

The rest – failed even earlier

Simple hardware failures (several teams)

Confusion involving first waypoint.

Insufficient sleep (Blue Team head forgot to start balance gyro on motorcycle)

Lesson: need extensive field testing

Team Overbot

A Silicon Valley project

All volunteers

Many Stanford alumni, some MIT

Privately funded (about $400K)

Startup space in Redwood City

Currently 6 people.

The Overbot

October 28, 2004

The Overbot

Polaris Ranger 6X6 platform

Base vehicle

Polaris Ranger 6x6.

Most rugged platform available stock.

Easy to fix if damaged.

Top speed 40MPH.

Continuously-variable auto transmission.

2 wheel steer, 4 or 6 wheel drive.

No computers.

Vehicle mods

Modest automotive work required.

Bigger gas tank (40 gal.)

Engine generator (3KW) in back

Stock suspension.

Outsourced to racing shop in Belmont

Vehicle actuators

Transmission

Steering

Throttle

Brake

External sensors – the usual

Scanning laser rangefinder (terrain)

Phased array radar (anti-collision)

Digital camera (road following)

Inertial guidance (attitude, heading)

GPS with corrections (location)

Radar speedometer (odometry, slip)

Sonars (backup, tight spots)

Water detectors (fording)

Internal sensors

Driveshaft speed

Engine RPM

Brake pressure

Encoders on motors

Laser rangefinder

Custom tilt head

Longer-range laser rangefinder

SICK unit has limited range, which limits speed.

We need 1.5x stopping distance

Riegl unit has more range; exploring that option.

True 3D LIDAR may become available in time

Phased-array radar

Radar speedometer

Other hardware

3KW engine generator

Power supplies

Generator control

Vehicle system control (start, 4/6WD, etc.)

Emergency stop system

Computers

...

Rejected sensors

Stereo vision

Dirt doesn't have enough edges for stereo lock.

Submillimeter radar

Technology not here yet, although promising

Flash LIDAR

The right answer. No moving parts.

Not quite here yet

Raytheon, others working on it

We have seen a prototype work

Currently driveable by remote control

Remote control uses a USB steering wheel and pedals, and runs through a computer and WiFi link.

E-stop radio is a safety-rated industrial remote control.

Video of first test

That's the hardware. Now what?

How do we do this?

It really has to work. There's no way to fake it. There's no human handy to handle the problems the system can't. That's why this is worth doing.

Approach #1 – Preplan in detail

Get available high resolution imagery and elevation data

Make plan

Follow plan using GPS.

Available imagery

Off-the-shelf imagery

Resolution high in major US urban areas, low in Mojave Desert.

Elevation data very low res (20m)

Overflight with LIDAR-equipped aircraft

20cm resolution.

$0.50/acre, minimum $5000

Feasible after route leaked

Why preplanning won't work

Available imagery resolution too low.

Need to see anything the vehicle can't roll over.

DARPA did place obstacles on route.

CMU failed that way.

Approach #2 – reactive behaviors

React to sensor data

“MIT approach” (Brooks)

No maps, no models.

Deals well with unstructured environments.

Limits of reactive behaviors

Slow, bumbling movement.

Maxes out at insect-level AI.

Insects work best when viscosity dominates inertia.

Work on purely reactive systems peaked a decade ago.

Approach #3 – game AI

Games have good vehicle control.

Game AIs don't cheat as much as they used to.

Game AI R&D efforts sizable – real applications.

Field-based control

First seen in Reynolds' “boids” (1985)

Attracted to goal (constant)

Repelled by obstacle (1/x, exp)

Improved versions widely used in games

Our architecture

Reactive survival behaviors at the bottom.

Field based map in the middle

“Back seat driver” adds subgoals when stuck.

Low-level – reactive behaviors

Self-protection reactions

Anti-collision, anti-tip, etc.

Has veto power over higher levels.

Mid-level – field map

Does most of the work.

Map centered on vehicle.

Sensors put data into map. GPS/INS data used to scroll map.

Borrowed from game technology

High-level - “backseat driver”

Limited authority, hence the name.

Can change goal direction; can't directly control vehicle.

Classic A* planner.

Used only when field map stuck in local minima.

Map updating

All sensors feed into map.

Map is centered on vehicle.

Map moves with vehicle.

Map is a certainty grid (Moravec)

Rejected approaches

“Learning” (a.k.a. hill-climbing)

Terrain too varied

Poor-performing systems hard to improve.

More vision processing

We have a good road-follower. That's do-able.

General image understanding still doesn't work.

Stanford vision group eliminated in 2003.

Logic-based AI

Hard to map to real world.

Terrain analysis

It's not about “obstacles”. It's about terrain.

Basic terrain analysis

Quickly recogize flat terrain

Quickly recognize impassable terrain

Analyze marginal terrain

Simulation environment

Overbot

Simulator

Summary

We're well along, and it's going well.

No big technological breakthroughs needed.

We need more people.

Joining Team Overbot

Volunteering

No pay, some risk, a fraction of the prize

We cover your expenses.

Free munchies and drinks.

1 or 2 evenings/wk in Redwood City

Interning

We will be hiring about four interns

About $15/hr

Must be available through October 2005

Half time job

What we're looking for

C++ real time programmers

Comfortable with 3D math

Write bulletproof code
(We'll want to see a sample of your code.)

Environment is GCC under QNX, which looks very UNIX-like, but is a true real-time microkernel.

Much work can be done at home using the simulator.

Hardware volunteers

Wiring, mounting, automotive work

Some custom electronics.

Hardware mostly done, but there's still work remaining.

Basic shop skills required.

We send out machine shop and welding work,

Should be available to go to Grand Challenge in October 2005.

Visit Team Overbot

We'll have an open house in November. Or call for a private visit.

We're in Redwood City, in the Redwood Junction Industrial Park

Team Overbot

2682 Middlefield Road, Unit N

Redwood City, CA 94063

American World Domination

Help Build

America's Robot Army

John Nagle

2004-10-26T11:34:20