Back to Search
Start Over
Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate.
- Source :
-
Expert Systems with Applications . Jun2019, Vol. 123, p82-90. 9p. - Publication Year :
- 2019
-
Abstract
- Highlights • Sampling-based algorithms are commonly used in motion planning problems. • The RRT* algorithm incrementally builds a tree of motion to find a solution. • Taking a shortcut to the ancestry increases the convergence rate to the optimal. • Combination with sampling strategies further improves the performance. Abstract The Rapidly-exploring Random Tree (RRT) algorithm is a popular algorithm in motion planning problems. The optimal RRT (RRT*) is an extended algorithm of RRT, which provides asymptotic optimality. This paper proposes Quick-RRT* (Q-RRT*), a modified RRT* algorithm that generates a better initial solution and converges to the optimal faster than RRT*. Q-RRT* enlarges the set of possible parent vertices by considering not only a set of vertices contained in a hypersphere, as in RRT*, but also their ancestry up to a user-defined parameter, thus, resulting in paths with less cost than those of RRT*. It also applies a similar technique to the rewiring procedure resulting in acceleration of the tendency that near vertices share common parents. Since the algorithm proposed in this paper is a tree extending algorithm, it can be combined with other sampling strategies and graph-pruning algorithms. The effectiveness of Q-RRT* is demonstrated by comparing the algorithm with existing algorithms through numerical simulations. It is also verified that the performance can be further enhanced when combined with other sampling strategies. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09574174
- Volume :
- 123
- Database :
- Academic Search Index
- Journal :
- Expert Systems with Applications
- Publication Type :
- Academic Journal
- Accession number :
- 134739088
- Full Text :
- https://doi.org/10.1016/j.eswa.2019.01.032