Introduction
Hybrid systems, which integrate continuous physical dynamics with discrete control logic, are fundamental to modern cyber-physical systems (CPS). However, verifying the safety of these systems through reachability analysis—determining all possible states the system can reach—is computationally intensive. This paper introduces a novel framework that significantly accelerates this process for systems governed by periodic, time-triggered controllers, achieving speedups of up to 5,000x compared to previous state-of-the-art methods.
The Challenge of Fast-Switching Systems
In many CPS applications, such as automotive braking, digital controllers sample system states at high frequencies. Traditional reachability analysis tools struggle with these "fast-switching" systems because they typically treat the clock as a standard state variable. This approach necessitates frequent, costly geometric operations (e.g., set conversions between zonotopes and polytopes) at every transition, leading to a "complexity explosion" that makes long-term verification computationally prohibitive.
Methodology: Decoupling Time and Space
The core innovation presented is the decoupling of the timing of discrete events from the continuous state dynamics. Since transitions in these systems are triggered by a periodic clock ($T$), the "guard" conditions are purely temporal.
By isolating the clock variable, the algorithm can determine when a transition occurs independently of the system's spatial location. This allows the algorithm to "jump" ahead to the next transition time without constantly checking spatial constraints. Key technical pillars include:
- Zonotope Representations: Efficiently handling linear transformations and Minkowski sums.
- Interval Matrix Maps: Managing uncertain parameters (like resistance or friction) without increasing computational complexity.
- Clustering: Using overapproximation to merge multiple flowpipes during non-deterministic transitions (jitter), ensuring the set representation remains compact.
Case Study: Electro-Mechanical Braking (EMB)
The authors validated their approach using an experimental EMB system model featuring a periodic PI controller. This model incorporates various physical and controller parameters, including inductance, resistance, and friction.
The evaluation covered scenarios ranging from fixed parameters to variations in all seven physical parameters, representing approximately 1% uncertainty.
Results and Performance
The proposed method demonstrated a massive performance leap. While the previous state-of-the-art tool, Flow, required 12 hours to analyze the simplified brake model, the new framework completed the same task in less than a minute*.
Crucially, this speed does not come at the expense of rigor. The method successfully verified critical safety requirements, such as ensuring the brake caliper contacts the disk within a specified time and maintaining safe contact velocities, even under parameter uncertainty and sampling jitter.
Conclusion and Future Directions
By exploiting the structure of time-triggered transitions, this research provides a scalable path for the formal verification of high-frequency hybrid systems. Future work aims to extend this framework to non-linear systems and explore adaptive step-size implementations to further optimize performance.
Summary updated