Abstract Generated abstract
The paper addresses the time-optimal control of a linear dynamical system whose control values lie in a closed bounded convex polyhedron, under a general-position condition previously used in Pontryagin-type optimal control results. It recalls that optimal controls are extremal and then gives a constructive method for modeling the extremal trajectory determined by a chosen initial adjoint vector, using a pair of linear systems corresponding to the state and adjoint equations together with relay elements that select the maximizing vertex of the control polyhedron. The construction yields a circuit realizing the motion along an extremal trajectory for arbitrary initial state and adjoint data, while leaving the search for the adjoint initial value leading to the target as a separate problem. A simplified relay scheme is also derived for the common case in which the admissible control set is a parallelepiped.
Full Text
MATHEMATICS
V. G. BOLTYANSKII
MODELING LINEAR OPTIMAL TIME-RESPONSES BY MEANS OF RELAY CIRCUITS
(Presented by Academician L. S. Pontryagin on 11 III 1961)
We shall consider an object whose law of motion in the phase space \(X\) of variables \(x^1,\ldots,x^n\) has the form
\[ \dot{x}^i=\sum_{\alpha=1}^{n} a_\alpha^i x^\alpha+\sum_{\rho=1}^{r} b_\rho^i u^\rho,\qquad i=1,\ldots,n. \tag{1} \]
We shall assume that the control parameter \(u=(u^1,\ldots,u^r)\) is a point of a convex closed bounded polyhedron \(U\), situated in the space \(E^r\) with coordinates \(u^1,\ldots,u^r\). We shall consider the problem of optimal time-response, i.e., of finding a control \(u(t)\) with values in \(U\), under whose action the object (1) passes in the shortest time from the position \(x_0\) to \(x_1\) (\(x_0\) and \(x_1\) are given). This problem was considered by L. S. Pontryagin, R. V. Gamkrelidze, and the author \((^{1-5})\); let us recall the results of these works.
In vector form the system (1) takes the form
\[ \dot{x}=Ax+Bu, \tag{2} \]
where \(A:X\to X\) and \(B:E^r\to X\) are linear operators defined, in the coordinates \(x^1,\ldots,x^n\) and \(u^1,\ldots,u^r\), by the matrices \((a_j^i)\) and \((b_k^i)\), respectively.
Everywhere in what follows it is assumed that the following general-position condition is fulfilled: if \(w\) is a vector parallel to one of the edges of the polyhedron \(U\), then the vectors \(Bw, ABw,\ldots,A^{n-1}Bw\) are linearly independent in the space \(X\) (see condition A in \((^4)\)).
Let us introduce the auxiliary system
\[ \dot{\psi}_i=-\sum_{\alpha=1}^{n} a_i^\alpha \psi_\alpha,\qquad i=1,\ldots,n, \]
or, in vector form,
\[ \dot{\psi}=-A^*\psi, \tag{3} \]
where \(A^*\) is the operator adjoint to \(A\), i.e., defined by the matrix obtained from the matrix \((a_j^i)\) by transposition.
Finally, for an arbitrary vector \(\psi=(\psi_1,\ldots,\psi_n)\) denote by \(e(\psi)\) the set of all those points \(u\in U\) for which the scalar product
\[ (\psi,Bu)=\sum_{\alpha=1}^{n}\sum_{\rho=1}^{r}\psi_\alpha b_\rho^\alpha u^\rho, \tag{4} \]
considered as a function of the point \(u\in U\), attains its greatest value.
Theorem 1. Whatever the nontrivial solution \(\psi(t)\) of equation (3), for all but a finite number of values of \(t\) the set \(e(\psi(t))\) repre-
constitutes one vertex of the polyhedron \(U\). Thus, the relation
\[ u(t)=e(\psi(t)) \tag{5} \]
(which loses meaning at a finite number of points, which is immaterial) defines a piecewise-constant function \(u(t)\) with values at the vertices of the polyhedron \(U\). Functions of this kind are called extremal controls.
Theorem 2. Every optimal control is extremal. Conversely, suppose that the origin of the coordinate space \(E^r\) is an interior point of the polyhedron \(U\), and that all eigenvalues of the matrix \((a_i^j)\) have negative real parts. Then for every point \(x_0\in X\) there exists, and moreover only one (up to a shift of time), extremal control \(u(t)\) that transfers the phase point from the position \(x_0\) to the origin \(O\) of the space \(X\). This extremal control is at the same time optimal.
By virtue of Theorem 1, every extremal trajectory issuing at the instant \(t_0\) from the point \(x_0\) is determined by the initial value \(\psi(t_0)\) of the solution \(\psi(t)\) of equation (3). Namely, if an arbitrary nonzero vector \(\psi_0\) is given, then the solution \(\psi(t)\) of equation (3) with initial condition \(\psi(t_0)=\psi_0\) is uniquely determined. After this, relation (5) uniquely determines the corresponding extremal control \(u(t)\). Finally, knowing the control \(u(t)\), from equation (2) we find the corresponding trajectory \(x(t)\) issuing from the point \(x_0\). Thus, ultimately the extremal trajectory \(x(t)\) is uniquely determined by the choice of the initial value \(\psi_0\). If we have managed to find precisely such an initial value \(\psi_0\) that the trajectory \(x(t)\) passes through the origin \(O\), then, by Theorem 2, the optimal control \(u(t)\) and the optimal trajectory \(x(t)\) have been found.
It should be noted that computing the trajectory \(x(t)\) corresponding to the initial value \(\psi_0\) is rather laborious. Indeed, this problem includes solving equation (3), finding the function \(u(t)\) by formula (5), and, finally, solving equation (2), which reduces to solving several systems of differential equations with successive “matching” of initial values (for the function \(u(t)\), generally speaking, is not constant, but only piecewise constant).
If one assumes that the determination of the trajectory \(x(t)\) from the initial value \(\psi_0\) is carried out by some device, then there remains the problem of finding the initial value \(\psi_0\) for which the trajectory \(x(t)\) passes through \(O\).
In the present note, without touching upon the second problem (the problem of finding the initial values \(\psi_0\)), we shall indicate a method for constructing a modeling device which, from the initial value \(\psi_0\), makes it possible to find the corresponding extremal trajectory \(x(t)\). It consists of two linear objects with equations (2) and (3), and of a certain number of relay elements, the number and connection scheme of which are determined by the polyhedron \(U\) and the operator \(B\).
Fig. 1
Let us pass to the mathematical description of the indicated modeling device (Fig. 1). Consider a linear object whose phase states are described by the variables \(\psi_1,\ldots,\psi_n\), varying according to law (3) (section \(AB\) of the circuit shown in Fig. 1). Let, further,
\[ w_1, w_2, \ldots, w_\gamma \tag{6} \]
be pairwise noncollinear vectors having the directions of the edges of the polyhedron \(U\) (i.e., each of the vectors (6) is parallel to at least one edge of the polyhedron \(U\), and for each edge there is in the system (6) one vector parallel to it). Denote the coordinates of the vector \(w_j\) by \(w_j^1,\ldots,w_j^r\), and set
\[ \xi_j = (\psi, Bw_j) = \sum_{\alpha=1}^{n} \sum_{\rho=1}^{r} \psi_\alpha b_\rho^\alpha w_j^\rho, \qquad j = 1, 2, \ldots, \gamma . \tag{7} \]
The variables \(\xi_1,\ldots,\xi_\gamma\) are linear forms (generally speaking, linearly dependent) of \(\psi_1,\ldots,\psi_n\). The values of the quantities \(\xi_j\) are determined by the quantities \(\psi_i\), but they exert no inverse action on them (this is expressed on the section \(BB\) by the directions of the arrows).
We shall feed each of the quantities \(\xi_j\) to its own relay element; denote the outputs of these relay elements by \(\eta_1,\ldots,\eta_\gamma\) (i.e., \(\eta_j=\operatorname{sign}\xi_j\); see the section \(B\Gamma\) in Fig. 1).
Let now \(e_1,\ldots,e_q\) be all the vertices of the polyhedron \(U\). Put \(\varepsilon_{ij}=1\) or \(\varepsilon_{ij}=-1\), if the vector issuing from the vertex \(e_i\), equal to \(w_j\) or, respectively, \(-w_j\), goes along one of the edges of the polyhedron \(U\). If, however, the vector \(w_j\) is not parallel to any edge incident with the vertex \(e_i\), then the number \(\varepsilon_{ij}\) is not defined. Fix some index \(i=(1,2,\ldots,q)\) and consider only those indices \(j\) for which the number \(\varepsilon_{ij}\) is defined. Then the vectors \(\varepsilon_{ij}w_j\) are directed along the edges issuing from the vertex \(e_i\); denote the number of these edges by \(l_i\). It is easy to see that the function (4) then and only then assumes its greatest value at one vertex \(e_i\) (i.e., \(e(\psi)=e_i\)) when all the quantities \(\varepsilon_{ij}\xi_j\) are negative, i.e., \(\varepsilon_{ij}\eta_j=-1\). In other words, the equality \(e(\psi)=e_i\) holds if and only if the quantity
\[ \zeta_i = l_i - 1 + \sum_j \varepsilon_{ij}\eta_j \tag{8} \]
is negative. The quantities \(\zeta_1,\ldots,\zeta_q\) are linear functions of the variables \(\eta_j\) (section \(\Gamma D\)). Feeding the quantities \(\zeta_1,\ldots,\zeta_q\) to relay elements and denoting the output quantities by \(\chi_1,\ldots,\chi_q\) (section \(DE\)), we find that the equality \(e(\psi)=e_i\) holds if and only if \(\chi_i=-1\).
Let now \(e_i^1,\ldots,e_i^r\) be the coordinates of the vertex \(e_i\) of the polyhedron \(U\). Put
\[ u^\rho = \frac{1}{2}\sum_{\alpha=1}^{q}(1-\chi_\alpha)e_\alpha^\rho, \qquad \rho = 1,\ldots,r \tag{9} \]
(section \(EЖ\) in Fig. 1). If \(e(\psi)=e_i\) (i.e., \(\chi_\alpha=1\) for \(\alpha\ne i\) and \(\chi_i=-1\)), then the point \((u^1,\ldots,u^r)\) coincides with \(e_i\) (see (9)). In other words, if the function (4) attains its maximum at only one vertex of the polyhedron \(U\), then
\[ (u^1,\ldots,u^r)=e(\psi). \tag{10} \]
Finally, the section \(ЖЗ\) of the circuit in Fig. 1 represents an object whose behavior is described by equation (2) (i.e., the original object or its model). From what has been said above it is clear that, whatever the initial conditions for the quantities \(\psi_i\) may be, the section \(AB\) of the circuit produces functions \(\psi_1(t),\ldots,\psi_n(t)\) constituting a solution of equation (3), which in the subsequent sections are transformed into the quantities \((u^1(t),\ldots,u^r(t))=e(\psi(t))\)
(see (10)), i.e., into the corresponding extremal control (see (5)), and at the output of the circuit we obtain the quantities \(x^1(t), \ldots, x^n(t)\), describing the extremal trajectory. Thus it has been proved:
Theorem 3. The circuit shown in Fig. 1 (see also (7), (8), (9)) realizes the motion of the object (2) along an extremal trajectory (for arbitrary initial values of the quantities \(\psi_i\) and \(x^i\)).
It remains to solve the problem of finding the initial value for \(\psi\) for which (for a given initial value \(x_0\)) the resulting trajectory passes through the origin—this will be the optimal trajectory. Such a search should apparently be carried out by one of the following two methods: either, having a fixed initial value \(x_0\), by means of several trials find the required initial value \(\psi_0\); or else, reversing the direction of the flow of time, draw a sufficiently dense net of trajectories emanating from the origin (all of them will be optimal), after which, having “memorized” all points of the phase space \(X\) at which switchings occur, construct the “switching surface” (i.e., carry out the synthesis of optimal controls).
Fig. 2
In conclusion let us consider an important case in applications, when the polyhedron \(U\) is a parallelepiped defined in the space \(E^r\) by the inequalities
\[ \alpha_\rho \leq u^\rho \leq \beta_\rho,\qquad \rho=1,\ldots,r . \tag{11} \]
In other words, we shall consider the case when each of the quantities \(u^\rho\) in equations (1) is a separate control parameter, whose range of variation does not depend on the values of the other control parameters and is specified by inequality (11).
In this case the circuit indicated above may be replaced by the simpler circuit shown in Fig. 2, where
\[ \xi_i=\sum_{\alpha=1}^{n}\psi_\alpha b_i^\alpha,\qquad i=1,\ldots,r, \]
\[ u^\rho=\frac{\alpha_\rho+\beta_\rho}{2}+\eta^\rho\frac{\beta_\rho-\alpha_\rho}{2},\qquad \rho=1,\ldots,r. \]
These formulas can be derived from (7), (8), (9) or proved directly.
Mathematical Institute named after V. A. Steklov
Academy of Sciences of the USSR
Received
9 III 1961
CITED LITERATURE
- V. G. Boltyanskii, R. V. Gamkrelidze, L. S. Pontryagin, DAN, 110, No. 1, 7 (1956).
- R. V. Gamkrelidze, Izv. AN SSSR, Ser. Math., 22, 449 (1958).
- V. G. Boltyanskii, DAN, 119, No. 6, 1070 (1958).
- L. S. Pontryagin, UMN, 14, No. 1, 3 (1959).
- V. G. Boltyanskii, R. V. Gamkrelidze, L. S. Pontryagin, Izv. AN SSSR, Ser. Math., 24, 3 (1960).