Distributed Agent-based Dynamic State Estimation over a Lossy Network

Abstract

In this paper, a novel distributed agent-based dynamical system estimation strategy is proposed. Each agent has a local observation space and is interested in a speci c set of system state elements. The agents have the ability of two-way communication with its neighbors (i.e., agents who share at least one state element). At a particular time instant, each agent predicts its state and makes intermediate correction based on its local measurements. Information about the corrected state elements are then exchanged among the neighboring agents. Based on the nal processing of these exchanged information, an agent-based Kalman consensus Filter (AKCF) and uniform weighting based di usion Kalman lter (ADKF) are proposed in the light of well-established theory of distributed Kalman ltering. Two di erent systems are simulated using the proposed lters. The e ect of communication is also investigated by introducing random failures in the communication link among neighboring agents. It is observed that the mean square deviation (MSD) of AKCF is lower than that of ADKF for the scenarios considered. Additionally, the results also demonstrate that the AKCF is more robust to communication link failures than the ADKF.

Keywords

• Kalman consensus lter
• di usion Kalman lter
• random link failure

-

Kalman ltering has been an e ective tool for real-time estimation and tracking of dynamical processes since its rst formulation by R. E. Kalman [ 5 ]. Tracking of a massive physical system (e.g. electric power system) is possible now-a-days by deploying a distributed network of communicable sensors over the occupied geographical region [ 4 ], [ 7 ]. In conventional Kalman lter, the sensors communicate with a single fusion center either directly or hierarchically to send updated measurement information in timely manner. Based on the knowledge of previous state values and overall system dynamics, the fusion center makes a minimum mean squared error (MMSE) prediction of the states. Necessary corrections are made to the predicted states based on sensor measurements. However, the underlying communication and computational burden is considerably high with a centralized Kalman lter. This issue is resolved through distributed implementation of Kalman lters across the sensor network. In this scenario, the sensors have additional responsibility of implementing local Kalman lter and intersensor communication in the neighborhood. The objective of each sensor is to have updated status of the overall system through local prediction and necessary correction based on the type of information (measurement and / or predicted state values) exchanged among the neighbors. Although, the fundamental concept is unchanged, the distributed Kalman lter has evolved through numerous algorithms. Among those, Kalman consensus lter (KCF) [ 10 ], [ 11 ] and di usion Kalman lter (DKF) [ 1 ] are worth mentioning. We refer to [ 8 ] to have a glimpse of the research carried out in this regard. It should be noted that, beside the system dynamics and local observation space, the topology of active sensor network as well as the inter-sensor communication reliability play vital role in successful implementation of the distributed Kalman lters. For KCF, the e ect of lossy sensor network is investigated in [ 12 ] by incorporating a Bernoulli random variable in the consensus step. In [ 2 ], the study is further extended through random addition of nonlinear dynamics as well as the quantization e ect in the sensor communication. On the other hand, the e ect of communication link failures and delays on the di usion Kalman ltering still needs to be investigated. Authors in [ 13 ] propose relative variance and adaptive combination rule for a single stationary parameter estimation. These rules are used to di use the neighborhood information received over noisy communication links.

Dynamic state estimation in a large cyber-physical system (CPS) presents some unique challenges. A typical example is the smart electric power distribution system with thousands of end-users. For such a system, the dimension of corresponding state vector is quite large presenting high computational as well as communication burden for the sensors. As mentioned earlier, in a conventional distributed Kalman ltering setup, each sensor has to regularly store and update the global state vector and estimation error covariance matrix. Thus, it may be impractical to track the high dimensional state vector in its entirety at each communicable sensor. This constraint can be overcome speci cally for sparse large-scale linear system [ 6 ]. In this case, the corresponding transition of states can be re ected on (approximately) banded matrix to spatially decompose the overall dynamics among sensors even when local measurement space projects onto global states. This idea is further extended for system speci c reduced order particle ltering [ 9 ] and distributed observer design for large-scale system partitioned into disjoint areas [ 3 ]. On the contrary, a particular sensor may be interested only on the state elements, which are directly coupled to its local observation space. Some state elements may even be coupled to two or more sensors' observation space. Under these circumstances, each sensor may be relieved to track only the pertinent state elements, thus reducing the size of error covariance matrices and subsequent reduction in computational requirements. In this way, the sensors are acting as agents and the corresponding local Kalman lters are referred to as agent-based Kalman lters.

