Falsify First, Certify Later: Active Training of Data-Driven Reachable Sets

Before we trust a learned controller on a robot, we would like to know every state the robot could end up in over the next few seconds, its reachable set. Exact reachable sets cannot be computed for most nonlinear systems. The field therefore settles for outer bounds. Formal tools give guaranteed but often very loose envelopes. Data-driven methods simulate many trajectories, fit a set around them, and check that set on held-out trajectories to obtain a statistical guarantee of the form "with confidence $1-\beta$, a new trajectory leaves the set with probability at most $\varepsilon$." The data-driven route is fast and often much tighter than formal bounds. Its weak point is that the trajectories are drawn at random, and most random trajectories land in the interior of the set, where they say nothing about where its boundary should be.

This note proposes a split between the two stages. An active learner chooses only the trajectories used to shape the set, and it acts as a falsifier: at each step it searches for initial conditions and disturbances whose trajectories escape the current set, then grows the set just enough to cover them. A separate pool of trajectories drawn passively at random is used to certify the set. Because certification never sees the actively chosen data, the statistical guarantee holds without modification, however aggressive the search was. The claim to test is that at a fixed simulation budget and a fixed certified violation level, falsifier-shaped sets are substantially smaller than passively fitted ones, and the gain grows with state dimension and with how rare the extreme trajectories are.

Core Claim and Why It Is Not Already Done

The certification machinery comes directly from Data-Driven Reachability with Scenario Optimization and the Holdout Method. That paper fits a minimum-volume set $\hat R = \{x : g(x) \le 1\}$, where $g$ is a sum of radial basis functions (smooth bump functions centred on chosen points), around $N$ training trajectories. It then counts the violations $k$ among $M$ fresh trajectories and inverts the binomial tail to get $\varepsilon$, with a $1/M$ rate when $k=0$. Both of its pools are passive, and the authors' own lemma shows that passive sampling is what makes tight bounds expensive in high dimension. The bound is valid for any $\hat R$ that is independent of the holdout set. This independence is the property our design relies on: we may build $\hat R$ however we like, provided the holdout stays untouched.

Active boundary search for reachable sets also exists. Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling introduces robUP!. It uses gradient ascent to push sampled trajectories away from the centre of the current convex hull, and it captures about 95% of true reachable volume with 2,000 samples, where Lipschitz-based bounds are up to 65 times more conservative. Its output, however, is an inner approximation that must be inflated by hand before it can be used for safety, and it is restricted to convex hulls. Exact Characterization of the Convex Hulls of Reachable Sets maps every boundary point of the hull to a direction on the unit sphere through an adjoint ODE. That gives quadratic convergence in direction spacing, but the directions are sampled uniformly and the method assumes smooth dynamics. Neither paper attaches a certificate to its actively found set. Our proposal differs in two ways. First, the active search maximizes the violation of a possibly non-convex learned set rather than the distance from a hull centre. Second, the result is wrapped in an unmodified holdout certificate, so no heuristic inflation is needed.

At the classifier level, On Improving Deep Active Learning with Formal Verification runs a verifier inside an active learning loop to generate diverse adversarial points. It discards any guarantee once the network is retrained, and it does not involve dynamics. We take the opposite stance: the guarantee is the product, and active learning serves only as a way to reach a tighter guaranteed set sooner.

The Mechanism

Let $\theta \in \Theta$ collect initial state, disturbance sequence and uncertain parameters, drawn from a known distribution $p$. Let $x_T(\theta)$ be the state at horizon $T$ given by a black-box simulator. Given the current set function $g$, the falsifier solves

$$ \theta^\star = \arg\max_{\theta \in \Theta} \; g\big(x_T(\theta)\big) + \lambda \log p(\theta), $$

by multi-start projected gradient ascent. It uses simulator gradients when they are available and finite differences or an ensemble surrogate when they are not. The first term rewards trajectories that escape the set. The second term, weighted by $\lambda \ge 0$, discourages chasing extreme trajectories that carry negligible probability mass.

The $\lambda$ term matters. The certified quantity is a $(1-\varepsilon)$-mass statement, not a worst-case one, so covering a vanishingly rare corner can make the set larger with no improvement in $\varepsilon$. $\lambda = 0$ recovers pure worst-case falsification in the spirit of robUP!, while large $\lambda$ collapses toward ordinary likely samples. Whenever $g(x_T(\theta^\star)) > 1$, the point is added and $g$ is refit by the same convex minimum-volume program used in the holdout paper. Falsification stops when restarts fail to find escapes or when the training budget is spent. Only then are $M$ passive trajectories simulated to certify.

The total simulator budget, meaning falsifier calls including gradient evaluations plus holdout calls, is matched against the baselines.

Research Program

