Analysis, design and testing of novel partition-based state estimation and fault detection schemes for large-scale systems

(1)

POLITECNICO DI MILANO

Facolt`

a di Ingegneria dell’Informazione

Master of Science in Automation and Control

Engineering

Analysis, Design and Testing of

Novel Partition-Based

State Estimation and

Fault Detection Schemes

for Large-Scale Systems

Relatore:

Prof. Marcello Farina

Correlatori: Prof. Thomas Parisini

Dr. Francesca Boem

Tesi di Laurea di:

Stefano Attuati

Matr. 837169

(2)

(3)

(4)

(5)

Acknowledgements

This Thesis is the result of my work carried out at Politecnico di Milano and at Imperial College of London.

First of all I would like to thank my thesis supervisor Prof. Marcello Farina for supporting me throughout all the development of my work and for being always patient and reliable.

Special thanks to my thesis supervisor at Imperial College Prof. Thomas Parisini and to Dr. Francesca Boem, for contributing in the development of this Thesis during my stay in London.

I would like to thank my parents and my sister for the support through my educational path, especially in the last five years at Politecnico di Milano.

(6)

(7)

Abstract

This Thesis addresses the study and development of new robust estimation and fault detection methods for large-scale systems featuring Plug and Play capabilities.

Linear discrete-time systems with stochastic Gaussian noise are considered, where the state is not directly measurable.

Two main algorithms for the distributed estimation of the state are treated, the Partiton-Based Kalman Filter, proposed in [3], and the Partition-Based Luenberger Filter, proposed in [2]. The conditions for the algorithms to be employed are studied and a comparison between their limits and effective-nesses is carried out. After the testing of their estimation performance, a fault detection scheme is proposed. For each algorithm, a local diagnoser and the related residual generation mechanism are analysed.

Different detection testing techniques are studied to provide a satisfactory trade-off analysis between false-alarm rates and missed-detection rates. Through the Thesis, simulation tests have been carried out using an academic exam-ple, while a more in-depth study has been performed implementing the full fault detection scheme on a Power Network System case study.

A specific Matlab toolbox (i.e., the Plug and Play toolbox, developed at

Univarsit´a degli Studi di Pavia) has been employed to manage large scale

systems, its code has been studied, modified and adapted in order to imple-ment the above-imple-mentioned algorithms.

(8)

(9)

Sommario

Questa Tesi si concentra sullo studio e sullo sviluppo di metodi innovativi di stima e individuazione di guasti, robusti e sviluppati ad hoc per sistemi di vasta scala e che abbiano propriet´a tali da poter essere impiegati in contesti Plug and Play.

In particolare verranno presi in considerazione sistemi lineari a tempo dis-creto affetti da rumore stocastico. Per tali sistemi si assume che lo stato non sia direttamente misurabile.

L’analisi si concentra su due principali algoritmi per la stima distribuita dello stato, il Partition-Based Kalman filter proposto in [3] e il Partition-Based Lu-enberger Filter proposto in [2]. Nel lavoro di Tesi, le condizioni necessarie per l’applicazione di entrambi gli algoritmi vengono studiate e confrontate mettendo in evidenza i limiti e i punti di forza di entrambi gli approcci. In primo luogo vengono studiate le prestazioni degli algoritmi riguardo alle loro capacit´a di stima, successivamente viene proposto uno schema per l’ in-dividuazione di guasti. Per ogni algoritmo vengono analizzate le unit´a locali di diagnostica e il relativo meccanismo di generazione di residui.

In seguito vengono considerate diverse tecniche per rilevare il guasto at-traverso l’analisi dei segnali generati dagli algoritmi di stima. Questa analisi permette di effettuare un confronto tra tasso di falsi allarmi e tasso di mancate rilevazioni di guasto. Le tecniche considerate consistono in alcune presenti in letteratura e in altre ideate ad hoc per lo schema sotto analisi. La maggior parte delle analisi sono state effettuate utilizzando un esempio accademico,

mentre l’implementazione dello schema completo di rilevazione di guasto ´e

stata fatta su un esempio complesso e ingegneristicamente significativo, i.e., una rete elettrica detta Power Network System.

´

E stato utilizzato un toolbox specifico di Matlab (i.e., il Plug and Play tool-iii

(10)

gli algoritmi di cui sopra.

(11)

List of Tables

2.1 MSE analysis. . . 29

5.1 Variables of a generation area with typical value ranges [14]. (p.u.) stands for “per unit”. . . 93

5.2 Model parameters for systems Σi, i ∈ {1, . . . , 5}. . . 95

5.3 Load of power ∆PLi (p.u.). +∆PLi means a step of required power, hence a decrease of the frequency deviation ∆ωi. . . 96

5.4 Area 2. MSE ∆θ2. . . 99

5.5 Area 2. MSE ∆ω2. . . 100

5.6 Area 2. MSE ∆Pm2. . . 100

5.7 Area 2. MSE ∆Pv2. . . 100

5.8 Empirical and theoretical variances, traces. Area 2. . . 101

(16)

(17)

List of Figures

1.1 Stages of model-based failure detection and isolation. . . 5

1.2 Faults acting on a system. . . 6

1.3 Example of large-scale system coupling graph. . . 8

2.1 Example of distributed estimation scheme. . . 17

2.2 System evolution and estimates, subsystem 1. . . 28

2.3 System evolution and estimates, subsystem 2. . . 28

2.4 Estimation error covariance matrix, subsystem 1. . . 31

2.5 Estimation error covariance matrix, subsystem 2. . . 32

3.1 Plug/Unplug information transmitted, PKF. . . 39

3.2 Plug/Unplug information transmitted, PLF. . . 44

3.3 Spectral radii of Γ and A − LC, PKF. . . 46

3.4 Spectral radii of Γ and A − LC, PLF. . . 46

4.1 Local fault detection scheme. . . 50

4.2 Diagnoser structure. . . 50

4.3 Standard normal distribution, f (rn). . . 55

4.4 (i)Small fault, PKF. . . 59

4.5 (i)Small fault, PKF-empirical. . . 59

4.6 (i)Small fault, PLF. . . 60

4.7 (i)Small fault, PLF-empirical. . . 60

4.8 (ii)Medium fault, PKF. . . 61

4.9 (ii)Medium fault, PKF-empirical. . . 61

4.10 (ii)Medium fault, PLF. . . 62

4.11 (ii)Medium fault, PLF-empirical. . . 62

4.12 (iii)Large fault, PKF. . . 63 xi

(18)

4.15 (iii)Large fault, PLF-empirical. . . 64

4.16 Areas over which the integrals have to be computed (case m=1). 69 4.17 Approach (f). . . 72

4.18 Approach (g). . . 73

4.19 False-alarm rate analysis, empirical. Blue stars, method (f); red stars, method (g); green circle, method (c); purple circle, method (e). . . 76

4.20 False-alarm rate analysis, PLF. Blue stars, method (f); red stars, method (g); green circle, method (c); purple circle, method (e). . . 76

4.21 Threshold analysis, empirical. Blue stars, method (f); red stars, method (g); green circle, method (c); purple circle, method (e). . . 77

4.22 Threshold analysis, PLF. Blue stars, method (f); red stars, method (g); green circle, method (c); purple circle, method (e). 77 4.23 False-alarm and missed-detection rates analysis, empirical, F Aratesingle = 5%. Blue and red stars indicate F Arate using methods (f) and (g); circles indicate M Drate accounting for different fault sizes. 79 4.24 False-alarm and missed-detection rates analysis, PLF, F Aratesingle = 5%. Blue and red stars indicate F Arate using methods (f) and (g); circles indicate M Drate accounting for different fault sizes. 80 4.25 False-alarm and missed-detection rates analysis, empirical, F Aratesingle = 20%. Blue and red stars indicate F Arate using methods (f) and (g); circles indicate M Drate accounting for different fault sizes. 80 4.26 False-alarm and missed-detection rates analysis, PLF, F Aratesingle = 20%. Blue and red stars indicate F Arate using methods (f) and (g); circles indicate M Drate accounting for different fault sizes. 81 4.27 (i)Small fault, PKF. . . 83

4.28 (i)Small fault, PKF-empirical. . . 84

4.29 (i)Small fault, PLF. . . 84

4.30 (i)Small fault, PLF-empirical. . . 85

4.31 (ii)Medium fault, PKF. . . 85 xii

(19)

4.32 (ii)Medium fault, PKF-empirical. . . 86

4.33 (ii)Medium fault, PLF. . . 86

4.34 (ii)Medium fault, PLF-empirical. . . 87

4.35 (iii)Large fault, PKF. . . 87

4.36 (iii)Large fault, PKF-empirical. . . 88

4.37 (iii)Large fault, PLF. . . 88

4.38 (iii)Large fault, PLF-empirical. . . 89

5.1 Power Network System. . . 92

5.2 PNS, 5 areas configuration. . . 95

5.3 Load profiles. . . 96

5.4 Coupling graph, two areas. Consider area 2. . . 101

5.5 Coupling graph, three areas. Consider area 2. . . 101

5.6 Coupling graph, 4 areas. Consider area 2. . . 102

5.7 PNS configuration. Fault on Area 3. . . 103

5.8 Single residual testing, fault H3- reduction from 8 to 4, SN R = 30dB. . . 104

5.9 Single residual testing, fault H3 - reduction from 8 to 0.8, SN R = 30dB. . . 105

5.10 Single residual testing, fault Tg,3 - increment from 0.1 to 1, SN R = 30dB. . . 105

(20)

5.18 Single residual testing, fault Tg,3 - increment from 0.1 to 1,

SN R = 10dB. . . 109 5.19 Single residual testing, fault Tg,3 - increment from 0.1 to 10,

SN R = 10dB. . . 110

5.20 Residual window testing, fault H3 - reduction from 8 to 4,

SN R = 30dB. . . 111

5.21 Residual window testing, fault H3 - reduction from 8 to 0.8,

SN R = 30dB. . . 112

5.22 Residual window testing, fault Tg,3 - increment from 0.1 to 1,

SN R = 30dB. . . 112 5.23 Residual window testing, fault Tg,3 - increment from 0.1 to 10,

SN R = 30dB. . . 113

SN R = 20dB. . . 113

SN R = 20dB. . . 114

SN R = 20dB. . . 115

SN R = 10dB. . . 115

SN R = 10dB. . . 116

SN R = 10dB. . . 117 5.32 Power Network System, events. . . 119

(21)

xv

5.33 Residual window testing (m = 1), Area 3, fault Tg,3 -

incre-ment from 0.1 to 10, SN R = 20dB. Green triangle defines the plugin of Area 4. Red triangle defines the unplug of Area 3, as consequence of the fault detection. . . 120

(22)

(23)

Chapter 1 Introduction

One of the most important tasks assigned to the computers supervising com-plex process plants is the detection and diagnosis of faults. As stated in [7], for the improvement of reliability, safety and efficiency, advanced methods of supervision, fault detection and fault diagnosis become increasingly im-portant for many technical processes. This holds especially for safety-related processes like aircrafts, trains, automobiles, power plants and chemical plants.

1.1 System monitoring

As shown in [4] and further discussed in [5], system faults can be seen as disturbances acting on the plant under control, see Fig.1.2. In general they are deviations in the normal behaviour of the plant or its instrumentation. The nature of faults can be diversified in

Additive process faults, i.e. unknown inputs acting on plant. The presence of these faults cause a change in the plant outputs which is not related to the value taken by the known inputs. For example, a leakage in a water tank.

Multiplicative process faults, i.e. changes of the plant parameters. These faults cause a change in the plant outputs which depends also on the known inputs. For example, a change in the inertia of a power network.

(24)

Measurement faults, i.e. measurements biases but also abrupt varia-tion of measurements noise variance. These faults are usually described as additive, but in particular situations they may be better charac-terized as multiplicative. For example, a bias on a sensor due to its malfunctioning.

Input faults, i.e. discrepancies between the input command of an actuator and its actual value. These faults are usually modelled as ad-ditive, although sometimes they are better described as multiplicative. For example, an unexpected behaviour of a motor which cannot provide the nominal torque.

The problems related to system monitoring are different and can be described by the following tasks.

Fault Detection, i.e. indication that something is going wrong in the system under monitoring. This is the first and most relevant task to be accomplished in any practical system.

Fault Isolation, i.e. determination of the exact location of the fault (indicating which component of a system is faulty). This task is equally important to the previous one. In fact it grants the possibility to per-form the replacement of the faulty component.

Fault Identification, i.e. determination of the magnitude of the fault. Although this task is very useful, it may not justify the extra effort required.

In the literature, the last two tasks are referred to as fault diagnosis. Among the aforementioned tasks, this Thesis focuses on Fault Detection.

To deal with the problems depicted above, in the literature different ap-proaches have been used. The two main categories are the following.

Model-free methods do not make use of the mathematical model for the plant. Those are usually data-driven techniques, meaning that they are based on the analysis of data coming from sensors and use statistical and logical approaches.

(25)

1.1 System monitoring 3

Model-based methods utilize an explicit mathematical model of the monitored plant. The latter are usually discrete-time models in the form of difference equations or their transformed equivalent. Although most physical systems are nonlinear, the models usually rely on linear approximations.

Some of the most well-known model free approaches are based on the follow-ing ideas.

Physical redundancy, i.e. one can use multiple sensors to measure the same quantity. Discrepancies between measurements indicate a sensor fault. Note that at least three sensors are needed, then a voting scheme can be devised. A remark is that this method involves extra hardware cost and extra weight, the later one can be critical in some specific applications.

Installation of special sensors, i.e. sensors with specific fault de-tection purposes. For example they can measure sound, vibrations, elongation or other quantities that may suggest the occurrence of a fault.

Limit checking of plant measurements, i.e. plant measurements are compared to predefined limits. Exceeding the thresholds results in the declaration of faulty condition. There are usually two kind of thresholds, one indicating warning conditions and the other one in-dicating emergency situations. This approach suffers from two main drawbacks: (i) thresholds need to be set in a very conservative way since the normal variation of plant inputs must not be interpreted as a fault; (ii) it is extremely difficult to identify the faulty component because of the way it propagates to many plant variables.

Frequency analysis of plants measurements, through the analysis of signals spectrum may be possible to perform detection and isolation. Indeed, plant measurements exhibit a typical frequency spectrum under normal operating conditions.

(26)

Expert systems come to a conclusion about the process status con-sidering a set of logical rules. These rules can be based on model-free methods described above. They can be defined as logical expressions, e.g. if symptom 1 ad symptom 2 then conclusion,

On the other hand, model-based approaches can be classified in

Observer-based methods. These methods can be further specified in Unknown Input Observers (UIO), Luenberger observers and Kalman Filters. They involve the use of the mismatch between the observer outputs and the measured system outputs in order to detect a fault. In the following, a simple example is provided.

Parity space methods. These methods involve the use of an input-output model for the system under monitoring. The model input-outputs are then compared with the system ones to test the presence of faults. Parameter estimation methods. These approaches are based on identification techniques, e.g. Recursive Least Square (RLS). They can sense a change in system parameters, indeed they are are the most efficient ones for the detection of multiplicative faults.

Bayesian networks are probabilistic models based on acyclic graphs. They represent a set of stochastic variables and their dependence. The basic idea is that the Bayesian network is a probabilistic model for the system behaviour instead of an analytical one. The fault detection is performed comparing the measured system variables with all the possible conditions for the non-faulty system provided by the network. All the methods listed above are described in detail in the introduction of [9].

As previously shown, model-based methods rely on the idea of analytical re-dundancy. Combining information coming from plant sensors and analytically-obtained values coming from the system model, specific signals are generated. These signals are denoted residuals. Their analysis can eventually lead to the fault detection.

(27)

1.1 System monitoring 5

detection scheme is described next. Consider the LTI system affected by noise described by

x(k + 1) = Ax(k) + w(k) y(k) = Cx(k) + v(k)

Also, consider the state observer defined by the equations ˆ

x(k + 1) = Aˆx(k) + L(y(k) − ˆy(k)) ˆ

y(k) = C ˆx(k)

In the depicted scheme, let us assume that the behaviour of the system under monitoring changes due to a fault. The observer cannot measure the fault, as a result the estimation error will increase. In view of this, one can analyse the trend of signal r(k) = y(k) − ˆy(k) in order to detect the fault. This signal is the residual for the scheme under analysis.

From the example, it is easy to see that the residual behaviour will be af-fected by the noise and by the fault. Indeed, the goal of the fault detection scheme is to distinguish a fault event analysing a noisy signal. This proce-dure is denoted as detection testing, see [5]. In this scenario, the design of the residual generation mechanism plays a fundamental role.

Through the statistical testing of the residuals, a logical pattern is generated, i.e. a signature. Analysing the signatures, information can be inferred about the system status. See Fig.1.1.

Among all the discussed fault detection methods, this Thesis focuses on model-based approaches and in particular on observer-based ones.

(28)

Fig. 1.2: Faults acting on a system.

1.2 Large-scale systems

Large-scale systems are defined as problems whose size may grow enormously. They are characterized by the cooperation of many different parts as ma-chines, reactors, robots, and transportation systems. Their components are linked by common resources, material flows and information networks. Some examples of large-scale systems are

• A fleet of drones in which every flying unit needs to keep a predefined position in order to carry out specific measurements. The fleet can include a large number of drones. Furthermore, the controllers must enable the possibility of adding or removing drones from the fleet with-out affecting the performance of other units.

• A power generation and distribution grid composed by many areas. Each area has generators and loads. It should be possible to change the grid configuration adding or removing areas with respect to their status or working conditions.

Other practical examples are simply the infrastructural systems of everyday use, e.g. road traffic and intermodal transport networks, water networks and electricity networks.

The behaviour of a large-scale system is complex since it is characterized, not only by the dynamics of each interconnected subsystem, but also by the coupling between them. Furthermore, in order to grant the possibility to add

(29)

1.2 Large-scale systems 7

or remove a subsystem without jeopardizing the performance of the overall system, the large-scale system must have some flexibility properties, in the literature denoted as plug-and-play features. An in-depth analysis regarding large-scale systems is carried out in [16] and in [10].

Fig.1.3 shows an example of large-scale system coupling graph. Each subsys-tem evolves according to its dynamics but there exist coupling terms which relate the behaviour of the subsystems with their neighbours.

In order to address control, estimation or fault detection problems for this type of systems, different approaches can be used. The first one is to have a centralized computational unit which collects data from the overall sys-tem and takes decisions for every subsyssys-tem. Note that this approach would require a huge amount of data to be transmitted as well as a huge computa-tional load for the central unit. Furthermore, the growth of the large-scale system makes this situation more and more critical. This means that the centralized approach is not scalable. The task cannot be solved simply using faster computers and larger memories. A new idea is needed in order to de-compose the centralized problem in smaller and independent subproblems, this can grant the scalability properties of the approach.

In view of this, a second method is considered. The basic idea is that each subsystem has its own local computational unit. Each local unit communi-cates with the others in order to provide the desired system performance. This kind of approaches is known in the literature as distributed.

Since in recent years the focus of research is moving toward distributed con-trol and monitoring of large-scale and networked systems, the development of new techniques for making these systems reliable and robust with respect to uncertainties, changes in environment and communication failures has grown in importance.

The problem dealt with in this Thesis is the development of a fault detec-tion and diagnosis scheme ad hoc for large-scale systems with plug and play features.

(30)

Fig. 1.3: Example of large-scale system coupling graph.

1.3 Contribution of the Thesis

The original contributions of this Thesis are the following.

Two recently proposed distributed state estimation algorithms ([3] and [2]) have been analysed and implemented for estimation and fault detection pur-poses.

The distributed estimation schemes have been implemented on an academic example. Extensive and detailed experiments have been carried out regard-ing the algorithms estimation capabilities.

A software tool for the distributed design of both the algorithms has been developed. Algorithms design limits have been also tested on an academic example.

For each algorithm, a fault detection scheme has been implemented and tested.

Alternative detection testing methods from the literature have been studied, compared and implemented for the first time in the devised fault detection schemes. Extensive tests regarding the fault detection performance have been carried out on an academic example.

Finally, the estimation and fault detection schemes have been implemented and extensively tested on a complex system of practical interest, i.e. a power network system.

(31)

1.4 Structure of the Thesis 9

1.4 Structure of the Thesis

The goal of this Thesis is to develop, analyse and test a fault detection scheme for large scale systems with plug and play features. First of all, in Chapter 2 the general system model is described, then the two algorithms for distributed state estimation are illustrated including their equations and properties.

In Chapter 3 the design conditions and the plug and play features of the two algorithms are examined and compared.

In Chapter 4 the fault detection scheme is analysed through the study of local diagnosers, residual generation and detection testing techniques. Finally, in Chapter 5 the implementation of the fault detection schemes on a Power Network System case study is analysed reporting different scenarios and results.

(32)

(33)

Chapter 2 New approaches for

partition-based distributed

state estimation

As discussed in the survey [8], two main classes of estimation techniques for distributed schemes are currently under investigation. In the literature they are generally both referred to as distributed state-estimation algorithms. The first class of problems concerns the case where the full state of the system is estimated by every subsystem, following this approach each subsystem needs to access the information regarding all the subsystems connected into the overall scheme. The other class of algorithms focuses on the estimation of a part of the state vector of the system gathering information only from the neighbouring subsystems: the latter approach is called partition-based esti-mation.

The strategies analysed in this Thesis are based on a partition-based estima-tion approach. The advantages of this strategy from the communicaestima-tion and computational load points of view will be further explained in the following sections.

In this chapter two algorithms are analysed, based on different methods. The main feature of these algorithms is that, besides providing a reliable state estimation with granted properties, they also provide an estimate of the estimation error covariance matrix, later used for fault detection

(34)

pur-poses.

2.1 System model

In this section, the equations of the model used for both the algorithms are described.

Consider a large scale system characterized by the interconnection of M dynamically coupled linear systems. Each of the M interconnected systems is described by the equations:

xi(k + 1) = Aiixi(k) +P

j6=iAijxj(k) + wi(k)

yi(k) = Cixi(k) + vi(k) (2.1)

where x_{i(k) ∈ R}ni _{are the states and y}_{i(k) ∈ R}pi _{are the outputs. Noises}

wi(k) ∈ Rni and vi(k) ∈ Rpi are zero-mean white noises, for i = 1, ..., M , and E{wi(k)wjT(k)} = Qiδij, E{vi(k)vjT(k)} = Riδij, E{wi(k)vjT(h)} = 0 for all i, j = 1, ..., M and h, k ≥ 0. In the above notation δij is the Kronecker delta function, i.e. δij = 1 if i = j and δij = 0 if i 6= j. Furthermore define the set of predecessors of i as Ni = {j|Aij 6= 0} and the set of successors of i as Si = {j|i ∈ Nj}. It is also useful to define the sets of strict predecessors and successors as ˜Ni = Ni\ {i} and ˜Si = Si\ {i}.

As far as the overall system is concerned, the full state and output vectors are x(k) = (x1(k), ..., xM(k)) and y(k) = (y1(k), ..., yM(k)) while the full noise vectors are w(k) = (w1(k), ..., wM(k)) and v(k) = (v1(k), ..., vM(k)). The overall system equations are therefore

x(k + 1) = Ax(k) + w(k)

y(k) = Cx(k) + v(k) (2.2)

where C =diag(C1, ..., CM), Q =diag(Q1, ..., QM), R =diag(R1, ..., RM) and

A =    A11 . . . A1M .. . . .. ... AM 1 . . . AM M   

(35)

2.2 Issues in centralised approaches 13

2.2 Issues in centralised approaches

In this section, the weaknesses related to centralised approaches for the esti-mation in a large scale system framework are analysed.

2.2.1 Centralised Luenberger predictor: filter and

co-variance structure

In a standard centralised approach to the estimation problem, the Luenberger predictor has the form

ˆ

x(k + 1) = Aˆx(k) + L(y(k) − ˆy(k))

ˆ

y(k) = Cˆx(k) (2.3)

Indeed, this estimator gathers the information from the overall system mea-suring all its outputs and estimating all its states. In this process the struc-ture of matrix L is full in order to weight every measured output. Such a gain matrix is computed using a pole placement procedure to properly select the eigenvalues of (A-LC), in such a way that reliable and/or fast estimation can be achieved.

A full gain matrix has the following general structure

L =    L11 . . . L1M .. . . .. ... LM 1 . . . LM M   

Where usually no one of the gains Lij ∀i, j = 1, ..., M is zero, as a result of the pole placement procedure.

The corresponding distributed predictor implementation is, for all i = 1, ..., M

ˆ xi(k + 1) = Aiixˆi(k) + X j∈ ˜Ni Aijxˆj(k) + M X j=1 Lij(yj(k) − ˆyj(k)) (2.4) Where ˆyj(k) = Cjxˆj(k).

Equation (2.4) shows that it is, in principle, possible to implement a dis-tributed estimator. However it has two main criticalities. First, while the

(36)

implementation of the termP

j∈ ˜NiAijxˆj(k) would require some information

transmitted from the predecessors of i only (i.e., the scheme can be supported by a suitable neighbour-to-neighbour transmission network), the implemen-tation of term PM_j=1Lij(yj(k) − ˆyj(k)) would require pieces of information to be transmitted in an all-to-all fashion. This becomes a problem in a dis-tributed context where the goal is to minimise the information transmitted among subsystems. A desired distributed implementation would indeed re-quire that each subsystem should use only the outputs of its neighbours and the resulting structure for the gain matrix should be adjusted to consider this. The matrix L should be sparse in order to weight only specific output measurements in the estimation equation of a given set of states, i.e., one would require that Lij = 0 if j /∈ Ni.

The second problem regards the design phase, which is, as described, purely centralized. This implies that it does not enjoy scalability properties (i.e. as the size of the system grows, the computational effort increases) and that it is not flexible with respect to changes to the system structure or to changes involving only one system at a time.

In some applications, it may be useful to compute explicitly the estimation error covariance matrix, e.g. in fault detection. Regarding it, it is possible to compute its update at each time instant using the following equation.

ΠL(k + 1) = (A − LC)ΠL(k)(A − LC)T + Q + LRLT

Note that this equation is centralised and needs the information about the overall system structure to be computed. In this case it is not trivial to devise a distributed way to perform the update, unless this computation is carried out by each local computing station, which entails a relevant computational effort for large-scale applications.

2.2.2 Centralised Kalman predictor: filter and

covari-ance structure

Consider now a Kalman predictor. The observer structure is the same as in (2.3), but in this case the gain matrix is time varying and is defined by

(37)

2.2 Issues in centralised approaches 15

Where Π(k) is the centralised Kalman prediction error covariance matrix and is computed iteratively using the difference Riccati equation

Π(k + 1) = (A − L(k)C)Π(k)(A − L(k)C)T + Q + L(k)RL(k)T (2.6)

This kind of covariance matrix structure needs the knowledge of the whole system to be computed and, in general, leads to a gain matrix

L(k) =    L11(k) . . . L1M(k) .. . . .. ... LM 1(k) . . . LM M(k)   

which is full, this introduces the same problem depicted in Section 2.2.1. With the Kalman centralised approach is not even possible to devise a scheme similar to that of (2.4) because the gains updates (2.5) need the centralised matrix Π(k) to be computed at each time instant. This means that, while using a Luenberger approach it is possible to have a centralised design and a distributed implementation for the estimate, using the Kalman approach it is not even possible to obtain a distributed estimation procedure.

2.2.3 Partition-based estimation goals

In contrast with the previously described approaches, a partition-based dis-tributed observer scheme should be designed in order to enjoy the following scalability properties

• At most data originated by neighbours should be used by the local estimators;

• Information about the model of the overall system should not be stored by each local estimator, but at most information concerning the neigh-bouring subsystems;

• The computational load required by each local filter should be scalable, both for design and implementation.

(38)

The objective is, therefore, to reduce the communication load of the scheme, memory usage and computation cost.

This also allows for some flexibility and robustness with respect to the net-work structure. It is indeed fundamental to consider that the system config-uration could change due to the plugging or unplugging of a subsystem. A suitable scalable approach should recompute the gains by updating the local estimators once their neighbours are modified.

2.3 Partition-Based Kalman Filter

In this section, the new algorithm proposed in [3] is described through the analysis of its equations and properties. This algorithm will often be referred to as PKF.

2.3.1 Algorithm equations

The algorithm relies on an estimation scheme of the type ˆ

xi(k + 1) = X

j∈Ni

{Aijxj(k) + Lijˆ (k)(yj(k) − Cjxjˆ (k))} (2.7) where

Lij(k) = AijPj(k)CjT(CjPj(k)CjT + Rj)−1 (2.8) and Pi(k), i = 1, ..., M are updated as follows

Pi(k+1) = X

j∈Ni

( ÃijPj(k) ÃTij− ÃijPj(k) ˜CjT( ˜CjPj(k) ˜CjT+ ˜Rj)−1C˜jPj(k) ÃTij)+Qi (2.9) The new matrices used in (2.9) are Ãij =pζjAij, ˜Ci =

√

ζiCi and ˜Ri = ζiRi, for all i, j = 1, ..., M , where ζi = |Si|.

Equation (2.7) is distributed, i.e., Lij 6= 0 only if Aij 6= 0. Also, the

computa-tion of Lij can be done distributedly, and communication is required between

local state estimators of dynamically interconnected subsystems only. Concerning the scalability of the algorithm, observe that, for i ∈ {1, ..., M }, subsystem i permanently stores in memory only the matrices Qi, Ri, Aii, Ci and, for j ∈ Ni, Aij, Cj and Rj; on the other hand, the information which

(39)

2.3 Partition-Based Kalman Filter 17

must be transmitted and temporarily stored at each time step consists of yj, ˆxj, Pj, Lij for all j ∈ Ni. The PKF algorithm is formally described in Algorithm 1.

In Fig.2.1 an example of the distributed estimation scheme is shown along

Algorithm 1

Memory requirements

For i ∈ {1, ..., M }, subsystem i stores in memory - Permanently Qi, Ri, Aii, Ci, {Aij, Cj, Rj; j ∈ ˜Ni} ;

- Temporarily, for each k ≥ 1, {yj(k), ˆxj(k), Pj(k), Lij(k); j ∈ Ni} ; On-line implementation

At each time step k ≥ 1 subsystem i: 1) Measures yi(k);

2) Broadcasts to its successors the quantities yi(k), ˆxi(k) and Pi(k); 3) Gathers from its neighbours the information

{yj(k), ˆxj(k), Pj(k); j ∈ ˜Ni};

4) Computes the gains {Lij(k); j ∈ Ni} as in (2.8);

5) Computes the estimate ˆxi(k + 1) and the matrix Pi(k + 1) as in (2.7) and (2.9);

with the system coupling graph.

Subsys 1

Subsys 2

Subsys 3

(40)

2.3.2 Main properties

Considering the distributed filter estimation error e(k) = x(k) − ˆx(k) where

ˆ

x(k) = (ˆx1(k), ..., ˆxM(k)), its dynamics is given by the equation

e(k + 1) = (A − L(k)C)e(k) − L(k)v(k) + w(k) (2.10)

where L(k) is the matrix whose block entries are Lij(k). In [3] the following main result is provided.

Lemma 1. Assume that the pair (A, G) is stabilizable (where GGT = Q)

and that there exist symmetric matrices ¯Pi ≥ 0, i = 1, ..., M such that ¯

Pi ≥ X

j∈Ni

( ˜AijP¯jA˜Tij − ˜AijP¯jC˜jT( ˜CjP¯jC˜jT + Rj)−1C˜jP¯jA˜Tij) + Qi (2.11)

for all i = 1, ..., M . For all i, j = 1, ..., M , let ¯Lij = AijP¯jCjT(CjP¯jCjT+Rj)−1 and let ¯L be the matrix whose block entries are ¯Lij. Then, the matrix A− ¯LC is Schur stable. A special case of (2.11) is ¯Pi = P j∈Ni( ˜Aij ¯ PjA˜Tij − ˜AijP¯jC˜jT( ˜CjP¯jC˜jT + Rj)−1C˜jP¯jA˜Tij) + Qi, meaning that, if there exist stationary conditions for (2.9), the predictor estimate is stable. Indeed, thanks to Lemma 1, it is

pos-sible to check a condition on matrices Pi in order to state a result about a

property of gains Lij, i.e, the stationarity of the predictor.

Consider, now the distributed estimation error covariance matrix Πd(k) =var(e(k)),

which evolves according to

Πd(k + 1) = (A − L(k)C)Πd(k)(A − L(k)C)T + L(k)RL(k)T + Q (2.12)

It is clear that Πd can be computed only in a centralized way. However, the

covariance matrix updated according to (2.9) can be used for establishing a suitable upper bound of Πd, as proved in [3]. In view of the result stated in Lemma 1, if the assumptions are satisfied, the error covariance is asymptoti-cally convergent to a bounded definite positive matrix, i.e. limk→∞Πd= ¯Πd for some positive definite matrix ¯Πd.

In case Algorithm 1 is implemented, under the assumption that there exist steady-state solutions of ¯Pi ≥ 0, i = 1, ..., M , the next result is proved in [3].

(41)

Proposition 1. Consider Algorithm 1. Assume that Pi(0), i = 1, ..., M ,

is such that there exist ¯Pi with the property that lim

k→∞Pi(k) = ¯Pi (2.13)

Let ¯P =diag( ¯P1, ..., ¯PM). Then, there exists a positive definite matrix ¯Πd such that limk→∞Πd= ¯Πd and ¯Πd≤ ¯P .

Note that, under the validity of (2.13), then in steady state conditions also (2.11) is verified.

Now the conditions for the implementation for the algorithm are analysed from a centralised point of view. Note that the convergence condition is related to the existence of a steady-state for the matrix update (2.9), i.e., guaranteeing condition (2.11). The design phase in this context, consists therefore in verifying this condition. In [3] the design phase can be conducted through two approaches:

(1) Linear Matrix Inequalities are used to solve an optimization problem and find matrices ¯Pi satisfying (2.11);

(2) Small Gain Arguments approach is used to find the conditions guaran-teeing the convergence of the update (2.9).

The remaining part of this section will focus on the second problem, i.e., how to grant the convergence of Pi. The satisfaction of this property is of utmost importance since the divergence of matrices Pi leads to the instability of the algorithm itself.

First of all the following assumption must be fulfilled.

Assumption 1. For any subsystem i, Aii is invertible.

Furthermore one of the following assumptions has to hold in order to properly initialize Pi(0).

Assumption 2. For subsystem i, (i) (Aii, Ci) is detectable;

(42)

Assumption 3. For subsystem i, (i) ( ˜Aii, ˜Ci) is detectable;

(ii) ( ˜Aii, Gi) is stabilizable;

Note that Assumption 2 allows to define, for a given subsystem i, ¯P_iN

as the unique semi-positive definite solution to the local Riccati algebraic equation ¯P_iN = AiiP¯_iNAT_ii− AiiP¯_iNC_iT(CiP¯_iNC_iT + Ri)−1CiP¯_iNAT_ii+ Qi, while Assumption 3 is required to define ˜P_iN as the unique semi-positive definite solution to ˜P_iN = ˜AiiP˜_iNA˜T_ii− ˜AiiP˜_iNC˜_iT( ˜CiP˜_iNC_iT + ˜Ri)−1Ci˜P˜_iNA˜T_ii+ Qi.

Now define full rank ni arbitrary transformation matrices Hi, i = 1, ..., M ,

i.e., Hi _{∈ R}ni×ni_{. These matrices are introduced in [3] to reduce the}

con-servativity of the results stated, they are actually not essential. In order

to simplify the problem one can consider Hi = Ini. Also define gains ¯Li,

selected in such a way that ¯Fi = ˜Aii − ¯LiCi˜ is Schur stable. Furthermore define matrices ˆFi = HiFiH¯ _i−1 and ˆAij = HiAijH_i−1 for all i = 1, ..., M and j = 1, ..., M . Finally define a matrix ΓP KF as follows

ΓP KF =    γij = 0 if i = j γij = µ2 i 1−λ2 i || ˆAijAˆ−1ij ||2 if i 6= j (2.14)

where scalars µi ≥ 1 and λi ∈ [0, 1) are defined in such a way that || ˆFih|| ≤ µiλhi.

Finally, one last assumption is needed to introduce the main result.

Assumption 4. For some values of ¯Li, Hi,

(i) σ( ˆFi) < 1 ∀i = 1, ..., M , and (ii) σ(ΓP KF) < 1.

Where symbol σ(·) indicates the spectral radius of the matrix.

Note that Assumption 3 is implicitly required by Assumption 4 since a nec-essary condition for the existence of ¯Li guaranteeing that σ( ˆFi) < 1 is that ( ˜Aii, ˜Ci) is detectable.

Now the main result concerning the convergence properties of Pi can be

(43)

Theorem 1. If Assumption 1 holds ∀i = 1, ..., M and under Assumption 4, there exists ¯Pi > 0 ∀i = 1, ..., M such that, limk→∞Pi(k) = ¯Pi if one of the following initializations is used:

a. Pi(0) = 0 ∀i = 1, ..., M .

b. Pi(0) = ¯P_iN if Assumption 2 holds ∀i = 1, ..., M . c. Pi(0) = ˜PiN if Assumption 3 holds ∀i = 1, ..., M .

A remark is due. In the author’s experience, it is not necessary to use only the conditions described in Theorem 1 to verify the convergence properties of the scheme. Indeed, experience suggests that, provided that Assumptions 1 and 4 are verified, convergence can be always achieved. However, these initial conditions are indicated, since convergence can be formally proved in these

cases only. Regarding Assumption 4, provided that Assumption 3 (i) is

verified, it is always possible to find ¯Lisuch that σ( ˆFi) < 1 for all i = 1, ..., M . As explained in [3], Assumption 4 can be easily verified if the system shows a cascade topology. The problem of verifying Assumption 4 becomes more complex if a generic system structure is considered.

This design problem can be cast as the centralized optimization problem min

{Hi,Li}i=1,...,M

σ(ΓP KF) (2.15a)

Subject to the definition of ΓP KF and to

σ(ΓP KF) < 1 (2.15b)

σ( ˆFi) < 1, i = 1, ..., M (2.15c)

To reduce the computational load of (2.15) the values of Hi can be

con-strained. For example, one can try to minimize the terms µi by constraining

Hi to take values corresponding to which ˆFi = HiF¯iHi−1 is diagonal (provided that ¯Fi is diagonalizable and has real eigenvalues), or one can set Hi = Ini

as previously stated.

Furthermore note that the optimization problem (2.15) is nonlinear, and therefore a suitable initialization is fundamental. In Chapter 3 we discuss

(44)

a method to face this problem in practice, and we also show how this cen-tralised problem can be formulated in a conservative but distributed way.

2.4 Partition-Based Luenberger filter

In this section, the algorithm described in [2] is analysed. This algorithm will often be referred to as PLF.

2.4.1 Algorithm equations

The algorithm relies on a distributed estimation scheme of the type ˆ xi(k + 1) = X j∈Ni {Aijxˆj(k) + Lij(yj(k) − Cjxˆj(k))} ˆ yi(k) = Cixˆi(k) (2.16)

The local estimation error is defined as ei(k) = xi(k)− ˆxi(k) and its dynamics is described by the equation

ei(k + 1) = X

j∈Ni

{(Aij − LijCj)ej(k) − Lijvj(k)} + wi(k) (2.17) It is important to notice that the substantial difference with respect to the PKF is that gains Lij are static in this case. It is indeed necessary to compute

them in a proper way as explained in Section 2.4.2. Another important

thing to notice is that, while the design phase of PKF basically consists of guaranteeing a priori that the matrix update (2.9) enjoys convergence properties, the design phase for PLF includes the actual design of gains Lij. Similarly to the previous case, in order to write the full equation of the estimation error one needs to define the vectors e, v, w as the column vectors collecting ei, vi and wi respectively for i = 1, ..., M . One defines L as the block matrix having the (i, j) − th element equal to Lij for i = 1, ..., M and j = 1, ..., M .

The dynamics of the extended estimation error is described by the following system

(45)

2.4 Partition-Based Luenberger filter 23

The covariance matrix of the extended estimation error is defined by Π(k +

1) := E[e(k + 1)eT_{(k + 1)] and obeys the recursive equation}

Π(k + 1) = (A − LC)Π(k)(A − LC)T + LRLT + Q (2.19)

As explained in Section 2.2, the full structure of matrix Π(k) does not al-low for a recursive distributed update where only local computations are performed and where communication is required only among neighbouring

computing units. In order to solve this problem, an upper bound Bi(k) to

the local estimation error covariance Πi(k) is defined in such a way that it is possible to compute it in a distributed fashion.

Setting k = 1 as the initial time instant, one defines the time-varying ma-trix Bi(k), i = 1, ..., M for all k > 1, using the following distributed update scheme

Bi(k + 1) = X

j∈Ni

[( ˜Aij − LijC˜j)Bj(k)( ˜Aij − LijC˜j)T + LijR˜jLTij] + Qi (2.20)

where ˜Aij = √ζiAij, ˜Ci = √ζiCi, ˜Ri = ζiRi and ζi = |Si|, for all i, j = 1, ..., M .

In Fig.2.1 an example of the distributed estimation scheme is shown along with the system coupling graph, the way local observers gather measurements and communicates with each other is indeed very similar to that of PKF. Concerning the implementation, the design phase consist of the computation of the gains Lii and Lij for j ∈ Ni, for each i = 1, ..., M . Once the gains have been obtained, the PLF works as described in Algorithm 2.

2.4.2 Main properties

In [2] it is proved that Bi(k) can be used as an upperbound to Πi(k), for

all i = 1, ..., M and for all k > 1. In the following the main properties of

this upperbound are shown, then the optimization problem to compute Lij

is explained in details.

Theorem 2. If one sets , for all i = 1, ..., M , diag(B1(1), ..., BM(1)) ≥ Π(1) then, for all k ≥ 1, it holds that Bi(k) ≥ Πi(k).

(46)

Algorithm 2

Memory requirements

For i ∈ {1, ..., M }, subsystem i stores in memory

- Permanently Qi, Ri, Aii, Ci, Lii {Aij, Cj, Rj, Lij; j ∈ ˜Ni} ; - Temporarily, for each k ≥ 1, {yj(k), ˆxj(k), Bj(k); j ∈ Ni} ; On-line implementation

At each time step k ≥ 1 subsystem i: 1) Measures yi(k);

2) Broadcasts to its successors the quantities yi(k), ˆxi(k) and Bi(k); 3) Gathers from its neighbours the information

{yj(k), ˆxj(k), Bj(k); j ∈ ˜Ni};

4) Computes the estimate ˆxi(k + 1) and the matrix Bi(k + 1) as in (2.16) and (2.20);

Now a centralised condition is given in order to guarantee that, at the

same time, the error dynamics (2.18) is asymptotically stable and Bi(k) are

bounded for all k. Some definitions are needed first. Define, for all i, j, ˜

Fij = ( ˜Aij − LijC˜j) and the matrix ˜F as the matrix whose blocks are ˜Fij. Also, define the following further matrix

F =F ˜˜ F =    ˜ F11⊗ ˜F11 . . . F˜1M⊗ ˜F1M .. . . .. ... ˜ FM 1⊗ ˜FM 1 . . . F˜M M⊗ ˜FM M    (2.21)

Where denotes the Khatri-Rao product, while ⊗ denotes the Kroneker product ([6]).

Given the above definition, one can state the following Theorem 3. If matrix F is Schur stable, then

(i) There exists, for all i = 1, ..., M , a matrix ¯Bi ≥ 0 such that Bi(k) → ¯Bi as k → +∞;

(ii) A − LC is Schur stable.

As stated in the previous theorem, the key condition guaranteeing the effectiveness of the estimation scheme is the Schur stability of matrix F.

(47)

2.5 Analysis of the estimation performance: application to an

academic example 25

This condition will be further analysed in Chapter 3 where the distributed design is considered and the problem of computing suitable gains Lij is faced. An important remark concerning the design conditions is due. Given matrices

˜

Fii and ˜Fij, it is possible to define the following matrix

ΓP LF =    γij = 0 if i = j γij = µ2 i 1−λ2 i || ˜Fij||2 if i 6= j (2.22)

Where scalars µi ≥ 1 and λi ∈ [0, 1) are defined in such a way that || ˜Fiih|| ≤ µiλhi.

Using the aforementioned ΓP LF matrix, it is possible to setup an optimization problem that allows to design the estimator gains. Although it is centralized, this condition has the advantage of being aggregate. Furthermore this condi-tion is more conservative that the one stated in Theorem 3. The optimizacondi-tion problem reads as follows

min {Lij}i,j=1,...,M

σ(ΓP LF) (2.23a)

Subject to the definition of ΓP LF and to

σ(ΓP LF) < 1 (2.23b)

σ( ˜Fii) < 1, i = 1, ..., M (2.23c)

In case the centralized problem (2.23) admits a solution, it is possible to design gains Lij satisfying (i) and (ii) of Theorem 3.

2.5 Analysis of the estimation performance:

application to an academic example

In this section, the implementation of the two estimation algorithms on a simple system is shown. The analysis focuses on the estimation results and

on the behaviour of estimation error covariance matrices upper bounds Bi

(48)

2.5.1 System description

A Linear Time-Invariant (LTI) system is considered. It is composed by two identical subsystems each one with two states and one output. Referring to the generic system model depicted in Section 2.1, this leads to M = 2 and ni = 2, pi = 1 for all i = 1, ..., M . The matrices describing the dynamics of the individual subsystems are

Aii = " 0.9 0.1 0.1 −0.9 # , ∀i = 1, 2

The way one subsystem influences the other is described by the coupling matrices Aij = " η η/2 η/2 η # , ∀i, j = 1, 2 i 6= j

Where η represents the coupling strength that has been set to 0.05 for the current application, this satisfies the design conditions as further explained in Chapter 3.

Using these matrices the equation for the distributed system evolution can be written as

xi(k + 1) = Aiixi(k) + Aijxj(k) + wi(k), ∀i, j = 1, 2 i 6= j

Where wi(k) is the noise acting on the states of subsystem i. The output

transformation is

yi(k + 1) = Cixi(k) + vi(k), ∀i = 1, 2

In this case vi(k) is the measurement noise acting on the outputs. The output matrix reads as follows

Ci = [1 1], ∀i = 1, 2

Noise covariance matrices have been defined as Qi = " 1 0 0 1 # and Ri = 1, ∀i = 1, 2

The system has been initialised to a non-zero value in order to obtain an initial transient. This is further explained in Section 2.5.3 and Section 2.5.4.

(49)

academic example 27

2.5.2 Algorithms implementation

The static gains used in the PLF have been computed in order to achieve the Schur stability of matrix F, this grants the stability of the estimation and

the convergence of matrices Bi as stated in Theorem 3. Matrices Bi evolve

as described in (2.20).

Concerning the PKF, the gains and the Pi matrices dynamics have been

im-plemented as described in (2.8) and (2.9) respectively.

2.5.3 Estimation results

In this section the estimation results coming from the implementation of the two algorithms are shown and compared to those of a Centralised Kalman Filter (CKF).

The estimation initialization for the two subsystem is

ˆ x1(0) = " 10 20 # and xˆ2(0) = " 5 30 # (2.24) Assuming a perfect knowledge of the system initial condition, the system states have been initialised as the estimate. This non-zero initialization al-lows for a starting transient to be seen. In Fig.2.2, the states evolution and the estimated values concerning subsystem 1 can be seen while in Fig.2.3, the same results are shown for subsystem 2. The two subsystems evolves in different ways due to their diverse initialization.

It is interesting to notice that the estimates obtained using CKF are very similar to those estimated using Partion-Based Luenberger and PKF. In or-der to obtain a more reasonable comparison, the analysis has been performed using the Mean Square Error. This gives a rough idea of the quality of the es-timates and emphasizes the difference between a centralised and a distributed approach. M SE = 1 Tsim Tsim X k=1 (x(k) − ˆx(k))2 (2.25)

Where Tsim is the length of the simulation.

(50)

0 10 20 30 40 50 60 70 80 90 100 -10 0 10 20 Subsystem 1, state 1 x ˆ xC K F ˆ xP K F ˆ xLuen t[s] 0 10 20 30 40 50 60 70 80 90 100 -20 -10 0 10 20 Subsystem 1, state 2 x ˆ xC K F ˆ xP K F ˆ xLuen

Fig. 2.2: System evolution and estimates, subsystem 1.

0 10 20 30 40 50 60 70 80 90 100 -10 -5 0 5 10 Subsystem 2, state 1 x ˆ xC K F ˆ xP K F ˆ xLuen t[s] 0 10 20 30 40 50 60 70 80 90 100 -40 -20 0 20 40 Subsystem 2, state 2 x ˆ xC K F ˆ xP K F ˆ xLuen

(51)

academic example 29

Table 2.1: MSE analysis.

Subsystem 1 Subsystem 2

x11 x12 x21 x22

CKF 1.6147 1.8046 1.6032 1.8056

PKF 1.6227 1.8224 1.6127 1.8246

PLF 1.6535 1.9367 1.6455 1.9414

and for both the algorithms under analysis is shown, these values have been computed on a 100000 time instants simulation to enhance the accuracy of the analysis. The results show that the estimation error of the PLF is larger than the estimation error of the PKF while the error of CKF is the smallest. In particular the performance of PKF are closer to those of CKF and the PLF shows the worst performances by far. This behaviour will be analysed also in Chapter 5, where the same analysis is performed on a more complex example.

2.5.4 Estimation error covariance upper bounds

com-parison

As in Section 2.5.3, the PLF and PKF algorithms have been compared with a Centralized Kalman Filter. The initialization of the centralised Kalman estimation error covariance matrix has been set to

Π(0) = 1.5Q =      1.5 0 0 0 0 1.5 0 0 0 0 1.5 0 0 0 0 1.5      = " Π1(0) 02×2 02×2 Π2(0) #

The Piand Bimatrices have been initialised to the same value of the diagonal blocks of the centralised Kalman matrix, i.e.

Pi(0) = Bi(0) = Πi(0), ∀i = 1, 2

Note that matrices Pi have been initialised to a value that does not satisfy

(52)

the functioning of the algorithm as explained in Section 2.3.2. Such an ini-tialization for the estimation error covariance matrix means that there is an uncertainty in the knowledge of the true value of the system state initial-ization. Indeed the estimates have been initialized to a fixed value, that is (2.24), while the system is initialized to an unknown value nearby (2.24). A large number of Montecarlo runs have been carried out varying the system initialization. This eventually led to the computation of the empirical values for the estimation error covariance matrix and made it possible to compare those values with the theoretical ones produced by the algorithms.

For each run, the system has been initialized based on the uncertainty of the estimation error at time zero, using a random generation from the distribu-tion

x(j)(0) ∼ N (ˆx(0), Π(0)) j = 1, ..., Nm

Where ˆx(0) is the initialization of the estimates described in (2.24). The

number of Montecarlo experiments performed is Nm = 10000, this is enough

to see the behaviour of empirical covariances clearly. For each experiment

a simulation length of Tsim = 50 time instants have been chosen, at every

time instant the data regarding the estimation errors for each of the three observers considered is collected.

e(j)_{P LF} i(k) = x (j) i (k) − ˆx (j) P LFi(k) e(j)_{P KF} i(k) = x (j) i (k) − ˆx (j) P KFi(k) e(j)_CKF i(k) = x (j) i (k) − ˆx (j) CKFi(k) ∀i = 1, 2 ∀k = 1, ..., Tsim ∀j = 1, ..., Nm

Using this data and the below equations, the empirical covariances have been computed. ˆ Bi(k) = 1 Nm Nm X j=1 e(j)_{P LF} i(k)e (j) P LFi(k) T ˆ Pi(k) = 1 Nm Nm X j=1 e(j)_{P KF} i(k)e (j) P KFi(k) T ˆ Πi(k) = 1 Nm Nm X j=1 e(j)_CKF i(k)e (j) CKFi(k) T ∀i = 1, 2 ∀k = 1, ..., Tsim (2.26)

These empirical values gathered from the Montecarlo experiments have been compared with the theoretical values coming from the three algorithms, i.e.

(53)

2.5 Analysis of the estimation performance: application to an academic example 31 t[s] 0 5 10 15 20 25 30 35 40 45 50 2.5 3 3.5 4 4.5 5 5.5

6 Traces comparison, subsystem 1

tr(B) tr(P ) tr_(Π) tr( ˆB) tr( ˆP) tr( ˆΠ)

Fig. 2.4: Estimation error covariance matrix, subsystem 1.

matrices Bi(k), Pi(k) and Πi(k). Note that in order to compare a centralised filter with the two distributed ones, the diagonal blocks of Π have to be con-sidered, i.e. Π1 and Π2.

Since our analysis focuses on the diagonal elements of the matrices, one of the possibilities is to consider the trace of each matrix to be compared. In Fig.2.4 and Fig.2.5 the results are shown. Note that the evolution of matrices Bi, Pi and Πi is the same in both the plots because the two subsystems are

identical. Moreover the Bi bounds are always more conservative than Pi.

Indeed this is a theoretical result coming from the definition of matrices Pi

and Bi. This behaviour will be analysed more in-deep in Chapter 5.

Another meaningful remark is that matrices Bi and Pi are bounds for the

empirical values ˆBi and ˆPi respectively. As expected, the behaviour of Πi is very close to that of ˆΠi. Furthermore the trend of ˆPi is similar to that of ˆΠi while ˆBi is definitely larger.

(54)

t[s] 0 5 10 15 20 25 30 35 40 45 50 2.5 3 3.5 4 4.5 5 5.5

6 Traces comparison, subsystem 2

tr(B) tr(P ) tr_(Π) tr( ˆB) tr( ˆP) tr( ˆΠ)

(55)

Chapter 3 Distributed and Plug&Play

Design

As previously explained, in a plug and play context one of the most relevant aspects is the minimization of information transmitted among the single com-ponents of the overall system. As a consequence, the design phase for these algorithms has to be performed in a distributed way without using the bulky information coming from the overall large scale system. In the next sections we show that the design phase, regarding the PKF and the PLF estimation schemes studied in Chapter 2, can be carried out in a distributed and scalable way, and that these schemes can indeed support plug and play operations. We will therefore devise conditions to be met in a distributed fashion after plug and play operations occur, to grant stability of the overall estimation scheme.

3.1 Partition-Based Kalman Filter design

As previously discussed, in [3] the design phase can be conducted through two approaches: (1) Linear Matrix Inequalities can be used to solve an op-timization problem and find matrices ¯Pi satisfying (2.11) while (2) a Small Gain Argument can be applied to find the conditions guaranteeing the

con-vergence of matrices Pi(k) (see (2.13)). In Chapter 2 the second problem

(56)

will focus on this problem more in-depth and a distributed way to check the conditions will be described. In particular, plug and play operations will be considered.

3.1.1 Distributed design conditions

In this section the conditions that are necessary to guarantee the existence of ¯Pi such that

lim

k→∞Pi(k) = ¯Pi ∀i = 1, ..., M

are analysed from a distributed point of view, i.e., defining a set of local conditions to be verified by each subsystem.

Focusing on the main assumptions of Theorem 1, while Assumptions 1 and 4 (i) are local conditions, Assumption 4 (ii) is centralised since it involves information regarding the overall system. In [3] the following assumption is introduced, providing a conservative, yet distributed and very simple condi-tion that must be verified at subsystem level.

Assumption 5. For all i = 1, ..., M and for some values of ¯Li, Hi, it holds that ρi = M X j=1 γij < 1 (3.1)

This assumption implies the Schur stability of ΓP KF as stated in the

following

Proposition 2. If Assumption 5 holds, then Assumption 4 (ii) is verified. As it will be shown in the next section, this result allows for plug and play operations.

In view of the results provided by Assumption 5 and Proposition 2, the centralised optimization problem (2.15) discussed in Section 2.3.2 can be formulated in a distributed way as follows. For each subsystem i = 1, ..., M

min {Hi,Li}

ρi (3.2a)

(57)

3.1 Partition-Based Kalman Filter design 35

ρi < 1 (3.2b)

σ( ˆFi) < 1 (3.2c)

Following an approach similar to the one stated in Section 2.3.2, it is possible to consider Hi = Ini in order to reduce the number of free variables of the

optimization problem. The aforementioned minimization problem has been implemented in the Plug-and-Play Matlab toolbox [12]. An important re-mark is that, being the problem nonlinear, its solution depends on the given initialization. In the toolbox the initialization is performed through the so-lution of a LQ problem, meaning that the optimal soso-lution found depends on the Q and R weight matrices used for the LQ problem.

3.1.2 Plug&Play operations

The plug and play scenario consists of the case when one or more subsystems

are added to or removed from the interconnected large scale system. It

may be necessary for some subsystems to update the dynamics (2.9) and to perform again the condition checking described in Section 3.1.1.

Definition of the PnP scenario

Assume that the plug and play event occurs at time TP nP. Denote using

”+” the quantities that must be used after the plug-in/out event. Some assumptions regarding the functioning of the algorithm before the plug and play event are needed.

(i) For k < TP nP, Assumptions 4 (i), 5, and 1 (for all i = 1, ..., M ) hold. (ii) At k = TP nP the updates (2.9) are in steady state, i.e., Pi(TP nP) = ¯Pi

for all i = 1, ..., M .

It is important to notice that, when PnP operations involving subsystems take place, the number of successors for some subsystems may change, when this happens the matrices ˜Aij, ˜Ci, and ˜Ri defined in Section 2.3.1 must

(58)

be redefined. For each subsystem i = 1, ..., M define ζ_i+ = |S_i+|, where S+

i is the new set of successors of subsystem i. In general it holds that

ζ_i+ 6= ζi. The update of ˜· matrices is described by ˜A+_ij = q ζ_j+Aij = r ζ_j+ ζj ˜ Aij, ˜ C_i+=pζ_i+Ci = q ζ_i+ ζi ˜ Ci, and ˜R+i = ζ + i Ri = ζ_i+ ζi ˜ Ri.

In the worst case, ζ_i+> ζi may prevent the detectability of the pair ( Ã+ii, ˜C + i ) to hold, which may jeopardize the verifiability of Assumption 4 (i). In [3] it is also assumed that Hi and ¯Li are not redefined, for i = 1, ..., M after the plug and play event. From this it follows that, for all i, j = 1, ..., M , k Â+_ij( Â+_jj)−1k = k ÂijAˆ−1jj k.

Plug-in of a subsystem

Assume that, at time TP nP, the subsystem (M + 1) needs to be introduced

and to be connected with predecessors ˜NM +1 and successors ˜SM +1. As shown in details in [3], for each i = 1, ..., M

• if i 6∈ SM +1∪ NM +1, then, since ζi+ = ζi, there is no need for the update of (2.9). Furthermore since ρ+_i = ρi < 1, there is no need to re-check the condition about stability;

• if i ∈ SM +1 but i 6∈ NM +1, ζi+ = ζi and there is no need to update (2.9). In this case ρ+_i > ρi and is therefore required to check the stability condition;

• if i ∈ NM +1 but i 6∈ SM +1, then ζi+= ζi+ 1, this means that ˜· matrices in (2.9) have to be updated. Moreover ρ+_i > ρi and stability condition has to be checked again;

• if i ∈ SM +1∩ NM +1, again ζi+ = ζi+ 1 and ˜· matrices in (2.9) have to be updated. ρ+_i > ρi and stability condition has to be re-checked. For the new subsystem, the design of ¯LM +1, HM +1can be addressed through the following optimization problem.

min {HM +1,LM +1}

ρ+_{M +1}+ X

j∈ ˜SM +1

(59)

3.1 Partition-Based Kalman Filter design 37 subject to σ( ˆF_{M +1}+ ) < 1, ρ+_{M +1} < 1 (3.3b) γ_{j(M +1)}+ < 1 − ρ+_j for all j ∈ ˜SM +1 (3.3c) Where ρ+_j = 1−λ 2 j 1−λ+2_j ρj for j ∈ ˜SM +1, as explained in [3].

When a plug-in request is received from subsystem M + 1, the following design procedure must be followed

(i) if (3.3) admits a solution and if, for all i ∈ NM +1, ρ+i < 1 and σ( ˆFi) < 1, then allow the plug-in, otherwise deny it;

(ii) properly initialize PM +1(TP nP).

The following corollary of Theorem 1 addresses the step (ii) and guarantees

convergence of the system matrices Pi(k), k = 1, ..., M + 1 to steady state

solutions.

Corollary 1. If Assumption 1 holds also for i = M +1 and if, after the plug-in event, Assumptions 4 (i) and 5 are verified, then there exist ¯P_i+ ≥ 0 for all i = 1, . . . , M such that, Pi(k) → ¯Pi+ as k → ∞ if the following initialization is used: Pi(TP nP) = ¯Pi for all i = 1, . . . , M and (a) PM +1(TP nP) = 0, or (b) if Assumption 2 holds for i = M + 1, PM +1(TP nP) = ¯PM +1N , or (c) if Assumption 3 holds for i = M + 1, PM +1(TP nP) = ˜PM +1N .

It is important to notice that initializations (b) and (c) limit possible un-desirable transients on the state estimates.

As far as the scalability of the approach is concerned, note that, at the (M + 1)-th subsystem level, to solve (3.3), the required data consist in (i) the local system matrices (A(M +1)(M +1), CM +1), (ii) the number ζM +1 of suc-cessors of subsystem M + 1, (iii) A(M +1)j, Ajj, Hj for all j ∈ NM +1, (iv) (1 − λ2_j)/(1 − λ+2_j )ρj, Aj(M +1), Hj for all j ∈ SM +1. It is therefore clear that this local design problem requires the transmission of a limited amount of information, i.e., through a neighbour-to-neighbour communication graph. The subsystems involved in the plug-in event are shown in Fig.3.1. In the picture, the blue subsystem is connected and the bold arrows indicates the information transmitted during the event, the red subsystems are the ones

Analysis, design and testing of novel partition-based state estimation and fault detection schemes for large-scale systems

POLITECNICO DI MILANO

Facolt`