In this paper, an agent-based general formulation of KCF and DKF is proposed. One is called agent-based KCF (AKCF) and the other one is agent-based DKF (ADKF). Each agent has access to a distinct set of measurements, that are coupled to a subset of global state elements. A set of binary projection matrices are de ned based on the distribution of system state elements over the observation space of the agents. These matrices map the overall system dynamics to agent-speci c state-space model and also de ne the set of neighbors of a particular agent. AKCF and ADKF are developed by proper inclusion of these projection matrices in the basic ltering steps. The application of proposed lters are illustrated with two custom built 3-agent systems to make a comparative performance analysis. The e ect of losses in the inter-agent information exchange is also investigated by allowing random and independent failure of the existing communication links. 1.1

Contributions We summarize the contributions of our work as follows: { Introduce binary projection matrices to form agent-wise local state-space model. { De ne Agent neighborhood based on the sharing of state elements. { Develop AKCF and ADKF where the observation space of each agent is (generally) underdetermined. { Investigate the e ect of communication over the performance of agent-based tracking of the dynamical system.

The rest of the paper is organized as follows. In section 2, general system model is given and projection matrices are de ned accordingly. Detailed description of the proposed AKCF and ADKF are given in section 3 and compared with typical distributed Kalman lter in terms of computation and communication requirements. The modeling of communication e ect is discussed in section 4. In the next section the proposed lters are compared for perfect and lossy communications over two multi-agent systems. 2

System

Model

We consider a system whose dynamics can be modeled in discrete time as 1st order Gauss-Markov Process, i.e., xt = Fxt 1 + wt 1; t = 0; 1; 2; ::: (1) where, the overall system state is represented by the n-dimensional state vector xt at time instant t. The initial values of the state vector elements at t = 1 follow Gaussian distribution with mean and covariance . Unlike [ 6 ], the state transition matrix F 2 Rn n is a general square matrix with spectral radius less than unity. The process noise wt N (0; Q). The underlying physical system is observed by N agents. The linear observation model for the kth agent is, yt;k = Hkxt;k + vt;k; k = 1; 2; :::; N (2) where, the nk-dimensional vector xt;k is Agent k's local state vector a subset of xt. The observation matrix Hk 2 Rmk nk , (mk nk) and the measurement noise vt;k N (0; Rk). Unlike conventional distributed Kalman ltering, a particular agent k attempts to estimate only the local state vector xt;k instead of xt. To incorporate this scenario, we introduce a binary projection matrix Tk such that,

xt;k = Tkxt; k = 1; 2; :::; N: It should be noted that, Tk is an nk n matrix (nk < n). The static set of physical neighbors for the kth agent is de ned based on the overlap/sharing of state elements. Mathematically,

Sk = fi : Pi;kxt;i projects onto Li;kxt;k; 8tg where, Pi;k and Li;k are nk ni and nk nk binary projection matrices, respectively. By default, Pk;k = Lk;k = Ink .

Using the projection matrix Tk, the system dynamics of equation (1) can be written as,

xt;k = TkFxt 1 + wt 1;k; where, wt 1;k = Tkwt 1. Therefore, wt 1;k 2 N (0; Qk). It should be noted that, Qk = TkQT>. The desired dynamical model for kth agent corresponds to, k

xt;k = Fkxt 1;k + wt 1;k; where, FkTk = TkF. Following equation (35) of [ 6 ], Fk = TkFTy . Here, ( )y k refers to the pseudo-inverse of a full row-rank matrix. 3

Proposed Method

The agent-based dynamic state estimation procedure is developed with minimum mean square error (MSE) as the metric of interest. The state vector estimated by the kth agent at discrete time instant i is de ned as,

x^i;kjj = E [xi;kjy0;k; y1;k; :::; yj;k] : The corresponding error covariance matrix is,

Mi;kjj = E (xi;k x^i;kjj )(xi;k x^i;kjj )> : The rst ve steps of estimation are performed according to traditional Kalman ltering, which are represented according to the de nitions given in equations (7) and (8). For the kth agent, (3) (4) (5) (6) (7) (8) { Initialization:

where k = Tk { Prediction: { Minimum Prediction MSE: and The steps described so far constitute the \computation phase" of agent-based Kalman ltering with a complexity of O(n3k) (including matrix inversion). This phase does not require any neighborhood communication. At the last step of estimation, b^t;k is used along with the exchanged information from the neighbors to arrive at the nal estimate of individual agents' local state values. And this step constitute the single \communication phase" in the agent-based formulation. Once the neighborhood information is exchanged, the nal correction in local state estimates can be performed using either consensus [ 11 ] or uniformly di using the exchanged information [ 1 ]. These approaches are called agent-based Kalman consensus lter (AKCF) and Di usion Kalman lter (ADKF), respectively. The mathematical representation of this nal correction step is given below, x^t;kjt = Dk

X Here, xk[j] represents the jth element of agent k's local state vector. (9) (10) (11) (12) (13) (14) (15) (16) { Final Correction: AKCF where, 0 < and vice versa. { Final Correction: ADKF

X i2Sk x^t;kjt = b^t;k + 1. Larger value of allows greater contribution of consensus The above equation mathematically interpret the uniform di usion when there is no loss or failure in the communication network. Certainly, each agent is not required to know the number of agents sharing its local state elements rather the awareness about its neighborhood. Intuitively, each agent counts the number of neighborhood information it receives for a particular state element and decides the uniform weighting accordingly.

It should be noted that in conventional distributed Kalman lters, each local sensor monitors the whole dynamical process with a computational complexity O(n3). Also, the calculations in equations (12) and (13) require two additional communication phases. The rst phase is required to fuse the weighted Gmreanmtm(Hiai>nR(iH1i>ytR;i)i 1fHromi) farlolmthealnletihgehbnoerisghnbeocerss.sitFautseisonthoef sweceoignhdtecdommmeuasnuicrae-tion phase. The proposed method curtails these fusions, reduces the dependency over the neighborhood measurement information exchange and computational complexity is drastically reduced. 4

E ect of Communication

In the proposed method of agent-based ltering, it is evident that only the information about relevant state elements are being exchanged among neighbors. This is illustrated in Fig. 1. In AKCF, the kth agent exchanges information about the predicted state elements obtained in equation (10) with its neighbors. Whereas, in ADKF, the intermediate correction vector obtained in equation (13) is exchanged. Therefore, the inter-agent two way information exchange plays an important role in agent-based Kalman ltering and can be hampered if the underlying communication link fails. These circumstances can be simulated by P ^ i, k xt, i|t-1

AKCF

P ^ k, i xt, k|t-1 P ^ i, k bt, i

ADKF

P ^ k, i bt, k i k i k introducing random link failures (RLF). Mathematically, e ect of RLF can be analyzed by inserting Bernoulli random variables i;k(t) in equations (14) and (15). These random variables have the following probability mass functions, Therefore, the nal correction step of AKCF with RLF is,

X i2Sk x^t;kjt = b^t;k + (17) (18) (19) (20) where, Dt;k = diag (dt;k[ 1 ]; dt;k[ 2 ];

; dt;k[nk]). And for uniform weighting, where, ct;k[j] represents the number of Successfully Received estimates for xk[j] at discrete time instant t. 5

Simulation and Results

We investigate the performance of the proposed lters for two 3-agent systems. The set of global state elements for the 1st system SYS1 is fa; b; c; d; e; f g and that for the 2nd system SYS2 is fa; b; c; d; e; f; g; h; i; j; k; l; mg. The Venn diagrams in Fig. 2 show the agent-wise distribution of the state elements for the two systems. It should be noted that in SYS2, there exist some state elements strictly local to the agents, whereas, each of the state elements is shared between two agents in SYS1. The rest of the parameters of SYS1 and SYS2 are given in Appendix A and B, respectively. The proposed lters are applied to these systems as illustrative examples. 5.1 To investigate the performance of AKCF and ADKF, an estimation error vector associated with each agent is calculated. The estimation error of kth agent at discrete time instant t is, t;k = x^t;kjt

xt;k. t =

A global estimation error vector is formed by stacking t>;1 t>;N >. t;k from all agents,

Agent 3

Agent 3

This vector is used to de ne the mean square deviation (MSD) as follows, MSDt = trace E t t> (21) MSD is used as the gure of merit to compare the performance of AKCF and ADKF. The lower the MSD is, the better. In the upcoming subsections we present the performance of the proposed lters in terms of MSD obtained from simulations. 5.2

Case Study: Perfect Communication In this scenario, all the inter-agent communication links are assumed to be working perfectly. The proposed ADKF is applied to SYS1 with uniform weighting rule (equation (16)). AKCF is applied to SYS1 with di erent values of . MSD is calculated from 1000 independent Monte Carlo trials at each time step. The comparative performance of ADKF and AKCF for SYS1 is shown in Fig. 3. In the same way, AKCF and ADKF is applied to SYS2 and the performance is summarized in Fig. 4. The MSD values from Fig. 3 and Fig. 4 di er from the classical distributed ltering approach [ 1 ] by showing better performance of AKCF, irrespective of the selection of within the prescribed range. In particular, the best performance of AKCF is obtained when is selected to be 0:1 and 0:01 for SYS1 and SYS2, respectively. The optimum values of thus obtained is used in AKCF for the following case study.

103 102 t D S M 101 100 0

Agent Based Kalman Filter, System 1

Agent Based Kalman Filter, System 2 The e ect of inter-agent communication is investigated for SYS1 and SYS2 by using equations (18-20) at the nal correction steps of the proposed lters. For simplicity, the probability of link failure, i;k = ; 8i; k; i 6= k. The MSD is obtained at di erent link failure rates, which is illustrated in Fig. 5 for SYS1. Based on the previous case study, the value of in AKCF is 0:1. The whole procedure AKCF Vs ADKF for System 1, Link Failure Rate = 

ADKF is repeated for SYS2 with the corresponding value of in AKCF being 0:01. Fig. 6 shows the relative performance for SYS2 a ected by imperfect communication. The e ect of faulty inter-agent communication link is insigni cant for AKCF as evident from Fig. 5 and Fig. 6. This is because of relatively small values of chosen for the two systems. On the other hand, a high link failure rate results in less contribution from neighboring agents in the nal correction step of ADKF. It is interesting to see that ADKF performs better when the communication link is highly unreliable. While this may appear counter intuitive, it is in fact a direct consequence of the system parameter choice. These observations suggest that, for the two systems considered in our simulations, the underlying system states are more dependent upon the agent-wise observation space as compared to the system dynamics itself. Nevertheless, the steady-state MSD values are

AKCF Vs ADKF for System 2, Link Failure Rate = 

ADKF smaller for AKCF, irrespective of the choice of value as well as the condition of inter-agent communication link and is more robust than ADKF. However, If the number of agents are increased for a particular dynamical process, the sharing of state elements and size of neighborhood will also increase. As a consequence, the proposed AKCF and ADKF are expected to perform better and exhibit more robustness under faulty communication network. 6

Conclusions and Future Work

An agent-based Kalman consensus and di usion Kalman lter is proposed. Each agent is interested in a distinct subset of state elements and is able to communicate to its neighbors who share at least one state element. The proposed ltering procedures are applied to two multi-agent systems to compare their performance.

The e ect of communication is also observed for the agent-based Kalman lters.

It is observed that AKCF performs better than ADKF for both systems even under random failure of inter-agent communication link. In the future work, it would be worthwhile to investigate the e ect of coupling strength of observation space and system dynamics over the performance of AKCF and ADKF under both perfect and faulty communication link.

Acknowledgment The authors would like to thank the NSF for providing support for this research through award No. CNS-1136040. The views expressed in this paper are of the authors. Appendix A: SYS1 Parameters { State initialization: { Agent-wise observation model: H3 = 6641135::52440068 4486::63847983 26:31:82936 773::38491761 7134::57885658757; R3 = diag(0:3703; 0:3765; 0:2747; 0:3410). = diag(:8; :2; :5; 1:3; :1; :3; :4; 1; :7; 1:2; :9; 3:9; 5:7); Q = diag(1:8; 0:9; 2:7; 3:6; 1; 0:5; 0:1; 4:5; 2; 8; 5; 1:5; 0:3); 2 0:0842 0:0977 0:1113 0:1249 0:1385 0:1520 0:0009 0:0145 0:0281 0:0416 0:0552 0:0688 0:0824 3 6 0:0968 0:1104 0:1240 0:1376 0:1511 0:0118 0:0136 0:0271 0:0407 0:0543 0:0679 0:0814 0:0833 7 66 0:1095 0:1231 0:1367 0:1502 0:0109 0:0127 0:0262 0:0398 0:0534 0:0670 0:0805 0:0941 0:0959 77 66 0:1222 0:1357 0:1493 0:0100 0:0235 0:0253 0:0389 0:0525 0:0661 0:0796 0:0932 0:0950 0:1086 77 66 0:1348 0:1484 0:0090 0:0226 0:0244 0:0380 0:0516 0:0652 0:0787 0:0923 0:1059 0:1077 0:1213 77 66 0:1475 0:0081 0:0217 0:0353 0:0371 0:0507 0:0643 0:0778 0:0914 0:1050 0:1068 0:1204 0:1339 77 F = 66 0:0072 0:0208 0:0344 0:0362 0:0498 0:0633 0:0769 0:0905 0:1041 0:1176 0:1195 0:1330 0:1466 77; 66 0:0199 0:0335 0:0471 0:0489 0:0624 0:0760 0:0896 0:1032 0:1167 0:1186 0:1321 0:1457 0:0063 77 66 0:0326 0:0462 0:0480 0:0615 0:0751 0:0887 0:1023 0:1158 0:1294 0:1312 0:1448 0:0054 0:0190 77 66 0:0452 0:0588 0:0606 0:0742 0:0878 0:1014 0:1149 0:1285 0:1303 0:1439 0:0045 0:0181 0:0317 77 66 0:0579 0:0597 0:0733 0:0869 0:1005 0:1140 0:1276 0:1412 0:1430 0:0036 0:0172 0:0308 0:0443 77 64 0:0706 0:0724 0:0860 0:0995 0:1131 0:1267 0:1403 0:1421 0:0027 0:0163 0:0299 0:0434 0:0570 75 0:0715 0:0851 0:0986 0:1122 0:1258 0:1394 0:1529 0:0018 0:0154 0:0290 0:0425 0:0561 0:0697

2 5:03 1:9 19:88 15:16 5:23 2:1 18:423 H1 = 664144::8525 47::1897 127::1283 83::7489 183::2233 147::4964 1102::0347775; 6:91 2:91 4:45

7:97 4:73 12:60 7:36 215:45 25:53 6:17 46:70 16:23 41:32 32:433 6 5:06 39:37 31:16 0:27 32:76 8:01 20:267 6417:46 39:27 48:45 31:98 15:56 6:85 44:7975

9:14 27:59 2:34 34:65 34:39 42:29 30:44

References

1. Cattivelli , F. , Sayed , A. : Di usion strategies for distributed kalman ltering and smoothing . Automatic Control, IEEE Transactions on 55(9) , 2069 { 2084 ( 2010 )

2. Dong , H. , Wang , Z. , Gao , H.: Distributed ltering for a class of time-varying systems over sensor networks with quantization errors and successive packet dropouts . Signal Processing, IEEE Transactions on 60(6) , 3164 { 3173 ( 2012 )

3. Dor er, F., Pasqualetti , F. , Bullo , F. : Continuous-time distributed observers with discrete communication . Selected Topics in Signal Processing , IEEE Journal of 7(2) , 296 {304 (April 2013 )

4. Farag , H. , El-Saadany , E. , Seethapathy , R.: A two ways communication-based distributed control for voltage regulation in smart distribution feeders . Smart Grid, IEEE Transactions on 3(1) , 271 { 281 ( 2012 )

5. Kalman , R.E. , et al.: A new approach to linear ltering and prediction problems . Journal of basic Engineering 82 ( 1 ), 35 { 45 ( 1960 )

6. Khan , U. , Moura , J.: Distributing the kalman lter for large-scale systems . Signal Processing, IEEE Transactions on 56(10) , 4919 { 4935 ( 2008 )

7. Lo , C.H. , Ansari , N.: Decentralized controls and communications for autonomous distribution networks in smart grid . Smart Grid, IEEE Transactions on 4(1) , 66 { 77 ( 2013 )

8. Mahmoud , M. , Khalid , H.: Distributed kalman ltering: a bibliographic review . Control Theory Applications, IET 7 ( 4 ), 483 { 501 ( 2013 )

9. Mohammadi , A. , Asif , A. : Distributed state estimation for large-scale nonlinear systems: A reduced order particle lter implementation . In: Statistical Signal Processing Workshop (SSP) , 2012 IEEE. pp. 249 { 252 (Aug 2012 )

10. Olfati-Saber , R. : Distributed kalman ltering for sensor networks . In: Decision and Control , 2007 46th IEEE Conference on. pp. 5492 { 5498 ( 2007 )

11. Olfati-Saber , R. : Kalman-consensus lter : Optimality, stability, and performance. In: Decision and Control, 2009 held jointly with the 2009 28th Chinese Control Conference . CDC/ CCC 2009 . Proceedings of the 48th IEEE Conference on . pp. 7036 { 7042 ( 2009 )

12. Yang , W. , Wang , X. , Shi , H. : Optimal consensus-based distributed estimation with intermittent communication . International Journal of Systems Science 42 ( 9 ), 1521 { 1529 ( 2011 )

13. Zhao , X. , Tu , S.Y. , Sayed , A. : Di usion adaptation over networks under imperfect information exchange and non-stationary data . Signal Processing, IEEE Transactions on 60(7) , 3460 { 3475 ( 2012 )