# Hybrid A-Star Path Planning Method Based on Hierarchical Clustering and Trichotomy
## 3 Hybrid A-Star Algorithm and Trichotomy Search
### Trichotomy Node Expansion Method
Table 3 presents data for the RRT algorithm and the Tri-HC-Hybrid A-star algorithm. Under setup 1, the RRT algorithm expands 757 nodes, resulting in a smoothed path length of 243.792 m and a cumulative change in heading angles of 6.914 radians. For the same setup, the Tri-HC-Hybrid A-star algorithm expands 65 nodes, resulting in a smoothed path length of 185.114 m and a cumulative change in heading angles of 3.208 radians. The Tri-HC-Hybrid A-star algorithm reduces the number of node expansions by 91.41% compared to the RRT algorithm, decreases the path length by 24.07%, and reduces the cumulative change in heading angles by 53.60%. Under setup 2, the RRT algorithm expands 860 nodes, resulting in a smoothed path length of 267.416 m and a cumulative change in heading angles of 4.126 radians. Conversely, the Tri-HC-Hybrid A-star algorithm expands 72 nodes, resulting in a smoothed path length of 196.475 m and a cumulative change in heading angles of 8.036 radians. The Tri-HC-Hybrid A-star algorithm decreases the number of node expansions by 91.63% compared to the RRT algorithm, and decreases the path length by 26.53%, but increases the cumulative change in heading angles by 94.76%. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Indexes**} & \multirow{2}{*}{**Maps**} & **HC-Hybrid** & **Dic-HC-Hybrid** & **Tri-HC-Hybrid** \\  & & **A-Star** & **A-Star** & **A-Star** \\ \hline \multirow{3}{*}{Planned path length (m)} & Map 1:Setup 1 & 190.313 & 195.583 & 185.114 \\  & Map 1:Setup 2 & 198.256 & 203.883 & 196.475 \\  & Map 2 & 151.388 & 150.452 & 148.295 \\  & Map 3 & 275.262 & 260.032 & 250.029 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Planned path lengths under different maps. Figure 9: The statistical analysis of the cumulative change in the heading angle and number of expanded nodes. (**a**) Cumulative change in the heading angle under different maps. (**b**) Number of expanded nodes under different maps. Figure 10: RRT algorithm in different setups in Map 1. (**a**) Setup 1: RRT algorithm node expansion diagram; (**b**) Setup 1: original path of the RRT algorithm; (**c**) Setup 1: stretched path of the RRT algorithm; (**d**) Setup 1: smoothed path of the RRT algorithm; (**e**) Setup 2: RRT algorithm node expansion diagram; (**f**) Setup 2: original path of the RRT algorithm; (**g**) Setup 2: stretched path of the RRT algorithm; (**h**) Setup 2: smoothed path of the RRT algorithm. Through comparison, it is evident that the Tri-HC-Hybrid A-star algorithm generates shorter paths with fewer node expansions compared to the RRT algorithm. Therefore, the proposed Tri-HC-Hybrid A-star algorithm is effective. To verify the practicability of the algorithm in different scenarios, the algorithm was tested on different test maps. Figure 11 shows the paths planned by the HC-Hybrid A-star algorithm, Dic-HC-Hybrid A-star algorithm, and Tri-HC-Hybrid A-star algorithm on the four different test maps. The sums of heading angle changes, the numbers of nodes expanded, and the planned path lengths of different test maps are sorted in Table 4. It can be seen from the table that the planned path of the Tri-HC-Hybrid A-star algorithm is the shortest and smoothest among different test maps. ## 5 Conclusions

This paper addresses the issues of poor smoothness and longer paths in the traditional Hybrid A-star algorithm for the path planning of autonomous vehicles in small-area, multi-obstacle unstructured scenarios. It proposes a Hybrid A-star path planning method