PaperlayerView exact revision on arXiv

Source-linked AI summary

Game-Theoretic Modeling of Driver and Vehicle Interactions for Verification and Validation of Autonomous Vehicle Control Systems

Nan Li, Dave Oyler, Mengxuan Zhang, Yildiray Yildiz, Ilya Kolmanovsky, Anouck Girard

arXiv:1608.08589v1cs.AIcs.GT

TL;DR

Autonomous-vehicle control systems require costly verification and validation for safe, comfortable operation amid uncertain, interacting traffic. The paper develops a scalable game-theoretic and reinforcement-learning traffic simulator, demonstrating quantitative policy comparison and controller-parameter calibration. Its case studies show how simulated traffic outcomes support safety-and-performance evaluation and optimization.

  • Problem

    Verification and validation of autonomous-vehicle control systems is costly because safe operation must be assessed in uncertain traffic involving interacting vehicles and drivers.

  • Method

    The paper combines a scalable game-theoretic traffic model with reinforcement learning to represent multi-vehicle interactions and generate driver policies for simulation.

  • Results

    The simulator is used to quantitatively compare autonomous-vehicle control policies and optimize controller parameters using simulated traffic outcomes.

  • Takeaways & Limitations

    The proposed simulation environment provides a venue for testing autonomous-vehicle decision and control systems and calibrating existing controllers before road tests.

Abstract

from arXiv · show

Autonomous driving has been the subject of increased interest in recent years both in industry and in academia. Serious efforts are being pursued to address legal, technical and logistical problems and make autonomous cars a viable option for everyday transportation. One significant challenge is the time and effort required for the verification and validation of the decision and control algorithms employed in these vehicles to ensure a safe and comfortable driving experience. Hundreds of thousands of miles of driving tests are required to achieve a well calibrated control system that is capable of operating an autonomous vehicle in an uncertain traffic environment where multiple interactions between vehicles and drivers simultaneously occur. Traffic simulators where these interactions can be modeled and represented with reasonable fidelity can help decrease the time and effort necessary for the development of the autonomous driving control algorithms by providing a venue where acceptable initial control calibrations can be achieved quickly and safely before actual road tests. In this paper, we present a game theoretic traffic model that can be used to 1) test and compare various autonomous vehicle decision and control systems and 2) calibrate the parameters of an existing control system. We demonstrate two example case studies, where, in the first case, we test and quantitatively compare two autonomous vehicle control systems in terms of their safety and performance, and, in the second case, we optimize the parameters of an autonomous vehicle control system, utilizing the proposed traffic model and simulation environment.

I. INTRODUCTION

The paper proposes a scalable game-theoretic traffic model for simulating interacting human-driven and autonomous vehicles, addressing the costly verification and validation of autonomous-vehicle control systems. It uses simulation to compare control policies and calibrate controller parameters in multi-vehicle scenarios.

  • 275 million miles without fatality have been estimated as necessary to match the reliability rate of human-driven cars, motivating simulation-based testing and calibration.
  • The proposed model represents multiple human-driven and autonomous vehicles as simultaneous decision makers in computationally tractable, many-move traffic scenarios.
  • The approach combines game theory for intelligent-agent interactions with reinforcement learning to evolve those interactions over time.
  • The simulator supports quantitative comparison of autonomous-vehicle control algorithms using safety and performance metrics.
  • A case study uses probabilistic traffic outcomes to optimize the calibration of an autonomous-vehicle controller.
  • The modeled problem concerns same-direction traffic on a 3-lane highway, while the method is intended to handle scenarios with more cars and lanes.

A. Physical models

