⚡ electrical engineering

A Pragmatic Guide to Building Conservative Discrete Abstractions of Cyber-Physical Systems

This paper presents a pragmatic, conservative-by-construction workflow for building discrete abstractions of cyber-physical systems that ensures sound verification guarantees by addressing common pitfalls through a modular four-step process involving state-space partitioning, conservative transition construction, spurious behavior mitigation, and sound specification lifting.

Original authors: Jordan Peper, Krish Kapadia, James Gast, Ethan Howes, Ivan Ruchkin

Published 2026-08-12

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Jordan Peper, Krish Kapadia, James Gast, Ethan Howes, Ivan Ruchkin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to drive a car through a busy city. The real world is messy and continuous; the car can be at any exact spot on the road, moving at any exact speed, and turning at any exact angle. But computers, especially the ones that need to prove a robot is safe before it ever moves, struggle with infinite possibilities. They work best with finite lists, like a board game with a fixed number of squares. This is the heart of Cyber-Physical Systems (CPS): the marriage of digital brains and physical bodies. To check if a robot will crash, engineers use a method called symbolic model checking. Think of this as a super-precise detective that checks every single possible move a robot could make to ensure it never hits a wall. But to do this, the detective needs to turn the smooth, flowing real world into a blocky, step-by-step map. This process is called discrete abstraction.

The tricky part is that if you make the map too simple, you might miss a real danger (the robot crashes in reality but looks safe on the map). If you make the map too complicated, the detective gets overwhelmed and can't finish the job. The goal is to build a map that is "conservative"—meaning it might imagine some dangers that don't actually exist (pessimism), but it will never miss a real danger. This paper is a guide for engineers on how to build these maps correctly, avoiding common traps that lead to false safety guarantees.

The Blueprint for a Safe Robot Map

