A Multi-Heuristic Search-based Motion Planning for Autonomous Parking
Planning is a crucial component of autonomous vehicle con-trol. It is responsible for finding a collision-free sequence of states that take the vehicle towards its goal. In unstructured environments like parking lots or construction sites, due to the large search-space and kinodynamic constraints of the vehicle, real-time planning is challenging. Several state-of-the-art solutions utilize heuristic search-based planning algorithms. However, they heavily rely on the quality of the single heuristic function used to guide the search, and they are not capable to achieve reasonable performance, resulting in unnecessary delays in the response of the vehicle. This work solves the planning problem by adopting a Multi-Heuristic Search approach, that enables the use of multiple heuristic functions and their advantages to capture different complexities of a given search space. Based on our knowledge, this approach was not used for this domain so far. For this purpose, multiple admissible and non-admissible heuristic functions are defined, original Multi-Heuristic A* Search was extended for bidirectional use and dealing with hybrid continuous-discrete search space and a mechanism for adapting scale of motion primitives is introduced. To demonstrate the advantage, Multi-Heuristic A* algorithm is benchmarked against a very popular heuristic search-based algorithm, Hybrid A*. The Multi-Heuristic A* algorithm outperformed Hybrid A* in terms of computation efficiency and motion plan (path) quality.