Singularities of Schubert Varieties within a Right Cell

Singularities of Schubert Varieties within a Right Cell

Martina LANINI a and Peter J. MCNAMARA b

M. Lanini and P.J. McNamara

a) Department of Mathematics, University of Rome “Tor Vergata”, Italy
<EMAIL_ADDRESS>https://sites.google.com/site/martinalanini5/

b) School of Mathematics and Statistics, The University of Melbourne,
Australia<EMAIL_ADDRESS>http://petermc.net/maths/

Received December 10, 2020, in final form July 06, 2021; Published online July
19, 2021

We describe an algorithm which pattern embeds, in the sense of Woo–Yong, any
Bruhat interval of a symmetric group into an interval whose extremes lie in
the same right Kazhdan–Lusztig cell. This apparently harmless fact has
applications in finding examples of reducible associated varieties of
$\mathfrak{sl}_{n}$-highest weight modules, as well as in the study of
$W$-graphs for symmetric groups, and in comparing various bases of irreducible
representations of the symmetric group or its Hecke algebra. For example, we
are able to systematically produce many negative answers to a question from
the 1980s of Borho–Brylinski and Joseph, which had been settled by Williamson
via computer calculations only in 2014.

Schubert varieties; interval pattern embedding; Kazhdan–Lusztig cells; Specht
modules

14M15; 20B30; 32C38; 20C08

##  1 Introduction

Let $\mathcal{F}l_{n}$ be the variety of complete flags in $\mathbb{C}^{n}$.
For each permutation $w\in S_{n}$, the Schubert variety $X_{w}$ is a closed
subvariety of $\mathcal{F}l_{n}$ consisting of flags which intersect a fixed
flag in a particular way prescribed by $w$ – see (3.1) for the precise
definition. The Bruhat order on $S_{n}$ is defined by $x\leq y$ if
$X_{x}\subseteq X_{y}$.

Right, left and two-sided cells were introduced by Kazhdan and Lusztig in
their seminal paper [13] in order to construct representations of the Hecke
algebra associated to a Coxeter group $W$. In general, cells are equivalence
classes on $W$ defined using the Kazhdan–Lusztig basis of the Hecke algebra.
When $W$ is a symmetric group, there is a simple combinatorial description in
terms of the Robinson–Schensted correspondence: namely that two permutations
belong to the same right, left, two-sided cell respectively if and only if
their $P$ symbols coincide, $Q$ symbols coincide, their $P$ (or, equivalently,
$Q$) symbols have the same shape.

The key result of this paper is the following:

######  Theorem 1.1.

Let $x,y\in S_{n}$ with $x\leq y$. Then, there exist $N\geq n$, and two
permutations $v,w\in S_{N}$ with $v\leq w$ such that

  * •

$v$ and $w$ belong to the same right cell;

  * •

the singularity of $X_{w}$ at $v$ is smoothly equivalent to the singularity of
$X_{y}$ at $x$.

The permutations $v$, $w$ of the above theorem are obtained from $x$ and $y$
by an explicit algorithm, described in Section 2. Each step of the algorithm
produces an interval pattern embedding (see Definition 3.1), which, by results
of Woo–Yong [25], induces smooth equivalences.

As a consequence, any possible behaviour of invariants of Schubert variety
singularities (e.g., Kazhdan–Lusztig polynomials, their positive
characteristic analogues, decomposition numbers of perverse sheaves, etc.) can
appear within a single right cell. An analogous statement holds for left
cells. Any of these statements imply the same result for two-sided cells.

Historically there had been some hope that the singularity of a Schubert
variety $X_{w}$ at a point $v$ with $v$ and $w$ in the same cell would be
better behaved than general singularities of Schubert varieties. Our work
shows this not to be the case. An example of this hope is Borho–Brylinski and
Joseph’s conjecture from the 1980s that the associated variety of an
$\mathfrak{sl}_{n}$-module would be always irreducible [3, 11]. Such a
question was settled only in 2014 by Williamson in [22]. For the moment, we
just want to mention that the answer provided in [22] is obtained by using
Howlett and Nguyen’s software [7] for computing $W$-graphs in MAGMA [4].
Thanks to our main result, this is now a consequence of the known reducibility
of type A characteristic varieties. We discuss this in greater detail in
Section 4.1.

In Sections 4.2 and 4.3 two further applications of Theorem 1.1 are presented.
The first one deals with the study of edge weights in $W$-graphs for symmetric
groups and the so-called 0-1 conjecture, which would have implied that all the
weights are either 0 or 1. Thanks to [15] the conjecture was already known to
be false, but we obtain in Section 4.2 a counterexample which does not come
from computer calculations. The last application we discuss is about the
comparison of several Specht module bases – the Springer basis, the Goldie
rank basis, the Kazhdan–Lusztig basis and the $p$-Kazhdan–Lusztig bases for
each prime $p$ (see Section 4 for more details). Our approach allows us to
transfer known examples of singularities of Schubert varieties into a single
cell and thus exhibit many examples where these bases differ. In fact, thanks
to the torsion explosion phenomenon from [23] we know that there are
infinitely many such examples, as explained in Section 4.3.

##  2 Robinson–Schensted correspondence

The Robinson–Schensted correspondence is a bijection between $S_{n}$ and pairs
of standard tableaux of the same shape with $n$ boxes. If $w\in S_{n}$, we
write $(P(w),Q(w))$ for the corresponding pair of tableaux. The $P$ symbol
$P(w)$ is obtained by successively performing $n$ column insertions into the
empty tableau, with numbers $w(n),w(n-1),\dots,w(1)$ in that order. The
equivalence of this with the more familiar row insertion definition follows
from [18, Lemma 7.23.15]. The $Q$ symbol $Q(w)$ is obtained by the recording
the cell added at each insertion step: after adding the $i$-th cell to $P(w)$,
one adds a cell with content $i$ in the same position as the new cell in
$P(w)$.

Here, and in the rest of the paper, we use the one line notation for
permutations: we represent $w\in S_{n}$ as $[w_{1}\dots w_{i}\dots w_{n}]$,
meaning that $w_{i}=w(i)$ for any $1\leq i\leq n$.

######  Example 2.1.

If $w=[3142]\in S_{4}$, the (column) insertion procedure produces the
following two sequences of tableaux, and hence the $P$ and $Q$ symbols:

$\young(2),\ \young(2,4),\ \young(12,4),\ \young(12,34)=P(w),\qquad\young(1),\
\young(1,2),\ \young(13,2),\ \young(13,24)=Q(w).$

Left and right cells are equivalence classes on a Coxeter group defined in
terms of Kazhdan–Lusztig polynomials by Kazhdan and Lusztig (cf. [13] after
Theorem 1.3). We omit the original definition here, as we only deal with the
symmetric group case where a combinatorial characterisation exists. The
following is [2, Theorem A] or [5, Fact 8], and is originally from [13,
Section 5]. It gives a characterisation of left and right cells in the
symmetric group.

######  Theorem 2.2.

Two permutations $x$ and $y$ in $S_{n}$ are in the same right $($respectively
left$)$ cell if and only if $P(x)=P(y)$ $($respectively $Q(x)=Q(y))$.

Two elements $x$ and $y$ of a Coxeter group are in the same left cell if and
only if $x^{-1}$ and $y^{-1}$ are in the same right cell. For a standard
tableau $T$ and an entry $s$ of $T$, we denote by $c_{T}(s)$ the column index
of the entry. For example if $T=P(w)$ from Example 2.1, then
$c_{T}(1)=c_{T}(3)=1$ and $c_{T}(2)=c_{T}(4)=2$.

######  Lemma 2.3.

Let $T$ be a standard tableau, and let $s$ be an entry of $T$. Let $r$ be such
that no entries of $T$ lie in the interval $(r,s)$ and let $k\leq r-s$ be a
positive integer. Choose $k-1$ integers $r<r_{1}<\cdots<r_{k-1}<s$. Let
$T^{\prime}$ be the tableau obtained from $T$ by column inserting
$r_{k-1},\dots,r_{1}$. Then

  1. $1)$

$c_{T^{\prime}}(r_{i})=i$ and $c_{T^{\prime}}(s)=m$, where
$m=\max\\{c_{T}(s),k\\}$,

  2. $2)$

if $s^{\prime}$ is an entry of $T$ such that $s^{\prime}>s$, then
$c_{T^{\prime}}(s^{\prime})=c_{T}(s^{\prime})$ or
$c_{T^{\prime}}(s^{\prime})\leq m+n$, where $m$ is as before and $n$ is the
number of entries in $T$ in $[s,s^{\prime})$.

###### Proof.

By induction on $t$, we show that if we column insert $r_{k-1},\dots,r_{k-t}$,
then

  * •

$r_{k-t+i}$ lies in the $(i+1)$-st column for $0\leq i<t$,

  * •

$s$ lies in the $m$-th column, for $m=\max\\{c_{T}(s),t+1\\}$.

The base case $t=0$ is tautologically true. Now suppose we have inserted
$r_{k-1},\dots,r_{k-t+1}$, in accordance with the inductive hypothesis. After
these insertions, $s$ will be placed in column $\max\\{c_{T}(s),t\\}$. When we
column insert $r_{k-t}$, any $r_{k-t+i}$ bumps out $r_{k-t+i+1}$ from the
$i$-th column. In particular, $r_{k-1}$ is placed in the $t$-th column and $s$
gets bumped out if and only if $\max\\{c_{T}(s),t\\}=t$, that is $c_{T}(s)\leq
t$. This proves the first part of the lemma.

We now prove the second statement by induction on $n$. Let
$s_{1}<\dots<s_{n-1}$ be the elements of $(s,s^{\prime})$ that lie in $T$.
During the column insertions $s^{\prime}$ can be bumped out only by the
entries between $r$ and $s^{\prime}$. By the previous part of this lemma, the
entries $r_{1},\dots,r_{k-1},s$ lie in the first $m$ columns of $T^{\prime}$,
and hence can bump $s^{\prime}$ out from its box only if
$c_{T}(s^{\prime})\leq m$ and none of the entries $s_{1},\dots,s_{n-1}$ appear
in the first $m$ columns. If this is the case, $c_{T^{\prime}}(s^{\prime})\leq
m+1$. Clearly, the entries $s_{1},\dots,s_{n-1}$ can bump $s^{\prime}$ out of
its box only if they move. Hence, assume that $s^{\prime}$ gets bumped out
from its box the first time by an $s_{i}$, then $s^{\prime}$ will always be
bumped out by $s_{i}$, unless it lands on a column which contains $s_{j}$ for
some $j$. If this is the case, then $s^{\prime}$ stays on that column. We
conclude that $c_{T^{\prime}}(s^{\prime})\leq c_{T^{\prime}}(s_{i})+1$, and
hence the statement follows by induction. ∎

Let $x\in S_{n}$ and $v\in S_{N}$ (for some $n\leq N$). We say that the
pattern of $v$ in the last $n$ positions is $x$ if it holds that
$v(N-n+i)<v(N-n+j)$ if and only if $x(i)<y(j)$ for all $1\leq i<j\leq n$.

Thanks to the first part of the previous lemma, we are now able to prove the
following central result.

######  Theorem 2.4.

Given $x,y\in S_{n}$, there exist $v,w\in S_{N}$ for some $N\geq n$ with
$P(v)=P(w)$, $v(i)=w(i)$ for $i\leq N-n$ and with the pattern of $v$ and $w$
in the last $n$ positions being the permutations $x$ and $y$.

###### Proof.

Let $k$ be the largest integer such that $P(x)$ and $P(y)$ have all entries
less than or equal to $k$ in the same place. (If $P(x)=P(y)$ we set $k=n$.) We
perform an induction on the value of $n-k$, the case $n-k=0$ being trivial.
Define $t$ by

$t=\max\\{c_{P(x)}(k+1),c_{P(y)}(k+1)\\}-1.$

Let $n^{\prime}=n+t$ and define $x^{\prime},y^{\prime}\in S_{n^{\prime}}$ by

$x^{\prime}(i)=\begin{cases}k+i&\mbox{if}\quad i\leq t,\\\
x(i-t)&\mbox{if}\quad i>t\mbox{ and }x(i-t)\leq k,\\\ x(i-t)+t&\mbox{if}\quad
i>t\mbox{ and }x(i-t)>k,\end{cases}$ (2.1)

with $y^{\prime}$ defined similarly from $y$.

By the description of $P$ in terms of column insertion, $P(x^{\prime})$ and
$P(y^{\prime})$ are obtained by inserting the numbers $k+t$, $k+t-1$, …,
$k+1$, into the tableau obtained from $P(x)$ and $P(y)$ by adding $t$ to all
entries greater than $k$. By Lemma 2.3(1), $P(x^{\prime})$ and $P(y^{\prime})$
agree for all entries less than or equal to $k+t+1$ (by the choice of $t$).

Let $k^{\prime}$ be defined from $x^{\prime}$ and $y^{\prime}$ analogously to
the definition of $k$. Then $n^{\prime}-k^{\prime}\leq(n+t)-(k+t+1)<n-k$. So
by induction there exists $v$ and $w$ with $P(v)=P(w)$ and the pattern of $v$
and $w$ in the last $n^{\prime}$ positions being the permutations $x^{\prime}$
and $y^{\prime}$. Since the patterns of $x^{\prime}$ and $y^{\prime}$ in the
last $n$ positions are those of $x$ and $y$ respectively, these $v$ and $w$
satisfy the conditions of the theorem, completing the proof. ∎

######  Example 2.5.

If $x=[21654387]$ and $y=[62845173]$, then the proof outputs the pair
$v=[895621a743cb]$ and $w=[8956a2c471b3]$, where $a=10$, $b=11$, $c=12$. This
example involves two invocations of Lemma 2.3.

