Incremental Sampling-based Algorithms for Optimal Motion Planning

Citations Over TimeTop 1% of 2010 papers

Abstract

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 almost surely to a non-optimal value, as the number of samples increases. Second, a new algorithm is considered, called the Rapidly-exploring Random Graph (RRG), and it is shown that the cost of the best path returned by RRG converges to the optimum almost surely. Third, a tree version of RRG is introduced, called RRT * , which preserves the asymptotic optimality of RRG while maintaining a tree structure like RRT. The analysis of the new algorithms hinges on novel connections between sampling-based motion planning algorithms and the theory of random geometric graphs. In terms of computational complexity, it is shown that the number of simple operations required by both the RRG and RRT * algorithms is asymptotically within a constant factor of that required by RRT.

Related Papers

• → A new algorithm for the detection of seismic quiescence: introduction of the RTM algorithm, a modified RTL algorithm(2011)29 cited
• → An improved filtering algorithm based on median filtering algorithm and medium filtering algorithm(2012)6 cited
• → Remarks on Algorithm 2, Algorithm 3, Algorithm 15, Algorithm 25 and Algorithm 26(1961)2 cited
• → Medical image registration algorithm based on Powell algorithm and improved genetic algorithm(2013)1 cited
• → Remarks on Algorithm 332: Jacobi polynomials: Algorithm 344: student's t -distribution: Algorithm 351: modified Romberg quadrature: Algorithm 359: factoral analysis of variance(1970)