# Efficient Path Planning Based on Dynamic Bridging Rapidly Exploring Random Tree
## 3 Problem Formulation
### Proposed Framework for Path Planning Algorithm  
Like the RRT-Connect algorithm, the DBR-RRT algorithm uses two trees, \(T_{start}\) and \(T_{goal}\), growing correspondingly from the starting state and target state. What differentiates our new algorithm is the use of heuristic sampling and dynamic sampling strategies.  
The DBR-RRT algorithm proposed in this paper is composed of a path search (Bridge Test [34]) strategy. Firstly, DBR-RRT introduces a heuristic method to determine whether a sample point is in the free space \"Bridge\". This method evaluates the expansion value of the sampled point based on the relationship between the auxiliary point's location and obstacles. The tree is only expanded when the Bridge Test concept is passed, to solve the problem of slow search due to extension collision detection. Moreover, DBR-RRT introduces a dynamic sampling strategy based on expansion speed, generating sampling points set around nodes with slower expansion speed. This allows the tree to expand into obstacle-dense areas or areas with complex shapes at a faster rate, thus enhancing the search efficiency. Finally, rapid path smoothing is applied to the path generated by this technique. Through continuous iterations, the original path is optimized to produce a smoother and higher-quality path.  
For initialization, two empty trees are initialized and expanded from the start node and goal node respectively. DynamicRandomNode() is used to generate an adaptive random sampling point. This function considers the current structure of the starting tree \(T_{start}\) and the goal tree \(T_{goal}\), thereby more intelligently choosing sampling points.  
The following is the Pseudocode of the DBR-RRT algorithm (Algorithm 1):  
```
0: start point \(S\), goal point \(G\), obstacle \(O\), vertices and edges of tree \(T_{start}\),\(T_{goal}\),\(V_{start}\),\(E_{start}\),\(V_{goal}\),\(E_{goal}\), random node \(X_{r}\), nearest node \(X_{start}\), new node \(X_{new}\), connect node \(X_{con}\) path \(P\).
1:\((V_{s},E_{a})\leftarrow\{S\},\{\};V_{b}=\{G\};E_{b}=\{\}\)
2:whileLocalPlanning()do
3:\(X_{r}\leftarrow GenerateRandomNode()\)
4:\(X_{near}\gets FindNearestPoint()\)
5:\(X_{new}\gets BridgeTest()\)
6:if\(X_{new}!=NULL\) and \(IsFree(X_{new})\)then
7:\(V_{start}\leftarrow V_{start}\cup\{X_{new}\};E_{start}\gets E_{start}\cup\{(X_{ max},X_{new})\}\)
8:\(UpdateBasedSpeed()\)
9:\(X_{con}\gets FindNearestPoint()\)
10:if\(X_{con}!=NULL\)then
11:\((E_{goal},V_{goal})\gets ConnectTrees()\)
12:ifTreesConnected()then
13:\(P\leftarrow ConstructPath()\)
14:returnPathSmoothing()
15:endif
16:endif
17:endif
18:endwhile
19:if\(V_{goal,size}()<V_{start,size}()\)then
20:\(Sway(V_{start},V_{goal});Sway(E_{start},E_{goal})\)
21:endif
22:\(GenerateExtraSamples()\)
```  
**Algorithm 1**DBR-RRT  
Figure 1: RRT-Connect extension steps. The nodes in \(T_{start}\) are displayed as black nodes, while the nodes in \(T_{goal}\) are displayed as red nodes.  
The algorithm will attempt to identify areas in the search space that have not been fully explored (i.e., where node expansion is slow), and generate sampling points in these areas. In addition, if the starting tree and the goal tree are close to each other in space, the function may be more inclined to generate sampling points in the area between the two trees to increase the chance of tree connection.