We choose this example because the singularity of $X_{y}$ at $x$ is the
Kashiwara–Saito singularity [12, Example 8.3.1] and to point out that the pair
$v,w\in S_{12}$ that we obtain is different from the permutations chosen in
[22, Section 3.5]. The relevance of this example will be discussed in more
detail in Section 4.1.

######  Proposition 2.6.

In Theorem 2.4 above, we can always take $N\leq n(n+1)/2$.

###### Proof.

The inductive proof of Theorem 1.1 gives an algorithm for constructing $u$ and
$v$ from $x$ and $y$. It produces a sequence of permutations $\\{x_{i}\\}$,
$\\{y_{i}\\}$ where $x_{0}=x$, $y_{0}=y$ and $x_{i+1}=x_{i}^{\prime}$ and
$y_{i+1}=y_{i}^{\prime}$ are defined as in (2.1) where $k_{i}+1$ is the
minimal entry which appears in a different place in $P(x_{i})$ and $P(y_{i})$,
and $t_{i}=\max\\{c_{P(x_{i})}(k_{i}+1),c_{P(y_{i})}(k_{i}+1)\\}-1$. Let
$n_{i}=n+\sum_{j=0}^{i-1}t_{j}$ be the index of the symmetric group $x_{i}$
and $y_{i}$ lie in.

We prove now by induction on $i\geq 1$ that for any $l>k_{i-1}+t_{i-1}$ Let
$i=1$. By Lemma 2.3(2), either $c_{P(x_{1})}(l)=c_{P(x)}(l-t_{0})$ or
$c_{P(x_{1})}(l)\leq(t_{0}+1)+l-(k_{0}+1+t_{0})$. In the first case, the
thesis follows from $c_{P(x)}(l-t_{0})\leq l-t_{0}=l-n_{1}+n$, as $P(x)$ is
standard. As for the second case, we just notice that $k_{0}\geq t_{0}$, and
hence also in this case we have $c_{P(x_{1})}(l)\leq l-t_{0}$.

The induction step is proven analogously: by Lemma 2.3(2) we can distinguish
the two cases $c_{P(x_{i})}(l)=c_{P(x_{i-1})}(l-t_{i-1})$ and
$c_{P(x_{i})}(l-t_{i-1})\leq(t_{i-1}+1)+l-(k_{i-1}+1+t_{i-1})=l-k_{i-1}$. In
the first case, the thesis follows by induction, while for the second case it
is enough to observe that $k_{i-1}\geq n_{i}-n$, which follows inductively
from $k_{i}\geq k_{i-1}+t_{i-1}$.

Clearly, the same upper bound is obtained for $c_{P(y_{i})}(l)$. Since
$k_{i}+1>k_{i-1}+t_{i-1}$, we get

$c_{P(x_{i})}(k_{i}+1),c_{P(y_{i})}(k_{i}+1)\leq k_{i}+1-n_{i}+n.$

Therefore $t_{i}\leq n-(n_{i}-k_{i})$. We have $N=n+\sum_{i}t_{i}$. The proof
of Theorem 2.4 shows that the sequence $n_{i}-k_{i}$ is a strictly decreasing
sequence of positive integers and that we have at most $n-1$ iterations.
Therefore $N\leq n+\sum_{j=1}^{n-1}j=n(n+1)/2$. ∎

##  3 Interval pattern embeddings

Pattern avoidance has been applied to investigate properties of Schubert
varieties for several decades. The first, and arguably most famous, instance
of this is Lakshmibai–Sandhya’s criterion for smoothness [14]. We refer the
interested reader to [1] for a nice survey on the power of pattern avoidance
techniques and generalisations.

Here we exploit Woo–Yong’s approach of interval pattern embeddings, which
gives a sufficient condition for when two singularities in different Schubert
varieties are smoothly equivalent.

We first recall the notion of pattern embedding:

######  Definition 3.1 ([25, Section 2.1]).

Let $2\leq n\leq m$.

  1. 1.

Let $y\in S_{n}$ and $w\in S_{m}$. We say that $y$ embeds into $w$ if there
are indices $1\leq\varphi_{1}<\dots<\varphi_{n}\leq m$ such that
$w(\varphi_{j})<w(\varphi_{k})$ if and only if $y(j)<y(k)$ for any $1\leq
j<k\leq n$. In this case we say that the set
$\Phi=\\{\varphi_{1},\dots,\varphi_{n}\\}$ is an embedding of $y$ into $w$.

  2. 2.

Let $[x,y]$ and $[v,w]$ be two intervals in the Bruhat orders on $S_{n}$ and
$S_{m}$. We say that $[x,y]$ embeds into $[v,w]$ if there is a common
embedding $\Phi=\\{\varphi_{1},\dots,\varphi_{n}\\}$ of $x$ into $v$ and of
$y$ into $w$, where the entries of $v$ and $w$ agree outside of $\Phi$, and
$[x,y]\simeq[v,w]$ as posets.

Now we briefly recall the definitions of Schubert and Richardson varieties.

For $v_{1},\dots,v_{j}\in\mathbb{C}^{n}$, we denote by $\langle
v_{1},\dots,v_{j}\rangle$ the $\mathbb{C}$-subspace of $\mathbb{C}^{n}$ that
they span. Let $e_{1},e_{2},\dots,e_{n}$ be the standard basis of
$\mathbb{C}^{n}$, and, for $j=1,\dots,n-1$, we set

$E_{j}=\langle e_{1},\dots,e_{j}\rangle,\qquad\hbox{and}\qquad
E^{\textrm{opp}}_{j}=\langle e_{n},e_{n-1},\dots,e_{n-j+1}\rangle.$

Write $V_{\bullet}=\\{V_{0}\subset V_{1}\subset\cdots\subset V_{n}\\}$ for a
complete flag of subspaces of $\mathbb{C}^{n}$ with $\dim V_{p}=p$.

Let $w\in S_{n}$. The Schubert variety is defined by

$X_{w}=\big{\\{}V_{\bullet}\in\mathcal{F}l_{n}\mid\dim(V_{p}\cap E_{q})\geq
k_{p,q},\ 1\leq p,q\leq n\big{\\}},$ (3.1)

where $k_{p,q}=\\#\\{i\leq p\mid w(i)\leq q\\}$. For $v\in S_{n}$, the
opposite Schubert variety is defined by

$X^{v}=\big{\\{}V_{\bullet}\in\mathcal{F}l_{n}\mid\dim\big{(}V_{p}\cap
E^{\textrm{opp}}_{q}\big{)}\geq h_{p,q},\ 1\leq p,q\leq n\big{\\}},$

where $h_{p,q}=\\#\\{i\leq p\mid v(i)\geq n+1-q\\}$.

For a pair of permutations $x\leq y\in S_{n}$, we define the Richardson
variety

$X^{x}_{y}=X_{y}\cap X^{x}.$

The relevant result for us is the following.

######  Theorem 3.2 ([25, Theorem 4.2]).

Let $\Phi$ be an interval pattern embedding of $[x,y]$ into $[v,w]$. Then the
affine neighbourhoods of $X_{y}$ and $X_{w}$ respectively at $x$ and $v$ are
isomorphic up to a Cartesian product with an affine space.

######  Remark 3.3 ([24, Theorem 1]).

Under the same conditions, we also get an isomorphism of Richardson varieties
$X_{y}^{x}$ and $X_{w}^{v}$.

We are now ready to prove Theorem 1.1.

###### Proof of Theorem 1.1.

By Theorem 3.2, we only have to show that any iteration of our algorithm
produces an interval pattern embedding. We keep the same notation as in the
proof of Theorem 2.4.

By the explicit formula (2.1), we see that $\Phi=\\{t,t+1,\dots,n+t-1\\}$
gives a common embedding of $x$ into $x^{\prime}$ and $y$ into $y^{\prime}$
such that $x^{\prime}(j)=y^{\prime}(j)$ for any $1\leq j<t$.

We are now left to show that $[x,y]\simeq[x^{\prime},y^{\prime}]$ as posets.
By [25, Lemma 2.1], it is enough to check that

$\ell(y)-\ell(x)=\ell(y^{\prime})-\ell(x^{\prime}),$

where $\ell(w)=\\#\\{i<j\mid w(i)>w(j)\\}$ for any permutation $w$. This is an
immediate consequence of (2.1), from which we see that

$\ell(x^{\prime})=\ell(x)+(t-1)(k-1)\qquad\hbox{and}\qquad\ell(y^{\prime})=\ell(y)+(t-1)(k-1).$

##  4 Some applications

###  4.1 Associated varieties of highest weight modules

A detailed account of the constructions and properties we mention in this
section can be found, for example, in [19, Section 1].

Let $\rho$ be half the sum of the positive roots of
$\mathfrak{sl}_{n}(\mathbb{C})$. For a permutation $w\in S_{n}$, we denote by
$L_{w}$ the simple $\mathfrak{sl}_{n}(\mathbb{C})$-module of highest weight
$-w(\rho)-\rho$. Denote by $\mathcal{D}$ the sheaf of complex algebraic linear
differential operators on the flag variety $\mathcal{F}l_{n}$ and by
$\mathcal{L}_{w}$ the $\mathcal{D}$-module corresponding to $L_{w}$ under the
Beilinson–Bernstein correspondence, that is the $IC$-extension of the constant
local system $\underline{\mathbb{C}}_{C_{w}}$ of the cell $C_{w}$. Its
characteristic variety $\tt{Ch}(\mathcal{L}_{w})$ is a subvariety of the
cotangent bundle $T^{*}\mathcal{F}l_{n}$ and the corresponding characteristic
cycle is a $\mathbb{Z}_{\geq 0}$-linear combination of the classes of the
(closures) of conormal bundles of the Schubert cells:

$CC(\mathcal{L}_{y})=\sum_{x\leq
y}m_{x,y}[\overline{T^{*}_{x}\mathcal{F}l_{n}}].$

Determining the numbers $m_{x,y}$ is a natural (but in general very hard)
question. As $m_{y,y}=1$, the characteristic variety
$\tt{Ch}(\mathcal{L}_{y})$ is irreducible if and only if $m_{x,y}=0$ for any
$x\neq y$. The $m_{x,y}$’s only depend on the singularity type of the Schubert
variety $X_{y}$ at $x$ (see [20, Section 3.2]). Thus, we have the following
corollary of Theorem 1.1:

######  Corollary 4.1.

Let $x$, $y$, $v$, $w$ be as in Theorem 1.1. Then $m_{x,y}=m_{v,w}$.

The associated variety $V(L_{w})$ can be obtained as the image of
$\tt{Ch}(\mathcal{L}_{w})$ under the moment map $\gamma\colon
T^{*}\mathcal{F}l_{n}\rightarrow\mathfrak{g}^{*}$. This variety $V(L_{w})$ is
irreducible if and only if $m_{x,y}=0$ for any $x\neq y$ such that $x$ and $y$
lie in the same two-sided Kazhdan–Lusztig cell (see [22, Introduction] for a
sketch of a proof of this fact).

While several examples of reducible characteristic varieties have been known
for a long time, it was conjectured that the associated varieties for
$\mathfrak{sl}_{n}(\mathbb{C})$-highest weight modules were irreducible (cf.
[3, Conjecture 4.5] and [11, Section 10.2]). The first example of a reducible
associated variety was exhibited by Williamson in [22]. This was found by a
computer search motivated by constraints that must be satisfied in order for
torsion to occur in the intersection cohomology of Schubert varieties.

Williamson’s example ended up producing a singularity in the $S_{12}$ flag
variety where $x$ and $y$ belong to in the same right cell and $m_{x,y}\neq
0$. It was then shown that this singularity is smoothly equivalent to the one
studied by Kashiwara and Saito [12] where the corresponding characteristic
variety was shown to be reducible. Since the $m_{x,y}$’s only depend on the
singularity type of the Schubert variety $X_{y}$ at $x$, this yields a
reducible associated variety. Corollary 4.1 gives a simpler and systematic
method for producing similar examples. See Example 2.5.

######  Remark 4.2.

By [19, Section 3.1(A)], the irreducibility of an associated variety is
equivalent to the coincidence of two bases (the _Goldie rank_ basis and the
_Springer basis_) of a complex irreducible $S_{n}$-representation, so that our
algorithm also provides a method to determine examples of representations for
which the two bases differ. A similar question is addressed in Section 4.3,
where we explain how to apply Theorem 1.1 to the comparison of bases of Specht
modules for the Hecke algebra of a symmetric group.

###  4.2 The 0-1 conjecture and edges of $\boldsymbol{W}$-graphs for symmetric
groups

Let $x,y\in S_{n}$. Let $\mu_{x,y}$ be the coefficient of
$q^{(\ell(y)-\ell(x)-1)/2}$ in the Kazhdan–Lusztig polynomial $P_{x,y}(q)$,
where $\ell(z)$ denotes the number of inversions of $z\in S_{n}$. This is the
highest possible monomial that can occur in $P_{x,y}(q)$. The _$0$ -$1$
conjecture_ stated that $\mu_{x,y}\in\\{0,1\\}$. This conjecture was disproven
in [15] by producing a pair of permutations $x,y\in S_{10}$ with $\mu_{x,y}=4$
via combinatorial methods. We note here that in their example $x$ and $y$
belong to different left cells.

A weaker hope was that the 0-1 conjecture was valid once restricted to pairs
of permutations lying in the same left cell.

The relevance of such a conjecture is in the representation theory of the
symmetric group Hecke algebra. Indeed, in [13] Kazhdan and Lusztig associated
with any left cell a representation which could be read off from its
$W$-graph, which is a graph having as set of vertices the elements of the cell
and edges between any pair $x<y$ labelled by $\mu_{x,y}$. The 0-1 conjecture
would have implied that these labels are unnecessary. A counterexample to this
weaker version of the 0-1 conjecture was exhibited in [15] and relied on
computer computations.

