GAMEOPT: Optimal Real-time Multi-Agent Planning and Control at Dynamic Intersections

Non-signalized intersections are one of the more complex, prone to accident scenarios faced in modern transportation networks. Cooperation among Connected Autonomous Vehicles (CAVs) is a promising approach to intersection control which provides increased safety, efficiency and fairness. We propose a novel hierarchical approach to navigating these dynamic, multi-lane, intersections. Our algorithm consists of a hierarchical formulation that first uses an auction mechanism to generate a priority order over all the agents, followed by an optimization-based trajectory planner that computes the optimal velocity commands that respects the priority order. The coupling of an auction mechanism for generating a vehicle entrance sequence and an optimization mechanism for trajectory planning, allows for real-time capable operation in high density multi-agent traffic, while providing formal guarantees in terms of fairness, safety, and efficiency. Our approach can operate at real-time speeds ($<10$ milliseconds), which is at least $40\times$ faster than prior methods. Tested on the SUMO simulator, our algorithm reduces congestion by at least $60\%$, time taken to reach the goal by $75\%$, and fuel consumption by $33\%$, compared to auction-based approaches and signaled approaches using traffic-lights and stop signs.