Dynamic Game-Informed Lane Changing: Leveraging Stochastic Search for Autonomous Vehicle Decision-Making

Tan Xiang*, Ziyan Wang*, Ding Li and Peng Chen

School of Transportation Science and Engineering, Beihang University

Abstract

Safe and efficient lane-changing remains a core challenge in autonomous driving, due to complex and uncertain inter-vehicle interactions in dynamic multi-agent environments. Existing prediction- and rule-based methods often struggle to capture bidirectional strategic coupling and reason under behavioral uncertainty. In this work, we propose Dynamic Game-Informed Stochastic Search (DGSS), a novel decision-making framework that integrates multi-tree Monte Carlo Tree Search (MCTS) with game-theoretic modeling to capture adaptive inter-agent interactions. DGSS constructs a dedicated game tree for each relevant surrounding vehicle, enabling parallel turn-based strategic simulations and mutual behavioral adaptation over time. Candidate actions are evaluated through a multi-objective reward function that balances safety, spatial advantage, and driving efficiency. We validate DGSS through extensive experiments in both a custom local simulator and the nuPlan dataset. Results show that DGSS significantly improves safety and interaction-awareness compared to existing baselines, providing a safe, interpretable, and robust solution for autonomous lane-changing.

Framework

we propose the DGSS framework, a game-theoretic lane-change decision-making algorithm designed for multi-vehicle interaction scenarios. The core idea is to model bidirectional strategy evolution using a multi-tree structure, where each tree corresponds to an interactive vehicle identified from the surrounding vehicles and simulates turn-based strategic games with predefined action sets and multi-objective rewards (e.g., safety, spatial gains, efficiency). The ego vehicle's strategy is evaluated during odd-numbered iterations, while interactive vehicles’ strategies evolve during even-numbered ones, capturing causal reactions over time. By combining multi-sample trajectory rollouts, quintic polynomial generation, and multi-tree decision aggregation, our algorithm performs parallel game simulations, infers interactive vehicles' intents, and selects the optimal lane-change action for the ego vehicle.

Experiments Videos

The video version of the local simulation scenarios in Fig. 2. In which the ego is shown in yellow, the interactive vehicles are shown in red.

Dynamic Game-Informed Lane Changing: Leveraging Stochastic Search for Autonomous Vehicle Decision-Making

Abstract

Framework

Experiments Videos

DGSS: Proactive continuous lane changes

DGSS: A disrupted left lane change

DGSS:An emergency response to a cut-in

DGSS: A disrupted right lane change

Nuplan Experiments Comparison Videos

DGSS

PDM-hybrid

GC-PGP

Urban_Driver