# On Target Control Synthesis Under Set-Membership Uncertainties Using Polyhedral Techniques

Elena K. Kostousova

► To cite this version:

Elena K. Kostousova. On Target Control Synthesis Under Set-Membership Uncertainties Using Polyhedral Techniques. 26th Conference on System Modeling and Optimization (CSMO), Sep 2013, Klagenfurt, Austria. pp.170-180, 10.1007/978-3-662-45504-3_16. hal-01286409

HAL Id: hal-01286409

https://inria.hal.science/hal-01286409

Submitted on 10 Mar 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On target control synthesis under set-membership uncertainties using polyhedral techniques*

Elena K. Kostousova

N.N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the
Russian Academy of Sciences
16, S.Kovalevskaja street, Ekaterinburg, 620990, Russia
kek@imm.uran.ru

**Abstract.** Problems of feedback terminal target control for linear and bilinear uncertain systems are considered. We continue the development of control synthesis using polyhedral (parallelotope-valued) solvability tubes. The paper deals with two types of problems, where controls appear either additively or in the system matrix. For both problems, the cases without uncertainties, with additive parallelotope-bounded uncertainties, and also with interval uncertainties in coefficients of the system (a bilinear uncertainty) are considered. Ordinary differential equations, which describe the mentioned polyhedral solvability tubes, are presented for each of these cases. New control strategies, which can be calculated by explicit formulas on the base of the mentioned tubes, are proposed. Results of computer simulations are presented.

**Keywords:** Differential systems, uncertain systems, control synthesis, polyhedral estimates, parallelotopes, interval analysis.

## 1 Introduction

Problems of feedback terminal target control for linear and bilinear differential uncertain systems are considered. There are known approaches for solving problems like these, in particular, based on constructing solvability tubes and the extremal aiming strategies of N.N. Krasovskii [13, 17]. The problem statement for linear systems, approaches for solving, and the tight interconnections between solvability tubes, the Pontriagin alternated integral, Hamilton-Jacobi-Bellman equations, and funnel equations can be found, for example, in [15–17].

Since practical construction of the mentioned tubes can be cumbersome, different numerical methods are devised, in particular, methods for approximating

<footnote>* The research was partially supported by the Program of Basic Research of the Ural Branch of RAS (Project 12-P-1-1019), by the Russian Foundation for Basic Research (Grant 12-01-00043), and by the Program for the State Support of Leading Scientific Schools of Russian Federation (Grant 2692.2014.1).</footnote>
the set-valued integrals and for numerical solving the mentioned equations, including methods based on approximations of sets by arbitrary polytopes with a large number of vertices [2, 4, 21, 22] (here and below we mention, as examples, only some references from numerous publications; see also references therein). Such methods are devised to obtain approximations as accurate as possible. But they can require much calculations, especially for large dimensional systems. Other techniques are based on estimates of sets by domains of some fixed shape such as ellipsoids and parallelepipeds, including boxes aligned with coordinate axes as in interval analysis [4, 5, 7–12, 14, 15, 17, 18, 20]. The main advantage of such techniques is that they enable to obtain approximate/particular solutions using relatively simple tools (up to explicit formulas). More accurate approximations may be obtained by using the whole families (varieties) of such simple estimates (as was proposed by A.B. Kurzhanski) [17, 15, 18, 12, 8].

For linear differential systems, the constructive computation schemes for solving the feedback target control problems by means of ellipsoidal techniques were proposed [17, 15] and then expanded to a polyhedral technique [8]. Here we continue the development of the polyhedral control synthesis using polyhedral (parallelotope-valued) solvability tubes. The paper deals with two types of problems, where the controls appear either additively or in the system matrix. For both problems, the cases without uncertainties, with additive uncertainties, and also with interval uncertainties in coefficients of the system (the bilinear uncertainty) are considered. Ordinary differential equations (ODE) for the mentioned polyhedral solvability tubes are presented. New control strategies, which can be calculated by explicit formulas on the base of the mentioned tubes, are proposed. In opposite to [17, 15, 8], they are concretized by explicit formulas when the state belongs to a tube. Also the polyhedral control synthesis for discrete-time systems is considered. The results of computer simulations are presented.

Note that there are also some works devoted to other approaches for solving different control problems under uncertainty and works concerning systems with bilinear uncertainties (see, for example, [1, 4, 6, 19, 20]).

The following notation is used below: $\mathbb{R}^n$ is the $n$-dimensional vector space; $\top$ is the transposition symbol; $\|x\|_2 = (x^\top x)^{1/2}$, $\|x\|_\infty = \max_{1\le i\le n} |x_i|$ are vector norms for $x=(x_1, x_2, \dots, x_n)^\top \in \mathbb{R}^n$; $e_i=(0, \dots, 0, 1, 0, \dots, 0)^\top$ is the unit vector oriented along the axis $0x_i$ (the unit stands at position $i$); $e = (1, 1, \dots, 1)^\top$; $\mathbb{R}^{n \times m}$ is the space of real $n \times m$-matrices $A = \{a_i^j\} = \{a^j\}$ (with columns $a^j$); $I$ is the identity matrix; $0$ is the zero matrix (vector); Abs $A = \{|a_i^j|\}$ for $A = \{a_i^j\}$; diag $\pi$, diag $\{\pi_i\}$ are the diagonal matrix $A$ with $a_i^i = \pi_i$ ($\pi_i$ are the components of the vector $\pi$); det $A$ is the determinant of $A$; tr $A=\sum_{i=1}^n a_i^i$ is the trace of $A$; $\|A\| = \max_{1\le i\le n} \sum_{j=1}^m |a_i^j|$ for $A\in\mathbb{R}^{n \times m}$; int $\mathcal{X}$ is the set of interior points of the set $\mathcal{X} \subset \mathbb{R}^n$; the notation of the type $k=1, \dots, N$ is used instead of $k=1, 2, \dots, N$.

## 2 Problems formulation

