Scalable Autonomous Vehicle Safety Validation through Dynamic Programming and Scene Decomposition

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