Dynamic programming guided exploration for sampling-based motion planning algorithms

Abstract

Several sampling-based algorithms have been recently proposed that ensure asymptotic optimality. The convergence of these algorithms can be improved if sampling is guided toward the most promising region of the search space where the solution is more likely to be found. In this paper we propose three sample rejection methods that leverage the classification of the samples according to their potential of being part of the optimal solution to guide the exploration of the motion planner to promising regions of the search space. These sampling strategies are a direct by-product of the exploitation phase of the algorithm, which uses a dynamic programming (DP) step while planning on random graphs as, for example, is done in the RRT# algorithm. It is shown that the proposed sampling strategies are able to compute high-quality solutions, much faster than existing algorithms. We provide numerical results and compare the performance of the proposed algorithm with the original RRT# and the RRT* algorithms.