The physical model represents vehicles with discrete-time longitudinal and lateral motion, bounded acceleration choices, lane-change assumptions, partial observations, and a reward function encoding safety, performance, comfort, and effort.

  • A. Physical models: Vehicle motion uses longitudinal acceleration and lateral velocity as control inputs, with discrete-time position and velocity updates.
  • A. Physical models: Vehicles use nominal or hard acceleration and deceleration levels, while lane changes maintain longitudinal velocity and continue to completion once started.
  • B. Observation space: Drivers observe discretized ranges and range rates for nearby vehicles, together with lane information, rather than exact distances for all traffic.
  • C. Action space: The seven basic actions include maintaining speed and lane, accelerating or decelerating at nominal or hard rates, and changing lanes left or right.
  • D. Reward function: The reward function combines constraint violation, velocity, headway, and effort metrics through weights that can vary with driver aggressiveness.
  • D. Reward function: Effort penalties discourage unnecessary maneuvers, especially hard acceleration or deceleration, while safety can justify those actions when needed.

E. Constraints

The interaction model imposes hard constraints that remove unsafe lane-change actions in specified nearby-vehicle configurations, while policies map observations probabilistically to actions.

  • E. Constraints: Hard constraints make selected lane changes unavailable when a neighboring vehicle is parallel, close, and approaching.
  • E. Constraints: The constraints prevent left or right lane changes based on the corresponding neighboring vehicle’s position and approach state.
  • E. Constraints: The interaction model represents driver behavior as a stochastic policy assigning action probabilities to observations.

A. Hierarchical decision making

The interaction model represents drivers with different reasoning levels, then uses reinforcement learning to derive policies for a partially observed multi-agent decision problem.

  • Hierarchical reasoning: Level-0 drivers act reflexively without considering other agents’ probable actions, while higher levels reason about progressively higher-level driver policies.A level-1 driver assumes others are level-0; a level-2 driver assumes others are level-1.
  • Hierarchical reasoning: A level-0 policy can be initialized by random action selection or a simple minimally reasonable policy.This study specifies deceleration, hard deceleration, or maintaining speed based on the front car’s proximity and approach state.
  • Policy learning: Reinforcement learning assigns values to observed message-action pairs using accumulated rewards and increases probabilities for higher-reward actions.Policy evaluation and policy improvement form the two main RL steps.
  • Policy learning: Because each driver observes only part of the Markov traffic state, the learning problem is treated as a Partially Observable Markov Decision Process.The Jaakkola algorithm is used because it provides convergence to at least a local maximum under this setting.
  • Policy learning: The driver policy is updated iteratively from value and Q-value estimates until the average reward converges.The learned policy maps observations, or messages, probabilistically to actions.

C. The role of hierarchical decision making in obtaining driver policies

The paper obtains scalable driver policies through hierarchical training and uses the resulting traffic model to evaluate autonomous-driving control approaches in interactive scenarios.

  • Policy training: Training a level-k driver uses level-(k-1) policies for all other vehicles, progressing from a level-0 policy to higher reasoning levels.The trained driver is the learner; other traffic and automation form its environment.
  • Control evaluation: The simulator compares Stackelberg and decision-tree autonomous-driving approaches while surrounding traffic follows game-theoretic driver policies.The controlled vehicle is evaluated against drivers modeled by the proposed interaction framework.
  • Control evaluation: Acceleration and deceleration actions were added because a faster test vehicle facing three slower cars cannot avoid collision risk through lane changes alone.The modified action space includes harder braking and faster acceleration than the earlier approaches.
  • Stackelberg policies: Stackelberg policies assign the controlled vehicle as leader and two vehicles behind it as followers, whose actions are selected sequentially.The leader maximizes utility against the followers’ worst-case actions.
  • Scope and assumptions: The model omits distance-measurement uncertainty, side-viewing, and response delays, although the authors state these aspects can be integrated.Its vehicle dynamics also differ from those used in the referenced Stackelberg studies.

B. Decision tree policies