a di Ingegneria dell’Informazione

Master of Science in Automation and Control

Engineering

Analysis, Design and Testing of

Novel Partition-Based

State Estimation and

Fault Detection Schemes

for Large-Scale Systems

Relatore:

Prof. Marcello Farina

Correlatori: Prof. Thomas Parisini

Dr. Francesca Boem

Tesi di Laurea di:

Stefano Attuati

Matr. 837169

Acknowledgements

Abstract

Sommario

Contents

List of Tables

List of Figures

Chapter 1

Introduction

1.1

System monitoring

1.2

Large-scale systems

1.3

Contribution of the Thesis

1.4

Structure of the Thesis

Chapter 2

New approaches for

partition-based distributed

state estimation

2.1

System model

2.2

Issues in centralised approaches

2.2.1

Centralised Luenberger predictor: filter and

co-variance structure

2.2.2

Centralised Kalman predictor: filter and

covari-ance structure

2.2.3

Partition-based estimation goals

2.3

Partition-Based Kalman Filter

2.3.1

Algorithm equations

2.3.2

Main properties

2.4

Partition-Based Luenberger filter

2.4.1

Algorithm equations

2.4.2

Main properties

2.5

Analysis of the estimation performance:

application to an academic example

2.5.1

System description

2.5.2

Algorithms implementation

2.5.3

Estimation results

2.5.4

Estimation error covariance upper bounds

com-parison

Chapter 3

Distributed and Plug&Play

Design

3.1

Partition-Based Kalman Filter design

3.1.1