# Fast-RRT: A RRT-Based Optimal Path Finding Method
###### Abstract  
As a sampling-based pathfinding algorithm, Rapidly Exploring Random Trees (RRT) has been widely used in motion planning problems due to the ability to find a feasible path quickly. However, the RRT algorithm still has several shortcomings, such as the large variance in the search time, poor performance in narrow channel scenarios, and being far from the optimal path. In this paper, we propose a new RRT-based path find algorithm, Fast-RRT, to find a near-optimal path quickly. The Fast-RRT algorithm consists of two modules, including Improved RRT and Fast-Optimal. The former is aims to quickly and stably find an initial path, and the latter is to merge multiple initial paths to obtain a near-optimal path. Compared with the RRT algorithm, Fast-RRT shows the following improvements: (1) A Fast-Sampling strategy that only samples in the unreched space of the random tree was introduced to improve the search speed and algorithm stability; (2) A Random Steering strategy expansion strategy was proposed to solve the problem of poor performance in narrow channel scenarios; (3) By fusion and adjustment of paths, a near-optimal path can be faster found by Fast-RRT, 20 times faster than the RRT* algorithm. Owing to these merits, our proposed Fast-RRT outperforms RRT and RRT* in both speed and stability during experiments. path planning; RRT; random expansion; path optimization +
Footnote †: journal: Applied Sciences  
The sampling-based planning algorithm is probabilistically complete; thus, the probability of finding a feasible path approaches 1 when the number of samples tends to infinity. Probabilistic Roadmaps (PRM) [6] and RRT [7] are two important algorithms of sampling-based planners. PRM is a multi-query motion planning algorithm, which obtains a graph representing spatial connectivity through random sampling in the state space, and then generates a feasible path through graph search. After constructing the graph, the PRM can be used to search multiple paths. However, it is a time-consuming process to construct a map of the entire space for a single search. By contrast, as a single-query motion planning algorithm, the RRT only explores the state space by growing a tree rooted at the start state and is thus faster than the PRM. The RRT algorithm involves three steps, which first randomly samples a state in state space, followed by selecting the nearest nodes of the random tree, and growing from the nearest neighbor sampling point to a random state. Once the tree reaches the goal region, the search is successful, and RRT will return to a feasible path. Although RRT can quickly find an initial path in high-dimensional space, it still has many disadvantages. For example, owing to the random sampling, the variance of its search time is so large that it may require a long time to find a feasible path. The RRT does not perform well in narrow channel scenarios [8]. Moreover, the path found by RRT may be far away from the optimal path [9] since the path is randomly generated. Rapidly Exploring Random Tree Star (RRT*) [10] was considered an important extension of RRT. After finding an initial path, RRT* keeps optimizing the initial path by continuously sampling [11]. Compared with RRT, RRT* introduces two operations of neighbor search and rewiring tree to reach the optimal path. It can be proved that the path obtained by RRT* is optimal when the number of sampling approaches infinity. However, for RRT*, plenty of time and memory usage are required to reach the optimal path [12]. Similarly, RRT* also suffers from the problem of the large variance in search time. Great efforts were devoted to improving the quality of the paths obtained by RRT and RRT*. For instance, by extending RRT* to kinodynamic systems, corresponding Kinodynamic RRT* can obtain an optimal trajectory that satisfies dynamic constraints. Anytime-RRT* can quickly re-plan the path with any point as the initial point.