⚡ electrical engineering

Data-Driven Reachability Analysis for Piecewise Affine Systems

This paper proposes a novel data-driven reachability analysis framework for piecewise affine hybrid systems that utilizes hybrid zonotopes to overcome boundary transition challenges and ensure accurate over-approximation of reachable sets in the presence of measurement noise.

Original authors: Peng Xie, Johannes Betz, Davide M. Raimondo, Amr Alanwar

Published 2026-02-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Peng Xie, Johannes Betz, Davide M. Raimondo, Amr Alanwar

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 predict where a very tricky, shape-shifting robot will be in the next few seconds. This robot doesn't just move in a straight line; it has different "personas." When it's in the kitchen, it moves like a clumsy turtle. When it's in the hallway, it zooms like a race car. When it hits the doorway (the boundary), it instantly switches from turtle to race car.

This is what engineers call a Piecewise Affine (PWA) system. It's a system that behaves differently depending on which "zone" it is in.

The problem? You don't have the robot's blueprints. You don't know the exact math for how the turtle moves or how the race car accelerates. All you have is a shaky video camera recording the robot's past movements, and the camera is a bit blurry (noisy data).

The Big Question: Can we guarantee that this robot will never crash into a fragile vase (an "unsafe region"), even though we don't know its exact rules and our data is imperfect?

This paper says: Yes, we can. Here is how they did it, explained simply:

1. The "Swiss Army Knife" of Shapes (Hybrid Zonotopes)

To track the robot, you need a shape that can wrap around all the possible places it could be.

