PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2607.25388v1cs.RO

TL;DR

Autonomous racing planners must generate diverse competitive behaviors and transition reliably during intense multi-vehicle interactions. SGTP combines game-theoretic reasoning with GPU-accelerated sampling and feasibility selection, achieving a 95.24% win rate and 0.095 s mean computation time in challenging races.

  • Problem

    Autonomous racing still lacks planners and interaction-rich benchmarks for generating diverse competitive behaviors and reliably transitioning among them during sustained interactions.

  • Method

    SGTP uses GPU-parallel control sampling, dynamics rollouts, game-aware trajectory ranking, and feasibility selection enforcing track-boundary and collision-avoidance constraints.

  • Results

    95.24% win rate and 100.00% wins without collisions were achieved, with real-time mean computation of 0.095 s in long-duration racing.

  • Takeaways & Limitations

    SGTP generates diverse competitive behaviors, including blocking, wheel-to-wheel contesting, and overtaking, while transitioning smoothly as interactions evolve.

Abstract

from arXiv · show

Autonomous multi-vehicle racing requires real-time planning of diverse competitive behaviors in intense interactions. Existing planners often struggle to balance strategic diversity and computational efficiency. To address this challenge, we propose Sampling-based Game-Theoretic Planning (SGTP), a real-time framework that combines game-theoretic reasoning with GPU-accelerated sampling of control sequences and dynamics rollouts. Sampled trajectories are ranked using a game-aware cost to capture competitive interactions and generate diverse racing behaviors. Our planner then performs feasibility selection by explicitly enforcing track-boundary and dynamic collision-avoidance constraints, ensuring safe and reliable transitions between racing strategies. Extensive simulations on challenging tracks show that SGTP achieves a 95.24% win rate and a 99.35% task-completion ratio in highly interactive races, with a mean computational time of 0.095 s over multiple iterative solving steps. We also demonstrate the successful application of SGTP in large-scale scenarios with up to 10 agents. We release our code and provide an open-source benchmark of multi-agent autonomous racing algorithms to facilitate future research. Project page: https://sgtp-racing.github.io/.

I. INTRODUCTION · II. SGTP ALGORITHM

SGTP addresses the difficulty of generating diverse, competitive behaviors and transitioning reliably between them in real-time multi-vehicle racing. It combines game-theoretic best-response reasoning with GPU-parallel sampling, dynamics rollouts, game-aware ranking, and feasibility selection.

  • I. INTRODUCTION: Sustained wheel-to-wheel interaction requires autonomous racers to generate multiple competitive behaviors and transition reliably as interactions evolve.
  • I. INTRODUCTION: SGTP reformulates each Iterative Best Response subproblem as GPU-parallel control sampling, dynamics rollout, and trajectory ranking to generate diverse racing strategies in real time.
  • I. INTRODUCTION: The game-aware cost favors competitive interactions, while feasibility selection enforces track-boundary and collision-avoidance constraints for reliable strategy transitions.
  • I. INTRODUCTION: 0.095s mean computation time enables SGTP’s real-time planning across multiple iterative solving steps.
  • II. SGTP ALGORITHM: SGTP initializes vehicle trajectories with distance-based collision avoidance and iteratively computes each vehicle’s approximate best response while holding preceding opponent predictions fixed.
  • II. SGTP ALGORITHM: For each vehicle, SGTP samples K candidate control sequences, projects perturbed inputs onto admissible limits, and propagates them in parallel through the dynamics.
  • II. SGTP ALGORITHM: Sampled rollouts are ranked by game-aware cost and checked for track-boundary and dynamic collision-avoidance feasibility; the lowest-cost feasible rollout warm-starts the next iteration.

III. SAMPLING-BASED GAME-THEORETIC PLANNING

SGTP performs best-response planning by ranking GPU-generated rollouts with a game-aware cost and selecting the lowest-cost feasible rollout.

  • Best-response planning: SGTP ranks rollouts generated in parallel on the GPU using a game-aware cost, then selects the lowest-cost feasible rollout.This implements best-response planning while retaining feasibility as a selection condition.