This paper acts as a pragmatic field guide for building "conservative" maps of complex machines. The authors, a team from the University of Florida, argue that while turning a continuous robot into a blocky game is necessary for safety checks, many engineers accidentally build maps that are either too dangerous (missing real risks) or too paranoid (imagining risks that aren't there). They propose a four-step workflow to build these abstractions "by construction," ensuring the map is always safe by design.

Step 1: Cutting the World into Tiles

First, you have to turn the smooth, infinite state space (where the robot can be anywhere) into a grid of finite tiles. Imagine taking a giant, continuous sheet of graph paper and cutting it into distinct, non-overlapping squares. Each square represents a "tile" or an abstract state. The authors suggest using a uniform grid, like a checkerboard, where you decide how many tiles you want along each dimension (length, width, angle). If you choose 10 tiles for each of the three dimensions of a unicycle robot, you end up with 1,000 total tiles ( $10 \times 10 \times 10$ ). This step ensures that every possible real-world position the robot could be in is covered by at least one tile.

Step 2: Drawing the Arrows (The Tricky Part)

Now you need to figure out which tiles the robot can jump to from its current tile. This is where the paper offers three different tools, each with a different flavor of "conservatism":

The Bounding Box (AABB): Imagine the robot is in a tile. You calculate where it could possibly end up after one second. To be safe, you draw the smallest possible rectangle (axis-aligned bounding box) that completely surrounds all those possible future spots. If this rectangle touches a neighboring tile, you draw an arrow to that tile. It's like wrapping the robot's future in a big, clumsy box. It's fast, but the box might be too big, creating "fake" arrows to tiles the robot could never actually reach.
The Polytope: This is a tighter, more flexible shape (like a stretched rubber sheet) that fits the robot's future more closely than a box. It's more accurate but takes more computing power to calculate.
The Sampling Method (PAC): Instead of calculating every possibility, you throw darts. You pick random starting points inside the tile, simulate where the robot goes, and record the arrows you see. The paper introduces a clever "certificate" (a statistical guarantee) that says, "We are 99% confident that we have seen every arrow that happens more than 1% of the time." This is great for complex, black-box robots where you can't write down a perfect formula, but it relies on probability rather than absolute proof.

Step 3: Cleaning Up the "Fake" Paths

Because the methods in Step 2 are conservative, they often create spurious transitions—arrows that look like they exist on the map but are impossible in reality. Worse, they often create self-loops, where the map says the robot can stay in the same tile forever. This is a nightmare for safety checks because if a robot can stay in a tile forever, it might never reach its goal, even if it could in real life.

The paper suggests two ways to clean this up:

CEGAR (Counterexample-Guided Abstraction Refinement): If the safety checker finds a "fake" path where the robot crashes, the system splits the tiles along that path to make the map more detailed, effectively erasing the fake path.
Self-Loop Erasure: The authors show how to prove that a robot must leave a tile within a certain number of steps. If you can prove the robot can't stay forever, you can safely delete the "stay here forever" arrow. They tested this on a "Mountain Car" problem and a "Unicycle" robot, showing that removing these fake loops significantly improved the accuracy of the safety checks.

Step 4: Translating the Rules

Finally, you have to translate the safety rules from the real world to the blocky map. If the rule is "Stay within the city limits," on the real map, this means "Don't touch the edge." On the blocky map, the rule changes. The paper explains how to use "May" and "Must" logic. A rule "Must" be true for a tile only if every point in that real-world tile satisfies the rule. A rule "May" be true if at least one point satisfies it. By carefully translating the rules, they ensure that if the robot passes the test on the blocky map, it is guaranteed to be safe in the real world.

What They Found

The authors tested this four-step pipeline on three different scenarios: a simple synthetic system, a "Mountain Car" (a classic reinforcement learning challenge), and an autonomous unicycle.

They found that the sampling-based method (Step 3) often produced the cleanest maps with the fewest fake arrows and self-loops, especially for complex, non-linear robots like the unicycle. While the "bounding box" method was faster to build, it created so many fake paths that the safety checker had a harder time proving the robot was safe.

Crucially, they showed that removing self-loops (Step 3) made a huge difference. For the unicycle, simply deleting the fake "stay forever" arrows improved the success rate of the safety check from about 19% to over 60% in some cases. This proves that a slightly more complex map that is "cleaner" is often better than a simple map full of fake possibilities.

The paper concludes that by following this structured, conservative workflow—partitioning the space, building transitions carefully, cleaning up fake paths, and translating rules correctly—engineers can build digital twins of physical robots that are trustworthy. They don't claim to have solved every problem in robotics, but they provide a clear, tested recipe for avoiding the most common mistakes that lead to unsafe or useless safety checks.

Technical Summary: A Pragmatic Guide to Building Conservative Discrete Abstractions of Cyber-Physical Systems

Problem Statement

Cyber-physical systems (CPS) operate in safety-critical environments where failures can threaten life and property. While symbolic model checking is an effective method for verifying complex temporal-logic properties, it requires a finite-state model. Real-world CPS, however, evolve over continuous state spaces. To apply model checking, engineers must discretize these continuous dynamics into a finite-state abstraction.

The core challenge lies in ensuring soundness: verification guarantees derived from the abstract model must transfer to the concrete system. This requires the abstraction to be a conservative over-approximation of the concrete state space and behaviors. In practice, model builders frequently encounter four pitfalls that compromise soundness or introduce excessive pessimism:

Under-covering the concrete state space.
Under-approximating the transition relation (omitting feasible behaviors).
Unsound pruning of "degenerate" behaviors (e.g., removing self-loops without certification).
Improper specification lifting, failing to preserve the logical implication from abstract satisfaction to concrete satisfaction.

These issues often lead to "spurious" counterexamples where the abstract model violates a specification that the concrete system actually satisfies, rendering verification useless.

Methodology

The paper proposes a four-step, modular workflow for constructing conservative discrete abstractions. The workflow is "conservative-by-construction," meaning soundness is maintained at every stage through specific mathematical guarantees.

Step 1: State-Space Abstraction

The continuous state space $X$ is partitioned into a finite set of abstract states $\hat{X}$ using a uniform rectilinear grid. A quantization function $\psi: X \to \hat{X}$ maps concrete states to abstract cells. The inverse mapping $\Psi(\hat{x})$ defines the concrete region (preimage) of each abstract state. This step ensures that every concrete state and initial condition has a representative in the abstract model.

Step 2: Conservative Transition Construction

The paper presents three interchangeable methods for computing the transition relation $\hat{f}$ (i.e., determining which abstract states can follow others), ensuring that every concrete transition is represented in the abstract model:

Axis-Aligned Bounding Box (AABB): Computes the bounding box of the image of a concrete cell under the system dynamics. Any abstract cell intersecting this box is added as a successor. This is computationally efficient but can be overly conservative for nonlinear systems.
Polytope Propagation: Uses a polytope (convex hull) to over-approximate the image of the concrete cell. This is tighter than AABB for nonlinear dynamics but computationally more expensive. It employs AABB culling to filter candidates before performing expensive polytope intersection tests.
Sampling with PAC Certificates: For black-box or highly nonlinear systems, transitions are discovered by sampling the state space. Instead of a deterministic guarantee, this method provides a Probably Approximately Correct (PAC) guarantee. It certifies that with high confidence ( $1-\delta$ ), the constructed transition relation includes all "significant" transitions (those occurring with probability $\ge \beta$ ), bounding the "missing mass" of unobserved transitions.

Step 3: Mitigation of Degenerate Behaviors

Conservative abstractions often introduce spurious transitions (transitions impossible in the concrete system) and self-loops (transitions from a state to itself). These can cause false negatives in verification, particularly for liveness properties.

Spurious Transitions: Addressed via Counterexample-Guided Abstraction Refinement (CEGAR). If a counterexample trajectory is found in the abstract model, the algorithm validates it against the concrete dynamics. If the trajectory is spurious (the reachable set becomes empty), the state space is refined (split) to eliminate the false transition.
Self-Loops: Addressed via Certified Self-Loop Erasure. A self-loop is removed only if it can be certified that every concrete trajectory starting in that cell escapes within a finite number of steps ( $K$ ). This is verified either by iterating reachable-set propagation or via a sampling-based strategy with a PAC guarantee.

Step 4: Sound Lifting of LTL Specifications

To verify the abstract model, the Linear Temporal Logic (LTL) specification $\phi$ defined on the concrete space must be lifted to an abstract specification $\hat{\phi}$ . The paper employs may-must semantics:

Must predicates: An atomic proposition holds on an abstract state only if it holds for all concrete states in that cell.
May predicates: An atomic proposition holds if it holds for at least one concrete state.
The lifting operator $\rho$ transforms $\phi$ into $\hat{\phi}$ by strengthening atomic propositions to "must" (for safety) or weakening them to "may" (as appropriate for the logic structure), ensuring that $\hat{s} \models \hat{\phi} \implies s \models \phi$ .

Key Contributions

A Pragmatic Workflow: A unified, four-step pipeline that integrates state partitioning, transition construction, degenerate behavior mitigation, and specification lifting into a single sound framework.
Interchangeable Subroutines: The methodology supports multiple approaches for transition construction (AABB, Polytope, Sampling) and degenerate behavior removal (CEGAR, Certified Erasure), allowing users to balance computational cost with abstraction tightness.
PAC Guarantees for Sampling: Introduces a data-driven approach for transition construction that provides rigorous probabilistic coverage certificates (via the Good-Turing estimator and McAllester-Schapire bounds) for systems where analytical over-approximation is intractable.
Systematic Handling of Degeneracy: Explicitly addresses the removal of spurious self-loops and transitions through certified erasure and CEGAR, preventing the pessimism that typically plagues conservative abstractions.

Experimental Results

The authors evaluated the pipeline on three case studies: a synthetic linear system, the Mountain Car benchmark (nonlinear, learned policy), and an Autonomous Unicycle (Dubins model).

Transition Construction: Sampling-based methods generally produced sparser transition relations with fewer self-loops and lower successor-count variability compared to AABB and Polytope methods, particularly for nonlinear systems. This led to higher True Positive Rates (TPR) in verification.
Self-Loop Erasure: Removing self-loops significantly improved verification outcomes. For the Unicycle case, TPR increased from ~0.19 to ~0.63 after erasure. In the Mountain Car case, TPR improved from ~0.83 to ~0.93.
CEGAR: While CEGAR substantially increased model size and construction time, it consistently reduced the self-loop proportion (SLP). It yielded pronounced TPR improvements for the Mountain Car system but had minimal impact on the Unicycle system, where high SLP was attributed to trivial counterexamples difficult to eliminate without targeted erasure.
Granularity: Finer state-space granularities consistently yielded higher TPR, confirming the trade-off between model size and verification accuracy.

Significance

The paper claims significance as a pragmatic guide for engineers and researchers building abstractions for CPS. It addresses the gap between theoretical abstraction techniques and practical implementation by:

Providing a sound-by-construction workflow that prevents common errors leading to unsound verification.
Offering modular tools that allow practitioners to choose between deterministic (AABB/Polytope) and probabilistic (Sampling) methods based on system complexity and available computational resources.
Demonstrating that mitigating degenerate behaviors (spurious transitions and self-loops) is not merely an optimization but a critical step for achieving meaningful verification results, particularly for liveness properties.

The authors conclude that while symbolic model checking is powerful, its utility for CPS depends entirely on the quality of the abstraction. This workflow provides a rigorous, adaptable framework to achieve that quality while balancing pessimism with tractability.