# CERRT: A Mobile Robot Path Planning Algorithm Based on RRT in Complex Environments
## 3 Craft
### Path Optimization Strategy  
Sampling-based algorithms for path planning can often generate redundant nodes due to their random nature, potentially lowering the quality of path planning. In this paper, a bidirectional shrinking optimization strategy (BSOS) is proposed based on the pruning optimization strategy (POS) to further enhance the quality of the path. Figure 5: Narrow passage perception. (**a**) Entrance of the passage; (**b**) Interior of the passage; (**c**) Exit of the passage; (**d**) Multiple branching passages. In Figure 6a, moving from \(x_{0}\) to \(x_{7}\) requires avoiding an obstacle, and the black line path \(x_{0}\)-\(x_{1}\)-\(x_{2}\)-\(x_{3}\)-\(x_{4}\)-\(x_{5}\)-\(x_{6}\)-\(x_{7}\) in the figure is the original planned path. This path contains a large number of redundant nodes. By using the pruning strategy and based on the triangle inequality theorem, the robot can move directly from \(x_{0}\) to \(x_{2}\) without passing through \(x_{1}\), thus identifying \(x_{1}\) as a redundant node. Figure 6b illustrates the application of the pruning operation on the entire initial path, eliminating superfluous nodes \(x_{1}\), \(x_{3}\), \(x_{5}\), and \(x_{6}\). The remaining nodes are connected to obtain the pruned and optimized yellow path \(x_{0}\)-\(x_{2}\)-\(x_{4}\)-\(x_{7}\), as shown in Figure 6c. The yellow path obtained by POS has not only fewer path points but also a shorter path length, but it is not an approximate optimal path. This paper proposes a bidirectional shrinking-based optimization of path points on the basis of pruning the path \(x_{0}\)-\(x_{2}\)-\(x_{4}\)-\(x_{7}\). The endpoints \(x_{0}\) and \(x_{7}\) are excluded from the shrinking process, leaving the remaining points to participate in two phases of reduction. In the first round, each path point moves toward the next point with a higher number according to the sequence of the point number. At the same time, it constantly checks whether there is any collision with the previous path point. If a collision is about to occur, the point stops moving, as shown in Figure 6d. For instance, path point \(x_{2}\) moves toward \(x_{4}\) until the \(x_{0}\)-\(x_{2}\) segment is about to collide with the obstacle, and then the point stops. After that, path point \(x_{4}\) moves toward \(x_{7}\) until the \(x_{2}\)-\(x_{4}\) segment is about to collide with the obstacle, and then the point stops. Once all path points have completed the shrinking movement, the blue path \(x_{0}\)-\(x_{2}\)-\(x_{4}\)-\(x_{7}\) in Figure 6d is obtained, indicating that the first round of shrinking is completed. In the second round of contraction, the order is reversed, with the points moving from high to low according to their vertex number. As shown in Figure 6e, path point \(x_{4}\) moves toward \(x_{2}\) first, and then it stops when the \(x_{4}\)-\(x_{7}\) segment is about to collide with the obstacle. Then, path point \(x_{2}\) moves toward \(x_{0}\) until the \(x_{2}\)-\(x_{4}\) segment is about to collide with the obstacle. Once all path points have completed the shrinking movement, the green path \(x_{0}\)-\(x_{2}\)-\(x_{4}\)-\(x_{7}\) in Figure 6f is obtained, which is the final path obtained by the bidirectional search optimization strategy. The bidirectional shrinking method results in a path that is shorter and closer to the optimal configuration. The specific process of using the bidirectional shrinking path optimization strategy to optimize the CERRT planning path is shown in Figure 7.  
Figure 6: Path optimization strategy. (**a**–**c**) show pruning optimization of the original path, where the yellow path represents the pruned optimized path. (**d**–**f**) show bidirectional shrinkage optimization of the path, where the green path represents the final optimized path. 1. Obtain the initial optimized path \(\sigma\) (\(x_{0}\), \(x_{1}\), \(\ldots\), \(x_{n}\)) using the CERRT and pruning optimization strategies, where \(x_{i}\) (i = 0, 1, \(\ldots\), \(n\)) is a path point and i is the path point number. 2. Initialize \(i=1\). 3.