The Role of Vertex Consistency in Sampling-based Algorithms for Optimal\n Motion Planning

Abstract

Motion planning problems have been studied by both the robotics and the\ncontrols research communities for a long time, and many algorithms have been\ndeveloped for their solution. Among them, incremental sampling-based motion\nplanning algorithms, such as the Rapidly-exploring Random Trees (RRTs), and the\nProbabilistic Road Maps (PRMs) have become very popular recently, owing to\ntheir implementation simplicity and their advantages in handling\nhigh-dimensional problems. Although these algorithms work very well in\npractice, the quality of the computed solution is often not good, i.e., the\nsolution can be far from the optimal one. A recent variation of RRT, namely the\nRRT* algorithm, bypasses this drawback of the traditional RRT algorithm, by\nensuring asymptotic optimality as the number of samples tends to infinity.\nNonetheless, the convergence rate to the optimal solution may still be slow.\nThis paper presents a new incremental sampling-based motion planning algorithm\nbased on Rapidly-exploring Random Graphs (RRG), denoted RRT# (RRT "sharp")\nwhich also guarantees asymptotic optimality but, in addition, it also ensures\nthat the constructed spanning tree of the geometric graph is consistent after\neach iteration. In consistent trees, the vertices which have the potential to\nbe part of the optimal solution have the minimum cost-come-value. This implies\nthat the best possible solution is readily computed if there are some vertices\nin the current graph that are already in the goal region. Numerical results\ncompare with the RRT* algorithm.\n