By [25, Corollary 6.3], if $x$, $y$, $v$, $w$ are as in Theorem 1.1, then
$P_{x,y}(q)=P_{v,w}(q)$, so that in particular we have the following
corollary:

######  Corollary 4.3.

If $x$, $y$, $v$, $w$ are as in Theorem 1.1, then $\mu_{x,y}=\mu_{v,w}$.

It is hence enough to find a pair of permutations $x$, $y$ not necessarily in
the same cell with $\mu_{x,y}>1$ to produce a pair $v^{-1}$, $w^{-1}$ of
elements belonging to the same left cell and satisfying
$\mu_{v^{-1},w^{-1}}>1$ (as $P_{v,w}=P_{v^{-1},w^{-1}}$). Since $v$ and $w$
are in the same right cell, $v^{-1}$ and $w^{-1}$ are in the same left cell.
Therefore, the failure of the weaker conjecture can be now deduced by
combining McLarnan–Warrington’s counterexample to the 0-1 conjecture together
with Corollary 4.3. As an illustration, we compute explicitly the obtained
counterexample to the weaker conjecture.

Let us identify $S_{10}$ with the permutation of the set $\\{0,1,\dots,9\\}$.
The second part of [15, Theorem 1] says that if

$x=[4321098765],\qquad y=[9467182350]$

then $\mu_{x,y}=4$. The algorithm in the proof of Theorem 2.4 applied to $x$,
$y$ outputs the pair

$\displaystyle v=[nopqrhijklcdef7845296310smgba],$ $\displaystyle
w=[nopqrhijklcdef78452s9bg1m36a0],$

where we identified $S_{29}$ with the permutations of
$\\{0,\dots,9,a,b,\dots,s\\}$.

The pair $v^{-1}$, $w^{-1}$ is an instance of two permutations lying in the
same left cell and having
$\mu_{v^{-1},w^{-1}}=\mu_{x^{-1},y^{-1}}=\mu_{x,y}=4>1$. Thanks to our main
result, this pair can be obtained more conceptually. We want to point out that
our counterexample does not appear in the smallest possible rank. In fact the
counterexample provided in the second part of [15, Theorem 1] lies in $S_{16}$
(and has $\mu_{v,w}=5$).

###  4.3 Bases of Specht modules

Consider the Hecke algebra $H_{n}(q)$ of the symmetric group $S_{n}$. Let
$\\{H_{x}\\}_{x\in S_{n}}$ be the Kazhdan–Lusztig basis of $H_{n}(q)$ as a
$\mathbb{Z}\big{[}q^{\pm\frac{1}{2}}\big{]}$-module. This is a cellular basis
(cf. [6, Example 1.2]). Let $\lambda$ be a partition and $Q$ a standard
tableau of shape $\lambda$. Since the Kazhdan–Lusztig basis is cellular, the
set

$\\{H_{x}\mid Q(x)=Q\\}$

is a basis of the Specht module $S^{\lambda}$ which does not depend on the
choice of $Q$. We call this the KL basis of $S^{\lambda}$. Jensen [8] studies
the analogous situation for the $p$-Kazhdan–Lusztig basis
$\\{^{p}H_{x}\\}_{x\in S_{n}}$ of $H_{n}(q)$ – defined in terms of parity
sheaves on the flag variety. Here $p$ is a prime. One defines left, right and
two-sided $p$-cells analogously to the case of the Kazhdan–Lusztig basis.
Jensen [8, Theorem 4.33] shows that these $p$-cells are the same as the
Kazhdan–Lusztig cells. Furthermore, in [8, Corollary 4.39], he shows that

$\\{^{p}H_{x}\mid Q(x)=Q\\}$

is a basis of the Specht module $S^{\lambda}$ which does not depend on the
choice of $Q$. We call this the $p$-KL basis of $S^{\lambda}$.111After this
was written, Jensen [9] further proved that the $p$-Kazhdan Lusztig basis is
cellular.

Define the transition matrix $(^{p}m_{xy})_{x,y\in S_{n}}$ by

${}^{p}H_{y}=\sum_{x}{}^{p}m_{xy}H_{x}.$

By Theorem 3.2 and [21, Theorem 3.7], if the pair $(x,y)$ is such that $x\neq
y$ and $x$ is a maximal (w.r.t. the Bruhat order) such that ${}^{p}m_{xy}\neq
0$ then the pair $(v,w)$ has the same property for any interval pattern
embedding of $[x,y]$ into $[v,w]$. Thus, we obtain a third immediate
application of Theorem 1.1.

######  Corollary 4.4.

If $x$, $y$, $v$, $w$ are as in Theorem 1.1 and $x$ is a maximal element $\neq
y$ such that ${}^{p}m_{xy}\neq 0$ then ${}^{p}m_{v,w}\neq 0$.

If we can find $x$ and $y$ with $x\neq y$, $Q(x)=Q(y)$ and ${}^{p}m_{xy}\neq
0$, then the KL and $p$-KL bases of the corresponding Specht module will
disagree. Thus, Corollary 4.4 is designed to provide such examples, whenever
we can find any $x\neq y$ maximal with the property that ${}^{p}m_{xy}\neq 0$.
For instance, in Example 2.5, ${}^{2}m_{v,w}\neq 0$ [10, Section 5.6], and
$P(v)=P(w)$ have shape $\lambda=(4,4,2,2)$. Hence the KL basis of
$S^{(4,4,2,2)}$ disagrees with the 2-KL basis.

For instance, transferring the torsion explosion examples from [23] and
applying Proposition 2.6, we get infinitely many examples where these bases
differ with $n<A(\log p)^{2}$ for some constant $A$ (we have made no effort to
optimise this bound).

By transferring the examples of non-perverse parity sheaves from [16], we see
that the change of basis matrix within a Specht module can contain polynomials
in $q$ of arbitrarily large degree.

The $W$-graph for the KL basis of a Specht module is bipartite. Since Nguyen
[17, Theorem 9.8] shows that all strongly connected admissible $W$-graphs in
type $A$ are the Kazhdan–Lusztig ones, this implies that whenever the $p$-KL
basis differs from the KL basis, the corresponding $W$-graph for the $p$-KL
basis is not bipartite. An explicit example of a non-bipartite $W$-graph for
$p=2$ in type $C_{3}$ was previously exhibited in [8].

### Acknowledgements

The authors would like to thank the Institut Henri Poincaré in Paris, and the
organisers of the “Representation Theory” Trimester. M.L. acknowledges the
MIUR Excellence Department Project awarded to the Department of Mathematics,
University of Rome Tor Vergata, CUP E83C18000100006, and the PRIN2017 CUP
E8419000480006. P.M. acknowledges support from ARC grants DE150101415 and
DP180103150. We thank G. Williamson for useful conversations and the anonymous
referees for their valuable input.

## References

  * [1] Abe H., Billey S., Consequences of the Lakshmibai–Sandhya theorem: the ubiquity of permutation patterns in Schubert calculus and related geometry, in Schubert Calculus – Osaka 2012, Adv. Stud. Pure Math., Vol. 71, Editors H. Naruse, T. Ikeda, M. Masuda, T. Tanisaki, Math. Soc. Japan, Tokyo, 2016, 1–52, arXiv:1403.4345.
  * [2] Ariki S., Robinson–Schensted correspondence and left cells, in Combinatorial Methods in Representation Theory (Kyoto, 1998), Adv. Stud. Pure Math., Vol. 28, Kinokuniya, Tokyo, 2000, 1–20, arXiv:math.QA/9910117.
  * [3] Borho W., Brylinski J.-L., Differential operators on homogeneous spaces. III. Characteristic varieties of Harish-Chandra modules and of primitive ideals, Invent. Math. 80 (1985), 1–68.
  * [4] Bosma W., Cannon J., Playoust C., The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), 235–265.
  * [5] Garsia A.M., McLarnan T.J., Relations between Young’s natural and the Kazhdan–Lusztig representations of $S_{n}$, Adv. Math. 69 (1988), 32–92.
  * [6] Graham J.J., Lehrer G.I., Cellular algebras, Invent. Math. 123 (1996), 1–34.
  * [7] Howlett R., Nguyen V.M., W-graph magma programs, available at http://www.maths.usyd.edu.au/u/bobh/magma/, 2013.
  * [8] Jensen L.T., The ABC of $p$-cells, Selecta Math. (N.S.) 26 (2020), 28, 46 pages, arXiv:1901.02323.
  * [9] Jensen L.T., Cellularity of the $p$-canonical basis for symmetric groups, arXiv:2009.11715.
  * [10] Jensen L.T., Williamson G., The $p$-canonical basis for Hecke algebras, in Categorification and Higher Representation Theory, Contemp. Math., Vol. 683, Amer. Math. Soc., Providence, RI, 2017, 333–361, arXiv:1510.01556.
  * [11] Joseph A., On the variety of a highest weight module, J. Algebra 88 (1984), 238–278.
  * [12] Kashiwara M., Saito Y., Geometric construction of crystal bases, Duke Math. J. 89 (1997), 9–36, arXiv:q-alg/9606009.
  * [13] Kazhdan D., Lusztig G., Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165–184.
  * [14] Lakshmibai V., Sandhya B., Criterion for smoothness of Schubert varieties in ${\rm Sl}(n)/B$, Proc. Indian Acad. Sci. Math. Sci. 100 (1990), 45–52.
  * [15] McLarnan T.J., Warrington G.S., Counterexamples to the 0-1 conjecture, Represent. Theory 7 (2003), 181–195, arXiv:math.CO/0209221.
  * [16] McNamara P.J., Non-perverse parity sheaves on the flag variety, arXiv:1812.00178.
  * [17] Nguyen V.M., Type $A$ admissible cells are Kazhdan–Lusztig, Algebr. Comb. 3 (2020), 55–105, arXiv:1807.07457.
  * [18] Stanley R.P., Enumerative combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, Vol. 62, Cambridge University Press, Cambridge, 1999.
  * [19] Tanisaki T., Characteristic varieties of highest weight modules and primitive quotients, in Representations of Lie Groups, Kyoto, Hiroshima, 1986, Adv. Stud. Pure Math., Vol. 14, Academic Press, Boston, MA, 1988, 1–30.
  * [20] Vilonen K., Williamson G., Characteristic cycles and decomposition numbers, Math. Res. Lett. 20 (2013), 359–366, arXiv:1208.1198.
  * [21] Williamson G., On an analogue of the James conjecture, Represent. Theory 18 (2014), 15–27, arXiv:1212.0794.
  * [22] Williamson G., A reducible characteristic variety in type $A$, in Representations of Reductive Groups, Progr. Math., Vol. 312, Birkhäuser/Springer, Cham, 2015, 517–532, arXiv:1405.3479.
  * [23] Williamson G., Schubert calculus and torsion explosion (with a joint appendix with Alex Kontorovich and Peter J. McNamara), J. Amer. Math. Soc. 30 (2017), 1023–1046, arXiv:1309.5055.
  * [24] Woo A., Interval pattern avoidance for arbitrary root systems, Canad. Math. Bull. 53 (2010), 757–762, arXiv:math.CO/0611328.
  * [25] Woo A., Yong A., Governing singularities of Schubert varieties, J. Algebra 320 (2008), 495–520, arXiv:math.AG/0603273.


# Robust Approximate Simulation for Hierarchical Control of Piecewise
Affine Systems under Bounded Disturbances

Zihao Song, Vince Kurtz, Shirantha Welikala, Panos J. Antsaklis and Hai Lin
This work was supported by the National Science Foundation under Grant
IIS1724070, Grant CNS-1830335, and Grant IIS-2007949. The authors are with the
Department of Electrical Engineering, University of Notre Dame, Notre Dame, IN
46556 USA (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>pantsakl@nd.edu). The first author sincerely appreciates Dr. P.
M. Wensing for several fruitful discussions.

###### Abstract

Piecewise affine (PWA) systems are widely applied in many practical cases such
as the control of nonlinear systems and hybrid dynamics. However, most of the
existing PWA control methods have poor scalability with respect to the number
of modes and system dimensions and may not be robust to the disturbances in
performance. In this paper, we present a robust approximate simulation based
control method for PWA systems under bounded external disturbances. First, a
lower-dimensional linear system (abstraction) and an associated _interface_
are designed to enable the output of the PWA system (concrete system) to track
the output of the abstraction. Then, a Lyapunov-like _simulation function_ is
designed to show the boundedness of the output errors between the two systems.
Furthermore, the results obtained for linear abstraction are extended to the
case that a simpler PWA system is the abstraction. To illustrate the
effectiveness of the proposed approach, simulation results are provided for
two design examples.

##  I Introduction

Piecewise Affine (PWA) systems are an important and powerful modeling tool
that can globally approximate nonlinear systems with finite number of linear
characteristics on partitions [1]. In this case, controllers can be designed
based on linear system control theories and better accommodate the existing
nonlinearities. Because of this advantage, PWA systems are applicable in many
engineering fields, and thus have attracted a plenty of attention since it was
first proposed. Moreover, PWA systems are particularly used in situations
where a plant operates in different modes or under physical constraints such
as in robot locomotion [2], manipulation with contacts [3] and hybrid control
systems [4].

In recent years, together with Mixed Logical Dynamical (MLD) systems, PWA
systems are the most popular modeling framework for hybrid systems in Model
Predictive Control (MPC) [5]. However, such on-line optimal control methods
typically lead to the synthesis of very inefficient Mixed-Integer Convex
Programs (MICPs) with large computational price [6]. To reduce the complexity
of computing the convex polyhedra for PWA systems, an optimal sampling-based
controller is proposed in [7], which can be cast into a single MICP problem.
Nevertheless, for general PWA systems, the aforementioned on-line control
strategies deteriorate with the number of partitions and the dimension of the
systems. Similarly, the existing off-line controller design approaches for PWA
(e.g., the LMI based controller synthesis approaches [8]) scale poorly for
high dimensional PWA systems. Therefore, the controller synthesis for high-
dimensional PWA systems with a great number of partitions is still an open
problem.