Consider the controlled system with a given terminal set $\mathcal{M} (x\in\mathbb{R}^n$ is the state):

$$ \dot{x} = (A(t) + U(t) + V(t)) x + u(t) + v(t), \quad t \in T = [0, \theta]. \quad (1) $$
Here $A(t) \in \mathbb{R}^{n \times n}$ is a given matrix function; Lebesgue measurable functions $U(t) \in \mathbb{R}^{n \times n}$ and $u(t) \in \mathbb{R}^n$ serve as controls and satisfy either (2) or (3):

$$ U(t) \equiv 0, \quad u(t) \in \mathcal{R}(t), \quad \text{a.e. } t \in T, \qquad (2) $$

$$ U(t) \in \mathcal{U}(t) = \{U \in \mathbb{R}^{n \times n} | \text{Abs}(U - \tilde{U}(t)) \le \hat{U}(t)\}, \quad u(t) \equiv 0, \quad \text{a.e. } t \in T; \quad (3) \\ V(t) \in \mathbb{R}^{n \times n} \text{ and } v(t) \in \mathbb{R}^n \text{ stand for unknown disturbances and satisfy} $$

$$ V(t) \in \mathcal{V}(t) = \{V \in \mathbb{R}^{n \times n} | \text{Abs}(V - \tilde{V}(t)) \le \hat{V}(t)\}, \quad v(t) \in \mathcal{Q}(t), \quad \text{a.e. } t \in T. \quad (4) $$

Matrix and vector inequalities ($\le$, $<$, $\ge$, $>$) here and below are understood componentwise. We presume the sets $\mathcal{R}(t)$, $\mathcal{Q}(t)$, and $\mathcal{M}$ to be parallelotopes and a parallelepiped respectively:

$$ \begin{gathered} \mathcal{R}(t) = \mathcal{P}[r(t), \bar{R}(t)], \quad \bar{R}(t) \in \mathbb{R}^{n \times n_1}, \quad \mathcal{Q}(t) = \mathcal{P}[q(t), \bar{Q}(t)], \quad \bar{Q}(t) \in \mathbb{R}^{n \times n_2}, \\ \mathcal{M} = \mathcal{P}(p_f, P_f, \pi_f) = \mathcal{P}[p_f, \bar{P}_f], \quad \bar{P}_f \in \mathbb{R}^{n \times n}, \det \bar{P}_f \ne 0; \end{gathered} \qquad (5) $$

$r(t)$, $\bar{R}(t)$, $q(t)$, $\bar{Q}(t)$, as well as $A(t)$, $\tilde{U}(t)$, $\hat{U}(t) \ge 0$, $\tilde{V}(t)$, $\hat{V}(t) \ge 0$, are known continuous vector and matrix functions; the parallelepiped $\mathcal{M}$ is nondegenerate.

By a parallelepiped $\mathcal{P}(p, P, \pi) \subset \mathbb{R}^n$ we mean a set such that $\mathcal{P}=\mathcal{P}(p, P, \pi) = \{x \in \mathbb{R}^n | x=p+\sum_{i=1}^n p^i \pi_i \xi_i, \|\xi\|_{\infty} \le 1\}$, where $p \in \mathbb{R}^n$; $P=\{p^i\} \in \mathbb{R}^{n \times n}$ is such that $\det P \ne 0$, $\|p^i\|_2=1$; $\pi \in \mathbb{R}^n$, $\pi \ge 0$. It may be said that $p$ determines the center of the parallelepiped, $P$ is the orientation matrix, $p^i$ are the “directions” and $\pi_i$ are the values of its “semi-axes”. We call a parallelepiped nondegenerate if $\pi>0$.

By a parallelootope $\mathcal{P}[p, \bar{P}] \subset \mathbb{R}^n$ we mean a set $\mathcal{P} = \mathcal{P}[p, \bar{P}] = \{x \in \mathbb{R}^n | x = p+\bar{P}\zeta, \|\zeta\|_{\infty} \le 1\}$, where $p \in \mathbb{R}^n$ and the matrix $\bar{P} = \{\bar{p}^i\} \in \mathbb{R}^{n \times m}$, $m \le n$, may be singular. We call a parallelootope $\mathcal{P}$ nondegenerate if $m=n$ and $\det \bar{P} \ne 0$.

Each parallelepiped $\mathcal{P}(p, P, \pi)$ is a parallelootope $\mathcal{P}[p, \bar{P}]$ with $\bar{P} = P$ diag $\pi$; each nondegenerate parallelootope is a parallelepiped with $P=\bar{P}$ diag $\{\|\bar{p}^i\|_2^{-1}\}$, $\pi_i = \|\bar{p}^i\|_2$ or, in a different way, with $P = \bar{P}$, $\pi = e$, where $e = (1, 1, \dots, 1)^T$.

We can consider the above system for the following cases: (I) *without uncertainty* when $v$ and $V \equiv 0$ are given functions, i.e., $\bar{Q} \equiv 0$, $\tilde{V} \equiv \hat{V} \equiv 0$; (II) *under uncertainty* including the following three subcases: (II,i) *only additive uncertainty* ($V \equiv 0$); (II,ii) *only matrix uncertainty* ($\bar{Q} \equiv 0$); (II,iii) *both ones*.

In [15–17], for cases (I) and (II,i) with controls (2), the following problem of terminal target control synthesis under uncertainty was investigated.

**Problem 1.** For the system (1),(2),(4), case (I) or (II,i), specify a solvability set $W(\tau, \theta, \mathcal{M}) = W(\tau)$ and a set-valued feedback control strategy<fnref n="2" /> $u = u(t, x)$, $u(\cdot, \cdot) \in U_{\mathcal{R}}^c$, such that all solutions to the differential inclusion $\dot{x} \in A(t)x + u(t, x) + \mathcal{Q}(t)$, $t \in T$, that start from any given position $\{\tau, x_\tau\}$, $x_\tau = x(\tau) \in W(\tau, \theta, \mathcal{M})$, $\tau \in [0, \theta)$, would reach the terminal set $\mathcal{M}$ at time $\theta: x(\theta) \in \mathcal{M}$.

