Symbolic Model Checking for Rectangular Hybrid Systems

Thomas A. Henzinger, Rupak Majumdar

Abstract

Rectangular hybrid automata represent a critical class of hybrid systems—those combining discrete control with continuous dynamics—for which model checking is theoretically decidable. However, a significant gap has persisted between theoretical decidability proofs and the practical performance of symbolic verification tools. While tools like HyTech utilize efficient symbolic operators, they lack termination guarantees for this class. This paper presents a symbolic Linear Temporal Logic (LTL) model-checking procedure, termed Observation Refinement ($A_{OR}$), which is mathematically guaranteed to terminate for initialized rectangular hybrid systems. By shifting the focus from bisimulation to trace equivalence and utilizing the guarded fragment of the $\mu$-calculus, the authors provide a robust decision procedure that bridges the gap between theory and implementation.

Introduction

Hybrid systems, which integrate discrete control logic with continuous physical processes, are essential for modeling safety-critical applications such as automated highways, medical devices, and industrial controllers. Within this domain, rectangular hybrid automata (RHA) are particularly significant because they are the most expressive class of hybrid systems for which the reachability problem remains decidable.

Despite this theoretical decidability, practical verification has faced a dichotomy. Theoretical proofs typically rely on complex reductions to timed automata, which are computationally expensive and rarely implemented. Conversely, practical symbolic model checkers like HyTech employ "Pre" operators to explore state spaces efficiently but often fail to terminate, even on systems known to be decidable. This paper addresses this discrepancy by introducing a symbolic procedure that is both implementable within existing frameworks and guaranteed to terminate.

The Problem: The Termination Gap

The primary challenge in verifying hybrid systems is the infinite nature of their state spaces. To manage this, model checkers use symbolic representations to group infinite sets of states. Traditional symbolic algorithms often attempt to find a "bisimulation"—a partition of the state space where all states in a group behave identically.

However, for rectangular hybrid automata, a finite bisimulation does not always exist. This causes standard partition-refinement algorithms to loop indefinitely. The authors identified that while bisimulation is a sufficient condition for model checking, it is not a necessary one for LTL properties.

Methodology: Observation Refinement

The authors propose the Observation Refinement ($A_{OR}$) algorithm. This symbolic procedure differs from standard methods in several key ways:

1. Trace Equivalence over Bisimulation

Instead of seeking bisimulation, $A_{OR}$ targets "trace equivalence." Two states are trace-equivalent if they produce the same sequences of observations over time. Because trace equivalence is a coarser relationship than bisimulation, it results in a finite number of equivalence classes for rectangular automata, even when bisimulation remains infinite. This shift is the "missing link" that ensures the algorithm stops.

2. Logical Translation to $G\mu$

To check LTL properties symbolically, the authors translate LTL formulas into a specific subset of the $\mu$-calculus known as the Guarded Fragment ($G\mu$). This translation allows the model-checking problem to be framed as the evaluation of a fixpoint expression using symbolic Pre (predecessor) and Post (successor) operators.

3. Integration with HyTech

Rather than building a new tool from the ground up, the $A_{OR}$ procedure was designed to utilize the existing symbolic primitives of the HyTech model checker. This demonstrates that the lack of termination in previous tools was not a limitation of the symbolic engine itself, but rather the strategy used to explore the state space.

Case Study: Assembly Line Scheduler

The algorithm's efficacy was evaluated using a formal model of an assembly line scheduler. The system consisted of two lines with varying processing speeds (1-2 m/s and 2-3 m/s) and specific cleanup requirements. The verification goal was a liveness property: ensuring that the scheduler could process an infinite stream of jobs without reaching a "shutdown" state.

Using the $A_{OR}$ procedure, the system successfully verified the property in 0.39 seconds of CPU time. This result confirmed that the symbolic approach is not only theoretically sound but also computationally efficient for practical engineering models.

Key Insights and Results

  • Guaranteed Termination: The paper provides the first symbolic LTL model-checking algorithm proven to terminate on all initialized rectangular hybrid automata.
  • Syntax Independence: A significant finding is that the termination of the algorithm depends on the structural properties of the hybrid system (the automata) rather than the complexity of the LTL formula being checked.
  • Algorithmic Equivalence: The authors proved that their $\mu$-calculus-based approach is equivalent to the traditional product-automaton approach, making it a versatile foundation for future symbolic analysis.

Limitations and Future Directions

While the paper marks a major advancement, certain constraints remain:

  • Initialization Requirement: The termination guarantee is strictly for "initialized" automata, where variables are reset or constrained when their dynamics change. Non-initialized rectangular systems remain undecidable.
  • State Space Explosion: Although the algorithm terminates, the number of symbolic regions can grow exponentially with the number of continuous variables. Addressing this "dimensionality bottleneck" is a primary focus for future scaling.
  • Zeno Behavior: The authors acknowledge the challenge of "divergent runs" (where time must progress to infinity). While they provide a construction to handle this, it increases the complexity of the model and requires careful implementation.

Conclusion

By aligning symbolic verification techniques with the coarser abstraction of trace equivalence, this research transforms theoretical decidability into a practical tool for hybrid system design. The $A_{OR}$ algorithm provides a reliable foundation for verifying complex, real-time control systems where safety and liveness are paramount.

Summary updated

Abstract

An important case of hybrid systems are the rectangular automata. First, rectangular dynamics can naturally and arbitrarily closely approximate more general, nonlinear dynamics. Second, rectangular automata are the most general type of hybrid systems for which model checking -in particular, Ltl model checking- is decidable. However, on one hand, the original proofs of decidability did not suggest practical algorithms and, on the other hand, practical symbolic model-checking procedures -such as those implemented in HyTech- were not known to terminate on rectangular automata. We remedy this unsatisfactory situation: we present a symbolic method for Ltl model checking which can be performed by HyTech and is guaranteed to terminate on all rectangular automata. We do so by proving that our method for symbolic Ltl model checking terminates on an infinite-state transition system if the trace-equivalence relation of the system has finite index, which is the case for all rectangular automata.
BibTeX
@inproceedings{henzinger2000symbolic,
  author = {Thomas A. Henzinger and Rupak Majumdar},
  title = {{Symbolic Model Checking for Rectangular Hybrid Systems}},
  booktitle = {TACAS},
  year = {2000},
  doi = {10.1007/3-540-46419-0\_11},
}

Loading related content...

Figure