Occupancy-Guided Refinement for Stochastic Abstractions

Controllers for noisy physical systems, such as a thermostat that must keep a building comfortable or a robot that must reach a goal without collisions, can come with a formal guarantee. The usual route replaces the continuous system with a finite grid model, solves the control problem on the grid, and uses a stochastic simulation relation to bound how far the real system can drift from the grid model. That relation is a certificate that the real trajectory stays within distance $\epsilon$ of the grid trajectory except with per-step probability $\delta$. Today the grid is fixed in advance, and $\epsilon$ and $\delta$ are single global numbers. One badly behaved region therefore forces fine resolution everywhere, and compute and memory grow exponentially with dimension.

This note proposes making the error budget local. Each grid cell gets its own $\delta$, and the guarantee is re-derived so that the satisfaction probability lost to abstraction equals the per-step error summed along the trajectories the controller actually produces. That one inequality supplies two things. The first is a refinement rule: split the cells where the controlled system spends its time and where $\delta$ is large. The second is a pruning rule: within the remaining time window, cells the controller will rarely visit can stay coarse or be dropped. The probability mass those cells carry is charged to the guarantee explicitly instead of being thrown away as an untracked heuristic.

Core Claim

Robust Dynamic Programming for Temporal Logic Control of Stochastic Systems builds a Bellman-style backward recursion over the grid model in which a uniform $\delta$ is subtracted at every step. It shows the resulting loss in satisfaction probability scales with the mean time to hit the target set, not with the horizon length. We claim this result generalizes to a cell-dependent $\delta(\hat{s})$:

$$ p_{\text{true}} \;\ge\; p_{\text{abs}} - \mathbb{E}\Big[\textstyle\sum_{k=0}^{\tau-1} \delta(\hat{s}_k)\Big] - \eta_{\text{prune}} . $$

The symbols are defined as follows. $p_{\text{abs}}$ is the satisfaction probability computed on the grid model. $\hat{s}_k$ is the grid state at step $k$ under the synthesized controller. $\tau$ is the step at which the specification automaton accepts or rejects. $\eta_{\text{prune}}$ is the total probability mass routed through pruned cells, which are treated pessimistically as violations.

With constant $\delta$, the bound reduces to $\delta\,\mathbb{E}[\tau]$, which is the mean-hitting-time result. With varying $\delta$, the expectation is a sum over cells of expected visits times $\delta$. Refinement should therefore target cells with large expected visits times $\delta$, not cells with large local error alone. The proof is expected to follow by applying the per-step coupling argument cell by cell and summing the failure events along the path, using a union bound over steps. Whether the interface function, which maps grid inputs to continuous inputs, can maintain a cell-dependent $\epsilon$ is the main technical risk. The fallback is to keep $\epsilon$ constant within each refinement level and let only $\delta$ vary freely.

Relation to Prior Work

Three existing systems each supply one ingredient and each lack the others.

FAUST2 already refines grids adaptively. It splits cells where a Lipschitz bound on the transition density gives large local error, but its guarantees are finite-horizon and it has no simulation-relation certificate. Our rule differs because it weights local error by how often the controlled system visits each cell. A high-error cell that the controller never enters is left coarse.

SySCoRe supplies the certificate machinery and non-growing infinite-horizon bounds for co-safe temporal logic, meaning specifications whose satisfaction is decided after finitely many steps. Its grids are static, and computing the relation takes over half its runtime. Local, lazy computation of the relation therefore attacks its dominant cost.

Lazy Abstraction-Based Controller Synthesis shows that refining only along the active search frontier cuts runtime by about 78% on a deterministic unicycle. It has no account of noise. Our expected-visit weighting is the stochastic analogue of "the frontier."

Temporal Logic Control for Stochastic Linear Systems using Abstraction Refinement of Probabilistic Games refines only cells whose outcome is still undecided. However, it handles only probability-one satisfaction, which yields nothing under Gaussian noise when the achievable probability is below one.

The pruning half of the proposal takes its motivation from temporal-graph search. A Chronological Edge-Driven Approach to Temporal Subgraph Isomorphism prunes a search branch the moment a candidate falls outside its time window. Span-core Decomposition for Temporal Networks prunes the space of time intervals using a containment property: anything that holds on an interval holds on every sub-interval. Both work on discrete deterministic graphs.

The pruning half takes its constraint from AMYTISS. AMYTISS discards low-probability transitions using a fixed cutoff that has no link to the guarantee, and it must disable the cutoff under multiplicative noise. We replace that cutoff with window-indexed expected visits. A cell can be pruned at stage $k$ only if its expected visits over the remaining window, times its contribution, fits inside an explicit budget $\eta_{\text{prune}}$, and that budget then appears in the bound.

Research Program

We will build the algorithm as a loop over five steps, implemented on SySCoRe's tensor-based pipeline.

The loop starts from a coarse box partition crossed with the automaton that encodes the specification. Second, it runs robust dynamic programming with cell-wise $\delta$. Third, it computes the expected visits to each cell under the resulting controller. This is one forward pass on the finite chain, at roughly the cost of a single value-iteration sweep.

