Sparse tree heuristics for RRT* family motion planners

Abstract

Sampling-based approaches constitute the state-of-the-art for robot motion planning. Collision checking and nearest neighbor search are the major performance bottlenecks of these methods. For an environment with fixed number of obstacles, collision checking for a new candidate state is a constant time operation, whereas nearest neighbor search usually degrades during the runtime of the algorithm. Multiple variants of the single-query probabilistically optimal RRT* algorithm were introduced to tackle these issues. In this work, we present heuristics to augmented RRT* such that it finds the initial solution faster and converges to the optimal solution with less number of nodes. Instead of checking collision for every new node candidate, we consider only samples which are maximum step size away from the nearest neighbor or are near obstacles. With our augmented node concept, we embed nearby obstacle information to the nodes either as a binary variable (RRT*K) or with a higher resolution quadrant based representation (RRT*Q). Extensive benchmark batteries conducted on 2D and 3D problems with geometric constraints show the efficacy of our approach.