Short-Term Multi-Vehicle Trajectory Planning for Collision Avoidance

Abstract

A trajectory planning is a technique that is widely used to automatically generate an expected geometric path that a vehicle needs to follow within a certain future time horizon. We propose a way to generate trajectories of multiple vehicles for a short-term planning with the formal guarantee of the collision avoidance using a SAT (Satisfiability) solver. We assume that each vehicle sends the local status (e.g., speed or position) and its planned trajectory to the server (e.g., road-side units or cloud servers). The server collects the information, and determines if the group of vehicles would encounter any collision within a fixed amount of time. Then, the server calculates the modified trajectories, and sends them back to the vehicles to avoid collisions. Calculating such trajectories is generally a complex problem, which makes it challenging to find them within a short amount of time. Given a driving scenario where multiple vehicles are engaged, we propose two methods to reduce the computation time to generate the trajectories. Firstly, we introduce the grouping method which systematically identifies vehicles that are not engaged in the collision scenario, and removes the related parameters from the SAT solving process. Our case study of the ramp merging driving scenario shows the grouping method saves the computation time by 40% compared to solving the constraints with the original parameters. Secondly, we introduce the collision check point method that chooses some waypoints to maintain their previous control input to reduce the problem complexity. Our experiment shows up to 98% computation time reduction compared to the approach without this method.