A. Game-Aware Cost for Diverse Behaviors

SGTP ranks candidate trajectories with a game-aware cost based on pairwise interactions against predicted opponent trajectories. Complementary terms shape competitive behavior, and costs are summed across opponents so each prediction contributes independently.

  • Pairwise Interaction Cost: The game-aware cost evaluates pairwise interactions between each candidate trajectory and predicted opponent trajectories.This interaction-based evaluation supports game-aware ranking of candidate rollouts.
  • Cost Components: Four terms represent contest-state maintenance, longitudinal advantage, blocking alignment, and safety separation.These terms are denoted ccontest, clong, cblock, and csafety, respectively.
  • Behavior Shaping: The contest, longitudinal, blocking, and safety terms preserve meaningful racing windows, promote forward advantage, encourage defensive positioning, and penalize insufficient separation.Together, the terms progressively shape competitive interaction behavior.
  • Opponent Aggregation: Pairwise game-aware costs are summed over all opponents, allowing each opponent prediction to contribute independently to candidate ranking.The total game-aware cost is defined for each candidate k.

1) Contest-State Maintenance Cost:

The contest-state cost evaluates candidate trajectories by their terminal longitudinal progress gaps relative to predicted opponent trajectories. It encourages sampled rollouts to interact closely with opponents within a meaningful competitive window.

  • Contest-state term: The contest-state term rewards candidates whose terminal progress gaps from predicted opponent trajectories remain within the longitudinal interaction range.This term evaluates competitive proximity at the rollout horizon.
  • Progress-gap definition: Pairwise gaps compare ego candidate k’s terminal Frenet progress with opponent j’s predicted terminal progress.The gaps are defined between the corresponding ego and opponent progress values at t+H.
  • Contest indicator: The contest indicator determines whether each candidate–opponent progress gap lies within the longitudinal contest range.The range is denoted scontest.
  • Contest-state cost: The pairwise contest-state cost uses a tunable weight wcontest to encourage close interaction with opponents’ predicted trajectories.The intended interaction occurs within a meaningful competitive window.

2) Longitudinal Advantage Cost:

The longitudinal advantage cost favors candidate trajectories that achieve greater terminal progress than an opponent. Its adaptive weight increases the importance of progress gains during close interactions and decreases as the progress gap widens.

  • Longitudinal Advantage Cost: The longitudinal advantage term rewards candidate trajectories with a terminal progress advantage over opponent j.It is designed to favor candidates that move ahead of the opponent.
  • Longitudinal Advantage Cost: A larger positive terminal progress gap reduces the cost and favors candidates that move ahead of opponent j.The terminal progress gap is denoted by ij,t+H.
  • Longitudinal Advantage Cost: The adaptive weight αij,t assigns greater importance to terminal progress gains when two vehicles are close.As their progress gap increases, αij,t decreases the reward because interaction relevance weakens; ϵ is a small positive constant.

3) Blocking Alignment Cost: · 4) Safety Cost:

