Guided Hybrid A-star Path Planning Algorithm for Valet Parking Applications

Abstract

Throughout the last decades, the Robotics Community has influenced the Autonomous Vehicles field in multiple different areas ranging from Scene Understanding and Decision Making to Vehicle Control and Optimal Path Planning. Existing path planning algorithms such as A-star, Dijkstra and Graph-based approaches, although providing good optimal path approximations, are suffering from high-runtimes to convergence. This paper presents an innovative and computationally efficient approach of fusing the well-known Hybrid A-star search engine with the Visibility Diagram planning to find the shortest possible non-holonomic path in a hybrid (continuous-discrete) environment for valet parking. The primary novelty of our method stems from two points: at first, we use the Visibility Diagram to introduce an improved and application-aware cost function for the Hybrid A-star algorithm, and then the derived shortest path is used to provide the correct waypoints for the Hybrid A-star to plan the optimum path in regard to the non-holonomic constraints. The method has been extensively tested and proven to up to 40% (20% in average) faster than Hybrid A-star algorithm.