Stochastic HYPE: Flow-based modelling of stochastic hybrid systems

Luca Bortolussi, Vashti Galpin, Jane HillstonarXiv 2014 · arXiv

Abstract

Modern cyber-physical systems require modeling frameworks that can simultaneously account for continuous physical flows, discrete digital control logic, and stochastic uncertainty. This paper introduces Stochastic HYPE, a compositional process algebra that extends the HYPE framework by incorporating stochastic events and random variable resets. By mapping the algebra to Transition-Driven Stochastic Hybrid Automata (TDSHA), the authors provide a rigorous foundation for both simulation and formal verification. A key contribution is the definition of a stochastic system bisimulation, allowing researchers to prove behavioral equivalence between different system architectures.

Introduction

Engineering complex systems—such as smart grids, automated manufacturing lines, or autonomous vehicles—involves managing hybrid dynamics. These systems combine continuous evolution (e.g., the temperature of a reactor or the velocity of a vehicle) with discrete transitions (e.g., a safety valve opening or a software-driven course correction).

While the original HYPE process algebra provided a modular way to describe these interactions through "influences" on Ordinary Differential Equations (ODEs), it lacked the capacity to model the inherent uncertainty of the real world. Network jitter, mechanical failure rates, and unpredictable packet loss require a framework that treats randomness as a first-class citizen. Stochastic HYPE bridges this gap, offering a formal language to quantify uncertainty within a modular, flow-based architecture.

Methodology

Stochastic Extensions

Stochastic HYPE introduces two primary mechanisms to handle uncertainty:

  1. Stochastic Events: Unlike deterministic events that occur when a specific threshold is met, stochastic events are governed by exponential probability distributions. This allows for the modeling of random failures or arrivals at specific rates.
  2. Random Resets: Upon the occurrence of an event, system variables can be reset to values drawn from arbitrary statistical distributions (e.g., uniform or log-normal). This is crucial for modeling scenarios like a machine restarting with a random initial load.

Formal Semantics

The authors define operational semantics that translate Stochastic HYPE expressions into a Labelled Transition System (LTS). This LTS is then mapped to a Transition-Driven Stochastic Hybrid Automaton (TDSHA). The TDSHA serves as a mathematical bridge to Piecewise Deterministic Markov Processes (PDMPs), which are the standard mathematical objects used to analyze stochastic hybrid systems. This mapping ensures that the high-level process algebra remains grounded in rigorous probability theory.

Bisimulation and Congruence

A central achievement of this work is the development of stochastic system bisimulation. In formal methods, bisimulation is a technique used to prove that two models are behaviorally identical. The authors demonstrate that their bisimulation is a congruence, meaning that if a component is replaced by an equivalent one, the behavior of the larger system remains unchanged. This property is essential for the modular design of large-scale systems.

Key Insights

Mitigating Zeno Behavior

A common pitfall in hybrid system modeling is "Zeno behavior," where a model attempts to execute an infinite number of discrete events in a finite amount of time, effectively stalling the simulation. The authors highlight that the introduction of stochastic events—which occur after a random, non-zero duration—naturally prevents these infinite loops, leading to more robust and "well-behaved" models.

Separation of Concerns

Stochastic HYPE maintains a strict separation between the logical structure of the system, the continuous ODE-based dynamics, and the controller logic. This modularity allows engineers to update the physical parameters of a system (like the flow rate of a pipe) without needing to rewrite the entire control logic.

Results and Applications

Manufacturing Optimization

The framework was validated using a manufacturing assembly line case study. The authors addressed a cost-optimization problem, seeking to balance quadratic energy costs against linear time-delay penalties. By simulating the Stochastic HYPE model, they identified an optimal batch size ($m=2$) that minimized the total cost function.

Proving Controller Equivalence

To demonstrate the power of their bisimulation technique, the authors compared two different controller designs for the assembly line: one utilizing explicit sequencing and another using a semaphore variable. Despite their different internal logic, the authors formally proved they were bisimilar. This theoretical proof was confirmed by 10,000 simulation runs, which showed identical average performance curves for both designs.

Limitations and Future Work

While Stochastic HYPE provides a powerful toolkit, it faces challenges regarding the "combinatorial explosion" of states when mapping process algebra to TDSHAs. Additionally, the current framework restricts stochastic event delays to exponential distributions to avoid the complexity of "residual clocks." Future research aims to expand the bisimulation definitions to handle more complex event label matching and to refine state-space pruning techniques to improve computational efficiency.

Summary updated

Abstract

Stochastic HYPE is a novel process algebra that models stochastic, instantaneous and continuous behaviour. It develops the flow-based approach of the hybrid process algebra HYPE by replacing non-urgent events with events with exponentially-distributed durations and also introduces random resets. The random resets allow for general stochasticity, and in particular allow for the use of event durations drawn from distributions other than the exponential distribution. To account for stochasticity, the semantics of stochastic HYPE target piecewise deterministic Markov processes (PDMPs), via intermediate transition-driven stochastic hybrid automata (TDSHA) in contrast to the hybrid automata used as semantic target for HYPE. Stochastic HYPE models have a specific structure where the controller of a system is separate from the continuous aspect of this system providing separation of concerns and supporting reasoning. A novel equivalence is defined which captures when two models have the same stochastic behaviour (as in stochastic bisimulation), instantaneous behaviour (as in classical bisimulation) and continuous behaviour. These techniques are illustrated via an assembly line example.
BibTeX
@misc{bortolussi2014stochastic,
  author = {Luca Bortolussi and Vashti Galpin and Jane Hillston},
  title = {{Stochastic HYPE: Flow-based modelling of stochastic hybrid systems}},
  year = {2014},
  eprint = {1411.4433},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1411.4433},
}
Figure