Optimal Cooperative Driving at Signal-Free Intersections with Polynomial-Time Complexity

Cooperative driving at signal-free intersections, which aims to improve driving safety and efficiency for connected and automated vehicles, has attracted increasing interest in recent years. However, existing cooperative driving strategies either suffer from computational complexity or cannot guarantee global optimality. To fill this research gap, this paper proposes an optimal and computationally efficient cooperative driving strategy with the polynomial-time complexity. By modeling the conflict relations among the vehicles, the solution space of the cooperative driving problem is completely represented by a newly designed small-size state space. Then, based on dynamic programming, the globally optimal solution can be searched inside the state space efficiently. It is proved that the proposed strategy can reduce the time complexity of computation from exponential to a small-degree polynomial. Simulation results further demonstrate that the proposed strategy can obtain the globally optimal solution within a limited computation time under various traffic demand settings.