Multi-Vehicle Cooperative Motion Planning Based on ADMM With Parallel Computing and Convexifying Guidance

For automated vehicle, motion planning especially multi-vehicle cooperative motion planning (MVCMP), is an important and challenging problem, while the high-dimensional coupled nonlinear constraints make it become a highly non-convex nonlinear programming (NLP) problem. In this paper, we propose a parallel computing and convexifying guidance framework based on alternating direction method of multipliers (ADMM) and constraint convexification. By applying ADMM and introducing auxiliary variables, the original problem is decomposed into two types of sub-problems that can be solved in a parallel manner. The first type of sub-problem only contains kinematics constraints and can be tackled by the proposed ‘First Solve Then Regulate Time’ (FSTRT) method, which can eliminate the time coupling and divide this sub-problem into multiple parallel secondary sub-problems for each vehicle. The second type of sub-problem only considers collision avoidance constraints among multiple vehicles, and can also be solved in parallel based on copy variable. In particular, the terminal guided convex feasible set (TG-CFS) algorithm and convexifying guidance strategy are proposed to achieve constraint convexification and efficient warm-start for this sub-problem. The advantage of proposed algorithm lies at effectively resolving constraint coupling and reduce the dimension of original problem, thereby achieving parallel and fast computation of the sub-problems. Simulation and comparison results of different cases indicate that the proposed algorithm can significantly improve the computational efficiency while preserving the optimality.