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

Learn More →

Reachability under uncertainty and measurement noise

Reachability under uncertainty and measurement noise 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 prespecified 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 effective 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 prespecified instants of time – ‘the points of correction’. But this information is now confined 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 final 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]). Efficient 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 coefficients A(t), B(t), C(t) and x2R . Here u = u(t)2R is an open-loop control which may be corrected at prespecified 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 Hausdorff 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 specific 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 first 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 different 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 , find 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 , find 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 Hausdorff semidistance between compact + + sets Q, G defined 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 Hausdorff distance is then defined as h(Q, G) = max {h (Q, G), h (G, Q)}. We shall also need the geometric + + (Minkowski) difference of sets Q, G which is defined 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 find þ þ 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 find the sequential maxmin, namely, first consider Stage 1 (t2 [t , t ]), which is to find 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 find (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 specifics 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 specific 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 fixed measurement y . Then the final 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 ) defined 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 defined for a fixed sequence of admissible measurements y[1, . . .., k]. Then the final 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, differences and intersections of convex sets. To calculate such items is a difficult 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 first 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 differences 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 coefficients a define 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 coefficients a define an external ellipsoid Eðx ; X Þ¼EðxðaÞ; XðaÞÞ iff 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 finally 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), find 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 final 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 final set-valued reach set X(t,t , X , m[1,2]) is a union of sets and satisfies 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 finite number of corrections, emphasizing the difference between problems of minmax and maxmin type. 2. We discussed the specific 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 finite- 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 (Springfield, 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 Verification of Hybrid Systems, Verimag, Grenoble. [7] Lygeros, J.C., Tomlin, C. and Sastri, S., 1999, Controllers for Reachability Specifications 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, Identification: 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Mathematical and Computer Modelling of Dynamical Systems Taylor & Francis

Reachability under uncertainty and measurement noise

Download PDF
12 pages

Loading next page...
 
/lp/taylor-francis/reachability-under-uncertainty-and-measurement-noise-f6K7NmcclR

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

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

Abstract

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 prespecified 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 effective 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 prespecified instants of time – ‘the points of correction’. But this information is now confined 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 final 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]). Efficient 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 coefficients A(t), B(t), C(t) and x2R . Here u = u(t)2R is an open-loop control which may be corrected at prespecified 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 Hausdorff 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 specific 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 first 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 different 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 , find 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 , find 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 Hausdorff semidistance between compact + + sets Q, G defined 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 Hausdorff distance is then defined as h(Q, G) = max {h (Q, G), h (G, Q)}. We shall also need the geometric + + (Minkowski) difference of sets Q, G which is defined 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 find þ þ 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 find the sequential maxmin, namely, first consider Stage 1 (t2 [t , t ]), which is to find 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 find (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 specifics 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 specific 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 fixed measurement y . Then the final 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 ) defined 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 defined for a fixed sequence of admissible measurements y[1, . . .., k]. Then the final 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, differences and intersections of convex sets. To calculate such items is a difficult 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 first 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 differences 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 coefficients a define 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 coefficients a define an external ellipsoid Eðx ; X Þ¼EðxðaÞ; XðaÞÞ iff 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 finally 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), find 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 final 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 final set-valued reach set X(t,t , X , m[1,2]) is a union of sets and satisfies 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 finite number of corrections, emphasizing the difference between problems of minmax and maxmin type. 2. We discussed the specific 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 finite- 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 (Springfield, 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 Verification of Hybrid Systems, Verimag, Grenoble. [7] Lygeros, J.C., Tomlin, C. and Sastri, S., 1999, Controllers for Reachability Specifications 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, Identification: 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.

Journal

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

References

  • Optimality and Reachability with Feedback Controls
  • Reach set computation using optimal control
  • Decidability of hybrid systems with rectangular inclusions
  • Identification: a Theory of Guaranteed Estimates