<footnote n="1">¹ The normality condition $\|p^i\|_2=1$ may be omitted to simplify formulas.</footnote>

<footnote n="2">² Here the class $U_{\mathcal{R}}^c$ of feasible control strategies is taken to consist of all convex compact-valued multifunctions $u(t, x)$ that are measurable in $t$, upper semi-continuous in $x$, being restricted by $u(t, x) \subseteq \mathcal{R}(t)$, $t \in T$. The condition $u(\cdot, \cdot) \in U_{\mathcal{R}}^c$ ensures that the corresponding differential inclusion does have a solution.</footnote>
The multivalued function $W(t)$, $t \in T$, is known as a *solvability tube* $W(\cdot)$.

The ellipsoidal synthesis was elaborated in [15, 17] for solving Problem 1. In [8], the families of external $\mathcal{P}^+(\cdot)$ and internal $\mathcal{P}^-(\cdot)$ parallelootope-valued (shorter, *polyhedral*) estimates for $W(\cdot)$ were introduced. The extremal aiming strategies of N.N. Krasovskii were used there. They were constructed in an analytical form on the base of a solution of some specific mathematical programming problem. Now let us consider two following problems, which concern all above cases of uncertainties. Unlike Problem 1, they involve single-valued control strategies. This is possible because our strategies will be continuous and even linear with respect to $x$. Moreover, they will be constructed in an explicit form.

**Problem 2.** For the system (1), (2), (4), (5), find a polyhedral tube $\mathcal{P}^-(t) = \mathcal{P}[p^-(t), \bar{P}^-(t)]$, $t \in T$, with $\mathcal{P}^-(\theta) = \mathcal{M}$, and find a corresponding feedback control strategy $u = u(t, x)$ such that $u(t, x) \in \mathcal{R}(t)$ for $x \in \mathcal{P}^-(t)$, $t \in T$, and each solution $x(\cdot)$ to the differential equation $\dot{x} = (A(t) + V(t))x + u(t, x) + v(t)$, $t \in T$, with $x(0) = x_0 \in \text{int} \mathcal{P}^-(0)$ would be defined on $T$ and would satisfy $x(t) \in \mathcal{P}^-(t)$, $t \in T$, whatever are $v(\cdot)$ and $V(\cdot)$ subjected to (4). Moreover, introduce a whole family of such tubes $\mathcal{P}^-(\cdot)$.

**Problem 3.** For the system (1), (3), (4), (5), find a polyhedral tube $\mathcal{P}^-(t) = \mathcal{P}[p^-(t), \bar{P}^-(t)]$, $t \in T$, with $\mathcal{P}^-(\theta) = \mathcal{M}$, and find a corresponding feedback control strategy $U = U(t, x)$ such that $U(t, x) \in \mathcal{U}(t)$ for $x \in \mathcal{P}^-(t)$, $t \in T$, and each solution $x(\cdot)$ to the differential equation

$$ \dot{x} = (A(t) + U(t, x) + V(t))x + v(t), \quad t \in T, \qquad (6) $$

with $x(0)=x_0 \in \text{int} \mathcal{P}^-(0)$ would be defined on $T$ and would satisfy $x(t) \in \mathcal{P}^-(t)$, $t \in T$, whatever are $V(\cdot), v(\cdot)$ subjected to (4). Introduce a family of such tubes.

### 3 Solutions to Problem 2

First, let us consider the following ODE system for $\mathcal{P}^-(t) = \mathcal{P}[p^-(t), \bar{P}^-(t)]$:

$$ \frac{dp^{-}}{dt} = (A(t) + \tilde{V}(t))p^{-} + r(t) + q(t), \quad p^{-}(\theta) = p_{f}; \qquad (7) $$

$$ \begin{aligned} \frac{d\bar{P}^{-}}{dt} &= (A(t) + \tilde{V}(t))\bar{P}^{-} + \bar{P}^{-}\operatorname{diag}\beta(t, \bar{P}^{-}) + \bar{R}(t)\Gamma(t) + \bar{P}^{-}\operatorname{diag}\gamma(t, \bar{P}^{-}), \\ \beta(t, \bar{P}^{-}) &= \max\{\operatorname{Abs}((\bar{P}^{-})^{-1})\hat{V}(t)\operatorname{Abs}(p^{-}(t) + \bar{P}^{-}\xi) | \xi \in \mathbb{E}(\mathcal{C})\}, \\ \gamma(t, \bar{P}^{-}) &= \operatorname{Abs}((\bar{P}^{-})^{-1}\bar{Q}(t))e, \quad \bar{P}^{-}(\theta) = \bar{P}_{f}. \end{aligned} \qquad (8) $$

Here (and below) the operation of maximum is understood componentwise, $\mathbb{E}(\mathcal{C})$ denotes the set of all vertices of $\mathcal{C} = \mathcal{P}(0, I, e)$ (i.e., points $\xi \in \mathbb{R}^n$ with $\xi_j \in \{-1, 1\}$); $\Gamma(t) \in \mathbb{R}^{n_1 \times n}$ is an arbitrary Lebesgue measurable matrix function satisfying $\Gamma(t) \in \mathcal{G}$, a.e. $t \in T$, where $\mathcal{G} = \{\Gamma = \{\gamma_i^j\} \in \mathbb{R}^{n_1 \times n} | \|\Gamma\| \le 1\}$, $\|\Gamma\| = \max_{1 \le i \le n_1} \sum_{j=1}^n |\gamma_i^j|$. Let $\mathcal{G}$ be the set of all such functions $\Gamma(\cdot)$. Let us consider the following control strategy, being connected with $\mathcal{P}^-(\cdot)$ from (7),(8):