The decision-tree controller evaluates short action sequences, while the simulator accounts for traffic responses and triggers planning according to spatial thresholds around the test vehicle.

  • Decision-tree policy: The decision-tree path planner evaluates pre-selected action profiles by expanding potential action sequences and scoring each branch with a specified metric.The planner selects among candidate profiles rather than using a single predetermined action.
  • Decision-tree policy: A two-layer tree with seven actions per layer evaluates 49 two-action profiles using a weighted sum of rewards from both layers.The first-layer action from the highest-total-reward profile is applied at each step.
  • Decision-tree policy: During profile evaluation, the controlled vehicle assumes other vehicles maintain their actions throughout the prediction horizon.The evaluation metric uses the same reward function employed to train level-k policies.
  • Interactive simulation: Unlike the deterministic planning assumption in prior work, the simulator models both the controlled vehicle responding to traffic and traffic responding to its actions.This makes the planning environment interactive rather than independent of the controlled vehicle.
  • Path-planner triggering threshold: The controller accelerates with no cars in region A, triggers path planning with cars in A but none in B, and enters Safe Mode when cars occupy region B.Regions A and B are positioned to detect nearby vehicles and lane-entry threats while reducing unnecessary action evaluations.

V. RESULTS

The simulator models multi-vehicle traffic with discrete longitudinal actions, lane changes, partial observations, and constraint-based episode termination. Its setup randomizes traffic configurations and assigns policies before iteratively observing, acting, and updating vehicle states.

  • Environment model: Vehicles use 3.6 m lanes, 6 m × 2 m safe zones, discrete accelerations of ±2.5 or ±5 m/s², and 2 s lane changes.Cars remain centered in lanes except during lane changes, while longitudinal velocity stays constant during lateral maneuvers.
  • Initialization: The simulation configuration specifies lane and car counts, maximum initialization distance, and duration before randomly placing vehicles and assigning level-0, level-1, or level-2 policies.Initial speeds are sampled uniformly from 62–98 km/h, with at least 30 m between cars.
  • Simulation loop: Each episode repeatedly obtains observations, selects an action from the assigned policy, updates position and velocity, and ends when time expires or a constraint violation occurs.The procedure initializes time at t = 0 and runs while t < t_f.
  • Observation space: The test vehicle observes five nearby cars using close, nominal, or far ranges and approaching, stable, or moving-away range rates within a 63 m visibility limit.Cars beyond visual range are unobservable and treated as far and moving away.
  • Example setup: The example three-lane setup depicts safe zones, relative velocities, lane index, and directional observations for surrounding vehicles.The test vehicle is located in the center lane at x = 0.
  • Observation limitations: Two cars in the example are unobservable because one lies beyond visual range and another is hidden, illustrating the problem’s POMDP observation limitations.The front-center car is actually stable despite being observed as moving away.

B. Level-0 driver behavior

Level-0 behavior is trained through reinforcement learning in simulated environments, with conservative fallback behavior for poorly visited observations. The simulator presents the resulting vehicle state and control actions through a user interface.

  • Simulation interface: The level-0 results section presents simulated driving behavior and the simulator user interface.The interface distinguishes the red trainee/test vehicle from yellow traffic vehicles.
  • Simulation interface: The interface visualizes travel direction, speed, lateral motion, and pedal activation around the test vehicle.A speedometer, steering wheel, gas pedal, and brake pedal communicate vehicle motion and control inputs.
  • Policy learning: Policy training evaluates actions using observation and action value functions, initializes action probabilities equally, and increases the probability of the maximizing action when Q(m, a) > V(m).The probability increment is 0.01 before normalization.
  • Training environments: The observation space contains 311 observations, and training samples both sparse and dense traffic by randomizing the number of cars.The number of cars is selected uniformly from 0 to n_c^max.
  • Policy learning: Level-k training initializes other cars with level-(k−1) policies, evaluates the trainee, improves the policy, and assigns level-0 behavior to insufficiently trained cases.This procedure is repeated for the desired number of training cycles.

D. Level-k driver interactions

