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.
The process follows four key steps:
- Lofi Discovery: AST is run in a low-fidelity simulator to identify "candidate failures."
- 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.
- 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.
- 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.
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