Approximate simulation is an extension of simulation relations from formal
methods to continuous systems. It is a powerful tool often used for
hierarchical control of complex and high-dimensional systems [9, 10, 11]. This
approximate simulation framework defines an approximate relationship between
two systems, i.e. the full-order (concrete) system and the reduced-order
system (abstraction). By constructing an abstraction and a corresponding
_interface_ between this abstraction and the concrete system, the outputs of
both systems can be guaranteed to remain close within some certain error bound
characterized by a Lyapunov-like _simulation function_. Different from the
asymptotic model matching [12] that enforces output global asymptotic
stability of the involved systems, it is not required in approximate
simulation framework that the trajectories of the system and its abstraction
match exactly but only approximately. This relaxation allows us to consider
simpler abstractions and thus simplify the design of high-level control tasks.

Motivated by the above observations, we extend the results in [11] to consider
the case where the concrete system is a PWA system. Our primary contributions
can be summarized as follows:

  1. 1.

A novel robust approximate simulation based control strategy is proposed for
the control of PWA systems using a linear system as the abstraction;

  2. 2.

The results obtained in the linear system abstraction approach is generalized
for the case that the abstraction is a simpler PWA system.

The remainder of this paper is organized as follows. The problem formulation
and some necessary preliminaries are presented in Section II. Our main results
are presented in Section III, and are supported by simulation examples in
Section IV. Finally, concluding remarks are provided in Section V.

##  II Background

###  II-A Problem Formulation

Consider a piecewise-affine (PWA) system as follows

