Hierarchical Planning for Autonomous Parking in Dynamic Environments

Abstract

This article investigates planning for autonomous parking in a dynamic environment where moving obstacles are present. To fulfill fast planning, we employ a divide-and-conquer approach where path planning with static obstacles and safe motion planning with moving obstacles are solved sequentially. We develop a bi-directional improved A-search guided tree (BIAGT) algorithm to achieve fast path planning by proposing two modifications to node selection and node expansion of the A* algorithm. First, with the simultaneous construction of two trees rooted at the initial configuration and goal configuration, respectively, the arrival costs of both trees are shared to better estimate the cost-to-go, which improves node selection. Second, by partitioning motion primitives (MPs) into prioritized modes to facilitate mode selection, node expansion grows the tree toward a more finely tuned direction. For safe motion planning, we define conflict areas (CAs) as segments of the path that overlap or intersect with moving obstacles' paths and then develop scheduling algorithms to assign time intervals during which the ego vehicle can occupy each CA. Particularly, to improve throughput and lower computational complexity, we divide large CAs into small areas and establish that, in certain scenarios, the original scheduling problem can be decoupled into subproblems involving the subsets of CAs. Simulation verifies the effectiveness of the proposed architecture and algorithms.