# CERRT: A Mobile Robot Path Planning Algorithm Based on RRT in Complex Environments
## 3 Craft
### Algorithm Framework  
The CERRT algorithm is an optimization of the RRT algorithm. It uses an array \(V\) to store expandable points in tree \(T\) and constantly deletes non-extensible points, known as dead nodes.  
The CERRT algorithm initially stores the starting point \(x_{start}\) point as the root node in the tree and pre-allocates a corresponding set of expandable points, \(x_{start}.CAND\) for it (Lines 1-3 in Algorithm 1). The sampler is adjusted to amplify the tree's growth orientation by systematically sampling points within the goal region with a certain probability. (Line 5 in Algorithm 1).  
Following sampling, the algorithm selects the nearest point \(x_{nearest}\) to the sampling point from the array \(V\) and queries the closest vertex to the sampling point \(x_{rand}\) from the expansion point set \(x_{nearest}.CAND\) of \(x_{nearest}\) to obtain the new node \(x_{new}\). Once found, the point is removed from \(x_{nearest}.CAND\). If \(x_{nearest}.CAND\) is empty after removal, and the vertex \(x_{nearest}\) is deemed dead and removed from the vertex array \(V\) (Lines 6-11 in Algorithm 1).  
Should a collision happen during expansion, the algorithm enters the environment perception phase to determine the type of environment where \(x_{nearest}\) is located. If \(x_{nearest}\) is near a channel, a new \(x_{new}\) point is calculated for expansion; otherwise, resampling is performed (Lines 13-14 in Algorithm 1).  
If no collision occurs during the expansion, \(x_{new}\) is added to tree \(T\), and a corresponding set of candidate nodes for \(x_{new}\) is pre-allocated. If the set of candidate nodes overlaps with any existing nodes in the tree, no allocation is performed. If the set of candidate nodes for \(x_{new}\) is empty after allocation, it is not added to array \(V\) (Lines 17-21 in Algorithm 1).  
Finally, after obtaining a feasible path, the algorithm optimizes it to reduce the cost \(C(\sigma)\) (Line 24 in Algorithm 1). A more detailed description of the algorithm process is given in the subsequent section.  
```
1:\(T=\{x_{start}\}\);
2:\(V=T\);
3:\(x_{start}.CAND=\) initTree(\(x_{start}\));
4:for\(i=1\) to \(N\)do
5:\(x_{rand}=\) GetSample(\(i\));
6:\((x_{nearest},\)\(near_{idx})=\) GetNearest(\(V\), \(x_{rand}\));
7:\((x_{new},\)\(new_{idx})=\) min(distance(\(x_{nearest}.CAND(c)\), \(x_{rand}\)));
8: Delete(\(x_{nearest}.CAND(new_{idx})\));
9:if Empty(\(x_{nearest}.CAND\)) then
10: Delete(\(V(near_{idx})\));
11:endif
12:if Overlap(\(x_{new}\), \(T\)) then continue; endif
13:if Collision(\(x_{new}\), \(x_{nearest}\), \(Map\)) then
14:\((x_{new},\)\(Fig)=\) Aware(\(x_{nearest}.parent\), \(x_{nearest}\), \(Map\), \(d_{step}\), \(d_{gap}\));
15:if -Fig then continue; endif
16:endif
17:\(x_{new}.CAND=\) SetCAND(\(x_{nearest}\), \(x_{new}\), \(d_{step}\), \(T\), \(V\));
18:if NoEmpty(\(x_{new}.CAND\))
19:\(V=V\cup\{x_{new}\}\);
20:endif
21: T = T \(\cup\{x_{new}\}\);
22:if\(x_{new}\in X_{goal}\)then break; endif
23:endfor
24:\(\sigma=\) GetPath(\(\sigma\));
25:return\(\sigma=\) OptPath(\(\sigma\));
```  
**Algorithm 1** CERRT(\(x_{start}\), \(x_{goal}\), \(d_{step}\), \(N\), \(Map\))