models.tex

由matlab开发的hybrid系统的描述语言

\chapter{From DHA to Computational Models}
\section{DHA and Piecewise Affine Systems}
\index{Piecewise Affine Systems}%
\index{PWA|see{Piecewise Affine Systems}} This section highlights
the relationships between the DHA introduced above and the class
of Piecewise Affine (PWA) systems~\cite{Son81}.

\label{sect:PWA} PWA systems~\cite{HDB01} are
 defined by partitioning
the state space into polyhedral regions, and associating with each
region a different linear state-update equation
\begin{subequations}
\begin{eqnarray}
    x'(k)&=&A_{i(k)}x(k)+B_{i(k)}u(k)+f_{i(k)}, \label{PWAa}\\
    y(k)&=&C_{i(k)}x(k)+D_{i(k)}u(k)+g_{i(k)}, \label{PWAb}\\
           &&i(k)~\mbox{such that}~~H_{i(k)}x(k) + J_{i(k)}u(k)\leq K_{i(k)}, \label{PWAc}
\end{eqnarray}%
\label{PWA}%
\end{subequations}%
where $x\in \XX\subseteq\rr^{n}$, $u\in \UU\subseteq\rr^{m}$,
$y\in \YY\subseteq\rr^{p}$,
 $\{H_{i}x + J_{i}u \leq K_{i}\}_{i=1}^{s}$,
is a polyhedral partition\footnote{The double definition of the
state-update function over common boundaries of the partition (the
boundaries will also be referred to as {\em guardlines}) is a
technical issue that can be resolved by allowing a part of the
inequalities in (\ref{PWA}) to be strict. However, from a
numerical point of view, this issue is not relevant.} of the set
$\XX\times\UU$, the matrices $A_{i}$, $B_{i}$, $f_{i}$, $C_{i}$,
$D_{i}$, $g_{i}$, $H_i$, $J_i$, $K_i$ are constant and have
suitable dimensions, the inequality in~(\ref{PWAc}) should be
interpreted componentwise. For PWA systems, well-posedness is
defined similarly to Definition~\ref{def:well-posed}.

\begin{definition}
Let $\Sigma_1$, $\Sigma_2$ be hybrid models, whose inputs are
$u_1(k), u_2(k)\in\UU$, and outputs $y_1(k),y_2(k)\in\YY$,
$k\in\Z_{\geq 0}$. Let $x_1(k)\in\XX_1$ be the state of $\Sigma_1$
and $x_2(k)\in\XX_2$ the state of $\Sigma_2$, $k\in\Z_{\geq 0}$.
The hybrid model $\Sigma_2$ is {\em equivalent} to $\Sigma_1$ on
$\XX_1,\UU,\YY$,
$\Sigma_{2}\stackrel{\XX_1,\UU,\YY}{\rightsquigarrow}\Sigma_{1}$,
if there exists a mapping $T:\XX_1\mapsto \XX_2$ such that for all
initial conditions $x_1(0)\in\XX_1$, and for all
$u_1(k)=u_2(k)=u(k)\in\UU$, the output trajectories $y_1(k)$ and
$y_2(k)$ coincide and $x_2(k)=Tx_1(k)$ at all steps $k\in\Z_{\geq
0}$.
\end{definition}

\begin{lemma}
Let $\Sigma_{\rm PWA}$ be a well-posed PWA model defined on a set
of states $\XX\subseteq\rr^n$, a set of inputs
$\UU\subseteq\rr^m$, and a set of outputs $\YY\subseteq\rr^p$.
Then there exists a well-posed DHA model $\Sigma_{\rm DHA}$ such
that $\Sigma_{\rm DHA}\stackrel{\XX,\UU,\YY}
{\rightsquigarrow}\Sigma_{\rm PWA}$ under the identity state
transformation $T(x)=x$. \label{lemma:DHAPWA}
\end{lemma}
\noindent\proof Equations~(\ref{PWAa})--(\ref{PWAb}) are the modes
of the SAS, the constraints $H_ix + J_iu \le K_i$, $i =
1,\ldots,s$ are the defining hyperplanes $f_{\rm H}(\cdot)$ of the
EG, and the MS is defined by Equation~(\ref{PWAc}), namely if all
the events associated to the hyperplanes of $H_{j}x + J_{j}u \le
K_{j}$ are satisfied then $i(k) = j$. \cvd

PWA systems can model a large number of physical processes, such
as systems with static nonlinearities, and can approximate
nonlinear dynamics via multiple linearizations at different
operating points.

\section{DHA and Mixed Logical Dynamical Systems}
\index{Mixed Logical Dynamical Systems} \index{MLD|see{Mixed
Logical Dynamical Systems}} This section describes how to
transform a DHA into linear mixed integer equations and
inequalities, by generalizing several results already appeared in
the literature~\cite{RaGr91,Will93,MLM94,BM99,BTM01a,Hurl01}, and
the equivalence between DHA and Mixed Logical Dynamical (MLD)
systems~\cite{BM99}.

\subsection{Logical Functions}
\label{sec.purelylogic} Boolean functions can be equivalently
expressed by inequalities. This technique allows us to translate
both the \hs{LOGIC} and \hs{AUTOMATA} sections of a \hysdel{}
model into inequalities.

