Hybridization of sampling-based motion planning algorithms and spherical representations

Abstract

Thanks to the probabilistic completeness and almost-sure asymptotic optimality, sampling-based motion planning algorithms have been widely and deeply studied for the past decades. It is, however, a well-known fact that the computational overhead of sampling-based algorithm can dramatically increase with respect to the complexity of a given problem. For this reason, improving the convergence speed toward the optimal solution in motion planning problem is a still-always open problem. In the aspect of computational importance, Sampling, Collision Checking, Nearest Neighbor Search have been considered major components in sampling-based approaches which can greatly affect the resulting random geometric graph. To this context, the thesis of this dissertation is that in order to achieve the faster convergence speed toward the optimal solution we analyze the aforementioned three major components to improve the overall performance of the sampling-based planning, i.e., convergence speed toward the optimal solution. We particularly consider spherical representations to discretize space for various purpose and exploit those for biased-sampling, probabilistic collision checking, and adaptive sparse graph construction. We also hybridize sampling-based and optimized-based planning in conjunction with the spherical representations for faster convergence speed.