A Hierarchical Motion Planning Framework for Autonomous Driving in Structured Highway Environments

Abstract

This paper presents an efficient hierarchical motion planning framework with a long planning horizon for autonomous driving in structured environments. A 3D motion planning with time information is a non-convex problem because there exists more than one local minimum point and various constraints such as roads and obstacles. Accordingly, to deal with high computational complexity and the problem of falling into a local minimum in an enormous solution space, a decoupled method is utilized, that consists of two steps: Long-term planning and short-term planning. First, the long-term planner provides reasonable far-sighted behavior through two processes. In the first process, a rough path that includes a driving strategy is generated in the 2D spatial space. Then, the jump point search algorithm is utilized with time information on the path to reduce the computational burden of A*, giving an acceptable quality of solution at the same time. In this step, a safe, comfortable, and dynamically feasible trajectory is generated. Next, the short-term planner optimizes a short-sighted trajectory using particle swarm optimization. In this method, a steering angle set is encoded as a particle, resulting in a safe, comfortable, and kinodynamically feasible trajectory. The proposed algorithm is implemented and evaluated in a range of vehicle-in-the-loop simulation scenarios, which include various virtual static and dynamic obstacles generated by Intelligent Driver Model. In the evaluation results, the proposed method reduced the computation time by up to 0.696 s with increasing the step cost by up to about 3%. The proposed algorithm is executed every 100 ms for a planning horizon of 10 seconds, and the average computation time is 31 ms with the worst-case computation time of 94 ms.

Keywords

• Motion planning
• Dijkstra’s algorithm
• jump point search algorithm
• particle swarm optimization