# Fast-RRT: A RRT-Based Optimal Path Finding Method
###### Abstract
Alternatively, improving the search efficiency is another focus in RRT algorithm-related work, such as speeding up the search and minimizing the variance of search time. For instance, RRT-Connect [13] constructs two trees rooted in the initial state and the target state and makes the two trees grow toward each other. In [14], a 2D Gaussian mixture model is used to find a high-quality initial solution quickly. Batch Informed Trees [15] limits the state space to an incrementally increasing subset and thus quickly finds a feasible path. Unfortunately, these methods only performed well in certain environments. Combining RRT with other path search algorithms is an important way to speed up the search process. In [16], the artificial potential field algorithm is incorporated in RRT* to accelerate convergence rate, but the planning time may dramatically increase in complex environments. The A*-RRT* [17] algorithm uses the path generated by the A* algorithm to guide the sampling procedure of the RRT* planner, which significantly accelerates the convergence speed. However, quite a long time is required for A* to find an initial path when it comes to large-scale problems. LM-RRT [18] applies reinforcement learning methods to guide the growth of trees, but the learning-based methods may not perform well in the new environment. Heuristic-biased sampling is another important method. Informed RRT* [19] limits the sampling area to an ellipsoidal containing a feasible path, thereby returning an approximate optimal path faster than RRT*. Hybrid-RRT [20] combines RRT-Connect and Informed RRT* to accelerate the convergence speed of the algorithm. In [21], the obstacle boundary information is used to ignore bad sampling points. Dynamic-Domain RRTs [22] avoid the samples that are too far from the current tree. RRT*-Smart [23] uses the initial path to generate biasing sampling points. Recently, learning-based methods have been widely applied in motion planning research. Neural RRT*[12] uses deep learning to learn a distribution probability for sampling. RL-RRT [24] explores deep reinforcement learning policy as a local planner and uses distance function that learns by deep learning to bias tree-growth towards the target area. In [25], a learning algorithm combining Inverse Reinforcement learning and RRT* is used to learn the RRT*'s cost function. The DL-P-RRT* algorithm applies deep learning to the RRT* algorithm using the virtual artificial potential field to learn the artificial potential field function. Learning-based methods perform well in some environments, but they may suffer from bad generalization ability in new environments. In this paper, we propose an RRT-based planning method for optimal motion planning, called Fast-RRT. Compared with RRT*, Fast-RRT accelerates the search speed of the optimal path by order of magnitude. To be specific, Fast-RRT divides the search for the optimal path into two steps. The Improved-RRT algorithm is first used to find a feasible path quickly, and then the Fast-Optimal algorithm fuses multiple paths to obtain an optimal path. For Improved RRT, two important improvements were made compared to the RRT algorithm, such as Fast Sampling and Random Steering. Fast Sampling improves the search speed of the RRT algorithm by refusing to sample in the explored area and solves the problem of the large variance in the search time of the RRT algorithm. Random Steering randomly chooses the direction to expand when the expansion fails, which solves the problem of poor performance of the RRT algorithm in narrow channel scenarios. By introducing these two improvements, the Improved-RRT algorithm can quickly find a feasible solution. Besides, Fast-Optimal can obtain the optimal path by virtue of fusing multiple paths and has a faster convergence speed as compared to RRT*. After a new feasible path is searched by Improved-RRT, Fast-Optimal merges it with the current optimal path to obtain a better path. The fusion operation of Fast-Optimal also consists of two steps, including path fusion and path fine-tuning.