Committee: 

Dr. Wills, Advisor

Dr. Tsiotras, Co-Advisor

Dr. Hutchinson, Chair

Dr. Vela

Abstract: The objective of the proposed research is to maximize the parallelism extracted from sampling-based motion planning algorithms on heterogeneous architectures by making explicit the interaction between fundamental algorithmic constraints and available computing resources. Motion planning plays a central role in autonomous robotic systems, enabling navigation of previously unseen environments in a safe and efficient manner. Sampling-based methods are the de facto choice for most applications, given their incremental anytime improvement, graceful handling of complex constraints, and efficient exploration of high dimensional configuration spaces. As new computer architectures emerge delivering better performance and power consumption, there will be increasing opportunity to utilize such architectures to extend robotic capability. This work will systematically explore the design space of incremental motion planning algorithms on heterogeneous architectures to identify the essential control and data dependencies among subroutines, barriers to dynamic compute allocation based on program performance, and cost-benefit analysis of path and data structure optimizations.