Event Location: Hillman Center 6501

Abstract: Real-time motion planning in complex dynamic environments requires new algorithms that exploit parallel computation. Robots that can move autonomously in complex and dynamic environments are desired for many purposes, such as efficient autonomous passenger vehicles, robots for industrial, agricultural, and military applications, etc. As an example, automating passenger vehicles would reduce traffic congestion and increase fuel efficiency while improving safety and revolutionizing the driving experience. Motion planning algorithms that can quickly plot a safe and efficient course through complex and dynamic environments require considerable computing resources. Future increases in computer performance will be realized by increasing parallelism, using processor architectures such as contemporary graphics processing units (GPUs), with multiple processor cores and SIMD instruction sets. This thesis will investigate parallel algorithms for motion planning, with a focus on algorithms relevant for autonomous ground vehicles. The work will involve both parallelizations of algorithms already used in motion planning, as well as development of new algorithms and motion planning approaches that are specifically designed to exploit the forms of parallelism offered by modern multi-core platforms.

In this proposal we present parallel algorithms to accelerate configuration free-space analysis and enable the creation of an improved heuristic function for heuristic search-based planning, we give a new single-source shortest path algorithm used to compute the heuristic, and we describe a novel state lattice structure and algorithm that will allow driving on-road at high speeds. Our parallel algorithms show significant performance improvements for motion planning tasks run on GPUs compared to sequential algorithms on traditional CPUs. In addition, the increased instruction throughput of GPUs enables problems to be solved in real-time that are too complex to be solved in real-time with traditional CPUs. We conclude that parallel algorithms are necessary to maximize the performance of motion planning systems, and we propose several extensions to our work, including a culminating demonstration on a robotic vehicle.

Committee:Chris Urmson, Chair

Tony Stentz

Guy Blelloch

Dmitri Dolgov, Google Inc.