In order to introduce our notation, we recall here some basic
definitions of Boolean algebra. A variable $X$ is a \emph{Boolean
variable} if $X \in \{0,1\}$. A \emph{Boolean expression} is
inductively defined\footnote{In the sake of simplicity we are
neglecting precedence.} by the grammar
\begin{equation}
    \phi ::= X | \lnot \phi_1 | \phi_1 \OR \phi_2 | \phi_1 \oplus \phi_2 | \phi_1 \ANd \phi_2 |
    \phi_1 \leftarrow \phi_2 | \phi_1 \rightarrow \phi_2
    |\phi_1 \leftrightarrow \phi_2 | (\phi_1)
    \label{eq:bf}
\end{equation}
where $X$ is a Boolean variable, and the logic operators $\lnot$
(not), $\OR$ (or), $\ANd$ (and), $\leftarrow$ (implied by),
$\rightarrow$ (implies), $\leftrightarrow$ (iff) have the usual
semantics. A Boolean expression is a \emph{conjunctive normal
form} (CNF) or \emph{product of sums} if it can be written
according to the following grammar:
\begin{eqnarray}
    \phi &::=& \psi | \phi \land \psi \\
    \psi &::=& \psi_1 \lor \psi_2 | \lnot X | X
\end{eqnarray}
where $\psi$ are called \emph{terms of the product}, and $X$ are
the \emph{terms of the sum} $\psi$. A CNF is minimal if it has the
minimum number of terms of product and each term has the minimum
number of terms of sum. Every Boolean expression can be rewritten
as a minimal CNF.

A Boolean expression $f$ will be also called {\em Boolean
function} when is used to define a literal $X_n$ as a function of
$X_1,\ldots,X_{n-1}$:
\begin{equation}
    X_n = f(X_1, X_2, \ldots, X_{n-1}){\rm .} \label{eq.ff}
\end{equation}
More in general, we can define relations among Boolean variables
$X_1,\ldots,X_{n}$ through a \emph{Boolean formula}
\begin{equation}
    F(X_1, \ldots, X_n) = 1{\rm ,} \label{eq.F}
\end{equation}
where $X_i \in \{0,1\}$, $i=1,\dots,n$. Note that each Boolean
function is also a Boolean formula, but not vice versa. Boolean
formulas can be equivalently translated into a set of integer
linear inequalities. For instance, $X_1\lor X_2=1$ is equivalent
to $X_1+X_2\geq 1$~\cite{Will93}. The translation can be performed
either using an {\em symbolical} method or a {\em geometrical}
method.

\subsubsection{Symbolical Method}

The symbolical method consists of first converting (\ref{eq.ff})
or (\ref{eq.F}) into CNF, a task that can be performed
automatically by using one of the several techniques available,
see e.g. \cite{Mill65,Sasa99}. Let the CNF have the form
$\bigwedge_{j=1}^m\left(\bigvee_{i\in P_j}X_i \bigvee\bigvee_{i\in
N_j}\NOT X_i\right)$, $N_j,P_j \subseteq \{1,\ldots,n\}~\forall
j=1,\ldots,m$. Then, the corresponding set of integer linear
inequalities is
\begin{equation}
  \left\{\ba{l}
    1\leq \sum_{i\in P_1}X_i+\sum_{i\in N_1}(1-X_i), \\
     \vdots\\
    1\leq \sum_{i\in P_m}X_i+\sum_{i\in N_m}(1-X_i){\rm . } \\
  \ea\right.
    \label{eq:CNFineq}
\end{equation}
With these inequalities we can define the set $P_{CNF}$ for any
Boolean formula $F$ as:
\begin{equation}
P_{CNF} = \{ x \in [0,1]^n : (\ref{eq:CNFineq}) \mathrm{ ~ are ~
satisfied  ~ with} ~ x = [X_1,\ldots,X_n]^T \}{\rm .}
\end{equation}

\subsubsection{Geometrical Method} The geometrical method
consists of two steps (see e.g.~\cite{MiBM99b}). First, the set of
points satisfying (\ref{eq.ff}) or (\ref{eq.F}) is computed (for
this reason, the method was also called {\em truth table} method
in~\cite{MiBM99b}). Each row of the truth table is associated with
a vertex of the hypercube $\{0,1\}^n$. The vertices are collected
in a set $V$ of {\em valid} points, all the other points
$\{0,1\}^n \setminus V$ are called {\em invalid}. The inequalities
representing the Boolean formula are obtained by computing the
convex hull of $V$, for which several tools are available (see
e.g.~\cite{Fuk97}). We therefore define
\begin{equation}
P_{CH} = \{ x \in [0,1]^n : x \in {\rm conv}(V) \}
\end{equation}

In general it holds that $P_{CH} \subseteq P_{CNF}$, since ${\rm
conv}(V)$ is the smallest set containing all integer feasible
points. However, there exist Boolean formulas, for which $P_{CH}
\neq P_{CNF}$\footnote{For example $(X_1 \vee X_2) \wedge (X_1
\vee X_3) \wedge (X_2 \vee X_3)$.}. Conditions for which
$P_{CH}=P_{CNF}$ are currently a topic of research.

\subsection{Continuous-Logic Interfaces}
\label{sect.cli} Events of the form~(\ref{eq::eventgenerator}) can
be equivalently expressed as
\begin{subequations}
\beqar
        f^i_{\rm H}(x_r(k),u_r(k),k)&\leq& M^i(1-\delta_e^i),\label{eq:ti1}\\