Incremental Sampling-based Algorithms for Optimal Motion Planning

Details Incremental Sampling-based Algorithms for Optimal Motion Planning Incremental Sampling-based Algorithms for Optimal Motion Planning

2010-05-03

arxiv.org/abs/1005.0416v1

Computer Science

Robotics

20 pages, 10 figures, this manuscript is submitted to the International Journal of Robotics Research, a short version is to ap

Scientific paper

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 have been established so far. The first contribution of this paper is a negative result: it is proven that, under mild technical conditions, the cost of the best path in the RRT converges almost surely to a non-optimal value. Second, a new algorithm is considered, called the Rapidly-exploring Random Graph (RRG), and it is shown that the cost of the best path in the RRG converges to the optimum almost surely. Third, a tree version of RRG is introduced, called the RRT$^*$ algorithm, 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.

Affiliated with

Also associated with

No associations

Rating

Incremental Sampling-based Algorithms for Optimal Motion Planning does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Incremental Sampling-based Algorithms for Optimal Motion Planning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incremental Sampling-based Algorithms for Optimal Motion Planning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-531003