Use of relaxation methods in sampling-based algorithms for optimal motion planning

Several variants of incremental sampling-based algorithms have been recently proposed in order to optimally solve motion planning problems. Popular examples include the RRT* and the PRM* algorithms. These algorithms are asymptotically optimal and thus provide high quality solutions. However, the convergence rate to the optimal solution may still be slow. Borrowing from ideas used in the well-known LPA* algorithm, in this paper we present a new incremental sampling-based motion planning algorithm based on Rapidly-exploring Random Graphs (RRG), denoted by RRT^# (RRT “sharp”), which also guarantees asymptotic optimality, but, in addition, it also ensures that the constructed spanning tree rooted at the initial state contains lowest-cost path information for vertices which have the potential to be part of the optimal solution. This implies that the best possible solution is readily computed if there are some vertices in the current graph that are already in the goal region.