The blocking alignment cost promotes defensive trajectories by aligning their tail lateral positions with predicted opponent positions when the ego vehicle has a sufficient longitudinal advantage within contest range. The safety cost penalizes predicted opponent separations below gsafe, with violations weighted quadratically by their magnitude.

  • 3) Blocking Alignment Cost:: Blocking alignment encourages candidate trajectories to match an opponent’s predicted lateral position near the end of the prediction horizon.The alignment uses mean lateral offsets over the final µtail portion of the horizon.
  • 3) Blocking Alignment Cost:: The tail lateral gap ∆d(k) measures the candidate’s lateral offset relative to the predicted opponent offset over the horizon tail.The opponent prediction is denoted ˆdj,t+τ.
  • 3) Blocking Alignment Cost:: The blocking cost is activated when vehicle i leads opponent j by at least srole while remaining within the contest range scontest.Its activation is γblock,ij = wblockI[∆sij,t > srole] I[∆sij,t < scontest], with ∆sij,t = si,t −ˆsj,t.
  • 3) Blocking Alignment Cost:: Lateral alignment reduces the space available to the trailing vehicle and promotes defensive blocking.The scalar wblock determines the blocking-cost weight.
  • 4) Safety Cost:: The safety term penalizes candidate rollouts whose predicted separation from an opponent falls below the desired threshold gsafe.For candidate k and opponent j, the safety calculation uses the minimum time-aligned distance.
  • 4) Safety Cost:: The safety cost compares candidate and opponent positions at the same time t + τ to evaluate pairwise predicted separation.The candidate position is associated with i,t+τ, while ˆpj,t+τ denotes the opponent’s predicted position.
  • 4) Safety Cost:: Safety violations incur a penalty weighted by wsafety that increases quadratically with the magnitude of the separation violation.The cost applies when the minimum predicted separation falls below gsafe.

5) Overall Game-Aware Rollout Ranking: · B. Feasibility Selection

SGTP ranks sampled rollouts using game-aware and nominal tracking/control costs, with reference progress and states propagated along an arc-length-parameterized raceline. Feasibility selection then chooses the lowest-cost ranked candidate satisfying track-boundary and inter-vehicle collision checks.

  • 5) Overall Game-Aware Rollout Ranking:: Each sampled rollout is evaluated against a reference trajectory derived from the arc-length-parameterized raceline G.The evaluation includes nominal quadratic tracking and control cost.
  • 5) Overall Game-Aware Rollout Ranking:: Reference progress sr_i,t+τ is propagated recursively along G using the associated reference velocity profile vr(s).Propagation starts from the rollout’s reference progress and continues across the horizon.
  • 5) Overall Game-Aware Rollout Ranking:: Reference states x^r_i,t+τ are obtained from the propagated reference progress and velocity information.These reference states support the nominal rollout cost calculation.
  • 5) Overall Game-Aware Rollout Ranking:: For each candidate rollout k, the nominal tracking and control cost is defined using its deviation from the reference trajectory.The source introduces this cost after specifying the corresponding reference states.
  • 5) Overall Game-Aware Rollout Ranking:: The nominal cost uses weighting matrices Q, R, and S before contributing to the total cost assigned to candidate k.The total cost also includes the game-aware cost.
  • 5) Overall Game-Aware Rollout Ranking:: The weight w_game balances the game-aware cost against the nominal tracking and control cost.This weighting determines how the two cost components influence the total candidate ranking.
  • B. Feasibility Selection: After batch cost evaluation, feasibility selection checks ranked candidates for track-boundary violations and inter-vehicle collisions.The checks are applied explicitly before a candidate is selected.
  • B. Feasibility Selection: The selected rollout is the lowest-cost ranked candidate that passes both feasibility checks.Candidates that fail either check are not selected.

1) Track-Boundary Check:  · 2) Collision-Avoidance Check:

SGTP evaluates each candidate rollout for track-boundary clearance and time-aligned inter-vehicle collision clearance. Feasibility selection retains candidates passing both checks, while a least-violation fallback handles cases with no feasible candidate.

  • 1) Track-Boundary Check: : Track-boundary clearance is defined for candidate k at prediction step τ.The boundary-check formulation evaluates clearance during the prediction rollout.
  • 1) Track-Boundary Check: : The minimum boundary clearance is evaluated over the prediction horizon as ρ(k).This horizon-wide minimum summarizes candidate k’s boundary proximity.
  • 1) Track-Boundary Check: : A candidate passes the track-boundary check when its minimum clearance remains above the required threshold m_bd.The criterion applies the prescribed boundary-clearance threshold across the rollout.
  • 2) Collision-Avoidance Check:: Collision checking uses a time-aligned minimum-distance operator to evaluate candidate rollout k against all opponents.The minimum clearance is defined over the candidate’s interactions with every opponent.
  • 2) Collision-Avoidance Check:: A candidate passes collision avoidance when its minimum inter-vehicle clearance remains above the collision threshold d_col.This enforces the prescribed separation criterion throughout the rollout.
  • 2) Collision-Avoidance Check:: A candidate is feasible only if it passes both track-boundary and collision-avoidance checks, and the lowest-cost feasible candidate is selected.The selection is made at IBR iteration ℓ using the candidate cost from (9).
  • 2) Collision-Avoidance Check:: Feasibility checks complement cost-based ranking: cost ranks candidates, constraints determine feasibility, and the selected control sequence warm-starts the next planning step.If no feasible candidate exists, SGTP invokes a least-violation fallback that selects the smallest combined boundary and collision violation.

