Motion planning and trajectory generation problems are at the at the core of all autonomous and robotic systems. Although – at least in theory – such problems can be solved using optimal control or dynamic programming, the computational complexity for realizing these solutions is still prohibitive for many real-life problems, especially for high-dimensional systems. Recently, randomized algorithms have been proposed, which promise to remedy the “curse of dimensionality” associated with more traditional, deterministic methods. This is achieved by avoiding the a priori gridding of the search space, and under certain conditions they even ensure optimality, at least asymptotically. Nonetheless, three main bottlenecks hinder the broader applicability of these randomized algorithms: the need for more efficient sampling strategies, the need to avoid the computationally expensive collision checking, and the lack of fast and near-optimal solutions of the so-called “local steering” problem, especially for the case of nonholonomic or underactuated nonlinear dynamic systems. In this research, we propose to eliminate these three bottlenecks by utilizing ideas from machine learning and spectral methods for random walk operators on graphs. Specifically, we build on recent results and ideas from Rapidly-exploring Random Graphs (RRG), along with relaxation methods from the area of Asynchronous Dynamic Programming (ADP) and regression techniques to speed-up execution times and minimize memory requirements. The proposed algorithms are easily parallelizable in order to take full advantage of recent technological advances in multi-core computer architectures and GPUs. The proposed motion-planners are suitable for solving trajectory generation problems for systems with many degrees of freedom (such as anthropomorphic robots and surgical robotics).
