# CERRT: A Mobile Robot Path Planning Algorithm Based on RRT in Complex Environments
## 1 Introduction
RRT* is a milestone in the development of RRT. To improve the convergence speed of the RRT* algorithm, numerous scholars have conducted extensive research, mainly optimizing the sampling, ChooseParent, and Rewire processes of RRT*. [PERSON] et al. put forth an intelligent sampling tree named RRT*-Smart [13] to expedite the convergence rate of the algorithm, but the quality of the generated path depends largely on the initial solution. Inspired by node exclusion, [PERSON] et al. [14] employ a direct sampling method within the hyperellipsoid to enhance algorithm performance, but the algorithm is no longer applicable when the ellipsoid is larger than the planning domain. P-RRT* [15] combines APF and RRT* to provide feasible directions for sampling exploration, which speeds up the convergence speed. [PERSON] et al. improved the ChooseParent and Rewire procedures using the triangle inequality to propose the Quick-RRT* [16], which generates better initial paths and faster convergence. Inspired by Quick-RRT*, F-RRT* [17] creates a parent node near the obstacle for each sampled point, obtaining better initial solutions and faster convergence speed than Quick-RRT* and RRT* under the same conditions. Although algorithms based on the RRT* framework can find the optimal or approximate optimal solution, they all require a large number of samples to gradually search for the optimal path. Therefore, when the important parameter for an algorithm is its running speed, optimizing the path directly generated by RRT is necessary. To optimize the initial path generated by RRT, [PERSON] et al. [18] proposed a method to optimize the initial path generated by RRT by merging trees based on the initial path to form a closed-loop path and then performing optimization to obtain the relatively optimal path. [PERSON] et al. [19] introduced a bidirectional pruning optimization strategy that prunes redundant nodes from both the starting and ending points of the path and selects the shortest optimized path, effectively improving the quality of the path. In conclusion, extensive research has been conducted on path planning utilizing the RRT algorithm in complex environments. However, no algorithm currently exists that effectively and simply addresses the dual issues of subpar performance in complex environments and inferior path quality. To remedy this, the present paper proposes the complex environments rapidly-exploring random tree (CERRT) path planning algorithm inspired by RRV, which greatly improves the efficiency of the algorithm in complex environments and optimizes the generated initial feasible paths. The main contributions of this paper are as follows:  
1. We have designed a new process for environmental perception. This process determines the type of environment by sampling the local area, eliminating the need for principal component analysis and significantly reducing computational complexity. 2. We propose a pre-allocated vertex expansion method in conjunction with a vertex death mechanism. This approach foregoes the expansion of inactive tree vertices to prevent the algorithm from getting stuck in concave areas. When combined with the environment-aware capability, the algorithm deftly navigates complex environments such as mazes, narrow passages, and concave regions. 3. We also suggest a bidirectional contraction optimization strategy. Once a feasible path is identified, its points are contracted in both directions, yielding a more streamlined and efficient path. The rest of this paper is structured as follows: Section 2 outlines the mathematical definition of the planning problem along with a brief introduction to the core principles of RRT, RRV and Fast-RRT. Section 3 offers an in-depth description of our proposed CERRT algorithm framework. Section 4 presents simulation experiments that compare the new algorithm against RRT and RRV. Finally, Section 5 concludes the paper.