An Efficient Improved Bidirectional Hybrid A* Algorithm for Autonomous Parking in Narrow Parking Slots

To address the computational-efficiency bottlenecks of Hybrid A* and its bidirectional variant in long-distance parking and narrow-slot scenarios, an improved bidirectional Hybrid A* algorithm is presented. First, the cohesion cost is reformulated in a vector-space representation. Distance and heading-consistency terms are evaluated using dot products, which eliminates trigonometric operations and reduces the overhead of node evaluation. Second, an RS (Reeds–Shepp) cost template is constructed on a sparse grid of key nodes. Neighborhood costs are approximated with Euclidean-distance correction. In addition, a geometry reachability-based trigger is designed for analytic RS connections to avoid redundant analytic linking and unnecessary RS curve computations. Third, a KD-tree spatial index is introduced to accelerate nearest-neighbor queries in the Voronoi potential field, and vehicle corner coordinates are updated in a vectorized manner to improve the efficiency of potential-field evaluation. Simulation results in parallel and perpendicular parking show that, compared with the baseline bidirectional Hybrid A* algorithm, RS computations are reduced by 98.7% and 97.8%, respectively, while total planning time is shortened by 63.2% and 57.5%, with stable path quality. These results indicate that the proposed method effectively mitigates the dominant computational costs of bidirectional Hybrid A* in complex parking tasks and improves the efficiency and real-time performance of automatic parking path planning.