Proceedings of the 26th International Workshop on Principles of Diagnosis
Decentralised Fault Diagnosis of Large-scale Systems: Application to Water
Transport Networks
Vicenç Puig and Carlos Ocampo-Martinez
Universitat Politècnica de Catalunya - BarcelonaTech
Institut de Robòtica i Informàtica Industrial, CSIC-UPC
Llorens i Artigas, 4-6, 08028 Barcelona, Spain
e-mail: {vpuig,cocampo}@iri.upc.edu
Abstract several proposals where there is no centralised control struc-
ture or coordination process among diagnosers [6, 7, 8]. Ev-
In this paper, a decentralised fault diagnosis ap- ery diagnoser shares information with the neighbouring di-
proach for large-scale systems is proposed. This agnosers. In these systems the model is distributed, the di-
approach is based on obtaining a set of local agnosis is locally generated and the consistency among the
diagnosers using the analytical redundancy rela- subsystems should be satisfied.
tion (ARRs) approach. The proposed approach In this paper, the main contribution relies on the devel-
starts with obtaining the set of ARRs of the sys- opment of a decentralised fault diagnosis approach for LSS
tem yielding into an equivalent graph. From that based on analytical redundancy relations (ARRs) and graph
graph, the graph partitioning problem is solved theory. The algorithm starts considering a set of ARRs and
obtaining a set of ARRs for each local diagnoser. then stating an equivalent graph. From that graph, the prob-
Finally, a decentralised fault diagnosis strategy is lem of graph partitioning is then solved. The resultant parti-
proposed and applied over the resultant set of par- tioning consists of a set of non-overlapped subgraphs whose
titions and ARRs. In order to illustrate the ap- number of vertices is as similar as possible and the num-
plication of the proposed approach, a case study ber of interconnecting edges between them is minimal. To
based on the Barcelona drinking water network achieve this goal, the partitioning algorithm applies a set of
(DWN) is used. procedures based on identifying the highly connected sub-
graphs with balanced number of internal and external con-
1 Introduction nections in order to minimize the degree of coupling among
the resulting partitions (diagnosers). This algorithm is spe-
Large-scale systems (LSS) present new challenges due to
cially useful in systems where there is no a clear functional
the large size of the plant and its resultant model [1, 2]. Tra-
decomposition. Finally, a decentralised fault diagnosis strat-
ditional supervision methods for LSS (including diagnosis
egy is introduced and applied over the resultant set of par-
and fault tolerant control) have been mostly developed as-
titions, in a similar way to the one introduced in [5]. In
suming a centralized scheme that assumes to have the full
order to illustrate the application of the proposed approach,
information. In the same way, a global dynamical model
a case study based on the Barcelona drinking water network
of the system is considered to be available for supervision
(DWN) is used.
design (off-line). Moreover, all measurements must be col-
The remainder of this paper is organised as follows. Sec-
lected in one location in a centralised way. When consid-
tion 2 presents and discusses the overall problem statement.
ering LSS, the centrality assumption usually fails to hold,
Section 3 presents the ARR graph partitioning methodology.
either because gathering all measurements in one location
Section 4 describes the proposed decentralised fault diag-
is not feasible, or because a centralised high-performance
nosis approach. Section 5 shows both the considered case
computing unit is not available. These difficulties have re-
study and the way of implementing the proposed decen-
cently led to research in fault diagnosis (and fault-tolerant
tralised fault diagnosis approach. Finally, Section 6 draws
control) algorithms that operate in either decentralised or
the main conclusions.
distributed way. Depending on the degree of interaction of
the diagnoser associated to the subsystems and their diag-
nosis process, they can be classified into decentralised and 2 Problem Statement
distributed diagnosis categories. 2.1 Fault Diagnosis using ARRs
In the decentralised diagnosis, both a central coordina- Consider a dynamical system represented in general form
tion module and a local diagnoser for each subsystem that by the state-space model
forms the whole supervision system are running in paral-
lel. Some examples were presented in [3, 4, 5], where local x+ = g(x, u, d), (1a)
diagnosers are communicated to a coordination process (su- y = h(x, u, d), (1b)
pervisor), obtaining a global diagnosis. On the other hand,
in the distributed approach, a set of local diagnosers share where x ∈ Rn and x+ ∈ Rn are, respectively, the vectors
information by means of some communication protocol in- of the current and successor system states (that is, at time
stead of requiring a global coordination process such as in instants k and k + 1, respectively if the model is expressed
a decentralised approach. In the related literature, there are in discrete-time), u ∈ Rm is the system input vector, d ∈
99
Proceedings of the 26th International Workshop on Principles of Diagnosis
Rp is the vector containing a bounded process disturbance graph, the problem consists in partitioning the graph R into
and y ∈ Rq is the system output vector. Moreover, g : subgraphs. Since such partitioning is oriented to the appli-
Rn × Rm × Rp 7→ R is the states mapping function and cation of a decentralised fault diagnosis, it is convenient that
h : Rn × Rm × Rp 7→ Rq corresponds with the output the resultant subgraphs have the following features:
mapping function. • nearly the same number of vertices;
The design of a model-based diagnosis system is based
on utilizing the system model (1) in the construction of the • few connections between the subgraphs.
diagnosis tests. According to [9], by means of the structural These features guarantee that the obtained subgraphs
analysis tool and perfect matching algorithm, a set of ARRs, have a similar size, fact that balances computations be-
namely R, can be derived from (1). ARRs are constraints tween local diagnosers and allows minimising communica-
that only involve measured variables (y, u) and known pa- tions with a supervisory diagnoser. Hence, the partitioning
rameters θ. The set of ARRs can be represented as the ARR graph can be more formally established following
R = {ri | ri = Ψi (yk , uk , θk ), i = 1, . . . , nr }, (2) the dual problem proposed in [13] as stated here in Problem
1.
where Ψi is the ARR mathematical expression and nr is the
Problem 1 (ARR Graph Partitioning Problem). Given a
number of obtained ARRs. Then, fault diagnosis is based
graph G(V, E) obtained from a set of ARRs, where V de-
on identifying the set of consistent ARRs
notes the set of vertices, E is the set of edges, and p ∈ Z≥1 ,
R0 = {ri |ri = Ψi (yk , uk , θk ) = 0, i = 1, . . . , nr }, (3) find p subsets V1 , V2 , . . . , Vp of V such that
and inconsistent ARRs, p
S
1. Vi = V ,
R1 = {ri |ri = Ψi (yk , uk , θk ) 6= 0, i = 1, . . . , nr }, (4) i=1
at time instant k when some inconsistency in (2) is de- 2. Vi ∩ Vj = ∅, for i ∈ {1, 2, . . . , p}, j ∈ {1, 2, . . . , p},
tected [10]. Fault isolation task starts by obtaining the ob- i 6= j,
served fault signature, where each single fault signal indi- 3. #V1 ≈ #V2 ≈ · · · ≈ #Vp ,
cator φi (k) is defined as follows:
4. the cut size, i.e., the number of edges with endpoints in
0 if ri (k) ∈ R0 , different subsets Vi , is minimised.
φi (k) = (5)
1 if ri (k) ∈ R1 . Remark 2.1. Conditions 3 and 4 of Problem 1 are of high
Fault isolation is based on the knowledge about the bi- interest from the point of view of a decentralised scheme
nary relation between the considered fault hypothesis set since they are related to the degree of interconnection be-
f1 (k), f2 (k), . . . , fnf (k) and the fault signal indicators tween resultant subsystems and their size balance.
φi that are stored in the fault signature matrix M . An el- Remark 2.2. The inclusion of additional specifications di-
ement of this matrix, namely mij , is equal to 1 if the fault rectly related to the FDI performance of each subsystem di-
hypothesis fj is expected to affect the residual ri such that agnoser will be addressed as a future extension of the pro-
the related fault signal φi is equal to 1 when this fault is af- posed partitioning approach.
fecting the monitored system. Otherwise, the element mij
Remark 2.3. The partitioning approach starts from a given
is zero-valued. A column of this matrix is known as a the-
set of ARRs obtained using the perfect matching algorithm.
oretical fault signature. Then, the fault isolation task in-
The selection of the best ARRs from the set of the all pos-
volves finding a matching between the observed fault signa-
sible ARRs (that could be obtained using the available sen-
ture with some of theoretical fault signatures.
sors and system structure) such that when applying the par-
2.2 Partitioning the Set of ARRs titioning algorithm produces a set of diagnosers with good
FDI performance could be considered as an additional fu-
In order to design a decentralised fault diagnosis system fol-
ture improvement.
lowing the ARR approach recalled above, the set of ARRs in
(2) should be decomposed into subsets with minimal degree In general, graph partitioning approaches are considered
of coupling. Each subset of ARRs will allow to implement as N P-complete problems [2]. However, they can be solved
a local diagnoser. With this aim, a graph representation of in polynomial time for #Vi = 2 (Kernighan-Lin algorithm);
R in (2) is determined. The graph G(V, E) representing the see, e.g., [14]. Since the latter condition is quite restric-
set of ARRs is obtained considering that tive for large-scale graphs, alternatives for graph partition-
• the ARRs are the graph vertices collected in a set V , ing based on fundamental heuristics are properly accepted
and and broadly discussed.
• the measured input/output variables are the graph 3 Proposed Partitioning Approach
edges collected in a set E.
Starting from the system ARR graph obtained as described
The graph incidence matrix IM is obtained considering that,
in Section 2, this section proposes a partitioning algorithm
without loss of generality, the directionality of the edges are
through which a decomposition of the set of system ARRs
derived from the relation between ARRs (rows of IM ) and
can be performed. This decomposition allows the splitting
input/output variables (columns of IM ), in analog way as
of a centralised diagnoser into local diagnosers. The philos-
proposed by [11] (and references therein) for the partition-
ophy of the proposed approach comes from the partitioning
ing of LSS1 . Once IM has been obtained from the ARR
methodology reported in [13], where a dynamic system is
1
There are alternative matrix representations for a graph such decomposed into several subsystems following certain cri-
as the adjacency matrix and the Laplacian matrix (see [12]), which teria towards fulfilling a set of design conditions. For com-
are related to the matrix representation used in this paper. pleteness and full understanding of the proposed diagnosis
100
Proceedings of the 26th International Workshop on Principles of Diagnosis
methodology, that approach is explained below and suitably for the particular case study. Additional auxiliary routines
adapted if needed. might be designed in such a way that the diagnosis perfor-
The algorithm is divided into the main kernel and auxil- mance that would be achieved when used in decentralised
iary routines in order to refine the final result according to or distributed fault diagnosis is taken into account. These
the nature of the system and the given criteria depending auxiliary routines are:
on the case. Here, the ARR graph is decomposed into sub- • The pre-filtering routine, which lightens the start-up
graphs in the same way as a system would be divided into routine by merging all these vertices with single con-
subsystems. nection to those to which they are connected. It al-
3.1 Main Kernel lows to have a smaller initial graph and then perform-
ing faster clustering of vertices.
This part performs the central task of defining how the
equivalent ARR graph of the LSS is split into subgraphs. • The post-filtering routine, which adds a tolerance pa-
The steps of the algorithm are followed in the form of sub- rameter δ in such a way that the uncoarsening rou-
routines towards reaching the main goals outlined in Prob- tine yields in less subgraphs when two of them may
lem 1. Notice that the whole algorithm is used off-line, be conveniently merged but the numerical constraints
i.e., the partitioning of the ARR graph is not carried out dy- does not allow to do so. This routine might increase
namically on-line. Ongoing research is focused to adapt the the complexity since the internal weight of some sub-
proposed algorithm such that the partitioning could be per- graphs would also increase, unbalancing the resultant
formed on-line when some structural change of the network set of partitions.
occurs. The different subroutines are briefly described next. • The anti-oscillation routine, which leads to solve a pos-
• The start-up routine, which requires the matrix-based sible issue when the refining (external balance) routine
definition of the graph, e.g., via the incidence matrix, is run since it defines a maximum number of iterations
in order to state the connections between the graph ver- ρ that the refining routine is executed.
tices.
• The preliminary partitioning routine, which performs 4 Decentralised Fault Diagnosis
a clustering-like procedure where all graph vertices are Once a partitioned set of ARRs has been obtained by means
assigned to a particular subset according to predefined of the algorithm presented in Section 3, the decentralised
indices related to the resultant subgraph and its inter- fault diagnosis approach is introduced. In order to explain
nal weight (defined as the number of vertices of a sub- how the proposed fault diagnosis approach works, it is con-
graph), its external weight (defined as the number of centrated on faults affecting the sensors measuring the in-
shared edges between subgraphs) and other statistical put/output variables implied in the ARRs. The approach
measures. The resultant amount of partitions at this could be easily extended to other type of faults, but in order
stage is automatically obtained. to keep the explanation simpler, it is restricted to the discus-
• The uncoarsening routine, which is applied for reduc- sion about the set of considered faults. In this way, a fault
ing the number of resultant subgraphs if their internal can be associated to each measured input/output variable.
weight is unbalanced, which would produce partitions Each subset of ARRs will allow to implement a local di-
with large differences of amount of vertices. This rou- agnoser Di in the way described in Section 2.1. The ARRs
tine defines a design parameter ϕmax for determining associated to a local diagnoser can be split in two groups.
the variance of the internal weight for all the resultant The first group, named in the following local ARRs, is com-
subgraphs. posed of ARRs that do not involve shared variables with
other ARRs in a different local diagnoser. On the other
• The refining routine, which aims at reducing the cut hand, the second group, named shared ARRs, is composed
size of the resultant subgraphs, i.e., the number of by ARRs that involve shared variables. Figure 1 shows two
edges they share. This routine is based on the connec- sets of ARRs associated to two local diagnosers, named
tivity of the vertices of a subgraph with other vertices D2 and D4 . These two diagnosers share some variables
in the same subgraph and in neighbouring subgraphs2 . (in this case only outputs, but can be both inputs and out-
Applying the aforementioned routines to the entire ARR puts). This set of shared variables allows to define the set
graph, the expected result consists of a set of subgraphs that of shared ARRs, named DC in the figure. The remaining
determines a particular decomposition. This set P is finally ARRs, which do not share variables, are local ARRs.
defined as Similarly, faults in the fault signature matrix M of the lo-
( p
) cal diagnoser that only involve local ARRs can be locally di-
[ agnosed. Thus, the local diagnoser works in a decentralised
P = Gi , i = 1, 2, . . . , p : Gi = G . (6)
manner regarding those faults. On the other hand, faults that
i=1
involve ARRs with shared variables in different subgraphs
3.2 Auxiliary Routines can not be locally diagnosed. On the contrary, a global diag-
Although the decomposition algorithm yields to an auto- noser that evaluates the involved ARRs is used. This diag-
matic partitioning of a given graph, it does not imply that noser has a fault signature matrix M collecting the involved
the resultant set P follows the pre-established requirements ARRs with shared variables between local diagnosers and
stated in Problem 1. Therefore, complementary routines faults that should be globally diagnosed. When local diag-
enhance the partitioning routine depending on their tune nosers evaluate an ARR composed of shared variables, they
send the result of the consistency check to the global di-
2
Two subgraphs are called neighbours if they are contiguous agnoser, which proceeds with the global diagnosis using a
and share edges (see, e.g., [15] among many others). fault signature matrix that contains the involved ARRs. As
101
Proceedings of the 26th International Workshop on Principles of Diagnosis
y1,S2 . . . y4,S2
. . . y1,S4 . . . y28,S4 y29,S4 . . . y32,S4 y5,S2 . . . y12,S2 through the m actuators (pumps and valves), d ∈ Rq cor-
..
responds to the vector of the q water demands (sectors of
. consume) and y ∈ Rn are the vector of measured water
ARR1,S4
.. volumes of the n tanks. In this case, the difference equa-
. D4 tions in (7a) describe the dynamics of the storage tanks,
ARR28,S4
ARR1,S2 ARR29,S4
the algebraic equations in (7b) describe the static relations
.. .. (i.e., mass balance at junction nodes) in the network and
. . DC in (7c) describe the relation between the physical and mea-
ARR4,S2 ARR32,S4
ARR5,S2
.. D2 sured tank volumes. Moreover, A, B, Bp , C, E1 and E2
. are system matrices of suitable dimensions dictated by the
ARR12,S2
network topology.
5.3 Implementation of the Proposed Approach
Figure 1: Subsets of ARRs of two local diagnosers sharing This section discusses the way the proposed decentralised
some variables fault diagnosis approach is implemented in the considered
real case study. Figure 2 corresponds to the aggregate model
a result of the global diagnosis based on the involved ARRs of the Barcelona DWN, which is a simplification of the com-
with shared variables, a fault in these variables could be di- plete model, where groups of elements have been aggre-
agnosed or alternative excluded. In case of exclusion, local gated (not discarded) in single nodes to reduce the size of
diagnosers sharing a given ARR whose shared variable has the whole network model. Using this aggregate model, the
been considered non-faulty continue reasoning now with all ARR graph of the Barcelona DWN has been derived after
ARRs, i.e., all the involved ones, proposing a fault candidate generating the set of ARRs from the mathematical model
using the local fault signature. (7) by using the perfect matching algorithm [9] that aims
to find a causal assignment which associates unknown sys-
5 Application to a Case Study tem variables with the system constraints from which they
can be calculated. Applying the partitioning algorithm to
This section briefly describes a case study in order to exem- this graph, five groups of ARRs are obtained, which corre-
plify the application of the proposed decentralised diagnosis sponds to five diagnosers that monitor a different part of the
approach in a real LSS. In particular, the transport infras- Barcelona DWN represented with different colors in Fig-
tructure of the Barcelona Drinking Water Network (DWN) ure 2. Table 2 collects the descriptions of the resultant sub-
is used. graphs, their number of ARRs and shared variables (ma-
nipulated flows through actuators) represented using circles
5.1 Case Study Description in Figure 2. At this point it should be recalled that one of
The Barcelona DWN, managed by Aguas de Barcelona, the goals of the partitioning algorithm is to reduce as much
S.A. (AGBAR), supplies drinking water to Barcelona city as possible the number of shared edges between subgraphs
and its metropolitan area through four drinking water treat- obtaining a graph decomposition as less interconnected as
ment plants: the Abrera and Sant Joan Despí plants, which possible and with similar number of vertices for each sub-
extract water from the Llobregat river, the Cardedeu plant, system (internal weight). This will allow an easier global
which extracts water from Ter river, and the Besòs plant, diagnosis configuration, not only with respect to the num-
which treats the underground flows from the aquifer of the ber of distributed diagnosers but also with respect to the
Besòs river. All source together provide a total amount of complexity of each local diagnoser Di . Thus, the appli-
flow of around 7 m3 /s. The water flow from each source cation of the approach to the Barcelona DWN implies the
is limited, what implies different water prices depending on design of five decentralised diagnosers together with a cen-
water treatments and legal extraction canons. See [16] for tralised/supervisory one, which is in charge of the coupled
further information about this system and [17] for further relations within the corresponding fault signature matrix of
details about its modelling and management criteria. the whole system.
5.2 Monitoring-oriented Model
In order to obtain a monitoring-oriented model of the DWN, Table 1: Barcelona DWN subsystems and number of both
the constitutive network elements (i.e., tanks, actuators, wa- shared elements and ARRs
ter demand sectors, nodes and sources) as well as their basic Number Color # ARRs # Shared variables
relationships should be stated [16].
1 green 4 1
By considering the mass balance at tanks and the static
2 red 5 5
relations at α network nodes, the monitoring-oriented
3 yellow 8 6
discrete-time state-space model of the DWN can be written
4 blue 8 16
as
5 purple 5 5
xk+1 = Axk + Γνk , (7a)
E1 νk = E2 , (7b)
For this example, it is important to highlight that ARRs
yk = Cxk , (7c) have been obtained by considering the following assump-
with Γ = [B Bp ], νk = [uTk dTk ]T , where x ∈ Rn is the tion.
state vector corresponding to the water volumes of the n Assumption 5.1. Fault in actuators are only taken into ac-
tanks, u ∈ Rm represents the vector of manipulated flows count. Sensors are supposed to operate properly.
102
Proceedings of the 26th International Workshop on Principles of Diagnosis
ApotA
x1
aMS
bMS_21
d 125 PAL _1 c125PAL
d1
u1
u3 vAdd
CPIV _1 u2
u4
vAdd_45
nAportA1_19
n70PAL_20
c70PAL d2
CPII _2
nAportA2_21 d110PAP _2 c110PAP c200BARs -c
u5 x2 d3
u6 vAdd_47
d200BLL _11
n200BARs -c
VF_30
c200ALT
VB _38
d200ALT _15
c200BLL
CA _17
c176BARsud c101MIR
d176BARsud _13 VMC _44
VP _39
VBSLL _43
CF176 _15 c200BARnord
d200BARnord _17
c140LLO CF200 _14 d101MIR _18
c176BARcentre
vAdd_60
n140LLO_24
aPousE n176BARcentre_33 vAdd_56
bPousE_23 VE _31
d130BAR_12 vAdd_55
CE _13
c130BAR AportT
c100LLO vAdd_57
n100LLO_22 VCO _37
CR O_20 vAdd_54
C-PR
c115 CAST
aPou Cast CCO _16 nAportT_32 vAdd_ 312
vAdd_48 d100FCE _9 c100FCE AportT
vAdd_61
VSJD _29 n100BLLsud_25 VS _36 V COA _40
ACast 8 bCast 8 bPou Cast _24 d100BLLnord _16
VRM _32 n100BLLcentre_29 VBMC_42
d115CAST
VCR _27
d80GAVi80CAS
85CRO _6
c80GAVi80CAS
u9 c100BLLsud c100BLLcentre
CRE _8 c100BLLno bPousB_26
CCA _3 aPousB
CB _4
VCA _28
x3 d54REL _8
CC 130 _19 VZF _33
VT _35
VPSJ _41
rd
CGIV _5 CC 100_11
vAdd_64
n70LLO_23 n70FLL_26 VCT _34
d70BBEsud _14
vAdd_53
vAdd_50
CPLANTA50 _7
c70LLO
CPLANTA70 _6
u7 CC50 _9
n135SCG
u8
CC70 _12
c70FLL d120POM
c 70BBEsu
d C_MO V_CON
d10COR _10 c135SCG
dPLANTA _7
PLANTA10 _10
vAdd_ 308 vAdd_ 309 c10COR
ApotLL1 c120POM
ApotLL2
Figure 2: ARR Partitioning of the Barcelona DWN
Table 2: Barcelona DWN subsystems and number of both
shared elements and ARRs S2
Number Color # ARRs # Shared variables S1 1
1 green 4 1
2
3
red
yellow
5
8
5
6
1 4
4 blue 8 16 S5 S3
5 purple 5 5
5 5
In order to easyly understand how the proposed decen-
tralised fault diagnosis approach would work, it will be ex-
S4
plained focusing on subsystems S1 and S4 presented in Fig-
ure 3 in red lines that corresponds to the subsystems in green
Figure 3: Scheme of decentralised diagnoser scheme for the
(S1 ) and in blue (in S4 ) in Figure 2. In particular, consider-
Barcelona DWN resultant subsystems and their number of
ing the set of ARRs corresponding to S1 as
shared variables
S1
r1,k = y1,k − y1,k−1 − ∆t[u1,k−1 + u2,k−1 − d1,k−1 ],
S1
r2,k = u1,k − u2,k − d2,k , Table 3: Fault signature matrix of S1
S1
r3,k = y2,k − y2,k−1 − ∆t[u5,k−1 − d3,k−1 ], ARR fy1 fu1 fu2 fy2 fu5 fu3 fu4 fu6
S1
r4,k = u3,k − u4,k − u5,k − u6,k , S1
r1,k 7 7 7
S1
the fault signature matrix presented in Table 3 can be ob- r2,k 7 7
tained. From this table, it is possible to identify the shad- S1
r3,k 7 7
owed part, which corresponds to the faults that the local di- S1
r4,k 7 7 7 7
agnoser D1 is able to isolate when a fault activates any of
the ARRs ri,k , i = 1, 2, 3, since those ARRs only involve
local variables. However, if the resiual r4,k is activated, it is
necessary that a global diagnoser interacts with D1 discrim- u6 is then in fault and hence isolated. Otherwise, D1 can
inating whether the corresponding ARR in S4 , defined here decide locally (then isolating u3 , u4 or u5 ).
S4
as r1,k , was also activated. If this is the case, the element In Table 4, the fault signature matrix for the ARRs that
103
Proceedings of the 26th International Workshop on Principles of Diagnosis
[4] Y. Pencolé and M.-O. Cordier. A formal framework
Table 4: Part of the fault signature matrix accounting shared for the decentralised diagnosis of large scale discrete
variables between S1 and S4 event systems and its application to telecommunica-
ARR . . . fu5 fu6 fu7 . . . tion networks. Artificial Intelligence, 164(1-2):121–
S1 170, 2005.
r4,k 7 7
S4
r1,k 7 7 [5] S. Indra, L. Travé-Massuyès, and E. Chanthery. De-
centralized diagnosis with isolation on request for
spacecraft. In Fault Detection, Supervision and Safety
of Technical Processes, pages 283–288, México, 2012.
contain shared variables between both S1 and S4 is pre-
S1 [6] F. Boem, R.M.G. Ferrari, T. Parisini, and M. M. Poly-
sented. There, r4,k corresponds with the fourth ARR of S1 carpou. Distributed fault diagnosis for continuous-
(last row of Table 3), while time nonlinear systems: The input-output case. Annual
S4
r1,k = x3,k − x3,k−1 − ∆t[u7,k−1 + u8,k−1 Reviews in Control, 37(1):163 – 169, 2013.
[7] J. Biteus, E. Frisk, and M. Nyberg. Distributed diagno-
+ u6,k−1 − u9,k−1 ]
sis using a condensed representation of diagnoses with
corresponds with the first defined ARR for S4 . Notice that application to an automotive vehicle. IEEE Transac-
the global diagnoser should decide by looking at the ARR tions on Systems, Man, and Cybernetics – Part A: Sys-
activations occurred in this fault signature matrix and then tems and Humans, 41(6):1262–1267, November 2011.
interact with the different local diagnosers if needed. [8] I. Roychoudhury, G. Biswas, and X. Koutsoukos. De-
signing distributed diagnosers for complex continuous
6 Conclusions systems. IEEE Transactions on Automation Science
and Engineering, 6(2):277–290, April 2009.
In this paper, a decentralised fault diagnosis approach for
large-scale systems based on graph-theory has been pre- [9] M. Blanke, M. Kinnaert, J. Lunze, and
sented. The algorithm starts with the translation of the sys- M. Staroswiecki. Diagnosis and Fault-Tolerant
tem model into a graph representation. Then, applying the Control. Springer-Verlag, Berlin, Heidelberg, second
perfect matching algorithm, a set of analytical redundancy edition, 2006.
relations is obtained. From the analytical redundancy rela- [10] S. Tornil-Sin, C. Ocampo-Martinez, V. Puig, and
tion graph, the problem of graph partitioning is then solved. T. Escobet. Robust fault diagnosis of nonlinear sys-
The resultant partition consists of a set of non-overlapped tems using interval constraint satisfaction and analyt-
subgraphs whose number of vertices is as similar as possi- ical redundancy relations. IEEE Transactions on Sys-
ble and the number of interconnecting edges between them tems, Man, and Cybernetics: Systems, 44(1):18–29,
is minimal. To achieve this goal, the partitioning algorithm Jan 2014.
applies a set of procedures based on identifying the highly
[11] A. I. Zečević and D. D. Šiljak. Control of Complex Sys-
connected subgraphs with balanced number of internal and
external connections. Finally, a decentralised fault diagno- tems: Structural Constraints and Uncertainty. Com-
sis strategy is introduced and applied over the resultant set munications and Control Engineering. Springer, 2010.
of partitions. In order to illustrate and discuss the use and [12] J.A. Bondy and U.S.R. Murty. Graph Theory, vol-
application of the proposed approach, a case study based on ume 244 of Graduate Series in Mathematics. Springer,
the Barcelona DWN has been used. As further research, the 2008.
partitioning algorithm will be improved by acting directly [13] C. Ocampo-Martinez, S. Bovo, and V. Puig. Parti-
on the system model and not on the set of ARRs in order tioning approach oriented to the decentralised predic-
to generate a set of ARRs for each local diagnoser with en- tive control of large-scale systems. Journal of Process
hanced fault diagnosis properties. Control, 21(5):775–786, 2011.
[14] T.N. Bui and B.R. Moon. Genetic algorithm and
Acknowledgements graph partitioning. IEEE Transactions on Computers,
This work has been partially supported by the EFFINET 45(7):841–855, 1996.
grant FP7-ICT-2012-318556 of the European Commission [15] L. Addario-Berry, K. Dalal, and B. Reed. Degree-
and the Spanish project ECOCIS (Ref. DPI2013-48243-C2- constrained subgraphs. Discrete Applied Mathematics,
1-R). 156(7):1168–1174, 2008.
[16] C. Ocampo-Martinez, V. Puig, G. Cembrano,
References
R. Creus, and M. Minoves. Improving water manage-
[1] J. Lunze. Feedback Control of Large-Scale Systems. ment efficiency by using optimization-based control
Prentice Hall, Great Britain, 1992. strategies: the Barcelona case study. Water Science &
[2] D.D. Šiljak. Decentralized control of complex systems. Technology: Water supply, 9(5):565–575, 2009.
Academic Press, 1991. [17] C. Ocampo-Martinez, V. Puig, G. Cembrano, and
[3] L. Console, C. Picardi, and D. Theseider Duprè. A J. Quevedo. Application of predictive control strate-
framework for decentralized qualitative model-based gies to the management of complex networks in the
diagnosis. In International Joint Conference on Artifi- urban water cycle [applications of control]. IEEE Con-
cial Intelligence (IJCAI), pages 286–291, Hyderabad, trol Systems Magazine, 33(1):15–41, 2013.
India, 2007.
104