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. Furthermore, we maintain that the proposed algorithms are easily parallelizable in order to take full advantage of recent technological advances in multi-core computer architectures and GPUs.
This project is sponsored by NSF.