PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Stress Testing for Autonomous Vehicles

Mark Koren, Saud Alsaif, Ritchie Lee, Mykel J. Kochenderfer

arXiv:1902.01909v1cs.ROcs.AIcs.LGstat.ML

TL;DR

Autonomous-vehicle validation must search a vast space of scenarios where direct sampling rarely finds failures. This paper formulates failure discovery as adaptive stress testing over a Markov decision process, using MCTS and DRL with a modular simulator. DRL finds more-likely failure scenarios more efficiently than MCTS.

  • Problem

    Validation is challenging because autonomous vehicles operate across a vast space of driving scenarios that road tests alone cannot adequately cover.

  • Method

    The paper formulates failure discovery as adaptive stress testing over a Markov decision process and uses MCTS and DRL with a modular autonomous-vehicle simulation framework.

  • Results

    DRL finds more-likely failure scenarios than MCTS and requires less than 1% of MCTS’s STEP calls across all scenarios.

  • Takeaways & Limitations

    The framework supports simulation testing of vehicle sensors and decision systems, with interchangeable simulator components.

Abstract

from arXiv · show

This paper presents a method for testing the decision making systems of autonomous vehicles. Our approach involves perturbing stochastic elements in the vehicle's environment until the vehicle is involved in a collision. Instead of applying direct Monte Carlo sampling to find collision scenarios, we formulate the problem as a Markov decision process and use reinforcement learning algorithms to find the most likely failure scenarios. This paper presents Monte Carlo Tree Search (MCTS) and Deep Reinforcement Learning (DRL) solutions that can scale to large environments. We show that DRL can find more likely failure scenarios than MCTS with fewer calls to the simulator. A simulation scenario involving a vehicle approaching a crosswalk is used to validate the framework. Our proposed approach is very general and can be easily applied to other scenarios given the appropriate models of the vehicle and the environment.

I. INTRODUCTION

The paper addresses the difficulty of validating autonomous-vehicle decision systems across a vast scenario space by adapting adaptive stress testing and introducing deep reinforcement learning as a solver. It also presents a modular simulation framework and reports that AST finds high-probability failure scenarios efficiently.

  • Validation is difficult because autonomous vehicles face a vast space of driving scenarios that road tests alone cannot adequately cover.
  • Adaptive stress testing formulates failure-scenario discovery as a Markov decision process and searches for most-likely failures.
  • The paper introduces deep reinforcement learning as an alternative AST solver alongside Monte Carlo tree search.
  • The proposed autonomous-vehicle simulation framework interfaces with AST and allows decision systems, sensor models, and dynamics models to be exchanged.
  • AST successfully finds high-probability failure scenarios, while the experiments report that DRL finds better solutions more efficiently than MCTS.

B. Monte Carlo Tree Search

The paper uses MCTS and DRL as reinforcement-learning solvers for the MDP underlying adaptive stress testing. MCTS searches by forward simulation, whereas DRL represents its policy with a neural network and updates it from trajectory-based policy gradients.

  • Monte Carlo Tree Search: MCTS builds a search tree by sampling states and using forward simulation to estimate state and action values.Double progressive widening regulates tree branching when state or action counts are large.
  • Deep Reinforcement Learning: DRL represents the policy πθ(s) with a feed-forward neural network whose outputs parameterize a Gaussian action distribution.The covariance matrix is diagonal, separately parameterized, and independent of state.
  • Deep Reinforcement Learning: Generalized Advantage Estimation estimates the policy gradient from batches of simulation trajectories.
  • Deep Reinforcement Learning: Trust Region Policy Optimization updates the policy by constraining KL divergence.The paper states that TRPO generally gives monotonic increases in policy performance.

D. Adaptive Stress Testing

