The Grand Challenge

Schematic of Alice by Simon Roulestone Photo © Alex Stewart

Alex Stewart used some of his Engineering Leadership Award funding to support his academic year at the California Institute of Technology (Caltech). There he became involved in an innovative competition sponsored by the US government. He reports here on his 120 hour working weeks developing a driverless ground vehicle with his fellow students.

Practical autonomous ground vehicles capable of driving through complex, unknown and variable terrain without any human assistance have featured frequently in science fiction but, until recently, not in practice. This is in spite of extensive research into path planning and machine vision. Although the key components required for autonomous ground vehicles exist, the significant engineering challenge remaining is that of integrating them to create a robust and truly autonomous system.

Recognising this, in 2001 the US Congress mandated that a third of all US military ground combat vehicles should be autonomous by 2015. In 2003 they allocated significant funding to the Defense Advanced Research Projects Agency (DARPA) – the research and development arm of the US Department of Defense – to realise this goal. In a pioneering move DARPA created the Grand Challenge (DGC), a competition in which teams must create a completely independent autonomous ground vehicle to traverse an off-road course of up to 175 miles in desert terrain, in less than 10 hours.

The DGC was first run in March 2004. Of the fifteen finalists, only five made it further than a mile and the greatest distance travelled was approximately seven miles.

The course was supplied as a spreadsheet formatted file, called an RDDF. This consisted of a set of sequential Global Positioning System (GPS) waypoints, the width of the corridor either side of a straight line connecting the waypoints that the vehicle must remain within, and the maximum speed limit within the corridor. The corridor width varied from a few metres to tens of metres and the speed limits ranged from 5mph to 40mph. The RDDF was given to the teams two hours before they were due to start. The winning team was the one that completed the course in the shortest time, which had to be less than ten hours. Teams were prohibited from using any government (US or Foreign) funding or government funded technology that was not publicly available.

The event ran again in October 2005, when the course was successfully completed by five teams (one of which was outside of the ten hour time limit). Of these five, all three podium teams were from universities; the winner ‘Stanley’ from Stanford University, and ‘Sandstorm’ and ‘Highlander’, second and third respectively, from Carnegie Mellon University in Pennsylvania.

Team Caltech

I took part in the 2005 DGC as a member of Team Caltech from the California Institute of Technology (Caltech). Unlike nearly all other semi-finalist and finalist teams from universities,Team Caltech is an undergraduate, not graduate driven team. Our team involved over 50 undergraduates throughout the 2004 and 2005 competitions, plus faculty sponsors and leading industrial and academic advisors.

Team Caltech was organised using modern engineering project techniques and tools, and consisted of three ‘race’ sub-teams responsible for different parts of the system: Terrain (creating terrain maps from data gathered by sensors),Vehicle-Embedded (all hardware and actuation) and Planning (designing a path through the terrain map, and determining the required vehicle commands).

Team Caltech was a finalist in the 2004 DGC with ‘Bob’, formerly a Chevrolet Tahoe SUV. Bob travelled 1.3 miles before becoming ensnared in a barbed wire fence that his sensors were unable to detect. Team Caltech returned in 2005 with a new, completely redesigned vehicle named ‘Alice’. ‘Alice’ and ‘Bob’ are conventional ‘placeholder’ terms, referring to common archetypal characters used in explanations in fields such as cryptography. We were too busy to think of another name, so ‘Alice’ stuck! Alice incorporates the lessons learnt from the fate of Bob, and features new research and development in the areas of data-rich sensor fusion, path-planning and high-level system control and fault tolerance.

Introducing Alice

Alice is based on a Ford E350 van. She has been extensively modified by Sportsmobile West for off-road driving, including 4 x 4 transmission and suspension upgrades; the sensor mount and integrated front and rear bumpers were custom made by Aluminess. Alice can be transitioned between streetlegal and autonomous states almost instantaneously and carries ~4kW of electrical power generation capacity on board. Internally she houses a fullyequipped mobile development laboratory connecting to a seven-server cluster including a state-of-the-art quad-core IBM AMD64 based server. All the servers are interconnected by a network management and messaging architecture developed by Team Caltech and supported by a gigabit Ethernet network. In ‘race’ configuration Alice’s average internal network traffic is in excess of 500Mb/s, roughly equivalent to a complete DVD-quality movie every minute.

Alice’s sensor suite consists of two groups. Terrain sensors are used by Alice to gather information about her surroundings, State sensors enable Alice to determine the evolution of her globally-referenced location, roll, pitch and yaw. This information is referred to as her state-estimate. The terrain sensors include LADARs, stereovision, and monocular vision, the latter is used in conjunction with selected LADAR data for road-detection. LADARs are optical radars, also known as LIDARs, used here as range-finders in which mirrors are used to sweep a laser beam back and forth across a fixed plane relative to Alice’s frame. The reflections of the laser from objects within the environment are then used to determine the terrain within the planar slice. The stereovision systems use pairs of video cameras to perform depth-perception by analysing differences between the two images, in much the same way that human eyes do.

Inside Alice's mind

Alice fuses the data from the terrain sensors and the state-estimate to create a series of 200m x 200m map layers representing the terrain in front of her. Each layer is centred on Alice’s current position, consists of 40cm square grid-cells, and represents her surrounding terrain as perceived by different sensors or combinations of sensors. The final map used by the path-planning software (the planner) assigns a speed to each cell. This is the fastest speed at which the cell can be driven through safely considering the elevation and gradient of the terrain within the cell and its surroundings.