$$ u(t, x) = r(t) + \bar{R}(t)\Gamma(t)\bar{P}^{-}(t)^{-1}(x - p^{-}(t)). \qquad (9) $$
**Theorem 1.** We consider the system (1), (2), (4), (5), where $\det \bar{P}_f \neq 0$. Let $\Gamma(\cdot) \in \mathbb{G}$. Then the system (7), (8) has a unique solution $(p^-(\cdot), \bar{P}^-(\cdot))$ at least on some subinterval $T_1=[\tau_1, \theta] \subseteq T$, where $0 \le \tau_1 < \theta$. If $T_1=T$ and we have $\det \bar{P}^-(t) \ne 0, t \in T$, then the tube $\mathcal{P}^-(\cdot)$ and the control strategy (9) give a particular solution to Problem 2; in cases (I), (II,i), all solutions $x(\cdot)$ with $x(0) \in \mathcal{P}^-(0)$ (not only with $x(0) \in \text{int} \, \mathcal{P}^-(0)$) generated by (9) satisfy $x(t) \in \mathcal{P}^-(t)$, $t \in T$.

The scheme of the proof is similar to the proof of Theorem 2 (see below).

Theorem 1 describes the whole family of tubes $\mathcal{P}^-(\cdot)$, where $\Gamma(\cdot)$ serves as a parameter. Thus the set $W^0 = \bigcup\{\text{int } \mathcal{P}^-(0) | \Gamma(\cdot) \in \mathbb{G} \text{ such that } \det \mathcal{P}^-(t) \ne 0, t \in T\}$ (or, in cases (I), (II,i), the analogous set $W^0 = \bigcup \mathcal{P}^-(0)$) provides the set of initial positions which can be steered to the terminal set $\mathcal{M}$ during the time $\theta$ by solving Problem 2. But, generally speaking, it is not true that $\det \mathcal{P}^-(0) \ne 0$ or even $\mathcal{P}^-(0) \ne \emptyset$ for each $\Gamma(\cdot) \in \mathbb{G}$. For cases (I), (II,i), the above family of the tubes $\mathcal{P}^-(\cdot)$ coincides with the family of internal estimates for $W(\cdot)$ introduced in [8]. It follows from [8, 11] that for the case (I) we have $T_1 = T$ for each $\Gamma(\cdot) \in \mathbb{G}$ and $W(0) = \bigcup\{\mathcal{P}^-(0) | \Gamma(\cdot) \in \mathbb{G}\}$. But we can not conclude from here that $W^0 = W(0)$. The attractive property of the control strategies (9) is their explicit form.

**Remark 1.** One of the heuristic ways to construct the parameter $\Gamma(\cdot)$ is to apply arguments of a “local” volume optimization similarly to [8] (see also Remark 2 below). Namely, assuming $\det \bar{P}_f > 0$ and introducing a grid $T_N$ of times $\tau_k = kh_N$, $k=0, \dots, N$, $h_N = \theta N^{-1}$, we can construct the piecewise constant function $\Gamma(t) \equiv \Gamma(\tau_k) \in \text{Argmin}_{\Gamma \in \mathcal{G}} \text{tr}(\bar{P}^-(\tau_k)^{-1} \bar{R}(\tau_k) \Gamma)$, $t \in (\tau_{k-1}, \tau_k]$, $k=N, \dots, 1$.

For case (I), we can use, similarly to [11], minimization over $\Gamma$ that satisfy $\Gamma \in \mathcal{G}$ and some constraints introduced to produce tight estimates $\mathcal{P}^-(t)$ for $W(t)$. Solutions of both optimization problems are known in the explicit form [8, 11].

# 4 Solutions to Problem 3

Let us consider the following ODE system for $\mathcal{P}^-(t) = \mathcal{P}[p^-(t), \bar{P}^-(t)]$:

$$ \frac{dp^{-}}{dt} = (A(t) + \tilde{U}(t) + \tilde{V}(t))p^{-} + q(t), \quad p^{-}(\theta) = p_{f}; \quad (10) $$

$$ \begin{aligned} \frac{d\bar{P}^{-}}{dt} = & (A(t)+\tilde{U}(t)+\tilde{V}(t))\bar{P}^{-}\text{-diag } \alpha(t, \bar{P}^{-})\bar{P}^{-}+\bar{P}^{-}\text{diag } (\beta(t, \bar{P}^{-})+\gamma(t, \bar{P}^{-})), \\ & \alpha_i(t, \bar{P}^{-})=\alpha_i(t, \bar{P}^{-}); J(t))=\hat{u}_i^{j_i}(t) \eta_i(t, \bar{P}^{-})(e^{i\top}(\text{Abs } \bar{P}^{-})e)^{-1}, \quad i=1, \dots, n, \\ & \eta(t, \bar{P}^{-}) = \max\{0, \text{Abs } p^{-}(t)-(\text{Abs } \bar{P}^{-})e\}, \\ & \beta(t, \bar{P}^{-}) = \max\{\text{Abs } ((\bar{P}^{-})^{-1})\hat{V}(t)\text{Abs } (p^{-}(t) + \bar{P}^{-}\xi) | \xi \in \mathbb{E}(\mathcal{C})\}, \\ & \gamma(t, \bar{P}^{-}) = \text{Abs } ((\bar{P}^{-})^{-1}\bar{Q}(t))e, \quad \bar{P}^{-}(\theta) = \bar{P}_{f}, \end{aligned} \quad (11) $$

where $\hat{u}_i^{j_i}$ stand for elements of $\hat{U}$. Here $J = \{j_1, \dots, j_n\}$ is an arbitrary permutation of numbers $\{1, \dots, n\}$ or even a measurable vector function with values $J(t)$ being arbitrary permutations. Let $\mathcal{J}$ be the set of all such functions $J(\cdot)$. Let us consider the control strategy connected with $\mathcal{P}^-(\cdot)$ from (10), (11):

