# TTT: A Temporal Refinement Heuristic for Tenuously Tractable Discrete Time Reachability Problems

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 22 references that are in the map.
- First posted on arXiv 19 Jul 2024.

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

- [Hamilton-Jacobi Reachability: A Brief Overview and Recent Advances](https://mlsanity.com/paper/1709.07523/) (2017)
- [OVERT: An Algorithm for Safety Verification of Neural Network Control Policies for Nonlinear Systems](https://mlsanity.com/paper/2108.01220/) (2021)
- [Reachable Set Estimation for Neural Network Control Systems: A Simulation-Guided Approach](https://mlsanity.com/paper/2004.12273/) (2020)
- [Decomposition of Reachable Sets and Tubes for a Class of Nonlinear Systems](https://mlsanity.com/paper/1611.00122/) (2016)
- [Backward Reachability Analysis of Neural Feedback Loops: Techniques for Linear and Nonlinear Systems](https://mlsanity.com/paper/2209.14076/) (2022)
- [One-Shot Reachability Analysis of Neural Network Dynamical Systems](https://mlsanity.com/paper/2209.11827/) (2022)
- [A Hybrid Partitioning Strategy for Backward Reachability of Neural Feedback Loops](https://mlsanity.com/paper/2210.07918/) (2022)
- [DRIP: Domain Refinement Iteration with Polytopes for Backward Reachability Analysis of Neural Feedback Loops](https://mlsanity.com/paper/2212.04646/) (2022)
- [Successor Sets of Discrete-time Nonlinear Systems Using Hybrid Zonotopes](https://mlsanity.com/paper/2210.09902/) (2022)

## Built on by (most cited first, 3 of 3)

- [Constraint-Aware Refinement for Safety Verification of Neural Feedback Loops](https://mlsanity.com/paper/2410.00145/) (2024)
- [BURNS: Backward Underapproximate Reachability for Neural-Feedback-Loop Systems](https://mlsanity.com/paper/2505.03643/) (2025)
- [Learning Verifiable Control Policies Using Relaxed Verification](https://mlsanity.com/paper/2504.16879/) (2025)

## Abstract (arXiv)

Reachable set computation is an important tool for analyzing control systems. Simulating a control system can show general trends, but a formal tool like reachability analysis can provide guarantees of correctness. Reachability analysis for complex control systems, e.g., with nonlinear dynamics and/or a neural network controller, is often either slow or overly conservative. To address these challenges, much literature has focused on spatial refinement, i.e., tuning the discretization of the input sets and intermediate reachable sets. This paper introduces the idea of temporal refinement: automatically choosing when along the horizon of the reachability problem to execute slow symbolic queries which incur less approximation error versus fast concrete queries which incur more approximation error. Temporal refinement can be combined with other refinement approaches as an additional tool to trade off tractability and tightness in approximate reachable set computation. We introduce a temporal refinement algorithm and demonstrate its effectiveness at computing approximate reachable sets for nonlinear systems with neural network controllers. We calculate reachable sets with varying computational budget and show that our algorithm can generate approximate reachable sets with a similar amount of error to the baseline in 20-70% less time.