Source-linked AI summary
Game-Theoretic Modeling of Multi-Vehicle Interactions at Uncontrolled Intersections
Nan Li, Yu Yao, Ilya Kolmanovsky, Ella Atkins, Anouck Girard
TL;DR
Autonomous-driving virtual tests depend on simulations that faithfully represent interactions at uncontrolled intersections, where drivers must negotiate passage without signals or signs. The paper models these interactions with concurrent leader-follower games and parameterized intersection layouts. Simulations show reasonable traffic behavior, including conflict resolution and performance assessed against level-of-service criteria.
Problem
At uncontrolled intersections, drivers must decide when and how to enter without signals or signs, making interaction modeling important for reliable virtual testing of autonomous systems.
Source: §I · p. 1Method
The framework models vehicle interactions using concurrent leader-follower games, receding-horizon optimization, common traffic rules, and parameterized intersection layouts.
Source: §I · p. 2Results
The model showed reasonably high success in resolving traffic conflicts, average completion times matching level-of-service criteria, and decision-making complexity increasing linearly with vehicle count.
Source: §VIII · p. 15Takeaways & Limitations
Simulations indicate the model can reproduce scenarios extracted from real-world traffic data and resolve conflicts with different drivers.
Source: §I · p. 2
Abstract
from arXiv · showhide
Motivated by the need to develop simulation tools for verification and validation of autonomous driving systems operating in traffic consisting of both autonomous and human-driven vehicles, we propose a framework for modeling vehicle interactions at uncontrolled intersections. The proposed interaction modeling approach is based on game theory with multiple concurrent leader-follower pairs, and accounts for common traffic rules. We parameterize the intersection layouts and geometries to model uncontrolled intersections with various configurations, and apply the proposed approach to model the interactive behavior of vehicles at these intersections. Based on simulation results in various traffic scenarios, we show that the model exhibits reasonable behavior expected in traffic, including the capability of reproducing scenarios extracted from real-world traffic data and reasonable performance in resolving traffic conflicts. The model is further validated based on the level-of-service traffic quality rating system and demonstrates manageable computational complexity compared to traditional multi-player game-theoretic models.
I. INTRODUCTION
Reliable virtual testing depends on simulations that capture vehicle interactions, especially at uncontrolled intersections where drivers must negotiate passage without signals or signs. The paper proposes a game-theoretic modeling framework and intersection representation for these scenarios.
I. INTRODUCTION
- Virtual testing can provide quick, safe alternatives to road tests, but its reliability depends on simulations faithfully representing traffic scenarios.Autonomous systems also need validation across varied traffic environments before mass production.Source: §I · p. 1
- Without signals or signs, drivers must decide when and how to enter; overly cautious behavior may cause deadlocks, while overly aggressive behavior may cause collisions.Intersections account for more than one fourth of U.S. fatal crashes, and about 50% of those occur at uncontrolled intersections.Source: §I · p. 1
- Prior work addressed two-vehicle intersection games or highway interactions, while extensions to more vehicles and varied intersection configurations remained unaddressed.A cited two-player intersection study reported a single straight-through scenario; generalizing the highway framework beyond two intersection vehicles was not addressed.Source: §I · p. 2
- The framework uses concurrent leader-follower games and receding-horizon optimization to model interactions at uncontrolled intersections, including scenarios with up to 10 vehicles.It accounts for vehicle dynamics, decision-making delays, and common traffic rules, and supports different intersection configurations.Source: §I · p. 2
II. VEHICLE INTERACTION MODELING BASED ON LEADER-FOLLOWER GAMES
- The section introduces a game-theoretic approach to model interactive vehicle decision-making at uncontrolled intersections.It first establishes leader-follower assignments, then formulates two-vehicle games and generalizes them to multi-vehicle interactions through pairwise leader-follower games.Source: §II · p. 2
A. Leader-follower role assignment to vehicles at uncontrolled intersections
- Pairwise roles are assigned using right-of-way-inspired rules, including progress through the intersection, right-side priority for adjacent approaches, and straight-through priority over turning.The rules can produce cyclic leader-follower patterns, which may leave vehicles deadlocked; the formal algorithm also incorporates kinematics, intersection geometry, and perception imperfections.Source: A. Leader-follower role assignment to… · pp. 2–3
B. Leader-follower game to model two-vehicle interactions
Two-vehicle interactions are modeled as a Stackelberg game, with leader-follower roles reflecting traffic priority and delayed observation handled through a maximin response. For multiple vehicles, pairwise games are combined into each vehicle’s decision, reducing the interaction problem while retaining a stated limitation in leader predictions.
B. Leader-follower game to model two-vehicle interactions
- A Stackelberg game models each vehicle pair asymmetrically, allowing the earlier-arriving leader to have the typical right of way.The leader is assumed to know that the follower uses a maximin strategy, while the follower cannot instantly observe the leader’s action because of reaction delay.Source: B. Leader-follower game to model… · pp. 3–4
- Each player's reward depends on both vehicles' states and actions, representing the interactive nature of their decision-making.The pair state contains the states of the two vehicles; each player selects an action to maximize its reward.Source: B. Leader-follower game to model… · p. 3
C. Pairwise leader-follower game to model multi-vehicle interactions
- Pairwise leader-follower games decouple n-vehicle interactions, with each vehicle maximizing its minimum secured or predicted reward across its pairwise relationships.A leader predicts its pairwise follower's maximin action; as a follower, it secures reward against the other vehicle's uncertain action.Source: C. Pairwise leader-follower game to… · p. 4
- The leader's predicted follower action may be inaccurate because that vehicle's actual choice also reflects its interactions with others.The authors describe the pairwise strategy as reasonable for the intersection question of who goes first, but identify this prediction mismatch as a caveat.Source: C. Pairwise leader-follower game to… · p. 4
- Unlike a rule that makes followers wait until leaders clear the intersection, the game can allow entry when their action choices have only minor conflicts.The decision process represents whether actions conflict and how those conflicts influence the interaction.Source: C. Pairwise leader-follower game to… · p. 5
III. PARAMETERIZED INTERSECTION AND VEHICLE PATH MODELING
The paper parameterizes intersection layouts and geometries to represent varied traffic scenarios for simulation. Its intersection model describes road arms, lane markings, boundaries, and lane entrance and exit points, with a stated right-hand-traffic scope.
III. PARAMETERIZED INTERSECTION AND VEHICLE PATH MODELING
- The model parameterizes intersection layout and geometry to support simulation of traffic scenarios across varied road networks.The section also introduces a simple vehicle-path model designed to work with the interaction model.Source: §III · p. 5
A. Parameterized intersection modeling
- Intersection parameters include arm count, forward and backward lane counts, arm angles, and lane width, with all road centerlines meeting at the origin.The model assumes equal lane widths and excludes an arm with zero forward and zero backward lanes simultaneously.Source: A. Parameterized intersection modeling · p. 5
- The study considers three-, four-, and five-arm intersections, with admissible directional variations represented for each topology.Figure 1 also depicts road centerlines, lane markings, boundaries, and off-road regions for a four-way intersection.Source: A. Parameterized intersection modeling · p. 5, Figure 1 · p. 5
- Lane markings and boundaries define the geometry; each forward lane's entrance point is where its center meets its road arm's entrance line.Exit points indicate leaving the intersection and are used to determine leader-follower relationships; their determination is coupled to the vehicle-path model.Source: A. Parameterized intersection modeling · pp. 5–6
- The parameterized intersection model represents right-hand traffic; left-hand traffic requires corresponding modifications.Forward lanes carry traffic entering the intersection, while backward lanes carry traffic moving away from it.Source: A. Parameterized intersection modeling · pp. 5–6
B. Vehicle path modeling
Vehicles follow pre-planned paths determined by their origin and target lanes, while adjusting speed to handle interactions. The section also defines vehicle kinematics and leader–follower priorities for intersection interactions.
B. Vehicle path modeling
- Origin and target lanes constrain legal turns and determine each vehicle’s pre-planned path through the intersection.The path is a smooth line–arc–line curve, with the arc tangent to the adjoining segments at the intersection entrance and exit.Source: B. Vehicle path modeling · p. 6
- A vehicle path P is a smooth three-segment curve from its origin-lane center to its target-lane center, with entrance and exit points marking intersection traversal.The first and third segments are lines, joined by an arc tangent to both at the entrance and exit; traveled distance ρ identifies a unique point on P.Source: B. Vehicle path modeling · p. 6
A. Vehicle kinematics
- Vehicle position and heading are derived from distance traveled along the planned path, while speed changes through finite acceleration choices at each time step.The vehicle is assumed to follow its pre-planned path perfectly; its dynamics are characterized by traveled distance, speed, and acceleration.Source: A. Vehicle kinematics · p. 7, Figure 2 · p. 7
- The vehicle state includes its path progress, speed, pose, and signed distances to the intersection entrance and exit.A negative signed distance indicates that the vehicle has entered or exited, respectively.Source: B. Vehicle path modeling · p. 6, A. Vehicle kinematics · p. 7
- Leader–follower priority uses right-of-way and turn rules, while a distance threshold accounts for drivers’ limited ability to distinguish close distances.Vehicles arriving from adjacent ways give priority to the vehicle on the right, and a straight-going vehicle leads a turning vehicle; ambiguous distances can leave both vehicles viewing themselves as followers.Source: A. Vehicle kinematics · p. 7
B. Reward function
The reward represents safety, separation, and progress toward a target, subject to common traffic rules. It combines predicted collision, separation, and speed terms over a finite horizon, and vehicles repeatedly apply the first acceleration of their optimized sequence.
B. Reward function
- Common traffic rules are incorporated in path planning and speed bounds, while each vehicle evaluates its interaction with other vehicles separately.After optimizing an acceleration sequence, the vehicle applies its first acceleration for one time step and repeats the decision process.Source: B. Reward function · pp. 7–8
- The reward combines collision avoidance, separation, and speed terms to represent driver goals at an intersection.The terms are weighted in a stage reward, and the cumulative reward discounts future stages over a prediction horizon.Source: B. Reward function · pp. 7–8
- Collision penalties are zero without c-zone overlap and increase with overlap area and vehicle speeds when collision danger is predicted.A tunable parameter adjusts the relative contribution of overlap area and speed; the formulation also imposes a minimum penalty for collisions.Source: B. Reward function · p. 8
- Separation is measured by overlap between vehicles’ s-zones, rectangles that extend beyond their c-zones with a safety margin.The s-zone dimensions may depend on whether the vehicle is acting as leader or follower in the pairwise interaction.Source: B. Reward function · p. 8, Figure 3 · p. 8
V. ADDITIONAL MODELING CONSIDERATIONS
The section introduces additional modeling considerations intended to represent human-driven vehicle behavior with higher fidelity.
V. ADDITIONAL MODELING CONSIDERATIONS
- The model adds several considerations to represent human-driven vehicle behavior with higher fidelity.The section discusses these additions after introducing the base model.Source: §V · p. 8
A. Courteous driving
The model adds courteous action constraints, limits interactions to vehicles within a perception range, and uses exploratory actions to address deadlocks caused by cyclic priority patterns.
A. Courteous driving
- Courteous driving removes actions that would cause a collision if other vehicles maintained their speeds.This is implemented by adjusting each vehicle’s action set.Source: A. Courteous driving · p. 8
B. Limited perception ranges
- A perception-distance limit reduces the number of vehicle pairs considered, lowering computational complexity and improving scalability.Each vehicle considers interactions only with other vehicles within its maximum perception distance.Source: B. Limited perception ranges · pp. 8–9
C. Breakage of deadlocks via exploratory actions
- When cyclic priority patterns leave conflicting vehicles stopped, random exploratory actions let vehicles probe whether they can go first.The strategy assigns probabilities of slight movement to vehicles in conflict after detecting that all have stopped and none chooses to move.Source: C. Breakage of deadlocks via… · p. 9
VI. AN ALTERNATIVE VEHICLE INTERACTIVE DECISION-MAKING MODEL
The alternative model uses finite level-K reasoning, with agents optimally responding to lower-level decisions, and adapts online when interacting agents’ levels are unknown.
VI. AN ALTERNATIVE VEHICLE INTERACTIVE DECISION-MAKING MODEL
- The authors compare the pairwise leader-follower model with adaptive level-K to illustrate robustness when interacting drivers’ styles are unknown.The alternative model is used in simulation case studies.Source: §VI · p. 9
- Level-K agents respond optimally to level-(K−1) decisions, while level-0 treats other vehicles as stationary obstacles.The paper describes level-0 as potentially representing an aggressive driver who assumes others will yield.Source: §VI · pp. 9–10
- Online estimation increases belief in a level model whose predicted acceleration best matches the observed acceleration, but cannot update beliefs when all models predict identically.The belief update is triggered only when at least one model prediction differs from the others.Source: §VI · p. 10
- The adaptive level-K model selects actions by maximizing expected reward across level combinations, weighted by the ego vehicle’s beliefs.The paper calls this combined decision and online-estimation approach the “adaptive level-K” model.Source: §VI · p. 10
VII. SIMULATION CASE STUDIES
The section presents simulation case studies illustrating the proposed framework and reports that the parameter values for all results are collected in Table I in Appendix B.
VII. SIMULATION CASE STUDIES
- Multiple simulation case studies illustrate the proposed game-theoretic framework for modeling vehicle interactions at uncontrolled intersections.The reported parameter values are collected in Table I in Appendix B.Source: §VII · p. 10
- Table I in Appendix B collects the parameter values used across the reported simulation results.Source: §VII · p. 10
- The case studies are presented as illustrations of the framework’s use for modeling vehicle interactions at uncontrolled intersections.Source: §VII · p. 10
A. Case study 1: Reproducing real-world traffic scenarios
The case studies show satisfactory reproduction of real-world traffic and conflict resolution in completely symmetric scenarios, where probing movements break deadlocks and vehicles proceed independently.
A. Case study 1: Reproducing real-world traffic scenarios
- The model reproduces three- and four-vehicle scenarios extracted from real-world video with satisfactory accuracy.Vehicles are initialized from the video’s positions and velocities; Fig. 4 and Fig. 5 show the corresponding scenarios.Source: A. Case study 1: Reproducing… · p. 10, Figure 4 · p. 11, Figure 5 · p. 11
B. Case study 2: Completely symmetric
- The symmetric tests use a four-way intersection: eight vehicles go straight in one case, while four vehicles make left turns in the other.Vehicles arrive with the same initial distance and speed, and use the pairwise leader-follower model with a deadlock-handling algorithm.Source: B. Case study 2: Completely symmetric · p. 11
- In the symmetric scenarios, probing breaks deadlocks and lets vehicles cross in sequence, demonstrating conflict resolution without centralized control.In the eight-vehicle case, the blue vehicle probes, becomes the overall leader, and crosses first; the remaining vehicles proceed clockwise.Source: Figure 6 · p. 11, B. Case study 2: Completely symmetric · pp. 11–12, Figure 7 · p. 12
C. Case study 3: Leader-follower versus adaptive level-K
The case studies contrast leader-follower decisions with adaptive level-K behavior and test the framework across randomly generated intersection layouts and traffic scenarios.
D. Case study 4: Randomized traffic scenarios
- Randomized tests cover 3-, 4-, and 5-arm intersections and 2, 4, 6, 8, or 10 vehicles, with 100 runs per intersection-arm and vehicle-count pair.Initial vehicle distances and speeds are sampled from [10, 28] m and m/s, respectively.Source: D. Case study 4: Randomized traffic… · pp. 12–13
C. Case study 3: Leader-follower versus adaptive level-K
- When it has right of way, the leader-follower model crosses first; in the contrasting setup, adaptive level-K can preempt a vehicle that should have priority.The simulations also show the leader-follower vehicle yielding when assigned a follower role and adapting to unexpected disruptions.Source: C. Case study 3: Leader-follower… · p. 12, Figure 8 · p. 13
D. Case study 4: Randomized traffic scenarios
- The illustrated randomized scenarios include three-way, four-way, and five-way intersection simulations.Source: Figure 9 · p. 13
1) Statistical evaluation:
The model reports lower failure rates than the scheme in in the cited six-vehicle comparison, with success rates above 0.9 for up to 10 vehicles at three-way and four-way intersections. Its decision-model computation grows linearly with the number of interacting vehicles, while total computation across vehicles grows quadratically.
1) Statistical evaluation:
- Success rates exceed 0.9 for up to 10 vehicles at three-way and four-way intersections, while the 10-vehicle five-way case has a success rate of 0.84.Collision and deadlock rates rise with the number of road arms and vehicles.Source: 1) Statistical evaluation · p. 14, Figure 10 · p. 14
- Most observed collisions follow simultaneous exploratory actions by multiple vehicles in deadlock scenarios.Algorithm 2 checks an acceleration against the case where conflicting vehicles remain stopped, but simultaneous accelerations can still collide; driver communication in deadlocks is not modeled.Source: 1) Statistical evaluation · p. 14
- 3% versus almost 50%: the framework’s failure rate is lower than the scheme in for six vehicles at four-way intersections.The cited failure cases include deadlock and collision scenarios.Source: 1) Statistical evaluation · p. 14, Figure 11 · p. 14
- Average completion time is measured for vehicles that reach their terminal points safely within 60 seconds and is used to reflect decision-making conservatism.Figure 12 shows average completion time, with black vertical bars indicating standard deviations.Source: 1) Statistical evaluation · p. 14, Figure 12 · p. 15
2) Computational complexity:
- Decision-model computation increases linearly with interacting vehicles, while total computation for all vehicles increases quadratically.Computation time rises with vehicle count, but its increase slows for four- and five-way intersections and as the number of road arms increases; the authors attribute this to fewer vehicles falling within one another’s perception ranges.Source: 2) Computational complexity · p. 15, Figure 13 · p. 15
VIII. SUMMARY
- The framework combines pairwise leader-follower decision-making with courteous driving, limited perception, and probing to represent human deadlock resolution across parametrized intersection layouts.The paper reports reasonable traffic behavior, LOS-matching average completion times, and linear growth in decision-model computation.Source: §VIII · p. 15
APPENDIX A
Appendix A describes intersection path segments using arc and line equations, with parameters determined from lane choices and intersection geometry.
APPENDIX A
- Appendix A represents a path with arc and line segments, and specifies how the arc parameters and exit radius are determined.The arc segment applies for ρ_en < ρ ≤ ρ_ex; a line equation applies for ρ > ρ_ex.Source: Appendix A · p. 17
APPENDIX B
- Table I is identified as a listing of simulation parameter values.Source: Table I · p. 17