Path-planning algorithms in high-dimensional spaces

Abstract

In this thesis, we discuss the problem of path-planning in high-dimensional spaces. Large search spaces tend to lead to slow algorithms in order to find a path or to converge towards the optimal solution of a path-planning problem. This thesis investigates both discrete and continuous search spaces. For discrete search spaces, the use of multi-scale data structure allows a planning algorithm to consider a region of space at different resolutions through the execution of the algorithm and to accelerate the execution of the algorithm. The proposed algorithm is proven to be complete, it will find a solution if one exists, or report that no solution exists. Multiple applications are presented with direct construction of the multi-scale map via perception algorithms, as well as a sampling approach for problems where constructing the multi-scale map is too expensive. For continuous search spaces, the thesis explores the use of classical optimization methods within the family of sampling-based planning algorithms. An experiment is first presented to show the convergence limits of sampling-based algorithms. Then an optimization formulation shows how samples of the search space can be repositioned in order to enhance the estimate of the value function of the problem. Finally, this optimization is integrated in the framework of Rapidly-exploring Random Trees to introduce the Deformable Rapidly-exploring Random Trees algorithm. This algorithm rapidly finds a feasible solution, similarly to the other RRT algorithms, and it also significantly increases the convergence rate of the solution thanks to the added optimization step. Analysis of the parameters and applications of the algorithm show significant improvement compared to the state-of-the-art algorithms.