  Extracting interesting scenarios from real-world data as well as generating
failure cases is important for the development and testing of autonomous
systems. We propose efficient mechanisms to both characterize and generate
testing scenarios using a state-of-the-art driving simulator. For any scenario,
our method generates a set of possible driving paths and identifies all the
possible safe driving trajectories that can be taken starting at different
times, to compute metrics that quantify the complexity of the scenario. We use
our method to characterize real driving data from the Next Generation
Simulation (NGSIM) project, as well as adversarial scenarios generated in
simulation. We rank the scenarios by defining metrics based on the complexity
of avoiding accidents and provide insights into how the AV could have minimized
the probability of incurring an accident. We demonstrate a strong correlation
between the proposed metrics and human intuition.
