# CERRT: A Mobile Robot Path Planning Algorithm Based on RRT in Complex Environments
## 3 Craft
### Vertex Expansion Method  
The traditional rapidly-exploring random tree (RRT) algorithm randomly samples the configuration space to guide the tree's expansion and exploration. When the RRT algorithm expands a new vertex, it calculates the distance '\(d\)' between the point and the goal. If '\(d\)' is less than a predetermined threshold '\(r\)', it means the algorithm has found the goal point and the search ceases. If not, the search continues. In this regard, each time a new node is expanded, the RRT algorithm explores the region with a radius of '\(r\)' centered on that node. The unexplored regions of tree nodes are referred to as the 'unknown regions', while the explored areas are defined as 'exploration regions'. With each expansion, new exploration regions are created within the unknown regions. The RRT algorithm achieves the exploration of the entire space by continuously sampling and expanding. However, this process brings about a scenario where some exploration regions are revisited, some even more than twice. The exploration efficiency is thus measured by the area of novel exploration regions explored by newly expanded vertices and the frequency of re-exploration of already known regions. Efficiency is high when the area of unexplored regions explored is large, but it is low if the area of already known regions explored is large or if they are explored multiple times. Figure 2 illustrates the issue of redundant exploration in known regions. In this figure, the blue region represents the explored area, while the overlapped area denotes the repeated examination. The green zone denotes the exploration area for new vertices, and new vertices conduct repeated exploration on region '\(T\)' enclosed by the red circle more than three times. Figure 2a elucidates the traditional RRT expansion process. This diagram illustrates that vertices \(x_{0}\), \(x_{1}\), and \(x_{2}\) have already examined the '\(T\)-region' twice. Following this, vertex \(x_{1}\) extends toward the \(x_{rand}\) point and produces a fresh vertex \(x_{new}\). Regrettably, this new vertex instigates a third redundant exploration of the '\(T\)-region'. Multiple explorations of the same area are pointless. In response to the problem mentioned earlier, our research suggests that setting the angle at 120 degrees between each vertex and its connected points can drastically decrease unnecessary exploration in space, as shown in Figure 2b. When a new point, \(x_{new}\), extends from vertex \(x_{1}\), the angles between the three edges \(x_{1}\)-\(x_{0}\), \(x_{1}\)-\(x_{2}\) and \(x_{1}\)-\(x_{new}\) are all 120 degrees. This decreases the '\(T\)-region' to a mere 30% of what it is in Figure 2a. The exploration process also avoids repeating exploration areas over three times, which greatly increases efficiency. To achieve this, we propose pre-allocated expansion points and a vertex dead strategy to ensure that the angle between each vertex's edges is 120 degrees. Algorithm 2 presents the detailed process of allocating candidate extension points. Initially, the angle \(ang_{0}\) of the edge \(x_{new}\)-\(x_{nearest}\) is computed within the Cartesian coordinate system. Following  
Figure 2: Issue of redundant exploration in known regions. (**a**) Redundant exploration using the traditional extension strategy. (**b**) Improved extension strategy to reduce redundancy. this, candidate extension points are created with a 120-degree bias angle (Lines 1-4 in Algorithm 2). If the candidate extension point coincides with a tree node, the allocation fails (Lines 6-10 in Algorithm 2). Figure 3 depicts the improved vertex expansion strategy. In this figure, the black, red, green, and yellow dots, respectively, represent standard tree vertices, \(x_{nearest}\), \(x_{new}\), and \(x_{rand}\) sample points. Dashed circles are potential expansion points for each vertex, while red-crossed points signify discarded vertices removed from array \(V\).