Comparison between two state estimation techniqueds for linear systems

Comparison between two state estimation techniques for linear systems ? D. Merhy ⇤C. Stoica Maniu ⇤T. Alamo ⇤⇤ E.F. Camacho ⇤⇤ S. Ben Chabane ⇤⇤⇤ ⇤Laboratoire des Signaux et Syst`emes, CentraleSup´elec-CNRS-Univ. Paris-Sud, Universit´e Paris Saclay, Gif-sur-Yvette, France (e-mail: {dory.merhy,cristina.stoica}@supelec.fr). ⇤⇤ Department of Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Camino de los Descubrimientos, 41092 Sevilla, Spain (e-mail: [email protected], eduar[email protected].es). ⇤⇤⇤ GIPSA Lab, Control Department, France (e-mail: [email protected]). Abstract: This paper presents a comparison in terms of accuracy and complexity between two approaches used for state estimation of linear systems: a classic Kalman filter and a guaranteed set-membership state estimation technique. The main goal of this paper is to analyze the advantages of these techniques and to combine them in the future in a new accurate and simple extension that handles system uncertainties and chance constraints. Two academic examples illustrate the main di↵erences between the compared techniques. Keywords: Set-membership estimation, Kalman filter, linear systems, ellipsoidal set 1. INTRODUCTION Generally, process control requires accurate information about the plant. However, the measured variables do not totally describe the behavior of the system. Particularly, the entire system state is not always accessible. This is why it is important to get access to the unknown information using available data/knowledge. Various methods for state estimation are suggested in the literature and they can be divided into two categories. Stochastic approaches such as the Kalman Filter (see Kalman (1960)) assume the prior knowledge of the distribution of the perturbations and the measurement noises (in general Gaussian distribution) taking into account certain characteristics like the mean and the covariance. This assumption can be sometimes unrealistic. Thus deterministic approaches (Bertsekas and Rhodes (1971), Fogel and Huang (1982)) that considers unknown but bounded perturbations and bounded noises have been elaborated. There are several deterministic approaches used for state estimation, like set-membership state estimation (Schweppe (1968)), interval observers (Pourasghar et al. (2016)) or robust filtering methods (El Ghaoui and Calafiore (2001)). In the implementation of set-based deterministic estimation methods, various sets are used: polytopes (Walter and Piet-Lahanier (1989)), zonotopes (Combastel (2003), Alamo et al. (2005), Le et al. (2013)), ellipsoids (Kurzhanski and V´alyi (1996), Durieu et al. (2001), Polyak et al. (2004), Daryin et al. (2006), Daryin and Kurzhanski (2012), Chernousko (1994)). The low complexity of ellipsoids makes them widely used compared to polytopes which o↵er better accuracy of the estimation. Combastel (2015) recently proposed a combi- ?The first author is a first year PhD student. nation between stochastic and deterministic approaches, more exactly a zonotopic Kalman filter. In the present paper, a comparison in terms of accuracy and computation complexity is made between two estimation techniques studied in the litterature: an ellipsoidal setmembership state estimation (Ben Chabane et al. (2014a), Ben Chabane et al. (2014b)) and a classical Kalman filter. The results illustrated in this paper are the main motivation to develop a future extension that will combine the advantages of the two compared techniques: better accuracy and less complexity. The remainder of the paper is organized as follows. Section 2 formulates the state estimation problem for linear systems. Section 3 briefly presents the ellipsoidal setmembership state estimation technique. Section 4 reminds the state estimation using the classical Kalman Filter. Section 5 exposes the comparison between the two techniques. Section 6 proposes two illustrative examples. Finally, conclusions and perspectives are drawn in Section 7. Notation. An interval denoted [a, b] is the set defined by {x2R:axb}.Thus,B= [-1,1] can be denoted as unitary interval. A box ([a1,b 1],...,[an,b n])>is an interval vector. A unitary box in Rnis a box composed by nunitary intervals. The identity matrix of size nis defined by In. A random variable xnormally distributed with mean of ¯x and with variance of 2is represented by x⇠N¯x, 2. 2. PRELIMINARIES AND SETUP Consider the following discrete-time Linear Time Invariant (LTI) system ⇢xk+1 =Axk+Buk+Ewwk yk=Cxk+Duk+Fvvk(1) where xk2Rnxis the state vector of the system, uk2Rnu is the input vector, and yk2Rnyis the measured output vector at sample time k. The matrices A,B,C,D,Ewand Fvhave the appropriate dimensions. Here, wk2Rnxis a vector containing the state perturbations, while vk2Rny contains the measurement noises. Combining the state perturbations and the measurement noises in one vector !k=[ wkvk]>2Rnx+ny, the system (1) can be rewritten in an equivalent form ⇢xk+1 =Axk+Buk+E!k yk=Cxk+Duk+F!k(2) with the matrices E=⇥Ew0nx,ny⇤and F=⇥0ny,nxFv⇤. In this work, we aim to compare an estimate of the state of the system (1) provided by two approaches that are further detailed in Sections 3 and 4. 3. GUARANTEED ELLIPSOIDAL SET-MEMBERSHIP STATE ESTIMATION This section briefly describes the guaranteed ellipsoidal set-membership state estimation proposed by Ben Chabane et al. (2014a) for the system (2). In this context, consider that the initial state x0belongs to the ellipsoid: E(P0,x 0,⇢ 0)={x2Rnx:(xx0)>P0(xx0)⇢0} with the shape matrix P0=P> 00, the center x0and the so called radius ⇢0. Given an ellipsoidal estimation set for xk,with¯xkthe nominal estimated state, the objective of this technique is to obtain an ellipsoidal set estimation for xk+1. Figure 1 illustrates the 2-step procedure (prediction and correction) to calculate the estimation set. At each sample time k, the green set represents the predicted state set. The yellow strip represents the set of states compatible with the measurements yk+1. The blue ellipsoid (which contains the state estimation set) overapproximates the intersection of the predicted state set and the measurement strip. Repeating the procedure at each time kleads to a guaranteed estimation set that contains the state of the system. Fig. 1. State estimation using ellipsoids More precisely, at each time k, the radius of the ellipsoidal set is minimized by solving a Linear Matrix Inequality (LMI) problem (see Ben Chabane et al. (2014a) for more details) min ,Yk,⇢k+1 ⇢k+1 subject to 8 > > > < > > > : "P⇤⇤ 0⇢k+1 ⇢k⇤ PAYkC(PE YkF)!kP#0 ⇢k+1 ⇢k+ 0<<1 (3) for all !k2Bnx+ny,withYk=PLkand the nominal estimated state ¯xk+1 =A¯xk+Buk+Lk(ykC¯xkDuk). The symbol ”*” denotes symmetrical terms. In fact, expression (3) guarantees that the system state xk+1 belongs to the ellipsoid E(P, ¯xk+1,⇢ k+1). An improvement of this method in terms of accuracy is proposed in Ben Chabane et al. (2014b), with the advantage that it can deal with interval uncertainties on the evolution matrix A. The main di↵erence with respect to Ben Chabane et al. (2014a) is the use of the measurement yk+1 together with additional quadratic constraints on the perturbations !k.Thisimprovement allows us to reduce even more the size of the ellipsoidal estimated state set by solving an additional optimization problem min ⇢0 k+1,P 0,¯x0 k+1,H,⌧,µi ⇢0 k+1 subject to 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) with ⌘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 that xk+1 2E(P, ¯xk+1,⇢ k+1), the expression (4) o↵ers an improved ellipsoidal state estimation set E0(P0,¯x0 k+1,⇢ 0 k+1). 4. KALMAN FILTER Recall the LTI system (1) taking into consideration that wkand vkare random, independent white Gaussian noises, with the covariance matrices denoted by Gwand Gv, respectively. Notice that the state is a random Gaussian vector denoted by x⇠N(¯x, ) and particularly the initial state is represented by x0⇠Nx0|1,G 0|1. The Kalman filter design is divided into two steps: •Prediction. A previously estimated state ˆxk1|k1and the linear nominal model (without any perturbation) are used to predict the value of the next estimated state ˆxk|k1as well as the state estimate covariance Gk|k1 ˆxk|k1=Aˆxk1|k1+Buk1(5) Gk|k1=AGk1|k1A>+EwGwE> w(6) •Correction. The current output measurements and the statistical properties of the model are used to correct the state estimation, leading to compute the state estimate covariance Sk=CGk|k1C>+FvGvF> v(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) with Kkthe Kalman gain and Skthe innovation covariance at the sample time k. 5. COMPARISON The main di↵erence between the approaches presented in Sections 3 and 4 can be mainly spotted in terms of system modeling. The ellipsoidal set-membership state estimation Ben Chabane et al. (2014a) guarantees the state estimation bounds within an ellipsoid for any LTI system (1) or (2), while certain requirements should be met in order to efficiently run the classical Kalman filter. The Kalman filter works properly when the LTI model matrices are fixed and do not present parametric uncertainties. The improved set-membership state estimation Ben Chabane et al. (2014b) o↵ers guaranteed bounds for the state estimation despite the presence of possible interval uncertainties on the evolution matrix Aof the system (1) or (2). However, the Kalman filter o↵ers a reduced computation complexity with respect to the considered set-membership estimation method. In fact, the Kalman equations are based on basic matrix operations and the computational complexity can be approximated by the number of multiplications per loop. Using the expressions (5)-(10) and considering the worst case scenario (i.e. full matrices) we can approximate the filter computational complexity to O(N3), with N=max(nx,n y). The computational complexity of the ellipsoidal state estimation method relies on solving a LMI optimization problem. The mincx solver of the Matlab Robust Control Toolbox is based on the interior point method Nesterov and Nemirovski (1994) which is an iterative technique solving a least square problem at each iteration. The complexity of the method in the worst case scenario can be approximated to O(m2.75l1.5)withmthe number of decision variables and lthe number of constraints Vandenberghe and Boyd (1994). Notice that m=(nx+ ny)2+nxny+ 2 and l=2 nx+ny + 3 for the optimization problem (3) and m=0.5(n2 x+n2 y)+2.5nx+1.5ny+2 and l=nx+ny+ 6 for the optimization problem (4). The comparison allows us to conclude that the Kalman filter o↵ers us a better result in terms of complexity, thus faster computations. In terms of accuracy, and for each iteration, the ellipsoidal method computes an ellipsoidal set to which the real state is guaranteed to belong. The set-membership estimation setup (Section 3) o↵ers the possibility to use correlated/uncorrelated perturbations and measurement noises, however the choice of the perturbation bounds needs good knowledge of the plant. The Kalman filter uses the assumption of Gaussian noises, which can be difficult to verify for some real plants. Starting from this results, the aim of our future research work is to combine the advantages of the two presented techniques in order to propose an extented method that handles systems uncertainties (i.e. interval uncertainties in the system matrices) and chance constraints. 6. ILLUSTRATIVE EXAMPLES Two numerical examples are considered in this section to illustrate the comparison of the presented state estimation techniques. Example 1. Consider the following stable LTI system 8 < : xk+1 =0.80.2 0.30.1xk+0.12 0.02 wk yk=[ 21 ]xk+0.2vk (11) In this example, we present the results obtained by the improved guaranteeed elipsoidal set-membership state estimation (4) compared to the results obtained by Kalman filter. In order to make a valid comparison between these two techniques, appropriate assumptions should be taken regarding the initial state, and noises. In fact, we consider that x0⇠Nx0|1,G 0|1and wk⇠N(0,1), vk⇠N(0,1) for the Kalman filter. For the ellipsoidal set-membership approach, the initial state x0belongs to E(P0,x 0|1,⇢ 0), and the perturbations and measurement noises are bounded, i.e. |wk|1 and |vk|1. Notice that x0|1=[ 55 ]>,G0|1=I2,P0= 109I2and ⇢0=2·108. Figure 2 and 3 show the bounds of x1and x2respec- tively after 10 iterations obtained by the ellipsoidal setmembership state estimation method (4) and the Kalman filter. The real state x(red asterix) is always inside the guaranteed bounds (in dashed blue) calculated by the ellipsoidal set-membership method (4). It can be noticed that, in this example, the state estimated with the Kalman filter (black asterix) has a slower convergence and it is not always inside the guaranteed bounds obtained with the improved set-membership method Ben Chabane et al. (2014b). Concerning the computational complexity, the classic Kalman filter takes around 0.21ms per iteration, while the set-membership estimation technique (LMIs (3) and (4)) spends around 9ms to determine the estimation bounds. Example 2. The aim of using an unstable system, in which the states do not converge to 0 is to prove the efficiency of the ellipsoidal method. In this context, we consider the previous example with a di↵erent evolution matrix A, while keeping the same perturbations, noises and initial conditions 8 < : xk+1 =1.50.2 0.30.1xk+0.12 0.02 !k yk=[ 21 ]xk+0.2vk (12) 0246810 Sample time k -6 -4 -2 0 2 4 6 Bounds of x1 Ellipsoidal method Real state Kalman filter Fig. 2. Bounds of x1 0246810 Sample time k -2 -1 0 1 2 3 4 5 Bounds of x2 Ellipsoidal method Real state Kalman filter Fig. 3. Bounds of x2 Figure 4 and its zoom (Fig. 6) show the bounds of x1 (in dashed blue) obtained with the ellipsoidal estimation method. The bounds of x2are illustrated in Fig. 5 and its zoom (Fig. 7). It can be noticed that the real state (red asterix) is guaranteed to be inside these bounds, while it is not the case for the classical Kalman filter (black asterix). 7. CONCLUSION In this paper, a brief comparison has been made between two methodogies used for the state estimation of discretetime linear time invariant systems, subject to perturbations and measurement noises. The guaranteed ellipsoidal set-membership estimation method Ben Chabane et al. (2014b) is compared to the classic Kalman Filter, in terms of accuracy and complexity. The best estimation results (i.e. guaranteed bounds) are obtained with the improved estimation method Ben Chabane et al. (2014b). The main advantage of the Kalman filter is its lower computational complexity. In order to take advantage of the benefits of the two proposed methodologies, future work will consist on finding a new estimation technique that guarantees high accuracy, with a small computational charge. Additionally, 0246810 Sample time k -150 -100 -50 0 50 100 150 200 250 Bounds of x1 Ellipsoidal method Real state Kalman filter Fig. 4. Bounds of x1 0246810 Sample time k -30 -20 -10 0 10 20 30 40 Bounds of x2 Ellipsoidal method Real state Kalman filter Fig. 5. Bounds of x2 5 5.5 6 6.5 7 Sample time k -60 -40 -20 0 20 40 Bounds of x1 Ellipsoidal method Real state Kalman filter Fig. 6. Zoom on the bounds of x1 parametric uncertainties and chance constraints will be considered in future developments. 7 7.2 7.4 7.6 7.8 8 8.2 8.4 8.6 Sample time k -10 -5 0 5 10 15 Bounds of x2 Ellipsoidal method Real state Kalman filter Fig. 7. Zoom on the bounds of x2 REFERENCES Alamo, T., Bravo, J.M., and Camacho, E.F. (2005). Guaranteed state estimation by zonotopes. Automatica, 41, 1035–1043. Ben Chabane, S., Stoica Maniu, C., Alamo, T., Camacho, E.F., and Dumur, D. (2014a). A new approach for guaranteed ellipsoidal state estimation. In Proc. of IFAC World Congress. Cape Town, South Africa. Ben Chabane, S., Stoica Maniu, C., Alamo, T., Camacho, E.F., and Dumur, D. (2014b). Ellipsoidal state estimation for systems with interval uncertainties. In Proc. of IEEE CDC. Los Angeles, United States. Bertsekas, D.P. and Rhodes, I.B. (1971). Recursive state estimation for a set-membership description of uncertainty. IEEE Transaction on Automatic Control, 16(2), 117–128. Chernousko, F.L. (1994). State estimation for dynamic systems. CRC Press, Boca Raton. Combastel, C. (2003). A state bounding observer based on zonotopes. In Proc. of ECC. Cambridge, UK. Combastel, C. (2015). Zonotopes and Kalman observers:gain optimality under distinct uncertainty paradigms and robust convergence. Automatica, 55, 265–273. Daryin, A.N. and Kurzhanski, A.B. (2012). Estimation of reachability sets for large-scale uncertain systems: from theory to computation. In Proc. of 51st IEEE CDC, Maui, Hawaii, USA, 7401–7406. Daryin, A.N., Kurzhanski, A.B., and Vostrikov, I.V. (2006). Reachability approaches and ellipsoidal techniques for closed-loop control of oscillating systems under uncertainty. In Proc. of 51st IEEE CDC, San Diego, CA, USA, 6390–6395. Durieu, C., Walter, E., and Polyak, B. (2001). Multi- Input Multi-Output ellipsoidal state bounding. Journal of Optimization Theory and Applications, 111(2), 273– 303. El Ghaoui, L. and Calafiore, G. (2001). Robust filtering for discrete time systems with bounded noise and parametric unicertainity. IEEE Transactions on Automatic Control, 46(7). Fogel, E. and Huang, Y.F. (1982). On the value of information in system identification-bounded noise case. Automatica, 18, 229–238. Kalman, R.E. (1960). A new approach to linear filtering and prediction problems. Transactions of the ASME– Journal of Basic Engineering, 82(Series D), 35–45. Kurzhanski, A.B. and V´alyi, I. (1996). Ellipsoidal calculus for estimation and control. Birkha¨user Boston. Le, V.T.H., Stoica, C., Alamo, T., Camacho, E.F., and Dumur, D. (2013). Zonotopic guaranteed state estimation for uncertain systems. Automatica, 49(1), 3418–3424. Nesterov, Y. and Nemirovski, A. (1994). Interior point polynomial methods in convex programming: Theory and applications. SIAM, Philadelphia. Polyak, B., Nazin, S.A., Durieu, C., and Walter, E. (2004). Ellipsoidal parameter or state estimation under model uncertainty. Automatica, 40, 1171–1179. Pourasghar, M., Puig, V., and Ocampo-Martinez, C. (2016). Comparison of set-membership and interval observer approaches for state estimation of uncertain systems. In Proc. of ECC. Aalborg, Denmark. Schweppe, F.C. (1968). Recursive state estimation: Unknown but bounded errors and system inputs. IEEE Transaction on Automatic Control, 13(1), 22–28. Vandenberghe, L. and Boyd, S. (1994). Positive definite programming. Mathematical Programming: State of the Art, 276–308. Walter, E. and Piet-Lahanier, H. (1989). Exact recursive polyhedral description of the feasible parameter set for bounded-error models. IEEE Transaction on Automatic Control, 34(8), 911–915.