A Fast Marching Gradient Sampling Strategy for Motion Planning using an Informed Certificate Set

Abstract

We present a novel fast marching gradient sampling strategy to accelerate the convergence speed of sampling-based motion planning algorithms. This strategy is based on an informed certificate set which consists of the robot states with exact collision status as well as the minimum distance and the gradient to the nearest obstacle. The informed certificate set covers almost the whole planning space such that it contains rich information for the planner. The best quality point in this set is selected as the marching seed to guide the search graph move steadily to the goal set. The distance and gradient information of the marching seed helps to generate a new sample with almost sure collision status. When a feasible solution has been found, this set can construct the restricted subset that can improve current path quality. This marching gradient sampling strategy is applied to the RRT and RRT* algorithms. Simulation experiments demonstrate that the convergence speed to a feasible solution or to the optimal solution is almost twice faster than that of the safety certificate algorithms.