# Optimal Control for Linear Networked Control Systems with Information
Transmission Constraints

Antoine Aspeel  ICTEAM at Université catholique de Louvain,
Email: {antoine.aspeel, raphael.jungers<EMAIL_ADDRESS>Kwesi
Rutledge  Department of Electrical Engineering and Computer Science at the
University of Michigan - Ann Arbor,
Email: {krutledg<EMAIL_ADDRESS>Raphaël M. Jungers  ICTEAM at Université
catholique de Louvain,
Email: {antoine.aspeel, raphael.jungers<EMAIL_ADDRESS>Benoit Macq
ICTEAM at Université catholique de Louvain,
Email: {antoine.aspeel, raphael.jungers<EMAIL_ADDRESS>Necmiye
Özay  Department of Electrical Engineering and Computer Science at the
University of Michigan - Ann Arbor,
Email: {krutledg<EMAIL_ADDRESS>
###### Abstract

This paper addresses the problem of robust control of a linear discrete-time
system subject to bounded disturbances and to measurement and control budget
constraints.

Using Q-parameterization and a polytope containment method, we prove that the
co-design of an affine feedback controller, a measurement schedule and a
control schedule can be exactly formulated as a mixed integer linear program
with 2 binary variables per time step. As a consequence, this problem can be
solved efficiently, even when an exhaustive search for measurement and control
times would have been impossible in a reasonable amount of time.

##  I INTRODUCTION

There are a growing number of situations in the world where controllers of
dynamical systems are required to use data acquired over a network to make
their decisions. For example, consider smart electrical power grids, which aim
to use sensing and prediction of power demand to control the power production
of a country. The sensors of such a system would be distributed throughout
homes, businesses, and public spaces. Thus, they will likely lie far away from
the power production facility and direct connection of the sensors to the
decision maker would be impossible. For such dynamical systems, controllers
should take into account the properties of the network (e.g. packet drop
probability, delay) when selecting their actions.

The areas of _control over networks_ and _control of networks_ were developed
to address this design problem [1], where _Control over networks_ focuses on
the design of controllers which are robust to the properties of a network
while _Control of Networks_ focuses on the design of controllers for all of
the nodes on a network such that a collective objective is achieved. In this
work, we are interested in making formal guarantees about reachability of a
target set when performing control and measurement of a single agent over a
network. This objective aligns these results closely with the area of _control
over networks_.

###  I-A Related Work

The obstacles to good performance while implementing a controller over a
network are many. Packet losses are one pervasive problem and can be modelled
by a probability of control or measurement packet loss during transmission
[2]. Some results in the literature analyze the expected performance of
controllers when the network is analyzed in this probabilistic manner. There
may also exist delays in the transmission of information [3, Remark II.4]
which can lead the same controller to be stable with one communication
protocol/network architecture but be unstable within another. Limited
bandwidth is also a problem, as a high frequency of controller and
communication updates across the network may overburden it. So, in works like
[4, 5], adaptive communication protocols are developed to minimize the amount
of information that must be sent across the network.

In the literature, two different types of controllers are used to minimize the
number of actions (e.g. control or communication actions) that are transmitted
by a controller during operation: event-triggered and self-triggered
controllers [6]. In event-triggered controllers, the controller decides to
take an action only when the measurement of the state satisfies a certain
condition (e.g. state leaves a set). Note that in most event-triggered
controllers, the state of the system or a measurement of it is available to
the controller at all times [7], an assumption that we do not allow in this
work.

In self-triggered controllers, the controller determines when it will take its
next action while computing the current action. These controllers rely on the
fact that the self-triggering control action always occurred simultaneously
with a self-triggered measurement, which is a convenient but potentially
restrictive assumption. This assumption is relaxed in the formulation of this
work.

To our knowledge, the method defined in this work is the first derivation of
robust output feedback control design with measurement and control budget
constraints. Other areas, such as parsimonious control [8], also have results
defining how to minimize the number of control actions that are taken in a
distributed system setting.

In the context of Q-parameterization, the quadratic invariance property has
been studied. It has been shown that it is a necessary [9] and sufficient [10]
condition for convexity. In this paper, we have similar results for linearity.
Then, the combinatorial structure allowing to co-design the controller, the
measurement and control times will lead to a _Mixed Integer Linear Program_
(MILP) and not only to a mixed integer convex program. Consequently, branch an
bounds methods can be used to find an optimal solution efficiently.

Note that some alternatives to Q-parameterization exist, e.g., disturbance
rejection control [11], or system level synthesis [12].

###  I-B Contribution

In this paper, we develop a controller which satisfies constraints on the
amount of bandwidth used on the network by jointly optimizing (i) a
measurement schedule, (ii) a control schedule, and (iii) the controller’s
gains, while guaranteeing that the output variable remains in a safety set.
The controller contains memory and a zero-order hold structure which is
partially illustrated in Fig. 1. When the uncertainty sets in this problem are
defined as polytopes, this problem can be formulated as a robust optimization
using the _polytope containment methods_ discussed in [13, 14]. The output
feedback controller, which would normally lead to complex nonconvex
constraints can be parameterized linearly in terms of the optimization
variables, using the methods of _Q-Parameterization_ [15, 16]. Then, the
unique binary choices associated with the schedules introduce binary
variables, making the optimization problem a MILP which is tractable to solve
on practical problems.

###  I-C Paper outline

We begin this paper by discussing the state of the art and the notation used
throughout the paper. In Section II, the main problem we are interested in is
defined, and several related problems are presented. In Section III, we
propose a solution to the problem using Q-Parameterization and Mixed-Integer
Linear Programming. Section IV demonstrates our method on two examples and
Section V concludes and proposes future works. The proofs of the lemmas are in
Appendix A.

###  I-D Notation and Terminology

The set of real numbers is denoted by $\mathbb{R}$ and the set $\\{0,1\\}$ is
denoted by $\mathbb{B}$. The set of $m\times n$ matrices with non-negative
real entries is $\mathbb{R}^{m\times n}_{+}$. For a matrix $A$, $A^{\top}$ is
the transpose of $A$. The symbol $I_{n}$ represents the identity matrix of
size $n$, $0_{m\times n}$ is the zero $m\times n$ matrix, $\mathbb{1}_{n}$ is
the $n$ dimensional vector of ones. For the sake of brevity, dimensions are
sometimes omitted when they can be inferred from compatibility. The Kronecker
product is $\otimes$. Inequalities between vectors are considered element-
wise. For $A\in\mathbb{R}^{m\times n}$ and
$\mathcal{I}\subset\\{1,\dots,m\\}$, we write $A_{\mathcal{I},:}$ the
$|\mathcal{I}|\times m$ matrix whose rows correspond to the rows of $A$ with
indices in $\mathcal{I}$. The notation $A_{:,\mathcal{J}}$ is used similarly
for the columns. For integers $i<j$, we write $i:j=\\{i,i+1,\dots,j\\}$.

Calligraphic letters represent polytopes (except $\mathcal{I}$ and
$\mathcal{J}$ which represent set of indices). For two polytopes $\mathcal{A}$
and $\mathcal{B}$, $\mathcal{A}\times\mathcal{B}$ is their Cartesian product;
for a positive integer $n$, $\mathcal{A}^{n}$ is the $n$-th Cartesian power of
$\mathcal{A}$; and $\partial\mathcal{A}$ denotes the boundary of
$\mathcal{A}$.

ControllerNetworkPlantZOH$u_{t}$${\scriptstyle\bullet}$${\scriptstyle\bullet}$$\sigma^{m}_{t}$$y_{t}$${\scriptstyle\bullet}$${\scriptstyle\bullet}$$\sigma^{c}_{t}$$w_{t},v_{t}$
Figure 1: Block diagram representing the interaction between the plant (1) and
the controller (2). ZOH means zero-order hold.

##  II PROBLEM STATEMENT

We consider the following discrete-time dynamical system

$\displaystyle x_{t+1}$
$\displaystyle=Ax_{t}+Bu_{t}+w_{t},\;\;w_{t}\in\mathcal{W},$ (1a)
$\displaystyle y_{t}$
$\displaystyle=\begin{cases}Cx_{t}+v_{t},&\sigma^{m}_{t}=1\\\
\emptyset,&\sigma^{m}_{t}=0\end{cases},\;\;v_{t}\in\mathcal{V},$ (1b)
$\displaystyle z_{t}$ $\displaystyle=Dx_{t}+d.$ (1c)

Quantities $w_{t}$, $v_{t}$, $x_{0}$ are unknown but are contained in known
sets $\mathcal{W}$, $\mathcal{V}$, $\mathcal{X}_{0}$, respectively. The
measurement scheduling signal $\sigma^{m}_{t}\in\mathbb{B}$ determines if a
measurement is acquired at time $t$.

We want to design the input signal $u_{t}$ from the previous measurements
$y_{t}$. We restrict to linear controllers of the form

$u_{t}=\begin{cases}f_{t}+\sum_{\tau\leq t\text{\ s.t.\
}\sigma^{m}_{\tau}=1}F_{(t,\tau)}y_{\tau},&\sigma^{c}_{t}=1,\\\
u_{t-1},&\sigma^{c}_{t}=0,\end{cases}$ (2)

with $u_{-1}=0$. Column vectors $x_{t}$, $y_{t}$, $z_{t}$ and $u_{t}$ are
respectively in $\mathbb{R}^{n_{x}}$, $\mathbb{R}^{n_{y}}$,
$\mathbb{R}^{n_{z}}$ and $\mathbb{R}^{n_{u}}$. Other dimensions can be deduced
from compatibility. The control scheduling signal
$\sigma^{c}_{t}\in\mathbb{B}$ determines when a new control input is sent to
the plant.

###### Remark 1

When $\sigma^{c}_{t}=0$, instead of zero-order hold, we could set the input to
zero, i.e., $u_{t}=0$. Both options are presented in [2], while [3] focuses on
zero-order hold.

We are interested in controlling the output $z_{t}$ during a finite horizon of
length $T$. Sensors and actuators are supposed to be constrained in their
number of uses. This kind of situation occurs for example to save energy for
sensors and actuators. Formally, we have a maximum number of measurements
$N_{m}\geq 0$, and a maximum number of new control inputs $N_{c}\geq 0$. It is

$\sum_{t=0}^{T-1}\sigma^{m}_{t}\leq N_{m}\text{\; and \;
}\sum_{t=0}^{T-1}\sigma^{c}_{t}\leq N_{c}.$ (3)

###### Remark 2

These constraints can be replaced by any linear constraints, i.e.,
$\sum_{t=0}^{T-1}\left(c_{it}^{m}\sigma_{t}^{m}+c_{it}^{c}\sigma_{t}^{c}\right)\leq
b_{i}$, for $i=1,\dots,I$ where $c_{it}^{m}$, $c_{it}^{c}$ and $b_{i}$ are
known constants. For example, instead of considering two separated budgets,
one for the measurements and the other for the controls, we could consider a
common budget
$\sum_{t=0}^{T-1}\left(c^{m}\sigma^{m}_{t}+c^{c}\sigma^{c}_{t}\right)\leq N$.
Budgets over a sliding window of length $\bar{t}\geq 1$ can also be
considered, i.e., $\sum_{\tau=t-\bar{t}}^{t-1}\sigma_{\tau}\leq N$, for
$t=\bar{t},\dots,T$.

A safety set $\mathcal{Z}$ is given for which our objective is to ensure
$z_{t}\in\mathcal{Z}$. In addition, we want the control input to stay inside a
known set $\mathcal{U}$, i.e., $u_{t}\in\mathcal{U}$. Furthermore, we include
the following assumption.

###### Assumption 1

The sets $\mathcal{X}_{0}$, $\mathcal{W}$, $\mathcal{V}$, $\mathcal{U}$ and
$\mathcal{Z}$ are (not necessarily bounded) convex polyhedra.

It is assumed to have these polyhedra in H-representation. For
$\mathcal{A}\in\\{\mathcal{X}_{0},\mathcal{W},\mathcal{V},\mathcal{U},\mathcal{Z}\\}$,
we write $\mathcal{A}=\\{x|H_{\mathcal{A}}x\leq h_{\mathcal{A}}\\}$ and
$n_{\mathcal{A}}$ the number of rows in the matrix $H_{\mathcal{A}}$ and in
the column vector $h_{\mathcal{A}}$.

The problem we are interested in is to find measurement times, control times,
control gains and control offsets, that keep the output variable $z_{t}$ in
the safety set $\mathcal{Z}$ during the complete horizon, i.e., for
$t=0,\dots,T$.

######  Problem 1 (Safety)

$\text{Find}\ \\{\sigma^{m}_{t}\\}_{t=0}^{T-1},\
\\{\sigma^{c}_{t}\\}_{t=0}^{T-1},\ \\{f_{t}\\}_{t=0}^{T-1},\
\\{F_{(t,\tau)}\\}_{t=0,\ \tau=0}^{T-1,\ t},$

such that

  * •

The dynamics (1) hold,

  * •

The controller (2) is used,

  * •

$\sigma^{m}_{t},\sigma^{c}_{t}\in\mathbb{B}$ for $t=0,\dots,T-1$,

  * •

Budget constraints (3) hold,

  * •

For all $w_{t}\in\mathcal{W}$, $v_{t}\in\mathcal{V}$, for $t=0,\dots,T-1$, and
for all $x_{0}\in\mathcal{X}_{0}$, it holds that $z_{t}\in\mathcal{Z}$ for
$t=0,\dots,T$, and $u_{t}\in\mathcal{U}$ for $t=0,\dots,T-1$.

###### Remark 3

It is possible to add an objective function for minimizing a cost related to
measurements and controls, e.g.,
$\sum_{t=0}^{T-1}\left(c_{m}\sigma^{m}_{t}+c_{c}\sigma^{c}_{t}\right)$, where
$c_{m}$ and $c_{c}$ are given non negative constants.

In addition, one could add the constraint $x_{T}\in\mathcal{X}_{0}$. Then, a
solution to Problem 1 can be applied periodically to keep
$z_{t}\in\mathcal{Z}$ and $u_{t}\in\mathcal{U}$ for all $t\geq 0$.

###  II-A Related problem - Safety as long as possible

In this problem, one wants to keep the output safe, i.e.,
$z_{t}\in\mathcal{Z}$ as long as possible. We assume to have an a priori upper
bound $\bar{T}$ on the largest such time. This can be formalized as follows.

######  Problem 2 (Safety as long as possible)

$\underset{\small{\begin{array}[]{c}T\in\\{0,\dots,\bar{T}\\}\\\
\\{\sigma^{m}_{t}\\}_{t=0}^{\bar{T}-1},\\{\sigma^{c}_{t}\\}_{t=0}^{\bar{T}-1}\\\
\\{f_{t}\\}_{t=0}^{\bar{T}-1},\\{F_{(t,\tau)}\\}_{t=0,\ \tau=0}^{\bar{T}-1,\
t}\end{array}}}{\max}T,$

such that

  * •

Equations (1) and (2) hold for $t=0,\dots,\bar{T}-1$,

  * •

$\sigma^{m}_{t},\sigma^{c}_{t}\in\mathbb{B}$ for $t=0,\dots,\bar{T}-1$,

  * •

Budget constraints (3) hold with $\bar{T}$ instead of $T$,

  * •

For all $w_{t}\in\mathcal{W}$, $v_{t}\in\mathcal{V}$, for $t=0,\dots,T-1$, and
for all $x_{0}\in\mathcal{X}_{0}$, it holds that $z_{t}\in\mathcal{Z}$ for
$t=0,\dots,T$, and $u_{t}\in\mathcal{U}$ for $t=0,\dots,T-1$.

Problem 2 consists of finding the largest $T$ such that Problem 1 is feasible.
Note that if Problem 1 is feasible for some $T^{\prime}$, then it is also
feasible for all $T\leq T^{\prime}$. Then, a binary search algorithm can be
used to find the optimal $T$ by solving $O\left(\log_{2}(\bar{T})\right)$
instances of Problem 1. In Subsection IV-B, we solve Problem 2 on an example.

##  III METHODS

In this section, we show that a feasible solution of Problem 1 can be obtained
by solving a MILP with $2T$ binary variables. In Subsection III-A, we show
that missing measurements and controls can be modeled as linear indicator
constraints on the gains $F_{(t,\tau)}$ and $f_{t}$. Subsection III-B recalls
the Q-parameterization approach which leads to express the trajectories of
$z_{t}$ and $u_{t}$ as linear transformation of the uncertainties $w_{t}$,
$v_{t}$ and $x_{0}$. It leads to the introduction of new design variables $Q$
and $r$. In Subsection III-C we use polytope containment techniques to handle
the robustness constraints $z_{t}\in\mathcal{Z}$ and $u_{t}\in\mathcal{U}$ for
all uncertainties $w_{t}$, $v_{t}$ and $x_{0}$. This leads to linear
constraints in terms of the new decision variables $Q$ and $r$. Then, it is
shown in Subsection III-D that the indicator constraints on $F_{(t,\tau)}$ and
$f_{t}$ for missing measurements and controls can be expressed as linear
indicator constraints in terms of the new design variables $Q$ and $r$.
Finally, Subsection III-E combines the previous results to prove that Problem
1 is equivalent to a MILP.

###  III-A Missing measurements and controls

There are different ways to deal with missing measurements. A common way is to
set the measurement matrix $C$ to zero when no measurements are taken, i.e.,
when $\sigma^{m}_{t}=0$, and treat the system as time-varying [17]. In our
case, the measurement times are decision variables and such an approach would
be equivalent to considering part of the dynamics of the system as a variable
of the problem. This would lead to non-linearities.

For this reason, we deal with missing measurements in a different way. We
consider that a measurement is available at each time step but that the
measurements that should be missing are forbidden to the controller. For this
reason, the gains associated with prohibited measurements are set to zero,
i.e., $\sigma^{m}_{\tau}=0$ implies $F_{(t,\tau)}=0$ for all $t$. Intuitively,
we do not consider missing measurements, but prohibited measurements instead.
Consequently, the choice of measurement times does not translate as a choice
on the dynamics of the system, but as a constraint on the controller’s gains.
This idea is taken up in the following lemma.

######  Lemma 1 (Forbidden measurements)

For given $x_{0}$, $w_{t}$, $v_{t}$, $\sigma^{m}_{t}$ and $\sigma^{c}_{t}$ for
$t=0,\dots,T-1$, the sequences $\\{z_{t}\\}_{t=0}^{T}$ and
$\\{u_{t}\\}_{t=0}^{T-1}$ generated by (1) and (2) are the same as the ones
generated by

$\displaystyle x_{t+1}$ $\displaystyle=Ax_{t}+Bu_{t}+w_{t},$ (4a)
$\displaystyle y_{t}$ $\displaystyle=Cx_{t}+v_{t},$ (4b) $\displaystyle z_{t}$
$\displaystyle=Dx_{t}+d$ (4c) $\displaystyle u_{t}$
$\displaystyle=f_{t}+\sum_{\tau\leq t}F_{(t,\tau)}y_{\tau},$ (4d)

when for all $\tau=0,\dots,T-1$,

$\sigma^{m}_{\tau}=0\Rightarrow\left(F_{(t,\tau)}=0,\text{\; for\ all\;
}t=\tau,\dots T-1\right),$ (5)

and for all $t=0,\dots,T-1$,

$\sigma^{c}_{t}=0\Rightarrow\begin{cases}f_{t}=f_{t-1},\\\
F_{(t,\tau)}=F_{(t-1,\tau)},\ \text{for}\ \tau=0,\dots,t\end{cases}$ (6)

with $f_{-1}=0$ and $F_{(-1,\tau)}=F_{(t,t-1)}=0$.

###  III-B Trajectories and Q-parameterization

This section follows the presentation of the Q-parameterization from [18].
First, let’s define the dynamical variables of (4) in terms of trajectories:

$\begin{array}[]{ll}x=\begin{bmatrix}x_{0}^{\top}&x_{1}^{\top}&\cdots&x_{T}^{\top}\end{bmatrix}^{\top},&z=\begin{bmatrix}z_{0}^{\top}&z_{1}^{\top}&\cdots&z_{T}^{\top}\end{bmatrix}^{\top},\\\
u=\begin{bmatrix}u_{0}^{\top}&u_{1}^{\top}&\cdots&u_{T-1}^{\top}\end{bmatrix}^{\top},&w=\begin{bmatrix}w_{0}^{\top}&w_{1}^{\top}&\cdots&w_{T-1}^{\top}\end{bmatrix}^{\top},\\\
v=\begin{bmatrix}v_{0}^{\top}&v_{1}^{\top}&\cdots&v_{T-1}^{\top}\end{bmatrix}^{\top},&f=\begin{bmatrix}f_{0}^{\top}&f_{1}^{\top}&\cdots&f_{T-1}^{\top}\\\
\end{bmatrix}^{\top},\\\
\mathbf{\sigma}^{m}=\begin{bmatrix}\mathbf{\sigma}^{m}_{0}&\mathbf{\sigma}^{m}_{1}&\cdots&\mathbf{\sigma}^{m}_{T-1}\end{bmatrix}^{\top},&\mathbf{\sigma}^{c}=\begin{bmatrix}\mathbf{\sigma}^{c}_{0}&\mathbf{\sigma}^{c}_{1}&\cdots&\mathbf{\sigma}^{c}_{T-1}\\\
\end{bmatrix}^{\top},\end{array}$ (7)
$F=\begin{bmatrix}F_{(0,0)}&0&0&\cdots&0\\\ F_{(1,0)}&F_{(1,1)}&0&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
F_{(T-1,0)}&F_{(T-1,1)}&F_{(T-1,2)}&\cdots&F_{(T-1,T-1)}\\\ \end{bmatrix}.$
(8)

Note that $F$ and $f$ characterize the control input and are decision
variables. The state trajectory $x$ (along with several other trajectories) is
a nonlinear function of the decision variables $F$ and $f$:

$\begin{array}[]{l}x=(H+SF(I-\bar{C}SF)^{-1}\bar{C}H)w+SF(I-\bar{C}SF)^{-1}v+\\\
\quad\quad(I+SF(I-\bar{C}SF)^{-1}\bar{C})Jx_{0}+S(I+Q\bar{C}S)f,\end{array}$
(9)

where

$J=\begin{bmatrix}I\\\ A\\\ A^{2}\\\ \vdots\\\
A^{T}\end{bmatrix},\;H=\begin{bmatrix}0_{n_{x}\times n_{x}}&0&0&\cdots&0\\\
I&0&0&\cdots&0\\\ A&I&0&\cdots&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
A^{T-1}&A^{T-2}&A^{T-3}&\cdots&I\end{bmatrix},$
$\bar{C}=\begin{bmatrix}I_{T}\otimes C&0_{Tn_{y}\times n_{x}}\end{bmatrix},$
$S=\begin{bmatrix}0_{n_{x}\times n_{u}}&0&0&\cdots&0\\\ B&0&0&\cdots&0\\\
AB&B&0&\cdots&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
A^{T-1}B&A^{T-2}B&A^{T-3}B&\cdots&B\end{bmatrix}.$

Thus, in view of (9), efficiently searching the set of feasible gains ($F$ and
$f$) for Problem 1 would be a search over a nonconvex set. However, from [18,
Theorem 2, Equation (17)], the following also holds

$x=(H+SQ\bar{C}H)w+SQv+(I+SQ\bar{C})Jx_{0}+Sr,$ (10)
$u=Q\bar{C}Hw+Qv+Q\bar{C}Jx_{0}+r,$ (11)

where the following Q-parameterization mapping is used

$\displaystyle Q$ $\displaystyle=F(I-\bar{C}SF)^{-1},$ (12) $\displaystyle r$
$\displaystyle=(I+Q\bar{C}S)f,$ (13)

and gives a $n_{x}\times n_{y}$ block lower triangular matrix $Q$. Conversely,
if $Q$ is $n_{x}\times n_{y}$ block lower triangular, then this mapping is
invertible and the inverse mapping is

$\displaystyle F$ $\displaystyle=(I+Q\bar{C}S)^{-1}Q,$ (14) $\displaystyle f$
$\displaystyle=(I+Q\bar{C}S)^{-1}r.$ (15)

This mapping allows to express our problem in terms of $Q$ and $r$ instead of
$F$ and $f$.

In addition, let’s write

$\bar{D}=I_{T+1}\otimes D,\;\bar{d}=\mathbb{1}_{T+1}\otimes d.$

Then, using $z=\bar{D}x+\bar{d}$, (10) and (11), one can write

$\begin{bmatrix}z\\\ u\end{bmatrix}=\begin{bmatrix}P_{zw}&P_{zv}&P_{zx_{0}}\\\
P_{uw}&P_{uv}&P_{ux_{0}}\end{bmatrix}\begin{bmatrix}w\\\ v\\\
x_{0}\end{bmatrix}+\begin{bmatrix}\tilde{z}\\\ \tilde{u}\end{bmatrix},$ (16)

where

$\displaystyle\begin{array}[]{rlrlrl}P_{zw}=&\bar{D}(H+SQ\bar{C}H),&P_{zv}=&\bar{D}SQ,&P_{zx_{0}}=&\bar{D}(I+SQ\bar{C})J,\\\
P_{uw}=&Q\bar{C}H,&P_{uv}=&Q,&P_{ux_{0}}=&Q\bar{C}J,\end{array}$ (19)
$\displaystyle\begin{array}[]{lcr}\tilde{z}=\bar{D}Sr+\bar{d}&\text{and}&\tilde{u}=r.\end{array}$
(21)

Note that these quantities depend linearly on the new decision variables $Q$
and $r$, which is at the heart of Q-parameterization.

###  III-C Robustness constraints by polytope containment

Problem 1 contains the robust constraints $z_{t}\in\mathcal{Z}$ and
$u_{t}\in\mathcal{U}$ for all $w_{t}$, $v_{t}$ and $x_{0}$. To deal with such
constraints, we use polytope containment techniques. To this end, we will need
the following extension of the Farkas’ lemma.

######  Lemma 2 (H-Polytope in H-Polytope, [19])

Let $\mathcal{A}=\\{x\in\mathbb{R}^{n}\;|\;H_{\mathcal{A}}x\leq
h_{\mathcal{A}}\\}$,
$\mathcal{B}=\\{x\in\mathbb{R}^{n}\;|\;H_{\mathcal{B}}x\leq
h_{\mathcal{B}}\\}\subset\mathbb{R}^{n}$,
$H_{\mathcal{A}}\in\mathbb{R}^{n_{\mathcal{A}}\times n}$,
$H_{\mathcal{B}}\in\mathbb{R}^{n_{\mathcal{B}}\times n}$. We have
$\mathcal{A}\subseteq\mathcal{B}$ if and only if

$\exists\Lambda\in\mathbb{R}^{n_{\mathcal{B}}\times n_{\mathcal{A}}}_{+}\text{
such that }\Lambda H_{\mathcal{A}}=H_{\mathcal{B}},\;\Lambda
h_{\mathcal{A}}\leq h_{\mathcal{B}}.$

We use Lemma 2 to prove the following lemma which allows to handle the
robustness constraint $z_{t}\in\mathcal{Z}$.

######  Lemma 3 (Safety constraint)

Let the sequence $\\{z_{t}\\}_{t=0}^{T}$ be generated by (4). The inclusion
$z_{t}\in\mathcal{Z}$ holds for all $t=0,\dots,T$, for all
$w_{t}\in\mathcal{W}$, for all $v_{t}\in\mathcal{V}$ and for all
$x_{0}\in\mathcal{X}_{0}$ if and only if there exists
$\Lambda\in\mathbb{R}^{(T+1)n_{\mathcal{Z}}\times(T(n_{\mathcal{W}}+n_{\mathcal{V}})+n_{\mathcal{X}_{0}})}_{+}$
such that

$\Lambda\begin{bmatrix}I_{T}\otimes H_{\mathcal{W}}&0&0\\\ 0&I_{T}\otimes
H_{\mathcal{V}}&0\\\ 0&0&H_{\mathcal{X}_{0}}\end{bmatrix}=\left(I_{T+1}\otimes
H_{\mathcal{Z}}\right)\begin{bmatrix}P_{zw}&P_{zv}&P_{zx_{0}}\end{bmatrix},$
(22)

and

$\Lambda\begin{bmatrix}\mathbb{1}_{T}\otimes h_{\mathcal{W}}\\\
\mathbb{1}_{T}\otimes h_{\mathcal{V}}\\\
h_{\mathcal{X}_{0}}\end{bmatrix}\leq\mathbb{1}_{T+1}\otimes
h_{\mathcal{Z}}-\left(I_{T+1}\otimes H_{\mathcal{Z}}\right)\tilde{z},$ (23)

where $P_{zw}$, $P_{zv}$, $P_{zx_{0}}$ are defined in (19) and $\tilde{z}$ is
defined in (21).

We can state a similar result for the bounded input constraint
$u_{t}\in\mathcal{U}$.

######  Lemma 4 (Bounded inputs)

Let the sequence $\\{u_{t}\\}_{t=0}^{T-1}$ be generated by (4). The inclusion
$u_{t}\in\mathcal{U}$ holds for all $t=0,\dots,T-1$, for all
$v_{t}\in\mathcal{V}$, for all $w_{t}\in\mathcal{W}$ and for all
$x_{0}\in\mathcal{X}_{0}$ if and only if there exists
$\Gamma\in\mathbb{R}^{Tn_{\mathcal{U}}\times(T(n_{\mathcal{W}}+n_{\mathcal{V}})+n_{\mathcal{X}_{0}})}_{+}$
such that

$\Gamma\begin{bmatrix}I_{T}\otimes H_{\mathcal{W}}&0&0\\\ 0&I_{T}\otimes
H_{\mathcal{V}}&0\\\ 0&0&H_{\mathcal{X}_{0}}\end{bmatrix}=\left(I_{T}\otimes
H_{\mathcal{U}}\right)\begin{bmatrix}P_{uw}&P_{uv}&P_{ux_{0}}\end{bmatrix},$
(24)

and

$\Gamma\begin{bmatrix}\mathbb{1}_{T}\otimes h_{\mathcal{W}}\\\
\mathbb{1}_{T}\otimes h_{\mathcal{V}}\\\
h_{\mathcal{X}_{0}}\end{bmatrix}\leq\mathbb{1}_{T}\otimes
h_{\mathcal{U}}-\left(I_{T}\otimes H_{\mathcal{U}}\right)\tilde{u},$ (25)

where $P_{uw}$, $P_{uv}$, $P_{ux_{0}}$ are defined in (19) and $\tilde{u}$ is
defined in (21).

###### Remark 4

Note that Lemmas 3 and 4 give linear constraints on $P_{zw}$, $P_{zv}$,
$P_{zx_{0}}$, $P_{uw}$, $P_{uv}$ and $P_{ux_{0}}$ which are linear functions
of $Q$ and $r$. Consequently, these constraints are linear in the decision
variables $Q$ and $r$. Thus, a feasibility problem which once contained non-
convex constraints on the decision variables $F$ and $f$ can be transformed
into an equivalent feasibility problem with convex constraints on the decision
variables $Q$ and $r$.

###  III-D Missing measurements and controls revisited

The two following Lemmas state how the forbidden measurements constraint (5)
and the missing control constraint (6) can be expressed linearly in terms of
the new design variables $Q$ and $r$.

######  Lemma 5 (Missing measurements)

Let a binary measurement signal $\sigma^{m}\in\mathbb{B}^{T}$ and let
$\\{F_{(t,\tau)}\\}_{t=0,\ \tau=0}^{T-1,\ t}$ be some control gains. Then, (5)
holds for $\tau=0,\dots,T-1$, if and only if

$\sigma^{m}_{\tau}=0\Rightarrow Q_{:,\mathcal{J}_{\tau}}=0,\text{\ for\
}\tau=0,\dots,T-1,$ (26)

where $Q$ is defined by (8) and (12) and where $\mathcal{J}_{\tau}=1+\tau
n_{y}:(\tau+1)n_{y}$.

######  Lemma 6 (Missing controls)

Let a binary control signal $\sigma^{c}\in\mathbb{B}^{T}$ and let
$\\{f_{t}\\}_{t=0}^{T-1}$ and $\\{F_{(t,\tau)}\\}_{t=0,\ \tau=0}^{T-1,\ t}$ be
some control offsets and control gains. Then, (6) holds for all
$t=0,\dots,T-1$ if and only if the following indicator constraints hold,

$\text{for\; }t=0,\dots,T-1,\
\sigma^{c}_{t}=0\Rightarrow\begin{cases}Q_{\mathcal{I}_{t},:}=Q_{\mathcal{I}_{t-1},:},\\\
r_{\mathcal{I}_{t}}=r_{\mathcal{I}_{t-1}},\end{cases}$ (27)

where $\mathcal{I}_{t}=1+tn_{u}:(t+1)n_{u}$, $Q_{\mathcal{I}_{-1},:}=0$ and
$r_{\mathcal{I}_{-1}}=0$.

Similar results can be obtained with quadratic invariance. Remark that Lemmas
5 and 6 prove that the constraints are linear (and not just convex) in $Q$ and
$r$.

###  III-E Main result

Before stating our main result, recall that indicator constraints such that
(26) and (27) can be handled as mixed integer linear constraints thanks to the
Big-M formulation. The Big-M formulation uses the fact that for
$\sigma\in\\{0,1\\}$, the indicator constraint $\sigma=0\Rightarrow f(x)=0$ is
equivalent to $-\sigma\bar{M}\leq f(x)\leq\sigma\bar{M}$ for $\bar{M}$
sufficiently large.

###### Theorem 1

Problem 1 is feasible if and only if the following MILP is feasible.

###### Problem 3

$\text{Find}\ \sigma^{m},\ \sigma^{c},\ Q,\ r,\ \Lambda\geq 0,\ \Gamma\geq 0,$

such that

  * •

$\sigma^{m}_{t},\sigma^{c}_{t}\in\\{0,1\\}$ for $t=0,\dots,T-1$,

  * •

Budget constraints (3) hold,

  * •

Matrix $Q$ is $n_{x}\times n_{y}$ block lower triangular,

  * •

Safety constraints (22) and (23) hold,

  * •

Bounded input constraints (24) and (25) hold,

  * •

Measurement compatibility constraint (26) holds,

  * •

Control compatibility constraint (27) holds.

Moreover, the feasible values of $\sigma^{m}$ and $\sigma^{c}$ are the same
for both problems and the feasible $Q$ and $r$ are linked by transformations
(14) and (15) to the feasible values of $\\{f_{t}\\}_{t=0}^{T-1}$ and
$\\{F_{(t,\tau)}\\}_{t=0,\ \tau=0}^{T-1,\ t}$ for Problem 1.

###### Proof:

From Lemma 1, the sequences $\\{z_{t}\\}_{t=0}^{T}$ and
$\\{u_{t}\\}_{t=0}^{T-1}$ generated by (1) and (2) are the same than the ones
generated by (4) when (5) and (6) hold.

Then, Lemma 3 indicates that (4) and the robustness constraint
$z_{t}\in\mathcal{Z}$ for $t=0,\dots,T$ hold if and only if (22) and (23)
hold. Similarly, Lemma 4 shows that the constraint $u_{t}\in\mathcal{U}$ for
$t=0,\dots,T-1$ holds if and only if (24) and (25) hold.

From Lemma 5, (5) holds if and only if (26) holds, and thanks to Lemma 6, (6)
holds if and only if (27) holds. Finally, the indicator constraints can be
handled using the Big-M method. ∎

Solving such a MILP can be done efficiently on many practical situations using
a branch and bound approach. This is illustrated in Section IV. In addition,
this problem is solved offline, before any measurements are received. Then,
the feasible solution can be efficiently used online.

##  IV EXAMPLES

A Julia code using Gurobi [20] generating the figures and implementing the
algorithms is available at https://github.com/kwesiRutledge/measurement-
scheduling0/tree/master/examples/. The reported computation times have been
obtained on a laptop with an Intel(R) Core(TM) i5-7267U 3.1 GHz processor.

###  IV-A A Double Integrator Drone System

Figure 2: Representation of 1000 trajectories $z_{t}$ sampled from the system
described in Section IV-A. The admissible set of initial positions is
indicated as $\mathcal{X}_{0}^{\text{position}}$ and the three different
safety sets $\mathcal{Z}_{t}$ are represented. Figure 3: Representation of
1000 simulated trajectories ($z_{t}$ and $u_{t}$) of the system described in
Section IV-A. Measurement and control times are indicated. The boundaries of
the safety sets $\partial\mathcal{Z}_{t}$ and the boundaries of the set of
admissible inputs $\partial\mathcal{U}$ are depicted. Finally, the sets of
possible values for $z_{t}$ and $u_{t}$ for all possible noises are also
depicted.

The task of remote monitoring of an area (e.g. for the remote reading of
pressure guages in power plants) is one of the more recent topics of interest
in cyber-physical systems [21]. Frequently implemented on collections of
robots including drones, quadripeds, and more, remote monitoring controllers
must be scalable enough to be implemented on large numbers of systems at once
while also avoiding exchanging too many messages and burdening the network. It
offers an excellent problem to solve with the methods developed in this paper
because each robot’s tasks can be encoded as reachability problems or reach-
avoid problems (i.e. reach a target set while avoiding an unsafe set) which
are readily handled with this method.

If one assumes that a drone’s $x$ position $p^{x}_{t}$ and $y$ position
$p^{y}_{t}$ are controlled by a simple force input, then the following
dynamics may be written:

$\begin{array}[]{l}\ddot{p}^{x}_{t}=u^{x}_{t},\\\
\ddot{p}^{y}_{t}=u^{y}_{t}.\end{array}$

The state and the input of the system are respectively

$x_{t}=\begin{bmatrix}p^{x}_{t}&p^{y}_{t}&\dot{p}^{x}_{t}&\dot{p}^{y}_{t}\end{bmatrix}^{\top},\;u_{t}=\begin{bmatrix}u^{x}_{t}&u^{y}_{t}\end{bmatrix}^{\top},$

and the dynamics is

$\dot{x}_{t}=\begin{bmatrix}0_{2\times 2}&I_{2}\\\ 0_{2\times 2}&0_{2\times
2}\end{bmatrix}x_{t}+\begin{bmatrix}0_{2\times 2}\\\ I_{2}\end{bmatrix}u_{t}.$

Finally, the output variable and the measurements are

$z_{t}=\begin{bmatrix}p^{x}_{t}&p^{y}_{t}\end{bmatrix}^{\top},\;y_{t}=z_{t}+v_{t}.$

We consider an exactly discretized version of this system with a
discretization time step of $0.1$. In addition, a process noise is considered.
The time horizon is $T=20$ time steps with $N_{m}=3$ measurements and
$N_{c}=4$ control inputs. In addition, we define
$\mathcal{W}=[-0.05,0.05]^{4}$, $\mathcal{V}=[-0.05,0.05]^{2}$,
$\mathcal{X}_{0}=[-1,1]^{2}\times\\{0\\}^{2}$ and $\mathcal{U}=[-20,20]^{2}$.
Finally, the safety set $\mathcal{Z}_{t}$ is time varying (see Remark 3) and
takes 3 different values for respectively $t=0,\dots,9$; $t=10,\dots,19$; and
$t=20$. They are represented in Fig. 2. This problem is solved in 292 seconds.

Fig. 3 shows 1000 simulated trajectories. For half of them, the $x_{0}$,
$w_{t}$ and $v_{t}$ are uniformly sampled in the polytopes. For the other half
of the trajectories, each uncertain variable is randomly sampled among the
vertices of the respective noise polytopes in order to promote extreme
trajectories. The measurement and control times are indicated, as well as the
boundaries of the safety sets $\partial\mathcal{Z}_{t}$ and the boundaries of
admissible inputs sets $\partial\mathcal{U}$. In addition, the set of possible
values for $z_{t}$ and $u_{t}$ for all admissible uncertainty $w_{t}$, $v_{t}$
and $x_{0}$ are represented. The same trajectories are depicted in Fig. 2
where the set of admissible initial positions of the drone is indicated (and
written $\mathcal{X}_{0}^{\text{position}}$), in addition to the time-varying
safety sets.

We can verify that all simulated trajectories respect the constraints
$z_{t}\in\mathcal{Z}$ and $u_{t}\in\mathcal{U}$. In addition, the measurement
and control times are not regularly spaced. In fact, if we impose the
measurement and control times to be spaced in time as regularly as possible,
i.e., $\sigma^{m}_{t}=1$ for $t\in\\{0,10,19\\}$ and $\sigma^{c}_{t}=1$ for
$t\in\\{0,6,13,19\\}$, then the problem is infeasible.

Finally, the left part of Table I presents the evolution of the solver time
with respect to the number of drones to be controlled in parallel. The state
dimension $n_{x}$ is also indicated. As expected, the solving time grows with
the state dimension. Note that for a state space in 48 dimensions, the problem
can be solved in less than $50$ minutes. In addition, these computations are
executed offline which make the computation time not critical.

TABLE I: Left: Problem 1 is solved for the system described in Section IV-A
with time horizon $T=20$ with a varying number of drones (and thus with
varying state dimension $n_{x}$). Right: Problem 1 is solved for the system
described in Section IV-B with a varying time horizon $T$ (and the number of
measurement and control times schedulings $\sigma^{m}$ and $\sigma^{c}$) with
$N_{m}=N_{c}=T/2$ measurements and controls.

Number | State | Solver
---|---|---
of Drones | Dimension | Time (s)
1 | 4 | 275.88
4 | 16 | 332.74
8 | 32 | 1118.96
12 | 48 | 2846.47

$T$ Number Solver Schedules Time (s) 2 4 0.03 10 63504 0.81 20 $3.41\cdot
10^{10}$ 19.96 30 $2.41\cdot 10^{16}$ 3284.71

###  IV-B Planar Linear Inverted Pendulum Model (Simplified Walker Dynamics)
[22]

Figure 4: Representation of 1000 simulated trajectories of system (28).
Measurement and control times are indicated. The boundaries of the safety set
$\partial\mathcal{Z}$ and the boundaries of the set of admissible inputs
$\partial\mathcal{U}$ are depicted. Finally, the sets of possible values for
$z_{t}$ and $u_{t}$ for all possibles noises are also depicted.

The task of walking is one which typically does not require constant
observation in order to safely execute. Humans routinely walk without
knowledge of the exact position of their foot or angle of their torso, yet
most controllers for walking robots require full state observation at all
times.

To show the utility of our method, we analyze a small example where a robot
model (the planar linear inverted pendulum) can be safely controlled by a
policy which infrequently observes the state.

The planar linear inverted pendulum model as discussed in [22] can be
represented as a state space model with the following equations:

$\ddot{x}^{cm}=\frac{g}{\bar{z}^{cm}}(x^{cm}+r^{foot}u),$ (28)

where $x^{cm}$ is the lateral position of the pendulum’s center of mass,
$\bar{z}^{cm}$ is the height of the pendulum’s center of mass (which is
assumed to be constant), $r^{foot}$ is the radius of the foot, and $u$
controls the center of pressure on the foot. We consider $\bar{z}^{cm}=1$,
$r^{foot}=0.5$ and $g=9.81$.

We solve Problem 2 for an exactly discretized version of (28) with a $0.1$
discretization time step. We have
$x_{t}=\begin{bmatrix}x^{cm}_{t}&\dot{x}^{cm}_{t}\end{bmatrix}^{\top}$,
$y_{t}=x_{t}$ and $z_{t}=x_{t}+v_{t}$. We consider
$\mathcal{W}=[-0.05,0.05]^{2}$, $\mathcal{V}=[-0.01,0.01]^{2}$,
$\mathcal{X}_{0}=[-0.1,0.1]^{2}$, $\mathcal{U}=[-1,1]$,
$\mathcal{Z}=[-0.75,0.75]\times[-5,5]$, $N_{m}=N_{c}=5$. We consider the upper
bound $\bar{T}=20$. This problem is solved in 284 seconds. The largest $T$ for
which the problem is feasible is $T^{*}=17$. Fig. 4 presents the obtained
trajectories. For half of them, the uncertainties are randomly selected among
the vertices of the polytopes to promote extreme trajectories.

For the same system, the right part of Table I presents the evolution of the
solving time for Problem 1 according to the time horizon $T$ when the number
of measurement and control times is $N_{m}=N_{c}=T/2$. In addition, the number
of measurement and control scheduling is indicated (assuming that the budget
constraints (3) are tight). This table shows that the solving time increases
with the time horizon but much slower than the number of possible measurement
and control times scheduling. Again, these computations are performed offline.

###### Remark 5

Although these time horizons may be modest for many applications, a long time
horizon $T^{\prime}$ can be decomposed into multiple “components” (e.g.,
$T_{1}+T_{2}=T^{\prime}$) where smaller problems are solved with appropriate
initial, intermediate conditions and budget constraints to derive a result for
the long time horizon $T^{\prime}$.

##  V CONCLUSIONS AND FUTURE WORKS

In this paper, we have addressed the problem of co-designing a linear
controller with memory, a measurement schedule, and a control schedule that
guarantees safety. By proving that such a problem is equivalent to a MILP, we
make this problem computationally tractable. This is illustrated on two
examples.

For our future research, we want to adapt this method to the case where
polytopes are zonotopes. In this case, we hope to reduce the computation time
using methods such as zonotope order reduction techniques [23]. Furthermore,
we plan to develop an online version of this algorithm, where observation
times are computed on the fly, while the system is running, and thus
leveraging the current observations at each time step. In such a formulation,
the problem will be solved again after each measurement in order to
incorporate the information recently acquired.

## References

  * [1] X. Zhang, Q. Han, X. Ge, D. Ding, L. Ding, D. Yue, and C. Peng, “Networked control systems: a survey of trends and techniques,” _IEEE/CAA Journal of Automatica Sinica_ , vol. 7, no. 1, pp. 1–17, 2020.
  * [2] L. Schenato, B. Sinopoli, M. Franceschetti, K. Poolla, and S. S. Sastry, “Foundations of control and estimation over lossy networks,” _Proceedings of the IEEE_ , vol. 95, no. 1, pp. 163–187, Jan 2007.
  * [3] W. M. H. Heemels, A. R. Teel, N. Van de Wouw, and D. Nešić, “Networked control systems with communication constraints: Tradeoffs between transmission intervals, delays and performance,” _IEEE Transactions on Automatic control_ , vol. 55, no. 8, pp. 1781–1796, 2010.
  * [4] M. S. Branicky, S. M. Phillips, and Wei Zhang, “Scheduling and feedback co-design for networked control systems,” in _Proceedings of the 41st IEEE Conference on Decision and Control, 2002._ , vol. 2, 2002, pp. 1211–1217 vol.2.
  * [5] M. Trivellato and N. Benvenuto, “State control in networked control systems under packet drops and limited transmission bandwidth,” _IEEE Transactions on Communications_ , vol. 58, no. 2, pp. 611–622, 2010.
  * [6] W. P. M. H. Heemels, K. H. Johansson, and P. Tabuada, “An introduction to event-triggered and self-triggered control,” in _2012 IEEE 51st IEEE Conference on Decision and Control (CDC)_ , 2012, pp. 3270–3285.
  * [7] X. Zhang, Q. Han, and B. Zhang, “An overview and deep investigation on sampled-data-based event-triggered control and filtering for networked systems,” _IEEE Transactions on Industrial Informatics_ , vol. 13, no. 1, pp. 4–16, 2017.
  * [8] C. De Persis, R. Sailer, and F. Wirth, “Parsimonious event-triggered distributed control: A zeno free approach,” _Automatica_ , vol. 49, no. 7, pp. 2116–2124, 2013. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0005109813001726
  * [9] L. Lessard and S. Lall, “Quadratic invariance is necessary and sufficient for convexity,” in _Proceedings of the 2011 American Control Conference_. IEEE, 2011, pp. 5360–5362.
  * [10] M. Rotkowitz and S. Lall, “A characterization of convex problems in decentralized control,” _IEEE transactions on Automatic Control_ , vol. 51, no. 2, 2006.
  * [11] Z. Gao, “Active disturbance rejection control: a paradigm shift in feedback control system design,” in _2006 American control conference_. IEEE, 2006, pp. 7–pp.
  * [12] Y. Wang, N. Matni, and J. C. Doyle, “A system-level approach to controller synthesis,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 10, pp. 4079–4093, 2019.
  * [13] A. Ben-Tal and A. Nemirovski, “Robust solutions of uncertain linear programs,” _Operations Research Letters_ , vol. 25, no. 1, pp. 1–13, 1999\. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167637799000164
  * [14] S. Sadraddini and R. Tedrake, “Robust output feedback control with guaranteed constraint satisfaction,” in _Proceedings of the 23rd International Conference on Hybrid Systems: Computation and Control_ , 2020, pp. 1–10.
  * [15] J. Skaf and S. P. Boyd, “Design of affine controllers via convex optimization,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 11, pp. 2476–2487, 2010.
  * [16] D. Youla, H. Jabr, and J. Bongiorno, “Modern wiener-hopf design of optimal controllers–part ii: The multivariable case,” _IEEE Transactions on Automatic Control_ , vol. 21, no. 3, pp. 319–338, 1976.
  * [17] R. M. Jungers, A. Kundu, and W. P. M. H. Heemels, “Observability and controllability analysis of linear systems subject to data losses,” _IEEE Transactions on Automatic Control_ , vol. 63, no. 10, pp. 3361–3376, 2018.
  * [18] K. Rutledge, S. Z. Yong, and N. Ozay, “Finite horizon constrained control and bounded-error estimation in the presence of missing data,” _Nonlinear Analysis: Hybrid Systems_ , vol. 36, p. 100854, 2020.
  * [19] J.-C. Hennet, “Une extension du lemme de farkas et son application au probleme de régulation linéaire sous contraintes,” _CR Acad. Sci. Paris_ , vol. 308, no. I, pp. 415–419, 1989.
  * [20] L. Gurobi Optimization, “Gurobi optimizer reference manual,” 2021. [Online]. Available: http://www.gurobi.com
  * [21] S. Bharadwaj, R. Dimitrova, and U. Topcu, “Synthesis of surveillance strategies via belief abstraction,” in _2018 IEEE Conference on Decision and Control (CDC)_. IEEE, 2018, pp. 4159–4166.
  * [22] M. A. Posa, T. Koolen, and R. L. Tedrake, “Balancing and step recovery capturability via sums-of-squares optimization,” 2017.
  * [23] X. Yang and J. K. Scott, “A comparison of zonotope order reduction techniques,” _Automatica_ , vol. 95, pp. 378–384, 2018.

##  Appendix A Proofs

###  A-A Proof of Lemma 1

If $\sigma^{c}_{t}=1$, one can use (5) to write

$f_{t}+\sum_{\tau\leq t\text{\ s.t.\
}\sigma^{m}_{\tau}=1}F_{(t,\tau)}y_{\tau}=f_{t}+\sum_{\tau\leq
t}F_{(t,\tau)}y_{\tau},$

then (2) and (4d) give the same $u_{t}$. On the other hand, if
$\sigma^{c}_{t}=0$, one can use (6) to write

$\displaystyle f_{t}+\sum_{\tau\leq t}F_{(t,\tau)}y_{\tau}$
$\displaystyle=f_{t-1}+\sum_{\tau\leq t}F_{(t-1,\tau)}y_{\tau}$
$\displaystyle=f_{t-1}+\sum_{\tau\leq t-1}F_{(t-1,\tau)}y_{\tau}.$

then (2) and (4d) give the same $u_{t}$.

It follows that the sequences of $u_{t}$ are the same. But then, so it is for
the sequences of $x_{t}$ and finally, for the sequences of $z_{t}$.

###  A-B Proof of Lemma 3

By writing
$\eta=\begin{bmatrix}w^{\top}&v^{\top}&x_{0}^{\top}\end{bmatrix}^{\top}\in\mathcal{W}^{T}\times\mathcal{V}^{T}\times\mathcal{X}_{0}$
and $P_{z,:}=\begin{bmatrix}P_{zw}&P_{zv}&P_{zx_{0}}\end{bmatrix}$ and using
(16), we can write

$\begin{array}[]{lrcl}&z_{t}&\in&\mathcal{Z}\text{\ for\ all\ }t=0,\dots,T\\\
\Leftrightarrow&H_{\mathcal{Z}}z_{t}&\leq&h_{\mathcal{Z}}\text{\ for\ all\
}t=0,\dots,T\\\ \Leftrightarrow&\left(I_{T+1}\otimes
H_{\mathcal{Z}}\right)z&\leq&\mathbb{1}_{T+1}\otimes h_{\mathcal{Z}}\\\
\Leftrightarrow&\left(I_{T+1}\otimes
H_{\mathcal{Z}}\right)(P_{z,:}\eta+\tilde{z})&\leq&\mathbb{1}_{T+1}\otimes
h_{\mathcal{Z}}\\\ \Leftrightarrow&\left(I_{T+1}\otimes
H_{\mathcal{Z}}\right)P_{z,:}\eta&\leq&\mathbb{1}_{T+1}\otimes
h_{\mathcal{Z}}\\\ &&&\hskip 28.45274pt-\left(I_{T+1}\otimes
H_{\mathcal{Z}}\right)\tilde{z}.\end{array}$

The last inequality can be interpreted as requiring that $\eta$ is in a
polyhedron (let’s call it $\mathcal{P}$). Then, $z_{t}\in\mathcal{Z}$ for all
$t=0,\dots,T$ and for all
$\eta\in\mathcal{W}^{T}\times\mathcal{V}^{T}\times\mathcal{X}_{0}$ if and only
if $\eta\in\mathcal{P}$ for all $\eta$. This is equivalent to
$\mathcal{W}^{T}\times\mathcal{V}^{T}\times\mathcal{X}_{0}\subseteq\mathcal{P}$.
Then, using Lemma 2, the constraint $z_{t}\in\mathcal{Z}$ for all
$t=0,\dots,T$ and for all
$\eta\in\mathcal{W}^{T}\times\mathcal{V}^{T}\times\mathcal{X}_{0}$ holds if
and only if there exists
$\Lambda\in\mathbb{R}^{(T+1)n_{\mathcal{Z}}\times(T(n_{\mathcal{W}}+n_{\mathcal{V}})+n_{\mathcal{X}_{0}})}_{+}$
such that (22) and (23) hold.

###  A-C Proof of Lemma 4

The proof is similar to the one of Lemma 3. Let
$\eta=\begin{bmatrix}w^{\top}&v^{\top}&x_{0}^{\top}\end{bmatrix}^{\top}\in\mathcal{W}^{T}\times\mathcal{V}^{T}\times\mathcal{X}_{0}$
and $P_{u,:}=\begin{bmatrix}P_{uw}&P_{uv}&P_{ux_{0}}\end{bmatrix}$ and using
(16), we can write

$\begin{array}[]{lrcl}&u_{t}&\in&\mathcal{U}\text{\ for\ all\
}t=0,\dots,T-1\\\
\Leftrightarrow&H_{\mathcal{U}}u_{t}&\leq&h_{\mathcal{U}}\text{\ for\ all\
}t=0,\dots,T-1\\\ \Leftrightarrow&\left(I_{T}\otimes
H_{\mathcal{U}}\right)u&\leq&\mathbb{1}_{T}\otimes h_{\mathcal{U}}\\\
\Leftrightarrow&\left(I_{T}\otimes
H_{\mathcal{U}}\right)(P_{u,:}\eta+\tilde{u})&\leq&\mathbb{1}_{T}\otimes
h_{\mathcal{U}}\\\ \Leftrightarrow&\left(I_{T}\otimes
H_{\mathcal{U}}\right)P_{u,:}\eta&\leq&\mathbb{1}_{T}\otimes
h_{\mathcal{U}}-\left(I_{T}\otimes
H_{\mathcal{U}}\right)\tilde{u}.\end{array}$

The last inequality can be interpreted as requiring that $\eta$ is in a
polytope (let’s call it $\mathcal{Q}$). Then, $u_{t}\in\mathcal{U}$ for all
$t=0,\dots,T-1$ and for all
$\eta\in\mathcal{W}^{T}\times\mathcal{V}^{T}\times\mathcal{X}_{0}$ if and only
if $\eta\in\mathcal{Q}$ for all $\eta$. This is equivalent to
$\mathcal{W}^{T}\times\mathcal{V}^{T}\times\mathcal{X}_{0}\subseteq\mathcal{Q}$.
Then, using Lemma 2, the constraint $u_{t}\in\mathcal{U}$ for all
$t=0,\dots,T-1$ and for all
$\eta\in\mathcal{W}^{T}\times\mathcal{V}^{T}\times\mathcal{X}_{0}$ holds if
and only if there exists
$\Gamma\in\mathbb{R}^{Tn_{\mathcal{U}}\times(T(n_{\mathcal{W}}+n_{\mathcal{V}})+n_{\mathcal{X}_{0}})}_{+}$
such that (24) and (25) hold.

###  A-D Proof of Lemma 5

Let $\tau\in\\{0,\dots,T-1\\}$ and assume $\sigma^{m}_{\tau}=0$. From (8), we
have that for a fixed $\tau$, the matrices $F_{(t,\tau)}$ are in the same
columns of $F$ for all $t$. The indices of these columns are
$\mathcal{J}_{\tau}$. Then, $F_{(t,\tau)}=0$ for all $t=\tau,\dots,T-1$, if
and only if $F_{:,\mathcal{J}_{\tau}}=0$. Then, looking at (14), one can write

$F_{:,\mathcal{J}_{\tau}}=(I+Q\bar{C}S)^{-1}Q_{:,\mathcal{J}_{\tau}}.$

Observing that $(I+Q\bar{C}S)^{-1}$ is invertible, it follows that
$F_{:,\mathcal{J}_{\tau}}=0$ if and only if $Q_{:,\mathcal{J}_{\tau}}=0$.

###  A-E Proof of Lemma 6

Let $t\in\\{1,\dots,T-1\\}$ and assume that $\sigma^{c}_{t}=0$. From (7) and
(8), the constraints $f_{t}=f_{t-1}$ and $F_{(t,\tau)}=F_{(t-1,\tau)}$ can be
written $f_{\mathcal{I}_{t}}=f_{\mathcal{I}_{t-1}}$ and
$F_{\mathcal{I}_{t},:}=F_{\mathcal{I}_{t-1},:}$.

Otherwise, from (12), one can write

$Q_{\mathcal{I}_{t},:}-Q_{\mathcal{I}_{t-1},:}=(F_{\mathcal{I}_{t},:}-F_{\mathcal{I}_{t-1},:})(I-\bar{C}SF)^{-1}.$
(29)

But $(I-\bar{C}SF)^{-1}$ is invertible so
$F_{\mathcal{I}_{t},:}-F_{\mathcal{I}_{t-1},:}=0_{n_{u}\times Tn_{y}}$ if and
only if $Q_{\mathcal{I}_{t},:}-Q_{\mathcal{I}_{t-1},:}=0$.

Finally, thanks to (13), one can write

$r_{\mathcal{I}_{t}}-r_{\mathcal{I}_{t-1}}=f_{\mathcal{I}_{t}}-f_{\mathcal{I}_{t-1}}+(Q_{\mathcal{I}_{t},:}-Q_{\mathcal{I}_{t-1},:})\bar{C}Sf,$

where, thanks to the observation following (29), the last term is cancelled in
both the necessary and the sufficient cases, i.e., when
$Q_{\mathcal{I}_{t},:}-Q_{\mathcal{I}_{t-1},:}=0$ and when
$F_{\mathcal{I}_{t},:}-F_{\mathcal{I}_{t-1},:}=0$. It leads to
$F_{\mathcal{I}_{t},:}-F_{\mathcal{I}_{t-1},:}=0$ and
$f_{\mathcal{I}_{t}}-f_{\mathcal{I}_{t-1}}=0$ if and only if
$Q_{\mathcal{I}_{t},:}-Q_{\mathcal{I}_{t-1},:}=0$ and
$r_{\mathcal{I}_{t}}-r_{\mathcal{I}_{t-1}}=0$.

The case $t=0$ is similar, indeed, consider that $u_{-1},f_{-1},F_{(-1,\tau)}$
and all quantities indexed by $\mathcal{I}_{-1}$ are zeros with compatible
dimensions.