Autonomous Parking Trajectory Planning With Tiny Passages: A Combination of Multistage Hybrid A-Star Algorithm and Numerical Optimal Control

Abstract

This paper introduces an autonomous parking trajectory planning method in an unstructured environment with narrow passages. The proposed hierarchical trajectory planner consists of a graph search layer and a numerical optimal control layer. The contribution mainly lies in the graph search layer, wherein a multistage hybrid A* algorithm is proposed to handle narrow passages formed by obstacles in the cluttered environment. In the multistage hybrid A* algorithm, a 2-dim A* search is conducted to find a global route that connects the starting and goal points. Along the derived global route, subtle segments that traverse narrow passages are extracted. Thereafter, the hybrid A* algorithm is used to plan kinematically feasible subpaths that connect the boundary points of each subtle segment. The hybrid A* algorithm is also used to find linking paths that connect adjacent subpaths. Combining all the subpaths and linking paths in a sequence yields a coarse path, which is converted into a coarse trajectory by attaching a time-optimal velocity profile to it. The coarse trajectory is fed into the numerical optimization layer as the initial guess. Simulation results indicate that the hierarchical trajectory planner runs much faster than prevalent ones in dealing with unstructured environments with narrow passages.

Keywords

• Autonomous parking
• hybrid A* algorithm
• optimal control
• trajectory planning