# RJ-RRT: Improved RRT for Path Planning in Narrow Passages
## 3 Rj-Rrt
### Sampling Space Greedy Reduction Strategy  
When there is only the root node \(x_{init}\) in the tree, like the sampling strategy is the same as Basic-RRT, sampling points will be randomly selected in the entire configuration space \(X\) (Line 1 in Algorithm 3). A space greedy reduction strategy is executed when \(x_{new}\) is successfully added to the tree, which is shown in Algorithm 4. For ease of description, the configuration space is denoted as the first \(OriginalSpace\). When a node \(x_{new}\) is successfully added to the tree, the \(OriginalSpace\) will be reduced (Lines 1-2 in Algorithm 4). The specific process is to take \(x_{new}\) as the boundary point of the new sampling space and use the boundary point as the benchmark to divide the \(OriginalSpace\) in each dimension to obtain a subspace containing the goal region. This subspace will be used as the space for the next random sampling and denoted as \(NextSpace\). In the next sampling, this \(NextSpace\) will replaced by \(OriginalSpace\) (Lines 3-6 in Algorithm 4). At this time, the sampling space completes a reduction. After each sampling space is reduced, record the \(GapSpace\) between \(NextSpace\) and the \(OriginalSpace\), where \(GapSpace\) is defined as Equation (1):  
\[GapSpace=OriginalSpace\setminus(OriginalSpace\cap NextSpace) \tag{1}\]  
As the number of space reductions increases, will generate \(N\)\(GapSpace\), denoted as \(Gap_{1},Gap_{2}\ldots Gap_{N}\). Ideally, the sampling space will gradually approach the goal region as the number of sampling increases, but this situation is often not practical. When the random tree expansion with random sampling fails in the \(OriginalSpace\), it means that the current space has failed to be reduced, and the space to sample will fall back to the \(GapSpace\) (\(Gap_{N}\)) nearest to the \(OriginalSpace\) (Line 8 in Algorithm 4). Specifically, when executing this function, sampling will first take place in the \(GapSpace\) and perform multiple times to provide more node expansion options for the next space reduction. When the specified sampling times are reached in the \(GapSpace\), forward to the space where the space reduction failed, that is, the \(OriginalSpace\) for sampling. If the expansion is successful after sampling, the random tree continues to expand according to the above reduction strategy. If the expansion fails, fall back to the previous \(GapSpace\) (\(Gap_{N-1}\)) sampling of the \(GapSpace\) (\(Gap_{N}\)). After sampling multiple times, forward to the \(GapSpace\) (\(Gap_{N}\)), sample again, and finally, forward to the \(OriginalSpace\) for sampling. If the reduction still fails, continue to fall back to sampling in more outer \(GapSpace\), and then sample in the next \(GapSpace\) of each \(GapSpace\) in turn. When fall back to the first \(GapSpace\) sampling, namely \(Gap_{1}\), the random tree generated by RJ-RRT in the configuration space is like the Basic- RRT. ```
1:\(OriginalSpace=ConfigurationSpace\)
2:\(x_{rand}\leftarrow Sample(OriginalSpace)\)
3:if\(FreeCollision(x_{rand},x_{near})\)then
4:\(NextSpace\gets Reduce(x_{rand},X_{goal})\)
5:\(GapSpace\gets Reduce(OriginalSpace,NextSpace)\)
6:\(OriginalSpace=NextSpace\)
7:else
8:\(x_{rand}\leftarrow BackwithForwardSample(GapSpace)\)
9:endif
```  
**Algorithm 4** GreedSpaceSampling  
Take Figure 2 as an example. Firstly, \(A\) is the configuration space and the first \(OriginalSpace\). After the sampling and steering function, the newly added node is \(P1\). The sampling space is reduced as the random tree expands, through \(P1\) formed new sampling space \(B\).