The work has three parts. The first is a reusable implementation: a falsifier loop around the radial-basis-function set fitting, with plug-in simulators for the benchmarks below. The second is an analysis of when active shaping should help. Our hypothesis is that the gain is governed by how much of the true $(1-\varepsilon)$ boundary consists of low-probability tail trajectories that passive sampling rarely produces. The analysis should make this concrete by measuring, for each system, what fraction of holdout violations under passive training come from rarely visited regions of $\Theta$. The third is a study of the $\lambda$ knob and of how the training/holdout split should change when the training data are active. With active training, a smaller training share may suffice, which frees budget for $M$ and therefore tightens $\varepsilon$.

Baselines

The naive reference is the passive holdout method of Data-Driven Reachability with Scenario Optimization and the Holdout Method, run with the same set family, the same kernel-width tuning protocol (chosen on training data only), the same total simulator calls and the same $M$. It is also the strongest existing certified data-driven method in the file. On the Duffing oscillator it reports $\varepsilon = 0.018$ against $0.035$ for wait-and-judge scenario optimization at equal sample count. No reported set-volume number for it was found on Lacuna. We will reproduce its $\varepsilon$ first, and beating it means a smaller certified set volume at equal $\varepsilon$, or a lower $\varepsilon$ at equal volume, at equal budget.

The strongest active competitor is robUP! from Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling, whose reported figure is about 95% volume capture with 2,000 samples on the neural-network double integrator. To make it a fair certified competitor, we take its convex hull and certify it with the same passive holdout. On smooth low-dimensional systems we do the same with the adjoint-direction hulls of Exact Characterization of the Convex Hulls of Reachable Sets, giving each method the same simulator-call budget. Beating these means smaller certified volume, with the advantage expected mainly on non-convex reachable sets and in dimensions where uniform sphere tiling becomes infeasible.

The sound reference is a formal reachability tool (CORA, POLAR or JuliaReach, as used in ARCH-COMP23 Category Report: Artificial Intelligence and Neural Network Control Systems (AINNCS) for Continuous and Hybrid Systems Plants) run on the same horizon. It answers a different question, a deterministic guarantee, so it serves as a volume ceiling rather than a competitor.

The key ablation replaces the violation-seeking acquisition with random sampling and with ensemble-disagreement uncertainty sampling, both inside the identical loop. This isolates whether falsification specifically, rather than adaptivity in general, drives the gain. A second ablation sweeps $\lambda$ from zero upward.

Why not just…?

Why not just sample more random trajectories? In low dimension this is a real threat, since the holdout method is already cheap: 35–50 seconds on the 6D quadrotor. Our budget-matched curves will show where passive sampling catches up. We expect the advantage to grow in the 6D and 12D systems, because the holdout paper's own lemma ties sample needs to dimension exponentially. If the curves converge at realistic budgets, the honest conclusion is that active shaping is unnecessary for those systems.

Why not just run robUP! and certify its hull with a holdout set? This is the closest alternative and is included as a baseline. Two things could separate it from our method. robUP! maximizes distance from a centroid, which ignores probability mass and so may overcover rare corners. It also yields only a convex hull, which fills in holes in non-convex reachable sets. If it matches us on the attraction–repulsion system and on bifurcating dynamics, our contribution reduces to "certify robUP!", and we will report that.

Why not just use axis-aligned conformal boxes on final states? These are cheap and have exact coverage. However, Zono-Conformal Prediction: Zonotope-Based Uncertainty Quantification for Regression and Classification Tasks documents that boxes cannot follow correlated outputs and bloat volume. We include a conformal box as a cheap certified reference in the volume comparison.

Why not just use a formal reachability tool? Formal tools give stronger guarantees and reached 75% verification success in ARCH-COMP23. Their conservatism is the motivating problem, though: robUP! reports Lipschitz-style bounds up to 65 times looser. The formal volume ceiling in our tables makes this trade explicit.

Proposed Experiments

The benchmarks are the 2D Duffing oscillator and 6D quadrotor from the holdout paper, the neural-network double integrator from robUP!, the attraction–repulsion system (non-convex), and the TORA, unicycle and 12-state quadrotor plants from the ARCH-COMP23 report. For each, we plot certified set volume against total simulator calls at fixed $\beta = 10^{-3}$, and certified $\varepsilon$ against calls at fixed volume, over ten seeds. Ground-truth volume is estimated by very large Monte Carlo runs on the low-dimensional systems.

The decisive checks are threefold. First, falsifier-shaped sets must reach the passive method's $\varepsilon$ with clearly less volume or fewer calls on the 6D and 12D systems, not only on Duffing. Second, the empirical violation rate on a further massive independent test set must stay at or below the certified $\varepsilon$, which confirms that the active stage did not compromise validity. Third, the non-convex attraction–repulsion system must show an advantage over certified robUP! hulls. If the first check fails at all dimensions, the hypothesis is wrong.