Efficient reachability analysis of parametric linear hybrid systems with time-triggered transitions

Marcelo Forets, Daniel Freire, Christian Schilling

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.

Figure 1: Illustration of the actual vs. computed transition time frames, accounting for sampling jitter.

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.

Figure 2: Hybrid automaton model of the electro-mechanical braking system with a periodic PI controller.

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

Abstract

Efficiently handling time-triggered and possibly nondeterministic switches for hybrid systems reachability is a challenging task. In this paper we focus on periodically controlled systems with fast-switching controller dynamics, which often require simulation time scales of the order of nanoseconds. Accurate set-based computations for such systems with relatively large time horizons are expensive due to the accumulation of errors in the discrete transitions. We present an approach based on conservative set-based enclosure of the dynamics that can handle systems with uncertain parameters and inputs. We demonstrate our algorithm on the plant model of an experimental electro-mechanical braking system with periodic controller.
BibTeX
@inproceedings{forets2020efficient,
  author = {Marcelo Forets and Daniel Freire and Christian Schilling},
  title = {{Efficient reachability analysis of parametric linear hybrid systems with time-triggered transitions}},
  booktitle = {MEMOCODE},
  year = {2020},
  doi = {10.1109/memocode51338.2020.9314994},
}
Figure