Adaptive stress testing treats a black-box simulator and an event region as a sequential decision problem: the solver selects environment actions, the simulator returns transition likelihood and event status, and rewards guide subsequent actions. Fixing stochastic elements makes the resulting trajectory deterministic for a chosen action sequence.

  • AST takes a generative simulator S and an event-state subset E as inputs, with the simulator containing the vehicle, other-agent, and environment models.
  • The solver controls simulation through INITIALIZE, STEP, and ISTERMINAL, which reset the simulator, advance it, and detect events or horizon termination.
  • Because actions fix the simulator’s stochastic elements, replaying an action history deterministically revisits the corresponding state.The action sequence a0:t−1 represents state st in this formulation.
  • The AST objective is to find the most likely trajectory leading to an event in E.Environment actions control the adversarial elements and uniquely determine scenario evolution.
  • The solver-simulator loop converts transition likelihood and event occurrence into rewards that determine subsequent environment actions.

III. AUTONOMOUS VEHICLES APPLICATION

The autonomous-vehicle AST framework separates the simulator, driving algorithm, sensors, tracker, solver, and scenario definition into interchangeable components. MCTS and DRL generate environment actions through different sampling procedures within this modular architecture.

  • III. AUTONOMOUS VEHICLES APPLICATION: The framework separates the driving algorithm, sensors, tracker, solver, and scenario definition into components that can be interchanged.This modularity supports comparing alternative implementations and more sophisticated models.
  • III. AUTONOMOUS VEHICLES APPLICATION: The solver outputs environment actions, which update AST-controlled participants before sensing, tracking, and driving-model decisions update the vehicle.The simulator returns transition information and an event indicator to the reward function.
  • III. AUTONOMOUS VEHICLES APPLICATION: The simulator modules can be swapped to test different scenarios, systems under test, or sensor configurations.
  • III. AUTONOMOUS VEHICLES APPLICATION: MCTS uses pseudorandom seeds to generate environment actions, whereas DRL outputs a distribution that is sampled for those actions.Both solver methods produce the environment actions supplied to the simulator.

B. Problem Formulation

The evaluation uses a crosswalk scenario with one autonomous vehicle and three initial-configuration variations. These variations demonstrate basic AST behavior, different collision trajectories, and scalability to multiple pedestrians.

  • B. Problem Formulation: The evaluation stresses a vehicle approaching a pedestrian crosswalk in a two-lane neighborhood-road scenario without other traffic.The scenario was intentionally simplified for pedagogical illustration and uses road and crosswalk dimensions based on California regulations.
  • B. Problem Formulation: Three initial configurations include one pedestrian in two variants and two pedestrians in a third variant.The study presents data from each pedestrian across the three scenario variations.
  • B. Problem Formulation: The first configuration demonstrates AST, the second shows different collision trajectories from changed initial conditions, and the third examines scalability with more participants.

1) Environment Models:

The environment model represents pedestrian actions as stochastic accelerations and sensor-noise perturbations, allowing AST to search over pedestrian motion and measurement disturbances. Pedestrians are modeled with a zero-mean multivariate Gaussian whose covariance parameters control lateral acceleration, longitudinal acceleration, and noise.

  • 1) Environment Models:: Each pedestrian action contains acceleration components and noise applied to measured velocity and position components.The action vector is represented consistently across the two solvers, although their sampling procedures differ.
  • 1) Environment Models:: AST controls pedestrian motion and sensor noise to search for likely collisions involving both environmental actions and hardware failures.
  • 1) Environment Models:: The solvers receive different state information: MCTS treats the simulator as a black box and distinguishes states using prior pseudorandom-seed history, while DRL takes simulation state as input.
  • 1) Environment Models:: The pedestrian action model is a multivariate Gaussian N(µa, Σ) with zero mean and diagonal covariance.Its diagonal parameters correspond to lateral acceleration, longitudinal acceleration, and sensor noise.
  • 1) Environment Models:: The pedestrian model uses σaLat = 0.01, σaLon = 0.1, and σnoise = 0.1.The zero-mean assumption implies that pedestrians hold course on average; location- or attention-dependent distributions are identified as future work.

2) Sensor and Tracker Models:

