Lazy Hybrid Automata
A hybrid automaton's discrete level of detail is in conflict with the implementability of its direct representation. Here I propose a lazy hybrid automata suitable for handling high levels of discrete detail, and sketch its practical impact on a simulation algorithm.
Locating the problem
We set out from the miniature HA outlined in Structured Transition Guards, based on [Schaft2000]:
The set of locations, \(L\), is the product of the domains of the discrete variables, \(P = (P_0,\ldots,P_{m1})\):
The cardinality of \(L\) is \(L = \prod_{i=0}^{m1} L_i\). If we (reasonably) assume \(L_i > 1\), then \(L\) is bounded from below by \(2^m\), and \(2^m \leq L\). As the level of discrete detail increases; as \(m\) grows, \(L\) explodes, and in practice it becomes problematic to represent the HA in its entirety. In particular, the storage required to represent the implicit graph, \((L,E)\), also explodes with \(L\).
Hybrid models with high levels of discrete detail do occur in practice. One such example can be seen in [OcampoMartinez2010], whose casestudy results in a PWAsystem (a more concrete type of hybrid system) with 22 binary variables and \(2^{22} = 4194304\) locations. I personally came across this topic during my yet unpublished work on a hybrid automata for hydropower plants in the context of production planning.
Lazy HAs
A high level of discrete detail might restrict us to work with partial representations of the HA during simulation. A partial representation which must at any point during the simulation contain the current location. The current location will change as the simulation progresses, so it must be possible to construct more of the HA in a lazy fashion.
Most of \(H\) is already lazy by definition. \(F \colon L \to X \to X\) and \(G \colon E \to X \to X\) are functions, and could potentially be computed lazily. 0 \(L\) and \(E\) however, the sets of all locations and edges, and their implicit graph \((L,E)\), are represented in their entirety. We lazify this by assuming that the edges out of a location can be computed from the location. To this end we define the edgefunction, \(\mathbf{E}\):
For a given location, we have \(\mathbf{E}(l) = \{ (G_\star,l_\star) \ldots \}\), where \(\{ l \} \times \mathbf{E}(l) \subseteq E\). Note that \(l\) and \(\mathbf{E}(l)\) encodes a subgraph of \((L,E)\):
We can now formulate a partial representation of \(H\), ignoring the components that were already lazy:
We denote the set of all possible partial HAs of \(H\) as \(\mathbb{H}_\ast(H)\).
 0

