# 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 path planning for different algorithms on map 2 is illustrated in Figure 7. The cumulative changes in heading angle for the HC-Hybrid A-star, Dic-HC-Hybrid A-star, and Tri-HC-Hybrid A-star algorithms are 8.785 radians, 6.813 radians, and 4.242 radians, respectively. The cumulative changes in heading angle for the Dic-HC-Hybrid A-star algorithm and Tri-HC-Hybrid A-star algorithm are increased by 22.45% and 51.71%, respectively, compared to the HC-Hybrid A-star algorithm. The numbers of expanded nodes for the HC-Hybrid A-star algorithm, Dic-HC-Hybrid A-star algorithm, and Tri-HC-Hybrid A-star algorithm are 45, 58, and 67, respectively. The numbers of expanded nodes for the

Figure 6: Map 1 path planning. (**a**) HC-Hybrid A-star algorithm path in setup 1; (**b**) Dic-HC-Hybrid A-star path in setup 1; (**c**) Tri-HC-Hybrid A-star algorithm path in setup 1; (**d**) HC-Hybrid A-star algorithm path in setup 2; (**e**) Dic-HC-Hybrid A-star algorithm path in setup 2; (**f**) Tri-HC-Hybrid A-star algorithm path in setup 2. The path planning for different algorithms on map 3 is depicted in Figure 8. The cumulative changes in heading angle for the HC-Hybrid A-star algorithm, Dic-HC-Hybrid A-star algorithm, and Tri-HC-Hybrid A-star algorithm are 17.146 radians, 14.128 radians, and 8.475 radians, respectively. The cumulative changes in heading angle for the Dic-HC-Hybrid A-star algorithm and Tri-HC-Hybrid A-star algorithm are increased by 17.60% and 50.57%, respectively, compared to the HC-Hybrid A-star algorithm. The numbers of expanded nodes for the HC-Hybrid A-star algorithm, Dic-HC-Hybrid A-star algorithm, and Tri-HC-Hybrid A-star algorithm are 90, 99, and 99, respectively. Both the Dic-HC-Hybrid A-star algorithm and Tri-HC-Hybrid A-star algorithm have an increased number of expanded nodes by 10% compared to the HC-Hybrid A-star algorithm. Figure 9 shows the statistical cumulative change in heading angle and the number of expanded nodes. Table 2 provides a statistical analysis of the planned path lengths under different algorithms. For setup 1 of map 1, the Dic-HC-Hybrid A-star algorithm and Tri-HC-Hybrid A-star algorithm exhibit reductions of -2.77% and 2.73%, respectively, in planned path length compared to the HC-Hybrid A-star algorithm. For setup 2, these algorithms demonstrate reductions of -2.84% and 0.90%, respectively. Under map 2, the Dic-HC-Hybrid A-star algorithm and Tri-HC-Hybrid A-star algorithm show reductions of 0.62% and 2.04%, respectively. Similarly, under map 3, these algorithms exhibit reductions of 5.53% and 9.17%, respectively, compared to the HC-Hybrid A-star algorithm. Figure 8: Map 3 path planning. (**a**) HC-Hybrid A-star algorithm path; (**b**) Dic-HC-Hybrid A-star algorithm path; (**c**) Tri-HC-Hybrid A-star algorithm path. Figure 7: Map 2 path planning. (**a**) HC-Hybrid A-star algorithm path; (**b**) Dic-HC-Hybrid A-star algorithm path; (**c**) Tri-HC-Hybrid A-star algorithm path. Comparing the cumulative change in heading angle, number of expanded nodes, and planned path length under different algorithms across two states produced the following insights: The Dic-HC-Hybrid A-star algorithm performs poorer than the HC-Hybrid A-star algorithm in both states of map 1, with all three indexes showing suboptimal results. However, its performance improves compared to the HC-Hybrid A-star algorithm in maps 2 and 3, although the improvement in all three indexes is not significant. The Tri-HC-Hybrid A-star algorithm consistently outperforms both the HC-Hybrid A-star and Dic-HC-Hybrid A-star algorithms in terms of cumulative change in heading angle and planned path length across all states. This confirms that the proposed Tri-HC-Hybrid A-star algorithm can generate shorter and smoother paths. In order to prove the effectiveness of the proposed algorithm, the RRT algorithm was used to carry out global path planning for the two setups of map 1. In Figure 10, a node expansion diagram, original path diagram, stretched path diagram, and smoothed path diagram of the RRT algorithm under two setups are shown.