IV. RESULTS AND DISCUSSION … C. Evaluation Metrics

The evaluation compares SGTP with literature planners and ablation variants in long-duration, closed-loop competitive racing, emphasizing competitiveness and real-time efficiency. It defines metrics for winning, overtaking, interaction duration, trial duration, and computation time.

  • IV. RESULTS AND DISCUSSION: The evaluation tests SGTP in long-duration, closed-loop competitive multi-vehicle racing scenarios across challenging tracks.It compares representative baselines, conducts ablations, and focuses on competitiveness and real-time efficiency.
  • A. Literature Benchmarks: SGTP is compared with eight literature benchmarks, including sampling-based lattice, End2Race, CFM, Race Stack, EVO-MPCC, MPPI, and Biased-MPPI planners.An EVO-MPCC solver is also integrated into the IBR loop for comparison under the same IBR setting.
  • A. Literature Benchmarks: Two ablations remove or replace key components: SGTP w/o GC removes the game-aware cost, while GA-IBR-MPPI retains it with standard MPPI updates.All planned trajectories are tracked with the same pure-pursuit controller.
  • B. Implementation and Racing Scenarios: SGTP and MPPI use K=128 samples over a 1.2s prediction horizon (H=12), with σa = 0.335 and σδ = 0.025.The implementation also specifies tracking-cost weights, game-aware weights, LIBR=2 IBR iterations, mbd=0.515m, and dcol=0.9m.
  • C. Evaluation Metrics: A trial counts as a win when ego Frenet progress gain exceeds every opponent’s by the margin ϵs = 5 × 10−3.Win rate is reported as Wins, and FPR measures the fraction of opponents overtaken by the ego vehicle.
  • C. Evaluation Metrics: CSD measures mean close-interaction duration when an opponent remains within 1.0m longitudinally and 0.5m laterally of ego in Frenet coordinates.Long-duration performance is additionally reported using maximum trial duration Dmax and mean trial duration Dmean.
  • C. Evaluation Metrics: Computation Time (CT) is the wall-clock duration of each planning call, including all IBR iterations and the additional ego response for IBR-based planners.The reported statistics are CTmean, CTstd, and CTmax over valid trials.

D. Qualitative Evaluation of Multi-Behavior Interactions · E. Quantitative Results: Performance & Real-Time Efficiency

