Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Properties of optimal ellipsoids approximating reachable sets of uncertain systems

Properties of optimal ellipsoids approximating reachable sets of uncertain systems Mathematical and Computer Modelling of Dynamical Systems Vol. 11, No. 2, June 2005, 135 – 147 Properties of Optimal Ellipsoids Approximating Reachable Sets of Uncertain Systems F.L. CHERNOUSKO* Institute for Problems in Mechanics of the Russian Academy of Sciences, pr. Vernadskogo 101-1, Moscow 119526, Russia. The ellipsoidal estimation of reachable sets is an efficient technique for the set-membership modelling of uncertain dynamical systems. In this paper, the optimal outer ellipsoidal approximation of reachable sets is considered, and attention is paid to the new criterion associated with the projection of the approximating ellipsoid onto a given direction. Nonlinear differential equations governing the evolution of ellipsoids are analysed and simplified. The asymptotic behaviour of ellipsoids near the initial point and at infinity is studied. It is shown that the optimal ellipsoids under consideration touch the corresponding reachable sets at all time instants. A control problem for a system subjected to uncertain perturbations is investigated in the framework of the optimal ellipsoidal estimation of reachable sets. Keywords: Uncertain dynamical systems, set-membership modelling, ellipsoidal estimation, reachable sets, control. 1. Introduction Dynamical systems subjected to unknown but bounded perturbations appear in numerous applications. The set-membership approach to modelling such systems allows one to obtain outer guaranteed estimates on reachable sets and thus to take into account all possible trajectories of the system. This approach can serve as an alternative to the well-known stochastic, or probabilistic, approach. In the framework of the set-membership approach, the ellipsoidal estimation seems to be the most efficient technique. Among its advantages are the explicit form of approximation, invariance with respect to linear transformations, possibility of optimization, etc. The method of ellipsoids for the approximation of reachable sets has been considered by a number of authors. The earlier results were summarized in [1, 2]. The concept of optimality for the approximating ellipsoids was first introduced in [3], where two-sided (inner and outer) ellipsoidal estimates optimal in the sense of volume were proposed and investigated. These results were generalized, extended, and *E-mail: chern@ipmnet.ru Mathematical and Computer Modelling of Dynamical Systems ISSN 1387-3954 print/ISSN 1744-5051 online ª 2005 Taylor & Francis Group Ltd http://www.tandf.co.uk/journals DOI: 10.1080/13873950500068427 136 F. L. Chernousko summarized in [4 – 6]. Various aspects of ellipsoidal estimation of reachable sets were considered in [7, 8]. In this paper, various optimality criteria for the outer ellipsoids approximating reachable sets are considered. The main attention is paid to the criterion introduced in [9] and associated with the projection of an ellipsoid onto a given direction. It is found that this criterion leads to rather simple equations governing the evolution of ellipsoids. Further simplifications of these nonlinear equations are discussed. The asymptotic behaviour of ellipsoids in two limiting cases is analysed, namely in the vicinity of the initial point, where these equations have a singularity, and also at infinity. Both locally and globally optimal ellipsoids (in the sense introduced in [10]) are investigated. It is shown that, in the case of the criterion under consideration and under certain assumptions, these two kinds of optimal ellipsoids coincide. Moreover, it is shown that these ellipsoids touch reachable sets at all time instants. In other words, these ellipsoids are ‘‘tight’’ in the sense of [11]. At the end of the paper, a special optimal control problem for a system subjected to uncertain perturbations is considered. The uncertainty is described by means of the ellipsoidal estimation, and thus the problem is reduced to the control of ellipsoidal sets. The solution is obtained in an explicit form. 2. Ellipsoidal estimation Consider a linear system of ordinary differential equations x ¼ AðtÞx þ BðtÞu þ fðtÞ; t  s ð1Þ n m Here, x2R is the n-vector of state, u2R is the m-vector of unknown perturbations, the dot denotes differentiation with respect to time t, A is an n6 n matrix, B is an n6 m matrix, and f is an n-vector. The matrices A(t)and B(t) as well as the vector f(t) are given functions of time for t 5 s, where s is the initial time instant. By E(a,Q) denote the following n-dimensional ellipsoid Eða; QÞ¼ fx : ðQ ðx  aÞ;ðx  aÞÞ  1g; ð2Þ where a 2 R is its centre, Q is a positive definite n6 n matrix, and (.,.) denotes the scalar product of vectors. Suppose the unknown perturbation u(t) is bounded by the ellipsoid as follows uðtÞ2 Eð0; GðtÞÞ; t  s; ð3Þ where G(t)isan m6 m matrix specified for t 5 s. The initial data for Equation (1) are also uncertain and are described by the inclusion xðsÞ2 M ¼ Eða ; Q Þ; ð4Þ 0 0 where M is a given set in R ,a is a given n-vector, and Q is a given positive definite n 0 0 n6 n matrix. The reachable or attainable set D(t,s,M) of system (1) for t 5 s is defined as the set of all end points x(t) at the instant t of all state trajectories x() compatible with Equations (1), (3), and (4). The reachable set has the following evolutionary property Dðt; s; MÞ¼ DtðÞ ; t; Dðt; s; MÞ ð5Þ Properties of optimal ellipsoids 137 which is true for all t 2 [s,t]. Since the precise determination of reachable sets usually presents a very complicated problem, we are often interested in finding an outer ellipsoidal approximation E(a(t),Q(t)) of these sets such that D(t,s,M)( E(a(t),Q(t)) for all t 5 s. The family of ellipsoids E (t)= E(a(t),Q(t)) is called superreachable (super- + + attainable),if E (t)) D(t,t,E (t)) for all t2 [s,t]. This property is similar to Equation (5). We shall consider outer ellipsoidal estimates of reachable sets in the class of superreachable ellipsoids. Also, we shall impose certain optimality conditions in order to make the approximating ellipsoids closer to reachable sets. 3. Optimality Let us characterize an ellipsoid E(a,Q) by a scalar optimality criterion J which is a given function L(Q) of the matrix Q, i.e. J(E(a,Q)) = L(Q). Here, the function L(Q) is defined for all symmetric positive definite matrices Q, is smooth and monotone. The latter property means that L(Q ) 5 L(Q ), if (Q – Q ) is a non-negative definite matrix. 1 2 1 2 Consider some important particular cases of the general optimality criterion L(Q). 1/2 1. The volume of an ellipsoid is given by J = c (detQ) , where c is a constant n n depending on n. 2. The sum of the squared semi-axes of an ellipsoid is equal to J=TrQ. 3. A more general linear optimality criterion is J = Tr(CQ), where C is a symmetric non-negative definite n6 n matrix. 4. The following criterion J=(Qv,v), where v is a given non-zero n-vector, is a particular case of the previous one. Here, we have C ¼ v  v; C ¼ v v ; i; j ¼ 1; ... ; n; ð6Þ ij i j where the symbol * denotes the dyadic product of vectors. This criterion has a clear geometric interpretation: it is related to the projection P (E) of the ellipsoid E(a,Q) 1/2 onto the direction of the vector v as follows [9]: P (E)=2(Qv,v) /jvj. Therefore, the minimization of the criterion J=(Qv,v) is equivalent to the minimization of the projection of an ellipsoid onto the direction of the vector v. Other examples of optimality criteria are given in [5]. We consider below locally optimal and globally optimal outer ellipsoids. A smooth family of ellipsoids E*(t)= E(a(t),Q(t)) is called locally optimal,ifitis superreachable and dL(Q(t)/dtj ?min for all t 5 s where the minimum is taken t=t + + over all smooth families of superreachable ellipsoids E (t) such that E (t)= E*(t). A smooth family of superreachable ellipsoids is called globally optimal for a given t = T, if the minimum of L(Q(T)) over all superreachable families of ellipsoids is attained on this family. As shown in [3 – 6], the parameters of locally optimal ellipsoids can be obtained from initial value problems for certain systems of ordinary differential equations (linear for the vectors a(t) and nonlinear for the matrix Q(t)). By contrast, the determination of globally optimal ellipsoids is reduced to a two-point boundary value problem, see [5, 6, 10]. Hence, locally optimal ellipsoids are easier to determine, and they can give reasonable outer approximations of reachable sets for all t 5 s. On the other hand, globally optimal ellipsoids require more complicated calculations and produce the optimal approximation of the reachable set, but only at t = T. 138 F. L. Chernousko Note that all definitions and results related to optimal ellipsoids are true also for the case where the criterion depends also on time t so that L = L(Q,t). Below, we restrict ourselves to the criterion J = Tr[C(t)Q] and its particular case J=(Qv,v) with v = v(t). It is found that this criterion leads to rather simple equations for ellipsoids and gives quite satisfactory outer approximations of reachable sets (sometimes, better than the approximations optimal in the sense of volume, see Section 6). However, only ellipsoids optimal in the sense of volume are invariant with respect to linear transformations [5, 6]. 4. Simplifications For the criterion J = Tr[(C(t)Q], the parameters of locally optimal ellipsoids satisfy the following differential equations and initial conditions [5, 6, 9]: a_ ¼ AðtÞa þ fðtÞ; aðsÞ¼ a ; ð7Þ T 1 T Q ¼ AQ þ QA þ hQ þ h K; KðtÞ¼ BGB ; QðsÞ¼ Q : ð8Þ Here, denotes a transposed matrix, and the following notation is used: 1=2 h ¼½TrðCKÞ=TrðCQÞ : ð9Þ The centre a(t) of globally optimal ellipsoids coincides with that of locally optimal ellipsoids and satisfies the same equation (7). The matrix Q(t) of globally optimal 1/2 ellipsoids satisfies (8), where, instead of (9), we have for h: h = [Tr(PK)/Tr(PQ] . Here, P(t) is a symmetric positive definite n6 n matrix satisfying the following equation and initial condition at t = T: P ¼PA  A P; PðTÞ¼ CðTÞ: ð10Þ Therefore, for the criterion J=Tr(CQ), the boundary value problem for the matrix Q(t) of globally optimal ellipsoids becomes decoupled and reduces to two initial value problems: a linear one (10) for P(t) (which is to be solved from t = T to t = s) and a nonlinear one defined by Equations (8) and (9) for Q(t). Further simplifications are possible for the criterion J=(Qv,v). Substituting C from 1/2 (6) into (9), we obtain for locally optimal ellipsoids h=[(Kv,v)/(Qv,v) . Here, v = v(t) is a given non-zero vector function. For globally optimal ellipsoids, we have CðTÞ¼ v  v where v is a given constant T T T n-vector. Let us introduce the adjoint vector c(t) satisfying the following initial value problem: c ¼A c; cðTÞ¼ v : ð11Þ Substituting the following expression for P(t): PðtÞ¼ cðtÞ cðtÞð12Þ into (10) and taking into account (6) and (11), we find out that Equations (10) are satisfied. Thus, the solution of Equations (10) is given by (12), where c satisfies Properties of optimal ellipsoids 139 Equations (11). Therefore, in order to find the matrix Q(t) of globally optimal ellipsoids in the case of the criterion J=(Qv,v), one has to solve first the linear n- dimensional initial value problem (11) for c (instead of the n(n + 1)/2-dimensional problem for P) and then a nonlinear initial value problem for Q, given by Equation (8), 1/2 where h=[Kc,c)/(Qc,c)] . 5. Properties of optimal ellipsoids First, let us consider ellipsoids globally optimal in the sense of criterion J=(Qv,v). We shall show that these ellipsoids E(a(t),Q(t)) for all t2 [s,T] touch the reachable sets D(t,s,M) at points x(t) where the normal to the boundary is parallel to the vector c. To prove that, consider first a point x(t)2 D(t,s,M) at which the support plane to D(t,s,M) is orthogonal to c. At this point the expression dðx; cÞ ðxðtÞ; cðtÞÞ ¼ ðxðsÞ; cðsÞÞ þ dt ð13Þ dt attains its maximum with respect to x(s)2 M and u(t),t2 [s,t]. Here, M is defined by Equation (4), and u(t) is bounded by (3). Substituting Equations (1) and (11) into (13) and maximizing the integrand with respect to u(t) over the ellipsoid E(0,G(t)), we obtain 1=2 dðx; cÞ=dt ¼ðf; cÞþðB u; cÞ¼ðf; cÞþðKc; cÞ ; ð14Þ where the matrix K is defined in Equation (8). Calculating the maximum of (x(s),c(s)) over x(s)2 M, we get 1=2 ðxðsÞ; cðsÞÞ ¼ ða ; cðsÞÞ þ ðQ cðsÞ; cðsÞÞ : ð15Þ 0 0 Substituting Equations (14) and (15) into (13), we obtain the following expression for the support function of the reachable set D(t,s,M): 1=2 r ðcðtÞÞ ¼ ða ; cðsÞÞ þ ðQ cðsÞ; cðsÞÞ 0 0 Dðt;s;MÞ ð16Þ 1=2 þ ½ðf; cÞþðKc; cÞ dt: On the other hand, the support function of the approximating ellipsoid E(a(t),Q(t)) is equal to 1=2 r ðcÞ¼ðaðtÞ; cÞþðQðtÞc; cÞ : ð17Þ EðaðtÞ;QðtÞÞ It follows from Equations (7), (8), and (11) that ðaðtÞ; cðtÞÞ ¼ ða ; cðsÞÞ þ ðf; cÞdt; 1=2 1=2 1=2 ðQðtÞcðtÞ; cðtÞÞ ¼ðQ cðsÞ; cðsÞÞ þ ðKc; cÞ dt: s 140 F. L. Chernousko Substituting these equations into (17) and comparing the obtained result with (16), we see that the values of the support functions of the sets D(t,s,M) and E(a(t),Q(t)) for the vector c(t) coincide. Since D(t,s,M)( E(a(t)),Q(t)), this means that the boundaries of these sets touch at the point x(t). Outer approximating ellipsoids which touch reachable sets at all time instants were called tight [11]. We have proved that the globally optimal (in the sense of the criterion J=(Qv,v)) ellipsoids are tight [12]. It is clear that globally optimal ellipsoids are also locally optimal for the vector v(t)= c(t), where c is defined by (11). Consider now locally optimal (in the sense of the criterion J=(Qv,v)) ellipsoids for the vector v(t) defined by T 0 vðtÞ¼ cðtÞ; c ¼A c; cðsÞ¼ v : ð18Þ Here, v is an arbitrary vector. Let us fix any time instant T*2 [s,T] and denote v*= v(T*). If the instant T* is taken as a terminal instant for globally optimal ellipsoids and v* as a respective value of the vector v for this instant, then our locally optimal ellipsoids are also globally optimal for the instant T* and vector v*. Thus, our locally optimal ellipsoids for the vector v(t) defined by (18) are, first, globally optimal for all t 5 s and respective v(t) and, second, touch reachable sets at all t 5 s at points, where the normal to the boundary is directed along v(t). The procedure for constructing these ellipsoids is rather simple. One is to solve the linear initial value problem for a(t) defined by (7) and also the initial value problem for the system consisting of Equation (8) for Q(t) and Equation (18) for v(t)= c(t). Here, 0 0 the vector v can be chosen arbitrarily, and different vectors v correspond to different approximating ellipsoids touching reachable sets at different points. 6. Example Consider a system of second order x_ ¼ x ; x_ ¼ u; juj 1; x ð0Þ¼ x ð0Þ¼ 0 ð19Þ 1 2 2 1 2 for which an exact solution for locally optimal ellipsoids can be found and compared with reachable sets. The optimality criterion is taken as follows: J=(Qv,v) where v =0, v = 1. Hence, the rate of the projection of the outer approximating ellipse onto 1 2 the axis x is minimized. For our example (19), Equations (7) for the centre of the ellipse give: a (t):a (t):0. 1 2 Equations (8) and (9) for this example become _ _ _ Q ¼ 2Q þ hQ ; Q ¼ Q þ hQ ; Q ¼ hQ þ h ; 12 11 22 12 22 11 12 22 ð20Þ 1=2 h ¼ Q ; Q ð0Þ¼ Q ð0Þ¼ Q ð0Þ¼ 0: 11 12 22 The nonlinear initial value problem (20) has the following exact solution: 4 3 t t Q ¼ ; Q ¼ ; Q ¼ t : ð21Þ 11 12 22 3 2 Properties of optimal ellipsoids 141 Thus, the centre of the approximating ellipse stay at the origin of coordinates, and its matrix is given by Equations (21). This ellipse E is shown in Figure 1. For comparison, the exact reachable set D and the approximating ellipse E locally optimal in the sense of volume [3 – 5] are also depicted in Figure 1. All sets are drawn in normalized –2 –1 coordinates x t and x t ; in these variables the sets remain constant. The areas 1 2 V ,V , and V of the reachable set D and ellipsoids E and E , respectively, are D 1 2 1 2 1=2 1 1=2 1 V ¼ 2=3  0:667; V ¼ pð2 3 Þ  0:907; V ¼ 8pð9 5 Þ  1:25: D 1 2 It is evident from these formulas and Figure 1 that ellipse E gives a much better approximation of the reachable set D than ellipse E , even in the sense of volume. This example shows that the ellipsoids optimal in the sense of the criterion J=(Qv,v) may give a rather efficient outer approximation of reachable sets. 7. Transformation of equations Equation (8) for the matrix Q depends on three matrices: A, K, and C. By means of special transformations, we shall simplify this equation both for locally and globally optimal ellipsoids in cases of the criteria J = Tr(CQ)and J=(Qv,v). In the locally optimal case, we make the change of variables [4 – 6]: Q ¼ VQ V ; ð22Þ where V(t) is an invertible n6 n matrix and Q is a new variable. Taking V(t) equal to the fundamental matrix of Equation (1), i.e. V ¼ AV; VðsÞ¼ I; t  s; ð23Þ where I is the unit n6 n matrix, we obtain from Equations (8), (9), (22) and (23): 1 1 1 Q ¼ h Q þ h K ; Q ðsÞ¼ Q ; K ¼ V KðV Þ ; ð24Þ 1=2 h ¼½TrðC K Þ=TrðC Q Þ ; C ¼ V CV: Let the matrix K(t) be positive definite for all t 5 s. By taking 1=2 VðtÞ¼½KðtÞ ; ð25Þ we obtain from Equations (8), (9), (19), and (25): T 1 1=2 1=2 Q ¼ A Q þ Q A þ h Q þ h I; Q ðsÞ¼ K ðsÞQ K ðsÞ; ð26Þ 1=2 1=2 1=2 A ¼ K ðAK  dK =dtÞ; 1=2 1=2 1=2 C ¼ K CK ; h ¼½TrC =TrðC Q Þ : Note that each of Equations (24) and (26) for Q depend only on two matrices: K and * * C ,or A and C , respectively. Thus, without loss of generality, one can always put * * * 142 F. L. Chernousko Figure 1. Approximation of reachable sets by ellipsoids. either A=0 or K = I (in the case of a positive definite matrix K) in Equations (8) and (9). For the criterion J=(Qv,v), the formulas for h in (24) and (26) become simpler: 1=2 h ¼½ðK v ; v Þ=TrðQ v ; v Þ ; v ¼ V v; ð27Þ 1=2 2 1=2 h ¼½v =ðQ v ; v Þ ; v ¼ K v; ð28Þ for the respective cases given by Equations (23) and (25). Consider now equations for globally optimal ellipsoids in the case of the criterion J=Tr(CQ). Here, we use the change of variables: T 1 1 Q ¼ VQ V ; P ¼ðV Þ P V ; ð29Þ where V(t) is the same matrix as in (22), whereas Q and P are new variables. In the * * case of V defined by Equation (23), we obtain from (10) that P (t):C(T). As a result, the equations for the matrix Q (t) take the form (24), where C (t)= V (t)C(T)V(t). * * If the matrix K(t) is positive definite for all t 5 s, we can make the change of variables (29) with V(t) defined by (25). As a result, Equations (8) and (10) for the matrices Q and P take the form: * * T 1 Q ¼ A Q þ Q A þ h Q þ h I; 1=2 1=2 1=2 Q ðsÞ¼ K ðsÞQ K ðsÞ; h ¼½TrP =TrðP Q Þ ; T 1=2 1=2 P ¼P A  A P ; P ðTÞ¼ K ðTÞCðTÞK ðTÞ: Let us now consider the equations of globally optimal ellipsoids for the criterion J=(Qv ,v ). Using the change of variables defined by (29) and (23), we come to T T Properties of optimal ellipsoids 143 Equations (24) for the matrix Q (t), where h is defined by (27) and v (t)= V (t)v . * * * Defining V by (25), we come to the following equations: T 1 Q ¼ A Q þ Q A þ h Q þ h I; 1=2 1=2 1=2 2 Q ðsÞ¼ K ðsÞQ K ðsÞ; h ¼½c =ðQ c ; c Þ ; 1=2 c ¼A c ; c ðTÞ¼ K ðTÞv : 8. Asymptotics near the initial point Consider an important special case, where the initial point is fixed. Then the initial set M in (4) degenerates into a point: a(s)= a ,Q(s) = 0. Hence, the right-hand side of Equation (8) for Q has a singularity at t = s, and the straightforward numerical integration of this equation near t = s is impossible. Let us study the asymptotic behaviour of locally optimal ellipsoids near t = s in the case of Q = 0. Suppose the matrix K in (8) is positive definite; then Equations (8) can be replaced by (26). We have T 1 Q ¼ A Q þ Q A þ h Q þ h I; ð30Þ 1=2 h ¼½TrC =TrðC Q Þ ; Q ðsÞ¼ 0: Here, the matrices A and C are assumed to be smooth functions of time, so that the following expansions hold A ¼ A þ yA þ Oðy Þ; y ¼ t  s  0; 0 1 ð31Þ C ¼ C þ yC þ Oðy Þ: 0 1 Here, A , A , C , and C are constant matrices. Let us find the solution of Equation 0 1 0 1 (30) in the form of a power series in y, i.e. 2 3 4 5 Q ¼ yQ þ y Q þ y Q þ y Q þ Oðy Þ: ð32Þ 1 2 3 4 Here, Q ,Q ,. . . are constant matrices as yet unknown. We substitute (31) and (32) into 1 2 Equation (30) for Q and expand both sides into series in y. By equating coefficients of the obtained series in both sides of the resultant equation, we find the unknown coefficients in Equation (32). After lengthy but straightforward calculations, we obtain Q ¼ 0; Q ¼ I; Q ¼ D ; 1 2 3 0 ð33Þ 2 ½TrðC D Þ TrðC D Þ 0 0 0 0 Q ¼ ðD þ D Þþ I  D ; 4 1 0 3 6TrC 12ðTrC Þ 0 T T where the following notation is introduced: D ¼ðA þ A Þ=2, D ¼ðA þ A Þ=2. 0 0 1 1 0 1 Note that the coefficients Q ,Q ,Q ,Q do not depend on the matrix C . 1 2 3 4 1 Consider two particular cases. 144 F. L. Chernousko 1. Let C = I; this equality corresponds to the criterion J=TrQ. Then we obtain from Equation (33): 2 ðTrD Þ TrD 0 0 Q ¼ ðD þ D Þþ I  D : ð34Þ 4 1 0 3 12n 6n Equations (33) and (34) coincide with those given in [5] for the ellipsoids locally optimal in the sense of volume. Thus, the approximating ellipsoids locally optimal in the sense of the sum of squared semi-axes coincide with the ellipsoids locally optimal in the sense of volume up to the terms of order of O(y ). 2. For the criterion J=(Qv,v), we have C = v v, and it follows from Equation (33) that 2 ðD v; vÞ ðD v; vÞ 0 0 Q ¼ ðD þ D Þþ I  D : 4 1 0 3 12 6 The obtained expansions can be used for starting the numerical integration of Equations (8) near the initial point t = s in case of Q =0. 9. Asymptotics at infinity Let us investigate the asymptotic behaviour at infinity of ellipsoids locally optimal in the sense of the criterion J=(Qv,v). Suppose for simplicity that the matrix K in Equations (8) is positive definite, so that we can use Equations (26). Also, suppose the matrix A is constant and diagonal: A = diag (a , ..., a ), where a 4a 4...4a . 1 n 1 2 n * * Under the assumptions made, the solution Q of Equations (26) is a diagonal matrix, its diagonal elements being positive and equal to the squares of semi-axes of the approximating ellipsoid: Q (t) = diag(y (t),. . .,y (t)). Equation (26) under the assump- 1 n tions made is reduced to equations: y_ ¼ 2a y þ h y þ h ; i ¼ 1; ... ; n: ð35Þ i i  i Here, h is given by Equation (28), where v is assumed to be a constant unit vector, jv j = 1. Omitting the subscripts , we have * * 1=2 h ¼ v y : ð36Þ i1 First, suppose at least one of a is non-negative: a 5 0. Then, since y (t) 5 0, the i n n right-hand side of the nth Equation (35) is positive for all t 5 s,and y (t) grows monotonically with t. If we assume that there exists a bounded limit y ðtÞ! y > 0as t??, then we come to a contradiction: the left-hand side of the nth Equation (35) tends to zero, whereas its right-hand side is non-zero as t??. Hence, y (t)?? as –1 t??. Then, by virtue of (36), h?0 and h ?? as t??. Thus, the right-hand sides of all Equations (35) tend to infinity as t??, and all y (t)?? as t??. Consider now the case where all a are negative. Denote a =– b , b 5 i n n 1 b 5...5b 4 0. Let us rewrite Equations (35): 2 n y_ ¼2b y þ hy þ h ; i ¼ 1; ... ; n; ð37Þ i i i i Properties of optimal ellipsoids 145 and find their stationary solutions by setting the right-hand sides of Equations (37) equal to zero. We obtain y ¼ ; i ¼ 1; ... ; n; ð38Þ h ð2b  h Þ 0 0 where the following notation is introduced: 1=2 2 0 h ¼ v y : ð39Þ i i i1 By substituting y from (38) into (39), we obtain the equation for h : 1 v ¼ : ð40Þ h 2b  h 0 0 i1 Since y  0 and b 4b for all i=1, ..., n, only those h are admissible which lie n i 0 within the interval h 2 (0,2b ). While h changes from 0 to 2b , the left-hand side of 0 n 0 n –1 Equation (40) decreases monotonically from ? to (2b ) , whereas its right-hand side increases from some positive value to ?. Hence, there exists a unique positive root h 2 (0,2b ) of Equation (40). Substituting this root into (39), we obtain a unique 0 n stationary point y ; i ¼ 1; ... ; n, of Equations (37). Numerical investigation of these equations shows that, in a wide range of parameters variation, the stationary point is asymptotically stable and attracts all solutions of the system in the domain y 5 0,i=1, ..., n. 10. Control Consider a system subjected to the control w and perturbation u: x_ ¼ Ax þ Bu þ Ww þ f; t 2½s; T: ð41Þ Here, w(t)is a k-vector of control, W(t) is a given n6 k matrix, T is a fixed terminal instant, and other notation is the same as in Equation (1). The initial conditions are given by (4). Suppose the perturbation u is caused by the imperfection of the control implementation, and the possible magnitude of u grows with the magnitude of the control w. More exactly, we assume that the matrices B in (41) and G in (3) depend on w in such a way that the matrix K from Equations (8) is equal to K ¼ BGB ¼jwj RðtÞ; ð42Þ where R(t) is a given positive definite n6 n matrix. This condition, together with (3), means that the magnitude of the perturbation u grows quadratically with the magnitude of the control w. Using the transformation given by (22) and (23), we will use Equations (24) for the ellipsoids locally optimal in the sense of the criterion J=(Qv,v) with constant v. Taking into account also Equations (27) and (42) and omitting the subscripts, we obtain 146 F. L. Chernousko a ¼ Ww þ f; ð43Þ 2 1=2 1=2 Q ¼jwj ½ðr=qÞ Q þðq=rÞ R; where the following notation is introduced: q=(Qv,v), r=(Rv,v). Let us find the control w(t) which minimizes the functional 0 1=2 2 J ¼ðaðTÞ; vÞþ½qðTÞ þ b jwj dt ð44Þ for Equations (43) describing the evolution of the outer approximating ellipsoids. Here, b is a positive constant. The functional defined by (44) includes the support function for the approximating ellipsoid E(a(T),Q(T)) at the terminal moment T and the quadratic integral cost. Thus, we seek the control w(t) which is, in a certain sense, optimal for the whole ensemble of possible trajectories of Equation (41). Differentiating q=(Qv,v) according to (43), we obtain 2 1=2 q_ ¼ 2jwj ðqrÞ : ð45Þ Instead of the matrix Q, it is sufficient to consider a scalar variable q. Thus, our optimal control problem is considerably simplified. We introduce adjoint variables c and f corresponding to the respective state variables a and q. Here, a and c are n-vectors, and q and f are scalars. The Hamiltonian for our optimal control problem is given by 2 1=2 2 H ¼ðc; Ww þ fÞþ 2jwj ðqrÞ j  bjwj : ð46Þ According to the maximum principle, the optimal control corresponds to the maximum value of H over w. We have 1=2 w ¼ W c=½2b  4ðqrÞ j: ð47Þ The adjoint equations and transversality conditions for our problem are: 2 1=2 1=2 c ¼ 0; j _ ¼jwj ðr=qÞ j; cðTÞ¼v; jðTÞ¼½qðTÞ =2: ð48Þ It follows from Equations (48) and (45) that c and qf are constant. Hence, we have 1=2 cðtÞ¼ v; jðtÞ¼q =2: ð49Þ Inserting (49) into Equation (47), we obtain finally 1=2 wðtÞ¼ W ðtÞv=½2b þ 4ðRðtÞv; vÞ : ð50Þ Thus, in the special case considered here, the control is found in explicit form. Substituting w(t) from (50) into Equations (43) and integrating them under the initial conditions given by (4), we can obtain the parameters of the approximating ellipsoid E(a(t),Q(t)) as functions of time. Properties of optimal ellipsoids 147 11. Conclusions A new criterion for outer optimal ellipsoids approximating reachable sets is discussed. This criterion is associated with the projection of an ellipsoid onto a given direction and has certain advantages. The resulting equations for the evolution of approximating ellipsoids are investigated and simplified. It is shown that, under certain assumptions, globally optimal ellipsoids coincide with locally optimal ones. These ellipsoids touch reachable sets at all time moments. The asymptotic behaviour of ellipsoids near the initial point and at infinity is investigated. A special control problem for an uncertain system is solved in explicit form. Acknowledgements The work is partially supported by the Russian Foundation of Basic Research (Grant 05-01-00647) and by the Grant of the President of the RF for leading scientific schools No. 1627.2003.1. References [1] Schweppe, F.C., 1973, Uncertain Dynamic Systems (Englewood Cliffs, Prentice Hall). [2] Kurzhanski, A.B., 1977, Control and Observation in Uncertainty Conditions (Moscow: Nauka). [3] Chernousko, F.L., 1981, Engineering Cybernetics, 18, No. 3, 3 – 11; No. 4, 3 – 11; No. 5, 5 – 11. [4] Chernousko, F.L., 1988, Estimation of the Phase State for Dynamical Systems (Moscow: Nauka). [5] Chernousko, F.L., 1994, State Estimation for Dynamic Systems (Boca Raton: CRC Press). [6] Chernousko, F.L., 1999, In: I. Elishakoff (Ed.) Whys and Hows in Uncertainty Modelling (Vienna: Springer), pp. 127 – 188. [7] Milanese, M., Norton, J., Piet-Lahanier, H. and Walter, E. (Eds), 1996, Bounding Approaches to System Identification (New York: Plenum Press). [8] Kurzhanski, A.B. and Valyi, I., 1997, Ellipsoidal Calculus for Estimation and Control (Boston: Birkha¨ user). [9] Chernousko, F.L., 2002, Cybernetics and Systems Analysis, No. 2, 85 – 95. [10] Ovseevich, A.I., 1991, In: G.B.Di Masi and A.B. Kurzhansky (Eds) Modelling, Estimation and Control of Systems with Uncertainty (Boston: Birkha¨ user), pp. 324 – 333. [11] Kurzhanski, A.B. and Varaiya, P., 2000, Ellipsoidal Techniques for Reachability Analysis. Lecture Notes in Computer Science, 1790, pp. 202 – 214. [12] Chernousko, F.L. and Ovseevich, A.I., 2003, Doklady Mathematics, 67, 123 – 126. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Mathematical and Computer Modelling of Dynamical Systems Taylor & Francis

