Trajectory Planning for an Autonomous Vehicle with Conflicting Moving Objects Along a Fixed Path – An Exact Solution Method

Trajectory planning for autonomous vehicles (AVs) by considering conflicting moving objects (CMOs) is a challenging problem to AV operations. This paper investigates an AV trajectory planning problem where the AV follows a given spatial path, and the trajectories of CMOs are predictable. With the spatial path fixed, the two-dimensional trajectory planning problem is reduced to a one-dimensional speed planning problem that decides the optimal speeds and accelerations of the AV along the spatial path. This paper first analyzes the conflict area caused by a single CMO in the space-time diagram, which reveals upper and lower bounds to the conflict area. Then a multi-area fusion algorithm is proposed to extend the upper and lower bound analyses to a relatively complex traffic scenario with multiple CMOs. To facilitate the computation of the investigated problem, a customized dynamic programming (DP) algorithm is developed, which employs the revealed upper and lower bounds and arriving time constraints to cut invalid trajectories at each stage. With this, the number of stages and states, as well as the computational time for solving the proposed problem, are largely reduced. A set of numerical experiments are conducted to evaluate the performance of the customized DP-based algorithm. The results show that the proposed customized DP-based algorithm can solve the investigated problem within milliseconds, which enables applications to real-time AV control. This much outperforms a state-of-the-art commercial solver, Gurobi, especially for complex traffic scenarios. We further implemented the proposed method in a real-world case study, and the results show that the trajectory generated by the proposed model has a great potential to enhance the future traffic system.