Prospect Eleven: Princeton University’s Autonomous Vehicle Entry 2005 DARPA Grand Challenge : Prospect Eleven: Princeton University’s Autonomous Vehicle Entry 2005 DARPA Grand Challenge Thursday, February 6, 2006
National Physical Laboratory
Teddignton, Middlesex, UK Alain L. Kornhauser
Team Leader, Prospect Eleven
Professor, Operations Research & Financial Engineering
Princeton University
Co-founder & Board Chair, ALK Technologies, Inc. Applications of Knowing “Where am I” Two Examples: CoPilot|MinETA Real-Time Dynamic Minimum ETA Sat/Nav
Prospect Eleven: The Making, Testing and Running of Princeton’s Entry in the 2005 DARPA Grand Challenge : Prospect Eleven: The Making, Testing and Running of Princeton’s Entry in the 2005 DARPA Grand Challenge Alain L. Kornhauser
Team Leader, Prospect Eleven
Professor, Operations Research & Financial Engineering
The DARPA Grand Challenge Defense Advanced Research Projects Administration : The DARPA Grand Challenge Defense Advanced Research Projects Administration DARPA Grand Challenge Created in response to a US Congressional and DoD mandate, it was a field test intended to accelerate research and development in autonomous ground vehicles that will help save lives on the battlefield. The Grand Challenge brought together individuals and organizations from industry, the R&D community, government, the armed services, academia, students, backyard inventors, and automotive enthusiasts in the pursuit of a technological challenge.
The First Grand Challenge: Across the Mojave, March 2004 From Barstow, California to Primm, Nevada offered a $1 million prize. From the qualifying round at the California Speedway, 15 finalists emerged to attempt the Grand Challenge. However, the prize went unclaimed as no vehicles were able to complete the difficult desert route.
The 2005 Grand Challenge October 8, 2005 in the desert near Primm. Prize increased to $2 million.
18 -month Life Cycle of Prospect Eleven : 18 -month Life Cycle of Prospect Eleven
Prospect Eleven & Competition : Prospect Eleven & Competition
Slide7 : http://www.pcmag.com/slideshow_viewer/0,1205,l=&s=1489&a=161569&po=2,00.asp Homemade
“Unlike the fancy “drive by wire” system employed by Stanford and VW, Princeton’s students built
a homemade set of gears to drive their pickup. I could see from the
electronics textbook they were using that they were learning as they went.”
Teamwork : Teamwork Real-time Decision System
Andrew Saxe’08 Object Detection System
Brendan Collins’08 Mechanical Systems
Gordon Franken’08 Planning Systems
Josh Herbach’08 Electronic Systems
Bryan Cattle’07 Computing Systems
Anand Atreya’07 Control Systems
Scott Schiffres’06 Organizational Systems
Rachel Blair’06 Team Leader
Alain Kornhauser*71P03
Mechanics : Mechanics Design and Fabrication of:
Vehicle Actuators
Steering
Brakes
Transmission
Sensor Housings
Stereo Camera
GPS Antennae
System Protection
Shock-absorbing computers
Secure installation of components
Vehicle Actuators : Vehicle Actuators Steering
Motor from Bosch cordless drill.
Modified gears mounted directly to steering wheel.
Rotary encoder used for position feedback.
Brakes
Bicycle brake cable used to depress pedal.
Motor-driven linear actuator.
Load-cell used for tension feedback.
Also: pneumatic e-brake, for fail-safe operation.
Transmission
Ability to shift from forward to reverse.
Not used due to several issues:
Slow actuation
Difficulty interfacing with vehicle transmission
Not open up an Achilles heel. Drill motor Steel Gears Rotary Encoder bike cable brake pedal motor Load cell
Sensor Housings : Sensor Housings Stereo Camera
Camera rated for “indoor office use only” !!!
Water & air tight enclosure
Mounts for photographic filters
System Protection : System Protection Shock Absorption for computers.
Old way: Computers were wrapped in foam.
New way: Computers are rack-mounted on shock-isolating feet.
Secure installation of other components.
Batteries, wires, power supplies, air compressor…
The “shake test” Shock-absorbing feet
Stereo Vision System : Stereo Vision System Principle of Operation: Difference between two cameras gives depth information
Steps:
Compute disparity image
Find obstacles in each column
Approximate with rectangles
Filter in time domain
Challenges : Challenges Quantization
Noise
Lighting condition
Field of view
Occlusion
Range
The left camera sees: : The left camera sees: Point Grey Bumblebee
Focal Length: 4mm
Resolution: 640x480
Black & White
The right camera sees: : The right camera sees: Point Grey Bumblebee
Focal Length: 4mm
Resolution: 640x480
Black & White
Yielding a disparity map: : Yielding a disparity map: Intensity indicates distance: the lighter, the closer
White indicates an invalidated location.
Processing in each column: : Processing in each column: Intensity indicates confidence that an obstacle exists at that location. A darker line indicates a higher confidence.
Bounding with rectangles: : Bounding with rectangles: Darker rectangles indicate higher confidence.
Data Representation : Data Representation Reference:
http://www.darpa.mil/grandchallenge/TechPapers/Stanford.pdf vs.
Tracking : Tracking
Navigation : Navigation Blind-Man’s Cane Approach:
Find best instantaneous velocity vector (heading and speed) within visible cone ahead.
Step 1: Tube Projection : Step 1: Tube Projection
Slide24 : Gap Identification
Examples of “Shoot the Gap” : Examples of “Shoot the Gap”
Interfacing to Existing Vehicle Data : Interfacing to Existing Vehicle Data Existing electronic information available on ’05 GMC Canyon:
Engine status – temp, RPM, diagnostic codes,...
Transmission – what gear are we in? 4WD on/off
Car traction control – are wheels slipping,
are we really moving?
Wheel speed/odometry – how far have we moved? how fast?
Throttle is electronic
All monitored & used by Prospect Eleven
Other thoughts : Other thoughts
Feedback Control Systems : Feedback Control Systems Speed Control Module:
Receives desired speed from Navigation
Decides how to modulate throttle and brake
Requirements
Gracefully reach and maintain desired speed
Smooth acceleration and braking
To minimize skidding on loose sand wet grass
Strict adherence to speed limit
Minimize overshoot
Steering Control Module
Receives desired heading angle and speed from Navigation
Converts to desired steering wheel angle
Constrains wheel angle as function of speed to avoid roll-over.
Control Coefficients tuned to trade off response and overshoot
Speed Control -- Implementation : Speed Control -- Implementation Proportional Integral Control
Output = KPev + ∫KIevdt + KD (dev∕dt)
Where evelocity = Vdesired – Vcurrent
KP term deals with the bulk of error
KI integrates up error to eliminate steady state error
KD reduces overshoot and ringing by slowing response
Speed Control Desired Speed Current Speed
Latest Speeds Percent Throttle Percent Brake Tension
Why P11 stopped after 9.4 miles : Why P11 stopped after 9.4 miles We store a list all obstacles we are currently concerned about
Each time a new obstacle is received, we add it to this list
Each obstacle needs to have its relative position updated each time we get new vehicle position information
It gets these updates by subscribing to the RelativeFrameUpdated event
When we have passed an obstacle by more than twenty feet, we remove it from the list
However, we were not unsubscribing the obstacle from the RelativeFrameUpdated event
Thus, nine miles down the road, our computer was still processing a bush it saw near the beginning of the course!
C# is a powerful language, but it has to be used carefully
Slide33 : DAPRPA Grand Challenge Event, October 07, 2005 The Day Before
2005 Grand Challenge Event
Slide34 : L2R: Rachel Blair’06, Dan Chiou’05, Prof. Alain Kornhauser*71 P03, Ben Essenburg’05, Bryan Cattle’07, Josh Herbach’08. Jeff Jones*05,
Kamil Chihoudy’06, Scott Schiffres’06, Anand Atreya’07; Launch Team: Andrew Saxe’08, Brendan Collins’08, Gordon Franken’08 DAPRPA Grand Challenge Event, October 08, 2005 The DARPA Grand Challenge Event Team 2005 Grand Challenge Event
Slide35 : DAPRPA Grand Challenge Event, October 08, 2005 The Launch of Prospect Eleven
2005 Grand Challenge Event
Slide36 : DAPRPA Grand Challenge Event, October 08, 2005 Return of Prospect Eleven @ 8 Mile Mark
2005 Grand Challenge Event
Slide37 : DAPRPA Grand Challenge, Unfinished Business, October 31, 2005 Approaching Beer Bottle Pass 19:02
2005 Grand Challenge Course
Slide38 : DAPRPA Grand Challenge, Unfinished Business, October 31, 2005 Beer Bottle Pass 19:10 PST
2005 Grand Challenge Course
Slide39 : DAPRPA Grand Challenge, Unfinished Business, November 1, 2005 The Assent: 17:00
Rerun to Beer Bottle Pass
Slide40 : DAPRPA Grand Challenge, Unfinished Business, November 1, 2005 The Assent: 17:01
Rerun to Beer Bottle Pass
Slide41 : DAPRPA Grand Challenge, Unfinished Business, November 2, 2005 12:25
2004 Grand Challenge Course
Slide42 : DAPRPA Grand Challenge, Unfinished Business, November 2, 2005 14:26
2004 Grand Challenge Course
Slide43 : DAPRPA Grand Challenge, Unfinished Business, November 2, 2005 The Finish 18:44
2004 Grand Challenge Course L2R: Prof. Alain Kornhauser*71 P03, Andrew Saxe’08, Bryan Cattle’07, Scott Schiffres’06
Prospect Eleven’s Unfinished Business October 31-November 2, 2005 DARPA Grand Challenge ’04 & ’05 Courses : Prospect Eleven’s Unfinished Business October 31-November 2, 2005 DARPA Grand Challenge ’04 & ’05 Courses GPS Tracks and Timing Maps DAPRPA Grand Challenge, Unfinished Business, October 31, 2005 Finish, ’05 Course
Slide45 : Start 7:53:30 PST
Finish 19:35:49
Elapsed Time 11:43:49
Pause Time ~2:55:49
Autonomous Time 8:48:59 8:44:48
1:10 Pause 10:48:04
3:45 Open & pass thru gate 9:52:53
8:14 Open gate & pass through 13:18:53
1:10 Pause 18:20:53
38:50 prepare inside video 19:00:21 – 0:56 Adjust Camera
19:02:53 – 1:52 Wait for chase car 10:37:37
5:54 Open & pass thru gate 18:02:50
2:08 Pause 11:15:15
5:14 Pause at ranch, go thru gate 11:29:52
42:00 Pull chase car out of mud 13:16:05
1:32 Rejoin course 10:53:33
2:15 Pause 14:16:03
2:23 remove rubble blocking I-15 underpass 12:42:35
4:40 Pause 12:33:51
1:19 Pause 15:13:31
1:30 Wait for traffic to clear on NV 161 16:03:07
1:53 Pause 16:07:48
4:32 to take pictures 16:12:50
11:44 negotiate bulldozed area 16:31:17
2:12 Survey another bulldozed area 8:20:55
5:20 Pictures at Primm return 8:31:42
8:53 Take down fence & pass through GPS Tracks & Timing of Prospect Eleven’s
Autonomous run of the 05 GC Course 10/31/05
Slide46 : Red: 8:00 Outbound 10/31
Deviation to avoid “lake” Yellow: 16:30 Return 10/31
Deviation to avoid “lake” Blue: 8:00 Outbound 11/2
Lake dried sufficiently,
no deviation required. GPS Tracks & Timing of Prospect Eleven
Diverting Around Not-so-dry Lake
05 GC Course 10/31/05
Slide47 : DAPRPA Grand Challenge, Unfinished Business, November 1, 2005 Return to Beer Bottle Pass GPS Tracks of return to
Beer Bottle Pass 11/01/05
Slide48 : DAPRPA Grand Challenge, Unfinished Business, November 1, 2005 Return to Beer Bottle Pass
2005 Grand Challenge Course, 1.9 miles Start Down: 17:10:17 End Up: 17:04:48
Duration: 0:10:21 Start Up: 16:54:27 End Down: 17:18:04
Duration: 0:7:47 GPS Tracks & Timing of Prospect Eleven’s
Autonomous run up then back down
Beer Bottle Pass 11/02/05
Slide49 : 7:28:33
4:35 negotiate bulldozed area 7:55:26
33:08 Divert to get gas for P11 8:39:13
11:50 take pictures 8:34:01
4:30 take pictures 10:13:43
2:10 cross road 9:42:26
1:50 take pictures 10:04:59
2:07 take pictures 10:28:11
3:20 take pictures 7:08:36
Start ’04 GC Course GPS Tracks & Timing of Prospect Eleven’s
Autonomous run of the 04 GC Course 11/02/05 DAPRPA Grand Challenge, Unfinished Business, November 2, 2005
Slide50 : 14:50:xx
4:00 Avoid Washout in 4 spots 15:10:10
2:04 Inspect burial monument 12:05:25
0:30 Xing CA 127 12:08:00
2:00 take pictures 13:08:54
1:05:56 Fix steering encoder 12:38:03
2:17 take pictures 12:19:37
1:50 take pictures 10:57:13
6:30 take pictures 12:53:36
0:54 Pause 14:33:15
2:45 take pictures 14:44:13
2:47 take pictures GPS Tracks & Timing of Prospect Eleven’s
Autonomous run of the 04 GC Course 11/02/05 DAPRPA Grand Challenge, Unfinished Business, November 2, 2005
Slide51 : 17:16:33
15:28 Replace Front Left Blowout 16:12:07
0:50 Xing road 15:19:00
4:32 take pictures 15:46:03
2:07 take pictures 15:38:01
1:37 take pictures 16:33:15
2:45 Letting traffic pass on Randall Drive 16:35:14
1:00 Xing Yermo Road 17:32:27
4:00 Inspecting Silt Filled underpasses < 4 ft. clearance 18:41:26
1:10 Pause let cars pass on Stoddar Valley Rd GPS Tracks & Timing of Prospect Eleven’s
Autonomous run of the 04 GC Course 11/02/05 18:18 Top 18:35 Bottom Daggett Pass Start 7:08:36
Finish 18:44:19 – Arrival at gate of Slash X Cafe
Elapsed Time 11:37:43
Pause Time ~03:28:00
Autonomous Time 08:09:00 File photo File photo File photo Finish, ’04 Course
Accomplishments: : Accomplishments: Invited to National Qualifying Event
Seeded 10th for Grand Challenge
Accomplished 10 miles of Autonomous Driving in GC
“Completed” the 2005 & 2004 Courses during Fall Break
Lessons Learned : Lessons Learned It is non-trivial to “Just Do It”
You must respect Uncertainty (and plan for it)
Harmonize Accuracy
Time is your Friend
(only know what you need to know when you need to know it)
More is not necessarily Better
Always assume your code has bugs
Stereo Vision Does Work!
Three (3) Regimes of Autonomous Control
Under “7” mph
Between 7- 25 mph
Above 25 mph
Slide55 : Operational Processes used by
Capital District Advanced Traveler Information System (CD-ATIS) CoPilot|MinETA: Real-Time Dynamic Minimum ETA Sat/Nav by
Alain L. Kornhauser
Co-founder & Board Chair, ALK technologies, Inc.
Slide56 : PROBLEM: How to get from A to B
Many Paths
Each with a Different Value to the Decision Maker
Each Segment Changing with Uncertainty over Time Things Change!!
Slide57 : Link Travel Times
Historic, Actual & Forecast During Day One week-day on one link
Things change!
Real-Time Dynamic Minimum ETA Sat/Nav : Real-Time Dynamic Minimum ETA Sat/Nav 250 Volunteers using CoPilot|Live commuting to/from RPI
CoPilot continuously shares real-time probe-based traffic data
CoPilot continuously seeks a minimum ETA route Conducted its version of the abandoned “ADVANCE” (Advanced Driver and Vehicle Advisory Navigation ConcEpt )project
Link
Project Objectives : Project Objectives Create: real-time data collection from vehicles and dissemination to vehicles of congestion avoidance information which is used to automatically reroute drivers onto the fastest paths to their destinations
Target locations: small to medium-sized urban areas
Aspects: operations, observability, controllability, users, information transfer to travelers
Experiment Details : 3-month field test
Capital District (Albany), NY, USA
Journey-to-work
200 participants
80 Tech Park employees
120 HVCC staff & students
“Techy” travelers
Network:
Freeways & signalized arterials
Congested links
Path choices exist
Experiment Details
Basic Operational Architecture : Basic Operational Architecture Two-way cellular data communications between
The In-Vehicle “Device” : The In-Vehicle “Device”
Every Second : Every Second CoPilot|Live Determines “Where am I”,
Then… Set i=j
Every “n” Minutes : Every “n” Minutes
ALK Server …
Send… New TT(mi, mj ) for every (i,j) in Uk
(280 bytes/100arcs)
CoPilot|Live …
Updates TT(mi, mj ) in Uk , ETA on current route, Finds new MinETA route, if MinETA “substantially” better then… Adopt new route ALK Server …
Determines Uk : set of TT(mi, mj ) within “bounding polygon” of (Location;Destination)k that have changed more than “y%” since last update.
When Available : When Available ALK Server …
Receives: Other congestion information from various source, blends them in TT(mi, mj )
What We Heard : What We Heard I find it interesting how willing I am to listen to a machine tell me which route to take I like using it for when I have no idea on how to get somewhere, and it is good for my normal route because it keeps me out of traffic on route 4. It is great, it took a while to trust it telling me where to go, but i like it because i cant get lost! Thanks. This thing is awesome. I was a little skeptical at first but once i got the hang of it I don’t know how I went along without it. I think any student commuting to school will benefit from this. I'm very impressed with the CoPilot program thus far. The directions are accurate and it adapts quickly to route changes.
also Can Watch Vehicles : 1 2 3 also Can Watch Vehicles
North American Monument Network : North American Monument Network ~125,000 North American “Monuments”
~106 (mi, mj)
1st Commercial application in PC*Miler v19
(contains Median Travel Time by Time-of-Day for all NA)
Slide70 : Thank you
Alain L. Kornhauser
alaink@alk.com
www.alk.eu.com
www.princeton.edu/~alaink/