Old way: Imagine trying to wrap a gift with a single, rigid box. If the robot moves from the kitchen to the hallway, the box either leaves part of the robot exposed (unsafe!) or is so huge it covers the whole room (useless!).
New way (This Paper): The authors invented a "Hybrid Zonotope." Think of this as a smart, stretchy, multi-compartment bubble wrap.
- It has "continuous" parts that stretch smoothly (for the robot's movement).
- It has "discrete" parts that snap into place (to handle the sudden switch from turtle to race car).
- This shape can hug the robot tightly, even when it jumps between zones, ensuring we never lose track of it.

2. Learning from a Shaky Video (Data-Driven)

Usually, to predict the future, you need the manual (the math equations). But here, the manual is missing.

The Analogy: Imagine trying to guess the rules of a board game just by watching someone play it on a shaky phone camera.
The Solution: The authors created an algorithm that looks at the "shaky video" (noisy input-output data) and builds a "family of possible rulebooks." Instead of guessing one set of rules, it creates a safe envelope containing all the rulebooks that could possibly explain what it saw. This ensures that even if the robot is following the worst-case scenario, our prediction still covers it.

3. The Three Ways to Check the Score (The Three Methods)

Once the robot moves and we get a new blurry photo, we need to update our "bubble wrap" to see where it is now. The paper proposes three different ways to do this math:

Reverse-Mapping (RM): Like working backward from the photo to draw the possible spots on the floor.
Implicit Intersection (IN): Like using a smart filter that squeezes the bubble wrap tighter by optimizing how much it shrinks.
Generalized Intersection (GI): Like adding new rules directly onto the bubble wrap to force it to fit the photo.

The Big Surprise: The authors proved that all three methods are mathematically identical. They are just three different dialects for saying the exact same thing.

Analogy: It's like asking for a glass of water. You can say "Water, please," "I'd like H2O," or "Can I have a drink?" The result is the same.
Performance: However, some dialects are faster to speak. The "Reverse-Mapping" method was the fastest, taking the least amount of computer time.

4. Why Does This Matter?

This isn't just about robots. This is about Safety.

Self-driving cars: They switch between "cruising," "braking," and "turning" modes. If the car doesn't know exactly how the brakes work in the rain, this method ensures it won't accidentally drive into a pedestrian.
Power grids: They switch between different energy sources. We need to know they won't crash the system.
Medical devices: They switch modes based on patient vitals. We need to guarantee they won't overdose a patient.

The Bottom Line

This paper gives us a new, super-accurate "safety net" for complex systems that change their behavior on the fly. Even if we don't know the exact rules and our data is messy, we can mathematically prove that the system will stay safe. It's like having a crystal ball that works even when the glass is cracked.

1. Problem Statement

The paper addresses the challenge of safety verification for Piecewise Affine (PWA) systems, a class of hybrid systems where continuous dynamics switch based on discrete modes (regions).

Core Challenge: Traditional reachability analysis requires precise mathematical models. However, in many real-world applications (e.g., autonomous vehicles, power grids), exact models are unavailable, and only noisy input-output data exists.
Specific Gap: Existing data-driven reachability methods (designed for linear or general nonlinear systems) fail to handle mode transitions in hybrid systems. At region boundaries where dynamics change abruptly, standard methods produce inaccurate over-approximations, leading to false alarms or missed safety violations.
Objective: Develop a data-driven framework to compute reachable sets (over-approximations of all possible future states) for PWA systems using only noisy measurement data, without prior knowledge of system matrices ( $A, B$ ), while rigorously handling boundary transitions and measurement noise.

2. Methodology

The authors propose a framework based on Hybrid Zonotopes, a set representation capable of capturing both continuous uncertainty and discrete mode switching.

A. Hybrid Zonotope Representation

The method utilizes Hybrid Zonotopes ( $Z_h$ ), which extend standard zonotopes by incorporating binary variables to represent discrete modes. This allows the set to represent the union of multiple polyhedral regions defined by different affine dynamics.

Operations: The paper defines algebraic operations for hybrid zonotopes, including Minkowski sum ( $\oplus$ ), intersection with linear maps ( $R$ ), and intersection with half-spaces ( $H^-$ ), which are essential for propagating sets through system dynamics and region boundaries.

B. Data-Driven Reachability (Input-State Data)

For systems where process noise exists but states are measured directly:

Model Identification: The authors extend a theorem from prior work to PWA systems. They partition data by operating mode and use matrix zonotopes to identify the set of all possible system matrices ( $[A_i, B_i]$ ) consistent with the noisy data.
Propagation Algorithm:
- Time Update: Compute the next state set by applying the identified family of models to the current state set and adding process noise.
- Boundary Handling: The algorithm explicitly intersects the propagated set with the specific region constraints ( $C_i$ ) of the PWA system. This ensures that trajectories crossing from one region to another are correctly split and propagated according to the new mode's dynamics.

C. Online Set-Based Estimation (Input-Output Data)

For scenarios where only input-output data is available (states are unobserved, and measurements are noisy), the paper extends the framework to include a Measurement Update step. It proposes and analyzes three mathematically equivalent methods to incorporate measurement constraints:

Reverse-Mapping (RM): Explicitly computes the state-space representation of the measurement constraint using Singular Value Decomposition (SVD) and intersects it with the predicted set.
Implicit Intersection (IN): Optimizes weight matrices to minimize the volume of the resulting set while satisfying measurement constraints, avoiding explicit SVD-based reconstruction.
Generalized Intersection (GI): Formulates measurement equations as additional linear constraints directly within the hybrid zonotope structure.

Key Theoretical Result: The paper provides a formal proof (Theorem 2) demonstrating that under conditions of full-rank measurement matrices and bounded noise, the RM, IN, and GI methods yield identical reachable sets, despite their different computational formulations.

3. Key Contributions

Hybrid Zonotope Framework: Introduction of a data-driven reachability method specifically designed for PWA systems that handles mode transitions and region boundaries without requiring a known mathematical model.
Boundary Transition Algorithm: Development of an algorithm that explicitly manages state-space partitioning, ensuring safety guarantees are maintained as trajectories cross region boundaries.
Three Equivalent Estimation Techniques: Proposal of three distinct methods (RM, IN, GI) for set-based state estimation with measurement noise, accompanied by a rigorous proof of their mathematical equivalence.
Comprehensive Evaluation: A complete framework for MIMO PWA systems that integrates process noise (input-state) and measurement noise (input-output) handling.

4. Results and Evaluation

The authors validated their approach using numerical benchmarks:

Reachability Validation: In a benchmark PWA system with two modes, the data-driven reachable sets (computed from noisy data) consistently over-approximated the analytically derived true reachable sets. This confirmed the method's ability to capture system behavior without prior model knowledge.
Estimation Equivalence: Numerical experiments confirmed that the RM, IN, and GI methods produced identical estimation bounds, verifying the theoretical equivalence proof. All three methods successfully contained the true state trajectory.
Computational Efficiency:
- The study observed an exponential growth in computation time as the time horizon increased, a known challenge in reachability analysis.
- Among the three estimation methods, Reverse-Mapping (RM) demonstrated the highest computational efficiency (lowest median time: ~0.025s), followed by GI and IN.
- The RM method outperformed the others across all statistical metrics (mean, variance, max time).

5. Significance

This work bridges a critical gap in the safety verification of cyber-physical systems:

Model-Free Safety: It enables safety verification for complex hybrid systems where accurate modeling is difficult or impossible, relying solely on data.
Robustness to Noise: By accounting for both process and measurement noise, the method provides rigorous safety guarantees suitable for real-world deployment.
Practical Application: The approach is directly applicable to safety-critical domains such as autonomous vehicles (where dynamics switch between road modes), power systems, and industrial control, offering a tool to prevent unsafe states even when system parameters are uncertain.
Future Directions: The paper sets the stage for analyzing more complex hybrid systems (e.g., Mixed Logical Dynamical systems) and investigating the coupling between partition boundaries and submodel parameters.