doctoral dissertation, tech. report CMU-RI-TR-11-30, Robotics Institute, Carnegie Mellon University, July, 2011
|For decades, humans have dreamed of making cars that could drive themselves, so that travel would be less taxing, and the roads safer for everyone. Toward this goal, we have made strides in motion planning algorithms for autonomous cars, using a powerful new computing tool, the parallel graphics processing unit (GPU).
We propose a novel ﬁve-dimensional search space formulation that includes both spatial and temporal dimensions, and respects the kinematic and dynamic constraints on a typical automobile. With this formulation, the search space grows linearly with the length of the path, compared to the exponential growth of other methods. We also propose a parallel search algorithm, using the GPU to tackle the curse of dimensionality directly and increase the number of plans that can be evaluated by an order of magnitude compared to a CPU implementation. With this larger capacity, we can evaluate a dense sampling of plans combining lateral swerves and accelerations that represent a range of effective responses to more on-road driving scenarios than have previously been addressed in the literature.
We contribute a cost function that evaluates many aspects of each candidate plan, ranking them all, and allowing the behavior of the vehicle to be ﬁne-tuned by changing the ranking. We show that the cost function can be changed on-line by a behavioral planning layer to express preferred vehicle behavior without the brittleness induced by top-down planning architectures. Our method is particularly effective at generating robust merging behaviors, which have traditionally required a delicate and failure-prone coordination between multiple planning layers. Finally, we demonstrate our proposed planner in a variety of on-road driving scenarios in both simulation and on an autonomous SUV, and make a detailed comparison with prior work.
Autonomous Driving Motion Planning
Number of pages: 233
|Matthew McNaughton, "Parallel Algorithms for Real-time Motion Planning," doctoral dissertation, tech. report CMU-RI-TR-11-30, Robotics Institute, Carnegie Mellon University, July, 2011|
author = "Matthew McNaughton",
title = "Parallel Algorithms for Real-time Motion Planning",
booktitle = "",
school = "Robotics Institute, Carnegie Mellon University",
month = "July",
year = "2011",
address= "Pittsburgh, PA",
|The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.|
Contact Us | Update Instructions