This representation of \(G\) was proposed in Structured Transition Guards.
A simple switch
To illustrate this encoding we consider a simple binary switch, again focussing only locations and edges:
Or as a diagram:
And define the edge function:
We have f.ex. \(\mathbf{E}_{switch}(l_{on}) = \{ l_{off} \}\); the only edge out of \(l_{on}\) is \((l_{on},l_{off})\), and visaversa for \(l_{off}\). The subgraphs of \(\mathbf{E}\), and \(\{ l_{on}, l_{off} \}\) are illustrated below:
Bowling balls on a circular rail
Here we will consider a more complex class of systems generated by \(H_{bowl} \colon \N \to \mathbb{H}\), which maps from some number of bowling balls to a hybrid automaton inspired by [Cellier2006]:
"The problem is by no means an academic one. Consider the case of a set of bowling balls resting on a guide rail. They are all in contact with each other. A new ball arrives with velocity v that hits the first of these balls. We all know what will happen: the new ball will come to rest at once, and the last of the previously resting balls will move away with the same speed v. Yet, convincing a simulation program that this is what must happen is anything but trivial."
We take the guide rail from the text, tie its ends together, and place \(n\) balls on it. We enumerate the balls, \(b\), in counterclockwise order from some arbitrary point on the rail:
The discrete state of \(H_{bowl}(n)\) is composed by \(n\) binary variables:
\(P_i\) describes whether or not the \(i\)th and \(i+1\ (\mathrm{mod}\ n)\)th balls are in contact, and the domain of \(P_i\) is \(L\):
We denote the indices of all pairs of balls in contact in \(l\) as \(I_{contact}(l) = I_{0}(l) = \{ i \mid l_i = 0 \}\), and similarly for separate balls, \(I_{separate}(l) = I_{1}(l) = \{ i \mid l_i = 1 \}\). Below is an illustration of the location \(l = (0,1,1)\) in \(H_{bowl}(3)\). Separation is drawn in dotted lines. Here \(I_{0} = \{ 0 \}\), and \(I_{1} = \{ 1, 2 \}\):
We term the transitive closure of adjacent balls in contact segments, \(s \subseteq J\). \(s(j)\) denotes the segment containing the \(j\)th ball. \(u_0(s)\) to refers to a segments most counterclockwise ball, and similarly for \(u_1(s)\) and clockwise. The segments of \(P = (0,1,1)\) are \(\{\{0,1\},\{2\}\}\). We assume that all the balls in a segment are moving at the same speed, so the only way they break apart or connect are through collisions.
As described in [Cellier2006], when one segment collides into another, they fuse, and the ball at the other side of the segment collided into is separated. These collisions are the edges of our automaton, for which we will construct an edgefunction, \(\mathbf{E}\). We focus only on \(L\), and \(E\), and ignore the guard.
Let \(w_0(i)\) denote the counterclockwisemost ball of \(P_i\), similar with \(w_1(i)\) and clockwise. Let \(p_0(j)\) denote the variable on the counterclockwise side of \(b_j\), and simliarly for \(p_1(j)\) and clockwise. For each separated pair of balls, \(i \in I_1(l)\), and for any \(d \in 2\), \(w_d(i)\) can collide into \(w_{d^\prime}(i)\), connecting \((s \circ w_d)(i)\) with \((s \circ w_{d^\prime})(i)\), and separating \((u_{d^\prime} \circ s \circ w_{d^\prime})(i)\) from \((s \circ w_{d^\prime})(i)\). We compute the location that results from the collision by considering \(l\) as a binary number \(\sum_{i \in n} l_i \cdot 2^{i}\):
Note that if the segment collided into, \((s \circ w_{d^\prime})(i)\), only has one ball, then \(l^{\ast}(l,i,d) = l\). The edge function is then:
For \(l = (0,1,1)\) we get \(\mathbf{E}(l) = \{ l_{\ast}(i,d) \mid i,d \in \{1, 2\} \times 2 \}\). If we assume that \(\{b_0,b_1\}\) is at rest, while \(\{b_2\}\) is moving in a counterclockwise direction, eventually it hits \(b_0\), causing a collision with \(i = 2\), \(d = 0\). We traverse the corresponding edge and arrive at \(l_{\ast}(0,0) = 011_2  001_2 + 100_2 = 110_2\), corresponding to \((1,1,0)\). \(\{b_0,b_2\}\) is now at rest while \(\{b_1\}\) has separated and is moving in a counterclockwise direction. It is only a matter of time before it hits \(b_2\), and so on and so forth. In fact \(P\) will cycle between the 3 locations illustrated below, ad infinitum:
Practical impact
We now sketch the impact of working with a partial HA on a simulation algorithm. We start with a reconstruction of Figure 5.10 from [Andersson1994] which gives a highlevel description of the simulation algorith of hybrid systems in Omola: 1
During the course of a simulation of \(H \in \mathbb{H}\), instead of working with \(H\) in its entirety, we advance a partial HA variable \(?H_\ast \in \mathbb{H}_\ast(H)\). Before solving the continuous problem at \(?P\), if \(?P \notin L^{t}_\ast\), we compute a new valuation \(?H^{t+1}_\ast\), such that \(?P \in L^{t+1}_\ast\). We are then able to construct the continuous problem with activity function, invariants, guards, symbols and jumps, and all the rest of it, before we start solving it. The impact of this is highlighted in green:
 1

The "Fire event." block has been rerouted from the original diagram to reuse the "Find consistent initial values" block.
Schemes of partialness
The only constraint to our partial HA has so far been \(?P \in L_\ast\). Having to work with a partial HA opens up some interesting possiblities with respect to for example precomputation, memoization and parallellization. From returning to direct representation with full a priori precomputation, \(?H^0_\ast = (L,E)\), to none, \(?H^0_\ast = (\emptyset, \mathbf{E})\). From no memoization, containing only the current location, \(?H^{t+1}_\ast = (\{?P^t\},\mathbf{E})\), to full memoization, where the information of all previous locations are cached, \(L^t_\ast \subseteq L^{t+1}\).
Circling back to the bowling balls, it's not hard to imagine initial conditions for which the number of segments will never change (for example in the illustrated example), and for which the discrete state will cycle between a fixed number of locations. With full memoization one would for example quickly have computed exactly the locations that will be used for the rest of the simulation. In addition, a particular collision contains information about the likelyhood of what edges will be traversed in the near furture, and thus gives opportunities for dynamic precomputation during the course of the simulation. Precomputation that might be parallelized with respect to the simulation itself.
Maybe a topic for a later time.
Glossary
 DAE

Differentialalgebraic equation
 HA

Hybrid automaton
 PWA

Piecewise affine
Bibliography
 Andersson1994

"Mats Andersson", "ObjectOriented Modelling and Simulation of Hybrid Systems"
 Schaft2000

"Arjan van der Schaft and Hans Schumacher", "An introduction to hybrid dynamical systems"
 Cellier2006(1,2)

"François E. Cellier and Ernesto Kofman", "Continuous Systems Simulation"
 OcampoMartinez2010

"Carlos OcampoMartinez", "Model Predictive Control of Wastewater Systems"