# Hybrid A-Star Path Planning Method Based on Hierarchical Clustering and Trichotomy
## 3 Hybrid A-Star Algorithm and Trichotomy Search
### Trichotomy Node Expansion Method  
The Hybrid A-star algorithm typically expands three new nodes for path planning in each iteration. Increasing the number of nodes expanded per iteration can effectively enhance the smoothness of path planning and reduce the path length. However, uniformly distributing node expansions consume significant computational resources, leading to a decrease in planning efficiency. Considering both node expansion and planning efficiency, this paper proposes an improvement to the node expansion method of the Hybrid A-star algorithm, introducing a trichotomy expansion method (Tri-Hybrid A-star). The resulting Tri-Hybrid A-star algorithm generates shorter and smoother paths. The node expansion method of the Hybrid A-star algorithm is shown in Figure 4a, which can only be expanded by three nodes: maximum left turn, straight, and maximum right turn. Based on the node expansion method of the Hybrid A-star algorithm, the node with the smallest evaluation function value in the maximum left turn, straight, and maximum right turn and its adjacent nodes are selected for the trichotomy expansion. When the set number of iterations is satisfied, the trichotomy expansion ends. The spatial position relationship diagram of the trichotomy expansion method is shown in Figure 4b. By comparing the evaluation functions of the three new nodes expanded by the Hybrid A-star algorithm, the node corresponding to the minimum evaluation function and its neighboring nodes are selected for trichotomy expansion. Initially, the maximum heading angle \(\theta_{max}\) and minimum heading angle \(\theta_{min}\) of the subnodes within the trichotomy region are used as the left and right boundaries for expansion. This yields the steering angle of the vehicle's front wheels corresponding to the parent node, as obtained by Equation (14):  
\[\delta_{i}=\frac{\theta_{max}-\theta_{min}}{3}\times i \tag{14}\]  
where \(\delta_{i}\) represents the front wheel steering angle corresponding to the parent node, with positive values to the left of the heading axis of the parent node and negative values to the right. \(i\) represents the index corresponding to the expansion point, with values ranging from 1 to 3. Figure 4: Node expansion diagram. (**a**) Hybrid A-star algorithm. (**b**) Tri-Hybrid A-star algorithm. Based on the front wheel steering angle obtained from Equation (14), the turning radius corresponding to each expansion point can be calculated according to spatial positional relationships in Equation (15):  
\[R_{i}=\frac{S}{2\text{sin}\frac{\delta_{i}}{2}} \tag{15}\]  
where \(S\) represents the set expansion step length; and \(R_{i}\) denotes the turning radius corresponding to each expansion point, with positive values to the left of the heading axis of the parent node and negative values to the right. Based on the turning radius corresponding to each expansion point, the coordinates of the centers of curvature corresponding to the turning radius can be determined according to Equations (16) and (17):  
\[X_{R_{i}} =X_{p}-R_{i}\text{sin}\,\theta \tag{16}\] \[Y_{R_{i}} =Y_{p}+R_{i}\text{cos}\,\theta \tag{17}\]  
where \(X_{p}\) represents the parent node's x-coordinate; \(Y_{p}\) represents the parent node's y-coordinate; \(X_{R_{i}}\) denotes the x-coordinate of the center; \(Y_{R_{i}}\) denotes the y-coordinate of the center; and \(\theta\) represents the heading angle of the parent node. To obtain the coordinates corresponding to the expansion node, it is necessary to introduce the intermediate variable (Equation (18)), which is an angle. \[\gamma_{i}=\delta_{i}+\text{tan}^{-1}\,\frac{Y_{R_{i}}-Y_{p}}{X_{R_{i}}-X_{p}} \tag{18}\]  
After introducing the intermediate variable, the corresponding transverse and longitudinal coordinates and the corresponding heading angle of the extended node can be calculated according to Equations (19) and (20).