# Hybrid A-Star Path Planning Method Based on Hierarchical Clustering and Trichotomy
## 1 Introduction  
In recent years, the rapid development of autonomous driving technology has greatly improved traffic safety and efficiency. Autonomous driving technology mainly includes positioning navigation, environmental perception, decision-making planning, and tracking control [1]. Decision-making planning includes behavioral decision-making, global path planning, and local path planning. Global path planning is the process of calculating a safe and efficient driving path from a given starting point to a destination [2]. Many scholars have conducted research on global path planning for autonomous vehicles [3]. Common methods of global path planning include graph-based algorithms [4; 5; 6], probability-sampling-based algorithms [7; 8; 9], and intelligent-based algorithms [10; 11; 12]. The Hybrid A-star algorithm belongs to graph-based algorithms, and it is an improvement and development of the A-star algorithm. It overcomes the disadvantage of the A-star algorithm that the expanded nodes must fall on the grid center and considers vehicle kinematic constraints [13]. The planned path is continuous and smooth, making it highly suitable for autonomous vehicles. Many scholars have conducted extensive research to address the incompleteness and suboptimality of the Hybrid A-star algorithm. [PERSON] et al. [14] proposed an improved A-star algorithm and map local scaling technique to solve the problem of non-optimal and inaccurate paths in the path planning process. Compared with traditional methods, their proposed method reduces the time by 23% and the path length by 21%. [PERSON] et al. [15] proposed a hierarchical motion planning method based on improved hybrid A-star algorithm and time-elastic band algorithm. By modifying the collision detection process and introducing the map guide cost, the search efficiency is accelerated. The improved hybrid A-star algorithm can quickly respond to environmental changes. The proposed algorithm can effectively solve the problem of vehicle lateral motion planning in conventional scenarios. [PERSON] et al. [16] proposed a multi-stage Hybrid A-star algorithm to address narrow passage problems. The Hybrid A-star algorithm generates a coarse path, which is then converted into a rough trajectory with an additional time-optimal speed profile and serves as the initial guess input for numerical optimization layers. The multi-stage Hybrid A-star algorithm significantly outperforms existing planners. [PERSON] et al. [17] addressed the issue of collisions at corners due to system errors by proposing an improved Reeds-Shepp method to enhance the safety of the Hybrid A-star algorithm. Fine-tuning of primitive actions during the forward search stage leads to smoother paths, reducing collision risk costs and the number of turning points by around 20% in the improved approach. [PERSON] et al. [18] proposed an improved Hybrid A-star algorithm by enhancing the heuristic function and designing obstacle penalty functions to proactively avoid obstacles, preventing the algorithm from becoming stuck in local optima, especially in U-shaped obstacles. The improved Hybrid A-star path planning algorithm exhibits high planning efficiency, safety performance, and path smoothness. [PERSON] et al. [19] integrated CCRS curve filtering with mining area scenarios to enhance the applicability of the Hybrid A-star algorithm. Segmented spline curves based on quadratic programming are utilized for path smoothing. The proposed method significantly improves the applicability of the traditional Hybrid A-star algorithm in searching paths and achieves a 10-fold increase in smoothing efficiency compared to traditional discrete point smoothing methods. [PERSON] et al. [20] proposed an improved Hybrid A-star path planning algorithm tailored to tight parking scenarios, efficiently generating safe parking paths by swapping the starting and target points of the path. The proposed reverse Hybrid A-star algorithm reduces the expansion of invalid nodes during a path search, enhancing the real-time performance of path planning.