  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.