Properties of optimal ellipsoids approximating reachable sets of uncertain systems

Download PDF
13 pages

Loading next page...
 
/lp/taylor-francis/properties-of-optimal-ellipsoids-approximating-reachable-sets-of-czQnRkpI0n

References (19)

Publisher
Taylor & Francis
Copyright
Copyright Taylor & Francis Group, LLC
ISSN
1744-5051
eISSN
1387-3954
DOI
10.1080/13873950500068427
Publisher site
See Article on Publisher Site

Abstract

Mathematical and Computer Modelling of Dynamical Systems Vol. 11, No. 2, June 2005, 135 – 147 Properties of Optimal Ellipsoids Approximating Reachable Sets of Uncertain Systems F.L. CHERNOUSKO* Institute for Problems in Mechanics of the Russian Academy of Sciences, pr. Vernadskogo 101-1, Moscow 119526, Russia. The ellipsoidal estimation of reachable sets is an efficient technique for the set-membership modelling of uncertain dynamical systems. In this paper, the optimal outer ellipsoidal approximation of reachable sets is considered, and attention is paid to the new criterion associated with the projection of the approximating ellipsoid onto a given direction. Nonlinear differential equations governing the evolution of ellipsoids are analysed and simplified. The asymptotic behaviour of ellipsoids near the initial point and at infinity is studied. It is shown that the optimal ellipsoids under consideration touch the corresponding reachable sets at all time instants. A control problem for a system subjected to uncertain perturbations is investigated in the framework of the optimal ellipsoidal estimation of reachable sets. Keywords: Uncertain dynamical systems, set-membership modelling, ellipsoidal estimation, reachable sets, control. 1. Introduction Dynamical systems subjected to unknown but bounded perturbations appear in numerous applications. The set-membership approach to modelling such systems allows one to obtain outer guaranteed estimates on reachable sets and thus to take into account all possible trajectories of the system. This approach can serve as an alternative to the well-known stochastic, or probabilistic, approach. In the framework of the set-membership approach, the ellipsoidal estimation seems to be the most efficient technique. Among its advantages are the explicit form of approximation, invariance with respect to linear transformations, possibility of optimization, etc. The method of ellipsoids for the approximation of reachable sets has been considered by a number of authors. The earlier results were summarized in [1, 2]. The concept of optimality for the approximating ellipsoids was first introduced in [3], where two-sided (inner and outer) ellipsoidal estimates optimal in the sense of volume were proposed and investigated. These results were generalized, extended, and *E-mail: chern@ipmnet.ru Mathematical and Computer Modelling of Dynamical Systems ISSN 1387-3954 print/ISSN 1744-5051 online ª 2005 Taylor & Francis Group Ltd http://www.tandf.co.uk/journals DOI: 10.1080/13873950500068427 136 F. L. Chernousko summarized in [4 – 6]. Various aspects of ellipsoidal estimation of reachable sets were considered in [7, 8]. In this paper, various optimality criteria for the outer ellipsoids approximating reachable sets are considered. The main attention is paid to the criterion introduced in [9] and associated with the projection of an ellipsoid onto a given direction. It is found that this criterion leads to rather simple equations governing the evolution of ellipsoids. Further simplifications of these nonlinear equations are discussed. The asymptotic behaviour of ellipsoids in two limiting cases is analysed, namely in the vicinity of the initial point, where these equations have a singularity, and also at infinity. Both locally and globally optimal ellipsoids (in the sense introduced in [10]) are investigated. It is shown that, in the case of the criterion under consideration and under certain assumptions, these two kinds of optimal ellipsoids coincide. Moreover, it is shown that these ellipsoids touch reachable sets at all time instants. In other words, these ellipsoids are ‘‘tight’’ in the sense of [11]. At the end of the paper, a special optimal control problem for a system subjected to uncertain perturbations is considered. The uncertainty is described by means of the ellipsoidal estimation, and thus the problem is reduced to the control of ellipsoidal sets. The solution is obtained in an explicit form. 2. Ellipsoidal estimation Consider a linear system of ordinary differential equations x ¼ AðtÞx þ BðtÞu þ fðtÞ; t  s ð1Þ n m Here, x2R is the n-vector of state, u2R is the m-vector of unknown perturbations, the dot denotes differentiation with respect to time t, A is an n6 n matrix, B is an n6 m matrix, and f is an n-vector. The matrices A(t)and B(t) as well as the vector f(t) are given functions of time for t 5 s, where s is the initial time instant. By E(a,Q) denote the following n-dimensional ellipsoid Eða; QÞ¼ fx : ðQ ðx  aÞ;ðx  aÞÞ  1g; ð2Þ where a 2 R is its centre, Q is a positive definite n6 n matrix, and (.,.) denotes the scalar product of vectors. Suppose the unknown perturbation u(t) is bounded by the ellipsoid as follows uðtÞ2 Eð0; GðtÞÞ; t  s; ð3Þ where G(t)isan m6 m matrix specified for t 5 s. The initial data for Equation (1) are also uncertain and are described by the inclusion xðsÞ2 M ¼ Eða ; Q Þ; ð4Þ 0 0 where M is a given set in R ,a is a given n-vector, and Q is a given positive definite n 0 0 n6 n matrix. The reachable or attainable set D(t,s,M) of system (1) for t 5 s is defined as the set of all end points x(t) at the instant t of all state trajectories x() compatible with Equations (1), (3), and (4). The reachable set has the following evolutionary property Dðt; s; MÞ¼ DtðÞ ; t; Dðt; s; MÞ ð5Þ Properties of optimal ellipsoids 137 which is true for all t 2 [s,t]. Since the precise determination of reachable sets usually presents a very complicated problem, we are often interested in finding an outer ellipsoidal approximation E(a(t),Q(t)) of these sets such that D(t,s,M)( E(a(t),Q(t)) for all t 5 s. The family of ellipsoids E (t)= E(a(t),Q(t)) is called superreachable (super- + + attainable),if E (t)) D(t,t,E (t)) for all t2 [s,t]. This property is similar to Equation (5). We shall consider outer ellipsoidal estimates of reachable sets in the class of superreachable ellipsoids. Also, we shall impose certain optimality conditions in order to make the approximating ellipsoids closer to reachable sets. 3. Optimality Let us characterize an ellipsoid E(a,Q) by a scalar optimality criterion J which is a given function L(Q) of the matrix Q, i.e. J(E(a,Q)) = L(Q). Here, the function L(Q) is defined for all symmetric positive definite matrices Q, is smooth and monotone. The latter property means that L(Q ) 5 L(Q ), if (Q – Q ) is a non-negative definite matrix. 1 2 1 2 Consider some important particular cases of the general optimality criterion L(Q). 1/2 1. The volume of an ellipsoid is given by J = c (detQ) , where c is a constant n n depending on n. 2. The sum of the squared semi-axes of an ellipsoid is equal to J=TrQ. 3. A more general linear optimality criterion is J = Tr(CQ), where C is a symmetric non-negative definite n6 n matrix. 4. The following criterion J=(Qv,v), where v is a given non-zero n-vector, is a particular case of the previous one. Here, we have C ¼ v  v; C ¼ v v ; i; j ¼ 1; ... ; n; ð6Þ ij i j where the symbol * denotes the dyadic product of vectors. This criterion has a clear geometric interpretation: it is related to the projection P (E) of the ellipsoid E(a,Q) 1/2 onto the direction of the vector v as follows [9]: P (E)=2(Qv,v) /jvj. Therefore, the minimization of the criterion J=(Qv,v) is equivalent to the minimization of the projection of an ellipsoid onto the direction of the vector v. Other examples of optimality criteria are given in [5]. We consider below locally optimal and globally optimal outer ellipsoids. A smooth family of ellipsoids E*(t)= E(a(t),Q(t)) is called locally optimal,ifitis superreachable and dL(Q(t)/dtj ?min for all t 5 s where the minimum is taken t=t + + over all smooth families of superreachable ellipsoids E (t) such that E (t)= E*(t). A smooth family of superreachable ellipsoids is called globally optimal for a given t = T, if the minimum of L(Q(T)) over all superreachable families of ellipsoids is attained on this family. As shown in [3 – 6], the parameters of locally optimal ellipsoids can be obtained from initial value problems for certain systems of ordinary differential equations (linear for the vectors a(t) and nonlinear for the matrix Q(t)). By contrast, the determination of globally optimal ellipsoids is reduced to a two-point boundary value problem, see [5, 6, 10]. Hence, locally optimal ellipsoids are easier to determine, and they can give reasonable outer approximations of reachable sets for all t 5 s. On the other hand, globally optimal ellipsoids require more complicated calculations and produce the optimal approximation of the reachable set, but only at t = T. 138 F. L. Chernousko Note that all definitions and results related to optimal ellipsoids are true also for the case where the criterion depends also on time t so that L = L(Q,t). Below, we restrict ourselves to the criterion J = Tr[C(t)Q] and its particular case J=(Qv,v) with v = v(t). It is found that this criterion leads to rather simple equations for ellipsoids and gives quite satisfactory outer approximations of reachable sets (sometimes, better than the approximations optimal in the sense of volume, see Section 6). However, only ellipsoids optimal in the sense of volume are invariant with respect to linear transformations [5, 6]. 4. Simplifications For the criterion J = Tr[(C(t)Q], the parameters of locally optimal ellipsoids satisfy the following differential equations and initial conditions [5, 6, 9]: a_ ¼ AðtÞa þ fðtÞ; aðsÞ¼ a ; ð7Þ T 1 T Q ¼ AQ þ QA þ hQ þ h K; KðtÞ¼ BGB ; QðsÞ¼ Q : ð8Þ Here, denotes a transposed matrix, and the following notation is used: 1=2 h ¼½TrðCKÞ=TrðCQÞ : ð9Þ The centre a(t) of globally optimal ellipsoids coincides with that of locally optimal ellipsoids and satisfies the same equation (7). The matrix Q(t) of globally optimal 1/2 ellipsoids satisfies (8), where, instead of (9), we have for h: h = [Tr(PK)/Tr(PQ] . Here, P(t) is a symmetric positive definite n6 n matrix satisfying the following equation and initial condition at t = T: P ¼PA  A P; PðTÞ¼ CðTÞ: ð10Þ Therefore, for the criterion J=Tr(CQ), the boundary value problem for the matrix Q(t) of globally optimal ellipsoids becomes decoupled and reduces to two initial value problems: a linear one (10) for P(t) (which is to be solved from t = T to t = s) and a nonlinear one defined by Equations (8) and (9) for Q(t). Further simplifications are possible for the criterion J=(Qv,v). Substituting C from 1/2 (6) into (9), we obtain for locally optimal ellipsoids h=[(Kv,v)/(Qv,v) . Here, v = v(t) is a given non-zero vector function. For globally optimal ellipsoids, we have CðTÞ¼ v  v where v is a given constant T T T n-vector. Let us introduce the adjoint vector c(t) satisfying the following initial value problem: c ¼A c; cðTÞ¼ v : ð11Þ Substituting the following expression for P(t): PðtÞ¼ cðtÞ cðtÞð12Þ into (10) and taking into account (6) and (11), we find out that Equations (10) are satisfied. Thus, the solution of Equations (10) is given by (12), where c satisfies Properties of optimal ellipsoids 139 Equations (11). Therefore, in order to find the matrix Q(t) of globally optimal ellipsoids in the case of the criterion J=(Qv,v), one has to solve first the linear n- dimensional initial value problem (11) for c (instead of the n(n + 1)/2-dimensional problem for P) and then a nonlinear initial value problem for Q, given by Equation (8), 1/2 where h=[Kc,c)/(Qc,c)] . 5. Properties of optimal ellipsoids First, let us consider ellipsoids globally optimal in the sense of criterion J=(Qv,v). We shall show that these ellipsoids E(a(t),Q(t)) for all t2 [s,T] touch the reachable sets D(t,s,M) at points x(t) where the normal to the boundary is parallel to the vector c. To prove that, consider first a point x(t)2 D(t,s,M) at which the support plane to D(t,s,M) is orthogonal to c. At this point the expression dðx; cÞ ðxðtÞ; cðtÞÞ ¼ ðxðsÞ; cðsÞÞ þ dt ð13Þ dt attains its maximum with respect to x(s)2 M and u(t),t2 [s,t]. Here, M is defined by Equation (4), and u(t) is bounded by (3). Substituting Equations (1) and (11) into (13) and maximizing the integrand with respect to u(t) over the ellipsoid E(0,G(t)), we obtain 1=2 dðx; cÞ=dt ¼ðf; cÞþðB u; cÞ¼ðf; cÞþðKc; cÞ ; ð14Þ where the matrix K is defined in Equation (8). Calculating the maximum of (x(s),c(s)) over x(s)2 M, we get 1=2 ðxðsÞ; cðsÞÞ ¼ ða ; cðsÞÞ þ ðQ cðsÞ; cðsÞÞ : ð15Þ 0 0 Substituting Equations (14) and (15) into (13), we obtain the following expression for the support function of the reachable set D(t,s,M): 1=2 r ðcðtÞÞ ¼ ða ; cðsÞÞ þ ðQ cðsÞ; cðsÞÞ 0 0 Dðt;s;MÞ ð16Þ 1=2 þ ½ðf; cÞþðKc; cÞ dt: On the other hand, the support function of the approximating ellipsoid E(a(t),Q(t)) is equal to 1=2 r ðcÞ¼ðaðtÞ; cÞþðQðtÞc; cÞ : ð17Þ EðaðtÞ;QðtÞÞ It follows from Equations (7), (8), and (11) that ðaðtÞ; cðtÞÞ ¼ ða ; cðsÞÞ þ ðf; cÞdt; 1=2 1=2 1=2 ðQðtÞcðtÞ; cðtÞÞ ¼ðQ cðsÞ; cðsÞÞ þ ðKc; cÞ dt: s 140 F. L. Chernousko Substituting these equations into (17) and comparing the obtained result with (16), we see that the values of the support functions of the sets D(t,s,M) and E(a(t),Q(t)) for the vector c(t) coincide. Since D(t,s,M)( E(a(t)),Q(t)), this means that the boundaries of these sets touch at the point x(t). Outer approximating ellipsoids which touch reachable sets at all time instants were called tight [11]. We have proved that the globally optimal (in the sense of the criterion J=(Qv,v)) ellipsoids are tight [12]. It is clear that globally optimal ellipsoids are also locally optimal for the vector v(t)= c(t), where c is defined by (11). Consider now locally optimal (in the sense of the criterion J=(Qv,v)) ellipsoids for the vector v(t) defined by T 0 vðtÞ¼ cðtÞ; c ¼A c; cðsÞ¼ v : ð18Þ Here, v is an arbitrary vector. Let us fix any time instant T*2 [s,T] and denote v*= v(T*). If the instant T* is taken as a terminal instant for globally optimal ellipsoids and v* as a respective value of the vector v for this instant, then our locally optimal ellipsoids are also globally optimal for the instant T* and vector v*. Thus, our locally optimal ellipsoids for the vector v(t) defined by (18) are, first, globally optimal for all t 5 s and respective v(t) and, second, touch reachable sets at all t 5 s at points, where the normal to the boundary is directed along v(t). The procedure for constructing these ellipsoids is rather simple. One is to solve the linear initial value problem for a(t) defined by (7) and also the initial value problem for the system consisting of Equation (8) for Q(t) and Equation (18) for v(t)= c(t). Here, 0 0 the vector v can be chosen arbitrarily, and different vectors v correspond to different approximating ellipsoids touching reachable sets at different points. 6. Example Consider a system of second order x_ ¼ x ; x_ ¼ u; juj 1; x ð0Þ¼ x ð0Þ¼ 0 ð19Þ 1 2 2 1 2 for which an exact solution for locally optimal ellipsoids can be found and compared with reachable sets. The optimality criterion is taken as follows: J=(Qv,v) where v =0, v = 1. Hence, the rate of the projection of the outer approximating ellipse onto 1 2 the axis x is minimized. For our example (19), Equations (7) for the centre of the ellipse give: a (t):a (t):0. 1 2 Equations (8) and (9) for this example become _ _ _ Q ¼ 2Q þ hQ ; Q ¼ Q þ hQ ; Q ¼ hQ þ h ; 12 11 22 12 22 11 12 22 ð20Þ 1=2 h ¼ Q ; Q ð0Þ¼ Q ð0Þ¼ Q ð0Þ¼ 0: 11 12 22 The nonlinear initial value problem (20) has the following exact solution: 4 3 t t Q ¼ ; Q ¼ ; Q ¼ t : ð21Þ 11 12 22 3 2 Properties of optimal ellipsoids 141 Thus, the centre of the approximating ellipse stay at the origin of coordinates, and its matrix is given by Equations (21). This ellipse E is shown in Figure 1. For comparison, the exact reachable set D and the approximating ellipse E locally optimal in the sense of volume [3 – 5] are also depicted in Figure 1. All sets are drawn in normalized –2 –1 coordinates x t and x t ; in these variables the sets remain constant. The areas 1 2 V ,V , and V of the reachable set D and ellipsoids E and E , respectively, are D 1 2 1 2 1=2 1 1=2 1 V ¼ 2=3  0:667; V ¼ pð2 3 Þ  0:907; V ¼ 8pð9 5 Þ  1:25: D 1 2 It is evident from these formulas and Figure 1 that ellipse E gives a much better approximation of the reachable set D than ellipse E , even in the sense of volume. This example shows that the ellipsoids optimal in the sense of the criterion J=(Qv,v) may give a rather efficient outer approximation of reachable sets. 7. Transformation of equations Equation (8) for the matrix Q depends on three matrices: A, K, and C. By means of special transformations, we shall simplify this equation both for locally and globally optimal ellipsoids in cases of the criteria J = Tr(CQ)and J=(Qv,v). In the locally optimal case, we make the change of variables [4 – 6]: Q ¼ VQ V ; ð22Þ where V(t) is an invertible n6 n matrix and Q is a new variable. Taking V(t) equal to the fundamental matrix of Equation (1), i.e. V ¼ AV; VðsÞ¼ I; t  s; ð23Þ where I is the unit n6 n matrix, we obtain from Equations (8), (9), (22) and (23): 1 1 1 Q ¼ h Q þ h K ; Q ðsÞ¼ Q ; K ¼ V KðV Þ ; ð24Þ 1=2 h ¼½TrðC K Þ=TrðC Q Þ ; C ¼ V CV: Let the matrix K(t) be positive definite for all t 5 s. By taking 1=2 VðtÞ¼½KðtÞ ; ð25Þ we obtain from Equations (8), (9), (19), and (25): T 1 1=2 1=2 Q ¼ A Q þ Q A þ h Q þ h I; Q ðsÞ¼ K ðsÞQ K ðsÞ; ð26Þ 1=2 1=2 1=2 A ¼ K ðAK  dK =dtÞ; 1=2 1=2 1=2 C ¼ K CK ; h ¼½TrC =TrðC Q Þ : Note that each of Equations (24) and (26) for Q depend only on two matrices: K and * * C ,or A and C , respectively. Thus, without loss of generality, one can always put * * * 142 F. L. Chernousko Figure 1. Approximation of reachable sets by ellipsoids. either A=0 or K = I (in the case of a positive definite matrix K) in Equations (8) and (9). For the criterion J=(Qv,v), the formulas for h in (24) and (26) become simpler: 1=2 h ¼½ðK v ; v Þ=TrðQ v ; v Þ ; v ¼ V v; ð27Þ 1=2 2 1=2 h ¼½v =ðQ v ; v Þ ; v ¼ K v; ð28Þ for the respective cases given by Equations (23) and (25). Consider now equations for globally optimal ellipsoids in the case of the criterion J=Tr(CQ). Here, we use the change of variables: T 1 1 Q ¼ VQ V ; P ¼ðV Þ P V ; ð29Þ where V(t) is the same matrix as in (22), whereas Q and P are new variables. In the * * case of V defined by Equation (23), we obtain from (10) that P (t):C(T). As a result, the equations for the matrix Q (t) take the form (24), where C (t)= V (t)C(T)V(t). * * If the matrix K(t) is positive definite for all t 5 s, we can make the change of variables (29) with V(t) defined by (25). As a result, Equations (8) and (10) for the matrices Q and P take the form: * * T 1 Q ¼ A Q þ Q A þ h Q þ h I; 1=2 1=2 1=2 Q ðsÞ¼ K ðsÞQ K ðsÞ; h ¼½TrP =TrðP Q Þ ; T 1=2 1=2 P ¼P A  A P ; P ðTÞ¼ K ðTÞCðTÞK ðTÞ: Let us now consider the equations of globally optimal ellipsoids for the criterion J=(Qv ,v ). Using the change of variables defined by (29) and (23), we come to T T Properties of optimal ellipsoids 143 Equations (24) for the matrix Q (t), where h is defined by (27) and v (t)= V (t)v . * * * Defining V by (25), we come to the following equations: T 1 Q ¼ A Q þ Q A þ h Q þ h I; 1=2 1=2 1=2 2 Q ðsÞ¼ K ðsÞQ K ðsÞ; h ¼½c =ðQ c ; c Þ ; 1=2 c ¼A c ; c ðTÞ¼ K ðTÞv : 8. Asymptotics near the initial point Consider an important special case, where the initial point is fixed. Then the initial set M in (4) degenerates into a point: a(s)= a ,Q(s) = 0. Hence, the right-hand side of Equation (8) for Q has a singularity at t = s, and the straightforward numerical integration of this equation near t = s is impossible. Let us study the asymptotic behaviour of locally optimal ellipsoids near t = s in the case of Q = 0. Suppose the matrix K in (8) is positive definite; then Equations (8) can be replaced by (26). We have T 1 Q ¼ A Q þ Q A þ h Q þ h I; ð30Þ 1=2 h ¼½TrC =TrðC Q Þ ; Q ðsÞ¼ 0: Here, the matrices A and C are assumed to be smooth functions of time, so that the following expansions hold A ¼ A þ yA þ Oðy Þ; y ¼ t  s  0; 0 1 ð31Þ C ¼ C þ yC þ Oðy Þ: 0 1 Here, A , A , C , and C are constant matrices. Let us find the solution of Equation 0 1 0 1 (30) in the form of a power series in y, i.e. 2 3 4 5 Q ¼ yQ þ y Q þ y Q þ y Q þ Oðy Þ: ð32Þ 1 2 3 4 Here, Q ,Q ,. . . are constant matrices as yet unknown. We substitute (31) and (32) into 1 2 Equation (30) for Q and expand both sides into series in y. By equating coefficients of the obtained series in both sides of the resultant equation, we find the unknown coefficients in Equation (32). After lengthy but straightforward calculations, we obtain Q ¼ 0; Q ¼ I; Q ¼ D ; 1 2 3 0 ð33Þ 2 ½TrðC D Þ TrðC D Þ 0 0 0 0 Q ¼ ðD þ D Þþ I  D ; 4 1 0 3 6TrC 12ðTrC Þ 0 T T where the following notation is introduced: D ¼ðA þ A Þ=2, D ¼ðA þ A Þ=2. 0 0 1 1 0 1 Note that the coefficients Q ,Q ,Q ,Q do not depend on the matrix C . 1 2 3 4 1 Consider two particular cases. 144 F. L. Chernousko 1. Let C = I; this equality corresponds to the criterion J=TrQ. Then we obtain from Equation (33): 2 ðTrD Þ TrD 0 0 Q ¼ ðD þ D Þþ I  D : ð34Þ 4 1 0 3 12n 6n Equations (33) and (34) coincide with those given in [5] for the ellipsoids locally optimal in the sense of volume. Thus, the approximating ellipsoids locally optimal in the sense of the sum of squared semi-axes coincide with the ellipsoids locally optimal in the sense of volume up to the terms of order of O(y ). 2. For the criterion J=(Qv,v), we have C = v v, and it follows from Equation (33) that 2 ðD v; vÞ ðD v; vÞ 0 0 Q ¼ ðD þ D Þþ I  D : 4 1 0 3 12 6 The obtained expansions can be used for starting the numerical integration of Equations (8) near the initial point t = s in case of Q =0. 9. Asymptotics at infinity Let us investigate the asymptotic behaviour at infinity of ellipsoids locally optimal in the sense of the criterion J=(Qv,v). Suppose for simplicity that the matrix K in Equations (8) is positive definite, so that we can use Equations (26). Also, suppose the matrix A is constant and diagonal: A = diag (a , ..., a ), where a 4a 4...4a . 1 n 1 2 n * * Under the assumptions made, the solution Q of Equations (26) is a diagonal matrix, its diagonal elements being positive and equal to the squares of semi-axes of the approximating ellipsoid: Q (t) = diag(y (t),. . .,y (t)). Equation (26) under the assump- 1 n tions made is reduced to equations: y_ ¼ 2a y þ h y þ h ; i ¼ 1; ... ; n: ð35Þ i i  i Here, h is given by Equation (28), where v is assumed to be a constant unit vector, jv j = 1. Omitting the subscripts , we have * * 1=2 h ¼ v y : ð36Þ i1 First, suppose at least one of a is non-negative: a 5 0. Then, since y (t) 5 0, the i n n right-hand side of the nth Equation (35) is positive for all t 5 s,and y (t) grows monotonically with t. If we assume that there exists a bounded limit y ðtÞ! y > 0as t??, then we come to a contradiction: the left-hand side of the nth Equation (35) tends to zero, whereas its right-hand side is non-zero as t??. Hence, y (t)?? as –1 t??. Then, by virtue of (36), h?0 and h ?? as t??. Thus, the right-hand sides of all Equations (35) tend to infinity as t??, and all y (t)?? as t??. Consider now the case where all a are negative. Denote a =– b , b 5 i n n 1 b 5...5b 4 0. Let us rewrite Equations (35): 2 n y_ ¼2b y þ hy þ h ; i ¼ 1; ... ; n; ð37Þ i i i i Properties of optimal ellipsoids 145 and find their stationary solutions by setting the right-hand sides of Equations (37) equal to zero. We obtain y ¼ ; i ¼ 1; ... ; n; ð38Þ h ð2b  h Þ 0 0 where the following notation is introduced: 1=2 2 0 h ¼ v y : ð39Þ i i i1 By substituting y from (38) into (39), we obtain the equation for h : 1 v ¼ : ð40Þ h 2b  h 0 0 i1 Since y  0 and b 4b for all i=1, ..., n, only those h are admissible which lie n i 0 within the interval h 2 (0,2b ). While h changes from 0 to 2b , the left-hand side of 0 n 0 n –1 Equation (40) decreases monotonically from ? to (2b ) , whereas its right-hand side increases from some positive value to ?. Hence, there exists a unique positive root h 2 (0,2b ) of Equation (40). Substituting this root into (39), we obtain a unique 0 n stationary point y ; i ¼ 1; ... ; n, of Equations (37). Numerical investigation of these equations shows that, in a wide range of parameters variation, the stationary point is asymptotically stable and attracts all solutions of the system in the domain y 5 0,i=1, ..., n. 10. Control Consider a system subjected to the control w and perturbation u: x_ ¼ Ax þ Bu þ Ww þ f; t 2½s; T: ð41Þ Here, w(t)is a k-vector of control, W(t) is a given n6 k matrix, T is a fixed terminal instant, and other notation is the same as in Equation (1). The initial conditions are given by (4). Suppose the perturbation u is caused by the imperfection of the control implementation, and the possible magnitude of u grows with the magnitude of the control w. More exactly, we assume that the matrices B in (41) and G in (3) depend on w in such a way that the matrix K from Equations (8) is equal to K ¼ BGB ¼jwj RðtÞ; ð42Þ where R(t) is a given positive definite n6 n matrix. This condition, together with (3), means that the magnitude of the perturbation u grows quadratically with the magnitude of the control w. Using the transformation given by (22) and (23), we will use Equations (24) for the ellipsoids locally optimal in the sense of the criterion J=(Qv,v) with constant v. Taking into account also Equations (27) and (42) and omitting the subscripts, we obtain 146 F. L. Chernousko a ¼ Ww þ f; ð43Þ 2 1=2 1=2 Q ¼jwj ½ðr=qÞ Q þðq=rÞ R; where the following notation is introduced: q=(Qv,v), r=(Rv,v). Let us find the control w(t) which minimizes the functional 0 1=2 2 J ¼ðaðTÞ; vÞþ½qðTÞ þ b jwj dt ð44Þ for Equations (43) describing the evolution of the outer approximating ellipsoids. Here, b is a positive constant. The functional defined by (44) includes the support function for the approximating ellipsoid E(a(T),Q(T)) at the terminal moment T and the quadratic integral cost. Thus, we seek the control w(t) which is, in a certain sense, optimal for the whole ensemble of possible trajectories of Equation (41). Differentiating q=(Qv,v) according to (43), we obtain 2 1=2 q_ ¼ 2jwj ðqrÞ : ð45Þ Instead of the matrix Q, it is sufficient to consider a scalar variable q. Thus, our optimal control problem is considerably simplified. We introduce adjoint variables c and f corresponding to the respective state variables a and q. Here, a and c are n-vectors, and q and f are scalars. The Hamiltonian for our optimal control problem is given by 2 1=2 2 H ¼ðc; Ww þ fÞþ 2jwj ðqrÞ j  bjwj : ð46Þ According to the maximum principle, the optimal control corresponds to the maximum value of H over w. We have 1=2 w ¼ W c=½2b  4ðqrÞ j: ð47Þ The adjoint equations and transversality conditions for our problem are: 2 1=2 1=2 c ¼ 0; j _ ¼jwj ðr=qÞ j; cðTÞ¼v; jðTÞ¼½qðTÞ =2: ð48Þ It follows from Equations (48) and (45) that c and qf are constant. Hence, we have 1=2 cðtÞ¼ v; jðtÞ¼q =2: ð49Þ Inserting (49) into Equation (47), we obtain finally 1=2 wðtÞ¼ W ðtÞv=½2b þ 4ðRðtÞv; vÞ : ð50Þ Thus, in the special case considered here, the control is found in explicit form. Substituting w(t) from (50) into Equations (43) and integrating them under the initial conditions given by (4), we can obtain the parameters of the approximating ellipsoid E(a(t),Q(t)) as functions of time. Properties of optimal ellipsoids 147 11. Conclusions A new criterion for outer optimal ellipsoids approximating reachable sets is discussed. This criterion is associated with the projection of an ellipsoid onto a given direction and has certain advantages. The resulting equations for the evolution of approximating ellipsoids are investigated and simplified. It is shown that, under certain assumptions, globally optimal ellipsoids coincide with locally optimal ones. These ellipsoids touch reachable sets at all time moments. The asymptotic behaviour of ellipsoids near the initial point and at infinity is investigated. A special control problem for an uncertain system is solved in explicit form. Acknowledgements The work is partially supported by the Russian Foundation of Basic Research (Grant 05-01-00647) and by the Grant of the President of the RF for leading scientific schools No. 1627.2003.1. References [1] Schweppe, F.C., 1973, Uncertain Dynamic Systems (Englewood Cliffs, Prentice Hall). [2] Kurzhanski, A.B., 1977, Control and Observation in Uncertainty Conditions (Moscow: Nauka). [3] Chernousko, F.L., 1981, Engineering Cybernetics, 18, No. 3, 3 – 11; No. 4, 3 – 11; No. 5, 5 – 11. [4] Chernousko, F.L., 1988, Estimation of the Phase State for Dynamical Systems (Moscow: Nauka). [5] Chernousko, F.L., 1994, State Estimation for Dynamic Systems (Boca Raton: CRC Press). [6] Chernousko, F.L., 1999, In: I. Elishakoff (Ed.) Whys and Hows in Uncertainty Modelling (Vienna: Springer), pp. 127 – 188. [7] Milanese, M., Norton, J., Piet-Lahanier, H. and Walter, E. (Eds), 1996, Bounding Approaches to System Identification (New York: Plenum Press). [8] Kurzhanski, A.B. and Valyi, I., 1997, Ellipsoidal Calculus for Estimation and Control (Boston: Birkha¨ user). [9] Chernousko, F.L., 2002, Cybernetics and Systems Analysis, No. 2, 85 – 95. [10] Ovseevich, A.I., 1991, In: G.B.Di Masi and A.B. Kurzhansky (Eds) Modelling, Estimation and Control of Systems with Uncertainty (Boston: Birkha¨ user), pp. 324 – 333. [11] Kurzhanski, A.B. and Varaiya, P., 2000, Ellipsoidal Techniques for Reachability Analysis. Lecture Notes in Computer Science, 1790, pp. 202 – 214. [12] Chernousko, F.L. and Ovseevich, A.I., 2003, Doklady Mathematics, 67, 123 – 126.

Journal

Mathematical and Computer Modelling of Dynamical Systems – Taylor & Francis

Published: Jun 1, 2005

Keywords: Uncertain dynamical systems; set-membership modelling; ellipsoidal estimation; reachable sets; control

There are no references for this article.