Sebastian Thrun (Stanford Professor) – Towards Self-Driving Cars, ICAPS (Sep 2009)

Chapters

Abstract

The Evolution and Impact of Autonomous Vehicles: A Journey from DARPA Challenges to Modern Day

Abstract:

This article delves into the revolutionary development of autonomous vehicles, tracing their evolution from the DARPA Grand Challenge to modern-day advancements. We investigate the technical milestones, challenges, and societal impacts of self-driving cars, presenting a comprehensive understanding of this transformative technology.

—

Introduction: The DARPA Grand Challenge and its Legacy

The DARPA Grand Challenge, launched in 2004, marked a pivotal moment in automotive history. It aimed to foster the development of self-driving cars, and the million-dollar prize competition attracted over 100 teams. Stanford University, led by Sebastian Thrun and Mike Montemello, emerged as formidable contenders. Despite initial setbacks, including the disastrous first race where no team could complete more than 5% of the course, the challenge set the stage for groundbreaking innovations in vehicle sensors, obstacle detection, and planning algorithms.

Overview of Autonomous Vehicle Competitions and Stanford’s Entry:

The first DARPA Grand Challenge in 2004 saw no team able to complete the course. Professor Sebastian Thrun of Stanford University, inspired by the competition, entered a class of students who worked on the project for course credit instead of pay. Stanford secured a car donation from Volkswagen, a computer system from Intel, and the students built a drive-by-wire system to enable proprioception and environmental perception. Sensors, including GPS, inertial measurements, lasers, and cameras, were strategically installed on the vehicle to facilitate these functions.

Stanford’s Journey: From Concept to Victory

Stanford’s entry into the competition, with limited resources, showcased ingenuity and collaboration. The team, armed with the donated Volkswagen car, Intel’s computer system, and the dedicated efforts of students enrolled in CS 294, developed “Stanley,” a robotic vehicle equipped with advanced sensors for proprioception and environmental perception. This innovative approach included GPS, inertial measurements, and a fusion of lasers and cameras for precise navigation.

Technical Breakthroughs: Obstacle Detection and Planning

The team’s obstacle detection strategy, utilizing a SICK laser range finder, proved pivotal in navigating challenging terrains like the Mojave Desert. Their planning approach, which included reactive steering adjustments and a straightforward controller for aligning with the trajectory, played a critical role in Stanley’s victory in the 2005 DARPA Grand Challenge.

Early Self-Driving Cars: Reactive Planning, Simple Controls, and Basic Perception:

Instead of formal planning, the vehicle responded to obstacles by generating potential steering adjustments, checking for collisions and proximity to the desired path, and selecting the most suitable option. A rudimentary controller adjusted the front wheels to follow a reference trajectory or steered in proportion to cross-track error to rectify deviations. Experiments took place in the Mojave Desert, with varying terrain ranging from smooth to rutted and sandy. Laser sensors detected obstacles, generating data visualized as colored displays, where white represented drivable areas, red indicated non-drivable areas, and gray signified unknown areas. GPS data was used to define a corridor, but its accuracy was limited. To enhance visibility beyond the limited range of laser sensors, a camera was mounted on the vehicle, and a computer vision algorithm was developed to identify the road ahead.

Stanley: The Autonomous Car that Won the DARPA Grand Challenge:

Stanley encountered several challenges, including finding drivable terrain, controlling a motorcycle, and navigating the race course. The pre-qualification event near Los Angeles highlighted the challenge’s complexity, with many competitors struggling. During the race, Stanley started second, followed by its chase vehicle, and overtook Carnegie Mellon’s paused vehicle by utilizing video footage to navigate the only man-made obstacle. Stanley’s victory was significant as it showcased the immense potential of autonomous vehicles.

DARPA Grand Challenge Victory:

Stanley, a robot vehicle, successfully completed the DARPA Grand Challenge, becoming the first robot to accomplish a challenge of such magnitude. The team celebrated their triumph, while Carnegie Mellon, who came in second place, did not. The victory was initially attributed to a fortunate incident rather than superior planning.

From Desert to Urban: Escalating Challenges

Following their desert triumph, DARPA escalated the challenge to urban driving, necessitating more intricate route planning and navigation. Junior, Stanford’s subsequent entry, boasted advanced sensors and algorithms for dynamic programming, tactical driving planning, and freestyle maneuvers. This transition underscored the escalating complexity and potential of autonomous driving technology.

Planning for Urban Driving:

DARPA issued a new challenge focused on urban driving, which posed greater planning complexities than desert driving. The goal was to create a system capable of autonomously planning routes, handling unexpected obstacles, and navigating through traffic.

Sensor Technology:

The vehicle, Junior, was equipped with a scanning laser sensor, Juno, which provided 64 scan lines at 10 hertz. The sensor facilitated obstacle detection, including curbs, using machine learning technology. Moreover, it enabled localization with an accuracy of approximately five centimeters, allowing for precise driving in lanes. The system could track other cars using particle filters, displaying them on a screen alongside camera images.

Path Smoothing and Voronoi Field for Autonomous Navigation:

Path smoothing is a post-processing step that enhances the smoothness of a trajectory, resulting in a locally optimized path. It rectifies topological paths without finding different topological paths. This process is efficient, typically taking only five milliseconds.

