Game-Theoretic Autonomous Driving: A Graphs of Convex Sets Approach
Preprint
Abstract
Multi-vehicle autonomous driving couples strategic interaction with hybrid (discrete-continuous) maneuver planning under shared safety constraints. We introduce IBR-GCS, an Iterative Best Response (IBR) planning approach based on the Graphs of Convex Sets (GCS) framework that models highway driving as a generalized noncooperative game. IBR-GCS integrates combinatorial maneuver reasoning, trajectory planning, and game-theoretic interaction within a unified framework. The key novelty is a vehicle-specific, strategy-dependent GCS construction. Specifically, at each best-response update, each vehicle builds its own graph conditioned on the current strategies of the other vehicles, with vertices representing lane-specific, time-varying, convex, collision-free regions and edges encoding dynamically feasible transitions. This yields a shortest-path problem in GCS for each best-response step, which admits an efficient convex relaxation that can be solved using convex optimization tools without exhaustive discrete tree search. We then apply an iterative best-response scheme in which vehicles update their trajectories sequentially and provide conditions under which the resulting inexact updates converge to an approximate generalized Nash equilibrium. Simulation results across multi-lane, multi-vehicle scenarios demonstrate that IBR-GCS produces safe trajectories and strategically consistent interactive behaviors.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning2025
- Distributed Potential iLQR: Scalable Game-Theoretic Trajectory Planning for Multi-Agent Interactions2023
- Urban Driving Games With Lexicographic Preferences and Socially Efficient Nash EquilibriaIEEE Robotics and Automation Letters, 2021
- Multi-agent sensitivity enhanced iterative best response: A real-time game theoretic planner for drone racing in 3D environmentsRobotics and Autonomous Systems, 2020
- Multi-Vehicle Automated Driving as a Generalized Mixed-Integer Potential GameIEEE Transactions on Intelligent Transportation Systems, 2019
- Spatiotemporal Motion Planning with Combinatorial Reasoning for Autonomous Driving2018
- Efficient mixed-integer planning for UAVs in cluttered environments2015
- Modeling and control of a multi-agent system using mixed integer linear programming2003
- Aircraft trajectory planning with collision avoidance using mixed integer linear programming2002
- Potential GamesGames and Economic Behavior, 1996