Finding Failures in High-Fidelity Simulation using Adaptive Stress Testing and the Backward Algorithm

Mark Koren, Ahmed Nassar, Mykel J. Kochenderfer

Introduction

Validating the safety of autonomous systems, such as self-driving cars, necessitates the use of high-fidelity (hifi) simulators. These environments model complex sensor noise, realistic physics, and the full software stack. However, the computational cost of running these simulations is prohibitive. Finding safety-critical failures in such a "haystack" is slow and expensive, often costing significant time and resources per simulation second.

Researchers often employ Adaptive Stress Testing (AST), a reinforcement learning (RL) technique, to identify the most likely scenarios leading to a crash. While effective, RL typically requires thousands of iterations, making it intractable in hifi environments. Conversely, low-fidelity (lofi) simulators are fast but prone to "spurious failures"—crashes that occur due to simplified physics rather than actual system flaws.

Methodology: The Backward Algorithm

To bridge this gap, this paper proposes a multi-fidelity approach combining AST with the Backward Algorithm (BA). The core idea is to find a "needle" in a cheap lofi simulator first, then use that discovery to guide the search in the hifi environment.

System architecture for Adaptive Stress Testing (AST) showing the interaction between the solver, simulator, and reward function.

The process follows four key steps:

  1. Lofi Discovery: AST is run in a low-fidelity simulator to identify "candidate failures."
  2. The Backward Algorithm: Treating the lofi failure as an "expert demonstration," the BA guides the hifi agent's exploration. This algorithm was originally designed for hard exploration problems in RL.
  3. Hifi Adaptation: The hifi agent begins training near the end of the lofi failure trajectory. Once a hifi failure is found from this late starting point, the starting point is moved incrementally back toward the beginning of the scenario.
  4. Spurious Failure Rejection: If a hifi failure cannot be found near the lofi demonstration within a set budget, the lofi failure is rejected as spurious, saving computational resources.

Case Studies and Evaluation

The method was evaluated using a "pedestrian crossing" scenario where a vehicle must react to a pedestrian entering a crosswalk. Four synthetic case studies represented common fidelity gaps:

  • Time Discretization: Differences in step sizes (0.5s vs 0.1s).
  • Dynamics: Low-precision vs. 32-bit precision state variables.
  • Tracker: Presence or absence of an alpha-beta filter in the perception stack.
  • Perception: Simple abstraction vs. complex LIDAR-based occupancy grids (DOGMa).

The approach was also demonstrated on NVIDIA DriveSim, an industry-standard high-fidelity simulator.

Key Results

The proposed BA-based method significantly outperformed standard Deep RL (DRL) baselines. In the "Dynamics" case study, the BA found a hifi failure using only 6.1% of the simulation steps required by the hifi-only baseline.

Performance comparison in the Dynamics case study showing significant reduction in steps to failure when using the Backward Algorithm.

In the most complex "Perception" scenario involving LIDAR modeling, the BA achieved a ~21x speedup, finding a failure in just 4.7% of the baseline steps. Furthermore, when applied to NVIDIA DriveSim, the system identified a failure in just 10 hours, proving its viability for real-world engineering pipelines. Interestingly, failures found via the BA often had higher likelihood scores, indicating they were more realistic than those found by scratch-trained agents.

Conclusion

By using lofi simulations as a "hint," the Backward Algorithm transforms a thousand-step exploration problem into a series of manageable one-step problems. While the approach may introduce search bias toward lofi-like failures, its efficiency gains—up to 20x—make it a powerful tool for autonomous system validation. Future work will explore transfer learning and meta-learning to further bridge the simulation gap.

Summary updated

BibTeX
@inproceedings{koren2021finding,
  author = {Mark Koren and Ahmed Nassar and Mykel J. Kochenderfer},
  title = {{Finding Failures in High-Fidelity Simulation using Adaptive Stress Testing and the Backward Algorithm}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2021},
  doi = {10.1109/iros51168.2021.9636072},
}
Figure