Hybrid A-Star Path Planning Method Based on Hierarchical Clustering and Trichotomy

Abstract

Aiming to improve on the poor smoothness and longer paths generated by the traditional Hybrid A-star algorithm in unstructured environments with multiple obstacles, especially in confined areas for autonomous vehicles, a Hybrid A-star path planning method based on hierarchical clustering and trichotomy is proposed. This method first utilizes the Prewitt compass gradient operator (Prewitt operator) to identify obstacle boundaries and discretize boundaries. Then, it employs a single linkage hierarchical clustering algorithm to cluster obstacles based on boundaries. Subsequently, the clustered points are enveloped using a convex hull algorithm, considering collision safety for vehicle expansion. This fundamentally addresses the ineffective expansion issue of the traditional Hybrid A-star algorithm in U-shaped obstacle clusters. Finally, the expansion strategy of Hybrid A-star algorithm nodes is improved based on the trichotomy method. Simulation results demonstrate that the improved algorithm can search for a shorter and smoother path without significantly increasing the computational time.

Keywords

• autonomous vehicle
• path planning
• hierarchical clustering
• Hybrid A-star algorithm