SGTP: Sampling-based Game-Theoretic Planning for Real-Time Multi-Vehicle Autonomous Racing
Zhouheng Li, Fangguo Zhao, Mattia Piccinini, Baha Zarrouki, Yuan Gao, Zitong Shan, Johannes Betz, Chen Lv, Lei Xie
cs.RO
2026-07-28
SGTP turns each game-theoretic best response into GPU control sampling, ranks by a game-aware cost, then filters by hard constraints: 95% win rate, 0.095s per step, about 20x faster than IBR-MPC.
Multi-vehicle autonomous racing has to plan in real time: overtake, defend, block, and finish computing in tens of milliseconds. Existing planners each fall short in their own way. FSM planners need hand-designed behavior modes and heavy parameter tuning. MPC variants are sensitive to initialization in tight combat and have variable solve times. Learning-based methods lack interpretability and do not generalize across scenarios. MPPI-style samplers handle collision avoidance only through soft cost penalties, with no hard feasibility check, so wheel-to-wheel they pick moves that will crash.
The fundamental tension is between strategic diversity and computational efficiency. SGTP (Sampling-based Game-Theoretic Planning) tries to take both.
SGTP recasts Iterative Best Response (IBR). Classic IBR has each vehicle in turn treat the opponents' trajectories as fixed and compute its own best response, iterating to convergence. The bottleneck is that each best response is itself an optimization and is slow.
SGTP replaces each best-response subproblem with GPU-parallel control-sequence sampling: draw K=128 control sequences, roll them forward through a kinematic bicycle model to get 128 trajectories, then rank them with a game-aware cost designed to produce diverse competitive behavior. The cost has four parts:
Then the key step, hard feasibility filtering. Where MPPI folds collision avoidance into a soft cost, SGTP explicitly checks each candidate trajectory, whether boundary clearance rhobd and obstacle clearance rhoobs both hold. Only trajectories passing both are feasible. The lowest-cost feasible one is chosen; if none is feasible, a least-violation fallback picks the candidate with the smallest combined violation. This keeps SGTP safe and reliable even when switching strategies.
Settings: K=128, horizon H=12 (1.2 s), 2 IBR iterations, then one extra best response for the ego car.
Across 7 MapZoo tracks, 6 starting positions each, one ego and two opponents, 50 s max, 42 trials total, against 8 literature baselines (lattice, End2Race, CFM, FSM, EVO-MPCC, standard MPPI, Biased-MPPI, IBR-MPC):
| Metric | SGTP | Comparison |
| Win rate | 95.24% | EVO-MPCC 92.86%, IBR-MPC 85.71% |
| Collision-free win rate | 100% | n/a |
| Per-step compute | 0.095 s (std 0.004) | EVO-MPCC 0.860 s, IBR-MPC 1.903 s |
| Task completion | 99.35% (mean 49.67 s / 50 s) | n/a |
SGTP is about 9x faster than EVO-MPCC and about 20x faster than IBR-MPC, with a higher win rate.
The ablations are clean. Remove the game-aware cost (tracking cost only): win rate drops to 50%, collision-free win to 14.29%. Put the game-aware cost into standard MPPI (GA-IBR-MPPI): 57.14% win, 0% collision-free. The sampling plus hard-constraint combination is what does it; the game-aware cost alone is not enough.
On scaling, from 2 up to 10 vehicles, SGTP keeps compute low with small variance and stays collision-free, while IBR-MPC's compute and variance climb and it crashes in dense scenarios. Under mild and severe perturbations of opponent prediction, SGTP holds 94–97% collision-free win rate.
Code, baselines, and the evaluation platform are open-sourced; project page sgtp-racing.github.io.
For anyone in autonomous-driving planning or real-time robotic decision-making, this is a clean example of stitching game-theoretic optimality together with the speed and hard safety constraints of sampling-based planning. The idea transfers to any real-time, multi-agent, strongly interactive setting that still needs hard collision avoidance: dense traffic, multi-robot coordination. The open benchmark is itself useful, since multi-vehicle racing has lacked a unified comparison platform.
A cold splash of water: this is a control and optimization method, not a learning method. It does not learn opponent style; opponent prediction is currently fixed. All experiments are in F1TENTH simulation, with no real-vehicle validation.
The four game-aware cost weights (wcontest, wlong, wblock, wsafety = 1.0, 2.0, 10.0, 50.0) are hand-tuned; the authors flag reducing the tuning burden as future work. Opponent prediction uses fixed trajectories, which they list as a limitation and plan to address with world-model-based opponent style recognition. Scalability beyond 10 vehicles is untested. Everything is in F1TENTH Gym with no real-vehicle validation, and the contact and limit dynamics of racing differ a lot between sim and a real car. Whether the cost weights transfer across tracks and vehicle types is also unverified.