# Hybrid A-Star Path Planning Method Based on Hierarchical Clustering and Trichotomy
## 3 Hybrid A-Star Algorithm and Trichotomy Search
### Trichotomy Node Expansion Method
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Indexes** & **Test Maps** & \begin{tabular}{c} **HC-Hybrid** \\ **A-Star** \\ \end{tabular} & \
\begin{tabular}{c} **Dic-HC-Hybrid** \\ **A-Star** \\ \end{tabular} &
\begin{tabular}{c} **Tri-HC-Hybrid** \\ **A-Star** \\ \end{tabular} \\ \hline \multirow{3}{*}{Sum of heading angle} & Test map 1 & 11.756 & 12.231 & 4.775 \\  & Test map 2 & 7.215 & 6.215 & 4.265 \\ \multirow{3}{*}{(rad)} & Test map 3 & 11.258 & 11.263 & 8.381 \\  & Test map 4 & 5.434 & 6.141 & 3.840 \\ \hline \multirow{3}{*}{Expanded node count} & Test map 1 & 57 & 94 & 76 \\  & Test map 2 & 64 & 87 & 87 \\ \cline{1-1}  & Test map 3 & 69 & 91 & 87 \\ \cline{1-1}  & Test map 4 & 59 & 74 & 74 \\ \hline \multirow{3}{*}{Planned path length (m)} & Test map 1 & 227.429 & 226.361 & 217.189 \\ \cline{1-1}  & Test map 2 & 228.090 & 225.976 & 225.080 \\ \cline{1-1} \cline{2-5}  & Test map 3 & 262.570 & 260.749 & 254.267 \\ \cline{1-1} \cline{2-5}  & Test map 4 & 207.299 & 205.664 & 205.138 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Different test maps’ data comparison. Figure 11: Different test maps’ plan path diagrams. (**a**) Test map 1: HC-Hybrid A-star algorithm path; (**b**) test map 1: Dic-HC-Hybrid A-star algorithm path; (**c**) test map 1: Tri-HC-Hybrid A-star algorithm path; (**d**) test map 2: HC-Hybrid A-star algorithm path; (**e**) test map 2: Dic-HC-Hybrid A-star algorithm path; (**f**) test map 2: Tri-HC-Hybrid A-star algorithm path; (**g**) test map 3: HC-Hybrid A-star algorithm path; (**h**) test map 3: Dic-HC-Hybrid A-star algorithm path; (**i**) test map 3: Tri-HC-Hybrid A-star algorithm path; (**j**) test map 4: HC-Hybrid A-star algorithm path; (**k**) test map 4: Dic-HC-Hybrid A-star algorithm path. based on a single linkage hierarchical clustering algorithm and trichotomy expansion. To fundamentally solve the problem of invalid expansion near U-shaped obstacle clusters in the Hybrid A-star algorithm, obstacles are hierarchically clustered, and the convex hull algorithm is used for envelope construction. A comparison of simulation results between the Hybrid A-star algorithm and the HC-Hybrid A-star algorithm shows that, after clustering obstacles, the algorithm successfully navigates around U-shaped obstacle clusters, effectively reducing the number of expansion nodes while improving the planning efficiency. In order to enhance path smoothness and shorten the path length, the expansion strategy of nodes in the HC-Hybrid A-star algorithm is improved based on trichotomy expansion. A comparison between the proposed algorithm, the HC-Hybrid A-star algorithm, the Dic-HC-Hybrid A-star algorithm, and the RRT algorithm using simulated data on different maps reveals that the proposed Tri-HC-Hybrid A-star algorithm can generate shorter and smoother paths. Conceptualization, T.C. ; methodology, T.C. ; software, T.C. ; writing-- original draft preparation, T.C. ; writing--review and editing, G.T. ; supervision, G.T. All authors have read and agreed to the published version of the manuscript. This research received no external funding. Not applicable. The data presented in this study are available on request from the corresponding author. The data are not publicly available due to privacy restrictions. The authors declare no conflicts of interest. ## References

* (1) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] A review of the development status of motion control for unmanned vehicles. _[PERSON]. Mech. Eng._**2020**, _56_, 127-143. [CrossRef]
* (2) [PERSON]; [PERSON] Classical and heuristic approaches for mobile robot path planning: A survey. _Robotics_**2023**, _12_, 93. [CrossRef]
* (3) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Diagonal parking path planning method based on predefined geometry sets. _China J. Highu. Transp._**2021**, _34_, 1-11. [CrossRef]
* (4) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Mobile robot path planning based on improved A*-DWA algorithm. _Comput. Integr. Manuf. Syst._**2024**, _30_, 158-171.