Abstract
Linear controlled objects are intensively studied in modern control theory. An important dynamic characteristic of such objects is their reachable sets. For example, these sets are used in optimal control theory to formulate problems that are interesting for applications. Knowing reachable sets at different times, one can roughly estimate the dynamic capabilities of the controlled object under study. Note that, in the absence of state constraints, the technique of support functions is effective for calculating these sets. Under state constraints, the calculation becomes more complicated. We develop a method for the approximate calculation of reachable sets for linear controlled objects under constraints. The convergence of these approximations to the desired reachable set in the sense of the Hausdorff metric is proved. It is assumed that the state constraint and the set constraining the control are convex and compact. To construct approximations, we use the Cauchy formula and a uniform partition of the interval \([0,T]\) on which the motion occurs. An estimate for the rate of convergence of approximations to the required set is obtained under some additional assumptions.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1. INTRODUCTION
Controlled processes under state constraints are important objects of study in the mathematical theory of optimal control (see, e.g., [1, 2, 3, 4] et al.). The presence of state constraints essentially complicates the investigation of the corresponding optimization problems. Note that an important characteristic of a control process is its reachable sets (see, e.g., [3, 4]). For linear controlled objects in the absence of state constraints, a theory was developed which gives an efficient calculation of reachable sets based on techniques of support functions (see, e.g., [4]). For linear controlled objects under state constraints, the constructive calculation of reachable sets is rather difficult.
This paper is devoted to the approximate calculation of reachable sets for linear controlled objects in the presence of a convex state constraint and a compact set \(P\) bounding the vector control \(u\).
2. THE MAIN PART
Consider a linear controlled object of the form (see [1, 2, 3, 4])
where \(x\in\mathbb{R}^{n}\) (\(n\geq 1\)); \(u\in\mathbb{R}^{p}\) (\(p\geq 1\)); \(A\) and \(B\) are \(n\times n\) and \(n\times p\) matrices, respectively; and the control \(u\in P\) is a convex compact set in \(\mathbb{R}^{p}\). For \(k\geq 1\), we denote by \(\mathbb{R}^{k}\) the Euclidean arithmetic space whose elements are ordered tuples of \(k\) numbers written as columns. The scalar product \(\langle x,y\rangle\) of vectors \(x\), \(y\) from \(\mathbb{R}^{k}\) and the length \(|x|\) of a vector \(x\in\mathbb{R}^{k}\) are introduced in the standard way.
For the controlled object (1), we fix a state constraint \(G\subset\mathbb{R}^{n}\), where \(G\) is a nonempty convex compact set; an initial condition \(x(0)=x_{0}\in G\); and a time \(T>0\). We consider all possible Lebesgue measurable functions \(u(t)\in P\), \(t\in\Delta=[0,T]\), called admissible controls. Denote by \(U\) the set of such functions. For each admissible control \(u(\cdot)\) and initial condition \(x(0)=x_{0}\), there is an absolutely continuous solution \(x(t,u(\cdot),x_{0})\), \(t\in\Delta\), of equation (1). We are interested in the controls \(u(\cdot)\in U\) for which \(x(t,u(\cdot),x_{0})\in G\) for all \(t\in\Delta\); denote the set of such controls by \(W\). In the general case, the set \(W\) can be empty. In what follows, we assume that \(W\neq\varnothing\). For the controlled object under consideration, we define the reachable set \(D(T,x_{0})\) by the formula
Recall that, for \(u(\cdot)\in U\) and the corresponding solution \(x(t)=x(t,u(\cdot),x_{0})\), \(t\in\Delta\), we have the Cauchy formula
where \(e^{tA}\) is the exponential of the matrix \(tA\), and the integral is understood in the Lebesgue sense. Using this formula and the convexity of the sets \(P\) and \(G\), one can easily prove the convexity of \(D(T,x_{0})\) (see (2)). Using the weak compactness of the set \(U\) in the Hilbert space \(L_{2}^{p}[0,T]\) (see [2]), the closedness of the set \(G\), and formula (3), we can prove that the reachable set \(D(T,x_{0})\) is convex and compact. We will study the problem of approximate (in the sense of the Hausdorff metric) calculation of the set \(D(T,x_{0})\).
Divide the interval \(\Delta\) into \(N\) equal parts (\(N\geq 1\)) by the points
where \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\) and \(h=T/N\). Define
where \(h>0\), \(K\) is an arbitrary nonempty compact set from \(\mathbb{R}^{n}\), \(U_{h}\) is the set of measurable functions \(u(t)\in P\) for \(t\in[0,h]\), and \(x(t,u(\cdot),y)\) is the solution of equation (1) corresponding to the control \(u(\cdot)\in U_{h}\) and the initial condition \(x(0)=y\). For the set \(E(h,K)\) (see (4)), using formula (3), we can prove the formula
where “+” means the algebraic addition of sets, and the integral of the set-valued mapping \(e^{rA}BP\) over \([0,h]\) is understood in the sense of the theory of set-valued mappings (see [4]). Note that if the compact set \(K\) is convex, then \(E(h,K)\) (see (5)) is also a convex compact set. In what follows, we will need the following chain of sets \(F_{i}\):
where \(h=T/N\) and \(i=0,\mathinner{\ldotp\ldotp\ldotp},N-1\). Using the Cauchy formula (3), we can show that, under the above assumptions, all the sets \(F_{i}\), \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\), are nonempty, convex, and compact. We are interested in the set \(F_{N}\) as a certain approximation of the set \(D(T,x_{0})\) as \(N\to+\infty\).
Consider an arbitrary control \(\tilde{u}(\cdot)\in W\). Then the solution \(\tilde{x}(t)=x(t,\tilde{u}(\cdot),x_{0})\) for \(t\in\Delta\) satisfies the inclusion
Using the Cauchy formula (3), we can show that
for \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\); in particular, \(\tilde{x}(T)\in F_{N}\). The definition of the set \(D(T,x_{0})\) (see (2)) and the inclusion \(\tilde{x}(T)\in F_{N}\) imply that
In what follows, we will use the following definitions.
Definition 1
Let \(X\) and \(Y\) be nonempty compact sets from \(\mathbb{R}^{n}\). The Hausdorff distance \(h(X,Y)\) is defined as the smallest nonnegative number \(\varepsilon\) for which
where \(S_{\varepsilon}=\{x\in\mathbb{R}^{n}:|x|\leq\varepsilon\}\). \(\square\)
Definition 2
The support function \(c(X,\psi)\) of a nonempty compact set \(X\subset\mathbb{R}^{n}\) is defined for \(\psi\in\mathbb{R}^{n}\) by the formula
Note that the properties of support functions were discussed in detail in [4]. \(\square\)
The aim of this study is to prove the convergence of the convex compact sets \(F_{N}\) to the convex compact set \(D(T,x_{0})\) as \(N\to+\infty\) in the Hausdorff metric and to derive some upper estimate for this convergence under an additional assumption concerning the controlled object (1), vector \(x_{0}\), and the set \(G\).
Denote by \(U_{N}\) the set of \(\hat{u}(\cdot)\in U\) such that
where \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\). Note that formulas (6) for \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\) and the inclusion \(\hat{u}(\cdot)\in U_{N}\) imply the relations
for \(i=0,\mathinner{\ldotp\ldotp\ldotp},N\). Using formulas (3)–(6), we can prove that
Using the compactness of the set \(G\) and formulas (3) and (9), we can prove that, for \(t\in\Delta\) and arbitrary \(\hat{u}(\cdot)\in U_{N}\), the following inequality holds:
where \(h=T/N\), the constant \(c\) is nonnegative and independent of \(N\), and the value \(\rho(y,G)\) for \(y\in\mathbb{R}^{n}\) is defined by the formula
From relation (11), for \(t\in\Delta\), we get the inclusion
where “+” means the algebraic addition of sets,
Note that
Theorem 1
The sequence of convex compact sets \(F_{N}\) (see (6), (10)) converges to the convex compact set \(D(T,x_{0})\) as \(N\to+\infty\) in the sense of the Hausdorff metric.
Proof
Fix some positive \(\varepsilon\). In view of relations (7), (8), it is sufficient to prove that
for large \(N\). Assume that this is not so. Then there exists a subsequence \(N_{k}\to+\infty\) such that
Hence, for some sequence of controls \(\hat{u}_{N_{k}}\in U_{N_{k}}\), we have
Let us now use the weak compactness of the set \(U\) in the Hilbert space \(L_{2}^{p}[0,T]\) (see [2]). Passing, if necessary, to a subsequence with the corresponding reindexing, we can assume that the sequence \(\hat{u}_{N_{k}}(\cdot)\) weakly converges as \(N_{k}\to+\infty\) in the sense of the Hilbert space \(L_{2}^{p}[0,T]\) to some control \(u_{0}(\cdot)\), which belongs to the set \(U\) and, at the same time, the sequence of functions \(x(t,\hat{u}_{N_{k}}(\cdot),x_{0})\) converges uniformly on the interval \([0,T]\) to the function \(x(t,u_{0}(\cdot),x_{0})\). Using (11), we can show that \(x(T,u_{0}(\cdot),x_{0})\in D(T,x_{0})\). However, this inclusion, according to the above, contradicts (12). We have come to a contradiction with our assumption.
The theorem is proved. \(\square\)
For applications, it is useful to have an estimate for the convergence rate of the sequence \(F_{N}\), \(N=1,2,\mathinner{\ldotp\ldotp\ldotp}\), to \(D(T,x_{0})\) in the Hausdorff metric. Such an estimate can be derived under the following assumption.
Assumption
There exist a control \(\overline{u}(\cdot)\in W\) and a constant \(\alpha>0\) such that
Theorem 2
Under the above assumption, the Hausdorff distance between the convex compact sets \(F_{N}\) and \(D(T,x_{0})\) can be estimated from above by the value \(c_{1}/N\) as \(N\to+\infty,\) where \(c_{1}\) is some positive constant.
Proof
In view of (7) and (8), it is sufficient to prove that
for \(N\geq 1\), where \(c_{2}\) is some nonnegative constant independent of \(N\). Then we can take the constant \(c_{2}\) as \(c_{1}\). Fix \(N\geq 1\) and consider some control \(\hat{u}(\cdot)\) from the set \(U_{N}\). This control corresponds to a solution \(\hat{x}(t)=x(t,\hat{u}(\cdot),x_{0})\), and the control \(\overline{u}(\cdot)\) corresponds to a solution \(\overline{x}(t)=x(t,\overline{u}(\cdot),x_{0})\). Let us also consider the control
on \(\Delta\), where \(\beta\in[0,1]\). It follows from the convexity of the set \(P\) that \(u_{\beta}(\cdot)\in U\). The control \(u_{\beta}(t)\) corresponds to a solution \(x_{\beta}(t)=x_{\beta}(t,x_{0})\) and, by the Cauchy formula (see (3)), we have
for \(t\in\Delta\). Since the control \(\hat{u}(\cdot)\) belongs to the set \(U_{N}\), we have inequality (11) for \(t\in\Delta\). Let us add algebraically the ball \(\beta S_{\alpha}\) to both sides of (14). In view of the assumption and relation (11), we obtain for \(t\in\Delta\) the inclusion
Since \(\beta G+(1-\beta)G=G\), it follows from (15) that
for \(t\in\Delta\) and \(h=T/N\). Using the techniques of support functions (see [4]), from inclusion (16) we obtain the inequality
for \(t\in\Delta\), where \(\psi\) is an arbitrary vector from \(\mathbb{R}^{n}\).
The number \(\beta\in[0,1]\) has been arbitrary so far. Let us consider the following equation with respect to \(\beta\):
Its solution is
Note that \(\beta_{h}\in[0,1]\). From relations (14)–(18),we get
for \(t\in\Delta\) and \(\psi\in\mathbb{R}^{n}\). Hence, using the convexity of the compact set \(G\) and the properties of support functions (see [4]), we find that
From formula (14), we derive the following relation:
Using the Cauchy formula (3), it is easy to prove the inequality
for arbitrary \(u(\cdot)\in U\), where \(c_{3}\) is some positive constant, which can be computed constructively. Using inequality (21), we derive from (20) the important inequality
Note that, since the choice of the control \(\hat{u}(\cdot)\in U_{N}\) was arbitrary, the vectors \(\hat{x}(T)\) in (22) fill the entire set \(F_{N}\). Hence, in view of relations (11), (18), and (19) and the equality \(h=T/N\), we obtain
Now, setting \(c_{2}=2cc_{3}T/\alpha\), we obtain the required inclusion for \(N\geq 1\).
The theorem is proved. \(\square\)
Remark
Note that a control of the form (13) was used earlier in [2, pp. 927–930] in the proof of Theorem 1, which is devoted to a numerical method of approximate solution of linear control problems with a terminal functional in the presence of a state constraint.
REFERENCES
L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze, and E. F. Mishchenko, The Mathematical Theory of Optimal Processes (Nauka, Moscow, 1976; Gordon and Breach, New York, 1986).
F. P. Vasil’ev, Optimization Methods (MTsNMO, Moscow, 2011), Vol. 2 [in Russian].
E. B. Lee and L. Markus, Foundations of Optimal Control Theory (Wiley, New York, 1967; Nauka, Moscow, 1972).
V. I. Blagodatskikh, Introduction to Optimal Control (Vysshaya Shkola, Moscow, 2001) [in Russian].
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
The author declares that he has no conflicts of interest.
Additional information
Translated from Trudy Instituta Matematiki i Mekhaniki UrO RAN, Vol. 27, No. 2, pp. 162 - 168, 2021 https://doi.org/10.21538/0134-4889-2021-27-2-162-168.
Translated by E. Vasil’eva
Rights and permissions
About this article
Cite this article
Nikol’skii, M.S. Linear Controlled Objects with State Constraints. Approximate Calculation of Reachable Sets. Proc. Steklov Inst. Math. 315 (Suppl 1), S219–S224 (2021). https://doi.org/10.1134/S0081543821060171
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0081543821060171