# Fast-RRT: A RRT-Based Optimal Path Finding Method
## 4 Simulation and Result
### Find Initial Path  
This experiment is to test the algorithm's ability to find an initial solution, which refers to finding an obstacle-free path from \(x_{start}\) to \(x_{goal}\). The RRT algorithm is used as a benchmark algorithm to verify the efficiency of the Improved-RRT algorithm. The simulation environment used for this experiment is shown in Figure 8. The length and width of the environment are 1200 and 900, respectively. \(d_{goal}\) is the distance from the initial state \(x_{start}\) to the goal state \(x_{goal}\), and its value is set to 1000. Different step sizes affect the complexity of the problem. In our case, we designed multiple sets of experiments and set the step sizes to 10, 20, 30, 40, and 50, respectively. As the step size decreases, the searching number required to find a feasible solution increase along with the complexity of the problem. Figure 10: Schematic illustration of simulation environment 2, where three narrow passages are required from the starting state \(x_{start}\) to the goal state \(x_{goal}\). The distance from the state \(x_{start}\) to the target state \(x_{goal}\) is \(d_{goal}\). The value is set to 1000. Figure 9: Schematic illustration of simulation environment 1 containing multiple obstacles of different shapes. The distance from the state \(x_{start}\) to the target state \(x_{goal}\) is \(d_{goal}\), and its value is 1000. The results of the Fast-RRT algorithm and RRT algorithm in a test are shown in Figure 11. The red points are the random sampling state of the algorithm, the green line is the random tree generated by the algorithm, and the blue line is the feasible path obtained by the search. Obviously, the sampling points of the RRT algorithm are randomly distributed at any position in the state space. By contrast, the sampling points of the Fast-RRT algorithm are sparsely distributed around the random tree and densely distributed in the area far from the random tree. Fast-RRT avoids sampling in the area that the random tree has reached, which is beneficial for guiding the random tree to expand to the unknown area. At the same time, compared with the RRT algorithm, Fast-RRT uses fewer nodes to cover the space due to the presence of the abundant random trees of the RRT algorithm, resulting in more invalid extensions. Finally, Fast-RRT has multiple random edges near the boundary of the obstacle. Although it increases memory consumption, the Fast-RRT facilitates the random tree to bypass the obstacles to reach the target point quickly. Finally, the efficiency of the algorithm was evaluated by search time and memory consumption. Specifically, the number of nodes in the random tree is used to evaluate memory consumption. The average and variance are used as two indicators for the characterization of the search time. The average value of the search time represents the average performance of the algorithm, while the variance indicates its stability, which is both very important for practical applications (e.g., robots). In our case, RRT and Fast-RRT were run 100 times, and then the running time and the number of nodes of the random tree were recorded. The running time of the two algorithms and the average and variance of the number of nodes were further calculated. Figure 12 shows the results of the running time. Compared with the RRT algorithm, the average and variance of the search time of the Fast-RRT algorithm are significantly reduced. When the step size is set to 50, the average and variance of the search time are 0.016 s and 0.009 s, respectively. By contrast, for the RRT algorithm, the average and variance of the search time are 0.043 s and 0.043 s, respectively. Correspondingly, the average search time and the variance within the Fast-RRT algorithm are only 37.2% and 20.9% of the RRT algorithm, respectively. As the step size decreases, the complexity of the problem increases along with the gap between them. When the step size is set to 10, the average and variance of the search time of the Fast-RRT algorithm are only 23.5% and 8.3% of the RRT algorithm.