Sampling-based motion planners (SBMPs) are effective for planning with complex kinodynamic constraints in high-dimensional spaces, but they still struggle to achieve real-time performance, which is mainly due to their serial computation design. In this thesis we introduce two highly parallel kinodynamic SBMP algorithms designed explicitly for many-core architectures such as GPUs.

Our first algorithm, Kinodynamic Parallel Accelerated eXpansion (Kino-PAX ), rapidly solves initial motion planning problems, whereas our second algorithm, Asymptotically Near-Optimal Kinodynamic Parallel Accelerated eXpansion (Kino-PAX* ), targets finding near-optimal trajectories over extended planning durations. Both algorithms concurrently grow a tree of trajectory segments by decomposing the iterative growth process into three massively parallelizable subroutines. We align the design closely with GPU execution hierarchies, through ensuring that threads are largely independent, share equal workloads, and take advantage of low-latency resources while minimizing high-latency data transfers and process synchronizations. This design results in a very efficient GPU implementation. We prove that Kino-PAX is probabilistically complete and analyze its scalability with compute hardware improvements. We also prove that Kino-PAX* achieves probabilistic δ-robust completeness and asymptotic δ-robust near-optimality.

Empirical evaluations demonstrate solutions in the order of 10 ms on a desktop GPU and in the order of 100 ms on an embedded GPU, representing up to 1000× improvement compared to coarse-grained CPU parallelization of state-of-the-art sequential algorithms over a range of complex environments and systems. In addition, Kino-PAX* finds high-quality solutions within approximately 10 ms and can also be tuned effectively to converge towards near-optimal solutions over extended planning periods.