Mixed logical dynamical (MLD) systems

We have just learnt how the logical conditions that encode the individual components of discrete hybrid automata can be turned into linear inequalities. Here we summarize them all into a single mathematical model called mixed logical dynamical (MLD).

\boxed{ \begin{aligned} x(k+1) &= Ax(k) + B_u u(k) + B_\delta\delta + B_zz(k) + B_0,\\ y(k) &= Cx(k) + D_u u(k) + D_\delta \delta + D_z z + D_0,\\ E_\delta \delta &+ E_z z(k) \leq E_u u(k) + E_x x(k) + E_0. \end{aligned}} \tag{1}

The first two (sets of) equations resemble the state and output equations of a linear time-invariant (LTI) system, but with some additional terms corresponding to auxilliary variebles (plus an offset). The auxilliary variables are not completely arbitrary – they must comply with the third (set of) equation(s).

Examples

Example 1 (Switched linear system) We consider a discrete-time switched system that switches between two linear systems x(k+1) = a_i x(k) + b_i u(k), \quad i\in\{0,1\}, where i=0 if x(k)< 0 and i=1 otherwise.

The auxilliary binary variable \delta (actually \delta(k), one for each discrete time k) is introduced to encode the switching condition: [\delta(k) = 1] \iff [-x(k)\leq 0].

This equivalence can be rewritten as \begin{aligned} -x(k) &\leq (1-\delta(k))M,\\ -x(k) &\geq \epsilon + (m-\epsilon)\delta(k), \end{aligned} where m and M are lower and upper bounds on x(k), respectively, and \epsilon is a small positive number. Say, if it is known that x\in [-10,10], then m=-10, M=10. We can set \epsilon = 10^{-8}.

Furthermore, just a single continuous (real) variable z is introduced to encode one of two modes of the system: \begin{aligned}\\ [\delta(k) = 1] \iff z(k) &= a_2 x(k) + b_2 u(k),\\ [\delta(k) = 0] \iff z(k) &= a_1 x(k) + b_1 u(k). \end{aligned}

This can be rewritten as \begin{aligned} (m_1-M_2)\delta(k) + z(k) &\leq a_1 x(k) + b_1 u(k),\\ (m_2-M_1)\delta(k) - z(k) &\leq -a_1 x(k) - b_1 u(k),\\ (m_2-M_1)(1-\delta(k)) + z(k) &\leq a_2 x(k) + b_2 u(k),\\ (m_1-M_2)(1-\delta(k)) - z(k) &\leq -a_2 x(k) - b_2 u(k), \end{aligned} where m_1 and M_1 are lower and upper bounds on a_1 x(k) + b_1 u(k), and m_2 and M_2 are lower and upper bounds on a_2 x(k) + b_2 u(k).

Collecting all the six inequalities (and reformatting them) we get \begin{aligned} M\delta(k) &\leq x(k) + M,\\ (m-\epsilon)\delta(k) &\leq -x(k) - \epsilon,\\ (m_1-M_2)\delta(k) + z(k) &\leq a_1 x(k) + b_1 u(k),\\ (m_2-M_1)\delta(k) - z(k) &\leq -a_1 x(k) - b_1 u(k),\\ (M_1-m_2)\delta(k) + z(k) &\leq a_2 x(k) + b_2 u(k) + (M_1-m_2),\\ (M_2-m_1)\delta(k) - z(k) &\leq - a_2 x(k) - b_2 u(k) + (M_2-m_1). \end{aligned}

We can rewrite these in a compact way as E_\delta \delta(k) + E_z z(k) \leq E_x x(k) + E_u u(k) + E_0, where \begin{aligned} E_\delta &= \begin{bmatrix} M\\ m-\epsilon\\ m_1-M_2\\ m_2-M_1\\ M_1-m_2\\ M_2-m_1\end{bmatrix}, \qquad E_z = \begin{bmatrix} 0\\ 0\\ 1\\ -1\\ 1\\ -1\end{bmatrix},\\ E_x &= \begin{bmatrix} 1\\ -1\\ a_1\\ -a_1\\ a_2\\ -a_2\end{bmatrix},\qquad E_u = \begin{bmatrix} 0\\ 0\\ b_1\\ -b_1\\ b_2\\ -b_2\end{bmatrix},\qquad E_0 = \begin{bmatrix} M\\ -\epsilon\\ 0\\ 0\\ M_1-m_2\\ M_2-m_1\end{bmatrix}. \end{aligned}

On top of these inequalities, we need to add the state update equation. It is, however, particularly simple in this case: x(k+1) = z(k), from which we can extract the remaining matrices parameterizing the MLD model in Equation 1: A = 0, \quad B_u = 0, \quad B_\delta = 0, \quad B_z = 1, \quad B_0 = 0.

Note, in particular, that the matrix A=0, which might be confusing at first, because it does not correspond to any of the time-discretized LTI models, but it is just a demonstration of the fact that MLD is not a state equation.

HYSDEL language

The previous example demonstrated that the procedure for turning the discrete-time hybrid automaton into a MLD model is rather tedious and error-prone. Automating this procedure is the goal of the HYSDEL language (and parser). Here we do not explain it, we only show the code for our example to get the idea.

SYSTEM switched_LTI_1 {
    INTERFACE {
        INPUT {
            REAL u [-1.0,1.0];
        }
        STATE {
            REAL x [-10, 10];
        }
        OUTPUT {
            REAL y;
        }
        PARAMETER {
            REAL A1 = -3/4;
            REAL A2 = 1/5;
            REAL B1 = 1;
            REAL B2 = 1;
        }
    }
    IMPLEMENTATION {
        AUX {
            REAL z;
            BOOL delta;
        }
        AD {
            delta = x >= 0;
        }
        DA {
            z = {IF delta THEN A2*x + B2*u ELSE A1*x + B1*u};
        }
        CONTINUOUS {
            x = z;
        }
        OUTPUT {
            y = x;
        }
    }
}

Piecewise affine systems

\begin{aligned} x(k+1) &= A_{i(k)}x(k) + B_{i(k)} u(k) + f_{i(k)}\\ y(k) &= C_{i(k)}x(k) + D_{i(k)} u(k) + g_{i(k)}\\ & \; H_{i(k)} x(k) + J_{i(k)} u(k) \leq K_{i(k)} \end{aligned}

DHA, MLD, PWA are equivalent. # TODO: explain