# Hybrid A-Star Path Planning Method Based on Hierarchical Clustering and Trichotomy
## 1 Introduction
[PERSON] et al. [21] introduced an enhanced Hybrid A-star algorithm with safety-enhanced and efficiency-enhanced designs, integrating Voronoi diagrams into the path search stage to further consider path safety. The efficiency-enhanced design proposes a multi-stage dynamic optimization strategy. The paths generated by the improved algorithm are safer and significantly improve the search efficiency. [PERSON] et al. [22] addressed efficiency and safety concerns in path planning by proposing an enhanced Hybrid A-star algorithm. They introduced a distance penalty function into the heuristic function, constructing safe corridors to guide mobile robots away from obstacles. The improved Hybrid A-star algorithm enhances the path planning efficiency, resulting in safer planned paths. [PERSON] et al. [23] proposed an optimization solution to address the slow search time of the Hybrid A-star algorithm by integrating a bidirectional search algorithm and the Hybrid A-star algorithm. They optimized the bidirectional search algorithm using grid methods and improved the node search process of the Hybrid A-star algorithm. The integrated algorithm can shorten the search time. [PERSON] et al. [24] optimized the Hybrid A-star algorithm based on the minimum jerk to address the issue of discomfort. They conducted algorithmic research on grid maps and proposed a \"corridor\" automatic adjustment strategy to prevent trajectory collisions caused by optimization. The optimized trajectory has a smaller curvature. This paper addresses the issues of poor smoothness and longer paths in Hybrid A-star algorithm navigating through small-scale, multi-obstacle, and unstructured scenarios. A solution is proposed using a Hybrid A-star algorithm based on single linkage hierarchical clustering and trichotomy searching, fundamentally resolving the ineffective expansion problem near U-shaped obstacle clusters and improving the node expansion approach of the Hybrid A-star algorithm. The enhanced algorithm is capable of searching for a shorter and smoother path without significantly increasing the computational complexity. The main contributions of this paper are as follows:  
(1) An obstacle hierarchical clustering method is proposed, which uses the Prewitt operator to identify an obstacle boundary and clusters the obstacles based on the single linkage hierarchical clustering algorithm after discretization of a boundary, fundamentally solving the problem of the ineffective expansion of the Hybrid A-star algorithm in U-shaped obstacle groups. (2) An obstacle expansion method considering vehicle collision safety is proposed. The point set after obstacle clustering is enveloped by a convex hull algorithm, and the convex hull expansion is processed considering vehicle collision safety. The function of expansion is to ensure vehicle safety. (3) A path planning method of the Hybrid A-star algorithm based on the expansion of the trichotomy is proposed to solve the problem of poor smoothness and a long path planned. The remaining sections of the article are organized as follows: Section 2 introduces the single linkage hierarchical clustering algorithm. Section 3 presents the Hybrid A-star algorithm and trichotomy search. Section 4 describes the simulation results and discussions. Section 5 concludes the paper.