  We present a fast planning architecture called Hamilton-Jacobi-based
bidirectional A* (HJBA*) to solve general tight parking scenarios. The
algorithm is a two-layer composed of a high-level HJ-based reachability
analysis and a lower-level bidirectional A* search algorithm. In high-level
reachability analysis, a backward reachable tube (BRT) concerning vehicle
dynamics is computed by the HJ analysis and it intersects with a safe set to
get a safe reachable set. The safe set is defined by constraints of positive
signed distances for obstacles in the environment and computed by solving QP
optimization problems offline. For states inside the intersection set, i.e.,
the safe reachable set, the computed backward reachable tube ensures they are
reachable subjected to system dynamics and input bounds, and the safe set
guarantees they satisfy parking safety with respect to obstacles in different
shapes. For online computation, randomized states are sampled from the safe
reachable set, and used as heuristic guide points to be considered in the
bidirectional A* search. The bidirectional A* search is paralleled for each
randomized state from the safe reachable set. We show that the proposed
two-level planning algorithm is able to solve different parking scenarios
effectively and computationally fast for typical parking requests. We validate
our algorithm through simulations in large-scale randomized parking scenarios
and demonstrate it to be able to outperform other state-of-the-art parking
planning algorithms.