$$ e^{i\top} U(t, x) = \begin{cases} e^{i\top} \tilde{U}(t) - \alpha_i(t, \bar{P}^-(t))(x_i - p_i^-(t))(x_{j_i})^{-1} e^{j_i\top} & \text{if } x_{j_i} \neq 0, \\ e^{i\top} \tilde{U}(t) & \text{if } x_{j_i} = 0, \end{cases} \quad i=1, \dots, n. \quad (12) $$
**Theorem 2.** We consider the system (1), (3)-(5), where $\det \bar{P}_f \neq 0$. Let $J(\cdot) \in \mathbb{J}$. Then the system (10), (11) has a unique solution $(p^-(\cdot), \bar{P}^-(\cdot))$ at least on some subinterval $T_1 = [\tau_1, \theta] \subseteq T$, where $0 \le \tau_1 < \theta$. If $T_1 = T$ and we have $\det \bar{P}^-(t) \neq 0$, $t \in T$, then the tube $\mathcal{P}^-(\cdot)$ and the control strategy (12) give a particular solution to Problem 3; in cases (I), (II,i), all solutions $x(\cdot)$ to (6) with $x(0) \in \mathcal{P}^-(0)$ (not only with $x(0) \in \text{int} \mathcal{P}^-(0)$) satisfy $x(t) \in \mathcal{P}^-(t)$, $t \in T$.

*Proof.* Here we give a sketch. First, it can be checked that the strategy (12) acts for $x \in \mathcal{P}^-(t)$ according to the rule $U(t,x) = \tilde{U}(t)x - \text{diag } \alpha(t, \bar{P}^-(t)) \cdot (x - p^-(t))$. Existence and uniqueness of the solution follow from the known results similarly to [8, 10]. Let $x_0 \in \text{int} \mathcal{P}^-(0)$ ($x_0 \in \mathcal{P}^-(0)$ for cases (I) and (II,i)). Let $x(\cdot)$ be the solution of (6) that corresponds to $x(0) = x_0$ (i.e., $x(0) = p^-(0) + \bar{P}^-(0)\zeta_0$, where $\|\zeta_0\|_{\infty} < 1$ (respectively, $\|\zeta_0\|_{\infty} \le 1$)), to the control $U(t,x)$ from (12), and to arbitrary admissible functions $v(\cdot)$ (such that $v(t) = q(t) + \bar{Q}(t)\chi(t)$, $\|\chi(t)\|_{\infty} \le 1$) and $V(\cdot)$ (which satisfies (4)). Let us represent $x(t) - p^-(t)$ in the form $x(t) - p^-(t) = \bar{P}^-(t)\zeta(t)$. Then we have $\frac{d}{dt}\zeta = -(\bar{P}^-)^{-1}(\frac{d}{dt}\bar{P}^-)\zeta + (\bar{P}^-)^{-1}\frac{d}{dt}(x - p^-)$ for the above function $\zeta$. Taking into account (11) and the relation $\frac{d}{dt}(x - p^-) = (A + \tilde{U} + \tilde{V})(x - p^-) - (\text{diag } \alpha)(x - p^-) + (V - \tilde{V})x + v - q$, which follows from (6), (10), (12), it is not difficult to see that $\dot{\zeta} = -(\text{diag } \beta + \text{diag } \gamma)\zeta + (\bar{P}^-)^{-1}((V - \tilde{V})x + v - q)$. Let us denote $b(t) = \beta(t, \bar{P}^-(t)) + \gamma(t, \bar{P}^-(t))$, $c(t, \zeta) = \bar{P}^-(t)^{-1}((V(t) - \tilde{V}(t)) \cdot (p^-(t) + \bar{P}^-(t)\zeta) + \bar{Q}(t)\chi(t))$. Then, using (4), (5), we have

$$ \begin{array}{l} \dot{\zeta}_i = -b_i(t)\zeta_i + c_i(t, \zeta), \quad i = 1, \dots, n, \quad \zeta(0) = \zeta_0; \\ b(t) \ge 0, \quad \text{Abs } c(t, \zeta) \le b(t) \quad \text{for } \zeta \in \mathcal{C} = \mathcal{P}(0, I, e). \end{array} \qquad (13) $$

It is not difficult to check that if $\zeta(\cdot)$ satisfies (13) and $\zeta_0 \in \text{int} \mathcal{C}$, then $\zeta(t) \in \text{int} \mathcal{C}$, $t \in T$; if $\zeta_0 \in \mathcal{C}$ and, in addition, $c(t, \zeta) \equiv c(t)$ (i.e., does not depend on $\zeta$), then $\zeta(t) \in \mathcal{C}$, $t \in T$. Thus we obtain $x(t) \in \mathcal{P}^-(t)$, $t \in T$. Also we have $\text{Abs} (\tilde{U}(t, x) - \tilde{U}(t)) \le \tilde{U}(t)$ for $x \in \mathcal{P}^-(t)$ because for such $x$ we have $|\alpha_i(x_i - p_i^-)(x_{j_i})^{-1}| \le \hat{u}_i^{j_i}$, $i=1, \dots, n$ (this can be obtained by simple estimates). $\square$

**Theorem 2** describes the family of tubes $\mathcal{P}^-(\cdot)$, where $J(\cdot)$ serves as a parameter. Thus the set $W^0 = \bigcup\{\text{int } \mathcal{P}^-(0) | J(\cdot) \in \mathbb{J}$ such that $\det \mathcal{P}^-(t) \neq 0, t \in T\}$ provides the set of $x_0$ that can be steered to $\mathcal{M}$ during the time $\theta$ by solving Problem 3. However it is not true that $\det \mathcal{P}^-(0) \neq 0$ or $\mathcal{P}^-(0) \neq \emptyset$ for each $J(\cdot) \in \mathbb{J}$.

