Access the full text.
Sign up today, get DeepDyve free for 14 days.
References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.
Mathematical and Computer Modelling of Dynamical Systems Vol. 11, No. 2, June 2005, 183 – 194 {,{ { ALEXANDER B. KURZHANSKI and PRAVIN VARAIYA Faculty of Computational Mathematics and Cybernetics, Moscow State (Lomonosov) University, 119992, Moscow, Russia. University of Califonia at Berkeley, EECS, ERL, Berkeley, CA, 94720-1774, USA. This paper deals with the problem of reachability under unknown but bounded disturbances and piecewise open-loop controls which may be feedback-corrected at isolated ‘points of correction’. It is presumed that there are hard bounds on the controls and the unknown but bounded items. The open-loop controls are reassigned at prespeciﬁed points of correction on the basis of additional information on the state space variable which arrives at these points. Such information typically comes through a given noisy instantaneous measurement of the state space variable which sometimes may or may not be complemented by information on the forthcoming disturbance. Thus the process is ‘piecewise feedback’ with feedback introduced at points of correction. The described situation is intermediate relative to purely open-loop control and continuous measurement feedback control under uncertainty. The novelty of this paper lies in considering incomplete noisy measurements of the state space variable at points of correction rather than exact complete measurements of these. The paper also describes some numerical algorithms relevant for computer modelling. It is emphasized that eﬀective computational results may be obtained if one relies on ellipsoidal techniques as given by Kurzhanski et al. Keywords: Reachability, measurement feedback, set-membership estimation, open-loop control, feedback control, set-valued analysis, ellipsoidal calculus. 1. Introduction The standard reachability problem is one of the essential topics in control theory [1 – 6]. However, recent applications require the treatment of this problem in a more complicated setting, presuming that the system is subjected to unknown but bounded disturbances ([7 – 10]). The reach set is then taken as the variety of such points that these or their neighbourhoods could be reached despite the unknown disturbances. The notion of such ‘reachability under uncertainty’ is relevant primarily for systems subjected to feedback controls. The respective notions were introduced and thoroughly explained in [10,11]. In these papers it was assumed that the respective feedback control strategies are based on complete and noise-free measurements of the state space variable. In the present paper we discuss computation of domains reachable by a controlled process through available piecewise open-loop controls, despite the unknown input 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/13873950500068831 184 A. B. Kurzhanski and P. Varaiya disturbances, with feedback control corrections allowed at isolated instants of time. If exact reachability is impossible, we introduce the notion of approximate reachability and indicate guaranteed error bounds for such approximations. The additional information for feedback control correction here again arrives at prespeciﬁed instants of time – ‘the points of correction’. But this information is now conﬁned to incomplete noisy measurements of the phase space variable at such points. All the uncertain items are taken to be unknown but bounded. The total process is therefore a combination of piecewise open-loop control and guaranteed (‘set-membership’) estimation as introduced in [10,13]. The ﬁnal reach sets then turn out to be set-valued and ensure guaranteed estimates. Here the controls, the unknown inputs and measurement noise are subjected to geometrical ‘hard’ bounds which are presumed ellipsoidal. However, the suggested computational schemes also allow original box-valued constraints or a combination of both options (see [11]). Eﬃcient numerical solutions through external and internal ellipsoidal-valued approximations of reach sets and their elements are then available. 2. The System Consider the system x_ ¼ AðtÞxðtÞþ BðtÞu þ CðtÞvðtÞ; ð1Þ n p with continuous matrix coeﬃcients A(t), B(t), C(t) and x2R . Here u = u(t)2R is an open-loop control which may be corrected at prespeciﬁed instants of correction thus allowing us to introduce elements of feedback control; v(t)2R is the unknown input disturbance and x(t ) is the initial value for the trajectory x(t,t ,x(t )). 0 0 0 The control u and the uncertain items v, x(t ) are subjected to hard bounds t 5 t 0 0 uðtÞ2PðtÞ; vðtÞ2 QðtÞ; xðt Þ2X ; ð2Þ where P(t), Q(t) are given set-valued functions with convex compact values, continuous 0 n in time in the Hausdorﬀ metric, X is a convex compact set in R . The classes of open- loop controls u(t) and unknown disturbances v(t) subjected to hard bounds of the above will be further denoted as P , Q , respectively. O O In this paper we consider hard bounds of speciﬁc ellipsoidal-valued type, with PðtÞ¼EðpðtÞ; PðtÞÞ ¼ fx : ðx pðtÞ;P ðtÞðx pðtÞÞÞ 1g; ð3Þ where p(t) is the centre and P(t)= P’(t)4 0 is the ‘shape’ matrix of the ellipsoid, so that 1/2 the support function is r(ljE(p,P)) = max{(l,x)jx2E(p,P)} = (l,p)+(l,Pl) . The restrictions Q(t), X are of similar ellipsoidal type. The problems considered in the sequel deal with reachability under open-loop or piecewise open-loop controls. Such problems will be further reduced to those of optimization. We ﬁrst start with open-loop control under uncertainty. 3. Reachability under open-loop controls The problem of open-loop control under uncertain inputs allows several interpreta- tions. Here we shall introduce two basic types of open-loop reach sets which are Reachability under uncertainty and measurement noise 185 diﬀerent from those introduced earlier in [10]. The relations for these sets will be important for further constructions which will be a superposition of such relations. In order to simplify the formal calculations, we transform system (1) without loss of generality, to system x_ ¼ BðtÞu þ CðtÞv; t t : ð4Þ with the same type of constraints on u,v as before (see [9]). For equation (4) consider the following two problems: 0 n Problem 1-1. Given an interval [t , t], a set X and a point x 2R , ﬁnd V ðt; xÞ¼ max min max min dðz; xðt ; t; xðtÞÞÞ; t t ; 0 0 v u z xðtÞ under the conditions z 2 X ; xðtÞ2B ðxÞ; uð Þ 2 U ; vð Þ 2 V : m O O Here 2 2 d ðz; xÞ¼ðz x; z xÞ; B ðxÞ¼fz : ðz x; z xÞ m g: 0 0 0 0 0’ We further assume X = E(x ,X ), X = X 4 0, so that in Problem 1-1 we have 0 0 0 0 z2E(x ,X ), where x , X are known. 0 n Problem 2-1. Given an interval [t , t], a set X , and x2R , ﬁnd V ðt; x; mÞ¼ min max max min dðz; xðt ; t; xðtÞÞÞ; t t ; 0 0 u v z xðtÞ under the conditions z 2X ; xðtÞ2B ðxÞ; uð Þ 2 U ; vð Þ 2 V : m O O Note that d(x,G) = min {d(x,z)jz2G} where G is a closed set in R . Thus d(x,G)= h (x,G), where h (Q, G) is the Hausdorﬀ semidistance between compact + + sets Q, G deﬁned as h ðQ;GÞ ¼ minfE : Gþ EB ð0Þ Qg þ 1 1=2 ¼ max minfðx z; x zÞ j x 2Q; z 2Gg: x z This is precisely the operation used in the above problems. The Hausdorﬀ distance is then deﬁned as h(Q, G) = max {h (Q, G), h (G, Q)}. We shall also need the geometric + + (Minkowski) diﬀerence of sets Q, G which is deﬁned as QG _ ¼ fx : Gþ x Qg: Direct calculations indicate that V – is given by V ðt; x; mÞ¼ dðx;X ðt; t ;X ; mÞÞ; ð5Þ where 186 A. B. Kurzhanski and P. Varaiya 0 0 0 X ðt; t ;X ; mÞ ¼ ððB ð0ÞE _ ðx ; X ÞÞ þ BðsÞPðsÞdsÞ 0 m ð6Þ _ ðCðsÞÞQðsÞds: This yields Lemma 3.1. The following equality is true: X ðt; t ;X ; mÞ¼fx : V ðt; x; mÞ 0g: 7 0 Here X (t, t , X , m) is the open loop reach set (OLRS) of maxmin type, namely, the set of points x2R whose m-neighbourhood B (x) may be reached at time t by system (4) for any disturbance v(t) given in advance, through some u( )2 U , whatever z2X . Assumption 3.1. The following relation is true for some g4 0 Z Z t t BðsÞPðsÞds _ ðCðsÞÞQðsÞds gB ð0Þ: t t 0 0 This assumption ensures B(s)P(s) _ CðsÞQðsÞ 6¼;: and is further presumed true. It is not seriously restrictive, however, since, by increasing the parameter m we may always 7 0 ensure the overall property X (t,t , X , m) 6¼;. Similarly, we may calculate þ 0 V ðt; x; mÞ¼ min max max minfdðx ; xðt ; t; xðtÞÞg u v z xðtÞ under the conditions z 2X ; xðtÞ2B ðxÞ; uð Þ 2 U ; vð Þ 2 V : m 0 0 0 0 0 Having in mind that again X =E(x ,X ), we ﬁnd þ þ 0 V ðt; x; mÞ¼ dðx;X ðt; t ;X ; mÞÞ; ð7Þ where þ 0 0 X ðt; t ;X ; mÞ¼ðB ð0ÞðX _ þ ðCðsÞÞQðsÞdsÞÞ 0 m Z ð8Þ þ BðsÞPðsÞds: This yields Lemma 3.2. The following equality is true þ 0 þ X ðt; t ;X ; mÞ¼fx : V ðt; x; mÞ 0g: ð9Þ 0 Reachability under uncertainty and measurement noise 187 + 0 Here X (t, t , X , m)isan open-loop reach set of minmax type. It consists of all x whose m-neighbourhood B (t) may be reached at time t by system (4) under some control u( )2 U , whatever v(t)2Q(t), t 4 t 4t and z2 X . (With m = 0 it turns out O 0 that X ¼;.) 0 0 Remark 3.1. With X ={x } one should recognize that the OLRS of the maxmin type is the set of points reachable at time t from a given point x for any disturbance v( )2 V , provided the function v(t), t 4 t 4t is communicated to the controller in advance, before the selection of control u(t). The control u( ) is then selected through an anticipative control procedure. On the other hand, for the m-reach set of the minmax type there is no information provided in advance on the realization of v( ), which is realized only after the selection of m. The control u( ) is then selected through a non- anticipative control procedure. We now pass to the main point of this paper – the treatment of corrections under noisy measurement. 4. Reachability with correction and incomplete measurement Let us start from the maxmin problem. Suppose a point of correction t 2 [t ,t] is given. 1 0 In the case of exact and complete measurements we could then consider (compare with [10]). 0 n Problem 1-2. Given a set X , a vector x 2R , numbers m 4 0, m 4 0 and an instant t , 1 2 1 ﬁnd the sequential maxmin, namely, ﬁrst consider Stage 1 (t2 [t , t ]), which is to ﬁnd 0 1 V ðt ; x; m Þ¼ max min max min dðz; xðt ; t; xðt ÞÞ; 1 0 1 1 1 v z xðt Þ 0 0 under the conditions z 2E(x , X ), x(t ) 2B (x), u( )2 U , v( )2 V . 1 m1 0 0 Then at Stage 2 ﬁnd (t2 [t , t]) V ðt; x; m ; m Þ¼ max min max dðz; xðt ; t; xðtÞÞ; 1 1 2 v u z under the conditions V ðt ; z; m Þ 0; xðtÞ2 B ðxÞ; uð Þ 2 P ; vð Þ 2 Q : 1 1 m O O 1 2 Here under complete measurements it is assumed that at time t one uses the additional information for Stage 2 which is the knowledge of the set X ðt ; t ;X ; m Þ¼fz : V ðt ; z; m Þ 0g: 1 0 1 1 1 1 Namely, at Stage 2, one is to start from the set of initial points 0 0 z 2X ðt ; t ;X ; m ÞþB ðxÞ¼X ðt ; t ;X ; m Þ; 1 0 1 m 1 0 1 1 0 7 0 where z2X (t , t , X , m ) is unknown. 1 0 1 Now, passing to the speciﬁcs of this paper, we suppose that the exact value of x(t )is unavailable and only the measurement is given: 188 A. B. Kurzhanski and P. Varaiya y ¼ yðt Þ¼ Hxðt Þþ x; ð10Þ 1 1 1 where H is a given matrix of dimension m6 n and x2R(t)={x: j(t,x) 4 0}. Here j(t,x) is continuous in both variables, convex in x and such that 02 intD – the j* interior of the set D ={x*:j*(t,x*)}5?. The function j*(t,x*) is the Fenchel j* conjugate of j(t,x) in the second variable. The last property ensures that R is bounded. Denote V ðt ; x; y ; m Þ¼ maxfV ðt ; x; m Þ; jðt ; yðt Þ GxÞg: 1 1 1 1 1 1 0 1 where V ðt; x; m Þ¼ dðx;X ðt ; t ;X ; m ÞÞ . 1 0 0 1 0 1 Then fx : V ðt ; x; y ; m Þ 0g¼X ðt ; t ;X ; m Þ\ Yðy Þ 1 1 1 0 1 1 0 1 ð11Þ ¼X ðt ; t ;X ; y ; m Þ; 1 0 1 where 0 0 X ðt ; t ;X ; m Þ¼ ðB ð0ÞX _ Þþ BðsÞPðsÞds 1 0 m ð12Þ _ ðCðsÞÞQðsÞds: Yðy Þ¼ fx : jðt ; yðt Þ Hxðt ÞÞ 0g: 1 1 1 1 We now pass to Problem 1-1-N – the ‘noisy measurement’ variant of Problem 1-1. We observe that Stage 1 is the same as above, in Problem 1-1, while at instant t we assume that given, in addition to the set X ðt ; t ;X ; m Þ , are also the value y = y(t ) 1 0 1 1 1 and the parameters H, R of the measurement equation (10). This allows us to presume that given instead of X ðt ; t ;X ; m Þ is the information (consistency) set X (t , t , 1 0 1 1 0 X , y , m , under measurement y (see [12], [9]). This information set is the level set of 1 1 1 the information function V(t ,x,y ,m ). 1 1 1 In order to formulate Stage 2 one may observe that at time t one of the sets 7 0 X (t ,t ,X ,y ,m ) is available depending on y . In turn, the speciﬁc realization 1 0 1 1 1 y = y*(t )= Gx*+ x* depends on the unknown actual values x 2 1 1 X ðt ; t ;X ; m Þ; x 2Rðt Þ . 1 0 1 0 1 We may now denote Yðt Þ¼fy : y ¼ Hx þ x ; x 2X ðt ; t ;X ; m Þ; x 2R:g 1 1 0 0 1 At Stage 2 under incomplete measurement we have the next problem. Problem 1-2-N: Find V ðt; x; y ; m½1; 2Þ ¼ max min max min dðz; xðt ; t; xðtÞÞÞ; 1 1 v u z xðtÞ under the conditions V ðt ; z; y ; m Þ 0 ; xðtÞ2B ðxÞ ; uð Þ 2 P ; vð Þ 2 Q : 1 1 m 0 0 2 Reachability under uncertainty and measurement noise 189 Denote 0 0 X ðt; t ;X ; y ; m½1; 2Þ ¼ X ðt; t ;X ðt ; t ;X ; y ; m Þ; m Þ 0 1 1 1 0 1 1 2 ¼fx : V ðt; x; y ; m½1; 2Þ 0g; This set was calculated for a given ﬁxed measurement y . Then the ﬁnal reach set 7 0 X (t,t ,X ,m[1,2]) of maxmin type after one correction will be the union of sets 7 0 X (t,t ,X ,y ,m[1,2]) over all admissible realizations of y : 0 1 1 0 0 X ðt; t ;X ; m½1; 2Þ ¼ [fX ðt; t ;X ; y ; m½1; 2Þ jy 2Yðt Þg: ð13Þ 0 0 1 1 1 The following proposition is true. 7 0 Theorem 4.1. The reach set X (t,t ,X ,m[1,2]) of maxmin type under one correction and incomplete measurement is the union (13) of sets X(t,t ,X ,y ,m[1,2]) over all 0 1 y 2Y 2 (t ). 1 1 This is the union of sets (the set of sets) whose (m + m )-neighbourhoods may be 1 2 reached for any disturbance v(t) through some piecewise open-loop control m, whatever the unknown value x(t )2X . Here the control u is subject to one correction at time t 0 1 and depends on the incomplete measurement y = y(t ). 1 1 In more detail we have: 7 0 Lemma 4.1 Each of the sets X (t,t ,X ,y ,m[1,2]) may be written as 0 1 0 0 X ðt; t ;X ; y ; m½1; 2Þ ¼ ðB ð0ÞX _ ðt ; t ;X ; y ; m ÞÞ 0 1 m 1 0 1 1 þ BðsÞPðsÞdsÞ ð14Þ _ ðCðsÞÞQðsÞds: If we introduce the mapping, 0 0 T ðt; t ; mÞX ¼X ðt; t ;X ; mÞ; 0 0 as given in (6), we come to the next statement. Lemma 4.2 0 0 X ðt; t ;X ; y ; m½1; 2Þ ¼ T ðt; t ; m ÞððT ðt ; t ; m ÞX þB ð0ÞÞ \ Yðt ÞÞ: ð15Þ 0 1 1 1 0 m 1 2 1 Suppose we now have several corrections at points t , ... t ,with t 5 t ,t 5 t, and 1 k 0 1 k measurements ðiÞ ðiÞ y ¼ yðt Þ¼ H xðt Þþ x ; i i i (i) (i) (i) subjected to unknown noise x bounded due to the relation j (t ,x 4 0 with (i) functions j of the same class as j and Y(t ) deﬁned as Y(t ). i 1 Then the respective reach set of sequential maxmin type after k corrections and incomplete measurements may be presented as follows: 190 A. B. Kurzhanski and P. Varaiya X ðt; t ;X ; y½1; k; m½1; k þ 1Þ ¼ T ðt; t ; m Þ 0 k kþ1 ðT ðt ; t ; m Þ; ... ; k k1 ðT ðt ; t ; m ÞððT ðt ; t ; m ÞX þE Þ\ Yðt ÞÞ 2 1 1 0 0 1 2 1 \ Yðt ÞþE Þ; ... ;Þ\ Yðt ÞÞ: 2 0 k This set is deﬁned for a ﬁxed sequence of admissible measurements y[1, . . .., k]. Then the ﬁnal reach set will be the union of such sets: X ½t¼ X ðt; t ;X ; m½1; k þ 1Þ ¼ [fX ðt; t ;X ; y½1; k; m½1; k þ 1Þ j y 2 Yðt Þ; i ¼ 1; ... ; kg: i i This is the set of sets whose (m + ... + m )-neighbourhoods may be reached for any 1 k disturbance v(t) through some piecewise open-loop control m, whatever the unknown value x(t )2X . Here the control u is subject to k corrections at instants t ,i=1, ..., k, 0 1 and depends on k incomplete measurements y = y(t ). i i The minmax problem is described similarly. But the basic operation will now consist of calculating the set X (t,t ,X ,m) according to (8) instead of X –(t,t ,X ,m) 0 0 0 0 according to (6). The other parts of the procedure are mostly similar to the maxmin problem. The analytical description of the problem is rather cumbersome, as we see. It is all the more true since here we have to deal with set-valued items. We further indicate a computation scheme based on ellipsoidal calculus [9, [11] which allows us to represent the given solutions in terms of ellipsoidal-valued relations. 5. Ellipsoidal representations When observing the equations of Section 3, one may note that they require calculations of set-valued integrals with varying upper limit, as well as of geometric sums, diﬀerences and intersections of convex sets. To calculate such items is a diﬃcult procedure. It would be easier to model such systems if the solution were rewritten in terms of the ellipsoidal approximations of such items. We shall therefore indicate ellipsoidal modules for such calculations, constructing the ellipsoidal representations along the lines of [9,11]. 7 0 Let us calculate the sets X (t,t ,X ,y,m[1,2]) of Proposition 3.1, assuming 0 0 0 P(t)=E(p(t),P(t)) and X = E(x ,X ), Q(t)=E(q(t),Q(t)) to be ellipsoidal-valued. (i) At Stage 1 we ﬁrst approximate X ðt Þ¼ ðCðsÞÞðqðsÞþEð0; QðsÞÞÞds; X ðt Þ Q 1 P 1 Z ð16Þ ¼ BðsÞðpðsÞþEð0; PðsÞÞÞds: Denote Z Z t t 1 1 x ðt Þ¼ BðsÞpðsÞds; x ðt Þ¼ ðCðsÞÞqðsÞds: p 1 q 1 t t 0 0 Reachability under uncertainty and measurement noise 191 Following [13], we have Eðx ðt Þ; X ðt ÞÞ X ðt ÞEðx ðt Þ;X ðt ÞÞ; q 1 1 Q 1 q 1 1 Q Q where, þ þ 1 0 X ¼ gðtÞX þðgðtÞÞ CðtÞQðtÞC ðtÞ; Q Q 1=2 1=2 0 0 X ¼ X ðSðtÞCðtÞQ ðtÞÞþðQ ðtÞC ðtÞS ðtÞÞX Q Q Q 0 þ gðtÞ > 0; SðtÞS ðtÞ¼ I; X X ¼ X ; X ðt Þ¼ X ðt Þ¼ 0: 0 0 Q Q Q Q Q Similarly, Eðx ðt Þ; X ðt ÞÞ X ðt ÞEðx ðt Þ; X ðt ÞÞ; p 1 1 P 1 p 1 1 P P where þ þ 0 X ¼ pðtÞX þðpðtÞÞ BðtÞPðtÞB ðtÞ; P P 1=2 1=2 0 0 X ¼ X SðtÞBðtÞP ðtÞþþP ðtÞB ðtÞS ðtÞX ; P P P 0 þ pðtÞ > 0; SðtÞS ðtÞ¼ I; X X ¼ X ; X ðt Þ¼ X ðt Þ¼ 0: 0 0 P P P P P (1) (1) (2) (2) (ii) The geometric diﬀerences of two ellipsoids E(x , X ), E(x , X ), (1) (1) (2) (2) X = X ’ 5 0,X = X ’ 5 0 are approximated as ð1Þ ð1Þ ð2Þ ð2Þ þ þ Eðx ; X Þ Eðx ; X ÞE _ ðx ; X ÞEðx ; X Þ; þ ð1Þ ð2Þ where x ¼ x ¼ x x , ð1Þ ð2Þ X ¼ðl þ l Þðl X l X Þ; l > 0; 1 2 1 2 i þ ð1Þ ð2Þ ð1Þ ð2Þ X ¼ðK X K X Þ ðK X K X Þ; and 1 2 1 2 0 0 0 ð1Þ ð1Þ ð1Þ ð2Þ ð2Þ ð2Þ K K ¼ I; i ¼ 1; 2; ðX Þ X ¼ X ; ðX Þ X ¼ X : (1) (1) (2) (2) (iii) The intersection E(x , X ) \E(x , X )=X is approximated as Eðx ; X Þ X Eðx ; X Þ: ð17Þ I I I I I The internal and external ellipsoids of (17) will be sought for as ð1Þ ð1Þ ð2Þ ð2Þ EðxðaÞ; XðaÞÞ ¼ a Eðx ; X Þþ a Eðx ; X Þ; 1 2 where a 4 0, so that 1=2 1=2 ð1Þ ð2Þ rðljEðxðaÞ; XðaÞÞ ¼ ðl; xðaÞÞ þ a ðl; X lÞ þ a ðl; X lÞ ; 1 2 (1) (2) with x(a)= a x + a x . 1 2 (i) (i) 1/2 n Denote f (l)=(l,x )+(l,X l) , l2R . The coeﬃcients a deﬁne an internal i i ellipsoid Eðx ; X Þ¼EðxðaÞ; XðaÞÞ if they satisfy the inequalities I 192 A. B. Kurzhanski and P. Varaiya maxfða f ðlÞþ a f ðlÞÞ=f ðlÞjðl; lÞ 1g 1; ð18Þ 1 1 2 2 i with i = 1,2. The coeﬃcients a deﬁne an external ellipsoid Eðx ; X Þ¼EðxðaÞ; XðaÞÞ iﬀ they satisfy the inequalities minfða f ðlÞþ a f ðlÞÞ=f ðlÞjðl; lÞ 1g 1; ð19Þ 1 1 2 2 i with i = 1,2. It is possible to retain one external and one internal ellipsoid respectively minimalizing or maximizing a positive measure of the set E(x(a), X(a)) over the solutions to inequalities (18) or (19) (see [9] for such measures). (iii-a) The possibly unbounded set fx : Hx 2Eðm; MÞ¼ Rg ¼ X may be approximated by a parametrized family of ellipsoids. Thus, for example, assuming H={D ,0}, x =(m,0}, with D 4 0 diagonal, we may replace X by m m m R Eðx ; M Þ , where M 0 M ¼ : E 1 0 E I (1) (1) ð1Þ ð1Þ Then the intersection Eðx ; X Þ\Eðx ; M Þ¼ Z converges to E(x ,X \ E E X = Z internally, namely, Z Z; 8E > 0and hðZ ; ZÞ! 0; E ! 0: E E Substituting M for M + e I for some k 5 2 and repeating the procedure, we will þ þ obtain an external estimate Z with convergence hðZ; Z Þ! 0(I is a unit m6 m E E matrix). (iv) We ﬁnally remark that the integrals Z Z t t ðCðsÞÞEðqðsÞ; QðsÞÞds; BðsÞEðpðsÞ; PðsÞÞds; t t 1 1 are approximated similarly to those of (16). The sequence of calculations (algorithmic scheme) may now be described as follows. (1) Following (i), calculate the external and internal approximations þ þ Eðx ðtÞ; X ðtÞÞ; Eðx ðtÞ; X ðtÞÞ; Eðx ðtÞ; X ðtÞÞ; Eðx ðtÞ; X ðtÞÞ: q q p p Q Q P P (2) Following (ii), calculate the external and internal ellipsoidal approximations þ 0 0 ð1Þ E ; E for B ð0Þ _ Eðx ; X Þ¼ X , then similar approximations E ; E that ensure m m 1 1 1 1 1 E ðE þEðx ðtÞ; X ðtÞÞÞE _ ðx ðtÞ; X ðtÞÞ p q 1 m P Q þ þ ðE þEðx ðtÞ; X ðtÞÞÞE _ ðx ðtÞ; X ðtÞÞ p q m P Q E : (3) Following (iii-a), ﬁnd external and internal approximations for X . (4) Following (11), (iii), (iii-a), calculate for a given vector y 2Y the approximations E ðy Þ;E ðy Þ that ensure 1 1 1 1 Reachability under uncertainty and measurement noise 193 0 þ E ðy Þ X ðt ; t ;X ; y ; m ÞE ðy Þ: 1 1 0 1 1 1 1 1 (5) As in points (1), (2), following remark (iv) and Lemma 4.1, calculate ﬁnal ellipsoids E (y ), E –(y ) that ensure the approximations 1 1 0 þ E ðy Þ X ðt; t ;X ; y ; m½1; 2Þ E ðy Þ: 1 0 1 1 Then the ﬁnal set-valued reach set X(t,t , X , m[1,2]) is a union of sets and satisﬁes the inclusions [ [ 0 þ fE ðyÞjy 2Yg Xðt; t ;X ; m½1; 2Þ fE ðyÞjy 2Yg: In each of the approximations indicated in the above the relations depend on the parameters g(t), p(t), S(t), S (t), l , K , a , etc. These parameters may be ‘tuned’ for each i i i i direction l2R along which the approximations would be tight. An array of directions is then selected so as to ensure tight approximations by a family of ellipsoids that envelopes the exact items from above and produces unions of ellipsoids which approximate these items internally. (This may be done through identical parallel calculations.) A detailed treatment of tight ellipsoidal approximations is given in [9,11,13]. The case of k4 1 corrections is dealt with by sequentially applying the present scheme. 6. Conclusion 1. In this paper we have treated the problem of reachability under piecewise open- loop control and set-membership uncertainty with a ﬁnite number of corrections, emphasizing the diﬀerence between problems of minmax and maxmin type. 2. We discussed the speciﬁc problem when the information at the points of corrections is incomplete and subjected to measurement noise. 3. We treated the maxmin problem in detail and showed that in the latter case (as also in the minmax case) the reach set has to be treated as consisting of set- valued elements. 4. We indicated an array of ellipsoidal-valued operations whose combination allows us to solve the problem numerically with the techniques of ﬁnite- dimensional calculus and also allows computer animation. 5. The schemes of this paper may be used as prototypes for treating hybrid systems with resets governed by enabling zones (‘guards’) given by ellipsoids or ellipsoidal cylinders similar to X of the above. References [1] Krasovski, N.N., 1971, Rendezvous Game Problems (Springﬁeld, VA: National Technical Information Survey). [2] Lee, E.B. and Markus, L., 1961, Foundations of Optimal Control Theory (New York: Wiley). [3] Leitmann, G., 1982, Optimality and Reachability with Feedback Controls. In: A. Blaquiere and G. Leitmann (Eds) Dynamic Systems and Microphysics (New York: Academic Press). 194 A. B. Kurzhanski and P. Varaiya [4] Kurzhanski, A.B., 1977, Control and Observation under Uncertainty (Moscow: Nauka). [5] Chernousko, F.L., 1994, State Estimation for Dynamic Systems (Boca Raton: CRC Press). [6] Varaiya, P., 1998, Reach set computation using optimal control. In: O. Maler and J. Sifakis (Eds), Proc. of KIT Workshop on Veriﬁcation of Hybrid Systems, Verimag, Grenoble. [7] Lygeros, J.C., Tomlin, C. and Sastri, S., 1999, Controllers for Reachability Speciﬁcations for Hybrid Systems. Automatica, 35, 349 – 370. [8] Puri, A. and Varaiya, P., 1996, Decidability of hybrid systems with rectangular inclusions. In: D. Dill (Ed.) Proc. CAV’ 94, Lecture Notes in Computer Sciences (LNCS), 1066 (Berlin: Springer). [9] Kurzhanski, A.B. and Valyi, I., 1997, Ellipsoidal Calculus for Estimation and Control (Boston: Birkha¨ user). [10] Kurzhanski, A.B. and Varaiya, P., 2002, Reachability under uncertainty. SIAM Journal on Control and Optimization, 41, 181 – 216. [11] Kurzhanski, A.B. and Varaiya, P., 2002, On ellipsoidal techniques for reachability analysis. Part I: External Approximations, Part II: Internal Approximations. Box-valued Constraints. Optimization Methods and Software, 17, 187 – 237. [12] Kurzhanski, A.B., 1988, Identiﬁcation: a Theory of Guaranteed Estimates. In: J.C. Willems (Ed) From Data to Model (Berlin: Springer-Verlag). [13] Kurzhanski, A.B. and Varaiya, P., 2002, Reachability Analysis for Uncertain Systems – The Ellipsoidal Technique. Dynamics of Continuous, Discrete and Impulsive Systems, Series B., 9, 347 – 367.
Mathematical and Computer Modelling of Dynamical Systems – Taylor & Francis
Published: Jun 1, 2005
Keywords: Reachability; measurement feedback; set-membership estimation; open-loop control; feedback control; set-valued analysis; ellipsoidal calculus
You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.