An MIQP-based heuristic for Optimal Coordination of Vehicles at Intersections

The problem of coordinating automated vehicles at intersections can be formulated as an optimal control prob- lem which is inherently difficult to solve, due to its combinato- rial nature. In this paper, we propose a two-stage approximation algorithm based on a previously presented decomposition. The procedure (a) first solves a Mixed Integer Quadratic Program (MIQP) to compute an approximate solution to the combinatorial part of the problem, i.e. the order in which the vehicles cross the intersection; then (b), solves a Nonlinear Program (NLP) for the optimal state and control trajectories. We demonstrate the performance of the algorithm through extensive simulation, and show that it greatly outperforms the natural First-Come-First-Served heuristic