# Hybrid A-Star Path Planning Method Based on Hierarchical Clustering and Trichotomy
## 3 Hybrid A-Star Algorithm and Trichotomy Search
### Trichotomy Node Expansion Method
In setup 1, the planned path length of the Hybrid A-star algorithm is 189.739 m, while the planned path length of the HC-Hybrid A-star algorithm is 190.313 m. In setup 2, the planned path length of the Hybrid A-star algorithm is 197.554 m, while the planned path length of the HC-Hybrid A-star algorithm is 198.256 m. In the two different setups, the computational time of the HC-Hybrid A-star algorithm is reduced by 25.43% and 95.29%, respectively, compared to the Hybrid A-star algorithm. The expanded node count is reduced by 62.31% and 98.18%, respectively. Although the HC-Hybrid A-star algorithm shows significant improvements in the computational time and expanded node count, there is only a slight change in the planned path length. This is because the HC-Hybrid A-star algorithm only clusters obstacles, fundamentally addressing the issue of ineffective expansions within U-shaped obstacle clusters, without modifying the structure of the Hybrid A-star algorithm. The Hybrid A-star algorithm typically expands three nodes per iteration during usage. Many scholars, considering path optimality and completeness, have increased the number of nodes expanded per iteration to five in the Hybrid A-star algorithm, resulting in lower computational planning efficiency. The improved Hybrid A-star algorithm using trichotomy and dichotomy methods expands four nodes per iteration, leading to increased computational complexity compared to the Hybrid A-star algorithm that expands three nodes per iteration. To investigate the improvement of the Tri-HC-Hybrid A-star algorithm over the Hybrid A-star algorithm that expands three nodes per iteration, simulations were conducted on different maps. In Figure 6, the path planning maps for different algorithms are shown under two setups for map 1. For setup 1, the accumulated heading angle changes for the HC-Hybrid A-star, Dic-HC-Hybrid A-star, and Tri-HC-Hybrid A-star algorithms are 6.785 radians, \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Indexes** & **Setups** & \begin{tabular}{c} **Hybrid** \\ **A-Star** \\ \end{tabular} & \
\begin{tabular}{c} **HC-Hybrid** \\ **A-Star** \\ \end{tabular} &
\begin{tabular}{c} **Improvement** \\ \end{tabular} \\ \hline \multirow{2}{*}{Computational time (s)} & Setup 1 & 18.738 & 13.973 & 25.43\% \\  & Setup 2 & 322.768 & 15.194 & 95.29\% \\ \hline \multirow{2}{*}{Expanded node count} & Setup 1 & 130 & 49 & 62.31\% \\  & Setup 2 & 2686 & 49 & 98.18\% \\ \hline \multirow{2}{*}{Planned path length (m)} & Setup 1 & 189.739 & 190.313 & \(-\)0.30\% \\  & Setup 2 & 197.554 & 198.256 & \(-\)0.36\% \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Data of two algorithms in different setups. Figure 5: Path planning in different setups. (**a**) Hybrid A-star algorithm path in setup 1; (**b**) HC-Hybrid A-star algorithm path in setup 1; (**c**) Hybrid A-star algorithm path in setup 2; (**d**) HC-Hybrid A-star algorithm path in setup 2. 8.779 radians, and 3.208 radians, respectively. The percentage increase in accumulated heading angle changes for the Dic-HC-Hybrid A-star algorithm and Tri-HC-Hybrid A-star algorithm compared to the HC-Hybrid A-star algorithm are \(-\)29.39% and 52.72%, respectively. The number of expanded nodes for the HC-Hybrid A-star algorithm, Dic-HC-Hybrid A-star algorithm, and Tri-HC-Hybrid A-star algorithm are 49, 66, and 65, respectively. The percentage increase in expanded nodes for the Dic-HC-Hybrid A-star algorithm and Tri-HC-Hybrid A-star algorithm compared to the HC-Hybrid A-star algorithm are 34.69% and 32.65%, respectively. For setup 2, the accumulated heading angle changes for the HC-Hybrid A-star algorithm, Dic-HC-Hybrid A-star algorithm, and Tri-HC-Hybrid A-star algorithm are 8.756 radians, 11.471 radians, and 8.036 radians, respectively. The percentage increase in accumulated heading angle changes for the Dic-HC-Hybrid A-star algorithm and Tri-HC-Hybrid A-star algorithm compared to the HC-Hybrid A-star algorithm are 30.61% and 46.94%, respectively.