# Efficient Path Planning Based on Dynamic Bridging Rapidly Exploring Random Tree
## 4 Methodology
### Bridge Test  
The Bridge Test is a heuristic method used to assess the likelihood of a sampling point being in the \"bridge\" concept of free space. The core principle of the Bridge Test is based on Voronoi diagram heuristics. Voronoi diagram is a graphical structure that partitions space into several regions, each containing a seed point, and any point within that region is closer to the seed point than to other seed points. In path planning, the Voronoi diagram can help find a path that is as far away from obstacles as possible. The basic idea of the Bridge Test is to identify sampling points located on the edge of the free space Voronoi diagram [35], as these points are more likely to be part of an excellent path. To achieve this, a geometric analysis method is adopted, combining the spatial relationships between the sampling points, nearby obstacles, and auxiliary test points, to determine whether the sampling points align with the conditions of the Voronoi edge. The theoretical concept of the Bridge Test is shown in Figure 2. A passage exists from the A direction to B direction. \(P_{c}\) represents a random sampling point on the map. \(P_{d}\) represents the nearest point in the known tree. \(P_{e}\) and \(P_{f}\) represent newly generated test points in two directions. Bridge Test is an algorithmic test method for quickly recognizing and passing through narrow passages (which we call \"bridges\") in complex environments. As shown in Figure 2, in the test we follow several steps to evaluate whether a new sampling point (\(P_{c}\)) can help find and enter these narrow passages. The steps in the Bridge Test are as follows:  
1. Find the line between the sampled point \(P_{c}\) and the nearest neighbor point \(P_{d}\) in the search tree and calculate angle \(\theta\) of this line with respect to the horizontal. 2. Depending on the angle \(\theta\), the sampling point \(P_{c}\) is offset by a fixed angle in each of the positive and negative directions, thus constructing two predetermined test points \(P_{e}\) and \(P_{f}\) that explore two different directions from \(P_{c}\). 3. Collision detection is used to verify that the path between the test points, \(P_{c}\), \(P_{e}\), \(P_{f}\) is not blocked by obstacles. 4. If the \(P_{c}\)'s path to one of the test points is open (i.e., unobstructed) and the path to the other test points is blocked, this indicates that the \(P_{c}\) is located at the entrance to a potentially narrow channel. 5. \(P_{c}\) is considered to have passed the Bridge Test and will be added to the current search tree. In Figure 2b, there is an unobstructed path from \(P_{c}\) to \(P_{e}\), which means that there are no narrow passages obstructing passage in this direction. On the contrary, the path from \(P_{c}\) to \(P_{f}\) partially enters inside the obstacle. This observation suggests that, if the path from \(P_{c}\) to one test point is blocked by an obstacle while the path to another test point is open, it can be determined that the point \(P_{c}\) passed the Bridge Test. By this means of creating handling points, the tree expansion can enter the narrow passage more quickly. This result suggests that the sampling point may be located on the Voronoi boundary of free space, and therefore has a higher expansion priority. During the search process, this priority allocation helps the algorithm to explore those possible effective paths which lead more efficiently to the target and pushes the nodes into the usually neglected narrow passages with a biasing concept, thus significantly improving search efficiency. Here is the Pseudocode of the Bridge Test (Algorithm 2):  
```
0: sample \(X_{s}\), angle \(\alpha\), angleOffset \(\alpha_{o}\),distance \(d\), testPoint1 \(P_{e}\), testPoint2 \(P_{f}\).