A modification was made to rescale the obstacle repellent force based on the proximity to the nearest clearing space. A Voronoi decomposition of the data is used to measure the clearance for any given point. The clearance is determined by finding the nearest Voronoi line and measuring the distance to the nearest obstacle. The obstacle repellent force in the potential field is rescaled according to the clearance, making the cost of navigating through a narrow opening equivalent to the cost of going through a wide opening.

The Voronoi field is incorporated into the path smoothing process to effectively repel the vehicle from obstacles. This approach is particularly useful when dealing with openings of varying widths, ensuring that the vehicle can traverse narrow openings as efficiently as wide openings. The Voronoi field modification offers a minor improvement to the extensive literature on potential field navigation. It enables efficient and effective obstacle avoidance in autonomous navigation, particularly in scenarios with openings of varying widths.

Sebastian Thrun’s Presentation on Autonomous Vehicle Planning:

The planning algorithm employed by Stanford’s autonomous car in the DARPA Grand Challenge was remarkably fast, taking no more than 0.2 seconds for replanning. The algorithm leveraged heuristics and smoothing techniques, effortlessly incorporating backups. Smoothing itself took approximately 10 milliseconds, while A-star replanning in the 3D space required no more than 200 milliseconds. The planning algorithm only activated when the most promising trajectory could not be further smoothed.

In a staged demonstration, the car successfully reversed into a tight parking spot, showcasing the precision required for such maneuvers. It adeptly navigated a parking lot filled with traffic cones, demonstrating its ability to handle intricate environments.

Sebastian Thrun’s Perspective on the Future of Transportation:

Sebastian Thrun draws parallels between the current inefficiencies of transportation systems and the inefficiencies of broadcast and print media before the internet. He underscores the lack of innovation in the automotive industry, with car usage remaining largely unchanged over the past 50 years.

Thrun emphasizes the paramount importance of autonomous cars in providing independence and enhancing the quality of life for individuals who cannot drive due to disabilities or age-related factors. He also highlights the potential for energy efficiency, with road traffic consuming a substantial amount of energy, a significant portion of which is wasted. Driving closely together, akin to a train, can enhance energy efficiency by reducing wind drag, potentially increasing highway capacity and alleviating traffic congestion.

Cars are often parked for extended periods, resulting in wasted natural resources and real estate. Self-driving cars could potentially increase car usage and reduce the number of vehicles needed, freeing up parking spaces and possibly eliminating the need for individual car ownership.

A Call for Collaboration and Innovation

The journey of autonomous vehicles from the DARPA challenges to their impending commercial success underscores the need for sustained innovation, collaboration, and adaptation. While significant progress has been made, the road ahead demands a concerted effort from all stakeholders to fully realize the transformative potential of self-driving cars.

—

Additional Insights from Sebastian Thrun’s Presentation:

Benefits of Autonomous Vehicles:

– Increased safety: Reduced accidents and fatalities.

– Cost savings: Cars and car-based transportation are the second largest expense for American households.

– Convenience: Passengers can focus on other activities while the car drives.

– Efficiency: Vehicles can travel faster and more efficiently.

– Sharing: Cars can be shared among multiple users, reducing the number of vehicles on the road.

Challenges in Developing Autonomous Vehicles:

– Lack of funding: The US automotive industry is struggling and there is little funding available for autonomous vehicle research.

– Technical challenges: Developing the necessary computer science and engineering solutions to enable autonomous vehicles is a complex task.

Call to Action:

– Encourages collaboration and innovation to advance the development of autonomous vehicles.

– Highlights the potential impact of autonomous vehicles on society, including increased safety, cost savings, convenience, efficiency, and environmental sustainability.

Car-to-Car and Car-to-Environment Communication:

– Acknowledges ongoing work in this area but chooses not to emphasize it due to the chicken-and-egg problem.

– Believes that focusing on developing the core technology of autonomous vehicles is more important at this stage.

Co-evolution of Environment and Cars:

– Thrun believes that autonomous vehicles (AVs) should adapt to existing infrastructure rather than waiting for major changes, just as early cars did on horse trails.

Computational Complexity of Global Traffic Optimization:

– Thrun acknowledges the computational challenges of optimizing traffic on a global scale, requiring more advanced scheduling and planning algorithms.

Safety and Reliability Concerns:

– He emphasizes the need for proper engineering methodology to guarantee safety and reliability, including extensive error analysis and component testing.

Cost-effectiveness and Marketability:

– Thrun mentions the high cost of current AV systems and the importance of cost reduction to make them marketable.

Liability and Insurance:

– Liability currently lies with the operators of AVs, but he believes that insurance companies will eventually benefit from reduced costs due to fewer accidents.

Energy Efficiency:

– Thrun suggests that AVs could become more energy-efficient by forming closely linked trains on highways, exploiting wind drag, and using special HOV lanes.

Government Interest:

– He notes that the Obama administration has expressed interest in pursuing AV technology if it becomes available.

Challenges and Time Constraints:

– Thrun acknowledges that there are many unanswered questions and challenges related to AVs, and his answers may evolve over time.

Notes by: BraveBaryon