# Scalable Autonomous Vehicle Safety Validation through Dynamic Programming and Scene Decomposition

arXiv: https://arxiv.org/abs/2004.06801 · HTML: https://mlsanity.com/paper/2004.06801/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2020.

## Built on by (most cited first, 8 of 8)

- [Testing Rare Downstream Safety Violations via Upstream Adaptive Sampling of Perception Error Models](https://mlsanity.com/paper/2209.09674/) (2022)
- [Intersection focused Situation Coverage-based Verification and Validation Framework for Autonomous Vehicles Implemented in CARLA](https://mlsanity.com/paper/2112.14706/) (2021)
- [Model-based Validation as Probabilistic Inference](https://mlsanity.com/paper/2305.09930/) (2023)
- [Large Foundation Models for Trajectory Prediction in Autonomous Driving: A Comprehensive Survey](https://mlsanity.com/paper/2509.10570/) (2025)
- [Scalable Safety-Critical Policy Evaluation with Accelerated Rare Event Sampling](https://mlsanity.com/paper/2106.10566/) (2021)
- [A Deep Reinforcement Learning Approach to Rare Event Estimation](https://mlsanity.com/paper/2211.12470/) (2022)
- [Adaptive Splitting of Reusable Temporal Monitors for Rare Traffic Violations](https://mlsanity.com/paper/2405.15771/) (2024)
- [Coverage Aware Active Evaluation for Failure Discovery with Paired Systems](https://mlsanity.com/paper/2608.13719/) (2026)

## Abstract (arXiv)

An open question in autonomous driving is how best to use simulation to validate the safety of autonomous vehicles. Existing techniques rely on simulated rollouts, which can be inefficient for finding rare failure events, while other techniques are designed to only discover a single failure. In this work, we present a new safety validation approach that attempts to estimate the distribution over failures of an autonomous policy using approximate dynamic programming. Knowledge of this distribution allows for the efficient discovery of many failure examples. To address the problem of scalability, we decompose complex driving scenarios into subproblems consisting of only the ego vehicle and one other vehicle. These subproblems can be solved with approximate dynamic programming and their solutions are recombined to approximate the solution to the full scenario. We apply our approach to a simple two-vehicle scenario to demonstrate the technique as well as a more complex five-vehicle scenario to demonstrate scalability. In both experiments, we observed an increase in the number of failures discovered compared to baseline approaches.