Skip to main content

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]:

\begin{equation*} \begin{gathered} H = (L,X,E,\mathbf{F}) \\ E = L \times \mathbf{G} \times L \end{gathered} \end{equation*}

The set of locations, \(L\), is the product of the domains of the discrete variables, \(P = (P_0,\ldots,P_{m-1})\):

\begin{equation*} \begin{gathered} L = \prod_{i=0}^{m-1} L_i \end{gathered} \end{equation*}

The cardinality of \(L\) is \(|L| = \prod_{i=0}^{m-1} |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 [Ocampo-Martinez2010], whose case-study results in a PWA-system (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 edge-function, \(\mathbf{E}\):

\begin{equation*} \mathbf{E} \colon L \to L \times \mathbf{G} \end{equation*}

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)\):

\begin{equation*} \begin{gathered} (L_\star,E_\star) \subseteq (L,E) \\ L_\star = \{l,l_\star \ldots \} \\ E_\star = \{l\} \times \mathbf{E}(l) \end{gathered} \end{equation*}

We can now formulate a partial representation of \(H\), ignoring the components that were already lazy:

\begin{equation*} \begin{gathered} H_\ast = (L_\ast,\mathbf{E}) \\ \mathbf{E} \colon L \to L \\ L_\ast \subseteq L \end{gathered} \end{equation*}

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:

\begin{equation*} H_{switch} = (\{l_{on},l_{off}\},\{(l_{on},l_{off}),(l_{off},l_{on})\}) \end{equation*}

Or as a diagram:

G on onoff offon->off off->on

And define the edge function:

\begin{equation*} \mathbf{E}_{switch}(l) = L_{switch} \setminus \{ l \} \end{equation*}

We have f.ex. \(\mathbf{E}_{switch}(l_{on}) = \{ l_{off} \}\); the only edge out of \(l_{on}\) is \((l_{on},l_{off})\), and visa-versa for \(l_{off}\). The subgraphs of \(\mathbf{E}\), and \(\{ l_{on}, l_{off} \}\) are illustrated below:

G cluster0 loncluster1 loffon0 onoff0 offon0->off0 on1 onoff1 offoff1->on1

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 counter-clockwise order from some arbitrary point on the rail:

\begin{equation*} b_j \mid j \in J = \{ 0, \ldots, n-1 \} \end{equation*}

The discrete state of \(H_{bowl}(n)\) is composed by \(n\) binary variables:

\begin{equation*} P = \{ P_0, \ldots, P_{n-1} \} \end{equation*}

\(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\):

\begin{equation*} L = \{ l_{contact}, l_{separate} \} = \{ 0, 1 \} \end{equation*}

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 \}\):

G b0 b0b1 b1b0--b1 P0b2 b2b1--b2 P1b2--b0 P2

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 counter-clockwise 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 edge-function, \(\mathbf{E}\). We focus only on \(L\), and \(E\), and ignore the guard.

Let \(w_0(i)\) denote the counter-clockwise-most ball of \(P_i\), similar with \(w_1(i)\) and clockwise. Let \(p_0(j)\) denote the variable on the counter-clockwise 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}\):

\begin{equation*} l^{\ast}(l,i,d) = l - 2^{i} + 2^{(p_{d} \circ u_{d^\prime} \circ s \circ w_{d^\prime})(i)} \end{equation*}

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:

\begin{equation*} \begin{aligned} \mathbf{E}(l) &= \{ l_{\ast}(l,i,d) \mid i,d \in I_{1}(l) \times 2 \} \end{aligned} \end{equation*}

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 counter-clockwise 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 counter-clockwise 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:

cluster_l0 P = (0,1,1)cluster_l1 P = (1,1,0)cluster_l2 P = (1,0,1)b00 b0b01 b1b00--b01 P0b02 b2b01--b02 P1b02--b00 P2b10 b0b02--b10 b11 b1b10--b11 P0b12 b2b11--b12 P1b12--b10 P2b21 b1b12--b21 b20 b0b20--b02 b20--b21 P0b22 b2b21--b22 P1b22--b20 P2

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 high-level description of the simulation algorith of hybrid systems in Omola: 1

The simulation algorithm for Omola Hybrid Modelsv0 Beginv1 Find consistent initial valuesv0->v1 v2 Check invariantsv1->v2 v3 Any events?v2->v3 v4 Solve DAE problem andadvance time until finaltime or discrete event.v3->v4 nov5 Fire event.v3->v5 yesv6 Final time?v4->v6 v5->v1 v6->v2:w nov7 Endv6->v7 yes

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:

An augmented simulation algorithm for Hybrid Modelsv0 Beginv9 Location inpartial HA?v0->v9 v1 Find consistent initial valuesv2 Check invariantsv1->v2 v3 Any events?v2->v3 v4 Solve DAE problem andadvance time until finaltime or discrete event.v3->v4 nov5 Fire event.v3->v5 yesv6 Final time?v4->v6 v5->v9 v6->v2:w nov7 Endv6->v7 yesv8 Advance partial HAv8->v1 v9->v1 yesv9->v8 no

1

The "Fire event." block has been rerouted from the original diagram to re-use 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 pre-computation, memoization and parallellization. From returning to direct representation with full a priori pre-computation, \(?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 pre-computation during the course of the simulation. Pre-computation that might be parallelized with respect to the simulation itself.

Maybe a topic for a later time.

Glossary

DAE

Differential-algebraic equation

HA

Hybrid automaton

PWA

Piecewise affine

Bibliography

Andersson1994

"Mats Andersson", "Object-Oriented 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"

Ocampo-Martinez2010

"Carlos Ocampo-Martinez", "Model Predictive Control of Wastewater Systems"