**Remark 2.** One of the ways of constructing $J(\cdot)$ is to apply arguments of a "local" volume optimization similarly to [9, 10]. Namely, assume, without loss of generality, that $\det \bar{P}_f > 0$. Fix a natural number $N$ and introduce a grid $T_N$ of times $\tau_k = kh_N$, $k=0, \dots, N$, $h_N = \theta N^{-1}$. Integrating the system (10), (11) from right to left, let us, for each $\tau \in T_N$, solve the optimization problem which is to maximize $\sum_{i=1}^n \alpha_i(\tau, \bar{P}^-(\tau); J)$ over all possible permutations $J = \{j_1, \dots, j_n\}$. This is equivalent to finding the maximal possible velocity of increasing (from right to left) $\det \bar{P}^-(\tau)$ (therefore $\text{vol} \mathcal{P}^-(\tau)$) at time $\tau$, by the choice of the value $J$, when the value $\bar{P}^-(\tau)$ has already been found. Thus we can sequentially construct the piecewise constant function $J(t) \equiv J(\tau_k) \in \text{Argmax}_J \sum_{i=1}^n \alpha_i(\tau_k, \bar{P}^-(\tau_k); J)$, $t \in (\tau_{k-1}, \tau_k]$, $k = N, \dots, 1$, and find $\bar{P}^-(\cdot)$.
## 5 Control synthesis for discrete-time systems

Now let us briefly consider a problem of control synthesis, similar to Problem 3, for discrete-time systems. This is of independent interest and also may be useful for constructing difference schemes for solving the system (10), (11). The analog of Problem 2 can be considered in a similar way.

Consider the controlled discrete-time system with a given terminal set $\mathcal{M}$:

$$x[k] = (A[k] + U[k] + V[k]) x[k-1] + v[k], \quad k = 1, \dots, N, \\ x[N] \in \mathcal{M} = \mathcal{P}[p_f, \bar{P}_f], \quad \det \bar{P}_f \neq 0, \tag{14}$$

$$U[k] \in \mathcal{U}[k] = \{U | \text{Abs}(U - \tilde{U}[k]) \le \hat{U}[k]\}, \quad V[k] \in \{V | \text{Abs}(V - \tilde{V}[k]) \le \hat{V}[k]\}, \tag{15}$$

$$v[k] \in \mathcal{Q}[k] = \mathcal{P}[q[k], \bar{Q}[k]], \quad k = 1, \dots, N. \tag{16}$$

**Problem 4.** Find a polyhedral tube $\mathcal{P}^-[k] = \mathcal{P}[p^-[k], \bar{P}^-[k]]$, $k=1, \dots, N$, with $\mathcal{P}^-[N] = \mathcal{M}$, and find a corresponding feedback control strategy $U = U[k, x]$ such that $U[k, x] \in \mathcal{U}[k]$ for $x \in \mathcal{P}^-[k-1]$, $k = 1, \dots, N$, and each solution $x[\cdot]$ to the equation $x[k] = (A[k] + U[k, x[k-1]] + V[k]) \cdot x[k-1] + v[k]$, $k = 1, \dots, N$, with $x[0] = x_0 \in \mathcal{P}^-[0]$ would satisfy $x[k] \in \mathcal{P}^-[k]$, $k = 1, \dots, N$, whatever are $V[\cdot]$ and $v[\cdot]$ subjected to (15), (16). Introduce a family of such tubes $\mathcal{P}^-[\cdot]$.

Let us consider the following system of relations for $\mathcal{P}^-[k] = \mathcal{P}[p^-[k], \bar{P}^-[k]]$:

$$p^-[k-1] = B[k]^{-1}(p^-[k] - q[k]), \quad B[k] = A[k] + \tilde{U}[k] + \tilde{V}[k], \quad k=N, \dots, 1, \quad p^-[N] = p_f, \tag{17}$$

$$\bar{P}^-[k-1] = H[k, \bar{P}^-[k-1]], \quad k = N, \dots, 1, \quad \bar{P}^-[N] = \bar{P}_f, \tag{18}$$

$$H[k, P] = (B[k] - \text{diag} \alpha[k, P])^{-1} \bar{P}^-[k] \text{diag} (e - \beta[k, P] - \gamma[k]), \\ \alpha_i[k, P] = \alpha_i[k, P; J[k]] = \hat{u}_i^{j_i}[k] \eta_{j_i}[k, P] (e^{i\top}(\text{Abs} P) e)^{-1}, \quad i=1, \dots, n, \\ \eta[k, P] = \max\{0, \text{Abs } p^-[k-1] - (\text{Abs } P)e\}, \tag{19}$$

$$\beta[k, P] = \max\{\text{Abs}(\bar{P}^-[k])^{-1} \hat{V}[k] \text{Abs}(p^-[k-1] + P\xi) \mid \xi \in \mathbb{E}(\mathcal{C})\}, \\ \gamma[k] = (\text{Abs}(\bar{P}^-[k])^{-1}\bar{Q}[k])\text{e}, \quad k = N, \dots, 1.$$

Note that (17) is the system of explicit recurrent relations while (18)-(19) is the system of implicit ones, i.e., for any time step $k \in \{N, \dots, 1\}$, we need to solve the system of nonlinear equations with respect to the unknown matrix $P=P^-[k-1]$.

**Theorem 3.** In the system (14)-(16), let $\det \bar{P}_f \ne 0$ and all $\det B[k] \ne 0$. Let $J[k] = \{j_1[k], \dots, j_n[k]\}$ be arbitrary permutations of numbers $\{1, \dots, n\}$, $k=N, \dots, 1$, and the system (17)-(19) has a solution $(p^-[\cdot], \bar{P}^-[\cdot])$ such that we obtain $\det \bar{P}^-[k] \ne 0$ and $e - \beta[k, \bar{P}^-[k-1]] - \gamma[k] > 0$, $k = N, \dots, 1$. Then the tube $\mathcal{P}^-[\cdot]$ and the control strategy which acts according to the following rule

$$U[k, x] x = \tilde{U}[k] x - \text{diag} \alpha[k, \bar{P}^-[k-1]; J[k]](x - p^-[k-1]), \quad k = 1, \dots, N, \tag{20}$$

