Real-Time Solution-Seeking for Game-Theoretic Autonomous Driving via Time-Distributed Iterations
This work addresses the real-time computation bottleneck of Nash equilibria in multi-agent autonomous driving, enabling faster decision-making at high sampling rates.
The paper tackles the computational complexity of game-theoretic model predictive control (GT-MPC) for autonomous driving by distributing solution-seeking iterations over time using Newton and Newton-Kantorovich methods, achieving real-time performance in intersection-crossing scenarios.
Computational complexity has been a major challenge in game-theoretic model predictive control (GT-MPC), as real-time solutions to a game (e.g., Nash equilibria (NEs)) have to be computed at each sampling instant of an MPC. This challenge is especially critical in autonomous driving, where interactions may involve many agents, and decisions must be made at fast sampling rates. We show that this challenge can be addressed through time-distributed solution-seeking iterations designed based on, e.g., Newton and Newton--Kantorovich methods. Specifically, the autonomous vehicle decision-making problem is first formulated as a GT-MPC problem. To ensure solution attainability, a potential game framework is adopted. Within this framework, both potential-function optimization and best-response dynamics are used to seek the NE. To enable real-time implementation, Newton and Newton--Kantorovich methods are employed to solve the optimization problems arising in the NE-seeking algorithms, with their iterations distributed over time. Numerical experiments on an intersection-crossing scenario demonstrate that the proposed methods achieve effective real-time performance.