# Hybrid A-Star Path Planning Method Based on Hierarchical Clustering and Trichotomy
## 3 Hybrid A-Star Algorithm and Trichotomy Search
### Trichotomy Node Expansion Method
\[X_{i} =X_{R_{i}}+|R_{i}|\text{cos}\,\gamma_{i} \tag{19}\] \[Y_{i} =Y_{R_{i}}+|R_{i}|\text{sin}\,\gamma_{i}\] (20) \[\theta_{i}=\theta+\delta_{i} \tag{21}\]  
Combining the vehicle's single-track kinematic model [30] with Equations (14)-(21) allows for the calculation of coordinates and heading angles for all expandable nodes within the trichotomy region. The single-track kinematic model constrains the vehicle's minimum turning radius, thereby imposing constraints on the curvature of the planned path to ensure smooth vehicle passage. After reaching the specified number of iterations, the trichotomy expansion method selects the node with the minimum evaluation function value for planning execution. The pseudocode for the Hybrid A-star algorithm improved by trichotomy expansion (Algorithm 1) is as follows:  
```
1:Input : \(N_{start}\), \(N_{goal}\), \(S\), \(D_{\text{s}ift}\), \(\alpha\), \(\beta\), Iterations. 2:Initialize: \(N_{start}\),\(f(n)\). 3: While \(N_{new}\
eq N_{goal}\)
4: Delete \(\text{min}/(n)\) in open list as \(N_{parent}\). 5:for\(i=0\): 3
6:if no collision
7: Create \(N_{lemporary}\), calculate \(g(n)\) with Equation (13), update \(f(n)\), Mark as 1. 8:end
9:end
10:if [1,1,1] & \(N_{middle}\) is \(\text{min}/(n)\)
11: Expansion areas are \(A_{\text{left}}\) and \(A_{right}\). 12:if \(A_{\text{left}}\) and \(A_{right}\) are no collision

## 4 Simulation Results and Discussion

To validate the research conducted, the Hybrid A-star algorithm was implemented using MATLAB software (version number 2020a). The simulation used a laptop computer, with the specific configuration including the following: the CPU is an Intel Core i7-8750H, the RAM is 16 GB, and the graphics card is an NVIDIA GEFORCE GTX 1080. The map used was a small area with multiple obstacles in an unstructured scene measuring \(150\) m \(\times\) 200 m, with a grid map discretization size of 1 m. First, simulations were performed using the Hybrid A-star algorithm and the Hierarchical Clustering-based Hybrid A-star algorithm (HC-Hybrid A-star algorithm) for two different setups. The measurement method of the path length used was to discretize the path obtained from the backtracking node, and the discretized distance was 1 m. By summing the discretized Euclidean distance between the points, the path length could be obtained. As shown in Figure 5a,c, during the node expansion process of the Hybrid A-star algorithm, even when using the shortest collision-free distance from the endpoint to each grid point planned by the A-star algorithm as the heuristic value, it can still be erroneously directed towards a cluster of U-shaped obstacles, resulting in a significant number of ineffective node expansions and thus reducing planning efficiency. As shown in Figure 5b,d, the HC-Hybrid A-star algorithm fundamentally addresses the issue of ineffective expansions into U-shaped obstacle clusters encountered by the Hybrid A-star algorithm. The computational times, expanded node counts, and planned path lengths of the two algorithms under different setups are shown in Table 1. In setup 1, the computational time of the Hybrid A-star algorithm is 18.738 s, while the computational time of the HC-Hybrid A-star algorithm is 13.973 s. In setup 2, the computational time of the Hybrid A-star algorithm is 322.768 s, while the computational time of the HC-Hybrid A-star algorithm is 15.194 s. In setup 1, the expanded node count of the Hybrid A-star algorithm is 130, while the expanded node count of the HC-Hybrid A-star algorithm is 49. In setup 2, the expanded node count of the Hybrid A-star algorithm is 2686, while the expanded node count of the HC-Hybrid A-star algorithm is 49.