Fourth, the loop splits the top cells by expected-visit-weighted $\delta$. It also splits cells whose $\epsilon$-neighbourhood crosses a region boundary in the specification, since such cells blur which region of the specification the state is in. The new cells' relation is recomputed locally, because SySCoRe's coupling is constructed per transition. Fifth, it repeats until the bound stops improving per unit of compute.

For specifications that contain time windows or deadlines, expected visits are indexed by the remaining time. Cells, and stages of the backward recursion, whose window-indexed visit mass falls below budget are frozen. This prunes along the time axis, which AMYTISS processes strictly in sequence.

The analysis has three parts. We will prove the displayed bound. We will characterize when the expected-visit weighting is a sound proxy for the controller that refinement will eventually produce, given that refinement changes the controller and hence the visits. Finally, we will establish monotone improvement of the bound under a conservative variant that only ever splits cells.

Baselines

The naive reference point is a uniform grid with global $\epsilon$ and $\delta$ in SySCoRe. We run it at the finest resolution that fits the same memory and wall-clock budget as our method. Our method beats it if it achieves a higher certified lower bound at equal compute, or equal certified probability with fewer cells.

The strongest existing method on the problems SySCoRe handles is SySCoRe itself. On the 7D building automation benchmark, it reports a certified satisfaction probability of at least 0.9035 in about 122 seconds after reduction to a 2D model. We rerun it on the same hardware with the same reduced model. Our method beats it if it certifies at least 0.9035 in clearly less time, or certifies a higher probability within 122 seconds.

For high-dimensional reach and safety problems, the strongest competitor is AMYTISS on a GPU uniform grid. The file reports a 692,000x speedup over FAUST2 on a 3D room-temperature network and success on the 7D BMW parking model. No reported absolute runtime was found on Lacuna for AMYTISS on these benchmarks, so we will measure AMYTISS and our method on the same GPU. We will report AMYTISS both with its probability cutoff enabled, alongside a post-hoc estimate of the guarantee it loses, and with the cutoff disabled.

For the deterministic special case, Lazy ABCS reports 609 seconds on the unicycle reach-avoid task. We will run our method with noise set to zero as a sanity check that it reduces to a comparably efficient lazy scheme.

Three ablations isolate the key ingredients. The first replaces expected-visit weighting with FAUST2-style unweighted local error. The second disables window-indexed pruning. The third prunes with a fixed probability cutoff that is not charged to the bound. All arms share one implementation, one compute budget, and one number of refinement rounds tuned on a held-out benchmark.

Why not just…?

Why not just use GPU parallelism on a uniform grid, as AMYTISS does? This is a real threat in three or fewer dimensions, where a dense grid fits in memory and GPU throughput may beat any adaptive bookkeeping. AMYTISS still processes the time axis in sequence, and its savings come from a cutoff that is not certified. The decisive test is the dimension sweep in the experiments. If our method does not reach a better certified bound per GPU-second by four to seven dimensions, the adaptive machinery is not justified.

Why not just refine where local error is largest, as FAUST2 does? That is exactly the first ablation. The displayed bound predicts that unweighted refinement wastes cells in regions the controller avoids, such as cells deep inside obstacles or past the target. If the two rules give similar bounds per cell, expected-visit weighting adds nothing and we will say so.

Why not just reduce the model order, as SySCoRe does on the building benchmark? Model-order reduction works when the dynamics project well onto a lower-dimensional space, as the 7D building model does. It is complementary to our method, which runs on the reduced model in that benchmark. On the Van der Pol oscillator and a noisy unicycle, localized nonlinearity is expected to make a single projection's $\epsilon$ large. We will report the bound with model-order reduction alone against model-order reduction plus our refinement.

Why not just refine the undecided cells of a probabilistic game? Under Gaussian noise the probability-one winning set used by the probabilistic-game approach is empty whenever the achievable probability is below one. That covers every benchmark here with a target such as 0.9.

Proposed Experiments

Benchmarks are drawn from the file: Van der Pol, building automation, and package delivery from SySCoRe; 2D and 3D room temperature from FAUST2 and AMYTISS; 7D BMW parking from AMYTISS; and a stochastic version of the unicycle reach-avoid task. We add deadline-windowed variants of the room-temperature and package-delivery specifications to exercise temporal pruning.

The metrics are the certified lower bound, wall-clock time, peak memory, and the number of grid cells. We also report how much of the guarantee is lost to pruning ($\eta_{\text{prune}}$) versus to $\delta$, and we validate each certified bound against Monte Carlo estimates from rollouts of the continuous system.

Four checks decide whether the idea works. First, the cell-wise bound must never exceed the Monte Carlo estimate; any violation falsifies the theory. Second, expected-visit weighting must beat unweighted refinement in certified probability at fixed cell count on at least the nonlinear benchmarks. Third, charged pruning must deliver speedups on the windowed specifications while keeping $\eta_{\text{prune}}$ small. The uncharged cutoff should be shown to overstate its guarantee by a measurable margin. Fourth, the comparison against AMYTISS across dimensions must locate the crossover point, if one exists, where adaptivity pays for itself.