# CERRT: A Mobile Robot Path Planning Algorithm Based on RRT in Complex Environments
## 3 Craft
### Environmental Awareness  
Algorithms based on Sampling often encounter difficulties when navigating narrow passages due to their lack of environmental sensitivity. However, whether a passage is deemed narrow is contingent on the extension step length. If the step length is much smaller than the narrow passage, it can be considered a spacious road. Conversely, if the step length is too small, the search accuracy will be too high, resulting in lower algorithm efficiency. To combat this, an environment perception strategy is proposed to enable the random tree to quickly identify and pass through narrow passages without decreasing the step length. When a collision occurs with an obstacle during the tree expansion process, expansion is halted and enters the environment perception stage. Algorithm 3 provides a comprehensive outline of this phase. To begin the environmental perception process, local spatial information is collected around the \(x_{narest}\) point through local sampling. Local sampling uniformly samples \(n\) points around the vertex to be expanded using the expansion step length as the radius and stores them in a point set \(S\). Here, \(n=16\) is used as an example. Set \(S\) is then separated into two subsets, \(S_{obs}\) and \(S_{free}\), based on whether the position of \(S\) lies within the obstacle area. The boundary points between \(S_{free}\) and \(S_{obs}\) are selected and stored in \(S_{blry}\), where \(S_{blry}\subseteq S_{free}\) (Lines 2-3 in Algorithm 3). Figure 4 illustrates the schematic diagram of local sampling, where the red point represents the expanding vertex where a collision occurred, the blue points represent \(S_{obs}\) sampling points, the green points represent boundary points \(S_{blry}\), and the yellow and green points represent \(S_{free}\) points. In Figure 4, the obstacle is recognized as a wall obstacle. For the local sampling to accurately identify narrow passages, it is crucial to further clarify the quantity of local sampling points \(n\) and the extension step size \(d_{step}\). Given the width \(d_{gap}\) of the minimum feasible driving passage and the extension step size \(d_{step}\), to ensure that the local sampling can sample the interior of the passage, the spacing between adjacent sampling points should not exceed \(d_{gap}\). The number of sampling points \(n\) must align with Equation (1). \[n\geq\frac{2\pi}{\arccos\left(1-\frac{d_{gap}^{2}}{2d_{step}^{2}}\right)} \tag{1}\]  
After local sampling, environments are categorized based on the numerical relation between the point sets \(S_{brr}\) and \(S_{blry}\). The environment is split into two primary classifications: wall obstacles and passage environments. If \(S_{blry}\) has only two vertices and \(S_{free}\) has more than two vertices, the environment is classified as a wall obstacle, as shown in Figure 4. In this case, the algorithm exits the environment perception and performs resampling (Lines 4-6 in Algorithm 3). Otherwise, the environment is considered a narrow passage environment, which can be further classified into entrance, interior, exit, and  
Figure 4: Local sampling process and wall obstacle types. multi-branching regions, as shown in Figure 5. In this figure, the red point represents the \(x_{narrest}\) point, the yellow points represent \(S_{free}\) sample points, the green points represent the boundary points \(S_{hdry}\), and the blue points represent the \(S_{abs}\) sample points. The green sector area \(R\) contains a continuous set of \(S_{free}\) points. To traverse the narrow passage, multiple sector regions are divided using \(x_{narrest}\) as the fulcrum and the expansion step as the radius. Each sector region contains only a continuous set of \(S_{free}\) points. The resulting \(n\) sector regions are denoted as \(R_{i}\) (i = 1, 2, \(\ldots\), \(n\)). The sector area that does not contain the \(x_{parent}\) point is selected as the area for expansion.