Comparison between two state estimation techniqueds for linear systems

Compa ison be ween wo s a e es ima ion echniques o linea sys ems ? D. Me hy ⇤C. S oica Maniu ⇤T. Alamo ⇤⇤ E.F. Camacho ⇤⇤ S. Ben Chabane ⇤⇤⇤ ⇤Labo a oi e des Signaux e Sys `emes, Cen aleSup´elec-CNRS-Uni . Pa is-Sud, Uni e si ´e Pa is Saclay, Gi -su -Y e e, F ance (e-mail: {do y.me hy,c is ina.s oica}@supelec. ). ⇤⇤ Depa men o Ingenie ´ıa de Sis emas y Au om´a ica, Uni e sidad de Se illa, Camino de los Descub imien os, 41092 Se illa, Spain (e-mail: alamo@ca uja.us.es, edua [email p o ec ed].es). ⇤⇤⇤ GIPSA Lab, Con ol Depa men , F ance (e-mail: so [email protected] enoble-inp. ). Abs ac : This pape p esen s a compa ison in e ms o accu acy and complexi y be ween wo app oaches used o s a e es ima ion o linea sys ems: a classic Kalman il e and a gua an eed se -membe ship s a e es ima ion echnique. The main goal o his pape is o analyze he ad an ages o hese echniques and o combine hem in he u u e in a new accu a e and simple ex ension ha handles sys em unce ain ies and chance cons ain s. Two academic examples illus a e he main di↵e ences be ween he compa ed echniques. Keywo ds: Se -membe ship es ima ion, Kalman il e , linea sys ems, ellipsoidal se 1. INTRODUCTION Gene ally, p ocess con ol equi es accu a e in o ma ion abou he plan . Howe e , he measu ed a iables do no o ally desc ibe he beha io o he sys em. Pa icula ly, he en i e sys em s a e is no always accessible. This is why i is impo an o ge access o he unknown in o ma ion using a ailable da a/knowledge. Va ious me hods o s a e es ima ion a e sugges ed in he li e a u e and hey can be di ided in o wo ca ego ies. S ochas ic app oaches such as he Kalman Fil e (see Kalman (1960)) assume he p io knowledge o he dis ibu ion o he pe u ba ions and he measu emen noises (in gene al Gaussian dis ibu ion) aking in o accoun ce ain cha ac e is ics like he mean and he co a iance. This assump ion can be some imes un ealis ic. Thus de e minis ic app oaches (Be sekas and Rhodes (1971), Fogel and Huang (1982)) ha conside s unknown bu bounded pe u ba ions and bounded noises ha e been elabo a ed. The e a e se e al de e minis ic ap- p oaches used o s a e es ima ion, like se -membe ship s a e es ima ion (Schweppe (1968)), in e al obse e s (Pou asgha e al. (2016)) o obus il e ing me hods (El Ghaoui and Cala io e (2001)). In he implemen a ion o se -based de e minis ic es ima ion me hods, a ious se s a e used: poly opes (Wal e and Pie -Lahanie (1989)), zono opes (Combas el (2003), Alamo e al. (2005), Le e al. (2013)), ellipsoids (Ku zhanski and V´alyi (1996), Du ieu e al. (2001), Polyak e al. (2004), Da yin e al. (2006), Da yin and Ku zhanski (2012), Che nousko (1994)). The low complexi y o ellipsoids makes hem widely used com- pa ed o poly opes which o↵e be e accu acy o he es ima ion. Combas el (2015) ecen ly p oposed a combi- ?The i s au ho is a i s yea PhD s uden . na ion be ween s ochas ic and de e minis ic app oaches, mo e exac ly a zono opic Kalman il e . In he p esen pape , a compa ison in e ms o accu acy and compu a ion complexi y is made be ween wo es ima- ion echniques s udied in he li e a u e: an ellipsoidal se - membe ship s a e es ima ion (Ben Chabane e al. (2014a), Ben Chabane e al. (2014b)) and a classical Kalman il e . The esul s illus a ed in his pape a e he main mo i- a ion o de elop a u u e ex ension ha will combine he ad an ages o he wo compa ed echniques: be e accu acy and less complexi y. The emainde o he pape is o ganized as ollows. Sec- ion 2 o mula es he s a e es ima ion p oblem o lin- ea sys ems. Sec ion 3 b ie ly p esen s he ellipsoidal se - membe ship s a e es ima ion echnique. Sec ion 4 eminds he s a e es ima ion using he classical Kalman Fil e . Sec- ion 5 exposes he compa ison be ween he wo echniques. Sec ion 6 p oposes wo illus a i e examples. Finally, con- clusions and pe spec i es a e d awn in Sec ion 7. No a ion. An in e al deno ed [a, b] is he se de ined by {x2R:axb}.Thus,B= [-1,1] can be deno ed as uni a y in e al. A box ([a1,b 1],...,[an,b n])>is an in e al ec o . A uni a y box in Rnis a box composed by nuni a y in e als. The iden i y ma ix o size nis de ined by In. A andom a iable xno mally dis ibu ed wi h mean o ¯x and wi h a iance o 2is ep esen ed by x⇠N¯x, 2. 2. PRELIMINARIES AND SETUP Conside he ollowing disc e e- ime Linea Time In a ian (LTI) sys em ⇢xk+1 =Axk+Buk+Ewwk yk=Cxk+Duk+F k(1) whe e xk2Rnxis he s a e ec o o he sys em, uk2Rnu is he inpu ec o , and yk2Rnyis he measu ed ou pu ec o a sample ime k. The ma ices A,B,C,D,Ewand F ha e he app op ia e dimensions. He e, wk2Rnxis a ec o con aining he s a e pe u ba ions, while k2Rny con ains he measu emen noises. Combining he s a e pe u ba ions and he measu emen noises in one ec o !k=[ wk k]>2Rnx+ny, he sys em (1) can be ew i en in an equi alen o m ⇢xk+1 =Axk+Buk+E!k yk=Cxk+Duk+F!k(2) wi h he ma ices E=⇥Ew0nx,ny⇤and F=⇥0ny,nxF ⇤. In his wo k, we aim o compa e an es ima e o he s a e o he sys em (1) p o ided by wo app oaches ha a e u he de ailed in Sec ions 3 and 4. 3. GUARANTEED ELLIPSOIDAL SET-MEMBERSHIP STATE ESTIMATION This sec ion b ie ly desc ibes he gua an eed ellipsoidal se -membe ship s a e es ima ion p oposed by Ben Cha- bane e al. (2014a) o he sys em (2). In his con ex , conside ha he ini ial s a e x0belongs o he ellipsoid: E(P0,x 0,⇢ 0)={x2Rnx:(xx0)>P0(xx0)⇢0} wi h he shape ma ix P0=P> 00, he cen e x0and he so called adius ⇢0. Gi en an ellipsoidal es ima ion se o xk,wi h¯xk he nominal es ima ed s a e, he objec i e o his echnique is o ob ain an ellipsoidal se es ima ion o xk+1. Figu e 1 illus a es he 2-s ep p ocedu e (p edic ion and co - ec ion) o calcula e he es ima ion se . A each sample ime k, he g een se ep esen s he p edic ed s a e se . The yellow s ip ep esen s he se o s a es compa ible wi h he measu emen s yk+1. The blue ellipsoid (which con ains he s a e es ima ion se ) o e app oxima es he in e sec ion o he p edic ed s a e se and he measu emen s ip. Repea ing he p ocedu e a each ime kleads o a gua an eed es ima ion se ha con ains he s a e o he sys em. Fig. 1. S a e es ima ion using ellipsoids Mo e p ecisely, a each ime k, he adius o he ellipsoidal se is minimized by sol ing a Linea Ma ix Inequali y (LMI) p oblem (see Ben Chabane e al. (2014a) o mo e de ails) min ,Yk,⇢k+1 ⇢k+1 subjec o 8 > > > < > > > : "P⇤⇤ 0⇢k+1 ⇢k⇤ PAYkC(PE YkF)!kP#0 ⇢k+1 ⇢k+ 0<<1 (3) o all !k2Bnx+ny,wi hYk=PLkand he nominal es ima ed s a e ¯xk+1 =A¯xk+Buk+Lk(ykC¯xkDuk). The symbol ”*” deno es symme ical e ms. In ac , exp ession (3) gua an ees ha he sys em s a e xk+1 belongs o he ellipsoid E(P, ¯xk+1,⇢ k+1). An imp o emen o his me hod in e ms o accu acy is p oposed in Ben Chabane e al. (2014b), wi h he ad an age ha i can deal wi h in e al unce ain ies on he e olu ion ma ix A. The main di↵e ence wi h espec o Ben Chabane e al. (2014a) is he use o he measu emen yk+1 oge he wi h addi ional quad a ic cons ain s on he pe u ba ions !k.Thisimp o emen allows us o educe e en mo e he size o he ellipsoidal es ima ed s a e se by sol ing an addi ional op imiza ion p oblem min ⇢0 k+1,P 0,¯x0 k+1,H,⌧,µi ⇢0 k+1 subjec o 8 > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > : 2 6 6 6 4 ⌧P+C>HC ⇤⇤ ⌘1⌧¯x> k+1P⌘ 2 nx+ny X i=1 µi⇤ P0P0¯x0 k+1 P0 3 7 7 7 5 0, P00, F>HF < nx+ny X i=1 µiTi, ⌧0, ⌧<1, ⇢0 k+1 >⌧⇢ k+1, µi0,i=1,...,n x+ny (4) wi h ⌘1=(yk+1 +Duk+1)>HC and ⌘2=⇢0 k+1 ⌧⇢k+1 + ⌧¯x> k+1P¯xk+1 +(yk+1 +Duk+1)>H(yk+1 +Duk+1). Supposing ha xk+1 2E(P, ¯xk+1,⇢ k+1), he exp ession (4) o↵e s an imp o ed ellipsoidal s a e es ima ion se E0(P0,¯x0 k+1,⇢ 0 k+1). 4. KALMAN FILTER Recall he LTI sys em (1) aking in o conside a ion ha wkand ka e andom, independen whi e Gaussian noises, wi h he co a iance ma ices deno ed by Gwand G , espec i ely. No ice ha he s a e is a andom Gaussian ec o deno ed by x⇠N(¯x, ) and pa icula ly he ini ial s a e is ep esen ed by x0⇠Nx0|1,G 0|1. The Kalman il e design is di ided in o wo s eps: •P edic ion. A p e iously es ima ed s a e ˆxk1|k1and he linea nominal model (wi hou any pe u ba ion) a e used o p edic he alue o he nex es ima ed s a e ˆxk|k1as well as he s a e es ima e co a iance Gk|k1 ˆxk|k1=Aˆxk1|k1+Buk1(5) Gk|k1=AGk1|k1A>+EwGwE> w(6) •Co ec ion. The cu en ou pu measu emen s and he s a is ical p ope ies o he model a e used o co ec he s a e es ima ion, leading o compu e he s a e es ima e co a iance Sk=CGk|k1C>+F G F> (7) Kk=Gk|k1C>S1 k(8) ˆxk|k=ˆxk|k1+Kk(ykCˆxk|k1) (9) Gk|k=(IKkC)Gk|k1(10) wi h Kk he Kalman gain and Sk he inno a ion co a iance a he sample ime k. 5. COMPARISON The main di↵e ence be ween he app oaches p esen ed in Sec ions 3 and 4 can be mainly spo ed in e ms o sys em modeling. The ellipsoidal se -membe ship s a e es ima ion Ben Chabane e al. (2014a) gua an ees he s a e es ima ion bounds wi hin an ellipsoid o any LTI sys em (1) o (2), while ce ain equi emen s should be me in o de o e icien ly un he classical Kalman il e . The Kalman il e wo ks p ope ly when he LTI model ma ices a e ixed and do no p esen pa ame ic unce - ain ies. The imp o ed se -membe ship s a e es ima ion Ben Chabane e al. (2014b) o↵e s gua an eed bounds o he s a e es ima ion despi e he p esence o possible in e - al unce ain ies on he e olu ion ma ix Ao he sys em (1) o (2). Howe e , he Kalman il e o↵e s a educed compu a ion complexi y wi h espec o he conside ed se -membe ship es ima ion me hod. In ac , he Kalman equa ions a e based on basic ma ix ope a ions and he compu a ional complexi y can be app oxima ed by he numbe o mul iplica ions pe loop. Using he exp essions (5)-(10) and conside ing he wo s case scena io (i.e. ull ma ices) we can app oxima e he il e compu a ional complexi y o O(N3), wi h N=max(nx,n y). The compu a ional complexi y o he ellipsoidal s a e es ima ion me hod elies on sol ing a LMI op imiza ion p oblem. The mincx sol e o he Ma lab Robus Con ol Toolbox is based on he in e io poin me hod Nes e o and Nemi o ski (1994) which is an i e a i e echnique sol ing a leas squa e p oblem a each i e a ion. The complexi y o he me hod in he wo s case scena io can be app oxima ed o O(m2.75l1.5)wi hm he numbe o decision a iables and l he numbe o cons ain s Vandenbe ghe and Boyd (1994). No ice ha m=(nx+ ny)2+nxny+ 2 and l=2 nx+ny + 3 o he op imiza ion p oblem (3) and m=0.5(n2 x+n2 y)+2.5nx+1.5ny+2 and l=nx+ny+ 6 o he op imiza ion p oblem (4). The compa ison allows us o conclude ha he Kalman il e o↵e s us a be e esul in e ms o complexi y, hus as e compu a ions. In e ms o accu acy, and o each i e a ion, he ellipsoidal me hod compu es an ellipsoidal se o which he eal s a e is gua an eed o belong. The se -membe ship es ima ion se up (Sec ion 3) o↵e s he possibili y o use co ela ed/unco ela ed pe u ba- ions and measu emen noises, howe e he choice o he pe u ba ion bounds needs good knowledge o he plan . The Kalman il e uses he assump ion o Gaussian noises, which can be di icul o e i y o some eal plan s. S a ing om his esul s, he aim o ou u u e esea ch wo k is o combine he ad an ages o he wo p esen ed echniques in o de o p opose an ex en ed me hod ha handles sys ems unce ain ies (i.e. in e al unce ain ies in he sys em ma ices) and chance cons ain s. 6. ILLUSTRATIVE EXAMPLES Two nume ical examples a e conside ed in his sec ion o illus a e he compa ison o he p esen ed s a e es ima ion echniques. Example 1. Conside he ollowing s able LTI sys em 8 < : xk+1 =0.80.2 0.30.1xk+0.12 0.02 wk yk=[ 21 ]xk+0.2 k (11) In his example, we p esen he esul s ob ained by he imp o ed gua an eeed elipsoidal se -membe ship s a e es- ima ion (4) compa ed o he esul s ob ained by Kalman il e . In o de o make a alid compa ison be ween hese wo echniques, app op ia e assump ions should be aken e- ga ding he ini ial s a e, and noises. In ac , we con- side ha x0⇠Nx0|1,G 0|1and wk⇠N(0,1), k⇠N(0,1) o he Kalman il e . Fo he ellipsoidal se -membe ship app oach, he ini ial s a e x0belongs o E(P0,x 0|1,⇢ 0), and he pe u ba ions and measu emen noises a e bounded, i.e. |wk|1 and | k|1. No ice ha x0|1=[ 55 ]>,G0|1=I2,P0= 109I2and ⇢0=2·108. Figu e 2 and 3 show he bounds o x1and x2 espec- i ely a e 10 i e a ions ob ained by he ellipsoidal se - membe ship s a e es ima ion me hod (4) and he Kalman il e . The eal s a e x( ed as e ix) is always inside he gua an eed bounds (in dashed blue) calcula ed by he ellipsoidal se -membe ship me hod (4). I can be no iced ha , in his example, he s a e es ima ed wi h he Kalman il e (black as e ix) has a slowe con e gence and i is no always inside he gua an eed bounds ob ained wi h he imp o ed se -membe ship me hod Ben Chabane e al. (2014b). Conce ning he compu a ional complexi y, he classic Kalman il e akes a ound 0.21ms pe i e a ion, while he se -membe ship es ima ion echnique (LMIs (3) and (4)) spends a ound 9ms o de e mine he es ima ion bounds. Example 2. The aim o using an uns able sys em, in which he s a es do no con e ge o 0 is o p o e he e iciency o he ellipsoidal me hod. In his con ex , we conside he p e ious example wi h a di↵e en e olu ion ma ix A, while keeping he same pe u ba ions, noises and ini ial condi ions 8 < : xk+1 =1.50.2 0.30.1xk+0.12 0.02 !k yk=[ 21 ]xk+0.2 k (12) 0246810 Sample ime k -6 -4 -2 0 2 4 6 Bounds o x1 Ellipsoidal me hod Real s a e Kalman il e Fig. 2. Bounds o x1 0246810 Sample ime k -2 -1 0 1 2 3 4 5 Bounds o x2 Ellipsoidal me hod Real s a e Kalman il e Fig. 3. Bounds o x2 Figu e 4 and i s zoom (Fig. 6) show he bounds o x1 (in dashed blue) ob ained wi h he ellipsoidal es ima ion me hod. The bounds o x2a e illus a ed in Fig. 5 and i s zoom (Fig. 7). I can be no iced ha he eal s a e ( ed as e ix) is gua an eed o be inside hese bounds, while i is no he case o he classical Kalman il e (black as e ix). 7. CONCLUSION In his pape , a b ie compa ison has been made be ween wo me hodogies used o he s a e es ima ion o disc e e- ime linea ime in a ian sys ems, subjec o pe u ba- ions and measu emen noises. The gua an eed ellipsoidal se -membe ship es ima ion me hod Ben Chabane e al. (2014b) is compa ed o he classic Kalman Fil e , in e ms o accu acy and complexi y. The bes es ima ion esul s (i.e. gua an eed bounds) a e ob ained wi h he imp o ed es ima ion me hod Ben Chabane e al. (2014b). The main ad an age o he Kalman il e is i s lowe compu a ional complexi y. In o de o ake ad an age o he bene i s o he wo p oposed me hodologies, u u e wo k will consis on inding a new es ima ion echnique ha gua an ees high accu acy, wi h a small compu a ional cha ge. Addi ionally, 0246810 Sample ime k -150 -100 -50 0 50 100 150 200 250 Bounds o x1 Ellipsoidal me hod Real s a e Kalman il e Fig. 4. Bounds o x1 0246810 Sample ime k -30 -20 -10 0 10 20 30 40 Bounds o x2 Ellipsoidal me hod Real s a e Kalman il e Fig. 5. Bounds o x2 5 5.5 6 6.5 7 Sample ime k -60 -40 -20 0 20 40 Bounds o x1 Ellipsoidal me hod Real s a e Kalman il e Fig. 6. Zoom on he bounds o x1 pa ame ic unce ain ies and chance cons ain s will be conside ed in u u e de elopmen s. 7 7.2 7.4 7.6 7.8 8 8.2 8.4 8.6 Sample ime k -10 -5 0 5 10 15 Bounds o x2 Ellipsoidal me hod Real s a e Kalman il e Fig. 7. Zoom on he bounds o x2 REFERENCES Alamo, T., B a o, J.M., and Camacho, E.F. (2005). Gua - an eed s a e es ima ion by zono opes. Au oma ica, 41, 1035–1043. Ben Chabane, S., S oica Maniu, C., Alamo, T., Camacho, E.F., and Dumu , D. (2014a). A new app oach o gua an eed ellipsoidal s a e es ima ion. In P oc. o IFAC Wo ld Cong ess. Cape Town, Sou h A ica. Ben Chabane, S., S oica Maniu, C., Alamo, T., Camacho, E.F., and Dumu , D. (2014b). Ellipsoidal s a e es ima- ion o sys ems wi h in e al unce ain ies. In P oc. o IEEE CDC. Los Angeles, Uni ed S a es. Be sekas, D.P. and Rhodes, I.B. (1971). Recu si e s a e es ima ion o a se -membe ship desc ip ion o unce - ain y. IEEE T ansac ion on Au oma ic Con ol, 16(2), 117–128. Che nousko, F.L. (1994). S a e es ima ion o dynamic sys ems. CRC P ess, Boca Ra on. Combas el, C. (2003). A s a e bounding obse e based on zono opes. In P oc. o ECC. Camb idge, UK. Combas el, C. (2015). Zono opes and Kalman ob- se e s:gain op imali y unde dis inc unce ain y pa adigms and obus con e gence. Au oma ica, 55, 265–273. Da yin, A.N. and Ku zhanski, A.B. (2012). Es ima ion o eachabili y se s o la ge-scale unce ain sys ems: om heo y o compu a ion. In P oc. o 51s IEEE CDC, Maui, Hawaii, USA, 7401–7406. Da yin, A.N., Ku zhanski, A.B., and Vos iko , I.V. (2006). Reachabili y app oaches and ellipsoidal ech- niques o closed-loop con ol o oscilla ing sys ems un- de unce ain y. In P oc. o 51s IEEE CDC, San Diego, CA, USA, 6390–6395. Du ieu, C., Wal e , E., and Polyak, B. (2001). Mul i- Inpu Mul i-Ou pu ellipsoidal s a e bounding. Jou nal o Op imiza ion Theo y and Applica ions, 111(2), 273– 303. El Ghaoui, L. and Cala io e, G. (2001). Robus il e ing o disc e e ime sys ems wi h bounded noise and pa a- me ic unice aini y. IEEE T ansac ions on Au oma ic Con ol, 46(7). Fogel, E. and Huang, Y.F. (1982). On he alue o in o ma ion in sys em iden i ica ion-bounded noise case. Au oma ica, 18, 229–238. Kalman, R.E. (1960). A new app oach o linea il e ing and p edic ion p oblems. T ansac ions o he ASME– Jou nal o Basic Enginee ing, 82(Se ies D), 35–45. Ku zhanski, A.B. and V´alyi, I. (1996). Ellipsoidal calculus o es ima ion and con ol. Bi kha¨use Bos on. Le, V.T.H., S oica, C., Alamo, T., Camacho, E.F., and Du- mu , D. (2013). Zono opic gua an eed s a e es ima ion o unce ain sys ems. Au oma ica, 49(1), 3418–3424. Nes e o , Y. and Nemi o ski, A. (1994). In e io poin polynomial me hods in con ex p og amming: Theo y and applica ions. SIAM, Philadelphia. Polyak, B., Nazin, S.A., Du ieu, C., and Wal e , E. (2004). Ellipsoidal pa ame e o s a e es ima ion unde model unce ain y. Au oma ica, 40, 1171–1179. Pou asgha , M., Puig, V., and Ocampo-Ma inez, C. (2016). Compa ison o se -membe ship and in e al obse e app oaches o s a e es ima ion o unce ain sys ems. In P oc. o ECC. Aalbo g, Denma k. Schweppe, F.C. (1968). Recu si e s a e es ima ion: Un- known bu bounded e o s and sys em inpu s. IEEE T ansac ion on Au oma ic Con ol, 13(1), 22–28. Vandenbe ghe, L. and Boyd, S. (1994). Posi i e de ini e p og amming. Ma hema ical P og amming: S a e o he A , 276–308. Wal e , E. and Pie -Lahanie , H. (1989). Exac ecu si e polyhed al desc ip ion o he easible pa ame e se o bounded-e o models. IEEE T ansac ion on Au oma ic Con ol, 34(8), 911–915.