(a formula similar to (12) is true), gives a particular solution to Problem 4.
*Proof.* We give a sketch following the scheme of the proof of Theorem 2 and keeping the similar notation. Let $x[\cdot]$ corresponds to $x[0] = x_0 \in \mathcal{P}^{-}[0]$, i.e., $x[0] = p^{-}[0] + \bar{P}^{-}[0]\zeta_0$, where $\|\zeta_0\|_{\infty} \le 1$. Let us represent $x[k]$ in the form $x[k] = p^{-}[k] + \bar{P}^{-}[k]\zeta[k]$, $k = 0, \dots, N$. The proof is by induction on the time step $k$. Let we already have $x[k-1] \in \mathcal{P}^{-}[k-1]$. Then it follows from (14), (17) that

$$x[k]=p^{-}[k]+B[k]\bar{P}^{-}[k-1]\zeta[k-1]+(U[k,x[k-1]]-\tilde{U}[k]+\Delta V[k])x[k-1]+v[k]-q[k],$$
where $\Delta V[k] = V[k] - \tilde{V}[k]$. Taking into account (20), we obtain

$$\zeta[k] = \bar{P}^{-}[k]^{-1}(B[k] - \operatorname{diag}\alpha[k, \bar{P}^{-}[k-1]])\bar{P}^{-}[k-1]\zeta[k-1] + c[k, x[k-1]],$$
$$c[k, x]=\bar{P}^{-}[k]^{-1}\Delta V[k] x+\bar{P}^{-}[k]^{-1}\bar{Q}[k]\chi[k].$$
Using (18), (19), (15), (16), we have

$$\zeta[k] = \operatorname{diag}(e - \beta[k, \bar{P}^{-}[k-1]] - \gamma[k])\zeta[k-1] + c[k, x[k-1]];$$
$$\operatorname{Abs} c[k, x] \le \beta[k, \bar{P}^{-}[k-1]] + \gamma[k] \quad \text{for } x \in \mathcal{P}^{-}[k-1].$$

It is not difficult to see that if $\|\zeta[k-1]\|_{\infty} \le 1$ and $e - \beta[k, \bar{P}^{-}[k-1]] - \gamma[k] \ge 0$, then $\|\zeta[k]\|_{\infty} \le 1$. Thus we obtain the desired inclusion $x[k] \in \mathcal{P}^{-}[k]$. Also it is not difficult to see that $\operatorname{Abs}(U[k, x] - \tilde{U}[k]) \le \hat{U}[k]$ for $x \in \mathcal{P}^{-}[k-1]$. $\square$

*Remark 3.* Let the system (14)-(16) be obtained by the Euler approximations of (1), (3)-(5) with the same $\mathcal{M}$, $A[k]=I+h_N A(t_{k-1})$, $\tilde{U}[k]=h_N \tilde{U}(t_{k-1})$, $\hat{U}[k] = h_N \hat{U}(t_{k-1})$, $\tilde{V}[k]=h_N \tilde{V}(t_{k-1})$, $\hat{V}[k]=h_N \hat{V}(t_{k-1})$, $Q[k]=h_N Q(t_{k-1})$, $t_k = kh_N$, $h_N = \theta N^{-1}$. Let, for a fixed $k$, $\det \bar{P}^{-}[k] \ne 0$ and the time step $h_N$ be sufficient small. Then the operator $H[k, P]$ is contractive in some domain $\mathcal{D}[k] = \{P \mid \|P - \bar{P}^{-}[k]\| \le \delta[k]\}$, i.e., $\|H[k, P^1] - H[k, P^2]\| \le L \|P^1 - P^2\|$ for any $P^1, P^2 \in \mathcal{D}[k]$, where $L=L[k] \in (0, 1)$, and therefore [3, p.319] the equation $P = H[k, P]$ from (18), (19) has a solution $P=\bar{P}^{-}[k-1]$, which can be found by the simple iteration $P^{l+1}=H[k, P^l]$, $l=0, 1, \dots$, starting from $P^0=\bar{P}^{-}[k]$, and we have $\|P^l - P\| \le L^l(1-L)^{-1}\|P^1-P^0\|$. Also, the relation $\gamma[k] + \beta[k, \bar{P}^{-}[k-1]] < e$ is satisfied. But certainly we can not derive from here the existence of nonsingular matrices $\bar{P}^{-}[k]$ for all $k = N, \dots, 1$ because the value of such “small” $h_N$ depends on $k$.

# 6 Examples

We consider model examples for Problem 3. For computations we use the Euler approximations (see Remark 3) with $N=200$. Let $\mathcal{M} = \mathcal{P}((1, 1)^{\top}, I, (0.1, 0.1)^{\top})$, $A(t) \equiv \begin{bmatrix} -0.5 & 0 \\ 0 & -0.5 \end{bmatrix}$, $\tilde{U}(t) \equiv \begin{bmatrix} 0 & 2 \\ 0 & 0 \end{bmatrix}$, $\hat{U}(t) \equiv \begin{bmatrix} 0 & 1.5 \\ 0 & 0 \end{bmatrix}$, $\tilde{V}(t) \equiv \begin{bmatrix} 0 & 0 \\ 2 & 0 \end{bmatrix}$, $\hat{V}(t) \equiv \begin{bmatrix} 0 & 0 \\ 0.2 & 0 \end{bmatrix}$ or $\hat{V}(t) \equiv 0$, $Q(t) \equiv \mathcal{P}(0, I, 0)$ or $Q(t) \equiv \mathcal{P}(0, I, (0.05, 0.05)^{\top})$, $\theta=0.25$. We consider 3 cases: (I), (II,ii), and (II,iii). The results are presented in Fig. 1. In the second example, we put the realization $V(t) \equiv \tilde{V}(t) + \hat{V}(t)$; in the third one we presume $V(\cdot)$ to be the same and $v(\cdot)$ to be some extremal bang-bang type disturbance [17, p.234], where the length of intervals of constancy of $v(t)$ is equal to $\theta/4$.

