Incremental Sampling-based Algorithms for Optimal Motion Planning

During the last decade, incremental sampling-based motion planning algorithms, such as the Rapidly-exploring Random Trees (RRTs), have been shown to work well in practice and to possess theoretical guarantees such as probabilistic completeness. However, no theoretical bounds on the quality of the solution obtained by these algorithms, e.g., in terms of a given cost function, have been established so far. The purpose of this paper is to fill this gap, by designing efficient incremental samplingbased algorithms with provable optimality properties. The first contribution of this paper is a negative result: it is proven that, under mild technical conditions, the cost of the best path returned by RRT converges…

• AF
  Air Force Office of Scientific Research

  Award: FA 8650-07-2-3744
• AF
  Air Force Research Laboratory

  Award: FA 8650-07-2-3744