Parallel Algorithms for Real-time Motion Planning

Matthew McNaughton
doctoral dissertation, tech. report CMU-RI-TR-11-30, Robotics Institute, Carnegie Mellon University, July, 2011

  • Adobe portable document format (pdf) (4MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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 five-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 fine-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.

Associated Project(s): Autonomous Driving Motion Planning
Number of pages: 233

Text Reference
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

BibTeX Reference
   author = "Matthew McNaughton",
   title = "Parallel Algorithms for Real-time Motion Planning",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "July",
   year = "2011",
   number= "CMU-RI-TR-11-30",
   address= "Pittsburgh, PA",