$\Sigma:\left\\{\begin{array}[]{ll}\mathbf{\dot{x}}_{1}=\mathbf{A}_{i}\mathbf{x}_{1}+\mathbf{B}_{i}\mathbf{u}_{1}+\mathbf{c}_{i}&\\\
\mathbf{y}_{1}=\mathbf{C}_{i}\mathbf{x}_{1}&\end{array}\right.$ (1)

where the system state
$\mathbf{x}_{1}\in\mathcal{X}_{1}^{i}:=\\{\mathbf{x}_{1}\in\mathbb{R}^{n}|\
\mathbf{E}_{i}\mathbf{x}_{1}\geq\mathbf{f}_{i}\\}$, and
$\mathbf{E}_{i}\in\mathbb{R}^{b\times n}$, $\mathbf{f}_{i}\in\mathbb{R}^{b}$,
$\mathbf{A}_{i}\in\mathbb{R}^{n\times n}$,
$\mathbf{B}_{i}\in\mathbb{R}^{n\times p}$ and
$\mathbf{C}_{i}\in\mathbb{R}^{k\times n}$ are given, for
$i\in\mathcal{I}:=\\{1,...,s\\}$. The system output is
$\mathbf{y}_{1}\in\mathbb{R}^{k}$. The term $\mathbf{c}_{i}\in\mathbb{R}^{n}$,
which represents the lumped bounded external disturbances and piecewise
linearization error, is assumed to be bounded such that
$||\mathbf{c}_{i}||_{\infty}\leq\bar{c}_{i}$, where $\bar{c}_{i}$ is known.
The cell bounding [13] is defined as
$\mathbf{\bar{E}}_{i}=\begin{bmatrix}\mathbf{E}_{i}&-\mathbf{f}_{i}\end{bmatrix}$
for the partitions with some of the boundaries not crossing the origin
(denoted as $\mathcal{I}_{1}$), with
$\mathbf{\bar{E}}_{i}\begin{bmatrix}\mathbf{x}_{1}^{T}&1\end{bmatrix}^{T}\geq\mathbf{0}$
and it reduces to $\mathbf{E}_{i}$ for the partitions with all their
boundaries crossing the origin (denoted as $\mathcal{I}_{0}$), with
$\mathbf{E}_{i}\mathbf{x}_{1}\geq\mathbf{0}$. Besides, the continuity matrix
[13] is defined as
$\mathbf{\bar{J}}_{i}=\begin{bmatrix}\mathbf{J}_{i}&h_{i}\end{bmatrix}$ for
$i\in\mathcal{I}_{1}$ (and $\mathbf{J}_{i}$ for $i\in\mathcal{I}_{0}$), with
$\mathbf{\bar{J}}_{i_{1}}\begin{bmatrix}\mathbf{x}_{1}^{T}&1\end{bmatrix}^{T}=\mathbf{\bar{J}}_{i_{2}}\begin{bmatrix}\mathbf{x}_{1}^{T}&1\end{bmatrix}^{T}$
for $\mathcal{X}_{1}^{i_{1}}\cap\mathcal{X}_{1}^{i_{2}}$, $i_{1}$,
$i_{2}\in\mathcal{I}$.

In this paper, we first consider the abstraction as a linear system of the
following form

$\Sigma^{\prime}:\left\\{\begin{array}[]{ll}\mathbf{\dot{x}}_{2}=\mathbf{F}\mathbf{x}_{2}+\mathbf{G}\mathbf{u}_{2}&\\\
\mathbf{y}_{2}=\mathbf{H}\mathbf{x}_{2}&\end{array}\right.$ (2)

where $\mathbf{x}_{2}\in\mathbb{R}^{m}$ is the state of system (2),
$\mathbf{y}_{2}\in\mathbb{R}^{k}$ is the system output. The matrices
$\mathbf{F}\in\mathbb{R}^{m\times m}$, $\mathbf{G}\in\mathbb{R}^{m\times q}$
and $\mathbf{H}\in\mathbb{R}^{k\times m}$ are free to select. The abstraction
(2) is typically simpler than each mode of the PWA system $\Sigma$ in terms of
system dimension, i.e., $m\leq n$.

Then, if a single linear abstraction may not be completely adequate (typically
if the concrete PWA system $\Sigma$ has many modes), the abstraction can be
selected as a simpler PWA system of the form

$\Sigma^{\prime\prime}:\left\\{\begin{array}[]{ll}\mathbf{\dot{x}}_{2}=\mathbf{F}_{j}\mathbf{x}_{2}+\mathbf{G}_{j}\mathbf{u}_{2}&\\\
\mathbf{y}_{2}=\mathbf{H}_{j}\mathbf{x}_{2}&\end{array}\right.$ (3)

where
$\mathbf{x}_{2}\in\mathcal{X}_{2}^{j}:=\\{\mathbf{x}_{2}\in\mathbb{R}^{m}|\
\mathbf{E}_{aj}\mathbf{x}_{2}\geq\mathbf{f}_{aj}\\}$,
$\mathbf{E}_{aj}\in\mathbb{R}^{d\times m}$,
$\mathbf{f}_{aj}\in\mathbb{R}^{d}$, $\mathbf{y}_{2}\in\mathbb{R}^{k}$, for
$j\in\mathcal{I}_{a}:=\\{1,...,r\\}$ with $r\leq s$. The matrices
$\mathbf{F}_{j}\in\mathbb{R}^{m\times m}$,
$\mathbf{G}_{j}\in\mathbb{R}^{m\times q}$ and
$\mathbf{H}_{j}\in\mathbb{R}^{k\times m}$ are free to select, for
$j\in\mathcal{I}_{a}$. Let us denote the partitions with all their boundaries
crossing the origin as $\mathcal{I}_{a0}$ and the partitions with some of the
boundaries not crossing the origin as $\mathcal{I}_{a1}$. It is important to
note that the abstraction $\Sigma^{\prime\prime}$ has less modes and much
simpler dynamics than the concrete system $\Sigma$. The details of the
partitions of the abstract PWA system will be studied in Section III.

Consider the abstraction in (2). Define
$\mathbf{\tilde{x}}=\mathbf{x}_{1}-\mathbf{P}_{i}\mathbf{x}_{2}$, where
$\mathbf{P}_{i}\in\mathbb{R}^{n\times m}$ is an injective map from the state
space of $\mathbf{x}_{2}$ to that of $\mathbf{x}_{1}$ for $i\in\mathcal{I}$.
Then,

$\displaystyle\mathbf{\dot{\tilde{x}}}$
$\displaystyle=\mathbf{\dot{x}}_{1}-\mathbf{P}_{i}\mathbf{\dot{x}}_{2}$
$\displaystyle=(\mathbf{A}_{i}\mathbf{x}_{1}+\mathbf{B}_{i}\mathbf{u}_{1}+\mathbf{c}_{i})-\mathbf{P}_{i}(\mathbf{F}\mathbf{x}_{2}+\mathbf{G}\mathbf{u}_{2})$
$\displaystyle=\mathbf{A}_{i}\mathbf{\tilde{x}}+\mathbf{B}_{i}\mathbf{u}_{v}+\mathbf{A}_{i}\mathbf{P}_{i}\mathbf{x}_{2}+\mathbf{c}_{i}-\mathbf{P}_{i}(\mathbf{F}\mathbf{x}_{2}+\mathbf{G}\mathbf{u}_{2})$

where
$\mathbf{u}_{v}:=\mathbf{u}_{1}(\mathbf{\tilde{x}},\mathbf{x}_{2},\mathbf{\bar{u}}_{2})$
is the control input of the concrete system, which is also known as the
_interface_ that we need to design. For the abstraction (2), an input
transformation law is designed as

$\mathbf{u}_{2}=\mathbf{L}\mathbf{x}_{2}+\mathbf{\bar{u}}_{2}$ (4)

where the matrix $\mathbf{L}\in\mathbb{R}^{q\times m}$ is selected such that
all the eigenvalues of the matrix $\mathbf{F}+\mathbf{G}\mathbf{L}$ of the
transformed abstraction $\Sigma^{\prime}$ have negative real parts, and
$\mathbf{\bar{u}}_{2}\in\mathbb{R}^{q}$ is the transformed input. Thus, we
define our _robust approximate simulation framework_ as the following joint
system

$\left\\{\begin{array}[]{ll}\mathbf{\dot{\tilde{x}}}=\mathbf{A}_{i}\mathbf{\tilde{x}}+\mathbf{B}_{i}\mathbf{u}_{v}-[\mathbf{B}_{i}\mathbf{Q}_{i}+\mathbf{P}_{i}\mathbf{G}\mathbf{L}]\mathbf{x}_{2}-\mathbf{P}_{i}\mathbf{G}\mathbf{\bar{u}}_{2}+\mathbf{c}_{i}&\\\
\mathbf{\dot{x}}_{2}=(\mathbf{F}+\mathbf{G}\mathbf{L})\mathbf{x}_{2}+\mathbf{G}\mathbf{\bar{u}}_{2}&\\\
\mathbf{e}=\mathbf{y}_{1}-\mathbf{y}_{2}=\mathbf{C}_{i}\mathbf{\tilde{x}}&\end{array}\right.$
(5)

for $i\in\mathcal{I}$, where $\mathbf{P}_{i}\in\mathbb{R}^{n\times m}$ and
$\mathbf{Q}_{i}\in\mathbb{R}^{n\times m}$ satisfy the conditions:

$\mathbf{H}=\mathbf{C}_{i}\mathbf{P}_{i},\
\mathbf{P}_{i}\mathbf{F}=\mathbf{A}_{i}\mathbf{P}_{i}+\mathbf{B}_{i}\mathbf{Q}_{i}$
(6)

Define the state of the joint system as
$\bm{\omega}=\begin{bmatrix}\mathbf{\tilde{x}}^{T}&\mathbf{x}_{2}^{T}\\\
\end{bmatrix}^{T}$. Then, the joint partitions can be written as

$\begin{split}\bm{\omega}\in\mathbf{\Omega}_{i}:&=\\{\mathbf{E}_{i}(\mathbf{x}_{1}-\mathbf{P}_{i}\mathbf{x}_{2})+\mathbf{E}_{i}\mathbf{P}_{i}\mathbf{x}_{2}\geq\mathbf{f}_{i}\\}\\\
&=\\{[\mathbf{E}_{i}\
\mathbf{E}_{i}\mathbf{P}_{i}]\bm{\omega}\geq\mathbf{f}_{i}\\}\end{split}$ (7)

Note that the joint partition (7) can be equivalently represented by:

$\begin{split}\bm{\bar{\omega}}\in\mathbf{\bar{\Omega}}_{i}:&=\\{\begin{bmatrix}\mathbf{E}^{\prime}_{i}&\mathbf{f}^{\prime}_{i}\end{bmatrix}\begin{bmatrix}\bm{\omega}\\\
1\end{bmatrix}\geq\mathbf{0}\\}=\\{\mathbf{\bar{E}}_{i}\bm{\bar{\omega}}\geq\mathbf{0}\\}\end{split}$
(8)

where
$\mathbf{E}^{\prime}_{i}=\begin{bmatrix}\mathbf{E}_{i}&\mathbf{E}_{i}\mathbf{P}_{i}\end{bmatrix}$
and $\mathbf{f}^{\prime}_{i}=-\mathbf{f}_{i}$.

The joint system (5) corresponding to the PWA system abstraction (3) is
similar to that of the linear system abstraction (2). In particular, it will
result in a joint system of the form (5) for each tuple ($\mathbf{F}_{j}$,
$\mathbf{G}_{j}$, $\mathbf{L}_{j}$), for $j\in\mathcal{I}_{a}$, and the
conditions in (6) become

$\mathbf{H}_{j}=\mathbf{C}_{i}\mathbf{P}_{i},\
\mathbf{P}_{i}\mathbf{F}_{j}=\mathbf{A}_{i}\mathbf{P}_{i}+\mathbf{B}_{i}\mathbf{Q}_{i}$
(9)

for $i\in\mathcal{I}$. In other words, for each $i\in\mathcal{I}$ we need to
determine matrices $\mathbf{P}_{i}$ and $\mathbf{Q}_{i}$ such that (9) holds
true for a pair ($\mathbf{F}_{j}$, $\mathbf{H}_{j}$), $j\in\mathcal{I}_{a}$.
The details of the joint partitions corresponding to this case will be
discussed in Section III.

###### Remark 1

The input transformation law (4) is introduced to increase the tunability of
the matrix $\mathbf{F}$ (or $\mathbf{F}_{j}$ for the PWA abstraction (3)).
Besides, it will be shown in Section III that some LMI based conditions should
be satisfied with all the eigenvalues of ($\mathbf{F}+\mathbf{G}\mathbf{L}$)
(or ($\mathbf{F}_{j}+\mathbf{G}_{j}\mathbf{L}_{j}$) for the PWA abstraction
(3)) having negative real parts.

The objective of this paper is to design an interface
$\mathbf{u}_{v}:=\mathbf{u}_{1}(\mathbf{\tilde{x}},\mathbf{x}_{2},\mathbf{\bar{u}}_{2})$
for the joint system (5) over the joint partitions (e.g.,(7)) to guarantee the
boundedness of output error between $\mathbf{y}_{1}$ and $\mathbf{y}_{2}$,
i.e., $||\mathbf{e}||=||\mathbf{y}_{1}-\mathbf{y}_{2}||\leq\delta$, where
$\delta\in\mathbb{R}_{\geq 0}$ is some certain error bound. The basic control
architecture proposed in this paper is shown in Figure 1.

Interface
$\mathbf{u}_{v}=\mathbf{u}_{1}(\mathbf{\tilde{x}},\mathbf{x}_{2},\mathbf{\bar{u}}_{2})$Concrete
System $\mathbf{x}_{1}$Transformed Abstraction
$\mathbf{x}_{2}$$\mathbf{\bar{u}}_{2}$$\mathbf{x}_{2}$$\mathbf{u}_{1}$$\mathbf{x}_{1}$$\mathbf{c}_{i}$$\mathbf{y}_{2}$$\mathbf{y}_{1}$
Figure 1: Hierarchical control system architecture considered in this work. We
extend the robust approximate simulation [11] to consider the case where the
concrete system is a PWA system.

###  II-B Robust Approximate Simulation

###### Definition 1

(Approximate Simulation [9]) A relation
$\mathcal{R}\subseteq\mathbb{R}^{m}\times\mathbb{R}^{n}$ is an approximate
simulation relation of precision $\delta$ between $\Sigma$ and
$\Sigma^{\prime}$ if for all $(\mathbf{x}_{20},\
\mathbf{x}_{10})\in\mathcal{R}$,

$1)$ $||\mathbf{y}_{10}-\mathbf{y}_{20}||\leq\delta$, where $\mathbf{y}_{10}$
and $\mathbf{y}_{20}$ are the initial values of $\mathbf{y}_{1}$ and
$\mathbf{y}_{2}$ at $\mathbf{x}_{10}$ and $\mathbf{x}_{20}$, respectively;

$2)$ For any state trajectory $\mathbf{x}_{2}(t)$ of $\Sigma^{\prime}$ such
that $\mathbf{x}_{2}(0)=\mathbf{x}_{20}$, there exists a state trajectory
$\mathbf{x}_{1}(t)$ of $\Sigma$ such that $\mathbf{x}_{1}(0)=\mathbf{x}_{10}$
and $(\mathbf{x}_{2}(t),\mathbf{x}_{1}(t))\in\mathcal{R}$, for all $t\geq 0$.

###### Definition 2

(Robust Approximate Simulation [14]) The relation $\mathcal{R}$ is a robust
approximate simulation relation if the approximate simulation relation still
hold for any disturbances $\mathbf{c}_{i}$ in some set
$\mathcal{D}\subseteq\mathbb{R}^{n}$.

##  III Main Results

In this section, we first analyze the case where the linear system is the
abstraction. Then, we extend the established theoretical results to the case
where the PWA system is the abstraction. In each case, we first design an
_interface_ ($\mathbf{u}_{v}$ in (5)) that enable the concrete system to track
the abstraction, and then design a Lyapunov-like _simulation function_ to
characterize the formal output tracking errors between the concrete system and
the abstraction.

###  III-A Linear Abstraction for a PWA System Under Disturbances

In this part, we first design an interface for the joint system (5) for the
linear abstraction in the form (2), and then a Lyapunov-like simulation
function is presented to guarantee a formal error bound for the output
tracking errors.

#### Interface

Considering the joint system (5) under the linear abstraction (2), we propose
to design the associated interface as

$\mathbf{u}_{v}(\mathbf{\tilde{x}},\mathbf{x}_{2},\mathbf{\bar{u}}_{2})=\mathbf{R}_{i}\mathbf{\bar{u}}_{2}+(\mathbf{Q}_{i}+\mathbf{R}_{i}\mathbf{L})\mathbf{x}_{2}+\mathbf{K}_{i}\mathbf{\tilde{x}}$
(10)

for $i\in\mathcal{I}$, where $\mathbf{R}_{i}\in\mathbb{R}^{p\times q}$ is an
arbitrary matrix and $\mathbf{K}_{i}\in\mathbb{R}^{p\times n}$ is a tunable
parameter matrix. Then, note that the joint system (5) under the interface
(10) can be written as

$\left\\{\begin{array}[]{ll}\bm{\dot{\mathbf{\bar{\omega}}}}=\mathbf{\bar{A}}_{i}\bm{\bar{\omega}}+\mathbf{\bar{B}}_{1i}\mathbf{x}_{2}+\mathbf{\bar{B}}_{2i}\mathbf{\bar{u}}_{2}+\mathbf{\bar{c}}_{i}&\\\
\mathbf{e}=\mathbf{\bar{C}}_{i}\bm{\bar{\omega}}&\end{array}\right.$ (11)

where the state $\bm{\bar{\omega}}=\begin{bmatrix}\bm{\omega}^{T}&1\\\
\end{bmatrix}^{T}$,
$\mathbf{\bar{A}}_{i}=\begin{bmatrix}\mathbf{A}^{\prime}_{i}&\mathbf{0}\\\
\mathbf{0}&0\end{bmatrix}$,
$\mathbf{A}^{\prime}_{i}=\begin{bmatrix}\mathbf{A}_{i}+\mathbf{B}_{i}\mathbf{K}_{i}&\mathbf{0}\\\
\mathbf{0}&\mathbf{F}+\mathbf{G}\mathbf{L}\end{bmatrix}$,
$\mathbf{\bar{B}}_{1i}=\begin{bmatrix}\mathbf{B}^{\prime}_{1i}\\\
\mathbf{0}\end{bmatrix}$,
$\mathbf{B}^{\prime}_{1i}=\begin{bmatrix}(\mathbf{B}_{i}\mathbf{R}-\mathbf{P}_{i}\mathbf{G})\mathbf{L}\\\
\mathbf{0}\end{bmatrix}$,
$\mathbf{\bar{B}}_{2i}=\begin{bmatrix}\mathbf{B}^{\prime}_{2i}\\\
\mathbf{0}\end{bmatrix}$,
$\mathbf{B}^{\prime}_{2i}=\begin{bmatrix}\mathbf{B}_{i}\mathbf{R}-\mathbf{P}_{i}\mathbf{G}\\\
\mathbf{G}\end{bmatrix}$,
$\mathbf{\bar{c}}_{i}=\begin{bmatrix}\mathbf{c^{\prime}}_{i}^{T}&0\end{bmatrix}^{T}$,
$\mathbf{c}^{\prime}_{i}=\begin{bmatrix}\mathbf{c}_{i}\\\
\mathbf{0}\end{bmatrix}$,
$\mathbf{\bar{C}}_{i}=\begin{bmatrix}\mathbf{C}^{\prime}_{i}&0\end{bmatrix}$,
$\mathbf{C}^{\prime}_{i}=\begin{bmatrix}\mathbf{C}_{i}&\mathbf{0}\end{bmatrix}$,
and the joint partition is defined as (8).

#### Simulation Function

In order to guarantee a formal error bound, we propose a Lyapunov-like
simulation function as

$\mathcal{V}(\bm{\omega}):=\frac{1}{\kappa}\sqrt{\bm{\omega}^{T}\mathbf{M}_{i}\bm{\omega}},\
\mbox{for}\ \bm{\omega}\in\mathbf{\Omega}_{i},\ i\in\mathcal{I}_{0}$ (12)
$\mathcal{V}(\bm{\bar{\omega}}):=\frac{1}{\kappa}\sqrt{\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{i}\bm{\bar{\omega}}},\
\mbox{for}\ \bm{\bar{\omega}}\in\mathbf{\bar{\Omega}}_{i},\
i\in\mathcal{I}_{1}$ (13)

where $\kappa>0$ is some adjustable parameter, each
$\mathbf{\bar{M}}_{i}=\mathbf{\bar{J}}_{i}^{T}\mathbf{T}\mathbf{\bar{J}}_{i}$
is a diagonal block matrix, i.e.,
$\mathbf{\bar{M}}_{i}=\begin{bmatrix}\mathbf{M}_{i}&\mathbf{0}\\\
\mathbf{0}&m_{i}\end{bmatrix}$ with
$\mathbf{M}_{i}\in\mathbb{R}^{(n+m)\times(n+m)}$ being positive definite and
$m_{i}>0$, $\mathbf{\bar{J}}_{i}$ is the continuity matrix of the joint system
(5), and $\mathbf{T}$ is some symmetric free parameter matrix, and
$\mathbf{\bar{M}}_{i}$ should satisfy the following linear matrix
inequalities:

$\mathbf{\bar{M}}_{i}-\mathbf{\bar{C}}_{i}^{T}\mathbf{\bar{C}}_{i}\geq 0,\
\mathbf{\bar{M}}_{i}-\mathbf{\bar{E}}_{i}^{T}\mathbf{U}_{i}\mathbf{\bar{E}}_{i}>0$
(14)
$\mathbf{\bar{A}}_{i}^{T}\mathbf{\bar{M}}_{i}+\mathbf{\bar{M}}_{i}\mathbf{\bar{A}}_{i}+\mathbf{\bar{E}}_{i}^{T}\mathbf{W}_{i}\mathbf{\bar{E}}_{i}+\bm{\bar{\lambda}}\mathbf{\bar{M}}_{i}\leq
0$ (15)

where $\bm{\bar{\lambda}}=\begin{bmatrix}\lambda\mathbf{I}&\mathbf{0}\\\
\mathbf{0}&0\end{bmatrix}$, $\lambda>0$ is some parameter free to choose.
$\mathbf{\bar{E}}_{i}$ is the cell bounding in (8), and $\mathbf{U}_{i}$ and
$\mathbf{W}_{i}$ are symmetric free parameter matrices with nonnegative
entries.

###### Theorem 1

Assume there exists a matrix $\mathbf{P}_{i}\in\mathbb{R}^{n\times m}$ and a
matrix $\mathbf{Q}_{i}\in\mathbb{R}^{p\times m}$ such that the linear matrix
equations in (6) hold for $i\in\mathcal{I}$. Then, for the associated
interface given by (10), there exists a robust approximate simulation relation
of $\Sigma$ by $\Sigma^{\prime}$, of a precision $\delta$ as

$\delta:=\left\\{\begin{array}[]{ll}\ \kappa\mathcal{V}(\bm{\omega}),&\ \
\mathcal{V}(\bm{\omega})\geq b_{0},\ i\in\mathcal{I}_{0}\\\ \ \kappa b_{0},&\
\ \mathcal{V}(\bm{\omega})<b_{0},\ i\in\mathcal{I}_{0}\\\ \
\kappa\mathcal{V}(\bm{\bar{\omega}}),&\ \ \mathcal{V}(\bm{\bar{\omega}})\geq
b_{1},\ i\in\mathcal{I}_{1}\\\ \ \kappa b_{1},&\ \
\mathcal{V}(\bm{\bar{\omega}})<b_{1},\ i\in\mathcal{I}_{1}\end{array}\right.$
(16)

where
$b_{0}=\gamma_{1}(||\mathbf{\bar{u}}_{2}||_{\infty})+\gamma_{2}(||\mathbf{c}^{\prime}_{i}||_{\infty})+\gamma_{3}(||\mathbf{x}_{2}||_{\infty})$,
$b_{1}=\gamma_{1}(||\mathbf{\bar{u}}_{2}||_{\infty})+\gamma_{2}(||\mathbf{\bar{c}}_{i}||_{\infty})+\gamma_{3}(||\mathbf{x}_{2}||_{\infty})+\sqrt{m_{i}}$
with $\gamma_{1}(\cdot)$, $\gamma_{2}(\cdot)$ and $\gamma_{3}(\cdot)$ being
some class-$\mathcal{K}$ functions, and $\mathcal{V}(\bm{\omega})$ and
$\mathcal{V}(\bm{\bar{\omega}})$ are Lyapunov-like simulation function as in
(12) and (13), respectively.

###### Proof:

First, note that the simulation function (13) can bound the output error under
(14) by

$\mathcal{V}(\bm{\bar{\omega}})=\frac{1}{\kappa}\sqrt{\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{i}\bm{\bar{\omega}}}\geq\frac{1}{\kappa}||\mathbf{\bar{C}}_{i}\bm{\bar{\omega}}||=\frac{1}{\kappa}||\mathbf{e}||$
(17)

Similarly, the simulation function (12) can bound the output error by the
reduced condition $\mathbf{M}_{i}-\mathbf{C}_{i}^{\prime
T}\mathbf{C}_{i}^{\prime}\geq 0$ in (14).

For the case $i\in\mathcal{I}_{1}$, take the directional derivative of the
simulation function (13) along (11),

$\displaystyle\mathcal{\dot{V}}(\bm{\bar{\omega}})=\frac{\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{i}(\mathbf{\bar{A}}_{i}\bm{\bar{\omega}}+\mathbf{\bar{B}}_{1i}\mathbf{x}_{2}+\mathbf{\bar{B}}_{2i}\mathbf{\bar{u}}_{2}+\mathbf{\bar{c}}_{i})}{\kappa\sqrt{\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{i}\bm{\bar{\omega}}}}$
$\displaystyle=\frac{\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{i}\mathbf{\bar{A}}_{i}\bm{\bar{\omega}}+\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{i}\mathbf{\bar{B}}_{1i}\mathbf{x}_{2}+\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{i}\mathbf{\bar{B}}_{2i}\mathbf{\bar{u}}_{2}+\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{i}\mathbf{\bar{c}}_{i}}{\kappa\sqrt{\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{i}\bm{\bar{\omega}}}}$

Based on (15),
$\mathbf{\bar{M}}_{i}\mathbf{\bar{A}}_{i}\leq-\frac{1}{2}\mathbf{\bar{E}}_{i}^{T}\mathbf{W}_{i}\mathbf{\bar{E}}_{i}-\frac{1}{2}\bm{\bar{\lambda}}\mathbf{\bar{M}}_{i}$,
and thus,

$\displaystyle\mathcal{\dot{V}}(\bm{\bar{\omega}})\leq$
$\displaystyle\frac{\bm{\bar{\omega}}^{T}\left[-\frac{1}{2}\mathbf{\bar{E}}_{i}^{T}\mathbf{W}_{i}\mathbf{\bar{E}}_{i}-\frac{1}{2}\bm{\bar{\lambda}}\mathbf{\bar{M}}_{i}\right]\bm{\bar{\omega}}}{\kappa\sqrt{\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{i}\bm{\bar{\omega}}}}+\frac{1}{\kappa}||\sqrt{\mathbf{\bar{M}}_{i}}\mathbf{\bar{B}}_{1i}||||\mathbf{x}_{2}||$
$\displaystyle+\frac{1}{\kappa}||\sqrt{\mathbf{\bar{M}}_{i}}\mathbf{\bar{B}}_{2i}||||\mathbf{\bar{u}}_{2}||+\frac{1}{\kappa}||\sqrt{\mathbf{\bar{M}}_{i}}||||\mathbf{\bar{c}}_{i}||$

Then, by the definition of the simulation function (13) and the parameter
matrix $\bm{\bar{\lambda}}$, we have

$\displaystyle\mathcal{\dot{V}}(\bm{\bar{\omega}})\leq$
$\displaystyle-\frac{\lambda}{2\kappa}\mathcal{V}(\bm{\bar{\omega}})+\frac{\lambda}{2\kappa^{2}}\frac{m_{i}}{\mathcal{V}(\bm{\bar{\omega}})}+\frac{1}{\kappa}||\sqrt{\mathbf{\bar{M}}_{i}}\mathbf{\bar{B}}_{1i}||||\mathbf{x}_{2}||$
$\displaystyle+\frac{1}{\kappa}||\sqrt{\mathbf{\bar{M}}_{i}}\mathbf{\bar{B}}_{2i}||||\mathbf{\bar{u}}_{2}||+\frac{1}{\kappa}||\sqrt{\mathbf{\bar{M}}_{i}}||||\mathbf{\bar{c}}_{i}||$

According to (13), we know that
$\mathcal{V}(\bm{\bar{\omega}})\geq\frac{1}{\kappa}\sqrt{m_{i}}$, and
therefore we have

$\displaystyle\mathcal{\dot{V}}(\bm{\bar{\omega}})\leq$
$\displaystyle-\frac{\lambda}{2\kappa}\mathcal{V}(\bm{\bar{\omega}})+\frac{\lambda}{2\kappa}\sqrt{m_{i}}+\frac{1}{\kappa}||\sqrt{\mathbf{\bar{M}}_{i}}\mathbf{\bar{B}}_{1i}||||\mathbf{x}_{2}||$
$\displaystyle+\frac{1}{\kappa}||\sqrt{\mathbf{\bar{M}}_{i}}\mathbf{\bar{B}}_{2i}||||\mathbf{\bar{u}}_{2}||+\frac{1}{\kappa}||\sqrt{\mathbf{\bar{M}}_{i}}||||\mathbf{\bar{c}}_{i}||$

For $\mathcal{\dot{V}}(\bm{\bar{\omega}})<0$, we need
$\mathcal{V}(\bm{\bar{\omega}})>\gamma_{1}(||\mathbf{\bar{u}}_{2}||_{\infty})+\gamma_{2}(||\mathbf{\bar{c}}_{i}||_{\infty})+\gamma_{3}(||\mathbf{x}_{2}||_{\infty})+\sqrt{m_{i}}$,
where
$\gamma_{1}(s)=\frac{2||\sqrt{\mathbf{\bar{M}}_{i}}\mathbf{\bar{B}}_{2i}||}{\lambda}s$,
$\gamma_{2}(s)=\frac{2||\sqrt{\mathbf{\bar{M}}_{i}}||}{\lambda}s$ and
$\gamma_{3}(s)=\frac{2||\sqrt{\mathbf{\bar{M}}_{i}}\mathbf{\bar{B}}_{1i}||}{\lambda}s$
are class-$\mathcal{K}$ functions.

For the case $i\in\mathcal{I}_{0}$, the above results will reduce to

$\displaystyle\mathcal{\dot{V}}(\bm{\omega})\leq$
$\displaystyle-\frac{\lambda}{2\kappa}\mathcal{V}(\bm{\omega})+\frac{1}{\kappa}||\sqrt{\mathbf{M}_{i}}\mathbf{B}^{\prime}_{1i}||||\mathbf{x}_{2}||$
$\displaystyle+\frac{1}{\kappa}||\sqrt{\mathbf{M}_{i}}\mathbf{B}^{\prime}_{2i}||||\mathbf{\bar{u}}_{2}||+\frac{1}{\kappa}||\sqrt{\mathbf{M}_{i}}||||\mathbf{c}^{\prime}_{i}||$

For $\mathcal{\dot{V}}(\bm{\omega})<0$, we have
$\mathcal{V}(\bm{\omega})>\gamma_{1}(||\mathbf{\bar{u}}_{2}||_{\infty})+\gamma_{2}(||\mathbf{c}^{\prime}_{i}||_{\infty})+\gamma_{3}(||\mathbf{x}_{2}||_{\infty})$,
where
$\gamma_{1}(s)=\frac{2||\sqrt{\mathbf{M}_{i}}\mathbf{B}^{\prime}_{2i}||}{\lambda}s$,
$\gamma_{2}(s)=\frac{2||\sqrt{\mathbf{M}_{i}}||}{\lambda}s$ and
$\gamma_{3}(s)=\frac{2||\sqrt{\mathbf{M}_{i}}\mathbf{B}^{\prime}_{1i}||}{\lambda}s$
are class-$\mathcal{K}$ functions.

Therefore, we know that for $i\in\mathcal{I}_{0}$, the set

$\mathcal{R}_{0}=\\{\bm{\omega}\in\bm{\Omega}_{i}|\
\mathcal{V}(\bm{\omega})\leq b_{0}\\}$ (18)

and for $i\in\mathcal{I}_{1}$, the set

$\mathcal{R}_{1}=\\{\bm{\bar{\omega}}\in\bm{\bar{\Omega}}_{i}|\
\mathcal{V}(\bm{\bar{\omega}})\leq b_{1}\\}$ (19)

are both forward invariant [15]. Thus, we know that $\mathcal{R}_{0}$ and
$\mathcal{R}_{1}$ satisfy robust approximate simulation relation with
precision $\kappa b_{0}$ and $\kappa b_{1}$, respectively. Furthermore, from
(17), we also know that
$\frac{1}{\kappa}||\mathbf{y}_{1}-\mathbf{y}_{2}||\leq\mathcal{V}(\bm{\omega})$
for $i\in\mathcal{I}_{0}$ and
$\frac{1}{\kappa}||\mathbf{y}_{1}-\mathbf{y}_{2}||\leq\mathcal{V}(\bm{\bar{\omega}})$
for $i\in\mathcal{I}_{1}$. Thus, we know that $\kappa\mathcal{V}(\bm{\omega})$
and $\kappa\mathcal{V}(\bm{\bar{\omega}})$ can bound the output errors and the
robust approximate simulation relation can be satisfied when
$\mathcal{V}(\bm{\omega})>b_{0}$ and $\mathcal{V}(\bm{\bar{\omega}})>b_{1}$.
Thus, all the cases in (16) now have been proven and this completes the proof.
∎

Note that the error bound in (16) is dependent on
$||\mathbf{x}_{2}||_{\infty}$. However, it can be computed since
$\mathbf{x}_{2}$ is always available.

###  III-B PWA Abstraction for a PWA System Under Disturbances

In this part, we consider the case where the abstraction is in form
$(\ref{eq:PWA_abstraction})$, where we are free to choose the partitions as
well as the system matrices on each partition. Compared to the previous part,
the main difference in this part lies in the computation of the cell boundings
of the joint system since the partitions of the abstract PWA system should be
involved in the computation of the joint $\mathbf{\bar{E}}_{ij}$ as
$\bm{\bar{\omega}}\in\mathbf{\bar{\Omega}}_{ij}$, where

$\begin{split}\mathbf{\bar{\Omega}}_{ij}:&=\Big{\\{}\begin{bmatrix}\mathbf{E}_{i}\\\
\mathbf{E}_{cj}\end{bmatrix}(\mathbf{x}_{1}-\mathbf{P}_{i}\mathbf{x}_{2})+\begin{bmatrix}\mathbf{E}_{i}\mathbf{P}_{i}\\\
\mathbf{E}_{cj}\mathbf{P}_{i}\end{bmatrix}\mathbf{x}_{2}\geq\begin{bmatrix}\mathbf{f}_{i}\\\
\mathbf{f}_{cj}\end{bmatrix}\Big{\\}}\\\
&=\Big{\\{}\begin{bmatrix}\mathbf{E}_{i}&\mathbf{E}_{i}\mathbf{P}_{i}\\\
\mathbf{E}_{cj}&\mathbf{E}_{cj}\mathbf{P}_{i}\end{bmatrix}\bm{\omega}\geq\begin{bmatrix}\mathbf{f}_{i}\\\
\mathbf{f}_{cj}\end{bmatrix}\Big{\\}}\\\
&=\\{\mathbf{\bar{E}}_{ij}\bm{\bar{\omega}}\geq\mathbf{0}\\}\end{split}$ (20)

where $i\in\mathcal{I}$, $j\in\mathcal{I}_{a}$ and the matrices
$\mathbf{E}_{cj}\in\mathbb{R}^{l\times n}$ and
$\mathbf{f}_{cj}\in\mathbb{R}^{l}$ construct the desired partitions of
$\mathbf{x}_{2}$ in the state space of $\mathbf{x}_{1}$ (i.e.,
$\mathbf{x}_{1}\in\mathcal{X}_{1}^{i}:=\\{\mathbf{x}_{1}\in\mathbb{R}^{n}|\
\mathbf{E}_{i}\mathbf{x}_{1}\geq\mathbf{f}_{i}\\}$, $i\in\mathcal{I}$). In
particular, the desired partitions of $\mathbf{x}_{2}$ in the state space of
$\mathbf{x}_{1}$ can be written in closed form as
$\mathbf{E}_{cj}\mathbf{x}_{1}\geq\mathbf{f}_{cj}$, i.e.,
$\mathbf{E}_{cj}\mathbf{\tilde{x}}+\mathbf{E}_{cj}\mathbf{P}_{i}\mathbf{x}_{2}\geq\mathbf{f}_{cj}$,
for $j\in\mathcal{I}_{a}$.

In fact, the partition of $\mathbf{x}_{2}$ can be viewed as
$\mathbf{E}_{aj}\mathbf{x}_{2}\geq\mathbf{f}_{aj}$ as in (3), where
$\mathbf{E}_{aj}=\mathbf{E}_{cj}\mathbf{P}_{i}$ and
$\mathbf{f}_{aj}=\mathbf{f}_{cj}-\mathbf{E}_{cj}\mathbf{\tilde{x}}$. It is not
surprising that the partition of $\mathbf{x}_{2}$ varies with
$\mathbf{\tilde{x}}$ because we know that there must exist some linear
transformation $\mathbf{\Pi}\in\mathbb{R}^{m\times n}$ between two different
spaces, i.e. $\mathbf{x}_{2}=\mathbf{\Pi}\mathbf{x}_{1}$ from Lemma 1 of [16].
However, this relation cannot hold for our case where the disturbances exist
in the state space of $\mathbf{x}_{1}$ or it may hold with very restrictive
conditions (see proposition 4.1 of [17]). The relations
$\mathbf{E}_{aj}=\mathbf{E}_{cj}\mathbf{P}_{i}$ and
$\mathbf{f}_{aj}=\mathbf{f}_{cj}-\mathbf{E}_{cj}\mathbf{\tilde{x}}$ can be
viewed as an online estimate to reshape the partitions of $\mathbf{x}_{2}$ in
our case.

###### Remark 2

It seems unreasonable to express the partitions of $\mathbf{x}_{2}$ in the
state space of $\mathbf{x}_{1}$ as
$\mathbf{E}_{cj}\mathbf{x}_{1}\geq\mathbf{f}_{cj}$ for $j\in\mathcal{I}_{a}$
because the combinations of the successive partitions of $\mathbf{x}_{1}$ may
not always be convex and thus the partitions may not be written in this closed
form. However, we can always convexify the combinations of the successive
partitions of $\mathbf{x}_{1}$ by manually adding more edges to the original
partitions. In this case, we can describe the joint partitions in terms of the
equivalent partitions of $\mathbf{x}_{1}$.

###### Remark 3

In (20), we use the joint partitions of the joint system because the
partitions of $\mathbf{x}_{2}$ are hard to determine. However, we know that
the partitions of $\mathbf{x}_{1}$ can be predefined and thus the desired
partitions of $\mathbf{x}_{2}$ in the state space of $\mathbf{x}_{1}$ can also
be determined. In order to do so, we first use the conditions in (6) to check
the approximate simulation relations between the concrete system (1) and the
abstraction (3). Once the relations can be found, the corresponding successive
partitions of $\mathbf{x}_{1}$ can be combined together. Then, we can analyze
these combinations in two cases. For the case that the combinations of the
successive partitions of $\mathbf{x}_{1}$ are still convex, the combined
partitions of $\mathbf{x}_{1}$ can be used to describe the desired partitions
of $\mathbf{x}_{2}$, i.e.,
$\mathbf{E}_{cj}\mathbf{\tilde{x}}+\mathbf{E}_{cj}\mathbf{P}_{i}\mathbf{x}_{2}\geq\mathbf{f}_{cj}$,
for $j\in\mathcal{I}_{a}$. For the case that the combinations of the
successive partitions of $\mathbf{x}_{1}$ are non-convex, we can first
convexify the combinations of the successive partitions by adding edges and
then follow the same processes as the previous case. Designing systematic
convexification approaches is a subject of future research.

#### Interface

Considering the abstraction being in the form as (3), an associated interface
can be designed as

$\mathbf{u}_{v}(\mathbf{\tilde{x}},\mathbf{x}_{2},\mathbf{\bar{u}}_{2})=\mathbf{R}_{ij}\mathbf{\bar{u}}_{2}+(\mathbf{Q}_{i}+\mathbf{R}_{ij}\mathbf{L}_{j})\mathbf{x}_{2}+\mathbf{K}_{i}\mathbf{\tilde{x}}$
(21)

for the pairs $(i,j)$, $i\in\mathcal{I}$ and $j\in\mathcal{I}_{a}$, where
$\mathbf{R}_{ij}\in\mathbb{R}^{p\times q}$ is an arbitrary matrix and
$\mathbf{K}_{i}\in\mathbb{R}^{p\times n}$ is a tunable parameter matrix. Then,
joint system under the interface (21) can be written in the following form

$\left\\{\begin{array}[]{ll}\bm{\dot{\mathbf{\bar{\omega}}}}=\mathbf{\bar{A}}_{ij}\bm{\bar{\omega}}+\mathbf{\bar{B}}_{1ij}\mathbf{x}_{2}+\mathbf{\bar{B}}_{2ij}\mathbf{\bar{u}}_{2}+\mathbf{\bar{c}}_{i}&\\\
\mathbf{e}=\mathbf{\bar{C}}_{ij}\bm{\bar{\omega}}&\end{array}\right.$ (22)

for $i\in\mathcal{I}$, $j\in\mathcal{I}_{a}$, where the state
$\bm{\bar{\omega}}=\begin{bmatrix}\bm{\omega}^{T}&1\\\ \end{bmatrix}^{T}$,
$\mathbf{\bar{A}}_{ij}=\begin{bmatrix}\mathbf{A}^{\prime}_{ij}&\mathbf{0}\\\
\mathbf{0}&0\end{bmatrix}$,
$\mathbf{A}^{\prime}_{ij}=\begin{bmatrix}\mathbf{A}_{i}+\mathbf{B}_{i}\mathbf{K}_{i}&\mathbf{0}\\\
\mathbf{0}&\mathbf{F}_{j}+\mathbf{G}_{j}\mathbf{L}_{j}\end{bmatrix}$,
$\mathbf{\bar{B}}_{1ij}=\begin{bmatrix}\mathbf{B}^{\prime}_{1ij}\\\
\mathbf{0}\end{bmatrix}$,
$\mathbf{B}^{\prime}_{1ij}=\begin{bmatrix}(\mathbf{B}_{i}\mathbf{R}_{ij}-\mathbf{P}_{i}\mathbf{G}_{j})\mathbf{L}_{j}\\\
\mathbf{0}\end{bmatrix}$,
$\mathbf{\bar{B}}_{2ij}=\begin{bmatrix}\mathbf{B}^{\prime}_{2ij}\\\
\mathbf{0}\end{bmatrix}$,
$\mathbf{B}^{\prime}_{2ij}=\begin{bmatrix}\mathbf{B}_{i}\mathbf{R}_{ij}-\mathbf{P}_{i}\mathbf{G}_{j}\\\
\mathbf{G}_{j}\end{bmatrix}$,
$\mathbf{\bar{c}}_{i}=\begin{bmatrix}\mathbf{c^{\prime}}_{i}^{T}&0\end{bmatrix}^{T}$,
$\mathbf{c}^{\prime}_{i}=\begin{bmatrix}\mathbf{c}_{i}\\\
\mathbf{0}\end{bmatrix}$,
$\mathbf{\bar{C}}_{ij}=\begin{bmatrix}\mathbf{C}^{\prime}_{ij}&0\end{bmatrix}$,
$\mathbf{C}^{\prime}_{ij}=\begin{bmatrix}\mathbf{C}_{ij}&\mathbf{0}\end{bmatrix}$
and the joint partition is defined as (20).

#### Simulation Function

Similar as the linear abstraction case in previous part, to guarantee a formal
error bound, the Lyapunov-like simulation function is presented as

$\mathcal{V}(\bm{\omega}):=\frac{1}{\kappa}\sqrt{\bm{\omega}^{T}\mathbf{M}_{ij}\bm{\omega}},\
\mbox{for}\ \bm{\omega}\in\mathbf{\Omega}_{ij},\
i\in\mathcal{I}_{0},j\in\mathcal{I}_{a0}$ (23)
$\mathcal{V}(\bm{\bar{\omega}}):=\frac{1}{\kappa}\sqrt{\bm{\bar{\omega}}^{T}\mathbf{\bar{M}}_{ij}\bm{\bar{\omega}}},\
\mbox{for}\ \bm{\bar{\omega}}\in\mathbf{\bar{\Omega}}_{ij},\
i\in\mathcal{I}_{1},j\in\mathcal{I}_{a1}$ (24)

where $\kappa>0$ is some adjustable parameter, with each
$\mathbf{\bar{M}}_{ij}=\mathbf{\bar{J}}_{ij}^{T}\mathbf{T}\mathbf{\bar{J}}_{ij}=\begin{bmatrix}\mathbf{M}_{ij}&\mathbf{0}\\\
\mathbf{0}&m_{ij}\end{bmatrix}$, where $\mathbf{M}_{ij}$ is a positive
definite matrix, $m_{ij}>0$ and the matrix $\mathbf{\bar{M}}_{ij}$ should
satisfy the following linear matrix inequalities:

$\mathbf{\bar{M}}_{ij}-\mathbf{\bar{C}}^{T}_{ij}\mathbf{\bar{C}}_{ij}\geq 0,\
\mathbf{\bar{M}}_{ij}-\mathbf{\bar{E}}_{ij}^{T}\mathbf{U}_{ij}\mathbf{\bar{E}}_{ij}>0$
(25)
$\mathbf{\bar{A}}_{ij}^{T}\mathbf{\bar{M}}_{ij}+\mathbf{\bar{M}}_{ij}\mathbf{\bar{A}}_{ij}+\mathbf{\bar{E}}_{ij}^{T}\mathbf{W}_{ij}\mathbf{\bar{E}}_{ij}+\bm{\bar{\lambda}}\mathbf{\bar{M}}_{ij}\leq
0$ (26)

for the pairs $(i,j)$, $i\in\mathcal{I}$ and $j\in\mathcal{I}_{a}$, where
$\bm{\bar{\lambda}}=\begin{bmatrix}\lambda\mathbf{I}&\mathbf{0}\\\
\mathbf{0}&0\end{bmatrix}$, for $\lambda>0$ free to be selected,
$\mathbf{\bar{E}}_{ij}$ is the cell bounding in (20), $\mathbf{U}_{ij}$ and
$\mathbf{W}_{ij}$ are some symmetric free parameter matrices with nonnegative
entries.

With the joint partitions in (20), we now provide a generalized version of
Theorem 1 in the following theorem.

###### Theorem 2

For a given tuple of the concrete system $(\mathbf{A}_{i},\ \mathbf{B}_{i},\
\mathbf{C}_{i})$, $i\in\mathcal{I}$, assume there exists a matrix
$\mathbf{P}_{i}\in\mathbb{R}^{n\times m}$ and a matrix
$\mathbf{Q}_{i}\in\mathbb{R}^{p\times m}$ such that the linear matrix
equations in (9) hold for a pair of $(\mathbf{F}_{j},\ \mathbf{H}_{j})$ of the
abstraction, $j\in\mathcal{I}_{a}$. Then, for the associated interface given
by (21), there exists a robust approximate simulation relation of $\Sigma$ by
$\Sigma^{\prime\prime}$, of the precision $\delta$ as

$\delta:=\left\\{\begin{array}[]{ll}\ \kappa\mathcal{V}(\bm{\omega}),&\ \
\mathcal{V}(\bm{\omega})\geq b_{0},\ i\in\mathcal{I}_{0},\
j\in\mathcal{I}_{a0}\\\ \ \kappa b_{0},&\ \ \mathcal{V}(\bm{\omega})<b_{0},\
i\in\mathcal{I}_{0},\ j\in\mathcal{I}_{a0}\\\ \
\kappa\mathcal{V}(\bm{\bar{\omega}}),&\ \ \mathcal{V}(\bm{\bar{\omega}})\geq
b_{1},\ i\in\mathcal{I}_{1},\ j\in\mathcal{I}_{a1}\\\ \ \kappa b_{1},&\ \
\mathcal{V}(\bm{\bar{\omega}})<b_{1},\ i\in\mathcal{I}_{1},\
j\in\mathcal{I}_{a1}\end{array}\right.$ (27)

where
$b_{0}=\gamma_{1}(||\mathbf{\bar{u}}_{2}||_{\infty})+\gamma_{2}(||\mathbf{c}^{\prime}_{i}||_{\infty})+\gamma_{3}(||\mathbf{x}_{2}||_{\infty})$
and
$b_{1}=\gamma_{1}(||\mathbf{\bar{u}}_{2}||_{\infty})+\gamma_{2}(||\mathbf{\bar{c}}_{i}||_{\infty})+\gamma_{3}(||\mathbf{x}_{2}||_{\infty})+\sqrt{m_{ij}}$,
with $\gamma_{1}(\cdot)$, $\gamma_{2}(\cdot)$ and $\gamma_{3}(\cdot)$ being
some class-$\mathcal{K}$ functions, and $\mathcal{V}(\bm{\omega})$ and
$\mathcal{V}(\bm{\bar{\omega}})$ are Lyapunov-like simulation functions as in
(23) and (24), respectively.

###### Proof:

The proof of Theorem 2 is similar to that of Theorem 1, and thus is omitted
here. ∎

##  IV Simulation Examples

In this section, we use two simulation examples to illustrate the
effectiveness of the proposed robust approximate simulation based control
method developed for PWA systems.

###  IV-A Case 1: PWA by Linear

In this part, we consider an example of a robot tracking a 3-part road
section. The robot must navigate the path with different dynamics in each
part. The output of both concrete and abstract systems represent the position
of the robot in the plane. The control objective is to make the robot track
the planned path in $\mathbf{x}_{2}$, meanwhile the output errors maintain
bounded.

The concrete system was selected as a triple integrator, but its dynamics is
different on each part of the path in terms of the input mapping matrix
$\mathbf{B}_{i}$, i.e.,

$\Sigma:\left\\{\begin{array}[]{ll}\mathbf{\dot{x}}_{1}=\mathbf{A}_{i}\mathbf{x}_{1}+\mathbf{B}_{i}\mathbf{u}_{1}+\mathbf{c}_{i}&\\\
\mathbf{y}_{1}=\mathbf{C}_{i}\mathbf{x}_{1}&\end{array}\right.$ (28)

with the parameters of the system as follows

$\mathbf{A}_{i}=\begin{bmatrix}\mathbf{0}_{2}&\mathbf{I}_{2}&\mathbf{0}_{2}\\\
\mathbf{0}_{2}&\mathbf{0}_{2}&\mathbf{I}_{2}\\\
\mathbf{0}_{2}&\mathbf{0}_{2}&\mathbf{0}_{2}\end{bmatrix},\
\mathbf{B}_{1}=0.5\mathbf{B}_{2}=2\mathbf{B}_{3}=\begin{bmatrix}\mathbf{0}_{2}\\\
\mathbf{0}_{2}\\\ \mathbf{I}_{2}\end{bmatrix},\ $
$\mathbf{C}_{i}=\begin{bmatrix}\mathbf{I}_{2}&\mathbf{0}_{2}&\mathbf{0}_{2}\end{bmatrix},\
\mathbf{c}_{i}=(-0.1+0.05sin(t))\mathbf{1}_{6\times 1}$

for $i=1,2,3$, and the partitions are set based on the position of the robot
as

$\mathbf{E}^{\prime}_{i}=\begin{bmatrix}\mathbf{E}^{\prime}_{i1}&\mathbf{0}_{2}&\mathbf{0}_{2}\\\
\mathbf{0}_{2}&\mathbf{0}_{2}&\mathbf{0}_{2}\\\
\mathbf{0}_{2}&\mathbf{0}_{2}&\mathbf{0}_{2}\end{bmatrix},\
\mathbf{f}^{\prime}_{i}=\mathbf{0},\mbox{ for $i=1,2,3$,}$

where
$\mathbf{E}^{\prime}_{11}=-\mathbf{E}^{\prime}_{31}=\begin{bmatrix}-1&1\\\
-1&-1\end{bmatrix}$ and $\mathbf{E}^{\prime}_{21}=\begin{bmatrix}-1&1\\\
1&1\end{bmatrix}$.

The abstract system was selected as a single integrator, i.e.,

$\Sigma^{\prime}:\left\\{\begin{array}[]{ll}\mathbf{\dot{x}}_{2}=\mathbf{u}_{2}&\\\
\mathbf{y}_{2}=\mathbf{x}_{2}&\end{array}\right.$ (29)

where the input transformation law was designed as
$\mathbf{u}_{2}=-\mathbf{x}_{2}+\mathbf{\bar{u}}_{2}$. The control parameters
for $i=1,2,3$ were selected as

$\mathbf{P}_{i}=\begin{bmatrix}\mathbf{I}_{2}&\mathbf{0}_{2}&\mathbf{0}_{2}\end{bmatrix}^{T},\
\mathbf{Q}_{i}=\mathbf{0}_{2},\
\mathbf{R}_{i}=\mathbf{B}_{i}^{T}[\mathbf{B}_{i}\mathbf{B}_{i}^{T}]^{-1}\mathbf{P}_{i}\mathbf{G},\
$
$\mathbf{K}_{1}=2\mathbf{K}_{2}=0.5\mathbf{K}_{3}=-\begin{bmatrix}52\mathbf{I}_{2}&52.3\mathbf{I}_{2}&13\mathbf{I}_{2}\end{bmatrix}$

The observed simulation results under these system and control parameters are
shown in Figures 2, 3 and 4.

Figure 2: The output of the concrete system $\Sigma$ and the abstraction
$\Sigma^{\prime}$, starting from the green circular region and ending at the
yellow circular target region. The boundaries of the partitions are shown in
green dashed lines. Figure 3: The simulated output error
$||\mathbf{y}_{1}-\mathbf{y}_{2}||$ between the concrete system $\Sigma$ and
the abstraction $\Sigma^{\prime}$ and the value of simulation function using
(12) with $\kappa=8$. Boundary crossing soon after green dashed lines. Figure
4: The computed error bound using $b_{0}$. Boundary crossing soon after green
dashed lines.

In Figure 2, it can be seen that the output of the concrete system $\Sigma$
starts from the green colored initial region and successfully tracks the
output of the abstraction $\Sigma^{\prime}$ and the two trajectories remain
considerably close to each other until the robot reaches the yellow colored
target region. More precisely, the output tracking error is shown in Figure 3,
which is bounded by the simulation function $\mathcal{V}$ (obtained with
$\kappa=8$). Thus, the proposed method is effective. In Figure 3, it can also
be seen that when $\Sigma^{\prime}$ crosses the boundary of the partitions,
the value of the simulation function increases. The reason is that
$\mathbf{x}_{2}$ is not slowly varying and the amplitude of
$||\mathbf{x}_{2}||$ also increases at the boundary, which will cause the
joint state $\bm{\omega}$ to increase. In Figure 4, the computed error bound
is relatively large with respect to the simulation function and the value of
this computed bound also changes around the instants that $\Sigma^{\prime}$
and $\Sigma$ cross a boundary. At the time instant around 7 sec, there is a
chattered switching between two different values of the error bounds, which is
because the concrete system temporarily moves back and forth across a boundary
of two different partitions. From Figure 3 and 4, we can also see that the
simulation function remains bounded within the computed error bound.

###  IV-B Case 2: PWA by PWA

In this part, we consider the case that a simpler PWA system is the
abstraction for the concrete PWA system. Therefore, we consider a more
complicated tracking example with 5-parts road section, while the control
objective is similar to the Case 1 discussed before.

The concrete PWA system was chosen to be in the same form as (28), but its
parameters were selected as

$\mathbf{A}_{i}=\eta_{i1}\begin{bmatrix}\mathbf{I}_{2}&\mathbf{I}_{2}\\\
\mathbf{0}_{2}&\mathbf{I}_{2}\end{bmatrix},\
\mathbf{B}_{i}=\eta_{i2}\begin{bmatrix}\mathbf{0}_{2}\\\
\mathbf{I}_{2}\end{bmatrix},\ $
$\mathbf{C}_{i}=\begin{bmatrix}\mathbf{I}_{2}&\mathbf{0}_{2}\end{bmatrix},\
\mathbf{c}_{i}=(-0.1+0.05sin(t))\mathbf{1}_{4\times 1}$

for $i=1,2,...,5$.

The abstraction was selected as a simpler PWA system,

$\Sigma^{\prime\prime}:\left\\{\begin{array}[]{ll}\mathbf{\dot{x}}_{2}=\mathbf{F}_{j}\mathbf{x}_{2}+\mathbf{G}_{j}\mathbf{u}_{2}&\\\
\mathbf{y}_{2}=\mathbf{H}_{j}\mathbf{x}_{2}&\end{array}\right.$ (30)

where the parameters were chosen as

$\mathbf{F}_{j}=\eta_{i1}\mathbf{I}_{2},\ \mathbf{G}_{j}=\mathbf{I}_{2},\
\mathbf{H}_{j}=\mathbf{I}_{2},\ $

for $j=1,2,3$, with $\eta_{11}=\eta_{21}=1$, $\eta_{31}=2$,
$\eta_{41}=\eta_{51}=0.5$, $\eta_{12}=\eta_{22}=1$, $\eta_{32}=2$,
$\eta_{42}=\eta_{52}=0.5$, and the input transformation law was designed as
$\mathbf{u}_{2}=-k_{i}\mathbf{x}_{2}+\mathbf{\bar{u}}_{2}$, where
$k_{1}=k_{2}=3$, $k_{3}=4$, $k_{4}=k_{5}=2.5$.

The joint partitions were selected as

$\mathbf{\bar{E}}_{ij}=\begin{bmatrix}\mathbf{E}^{\prime}_{ij}&\mathbf{0}_{2}&\mathbf{f}^{\prime}_{ij}\\\
\mathbf{0}_{2}&\mathbf{0}_{2}&\mathbf{0}_{2\times 1}\end{bmatrix},\ $

for $i=1,...,5$ and $j=1,2,3$, where
$\mathbf{E}^{\prime}_{11}=\begin{bmatrix}-1&0\\\ 0&0\end{bmatrix}$,
$\mathbf{E}^{\prime}_{21}=\begin{bmatrix}1&0\\\ -1&0\end{bmatrix}$,
$\mathbf{E}^{\prime}_{32}=\begin{bmatrix}1&0\\\ -1&0\end{bmatrix}$,
$\mathbf{E}^{\prime}_{43}=\begin{bmatrix}1&0\\\ -1&0\end{bmatrix}$,
$\mathbf{E}^{\prime}_{53}=\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$,
$\mathbf{f}^{\prime}_{11}=\begin{bmatrix}1.5\\\ 0\end{bmatrix}$,
$\mathbf{f}^{\prime}_{21}=\begin{bmatrix}-1.5\\\ 0.5\end{bmatrix}$,
$\mathbf{f}^{\prime}_{32}=\begin{bmatrix}-0.5\\\ -0.5\end{bmatrix}$,
$\mathbf{f}^{\prime}_{43}=\begin{bmatrix}0.5\\\ -1.5\end{bmatrix}$ and
$\mathbf{f}^{\prime}_{53}=\begin{bmatrix}1.5\\\ 0\end{bmatrix}$. The output of
both systems represents the position of the robot in the plane. The control
parameters for $i=1,...,5$ and $j=1,2,3$ were selected as

$\mathbf{P}_{i}=\begin{bmatrix}\mathbf{I}_{2}&\mathbf{0}_{2}\end{bmatrix}^{T},\
\mathbf{Q}_{i}=\mathbf{0}_{2},\
\mathbf{R}_{ij}=\mathbf{B}^{T}_{i}[\mathbf{B}_{i}\mathbf{B}_{i}^{T}]^{-1}\mathbf{P}_{i}\mathbf{G}_{j}$
$\mathbf{K}_{1}=\mathbf{K}_{2}=2\mathbf{K}_{3}=0.5\mathbf{K}_{4}=0.5\mathbf{K}_{5}=-\begin{bmatrix}50\mathbf{I}_{2}&10\mathbf{I}_{2}\end{bmatrix}$

Under these system and the control parameters, the observed simulation results
are shown in Figures 5, 6 and 7.

In Figure 5, it can be seen that the output of the concrete system $\Sigma$
can track the output of the abstraction $\Sigma^{\prime\prime}$, starting from
the green colored initial region and ending at the yellow colored target
region, and in-between, the two trajectories remain close. The output tracking
error is shown in Figure 6, which is bounded by the simulation function
$\mathcal{V}$ (obtained with $\kappa=12$), which implies that the proposed
method is effective. In Figure 6, it can also be seen that the value of
simulation function changes when $\Sigma^{\prime\prime}$ crosses the boundary
of a partition and the reason is similar to that of Case 1. According to
Figure 6 and 7, the simulation function is bounded by the computed error bound
and the value of this computed error bound also change around the instants
where $\Sigma^{\prime\prime}$ and $\Sigma$ cross a boundary.

Figure 5: The output of the concrete system $\Sigma$ and the abstraction
$\Sigma^{\prime\prime}$, starting from the green circular region and ending at
the yellow target region. The boundaries of the partitions are shown in green
dashed lines. Figure 6: The simulated output error
$||\mathbf{y}_{1}-\mathbf{y}_{2}||$ between the concrete system $\Sigma$ and
the abstraction $\Sigma^{\prime\prime}$ and the value of simulation function
using (24) with $\kappa=12$. Boundary crossing soon after green dashed lines.
Figure 7: The computed error bound using $b_{1}$. Boundary crossing soon after
green dashed lines.

##  V Conclusion

In this paper, a novel control strategy was presented for the control of PWA
systems based on robust approximate simulation framework. First, we designed
the interface and the simulation function for a configuration where the
concrete system is a known PWA system and the abstraction is a linear system
with the system matrices free to choose. Then, the proposed design procedure
was generalized for a configuration where the abstraction is a PWA system with
the system matrices free to choose under some constraints on its partitions.
Finally, we used two simulation examples to illustrate the effectiveness of
the proposed method. Future work aim to improve the established formal error
bound such that the proposed approximate simulation based control method can
be applied to address more general planning tasks.

## References

  * [1] L. Rodrigues and J. How, “Automated control design for a piecewise-affine approximation of a class of nonlinear systems,” in _Proceedings of the American Control Conference_ , vol. 4, 2001, pp. 3189–3194.
  * [2] W. Han and R. Tedrake, “Feedback design for multi-contact push recovery via LMI approximation of the Piecewise-Affine Quadratic Regulator,” in _Proceedings of the 17th International Conference on Humanoid Robotics_ , 2017, pp. 842–849.
  * [3] F. R. Hogan, E. R. Grau, and A. Rodriguez, “Reactive Planar Manipulation with Convex Hybrid MPC,” in _Proceedings of the International Conference on Robotics and Automation_ , 2018, pp. 247–253.
  * [4] L. Habets, P. Collins, and J. van Schuppen, “Reachability and control synthesis for piecewise-affine hybrid systems on simplices,” _IEEE Transactions on Automatic Control_ , vol. 51, no. 6, pp. 938–948, 2006.
  * [5] E. Camacho, D. Ramirez, D. Limon, D. Muñoz de la Peña, and T. Alamo, “Model predictive control techniques for hybrid systems,” _Annual Reviews in Control_ , vol. 34, no. 1, pp. 21–31, 2010.
  * [6] T. Marcucci and R. Tedrake, “Mixed-integer formulations for optimal control of piecewise-affine systems,” in _Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control_ , 2019, p. 230–239.
  * [7] S. Sadraddini and R. Tedrake, “Sampling-based polytopic trees for approximate optimal control of piecewise affine systems,” _arXiv e-prints_ , p. 1809.09716, 2018. [Online]. Available: https://arxiv.org/abs/1809.09716
  * [8] A. Hassibi and S. Boyd, “Quadratic stabilization and control of piecewise-linear systems,” in _Proceedings of the American Control Conference._ , vol. 6, 1998, pp. 3659–3664.
  * [9] A. Girard and G. J. Pappas, “Hierarchical control using approximate simulation relations,” in _Proceedings of the 45th Conference on Decision and Control_ , 2006, pp. 264–269.
  * [10] A. Girard and G. J. Pappas., “Hierarchical control system design using approximate simulation,” _Automatica_ , vol. 45, no. 2, pp. 566–571, 2009\.
  * [11] V. Kurtz, P. M. Wensing, and H. Lin, “Robust approximate simulation for hierarchical control of linear systems under disturbances,” in _Proceedings of the American Control Conference_ , 2020, pp. 5352–5357.
  * [12] M. Di Benedetto and J. Grizzle, “Asymptotic model matching for nonlinear systems,” _IEEE Transactions on Automatic Control_ , vol. 39, no. 8, pp. 1539–1550, 1994.
  * [13] M. Johansson, _Piecewise linear control systems: a computational approach_. Springer, 2003, vol. 284.
  * [14] V. Kurtz, P. M. Wensing, and H. Lin, “Approximate simulation for template-based whole-body control,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 558–565, 2021.
  * [15] H. K. Khalil, _Nonlinear systems_. Pretince Hall, 2002.
  * [16] S. Sadraddini and R. Tedrake, “Sampling-based polytopic trees for approximate optimal control of piecewise affine systems,” in _Proceedings of the International Conference on Robotics and Automation_ , 2019, pp. 7690–7696.
  * [17] S. Raković, E. Kerrigan, D. Mayne, and K. Kouramas, “Optimized robust control invariance for linear discrete-time systems: Theoretical foundations,” _Automatica_ , vol. 43, no. 5, pp. 831–841, 2007.