The planner uses a simplified vehicle model to calculate the fastest feasible plan possible through the terrain ahead given the speed limits in the map, acceleration/deceleration, steering and vehicle roll-over constraints. Typically 5 –10 new plans, each of which are 30m long, are created each second and sent to the path-follower module. This uses the current state-estimate and plan to compute vehicle (steering and throttlebrake) commands to make Alice follow the plan as closely as possible. Each plan is defined by a set of sequential points which detail the spatial, velocity and acceleration components of the desired route. The vehicle commands are processed and transferred to embedded microcontrollers that control the actuators or, in the case of the throttle and ignition interface, directly to the standard engine management computer.

Two types of nothing

An example of the issues we encountered occurs as a result of the inability to distinguish between cells which Alice tried to see but couldn’t, for example cells in the ‘shadow’ of an obstacle, and cells which Alice has not yet tried to see, but are within her field of view. In both cases the elevation map produced by each sensor contains no data for the cell in question. This would be a particularly hazardous problem for the LADARs if Alice were looking over a cliff edge; either insufficient signals would be returned for range calculations, or only the top of the cliff and the terrain some distance away from the base of the cliff (below Alice) would be seen, leaving a large swathe of no-data between the two measurements. Whilst interpolation based on the values of neighbouring cells is used to produce a reasonable estimate for small patches of nodata, these methods are ineffective for large areas. They could lead to a vertical cliff being interpreted as a negative slope that might appear to be drivable. Since patches of nodata frequently appear when cresting hills or small rises it is undesirable for them to appear as intraversable, but of course driving over a cliff edge should also not appear preferable to avoiding a rut in the road! In the end our design is a compromise. Nodata is assigned a slow speed of 2m/s (~5mph), and is regarded as more significant by the planner the closer it is to Alice’s current position. This is because longer range sensors are generally more susceptible to no-data caused by obstacles blocking the view of a cell and reduced reflections.

Supervisory control

Alice’s system as described thus far assumes that she is operating in nominal (ie normal – no faults) conditions. The Supervisory Control module (SuperCon) is responsible for detecting and responding to any systemlevel faults which might occur. These are situations in which although all the individual components of the system are operating correctly (ie as detailed in their specifications) the system as a whole is unable to achieve its stated goals.

The principal group of faults are those which prevent Alice from driving forwards along the course and include unseen obstacles blocking her path (eg barbed wire) and seen obstacles which appear to completely block the corridor. SuperCon uses system-level feedback loops, rulesbased filtering, and a state-machine to determine what action to take in these situations. It also has command interfaces to other modules, including exclusive control of higher-level functionality, eg reversing, to resolve any issues detected.

Alice’s performance

Alice successfully drove autonomously for hundreds of miles off-road in the desert in the weeks leading up to the DGC, and gave a very strong performance at the DGC semifinal, earning her one of ten pre-selection places in the final race.

Unfortunately Alice’s race ended prematurely after approximately nine miles, when she left the course. The cause was a combination of a LADAR hardware failure which, despite trying, Alice was unable to rectify, and a freak error within the stateestimator fuelled by very inaccurate GPS signals; this led Alice to believe that she was still within the course when she was in fact driving outside of it.

Despite the 120+ hours per week of work maintained over months that was required to create Alice, it was without doubt one of the greatest experiences of my life to date. I have learnt an immeasurable amount and have had the privilege of working with an incredibly talented and driven team of friends. Alice was an amazing success and demonstrates just what can be achieved through determination; Seymour Cray was on to something when he said that he “liked to hire inexperienced engineers right out of school, because they do not know what's supposed to be impossible.”

What next?

Ultimately the final barrier to the widespread adoption of autonomous vehicles will be psychological, not technological. Convincing the general public that they are safer and better served by autonomous systems is a vitally important challenge that cannot be neglected by the engineering community if we are to successfully exploit this technology. Although the current DGC will not be re-run, DARPA have solicited teams for a future autonomous ground vehicle competition within urban environments for 2006/07.

I believe that open competitions like the DGC, which further the development and promotion of new technologies, are critical if we are to win the hearts and minds of the public. It is also important to note that the DGC received worldwide publicity, captured the interest and imagination of students of all ages and spurred new collaborations between universities and industry. This is to say nothing of the huge technological advances resulting from the challenge, all of which were achieved for the comparatively small cost to the US government of hosting the event. The estimated benefits from the DGC amount to billions of dollars, so it is little wonder that DARPA have been said to regard it as one of their most successful and cost-effective projects. I hope that in the future the UK adopts the model on which the DGC is based and hosts significant challenges of similar scale – I do not believe it coincidental that no challenges of this type exist anywhere in the world outside of the US, currently the world leader in autonomous technology.

Further reference

More information about Alice and the team including detailed technical reports, pictures and movies of Alice in action, are available from the team website http://team.caltech.edu The team also has a podcast, ‘Caltech: TecherTrax – DARPA: Team Caltech’, available free for download from the iTunes Music Store, which follows our experiences during the DGC.

Biography

Alex Stewart Alex Stewart is in the final year of his Electrical Engineering degree at UCL, where he is currently working within the Optical Networks Group. He spent 2004/05 on exchange at the California Institute of Technology (Caltech) throughout which he was an active member of Team Caltech – he developed the Supervisory Control module and also worked on the Path-Following module. He is an Engineering Leadership Award (ELA) recipient, and spent his gap year and a subsequent summer working for Accenture, a leading technology consultancy firm who have sponsored him throughout his degree. He is hoping to pursue a PhD in system-level control for autonomous systems.