Level-1 and level-2 policies produce distinct responses to surrounding vehicles, reflecting different reasoning levels in multi-vehicle interactions. Higher-level evaluation occurs in more difficult traffic and yields higher observed violation rates for level-2 cars.

  • Level-1 behavior: A level-1 car responds to an approaching vehicle by decelerating, steering, changing lanes, and stabilizing its headway.The lane change completes after 2 s, and the sequence is described as reasonable driving behavior.
  • Level-2 behavior: A level-2 car brakes or maintains speed when nearby vehicles create uncertainty about lane changes, rather than accelerating whenever the lane ahead is clear.It decelerates when another vehicle moves into its lane.
  • Violation evaluation: The violation-rate comparison varies the number of traffic cars across 10,000 simulations per case, with level-2 tested among level-1 vehicles and level-1 among level-0 vehicles.Constraint violation means another vehicle enters the test car’s safe zone.
  • Violation evaluation: The level-2 test car experiences higher violation rates than the level-1 test car, partly because level-1 traffic is harder to predict than level-0 traffic.The comparison therefore reflects both policy level and the different surrounding traffic environments.

E. A comparative quantitative evaluation of Stackelberg and decision tree policies

The study compares Stackelberg and decision tree controllers for safety, driving performance, and computational load in simulated traffic. The decision tree performs better on safety and speed in the reported comparisons, but requires more computation.

  • Safety comparison: In level-0 traffic, both Stackelberg and decision tree policies perform well, with no observed constraint violations.Level-0 vehicles do not change lanes in this environment.
  • Safety comparison: In mixed-level traffic, both controllers exhibit significant distance constraint violation percentages.The simulations last 200 s and use 10,000 runs, while some violations may also arise from level-k drivers.
  • Evaluation setting: The interacting-driver traffic model is more complex than the models used to develop the Stackelberg and decision tree algorithms.The paper notes that few prior control-policy studies consider traffic of similar complexity.
  • Density effects: Constraint violation rates first increase and then decrease with traffic density as sparse traffic permits free motion and very dense traffic reduces speed and lane changes.The reported pattern links the decrease at high density to traffic-jam behavior.
  • Performance comparison: The decision tree policy has better average-travel-speed performance than the Stackelberg policy.Average travel speed is used as the driving-performance metric.
  • Computational cost: The decision tree evaluates 49 two-layer action profiles, giving it higher computational load than the Stackelberg policy.The reported computational times are average runtimes for 200 s simulations measured on a desktop implementation.

F. Optimal autonomous driving controller calibration

The traffic simulator supports simulation-based calibration of autonomous driving controller parameters by optimizing a reward function that combines safety and performance. For maximum safety, the resulting optimization identifies a parameter pair that lowers constraint violations relative to the original selection.

  • Calibration objective: The decision tree policy is calibrated by optimizing two parameters whose effects on safety and performance are difficult to set from intuition.The parameters are the layer-weight ratio wl1/wl2 and the longitudinal size xB of region B, which triggers the path planner.
  • Calibration objective: The reward function maximizes a user-weighted combination of safety and performance over 200-second simulations with 20 cars.Its terms use constraint violation rate and average speed bounded by vmin and vmax; p1 and p2 select the relative emphasis.
  • Optimization results: Fig. 16 presents reward surfaces over wl1/wl2 and xB for four reward-weight selections: (1,0), (0,1), (0.7,0.3), and (0.6,0.4).The surfaces are used to select the best parameter pair for each reward design.
  • Optimization results: 27.5% constraint violation results from the optimized pair (2.5, 23) under maximum safety, versus 31.8% for the original pair (2, 21).The comparison uses p1 = 1 and p2 = 0 in the 20-car traffic scenario.

VI. SUMMARY

The paper presents a hierarchical reasoning game-theoretic approach and a level-k traffic simulator for modeling interactive driver behavior. The simulator supports autonomous-driving algorithm testing, challenging-scenario discovery, and simulation-based parameter calibration.

  • VI. SUMMARY: The proposed method models interacting driver behavior under given traffic conditions using hierarchical reasoning game theory.It provides a way to simulate interactive driver behavior in traffic.
  • VI. SUMMARY: A traffic simulator based on level-k driver models supports testing and verification of autonomous-driving algorithms.It can also help discover challenging trajectories and scenarios for future autonomous-vehicle testing.
  • VI. SUMMARY: The simulator supports parameter calibration of autonomous-vehicle control policies through simulation-based optimization.The demonstrated policies are evaluated in terms of safety and performance.
Loading 1608.08589v1…