SGTP produces diverse, smoothly transitioning competitive behaviors in highly interactive multi-vehicle races. Across quantitative trials, it achieves strong win, collision-free, overtaking, and sustained-racing performance while supporting real-time planning.

  • D. Qualitative Evaluation of Multi-Behavior Interactions: SGTP sustains close-range interactions across Berlin, f-shape, and Brands Hatch using three competitively reactive vehicles in trials lasting up to 40s.The ego vehicle and two opponents are all controlled by SGTP.
  • D. Qualitative Evaluation of Multi-Behavior Interactions: SGTP generates blocking, wheel-to-wheel contesting, and opportunistic overtaking through IBR updates and game-aware rollout ranking.These behaviors arise as competitive interactions evolve.
  • D. Qualitative Evaluation of Multi-Behavior Interactions: SGTP transitions smoothly among racing behaviors as multi-vehicle interactions evolve.The qualitative results specifically report smooth transitions between the generated behaviors.
  • E. Quantitative Results: Performance & Real-Time Efficiency: 42 trials span 7 tracks and 6 starting positions, with one ego vehicle and two opponents, running for at most 50s or until collision.CFM and End2Race use MPPI-controlled opponents, whereas other methods use the same planner for ego and opponents.
  • E. Quantitative Results: Performance & Real-Time Efficiency: 95.24% Wins and 100.00% wins without collisions (CFW) constitute SGTP’s best overall performance in Table I.These metrics summarize SGTP’s reported win and collision-free performance.
  • E. Quantitative Results: Performance & Real-Time Efficiency: 49.67s Dmean under a 50s maximum trial duration shows that SGTP sustains racing for nearly the entire allowed duration.The reported mean duration is Dmean = 49.67s.
  • E. Quantitative Results: Performance & Real-Time Efficiency: 75.00% FPR and 0.99 CSD are the highest reported values, indicating successful overtaking after sustained close-range interactions.SGTP also maintains competitive speed with ¯vego = 5.86 m/s.
  • E. Quantitative Results: Performance & Real-Time Efficiency: 50.00% Wins and 14.29% CFW result when the game-aware cost is removed, indicating weaker competitive performance in the ablation.The ablation passage attributes these reductions to SGTP w/o GC.

F. Defensive Capability and Robustness to Perturbations · G. Scalability Analysis Across Vehicle Counts · V. CONCLUSIONS

SGTP demonstrates defensive effectiveness and robustness under perturbed predictions while maintaining collision-free, stable computation as vehicle counts increase. Its GPU-parallel sampling, game-theoretic reasoning, and feasibility selection support diverse, reliable competitive behaviors in real-time multi-vehicle racing.

  • F. Defensive Capability and Robustness to Perturbations: 3.88% CFW demonstrates SGTP can defend against an MPC-based planner despite EVO-MPCC receiving the only additional final response.The defensive evaluation used one EVO-MPCC rearmost vehicle against two SGTP opponents whose performance was reduced by 10%.
  • F. Defensive Capability and Robustness to Perturbations: 0.52% Dmean decrease under mild perturbations indicates preserved mean separation, while 55.88% CSD decrease reflects more conservative interactions.Safety cost and feasibility selection penalize or reject candidates with insufficient clearance.
  • F. Defensive Capability and Robustness to Perturbations: Prediction-perturbation experiments use (σlon, σlat) = (0.03, 0.015) for mild noise and (0.08, 0.04) for severe noise.The reported ∆Dmean and ∆CSD values are computed relative to SGTP without noise.
  • G. Scalability Analysis Across Vehicle Counts: Across 2 to 10 vehicles on Brands Hatch, SGTP maintains low, stable computation time with small variance and remains collision-free.Each scalability trial lasts 11s.
  • G. Scalability Analysis Across Vehicle Counts: IBR-MPC shows rapidly increasing computation time, greater variance, and collisions as vehicle counts increase, unlike SGTP.The comparison is reported for the Brands Hatch scalability evaluation.
  • G. Scalability Analysis Across Vehicle Counts: SGTP combines IBR reasoning with sampling-based planning to maintain real-time performance and generate reliable behaviors across varying vehicle counts.This scalability design supports performance across the evaluated range of interacting vehicles.
  • V. CONCLUSIONS: GPU-parallel sampling and rollout evaluation let SGTP efficiently approximate unilateral best responses in IBR.Feasibility selection explicitly enforces track-boundary and collision-avoidance constraints, supporting reliable transitions between diverse behaviors.
  • V. CONCLUSIONS: SGTP’s game-aware cost produces diverse competitive behaviors, including blocking, while its feasibility mechanisms support reliable transitions between behaviors.The conclusion identifies SGTP as a real-time game-theoretic planner for competitive multi-vehicle racing.
Loading 2607.25388v1…