Collision-free Minimum-time Trajectory Planning for Multiple Vehicles based on ADMM

Abstract

The paper presents a practical approach for planning trajectories for multiple vehicles where both collision avoidance and minimum travelling time are simultaneously considered. It is first proposed to exploit the mixed-integer programming (MIP) approach to formulate the collision avoidance paradigm, where the linear dynamic models are utilized to derive the linear constraints. Moreover, travelling time of each vehicle is compromised among them and set to be minimized so that all the vehicles can practically reach the expected destinations at the shortest time. Unfortunately, the formulated optimization problem is NP-hard. In order to effectively address it, we propose to employ the alternating direction method of multipliers (ADMM), which can share the computational burdens to distributive optimization solvers. Thus, the proposed method can enable each vehicle to obtain an expected trajectory in a practical time. Convergence of the proposed algorithm is also discussed. To verify effectiveness of our approach, we implemented it in a numerical example, where the obtained results are highly promising.