All the presented trajectories reach the target set $\mathcal{M}$ including the one with a small violation of the inclusion $x_0 \in \mathcal{P}^{-}[0]$, though if $x_0 \notin \mathcal{P}^{-}[0]$, then there is not guarantee that the trajectory can be steered into the target set $\mathcal{M}$ by using the control strategy (12) under any disturbances.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Examples of polyhedral control synthesis for Problem 3 ($n = 2$). (a) Case (I): the set $\mathcal{M}$ (dash line), two parallelotopes $P^{-}[0]$ and the controlled trajectory for $x_0 = (0.5, 0.8)^{\top}$. (b) Case (I): the tube $P^{-}[\cdot]$ and the controlled trajectory. (c) Case (II,ii): $\mathcal{M}, P^{-}[0]$ corresponding to $J[\cdot]$ from Remark 2, and the controlled trajectory for $x_0 = (0.5, 0.8)^{\top}$. (d) Case (II,iii): $\mathcal{M}, P^{-}[0]$ corresponding to $J[\cdot]$ from Remark 2, and controlled trajectories for two initial points $x_0 = (0.5, 0.8)^{\top}$ and $x_0 = (1, 0.6)^{\top}$.</figcaption></figure>

References

1. Anan'evskii, I.M., Anokhin, N.V., Ovseevich, A.I.: Synthesis of a Bounded Control for Linear Dynamical Systems Using the General Lyapunov Function. Dokl. Math. 82 (2), 831-834 (2010)

2. Baier, R., Lempio, F.: Computing Aumanns Integral. In: Kurzhanski, A.B., Veliov, V.M. (eds.) Modeling Techniques for Uncertain Systems (Sopron, 1992). Progr. Systems Control Theory, vol. 18, pp. 71–92. Birkhäuser, Boston (1994)

3. Bakhvalov, N. S., Zhidkov, N. P., Kobel'kov, G. M.: Numerical methods. (Russian). Nauka, Moscow (1987)

4. Chernousko, F.L.: State Estimation for Dynamic Systems. CRS Press, Boca Raton (1994)

5. Filippova, T.F.: Trajectory Tubes of Nonlinear Differential Inclusions and State Estimation Problems. J. Concr. Appl. Math. 8 (3), 454–469 (2010)

6. Filippova, T.F., Lisin, D.V.: On the Estimation of Trajectory Tubes of Differential Inclusions. Proc. Steklov Inst. Math. Suppl. 2, S28–S37 (2000)

7. Gusev, M.I.: External Estimates of the Reachability Sets of Nonlinear Controlled Systems. Autom. Remote Control 73 (3), 450–461 (2012)
8. Kostousova, E.K.: Control Synthesis via Parallelotopes: Optimization and Parallel Computations. Optim. Methods Softw. 14 (4), 267–310 (2001)

9. Kostousova, E.K.: State Estimation for Control Systems with a Multiplicative Uncertainty through Polyhedral Techniques. In: System Modeling and Optimization, 25th IFIP TC 7 Conference, Berlin, Germany, September 12-16, 2011. IFIP AICT, vol. 391, pp.165–176. Springer, Heidelberg (2013)

10. Kostousova, E.K.: On Polyhedral Estimates for Reachable Sets of Differential Systems with Bilinear Uncertainty. (Russian). Trudy Instituta Matematiki i Mekhaniki UrO RAN 18 (4), 195–210 (2012)

11. Kostousova, E.K.: On Tight Polyhedral Estimates for Reachable Sets of Linear Differential Systems. In: 9th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences: ICNPAA 2012, Vienna, Austria, July 10-14, 2012. AIP Conf. Proc. 1493 (2012); doi: http://dx.doi.org/10.1063/1.4765545.

12. Kostousova, E.K., Kurzhanski, A.B.: Guaranteed Estimates of Accuracy of Computations in Problems of Control and Estimation. (Russian). Vychisl. Tekhnol. 2 (1), 19–27 (1997)

13. Krasovskii, N.N., Subbotin, A.I.: Positional Differential Games. (Russian). Nauka, Moscow (1974)

14. Kuntsevich, V.M., Kurzhanski, A.B.: Calculation and Control of Attainability Sets for Linear and Certain Classes of Nonlinear Discrete Systems. J. Automation and Inform. Sci. 42 (1), 1–18 (2010)

15. Kurzhanskii, A. B., Mel'nikov, N. B.: On the Problem of the Synthesis of Controls: the Pontryagin Alternative Integral and the Hamilton-Jacobi Equation. Sb. Math. 191 (5-6), 849–881 (2000)

16. Kurzhanski, A.B., Nikonov, O.I.: On the Problem of Synthesizing Control Strategies. Evolution Equations and Set-Valued Integration. Soviet Math. Doklady 41 (2), 300–305 (1990)

17. Kurzhanski, A.B., Vályi, I.: Ellipsoidal Calculus for Estimation and Control. Birkhäuser, Boston (1997)

18. Kurzhanski, A.B., Varaiya, P.: On Ellipsoidal Techniques for Reachability Analysis. Part I: External Approximations. Part II: Internal Approximations. Box-valued Constraints. Optim. Methods Softw. 17 (2), 177–237 (2002)

19. Mazurenko, S.S.: A Differential Equation for the Gauge Function of the Star-Shaped Attainability Set of a Differential Inclusion. Doklady Mathematics 86 (1), 476–479 (2012)

20. Polyak, B.T., Scherbakov, P.S.: Robust Stability and Control. (Russian). Nauka, Moscow (2002)

21. Taras'yev, A.M., Uspenskiy, A.A., Ushakov, V.N.: Approximation Schemas and Finite-Difference Operators for Constructing Generalized Solutions of Hamilton-Jacobi Equations. J. Comput. Systems Sci. Internat. 33 (6), 127–139 (1995)

22. Veliov, V.M.: Second Order Discrete Approximations to Strongly Convex Differential Inclusions. Systems & Control Letters 13 (3), 263–269 (1989)