The sensor model converts participant states into noisy measurements, and an alpha-beta tracker filters those measurements before they reach the autonomous vehicle's driving model.

  • 2) Sensor and Tracker Models:: Sensors receive participant-state vectors and output noisy measurement vectors for the pedestrians.
  • 2) Sensor and Tracker Models:: An alpha-beta tracker filters the sensor measurements before passing them to the system under test.
  • 2) Sensor and Tracker Models:: The tracker parameters are αtracker = 0.85 and βtracker = 0.005.

3) System Under Test Model:

The system under test uses the Intelligent Driver Model to maintain lane-following and safe-distance behavior, adapted to respond to pedestrians at crosswalks.

  • The SUT is based on the Intelligent Driver Model, designed to stay in one lane and safely follow traffic.
  • 25 miles per hour (11.17 m/s) is set as the desired velocity for following crosswalk rules.
  • The adapted IDM treats the closest pedestrian in the road as the target vehicle and follows a safe distance behind.
  • Relative x velocity and relative x distance to the closest pedestrian determine the SUT's acceleration at the next time step.

4) Modified Reward Function:

The modified reward function uses Mahalanobis distance to proxy action probability and adds distance-based shaping to encourage near-collision pedestrian behavior during failed trials.

  • Mahalanobis distance proxies the probability of an action by measuring its distance from the multivariate mean.
  • The no-collision penalty is a very large negative number rather than −∞.
  • A distance-scaled end-of-trial penalty encourages pedestrians to finish failed trials closer to the vehicle and speeds convergence.
  • M(a, µ_a | s) measures the distance between action a and expected action µ_a given state s.
  • DIST(p_v, p_p) gives the distance between the vehicle position and closest pedestrian position.

5) Metrics:

The AST solvers are evaluated by collision-trajectory likelihood and simulator-step calls, with results indicating that DRL finds failure scenarios far more efficiently than MCTS.

  • The two evaluation metrics are final collision-trajectory likelihood and the number of calls to the STEP function.
  • MCTS uses depth, horizon T, and iterations to control state-space exploration; the study uses horizon 100 and 2000 iterations.
  • DRL results use batch size 4000, step size 0.1, and discount factor 0.99.
  • Both solvers identify collision trajectories and converge to solutions in a tractable number of simulator steps.
  • MCTS STEP-call counts average 100 single runs and multiply that average by 100 to represent calls needed for confidence in results.
  • Across all scenarios, DRL requires orders of magnitude fewer STEP calls than MCTS, using less than 1% of MCTS's calls.

B. Trajectories

The trajectories show how MCTS and DRL generate collision scenarios differently, with DRL producing more probable paths and greater efficiency. The results also reveal that collision scenarios may not always diagnose vehicle-system changes.

  • Scenario comparisons: DRL produces smoother, slightly more likely pedestrian paths than MCTS in scenario 1 because less acceleration is needed.In scenario 1, MCTS turns sharply after nearly stopping, whereas DRL follows a smoother path.
  • Scenario comparisons: Scenario 3 shows the largest trajectory difference: DRL minimizes the first pedestrian’s reward effect through a slight turn followed by low-acceleration motion.MCTS couples pedestrian actions through a single seed, limiting its ability to minimize the first pedestrian’s contribution to total reward.
  • Interpretation and scope: Scenarios 1 and 3 assign collision blame to the pedestrian, so they do not directly inform modifications to the system under test.The paper proposes restricting the event set to collisions for which the system bears responsibility, requiring formal responsibility and blame models.
  • Solver performance: DRL finds more-probable failure scenarios than MCTS with substantially fewer simulator STEP calls.The table also reports reward without noise to illustrate MCTS’s difficulty eliminating sensor noise.
  • Framework contribution: The framework extends adaptive stress testing to autonomous vehicles and uses modular components that can be adapted for simulated sensor or decision-system testing.Its components include interchangeable vehicle, sensor, and environment models.
Loading 1902.01909v1…