# Efficient Path Planning Based on Dynamic Bridging Rapidly Exploring Random Tree
## 4 Methodology
### Dynamic Sampling Strategy  
To overcome the dilemma of the slow expansion speed of the tree structure when the traditional RRT-Connect algorithm deals with high-density environments and areas with many obstacles, an innovative dynamic sampling strategy based on node expansion speed is proposed. In each iteration cycle, the expansion speed of each node is meticulously calculated. This is an insightful metric that accurately reflects the expansion of the search tree in a specific area, which is positively correlated with the priority of the node in the search process. In each iteration, the node with the most lethargic expansion speed \(x_{slowest}\) is selected to generate a batch of additional sample points \(N\) around it, taking the expansion speed (expandSpeed) as a key evaluation criterion. This unique strategy significantly reduces the ineffective sampling points caused by random sampling. Particularly when the robot is in a dense environment and trapped in a local minimum, the tree's growth can be steered by tweaking the node generation range, allowing the robot to quickly leave the dangerous area. This strategy not only greatly improves the efficiency of the algorithm, but also enhances its adaptability to complex environments. It is hypothesized that there is a collision-free path from the start point to the target point. Even if this path is not located in the initial iteration, the algorithm will still select the node with the slowest expansion speed according to the rules (Algorithm 1) and take this node as the center to construct a sector with a certain radius. Within this sector, the algorithm will generate a series of sub-nodes, and then enter the next round of iteration. In Figure 3, yellow nodes represent failure to pass the collision detection, and green nodes represent successful passage. The newly generated nodes in the figure are crucial for connecting the start and target points. Generating additional sample points can be regarded as an efficient optimization strategy, which aims to further improve the execution efficiency of the algorithm on an existing basis. In each iteration cycle, the algorithm first tries to execute normal extension steps (Algorithm 1, steps 3-14). Only when the normal extension steps fail to find the path, and the set size of the target point is smaller than the set size of the start point (i.e., the tree range starting from the target point is still relatively small), does the algorithm need to generate additional sample points at the node with the slowest expansion speed to accelerate the expansion of the tree. This implies that, barring the inability to pinpoint unexplored regions, additional sampling will not be conducted, but regular search steps will continue to be executed. Figure 3: Generate new nodes within the slowest node region. This method achieves effective management of the search range, allowing us to reasonably allocate and optimize unexplored areas while ensuring efficiency, avoiding invalid searches and waste of resources, and further improving the efficiency and effects of path planning. The steps for Dynamic Sampling are as follows (Algorithm 3):  
```
0: number of extra samples \(N_{e}\), the slowest expand node \(X_{se}\), extra samples \(S_{e}\), tree of samples \(T_{s}\)
1: Initialize \(N_{e}\gets N\)
2:if\(X_{se}\
eq NULL\)then
3:\(N_{e}\leftarrow\textit{StaticCast}(N_{e})\)
4:\(S_{e}\leftarrow\textit{GenerateExtraSamples}(N_{e})\)
5:for each sample \(X\) in \(S_{e}\)do
6:if\(\
eg IsAny\textit{ObstadelnPath}(X)\)then
7: Insert \(X\) into \(T_{s}\)
8:endif
9:endfor
10:else
11: skip to the next iteration
12:endif
```  
**Algorithm 3** Dynamic Sampling  
Initialize \(N_{e}\gets N\): The number of dynamic sampling points is first set to \(N\). This is the initial setting for dynamic sampling, preparing for subsequent additional sampling.