# Adaptive Splitting of Reusable Temporal Monitors for Rare Traffic Violations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 50 references that are in the map.
- First posted on arXiv 13 Mar 2024.

## Builds on (most cited first, 21 of 21)

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space](https://mlsanity.com/paper/1706.02413/) (2017)
- [PointPillars: Fast Encoders for Object Detection from Point Clouds](https://mlsanity.com/paper/1812.05784/) (2018)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [Neural Importance Sampling](https://mlsanity.com/paper/1808.03856/) (2018)
- [Scalable End-to-End Autonomous Vehicle Testing via Rare-event Simulation](https://mlsanity.com/paper/1811.00145/) (2018)
- [A Survey of Algorithms for Black-Box Safety Validation of Cyber-Physical Systems](https://mlsanity.com/paper/2005.02979/) (2020)
- [Accelerated Evaluation of Automated Vehicles Safety in Lane Change Scenarios Based on Importance Sampling Techniques](https://mlsanity.com/paper/1605.04965/) (2016)
- [Robust Online Monitoring of Signal Temporal Logic](https://mlsanity.com/paper/1506.08234/) (2015)
- [Neural Bridge Sampling for Evaluating Safety-Critical Autonomous Systems](https://mlsanity.com/paper/2008.10581/) (2020)
- [Evaluating Trajectory Collision Probability through Adaptive Importance Sampling for Safe Motion Planning](https://mlsanity.com/paper/1609.05399/) (2016)
- [A Two-Stage Optimization-based Motion Planner for Safe Urban Driving](https://mlsanity.com/paper/2002.02215/) (2020)
- [Scalable Autonomous Vehicle Safety Validation through Dynamic Programming and Scene Decomposition](https://mlsanity.com/paper/2004.06801/) (2020)
- [Testing Rare Downstream Safety Violations via Upstream Adaptive Sampling of Perception Error Models](https://mlsanity.com/paper/2209.09674/) (2022)
- [Interaction-Aware Behavior Planning for Autonomous Vehicles Validated with Real Traffic Data](https://mlsanity.com/paper/2101.05985/) (2021)
- [PEM: Perception Error Model for Virtual Testing of Autonomous Vehicles](https://mlsanity.com/paper/2302.11919/) (2023)
- [Certifiable Deep Importance Sampling for Rare-Event Simulation of Black-Box Systems](https://mlsanity.com/paper/2111.02204/) (2021)
- [A Control Architecture for Provably-Correct Autonomous Driving](https://mlsanity.com/paper/2105.02759/) (2021)
- [Elliptical Slice Sampling for Probabilistic Verification of Stochastic Systems with Signal Temporal Logic Specifications](https://mlsanity.com/paper/2203.00078/) (2022)
- [Online Monitoring of Dynamic Systems for Signal Temporal Logic Specifications with Model Information](https://mlsanity.com/paper/2203.16267/) (2022)

## Abstract (arXiv)

Autonomous Vehicles (AVs) are often tested in simulation to estimate the probability they will violate safety specifications. Two common issues arise when using existing techniques to produce this estimation: If violations occur rarely, simple Monte-Carlo sampling techniques can fail to produce efficient estimates; if simulation horizons are too long, importance sampling techniques (which learn proposal distributions from past simulations) can fail to converge. This paper addresses both issues by interleaving rare-event sampling techniques with online specification monitoring algorithms. We use adaptive multi-level splitting to decompose simulations into partial trajectories, then calculate the distance of those partial trajectories to failure by leveraging robustness metrics from Signal Temporal Logic (STL). By caching those partial robustness metric values, we can efficiently re-use computations across multiple sampling stages. Our experiments on an interstate lane-change scenario show our method is viable for testing simulated AV-pipelines, efficiently estimating failure probabilities for STL specifications based on real traffic rules. We produce better estimates than Monte-Carlo and importance sampling in fewer simulations.