# Stochastic DES Fault Diagnosis with Coloured Interpreted Petri Nets

Authors: Doyra Mariela Muñoz; Antonio Correcher; Emilio García; Francisco Morant
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This proposal presents an online method to detect and isolate faults in stochastic discrete event systems without previous model. A coloured timed interpreted Petri Net generates the normal behavior language after an identification stage. The next step is fault detection that is carried out by comparing the observed event sequences with the expected event sequences. Once a new fault is detected, a learning algorithm changes the structure of the diagnoser, so it is able to learn new fault languages. Moreover, the diagnoser includes timed events to represent and diagnose stochastic languages. Finally, this paper proposes a detectability condition for stochastic DES and the sufficient and necessary conditions are proved.


---

## Body

## 1. Introduction

Fault diagnosis has a major role in industrial systems since it allows the fault detection as soon as possible to avoid serious damages of the system or the injury of an operator. Fault diagnosis of Discrete Event Systems (DES) is an issue that has been addressed from different approaches. A fault is a deviation of the normal or required behavior. Fault diagnosis is the process of detecting and identifying such deviations of the system by using the information available on system variables [1].According to [2], fault diagnosis aims to achieve three complementary tasks: fault detection, fault isolation, and fault identification. Fault detection is a functionality that decides whether the system works in normal conditions or whether a fault has occurred. If a fault has occurred, fault isolation aims to locate the component(s) causing the fault. Fault identification is concerned with identifying the specific nature of the fault (its size, criticality, importance, etc.). This problem has been addressed by many researchers related with developing new models, new properties, new algorithms, and efficient solutions to fault diagnosis of DES. Model based diagnosis techniques can be divided into two groups. The first group uses models which include fault-free and faulty behaviors. The second group only uses fault-free models.The work of [3, 4] has provided a formal foundation of fault diagnosis and diagnosability analysis of DES that has been the base for many approaches of diagnosis. They use an automaton which generates all the possible event sequences in nominal and faulty operation.Petri Nets (PNs) have been recognized as a suitable model to describe DES, particularly when a system is asynchronous [5, 6]. PN has been used for fault diagnosis starting from [7–9] who presented diagnosis proposals of estimating faulty states. In [10] a net unfolding approach to online asynchronous diagnosis is presented. This proposal avoids the state explosion problem that typically results from having concurrent components interacting asynchronously in a distributed system, but the computing cost of performing the online diagnosis increases for offline diagnosis. In [11], the authors extend the proposal of [3] to online fault diagnosis of modeled systems by PN. Some years later, these authors in [12] present two new algorithms to deal with the case of multiple modules and real-time communication requirements. In [13] the authors not only model faults by unobservable transitions but also include other transitions representing legal unobservable behaviors as well. They prove that all possible firing sequences corresponding to a given observation can be characterized and based on the notion of basis markings and justifications. The authors use a basis reachability tree to compute the set of basis markings; [6] changes the concept of basis marking and enumerates only a subset of the reachability space. This approach includes a different characterization in terms of new original notions such as justifications and minimal explanations. The work of [14] considers the system modeled as an interpreted PN (IPN) with partially observable states and events; the model includes the possible faults that may happen. Reference [15] proposes an online fault detection technique to avoid the redesign and the redefinition of the diagnoser when the structure of the system changes. The diagnoser waits for an observable event and an algorithm decides whether the system behavior is normal or may exhibit some possible faults. The solution of an integer linear programming (ILP) problem provides a sequence of unobservable transitions containing the faults that may have occurred. The system is modeled by IPN where fault events are modeled as unobservable transitions. It associates a different label to each transition, so it models the regular behavior. In [16] the authors started from the results of [15]. They extend the work by considering a new source of nondeterminism (different observable transitions sharing the same label) and by considering distributed systems. To conclude [17] builds an online diagnoser based on PN approach, using the ILP definition and resolution.The advantage of this class of methods lies in the possibility to give guarantees about the diagnosability of faults; moreover, if certain conditions hold, modeled faults can be precisely localized. An inherent disadvantage is that only faults explicitly considered in the system model can be detected and localized.Diagnosis methods without fault model avoid this disadvantage; moreover, they build straightforward models since no special knowledge of system fault behavior is necessary. Nevertheless, the main drawback of these approaches is how to locate the fault since the models have less knowledge. Moreover, diagnosability of a given set of faults usually cannot be guaranteed. These methods are based on comparing the system outputs with model nominal outputs. In [18, 19] the proposed method compares the observed and the expected behavior, a fault can be detected, and a set of fault candidates is determined. Inspired by residuals known from diagnosis in continuous systems, different set operations are introduced to generate the fault candidate set. After fault detection and a first fault localization, a procedure is given to locate the fault more precisely by an analysis of the further observed system behavior.Coloured Petri Nets (CPNs) have also been oriented to fault diagnosis. Some approaches deal with combinatorial explosion, so they can be used to diagnose large systems. In [20], the authors present a method for modeling flexible manufacturing systems including fault models (based on fault trees). In [21], the authors present a method for modeling and diagnosing an orchestrated complex Web service. This approach is very restrictive to Web services models. In [22] the author presents a method for including the fault diagnosis within an embedded controller. The integration between diagnosis and controller in a reduced CPN model is suitable since it allows merging information about device states in a single token. Nevertheless, this approach has the same weak point as other model based approaches; it needs a fault model.Reference [23] presented a new diagnosis method based on CPN called Latent Nestling Method. The initial model of the normal behavior of the system is performed from modeling techniques, based on generalized PNs. However, for complex systems the synthesis capabilities of CPNs can be used in these modeling steps. The set of faults to be diagnosed are defined and assigned to the subset of coloured tokens. A faulty event will be defined by establishing dynamic conditions in every marking and subsequently in every state reached by the system and the set of unexpected signals of the sensor readings. Next the coloured tokens of faulty events are allocated in appropriate places called places of latent nestling faults. These tokens are susceptible to fire from that place by the activation of an event sequence, s, associated with an abnormal sensor reading.Regarding diagnosability [3] defines diagnosability in the framework of formal languages and presents necessary and sufficient conditions for diagnosability of DES. The authors in [24] focused on diagnosability of IPN. They defined and characterized the property of input-output diagnosability in IPN models, so they avoided the reachability analysis. In their next work [25], they presented a polynomial algorithm to decide if an IPN is diagnosable. Reference [26] provides a necessary and sufficient condition for diagnosability of bounded PNs, namely, PNs whose set of reachable markings is finite. The effectiveness of the proposed procedure was illustrated in [27]. They showed that, under certain conditions, the number of basis markings (a basis marking is a marking reached from M
0 with the firing of σ
0, where σ
0
∈
T
r
0
∣
L
σ
0
=
ω, and of all unobservable transitions whose firing is strictly necessary to enable ω) is always smaller than the number of reachable markings (that increase exponentially with the size of the net).Approach of the Work. In [2], the authors made a classification of diagnosis methods with respect to a number of criteria such as fault compilation (offline or online), modeling tools (automaton, PN, and state machines), fault representation (fault model: event-based or state-based, fault-free model), and decision structure or architecture (centralized, decentralized, and distributed). According to this classification, the diagnoser presented in this proposal can be classified as online fault diagnosis, based on PN without previous model and under a centralized structure.In general terms the proposal is based on language theory and on stochastic timed interpreted Petri Nets (st-ICPN), as structures to generate DES languages. The diagnosis process starts by identifying the fault-free model, from the observed language. As a result, a st-ICPN language generator is built. The generator of the fault-free language is a base to building the diagnoser and, in addition, to the concepts of Coloured Petri Nets. A learning algorithm modifies the net structure each time a new fault is detected, so the diagnoser is able to learn fault languages. The net structure changes with each new detected fault. The modifications are as follows: addition of a token in the fault transition, modification of the arcs linking that transition, and the addition of a specific fault token to the initial marking.The main advantages of this proposal about other diagnosis methodologies are the generation of deterministic models and the absence of previous fault models. The learning algorithm guarantees the diagnosis of faults not included in the fault set.This paper is organized as follows: Section2 describes the background on PN; Section 3 describes the fault behavior; Section 4 presents the diagnosis method; Section 5 shows an application case; and finally, the concluding remarks and discussion are shown in Section 6.


## 2. Background

This section introduces the formalism and definitions used in the paper.


### 2.1. System under Study

In real systems, there are various stochastic disturbances such as sensor noises, stochastic disturbance, fault, or random variation of parameters. Thus, the system representation should be based on stochastic models [28]; therefore, the system to be diagnosed is a stochastic DES, whose dynamics can be described by the interrelation of I
/
O signals and its behavior could be described with formal languages based on event sequences; the system is split into c subsystems; a subsystem is a part of a system with a particular behavior. This structure can be seen in Figure 1.Figure 1
Complex system.In a closed loop system, there exist two kinds of inputs. Some inputs are external observable SCADA commands or operator requirements that modify the operation mode of the controller (E
x
I
n
C). The other kind of inputs is external events affecting the plant (E
x
I
n
P); these inputs can be either observable or unobservable. E
x
I
n
P includes disturbances and interaction with other systems or faults. Moreover, control commands are plant inputs and can be considered as internal signals (I
n
t
I
n
P) of the closed loop model. When the system can be split into subsystems, control commands can be considered as local or global. A control command is considered global if it is applied to more than one subsystem, and it is considered local otherwise.System outputs are sensor reading; each sensor reading belongs to a subsysteml; then, the set of sensor readings (S) will be S
=
∪
S
r
l. An input symbol for a subsystem l is composed of global and local control commands, [
g
c
c
1
⋯
g
c
c
n
g
c
c
c
l
,
1
⋯
c
c
l
,
n
l
,
c
c
], where g
c
c
i
,
i
=
1
⋯
n
g
c, are global control commands and c
c
l
,
j
,
j
=
1
⋯
n
l
,
c
c, are local control commands; it is represented as u
l
,
s, u
l
,
s being a binary representation of s; s stands for the input symbol at time τ
i. An output symbol for a subsystem l is s
r
l
,
1
⋯
s
r
l
,
n
l; it is represented as y
l
,
j, y
l
,
j being a binary representation of j; j stands for the output symbol at time τ
i. An operation mode is composed of a combination of E
x
I
n
C signals, [
e
c
1
⋯
e
c
n
e
c
]; it is represented as o
o
m, o
o
m being a binary representation of o
m; o
m stands for the external event at time τ
i. For example, given a set of sensor readings for subsystem l
=
1


:
S
r
1
=
s
r
1,1
,
s
r
1,2; if s
r
1,1
=
1 and s
r
1,2
=
0, then the output symbol is represented by y
1,2.


### 2.2. Events and Languages

LetΩ
1
,
Ω be two event sets, such that Ω
1
⊂
Ω. A language, L, defined over Ω is a set of finite-length strings formed from events in Ω; that is, L
⊂
Ω
*. The projection operation, P
:
Ω
*
→
Ω
1, is defined as P
Ω
ɛ
=
ɛ; P
Ω
a
s
=
a
P
s if a
∈
Ω
1
,
s
∈
Ω
1
*; P
Ω
a
s
=
P
s if a
∉
Ω
1. Given s
,
s
′
⊂
Ω
*, s
s
′ is the concatenation of s and s
′. s is the length of s.Definition 1 (compound event).
Given two event setsΩ
p
,
Ω
q and given two events e
p and e
q, such that e
p
∈
Ω
p and e
q
∈
Ω
q, a compound event ω is the concatenation of e
p and e
q; ω
=
e
p
e
q. Ω
=
Ω
p
Ω
q is a compound event set (Ω over Ω
p
Ω
q) and a language defined over Ω will be L
⊂
Ω
p
Ω
q
*.
For example, given two event setsΩ
p
=
p
1
,
p
2, Ω
q
=
q
1
,
q
2, a compound event set will be Ω
=
p
1
q
1
,
p
1
q
2
,
p
2
q
1
,
p
2
q
2.Definition 2 (projection operation over compound event sets,P
c).
Given a compound event setΩ over Ω
p
Ω
q, P
c operation over compound events, P
c
:
Ω
→
Ω
q, is P
c
Ω
q
ɛ
=
ɛ; P
c
Ω
q
e
p
e
q
=
P
Ω
q
e
p
P
Ω
q
e
q.
P
c used at the previous example will give P
c
:
Ω
→
Ω
p; P
c
Ω
p
p
2
q
2
=
p
2. Given an event sequence s
∣
s
∈
Ω
*, where s
=
p
1
q
1
p
2
q
2
p
1
q
1, P
c of s over Ω
p is P
c
Ω
p
s
=
p
1
p
2
p
1.Definition 3 (timed event and stochastic timed event).
A timed event is a composition of an event and the elapsed time between two consecutive events. Thene
i
=
e
·
t
ev at time τ
i, where t
ev
=
τ
current
_
ev
-
τ
previous
_
ev.
A language,L, defined over timed event set Ω is a set of finite-length strings formed from timed events in Ω; that is, L
⊂
Ω
*; L
=
{
s
∣
s
⊂
Ω
*
}, where s is a timed event sequence, at times τ
0
≤
⋯
≤
τ
k. In real systems, it is nearly impossible to repeat the same event sequence with the same times between events. In that case, if times fit a probability density function, t
ev
~
f
(
t
ev
), timed events are called stochastic timed events.Definition 4 (projection operation of timed event sequences:P
t).
Given two timed event setsΩ
1
,
Ω, such that Ω
1
⊆
Ω, let s
=
e
0
⋯
e
k be a timed event sequence with e
i
=
e
·
t
ev; the projection operation of timed event sequences, P
t
:
Ω
*
→
Ω
1, is defined as P
t
Ω
1
s
=
P
t
Ω
1
e
0
⋯
P
t
Ω
1
e
k, for all e
i
∈
s, which is calculated as follows: a variable is started to zero t
proy
=
0; for i
=
0
⋯
k, P
t
Ω
1
e
i
=
e
·
t
ev if e
i
∈
Ω
1; then t
proy
=
t
ev and the variable back to zero t
proy
=
0; else P
t
Ω
1
e
i
=
ɛ and t
proy
=
t
proy
+
t
ev.For example (see Figure2), given a timed set Ω
1
=
e
1
·
t
e
1
,
e
3
·
t
e
3, let s be a timed event sequence, s
=
e
1
·
t
e
1
e
2
·
t
e
2
e
3
·
t
e
3; P
t
:
Ω
*
→
Ω
1; P
t
Ω
1
s
=
P
t
Ω
1
e
1
·
t
e
1
P
t
Ω
1
e
2
·
t
e
2
P
t
Ω
1
e
3
·
t
e
3; thenfori
=
0,
e
1
·
t
e
1
∈
Ω
1; then t
proy
=
t
e
1; P
t
Ω
1
e
1
·
t
e
1
=
e
1
·
t
proy; t
proy
=
0;
fori
=
1,
e
2
·
t
e
2
∉
Ω
1; then t
proy
=
t
proy
+
t
e
2
=
t
e
2; P
t
Ω
1
e
2
·
t
e
2
=
ɛ;
fori
=
2,
e
3
·
t
e
3
∈
Ω
1; then t
proy
=
t
proy
+
t
e
3
=
t
e
2
+
t
e
3; P
t
Ω
1
e
3
·
t
e
3
=
e
3
·
t
proy.Figure 2
Example ofP
t.ThereforeP
t
Ω
1
s
=
e
1
·
t
e
1
e
3
·
t
e
2
+
t
e
3.Now, ifΩ
1
=
e
4
·
f
t
e
4
e
5
·
f
t
e
5 and given a stochastic timed event sequence s
=
e
4
·
t
e
4
e
5
·
t
e
5, then P
t of s over Ω
1 is P
t
Ω
1
s
=
P
t
Ω
1
e
4
·
t
e
4
P
t
Ω
1
e
5
·
t
e
5, where P
t
Ω
1
e
4
·
t
e
4
=
e
4
·
t
e
4 if e
4
∈
Ω
1
∧
a
≤
t
e
4
≤
b, where ∫
a
b
f
t
e
4
≥
1
-
α, 1
-
α is the confidence level.


### 2.3. Petri Nets

Petri Nets (PNs) are widely used for modeling DES ([29]). A PN, N, is a bipartite digraph represented by the five-tuple N
=
P
,
T
R
,
P
r
e
,
P
o
s
t
,
M
0, where P is a set of places with cardinality n
p and T
R is a set of transitions with cardinality n
t
r; P
r
e
:
P
×
T
R
→
N and P
o
s
t
:
T
R
×
P
→
N are thePre andPost incidence matrices
I
=
P
o
s
t
-
P
r
e. The marking function M
:
P
→
N represents the number of tokens residing inside each place; M
0 is the initial marking [30, 31]. For thePre andPost sets, the dot notation is used: t
r
·
=
p
∈
P
:
P
r
e
p
,
t
r
>
0 [31].IPN is an extension of PN allowing the association of input and output signals to models [32].Definition 5 (interpreted Petri Net).
An IPN is a tupleQ
=
N
,
U
o
,
Y
,
λ
,
φ, where N is a PN. U
o
=
u
0
,
u
1
,
…
,
u
2
m
o
-
1 is the observable inputs set, u
s is an input symbol, and m
o is the number of observable inputs; Y
=
y
0
,
y
1
,
…
,
y
2
n
-
1 is the output set, y
j is an output symbol, and n is the number of outputs; λ
:
T
R
→
U
o is a transition labeling function that assigns an input symbol to each transition. φ
:
R
(
N
)
→
Y is an output function that assigns an output symbol to each reachable marking.Differential of output symbols is introduced in [33] to avoid IPN nondeterminism.Definition 6 (differential of output symbold
y).
Given two output symbolsy
j
,
y
j
-
1
∈
Y, at times τ
i and τ
i
-
1, respectively, d
y
j is defined as d
y
j
(
y
j
×
y
j
-
1
)
→
{
-
1,0
,
1
}, where d
y
j
=
y
j
-
y
j
-
1 with d
y
j
∈
{
-
1,0
,
1
}; so d
y
j possible values are 0
×
0
→
0; 0
×
1
→
1; 1
×
0
→
-
1; 1
×
1
→
0.
A st-IPN is defined as follows.Definition 7 (stochastic timed interpreted Petri Net (st-IPN) (see [33])).
A st-IPN is a structure represented bys
t
Q
=
Q
,
Ω
,
δ
,
O
M, where Q
=
N
,
U
o
,
Y
,
λ
,
φ is an IPN; N
,
U
o
,
Y have the same meaning as in Definition 5; λ
:
T
R
→
U
o
×
δ is a labeling function that assigns an input symbol and a time density function to each transition; φ is defined as φ
:
R
N
→
Y
/
d
Y; φ is isomorphic over Y
/
d
Y. Consider Ω
:
=
U
o
×
Y. δ is the system alphabet. δ
:
=
T
R
×
O
M
→
f
(
t
T
R
×
O
M
) is a transition firing time density function for each o
o
m. O
M
=
o
0
,
…
,
o
2
n
e
c
-
1 is the set of operation modes.
The system alphabetΩ
=
U
o
×
Y. δ relates signals. A letter ω
i
∈
Ω is a symbol that concatenates input signals and output signals at every instant τ
i, (I/O symbol); this symbol is a compound event as in Definition 1 but is a timed event (see Definition 3); therefore Ω is a timed compound event set over U
o
,
Y. Consider(1)
ω
i
=
u
s
y
j
·
t
ev
.Definition 8 (st-ICPN language).
TheL
s
t
C
Q is L
s
t
C
Q
=
{
s
∣
s
⊂
Ω
*
}, where s
=
ω
0
,
…
,
ω
k is a timed compound event sequence, at times τ
0
≤
⋯
≤
τ
k; that is, s is an ordered sequence at a time line. If the elapsed time between events is not constant, the time fits a probability density function f
t
ev, that is, t
ev
~
f
(
t
ev
), and L
s
t
C
Q is a stochastic language.
Coloured Petri Nets (CPNs) have formal semantics, and they allow different types of analysis [34]. CPNs are defined as follows.Definition 9 (Coloured Petri Net (CPN) (see [35])).
A CPN is defined by a tupleC
N
=
P
,
T
R
,
C
,
c
d
,
P
r
e
,
P
o
s
t
,
M
0, where P, T
R have the same meaning of a PN; C
=
clas
s
1
,
…
,
clas
s
n
c
c is the set of colour classes with cardinality n
c
c; c
d
:
P
∪
T
R
→
C is the colour domain mapping; P
r
e
,
P
o
s
t
∈
β
P
×
T
R are incidence matrices, such that P
r
e
p
,
t
r
:
c
d
t
r
→
B
a
g
c
d
p and P
o
s
t
p
,
t
r
:
c
d
t
r
→
B
a
g
c
d
p are mappings for each pair p
,
t
∈
P
×
T
R. β can be taken as the set of mappings of the form f
:
c
d
t
r
→
B
a
g
c
d
p. Representation of the incidence matrices entries P
r
e and P
o
s
t will be by vectors. A place marking is a vector, such that m
p
→
B
a
g
c
d
p for each p
∈
P; m
0 is the initial marking.
If a CPN has output and transition labeling functions, it can be considered as an ICPN. Therefore, a PN including the characteristics of CPN and st-IPN can be defined as follows.Definition 10 (stochastic timed interpreted Coloured Petri Net (st-ICPN)).
A st-ICPN is a structure represented bys
t
C
Q
=
C
N
,
U
o
,
Y
,
λ
,
φ
,
Ω
,
δ
,
O
M, where C
N is a CPN defined as in Definition 9, U
o
,
Y are input and output alphabets, respectively, U
o
=
∪
U
o
c
l and Y
=
∪
Y
c
l, with c
l
=
1
:
n
c
c, λ
:
T
R
×
B
a
g
c
d
t
r
→
U
o. δ is the transition labeling function. φ
:
R
(
C
N
)
×
B
a
g
c
d
p
→
Y
/
d
Y is the output function. Consider Ω
:
=
U
o
×
Y. δ is the system alphabet. δ
:
=
T
R
×
O
M
×
C
→
f
(
t
T
R
×
O
M
×
C
) is the transition firing time density function for each o
o
m in each c
l. O
M
=
o
0
,
…
,
o
2
n
e
c
-
1 is the set of operation modes.
A transitiont
r
r
∈
T
R with λ
(
t
r
j
)
=
u
s
·
f
t
t
r
r
,
o
o
m
,
c
l is enabled with respect to c
d
t
r at operation mode o
o
m, if and only if, for all p
q
∈
t
r
r
·, m
p
q
≥
P
r
e
t
r
·
c
d
t
r and if a
≤
t
ev
≤
b, where ∫
a
b
f
t
t
r
r
,
o
o
m
,
c
l
≥
1
-
α, 1
-
α is the confidence level and a
,
b is the confidence interval. If t
r
r is enabled and t
r
r is fired a new marking M
k
+
1 is reached; it is computed with the classical state space equation: M
k
+
1
=
M
k
+
I
·
t
r
r
→,  y
j
/
d
y
j
=
φ
M
k.Definition 11 (firing language of a st-ICPN).
Letσ
c
l be a firing sequence σ
c
l
=
t
r
1
⋯
t
r
k for colour class c
l, of a s
t
C
Q, such that M
0
⌈
σ
i
>
M
k. The set of all firing sequences for the colour class c
l is called the firing language L
F
c
l
s
t
C
Q for c
l. Consider L
F
c
l
s
t
C
Q
=
{
σ
c
l
∣
P
r
o
b
(
σ
c
l
∣
m
0
)
≥
1
-
α
}.
The transition and output labeling sequences generated byσ
c
l allow the definition of the generated languages as follows.Definition 12 (input and output languages of a st-ICPN).
Letσ
c
l be a firing sequence such that σ
c
l
∈
L
F
c
l
(
s
t
C
Q
); the input language for c
l is defined as the labeling function sequences of the t
r
r
∈
L
F
c
l
(
s
t
C
Q
); that is, L
in
c
l
s
t
C
Q
=
{
σ
c
l
∣
σ
c
l
=
λ
t
r
1
⋯
λ
t
r
k
}, and the output language for c
l is defined as the reached marking sequences by the firing of σ
c
l; that is, L
out
c
l
s
t
C
Q
=
φ
M
0
⋯
φ
M
k. st-ICPN language is L
s
t
C
Q
=
L
c
l
s
t
C
Q.


## 2.1. System under Study

In real systems, there are various stochastic disturbances such as sensor noises, stochastic disturbance, fault, or random variation of parameters. Thus, the system representation should be based on stochastic models [28]; therefore, the system to be diagnosed is a stochastic DES, whose dynamics can be described by the interrelation of I
/
O signals and its behavior could be described with formal languages based on event sequences; the system is split into c subsystems; a subsystem is a part of a system with a particular behavior. This structure can be seen in Figure 1.Figure 1
Complex system.In a closed loop system, there exist two kinds of inputs. Some inputs are external observable SCADA commands or operator requirements that modify the operation mode of the controller (E
x
I
n
C). The other kind of inputs is external events affecting the plant (E
x
I
n
P); these inputs can be either observable or unobservable. E
x
I
n
P includes disturbances and interaction with other systems or faults. Moreover, control commands are plant inputs and can be considered as internal signals (I
n
t
I
n
P) of the closed loop model. When the system can be split into subsystems, control commands can be considered as local or global. A control command is considered global if it is applied to more than one subsystem, and it is considered local otherwise.System outputs are sensor reading; each sensor reading belongs to a subsysteml; then, the set of sensor readings (S) will be S
=
∪
S
r
l. An input symbol for a subsystem l is composed of global and local control commands, [
g
c
c
1
⋯
g
c
c
n
g
c
c
c
l
,
1
⋯
c
c
l
,
n
l
,
c
c
], where g
c
c
i
,
i
=
1
⋯
n
g
c, are global control commands and c
c
l
,
j
,
j
=
1
⋯
n
l
,
c
c, are local control commands; it is represented as u
l
,
s, u
l
,
s being a binary representation of s; s stands for the input symbol at time τ
i. An output symbol for a subsystem l is s
r
l
,
1
⋯
s
r
l
,
n
l; it is represented as y
l
,
j, y
l
,
j being a binary representation of j; j stands for the output symbol at time τ
i. An operation mode is composed of a combination of E
x
I
n
C signals, [
e
c
1
⋯
e
c
n
e
c
]; it is represented as o
o
m, o
o
m being a binary representation of o
m; o
m stands for the external event at time τ
i. For example, given a set of sensor readings for subsystem l
=
1


:
S
r
1
=
s
r
1,1
,
s
r
1,2; if s
r
1,1
=
1 and s
r
1,2
=
0, then the output symbol is represented by y
1,2.


## 2.2. Events and Languages

LetΩ
1
,
Ω be two event sets, such that Ω
1
⊂
Ω. A language, L, defined over Ω is a set of finite-length strings formed from events in Ω; that is, L
⊂
Ω
*. The projection operation, P
:
Ω
*
→
Ω
1, is defined as P
Ω
ɛ
=
ɛ; P
Ω
a
s
=
a
P
s if a
∈
Ω
1
,
s
∈
Ω
1
*; P
Ω
a
s
=
P
s if a
∉
Ω
1. Given s
,
s
′
⊂
Ω
*, s
s
′ is the concatenation of s and s
′. s is the length of s.Definition 1 (compound event).
Given two event setsΩ
p
,
Ω
q and given two events e
p and e
q, such that e
p
∈
Ω
p and e
q
∈
Ω
q, a compound event ω is the concatenation of e
p and e
q; ω
=
e
p
e
q. Ω
=
Ω
p
Ω
q is a compound event set (Ω over Ω
p
Ω
q) and a language defined over Ω will be L
⊂
Ω
p
Ω
q
*.
For example, given two event setsΩ
p
=
p
1
,
p
2, Ω
q
=
q
1
,
q
2, a compound event set will be Ω
=
p
1
q
1
,
p
1
q
2
,
p
2
q
1
,
p
2
q
2.Definition 2 (projection operation over compound event sets,P
c).
Given a compound event setΩ over Ω
p
Ω
q, P
c operation over compound events, P
c
:
Ω
→
Ω
q, is P
c
Ω
q
ɛ
=
ɛ; P
c
Ω
q
e
p
e
q
=
P
Ω
q
e
p
P
Ω
q
e
q.
P
c used at the previous example will give P
c
:
Ω
→
Ω
p; P
c
Ω
p
p
2
q
2
=
p
2. Given an event sequence s
∣
s
∈
Ω
*, where s
=
p
1
q
1
p
2
q
2
p
1
q
1, P
c of s over Ω
p is P
c
Ω
p
s
=
p
1
p
2
p
1.Definition 3 (timed event and stochastic timed event).
A timed event is a composition of an event and the elapsed time between two consecutive events. Thene
i
=
e
·
t
ev at time τ
i, where t
ev
=
τ
current
_
ev
-
τ
previous
_
ev.
A language,L, defined over timed event set Ω is a set of finite-length strings formed from timed events in Ω; that is, L
⊂
Ω
*; L
=
{
s
∣
s
⊂
Ω
*
}, where s is a timed event sequence, at times τ
0
≤
⋯
≤
τ
k. In real systems, it is nearly impossible to repeat the same event sequence with the same times between events. In that case, if times fit a probability density function, t
ev
~
f
(
t
ev
), timed events are called stochastic timed events.Definition 4 (projection operation of timed event sequences:P
t).
Given two timed event setsΩ
1
,
Ω, such that Ω
1
⊆
Ω, let s
=
e
0
⋯
e
k be a timed event sequence with e
i
=
e
·
t
ev; the projection operation of timed event sequences, P
t
:
Ω
*
→
Ω
1, is defined as P
t
Ω
1
s
=
P
t
Ω
1
e
0
⋯
P
t
Ω
1
e
k, for all e
i
∈
s, which is calculated as follows: a variable is started to zero t
proy
=
0; for i
=
0
⋯
k, P
t
Ω
1
e
i
=
e
·
t
ev if e
i
∈
Ω
1; then t
proy
=
t
ev and the variable back to zero t
proy
=
0; else P
t
Ω
1
e
i
=
ɛ and t
proy
=
t
proy
+
t
ev.For example (see Figure2), given a timed set Ω
1
=
e
1
·
t
e
1
,
e
3
·
t
e
3, let s be a timed event sequence, s
=
e
1
·
t
e
1
e
2
·
t
e
2
e
3
·
t
e
3; P
t
:
Ω
*
→
Ω
1; P
t
Ω
1
s
=
P
t
Ω
1
e
1
·
t
e
1
P
t
Ω
1
e
2
·
t
e
2
P
t
Ω
1
e
3
·
t
e
3; thenfori
=
0,
e
1
·
t
e
1
∈
Ω
1; then t
proy
=
t
e
1; P
t
Ω
1
e
1
·
t
e
1
=
e
1
·
t
proy; t
proy
=
0;
fori
=
1,
e
2
·
t
e
2
∉
Ω
1; then t
proy
=
t
proy
+
t
e
2
=
t
e
2; P
t
Ω
1
e
2
·
t
e
2
=
ɛ;
fori
=
2,
e
3
·
t
e
3
∈
Ω
1; then t
proy
=
t
proy
+
t
e
3
=
t
e
2
+
t
e
3; P
t
Ω
1
e
3
·
t
e
3
=
e
3
·
t
proy.Figure 2
Example ofP
t.ThereforeP
t
Ω
1
s
=
e
1
·
t
e
1
e
3
·
t
e
2
+
t
e
3.Now, ifΩ
1
=
e
4
·
f
t
e
4
e
5
·
f
t
e
5 and given a stochastic timed event sequence s
=
e
4
·
t
e
4
e
5
·
t
e
5, then P
t of s over Ω
1 is P
t
Ω
1
s
=
P
t
Ω
1
e
4
·
t
e
4
P
t
Ω
1
e
5
·
t
e
5, where P
t
Ω
1
e
4
·
t
e
4
=
e
4
·
t
e
4 if e
4
∈
Ω
1
∧
a
≤
t
e
4
≤
b, where ∫
a
b
f
t
e
4
≥
1
-
α, 1
-
α is the confidence level.


## 2.3. Petri Nets

Petri Nets (PNs) are widely used for modeling DES ([29]). A PN, N, is a bipartite digraph represented by the five-tuple N
=
P
,
T
R
,
P
r
e
,
P
o
s
t
,
M
0, where P is a set of places with cardinality n
p and T
R is a set of transitions with cardinality n
t
r; P
r
e
:
P
×
T
R
→
N and P
o
s
t
:
T
R
×
P
→
N are thePre andPost incidence matrices
I
=
P
o
s
t
-
P
r
e. The marking function M
:
P
→
N represents the number of tokens residing inside each place; M
0 is the initial marking [30, 31]. For thePre andPost sets, the dot notation is used: t
r
·
=
p
∈
P
:
P
r
e
p
,
t
r
>
0 [31].IPN is an extension of PN allowing the association of input and output signals to models [32].Definition 5 (interpreted Petri Net).
An IPN is a tupleQ
=
N
,
U
o
,
Y
,
λ
,
φ, where N is a PN. U
o
=
u
0
,
u
1
,
…
,
u
2
m
o
-
1 is the observable inputs set, u
s is an input symbol, and m
o is the number of observable inputs; Y
=
y
0
,
y
1
,
…
,
y
2
n
-
1 is the output set, y
j is an output symbol, and n is the number of outputs; λ
:
T
R
→
U
o is a transition labeling function that assigns an input symbol to each transition. φ
:
R
(
N
)
→
Y is an output function that assigns an output symbol to each reachable marking.Differential of output symbols is introduced in [33] to avoid IPN nondeterminism.Definition 6 (differential of output symbold
y).
Given two output symbolsy
j
,
y
j
-
1
∈
Y, at times τ
i and τ
i
-
1, respectively, d
y
j is defined as d
y
j
(
y
j
×
y
j
-
1
)
→
{
-
1,0
,
1
}, where d
y
j
=
y
j
-
y
j
-
1 with d
y
j
∈
{
-
1,0
,
1
}; so d
y
j possible values are 0
×
0
→
0; 0
×
1
→
1; 1
×
0
→
-
1; 1
×
1
→
0.
A st-IPN is defined as follows.Definition 7 (stochastic timed interpreted Petri Net (st-IPN) (see [33])).
A st-IPN is a structure represented bys
t
Q
=
Q
,
Ω
,
δ
,
O
M, where Q
=
N
,
U
o
,
Y
,
λ
,
φ is an IPN; N
,
U
o
,
Y have the same meaning as in Definition 5; λ
:
T
R
→
U
o
×
δ is a labeling function that assigns an input symbol and a time density function to each transition; φ is defined as φ
:
R
N
→
Y
/
d
Y; φ is isomorphic over Y
/
d
Y. Consider Ω
:
=
U
o
×
Y. δ is the system alphabet. δ
:
=
T
R
×
O
M
→
f
(
t
T
R
×
O
M
) is a transition firing time density function for each o
o
m. O
M
=
o
0
,
…
,
o
2
n
e
c
-
1 is the set of operation modes.
The system alphabetΩ
=
U
o
×
Y. δ relates signals. A letter ω
i
∈
Ω is a symbol that concatenates input signals and output signals at every instant τ
i, (I/O symbol); this symbol is a compound event as in Definition 1 but is a timed event (see Definition 3); therefore Ω is a timed compound event set over U
o
,
Y. Consider(1)
ω
i
=
u
s
y
j
·
t
ev
.Definition 8 (st-ICPN language).
TheL
s
t
C
Q is L
s
t
C
Q
=
{
s
∣
s
⊂
Ω
*
}, where s
=
ω
0
,
…
,
ω
k is a timed compound event sequence, at times τ
0
≤
⋯
≤
τ
k; that is, s is an ordered sequence at a time line. If the elapsed time between events is not constant, the time fits a probability density function f
t
ev, that is, t
ev
~
f
(
t
ev
), and L
s
t
C
Q is a stochastic language.
Coloured Petri Nets (CPNs) have formal semantics, and they allow different types of analysis [34]. CPNs are defined as follows.Definition 9 (Coloured Petri Net (CPN) (see [35])).
A CPN is defined by a tupleC
N
=
P
,
T
R
,
C
,
c
d
,
P
r
e
,
P
o
s
t
,
M
0, where P, T
R have the same meaning of a PN; C
=
clas
s
1
,
…
,
clas
s
n
c
c is the set of colour classes with cardinality n
c
c; c
d
:
P
∪
T
R
→
C is the colour domain mapping; P
r
e
,
P
o
s
t
∈
β
P
×
T
R are incidence matrices, such that P
r
e
p
,
t
r
:
c
d
t
r
→
B
a
g
c
d
p and P
o
s
t
p
,
t
r
:
c
d
t
r
→
B
a
g
c
d
p are mappings for each pair p
,
t
∈
P
×
T
R. β can be taken as the set of mappings of the form f
:
c
d
t
r
→
B
a
g
c
d
p. Representation of the incidence matrices entries P
r
e and P
o
s
t will be by vectors. A place marking is a vector, such that m
p
→
B
a
g
c
d
p for each p
∈
P; m
0 is the initial marking.
If a CPN has output and transition labeling functions, it can be considered as an ICPN. Therefore, a PN including the characteristics of CPN and st-IPN can be defined as follows.Definition 10 (stochastic timed interpreted Coloured Petri Net (st-ICPN)).
A st-ICPN is a structure represented bys
t
C
Q
=
C
N
,
U
o
,
Y
,
λ
,
φ
,
Ω
,
δ
,
O
M, where C
N is a CPN defined as in Definition 9, U
o
,
Y are input and output alphabets, respectively, U
o
=
∪
U
o
c
l and Y
=
∪
Y
c
l, with c
l
=
1
:
n
c
c, λ
:
T
R
×
B
a
g
c
d
t
r
→
U
o. δ is the transition labeling function. φ
:
R
(
C
N
)
×
B
a
g
c
d
p
→
Y
/
d
Y is the output function. Consider Ω
:
=
U
o
×
Y. δ is the system alphabet. δ
:
=
T
R
×
O
M
×
C
→
f
(
t
T
R
×
O
M
×
C
) is the transition firing time density function for each o
o
m in each c
l. O
M
=
o
0
,
…
,
o
2
n
e
c
-
1 is the set of operation modes.
A transitiont
r
r
∈
T
R with λ
(
t
r
j
)
=
u
s
·
f
t
t
r
r
,
o
o
m
,
c
l is enabled with respect to c
d
t
r at operation mode o
o
m, if and only if, for all p
q
∈
t
r
r
·, m
p
q
≥
P
r
e
t
r
·
c
d
t
r and if a
≤
t
ev
≤
b, where ∫
a
b
f
t
t
r
r
,
o
o
m
,
c
l
≥
1
-
α, 1
-
α is the confidence level and a
,
b is the confidence interval. If t
r
r is enabled and t
r
r is fired a new marking M
k
+
1 is reached; it is computed with the classical state space equation: M
k
+
1
=
M
k
+
I
·
t
r
r
→,  y
j
/
d
y
j
=
φ
M
k.Definition 11 (firing language of a st-ICPN).
Letσ
c
l be a firing sequence σ
c
l
=
t
r
1
⋯
t
r
k for colour class c
l, of a s
t
C
Q, such that M
0
⌈
σ
i
>
M
k. The set of all firing sequences for the colour class c
l is called the firing language L
F
c
l
s
t
C
Q for c
l. Consider L
F
c
l
s
t
C
Q
=
{
σ
c
l
∣
P
r
o
b
(
σ
c
l
∣
m
0
)
≥
1
-
α
}.
The transition and output labeling sequences generated byσ
c
l allow the definition of the generated languages as follows.Definition 12 (input and output languages of a st-ICPN).
Letσ
c
l be a firing sequence such that σ
c
l
∈
L
F
c
l
(
s
t
C
Q
); the input language for c
l is defined as the labeling function sequences of the t
r
r
∈
L
F
c
l
(
s
t
C
Q
); that is, L
in
c
l
s
t
C
Q
=
{
σ
c
l
∣
σ
c
l
=
λ
t
r
1
⋯
λ
t
r
k
}, and the output language for c
l is defined as the reached marking sequences by the firing of σ
c
l; that is, L
out
c
l
s
t
C
Q
=
φ
M
0
⋯
φ
M
k. st-ICPN language is L
s
t
C
Q
=
L
c
l
s
t
C
Q.


## 3. Fault Behavior

The system generates a language that can be split into sublanguages, taking into account if a fault has occurred or not.L
l is the language generated by a subsystem.The set of timed compound events is partitioned into observable and unobservable events,Ω
l
=
Ω
o
l
∪
Ω
u
o
l, where Ω
u
o
l includes two subsets: fault and regular unobservable event subsets Ω
u
o
l
=
Ω
f
l
∪
Ω
re
g
l (adapted from [36]). An event ω
l
i
∈
Ω
l is of the form ω
l
i
=
u
l
,
s
y
l
,
j
·
t
ev (see (1)). The set of normal timed compound events Ω
N
l is a subset of Ω
o
l such that L
N
l
⊂
Ω
N
l
*.A timed fault event can be defined as follows.Definition 13 (timed fault event).
Given a timed event sequences and an event of the form ω
l
i
*
=
u
l
,
s
y
l
,
j
·
t
ev and if s
∈
L
N
l
∧
s
ω
l
i
*
∉
L
N
l, then ω
l
i
* is a timed fault event.A fault event,ω
l
i, does not belong to the normal language (based on Definition 2) ω
l
i
=
u
l
,
s
i
y
l
,
j
i
·
t
ev
∉
L
N
l ( the superscript “i” has been added to identify the event time), if(i)
P
c
Ω
N
l
u
l
,
s
i
∉
L
in
N
l
∧
P
c
Ω
N
l
y
l
,
j
i
∈
L
out
N
l or
(ii)
P
c
Ω
N
l
u
l
,
s
i
∈
L
in
N
l
∧
P
c
Ω
N
l
y
l
,
j
i
∉
L
out
N
l or
(iii)
P
c
Ω
N
l
u
l
,
s
i
∉
L
in
N
l
∧
P
c
Ω
N
l
y
l
,
j
i
∉
L
out
N
l or
(iv)
P
c
Ω
N
l
u
l
,
s
i
∈
L
in
N
l
∧
P
c
Ω
N
l
y
l
,
j
i
∈
L
out
N
l but t
ev
∉
a
,
b; ∫
a
b
f
t
≥
1
-
α; 1
-
α is the confidence level and f
t is the density function of normal event, ω
l
i
∈
L
N
l
/
s.In cases (i), (ii), and (vi) the fault event is observable and in case (iii) the fault event is unobservable. Fault language can be defined as follows.Definition 14 (fault language,L
F
l).
Given a timed event sequences, the fault language is L
F
l
=
{
s
t
∣
s
∈
L
N
l
∧
t
∈
L
/
s
∧
∃
ω
l
i
*
∈
t
∣
ω
l
i
*
∉
L
N
l
}, that is, the set of all timed event sequences with at least one timed fault event in the postlanguage of a normal sequence.


## 4. Diagnosis Method

The diagnoser proposed in this paper works without any previous knowledge of the system language. The diagnoser construction starts with the identification of the normal behavior, which results in a set of st-IPNs that generate the observed normal language.L
N
l is the language generated by the identified st-IPN for subsystem l. The diagnosis task is carried out by comparing the current event trace t with L
N
l. If t
∉
L
N
l, a timed fault event has been detected. The algorithm creates a language model recognizer for this new situation and t is considered as part of a fault language, L
f
i.Once a fault has been detected, a fault filtering algorithm allows the full diagnosis. This algorithm takes into account flow sharing (data, materials, or energy) between subsystems. The consequence of flow sharing is that a subsystem that operates without fault could reach an erroneous state, not described inL
N
l. This problem happens when the subsystem does not receive the prospective service (the flow) of another subsystem linked to it. Flow stopping could be due to failures in another subsystem up or down the line [37]. In order to include this fact in the diagnoser the notion of shared flow sensor (SFS) is introduced.When a fault has been detected and it has not been eliminated by the filtering algorithm, the structure of diagnoser proposed allows isolating and identifying the fault; at this time a new fault trace ofL
f
i is learned by the diagnoser. So, the diagnosis skills of the diagnoser grow over time.


### 4.1. Architecture for the Diagnostic Method

As it was mentioned in the previous section, the diagnoser is based on a set of identified st-IPNs. The diagnoser also includes color in order to compare languages and detect faults. So the diagnoser is astochastic timed interpreted Coloured Petri Net to diagnosis (st-DICPN), which is shown in Figure 3.Figure 3
st-DICPN architecture.The set of places is partitioned intoP
l
=
P
L
N
l
∪
P
V
F
l
∪
P
I
F
l, where P
L
N
l represents the set of latent nestling places, that is, places with nominal behavior in which a fault can happen; P
V
F
l is the set of places that verify the detected fault kind; P
I
F
l is a place that counts the identified faults.The set of transitions is partitioned intoT
R
l
=
T
R
N
l
∪
T
R
F
l, where T
R
N
l represents the set of normal transitions that fire following the normal language and T
R
F
l represents the set of fault transitions whose size can be increased each time a fault event is detected; they fire when a fault f
d
f is detected.The set of colour classes isC
l
=
Behavior
,
V
F
,
I
F
,
Mode, where Behavior
=
N
l
,
l
,
q
g
f
g
f
l: N
l is the normal token, l
,
q
g
f
g
f
l is the generic fault token, l stands for the subsystem, q stands for the place, and the subscript g
f
l is a fault identification index; V
F
=
l
,
q
g
f
g
f
l; I
F
=
integer is variable token that depends on variable d
f, and the Mode colour class set includes the colours assigned to transitions, where Mode
=
m
_
N
,
m
_
f
d
f: m
_
N is “normal mode” and m
_
f
d
f is “detected fault mode d
f.”In Figure4, the part of the net in green colour represents the normal behavior which is identified online from the observed legal sequences. The part of the net in black colour represents the identified fault behavior by means of applying the diagnostic algorithm. This net has a variable structure because the diagnosis process learns the fault languages.Figure 4
st-DICPN with fault.In Figure4, when a fault is detected on place p
l
,
0, d
f
=
1, the transition t
r
1,3 fires in m
_
f
1 mode and then a colour token l
,
0
g
f
1 is reached in p
l
,
2 (VF place) and an integer 1 is reached in p
l
,
3 (IF place). In this moment, thefut function is executed and the arcs and transitions structure increases, so p
r
e
(
p
l
,
0
,
t
r
l
,
3
)
=
l
,
0
g
f
1
;
l
,
0
g
f
g
f, p
o
s
t
(
p
l
,
0
,
t
r
l
,
3
)
=
l
,
0
g
f
g
f, p
o
s
t
(
p
l
,
2
,
t
r
l
,
3
)
=
l
,
0
g
f
1, p
o
s
t
(
p
l
,
3
,
t
r
l
,
3
)
=
1, and the token in transition t
r
l
,
3 is m
_
f
1
;
m
_
f
d
f.The incidence matrix entries are represented by vectors [35]. If a fault f
1 is detected in place (p
l
,
0), thenPre andPost matrices will be updated as shown as follows.Pre
(2)
t
r
l
,
1
t
r
l
,
2
t
r
l
,
3
t
r
l
,
4
m
_
N
m
_
N
m
_
f
d
f
m
_
f
1
m
_
f
d
f
p
l
,
0
p
l
,
1
p
l
,
2
p
l
,
3
N
l
0
0
0
0
N
l
0
0
N
l
∧
l
,
0
g
f
1
N
l
∧
l
,
0
g
f
g
f
0
0
0
0
N
l
∧
l
,
1
g
f
g
f
0
0
.Post
(3)
t
r
l
,
1
t
r
l
,
2
t
r
l
,
3
t
r
l
,
4
m
_
N
m
_
N
m
_
f
d
f
m
_
f
1
m
_
f
d
f
p
l
,
0
p
l
,
1
p
l
,
2
p
l
,
3
0
N
l
0
0
N
l
0
0
0
l
,
0
g
f
g
f
0
l
,
0
g
f
1
l
,
0
g
f
g
f
1
0
l
,
1
g
f
g
f
l
,
1
g
f
g
f
0
.Definition 15 (stochastic timed interpreted Coloured Petri Net to diagnosis (st-DICPN)).
A st-DICPN for a subsysteml is defined as s
t
D
C
Q
l
=
s
t
C
Q
l
,
f
u
t, where s
t
C
Q
l
=
C
Q
l
,
Ω
l
,
δ
l is a st-ICPN defined as in Definition 10 for a subsystem l; P
l
=
P
L
N
l
∪
P
V
F
l
∪
P
I
F
l; T
R
l
=
T
R
N
l
∪
T
R
F
l; C
l
=
Behavior
,
V
F
,
I
F
,
Mode. The set of colour domain of places are c
d
P
L
N
l
=
N
l
,
l
,
q
g
f
g
f
l, c
d
P
V
F
l
=
l
,
q
g
f
g
f
l, and c
d
P
I
F
l
=
Integer. The set of colour domain of transitions are c
d
T
R
N
l
=
m
_
N
l and c
d
T
R
F
l
=
m
_
f
d
f. P
r
e
,
P
o
s
t
∈
β
P
×
T
R are incidence matrices based on Definition 9. The normal transitions labeling function is λ
l
:
T
R
N
l
×
m
_
N
→
U
l
·
δ
l. δ
l
:
=
T
R
l
×
O
M
→
f
t
T
R
l
×
O
M is the transition firing time density function for each O
M. The normal places output function is φ
l
:
R
(
C
Q
l
)
×
c
d
P
L
N
l
→
Y
l
/
d
Y
l. And f
u
t
:
M
l
×
Y
l
→
T
R
l
×
P
r
e
l
×
P
o
s
t
l is a function that updates T
R
l
,
P
r
e
l
,
P
o
s
t
l.The incidence matrices areP
r
e
p
,
t
r
:
c
d
t
r
→
c
d
p and P
o
s
t
p
,
t
r
:
c
d
t
r
→
c
d
p. That is, P
r
e
p
l
,
q
L
N
,
t
r
l
,
r
N
m
_
N
l
=
N
l; P
r
e
p
l
,
q
L
N
,
t
r
l
,
r
F
m
_
f
d
f
=
N
l
∧
l
,
q
g
f
g
f
l; P
o
s
t
p
l
,
q
L
N
,
t
r
l
,
r
N
m
_
N
l
=
N
l; P
o
s
t
p
l
,
q
L
N
,
t
r
l
,
r
F
m
f
d
f
=
l
,
q
g
f
g
f
l; P
o
s
t
p
l
,
q
V
F
,
t
r
l
,
r
F
m
_
f
d
f
=
l
,
q
g
f
g
f
l; P
o
s
t
p
l
,
q
I
F
,
t
r
l
,
r
F
m
_
f
d
f
=
x
+
1.This structure of incidence matrices allows the net evolution under normal conditions or nonpredefined event traces.


### 4.2. Online Diagnosis Process

This section proposes a procedure that specifies the online work of the diagnoser. This process has five steps and it can be seen in Figure5.Figure 5
Diagnosis process.The first step is the configuration of the system. The system has to be split into subsystems, I/O signals must be defined, and the starting event for each subsystem will beω
l
0
=
u
l
,
s
y
l
,
j
τ
0, where u
l
,
s, y
l
,
j stand for the starting values of control commands and sensor readings, at time τ
0, and the set of operation modes o
o
m has to be stated.The second step is the observation and learning of the normal behavior. The identification algorithm [33] builds a set of st-IPNs generating the observed language.The third step is the computing of the initial diagnoser which transforms the st-IPNs into st-DICPNs. The proposed algorithm modifies the net structure as follows.(i)
A normal tokenN
l will be added to each at initial place.
(ii)
The set ofP
V
F
l, P
I
F
l, and T
R
F
l will be added as well as the arcs required to complete the diagnoser architecture (as the one shown in Figure 4).
(iii)
To represent generic faults, a coloured fault token,l
,
q
g
f
g
f
l, must be added to each p
l
,
q
∈
P
L
N
l.The fourth step is the online fault detection and fault isolation. More precisely the process consists of the following.Initialize the variablesd
f
l
=
0, g
f
l
=
0, and L
f
d
f
l
= (set of identified fault traces).
Being the current state of the netp
l
,
q
∈
P
L
N
l and given an observed event, ω
l
i
*
=
u
l
,
s
i
*
y
l
,
j
i
*
·
t
l
,
o
o
m
ev.
(i)
IfP
c
Ω
N
l
ω
l
i
*
=
ω
l
i
* (see Definition 4), then ω
l
i
*
∈
L
N
l. t
r
l
,
r
∈
T
R
N
l is firing in normal mode with λ
l
t
r
l
,
r
=
u
l
,
s
.
f
t
t
r
l
,
r
,
o
o
m and a normal token is placed at m
p
l
,
q
+
1
=
N
l, with φ
l
m
p
l
,
q
+
1
=
y
l
,
j
/
d
y
l
.
j and wait for a new ω
l
i
*.
(ii)
Else, ifP
c
Ω
N
l
ω
l
i
*
=
ɛ then ω
l
i
∉
L
N
l, and a fault trace has been detected in l: d
f
l
=
d
f
l
+
1:
(a)
at
r
l
,
r
∈
T
R
F
l is firing in f
d
f
l mode, g
f
l
=
g
f
l
+
1;
(b)
a generic fault token is reached inm
p
l
,
V
F
l
=
m
p
l
,
q
l
=
l
,
q
g
f
g
f
l and another integer token is reached in p
l
,
I
F
l
=
d
f
l.This process is shown in Algorithm 1.Algorithm 1:Diagnosis process.
Inputs: L
N
l, s
t
-
D
I
C
P
N
l; ω
l
i
=
u
l
,
s
y
l
,
j
·
t
e
v, for i
=
0
,
…
,
k;
Outputs: I
F
l; L
I
F
l; update s
t
-
D
I
C
P
N
l
Initial Conditions: ω
l
0
=
u
l
,
s
y
l
,
j
·
t
e
v; I
F
l
=
[
]; L
f
d
f
l
=
{
}.
(1)i
=
0;
(2) forl
=
1
,
…
,
c
(i)q
l
=
1; p
f
l
=
0; p
f
l
=
0; f
l
=
0; d
f
l
=
0.
(ii) readu
l
,
s, y
l
,
j at time τ
0
(iii)φ
l
m
p
l
,
q
l
=
y
l
,
j
/
0
→; m
p
l
,
q
l
=
N
l;
end for
(3)i
=
i
+
1;
(4) Wait for a newω
l
i; read ω
l
i
=
u
l
,
s
y
l
,
j
τ
i;
(5)s
u
b = l
(a) ifω
l
i
=
u
l
,
s
y
l
,
j
·
t
e
v
∈
L
N
s
u
b then m
p
s
u
b
,
q
l
+
1
=
N
s
u
b and σ
N
s
u
b
=
t
r
s
u
b
,
1
,
…
,
t
r
s
u
b
,
i.
(b) elseω
l
i
=
u
l
,
s
y
l
,
j is a generic fault in p
s
u
b
,
q
s
u
b; g
f
s
u
b
=
g
f
s
u
b
+
1;
then a new t
r
l
,
r is generated as:
(i) compute ap
r
e vector of zeros except in position p
s
u
b
,
q
s
u
b which has
a value of N
l
∧
s
u
b
,
q
s
u
b
g
f
g
f
s
u
b.
(ii) compute ap
o
s
t vector of zeros except in position p
s
u
b
,
q
s
u
b
,
p
s
u
b
,
V
F
s
u
b
which has a value of s
u
b
,
q
s
u
b
g
f
g
f
s
u
b and position p
s
u
b
,
I
F which has a weight of d
f
l.
(iii) the newt
r
l
,
r fire, the net reaches the marking: m
p
s
u
b
,
V
F
s
u
b
=
s
u
b
,
q
s
u
b
p
f
p
f
s
u
b;
m
p
s
u
b
,
q
s
u
b
=
s
u
b
,
q
s
u
b
g
f
g
f
s
u
b and d
f
l
=
d
f
l
+
1. m
p
l
,
I
F
l
=
d
f
l.
(iv)f
d
f
s
u
b
=
f
d
f
s
u
b
+
1.
(v) Execute Algorithm2.
end if
(6) Wait for the next event and return to Step  (3)Algorithm 2:Fault filtering.
Input: S
F
S
r; ω
l
,
q
i
*
=
u
l
,
s
i
*
y
l
,
j
i
*
·
t
e
v
⊂
L
f
i; s
ω
l
p
∈
L
N
l is the expected sequence.
Output: I
S
F
S
r.
Initial Conditions: I
S
F
S
r
=
{
}.
IfP
Ω
N
l
y
l
,
j
i
*
=
ε then ∃
i
∣
s
r
l
,
i
*
∈
y
l
,
j
*
≠
s
r
l
,
i
∈
y
l
,
j, therefore s
r
l
,
i
=
s
r
l
,
i
e
x is the expected sensor reading.
Ifs
r
l
,
i
e
x
∈
S
F
S
r then
Forl
:
1
,
…
,
c
if∃
s
r
l
,
n
l
∈
I
S
F
S
r then, delete ω
l
,
q
i
* because is a fault propagation.
else includes
r
l
,
i
e
x in I
S
F
S
r
end if
end for
end if
else there is not a fault propagation.
end ifAt the end of this step a fault has been detected over a time line, as well as its fault trace.The fifth step eliminates the fault if it has been generated by a false alarm caused by coupling. Coupling ofs
t
-
D
I
C
P
N
l and faults propagation ([38]) are generated by interactions among subsystems. Therefore, a fault filtering algorithm is proposed, which is described below.The algorithm analyzes the shared flow sensor reading set,S
F
S
r
=
∪
s
r
l
,
n
l, where n
l is the number of sensors in subsystem l. Given an identified fault event ω
l
,
q
i
* at current time τ
a
c, L
out
ω
l
,
q
i
*
=
y
l
,
j, and y
l
,
j
=
s
r
l
,
1
⋯
s
r
l
,
n
l, the algorithm compares the values of the shared flow sensors to decide if the fault is due to propagation (Algorithm 2).Once Algorithm2 filters each fault, the st-DICPN architecture is updated and f
u
t function updates the st-DICPN as follows.(i)
Detected fault colour tokens are added in the verification place.
(ii)
The integer colour token is updated.
(iii)
A colour token,m
_
f
d
f, is added in the fired fault transition, the same way the colour token l
,
q
g
f
g
f
l is added in the involved arcs.
(iv)
The fault has been isolated and thens
ω
l
i
* is included in the set of identified fault trace, s
ω
l
i
⊂
L
f
d
f
l.Therefore, the fault trace is learned by the st-DICPN and the fault is identified.This trace contains information about the faulty subsystem as well as the unexpected behavior and it is possible to distinguish the subsystem that made the fault as well as the faulty signals.


### 4.3. Properties

The structure of as
t
D
C
Q
l is variable because the number of coloured tokens, as well as the number of transitions, grows with each new fault trace. Nevertheless, the size of each s
t
D
C
Q
l is bounded by the number of sensors.Letσ
N
l be a transition firing sequence, such that, for all t
r
l
,
r
∈
σ
N
l
,
t
r
l
,
r
∈
T
R
N
l; let s be the generated event sequence by σ
N
l such that s
∈
L
N
l
s
t
D
C
Q
l, where s
=
ω
l
0
,
…
,
ω
l
k; if φ
m
p
l
,
0
=
φ
m
p
l
,
k, then s
*
∈
L
N
l
s
t
D
C
Q; that is, s is a cycle.Given a sequence of eventss
ω
l
i
*, such that s
∈
L
N
l, s
=
ω
l
0
,
…
,
ω
l
k, at times τ
1
≤
⋯
≤
τ
k and s
ω
l
,
q
i
*
∈
L
I
F
l, then the transition firing sequence σ
F
l that generates s
ω
l
i
* is σ
F
l
=
t
r
l
,
1
,
…
,
t
r
l
,
k
,
t
r
l
,
k
+
1
,
t
r
l
,
k, where t
r
l
,
1
,
…
,
t
r
l
,
k
∈
T
R
N
l, t
r
l
,
k
+
1
∈
T
R
F
l, and M
l
,
0
⌈
σ
F
l
>
M
l
,
k, where m
p
l
,
V
F
l
=
l
,
q
g
f
g
f
l; m
p
l
,
k
=
N
,
l
,
q
g
f
g
f
l. (p
l
,
k
∈
P
L
N
l). That is, the fault language L
I
F
l
s
t
D
C
Q
=
ω
l
0
,
…
,
ω
l
k
ω
l
,
q
i
*
ω
l
k
+
1 reaches a normal token in a latent nesting place, from which the system can evolve when the fault has been repaired.


### 4.4. Detectability

The analysis of detectability presented in this proposal is based on language theory and prior works on temporal observability. Detectability proves if the system can detect the occurrence of a fault in a finite number of observable events.Based on Definition13  n-detectability is defined as follows.Definition 16 (n-detectable).
Lets
ω
l
i
* be an event sequence ending with a fault event and let t be an observable event sequence after s
ω
l
i
*, with n
=
t. Given s
1
=
s
ω
l
i
*
t, ω
l
i
*
=
u
l
,
s
y
l
,
j·t
ev is n-detectable if ∃
ω
l
i
∈
t such that (i) P
c
Ω
N
l
u
l
,
s
∉
L
in
N
l
∧
P
c
Ω
N
l
y
l
,
j
∈
L
out
N
l or (ii) P
c
Ω
N
l
u
l
,
s
∈
L
in
N
l
∧
P
c
Ω
N
l
y
l
,
j
∉
L
out
N
l or (iii) P
c
Ω
N
l
u
l
,
s
∈
L
in
N
l
∧
P
c
Ω
N
l
y
l
,
j
∈
L
out
N
l but t
ev
∉
a
,
b in n steps.Necessary and Sufficient Conditions for DetectabilityTheorem 17 (detectability).
Givens
ω
l
p, an event sequence ending with a fault event, ω
l
p, let t
1
,
t
2 be two observable events sequences, where s
,
t
1
∈
L
N
l
∧
t
1
,
t
2
∈
L
/
s; ω
l
p is detectable if P
t
Ω
N
l
s
t
1
≠
P
t
Ω
N
l
s
ω
l
p
t
2.Proof.
Ast
1
∈
L
N
l
/
s
∧
t
1
∈
L
N
l then s
t
1
∈
L
N
l. And as ω
l
p is a fault event then s
ω
l
p
t
2 is a fault trace of the s
t
D
C
Q
l, (L
f
i
=
s
ω
l
p
t
2). Give s
=
ω
l
0
,
…
,
ω
l
k and t
2
=
ω
l
q
,
…
,
ω
l
x.
Necessary Condition. If ω
l
p is detectable then P
t
Ω
N
l
s
t
1
≠
P
t
Ω
N
l
s
ω
l
p
t
2.
Ast
1
∈
L
N
l then, for all ω
l
i
∈
t
1
,
ω
l
i
∈
Ω
N
l. If ω
l
p is detectable then ∃
ω
l
i
*
∈
t
2
∣
ω
l
i
*
∈
Ω
o
l
∧
ω
l
i
*
∉
Ω
N
l (see Definition 16); therefore t
1
≠
t
2 and P
t
Ω
N
l
s
t
1
≠
P
t
Ω
N
l
s
ω
l
p
t
2.
Sufficient Condition. If P
t
Ω
N
l
s
t
1
≠
P
t
Ω
N
l
s
ω
l
p
t
2, then ω
l
p is detectable.
s
t
D
C
Q
l represents only observed languages. If s
t
1 and s
ω
l
p
t
2 are represented in a s
t
D
C
Q
l, then s
t
1 and s
t
2 must be observed event sequences.
Assuming thatP
t
Ω
N
l
s
t
1
=
P
t
Ω
N
l
s
ω
l
p
t
2, then t
2
∈
L
N
l and ω
l
p is not detectable.


## 4.1. Architecture for the Diagnostic Method

As it was mentioned in the previous section, the diagnoser is based on a set of identified st-IPNs. The diagnoser also includes color in order to compare languages and detect faults. So the diagnoser is astochastic timed interpreted Coloured Petri Net to diagnosis (st-DICPN), which is shown in Figure 3.Figure 3
st-DICPN architecture.The set of places is partitioned intoP
l
=
P
L
N
l
∪
P
V
F
l
∪
P
I
F
l, where P
L
N
l represents the set of latent nestling places, that is, places with nominal behavior in which a fault can happen; P
V
F
l is the set of places that verify the detected fault kind; P
I
F
l is a place that counts the identified faults.The set of transitions is partitioned intoT
R
l
=
T
R
N
l
∪
T
R
F
l, where T
R
N
l represents the set of normal transitions that fire following the normal language and T
R
F
l represents the set of fault transitions whose size can be increased each time a fault event is detected; they fire when a fault f
d
f is detected.The set of colour classes isC
l
=
Behavior
,
V
F
,
I
F
,
Mode, where Behavior
=
N
l
,
l
,
q
g
f
g
f
l: N
l is the normal token, l
,
q
g
f
g
f
l is the generic fault token, l stands for the subsystem, q stands for the place, and the subscript g
f
l is a fault identification index; V
F
=
l
,
q
g
f
g
f
l; I
F
=
integer is variable token that depends on variable d
f, and the Mode colour class set includes the colours assigned to transitions, where Mode
=
m
_
N
,
m
_
f
d
f: m
_
N is “normal mode” and m
_
f
d
f is “detected fault mode d
f.”In Figure4, the part of the net in green colour represents the normal behavior which is identified online from the observed legal sequences. The part of the net in black colour represents the identified fault behavior by means of applying the diagnostic algorithm. This net has a variable structure because the diagnosis process learns the fault languages.Figure 4
st-DICPN with fault.In Figure4, when a fault is detected on place p
l
,
0, d
f
=
1, the transition t
r
1,3 fires in m
_
f
1 mode and then a colour token l
,
0
g
f
1 is reached in p
l
,
2 (VF place) and an integer 1 is reached in p
l
,
3 (IF place). In this moment, thefut function is executed and the arcs and transitions structure increases, so p
r
e
(
p
l
,
0
,
t
r
l
,
3
)
=
l
,
0
g
f
1
;
l
,
0
g
f
g
f, p
o
s
t
(
p
l
,
0
,
t
r
l
,
3
)
=
l
,
0
g
f
g
f, p
o
s
t
(
p
l
,
2
,
t
r
l
,
3
)
=
l
,
0
g
f
1, p
o
s
t
(
p
l
,
3
,
t
r
l
,
3
)
=
1, and the token in transition t
r
l
,
3 is m
_
f
1
;
m
_
f
d
f.The incidence matrix entries are represented by vectors [35]. If a fault f
1 is detected in place (p
l
,
0), thenPre andPost matrices will be updated as shown as follows.Pre
(2)
t
r
l
,
1
t
r
l
,
2
t
r
l
,
3
t
r
l
,
4
m
_
N
m
_
N
m
_
f
d
f
m
_
f
1
m
_
f
d
f
p
l
,
0
p
l
,
1
p
l
,
2
p
l
,
3
N
l
0
0
0
0
N
l
0
0
N
l
∧
l
,
0
g
f
1
N
l
∧
l
,
0
g
f
g
f
0
0
0
0
N
l
∧
l
,
1
g
f
g
f
0
0
.Post
(3)
t
r
l
,
1
t
r
l
,
2
t
r
l
,
3
t
r
l
,
4
m
_
N
m
_
N
m
_
f
d
f
m
_
f
1
m
_
f
d
f
p
l
,
0
p
l
,
1
p
l
,
2
p
l
,
3
0
N
l
0
0
N
l
0
0
0
l
,
0
g
f
g
f
0
l
,
0
g
f
1
l
,
0
g
f
g
f
1
0
l
,
1
g
f
g
f
l
,
1
g
f
g
f
0
.Definition 15 (stochastic timed interpreted Coloured Petri Net to diagnosis (st-DICPN)).
A st-DICPN for a subsysteml is defined as s
t
D
C
Q
l
=
s
t
C
Q
l
,
f
u
t, where s
t
C
Q
l
=
C
Q
l
,
Ω
l
,
δ
l is a st-ICPN defined as in Definition 10 for a subsystem l; P
l
=
P
L
N
l
∪
P
V
F
l
∪
P
I
F
l; T
R
l
=
T
R
N
l
∪
T
R
F
l; C
l
=
Behavior
,
V
F
,
I
F
,
Mode. The set of colour domain of places are c
d
P
L
N
l
=
N
l
,
l
,
q
g
f
g
f
l, c
d
P
V
F
l
=
l
,
q
g
f
g
f
l, and c
d
P
I
F
l
=
Integer. The set of colour domain of transitions are c
d
T
R
N
l
=
m
_
N
l and c
d
T
R
F
l
=
m
_
f
d
f. P
r
e
,
P
o
s
t
∈
β
P
×
T
R are incidence matrices based on Definition 9. The normal transitions labeling function is λ
l
:
T
R
N
l
×
m
_
N
→
U
l
·
δ
l. δ
l
:
=
T
R
l
×
O
M
→
f
t
T
R
l
×
O
M is the transition firing time density function for each O
M. The normal places output function is φ
l
:
R
(
C
Q
l
)
×
c
d
P
L
N
l
→
Y
l
/
d
Y
l. And f
u
t
:
M
l
×
Y
l
→
T
R
l
×
P
r
e
l
×
P
o
s
t
l is a function that updates T
R
l
,
P
r
e
l
,
P
o
s
t
l.The incidence matrices areP
r
e
p
,
t
r
:
c
d
t
r
→
c
d
p and P
o
s
t
p
,
t
r
:
c
d
t
r
→
c
d
p. That is, P
r
e
p
l
,
q
L
N
,
t
r
l
,
r
N
m
_
N
l
=
N
l; P
r
e
p
l
,
q
L
N
,
t
r
l
,
r
F
m
_
f
d
f
=
N
l
∧
l
,
q
g
f
g
f
l; P
o
s
t
p
l
,
q
L
N
,
t
r
l
,
r
N
m
_
N
l
=
N
l; P
o
s
t
p
l
,
q
L
N
,
t
r
l
,
r
F
m
f
d
f
=
l
,
q
g
f
g
f
l; P
o
s
t
p
l
,
q
V
F
,
t
r
l
,
r
F
m
_
f
d
f
=
l
,
q
g
f
g
f
l; P
o
s
t
p
l
,
q
I
F
,
t
r
l
,
r
F
m
_
f
d
f
=
x
+
1.This structure of incidence matrices allows the net evolution under normal conditions or nonpredefined event traces.


## 4.2. Online Diagnosis Process

This section proposes a procedure that specifies the online work of the diagnoser. This process has five steps and it can be seen in Figure5.Figure 5
Diagnosis process.The first step is the configuration of the system. The system has to be split into subsystems, I/O signals must be defined, and the starting event for each subsystem will beω
l
0
=
u
l
,
s
y
l
,
j
τ
0, where u
l
,
s, y
l
,
j stand for the starting values of control commands and sensor readings, at time τ
0, and the set of operation modes o
o
m has to be stated.The second step is the observation and learning of the normal behavior. The identification algorithm [33] builds a set of st-IPNs generating the observed language.The third step is the computing of the initial diagnoser which transforms the st-IPNs into st-DICPNs. The proposed algorithm modifies the net structure as follows.(i)
A normal tokenN
l will be added to each at initial place.
(ii)
The set ofP
V
F
l, P
I
F
l, and T
R
F
l will be added as well as the arcs required to complete the diagnoser architecture (as the one shown in Figure 4).
(iii)
To represent generic faults, a coloured fault token,l
,
q
g
f
g
f
l, must be added to each p
l
,
q
∈
P
L
N
l.The fourth step is the online fault detection and fault isolation. More precisely the process consists of the following.Initialize the variablesd
f
l
=
0, g
f
l
=
0, and L
f
d
f
l
= (set of identified fault traces).
Being the current state of the netp
l
,
q
∈
P
L
N
l and given an observed event, ω
l
i
*
=
u
l
,
s
i
*
y
l
,
j
i
*
·
t
l
,
o
o
m
ev.
(i)
IfP
c
Ω
N
l
ω
l
i
*
=
ω
l
i
* (see Definition 4), then ω
l
i
*
∈
L
N
l. t
r
l
,
r
∈
T
R
N
l is firing in normal mode with λ
l
t
r
l
,
r
=
u
l
,
s
.
f
t
t
r
l
,
r
,
o
o
m and a normal token is placed at m
p
l
,
q
+
1
=
N
l, with φ
l
m
p
l
,
q
+
1
=
y
l
,
j
/
d
y
l
.
j and wait for a new ω
l
i
*.
(ii)
Else, ifP
c
Ω
N
l
ω
l
i
*
=
ɛ then ω
l
i
∉
L
N
l, and a fault trace has been detected in l: d
f
l
=
d
f
l
+
1:
(a)
at
r
l
,
r
∈
T
R
F
l is firing in f
d
f
l mode, g
f
l
=
g
f
l
+
1;
(b)
a generic fault token is reached inm
p
l
,
V
F
l
=
m
p
l
,
q
l
=
l
,
q
g
f
g
f
l and another integer token is reached in p
l
,
I
F
l
=
d
f
l.This process is shown in Algorithm 1.Algorithm 1:Diagnosis process.
Inputs: L
N
l, s
t
-
D
I
C
P
N
l; ω
l
i
=
u
l
,
s
y
l
,
j
·
t
e
v, for i
=
0
,
…
,
k;
Outputs: I
F
l; L
I
F
l; update s
t
-
D
I
C
P
N
l
Initial Conditions: ω
l
0
=
u
l
,
s
y
l
,
j
·
t
e
v; I
F
l
=
[
]; L
f
d
f
l
=
{
}.
(1)i
=
0;
(2) forl
=
1
,
…
,
c
(i)q
l
=
1; p
f
l
=
0; p
f
l
=
0; f
l
=
0; d
f
l
=
0.
(ii) readu
l
,
s, y
l
,
j at time τ
0
(iii)φ
l
m
p
l
,
q
l
=
y
l
,
j
/
0
→; m
p
l
,
q
l
=
N
l;
end for
(3)i
=
i
+
1;
(4) Wait for a newω
l
i; read ω
l
i
=
u
l
,
s
y
l
,
j
τ
i;
(5)s
u
b = l
(a) ifω
l
i
=
u
l
,
s
y
l
,
j
·
t
e
v
∈
L
N
s
u
b then m
p
s
u
b
,
q
l
+
1
=
N
s
u
b and σ
N
s
u
b
=
t
r
s
u
b
,
1
,
…
,
t
r
s
u
b
,
i.
(b) elseω
l
i
=
u
l
,
s
y
l
,
j is a generic fault in p
s
u
b
,
q
s
u
b; g
f
s
u
b
=
g
f
s
u
b
+
1;
then a new t
r
l
,
r is generated as:
(i) compute ap
r
e vector of zeros except in position p
s
u
b
,
q
s
u
b which has
a value of N
l
∧
s
u
b
,
q
s
u
b
g
f
g
f
s
u
b.
(ii) compute ap
o
s
t vector of zeros except in position p
s
u
b
,
q
s
u
b
,
p
s
u
b
,
V
F
s
u
b
which has a value of s
u
b
,
q
s
u
b
g
f
g
f
s
u
b and position p
s
u
b
,
I
F which has a weight of d
f
l.
(iii) the newt
r
l
,
r fire, the net reaches the marking: m
p
s
u
b
,
V
F
s
u
b
=
s
u
b
,
q
s
u
b
p
f
p
f
s
u
b;
m
p
s
u
b
,
q
s
u
b
=
s
u
b
,
q
s
u
b
g
f
g
f
s
u
b and d
f
l
=
d
f
l
+
1. m
p
l
,
I
F
l
=
d
f
l.
(iv)f
d
f
s
u
b
=
f
d
f
s
u
b
+
1.
(v) Execute Algorithm2.
end if
(6) Wait for the next event and return to Step  (3)Algorithm 2:Fault filtering.
Input: S
F
S
r; ω
l
,
q
i
*
=
u
l
,
s
i
*
y
l
,
j
i
*
·
t
e
v
⊂
L
f
i; s
ω
l
p
∈
L
N
l is the expected sequence.
Output: I
S
F
S
r.
Initial Conditions: I
S
F
S
r
=
{
}.
IfP
Ω
N
l
y
l
,
j
i
*
=
ε then ∃
i
∣
s
r
l
,
i
*
∈
y
l
,
j
*
≠
s
r
l
,
i
∈
y
l
,
j, therefore s
r
l
,
i
=
s
r
l
,
i
e
x is the expected sensor reading.
Ifs
r
l
,
i
e
x
∈
S
F
S
r then
Forl
:
1
,
…
,
c
if∃
s
r
l
,
n
l
∈
I
S
F
S
r then, delete ω
l
,
q
i
* because is a fault propagation.
else includes
r
l
,
i
e
x in I
S
F
S
r
end if
end for
end if
else there is not a fault propagation.
end ifAt the end of this step a fault has been detected over a time line, as well as its fault trace.The fifth step eliminates the fault if it has been generated by a false alarm caused by coupling. Coupling ofs
t
-
D
I
C
P
N
l and faults propagation ([38]) are generated by interactions among subsystems. Therefore, a fault filtering algorithm is proposed, which is described below.The algorithm analyzes the shared flow sensor reading set,S
F
S
r
=
∪
s
r
l
,
n
l, where n
l is the number of sensors in subsystem l. Given an identified fault event ω
l
,
q
i
* at current time τ
a
c, L
out
ω
l
,
q
i
*
=
y
l
,
j, and y
l
,
j
=
s
r
l
,
1
⋯
s
r
l
,
n
l, the algorithm compares the values of the shared flow sensors to decide if the fault is due to propagation (Algorithm 2).Once Algorithm2 filters each fault, the st-DICPN architecture is updated and f
u
t function updates the st-DICPN as follows.(i)
Detected fault colour tokens are added in the verification place.
(ii)
The integer colour token is updated.
(iii)
A colour token,m
_
f
d
f, is added in the fired fault transition, the same way the colour token l
,
q
g
f
g
f
l is added in the involved arcs.
(iv)
The fault has been isolated and thens
ω
l
i
* is included in the set of identified fault trace, s
ω
l
i
⊂
L
f
d
f
l.Therefore, the fault trace is learned by the st-DICPN and the fault is identified.This trace contains information about the faulty subsystem as well as the unexpected behavior and it is possible to distinguish the subsystem that made the fault as well as the faulty signals.


## 4.3. Properties

The structure of as
t
D
C
Q
l is variable because the number of coloured tokens, as well as the number of transitions, grows with each new fault trace. Nevertheless, the size of each s
t
D
C
Q
l is bounded by the number of sensors.Letσ
N
l be a transition firing sequence, such that, for all t
r
l
,
r
∈
σ
N
l
,
t
r
l
,
r
∈
T
R
N
l; let s be the generated event sequence by σ
N
l such that s
∈
L
N
l
s
t
D
C
Q
l, where s
=
ω
l
0
,
…
,
ω
l
k; if φ
m
p
l
,
0
=
φ
m
p
l
,
k, then s
*
∈
L
N
l
s
t
D
C
Q; that is, s is a cycle.Given a sequence of eventss
ω
l
i
*, such that s
∈
L
N
l, s
=
ω
l
0
,
…
,
ω
l
k, at times τ
1
≤
⋯
≤
τ
k and s
ω
l
,
q
i
*
∈
L
I
F
l, then the transition firing sequence σ
F
l that generates s
ω
l
i
* is σ
F
l
=
t
r
l
,
1
,
…
,
t
r
l
,
k
,
t
r
l
,
k
+
1
,
t
r
l
,
k, where t
r
l
,
1
,
…
,
t
r
l
,
k
∈
T
R
N
l, t
r
l
,
k
+
1
∈
T
R
F
l, and M
l
,
0
⌈
σ
F
l
>
M
l
,
k, where m
p
l
,
V
F
l
=
l
,
q
g
f
g
f
l; m
p
l
,
k
=
N
,
l
,
q
g
f
g
f
l. (p
l
,
k
∈
P
L
N
l). That is, the fault language L
I
F
l
s
t
D
C
Q
=
ω
l
0
,
…
,
ω
l
k
ω
l
,
q
i
*
ω
l
k
+
1 reaches a normal token in a latent nesting place, from which the system can evolve when the fault has been repaired.


## 4.4. Detectability

The analysis of detectability presented in this proposal is based on language theory and prior works on temporal observability. Detectability proves if the system can detect the occurrence of a fault in a finite number of observable events.Based on Definition13  n-detectability is defined as follows.Definition 16 (n-detectable).
Lets
ω
l
i
* be an event sequence ending with a fault event and let t be an observable event sequence after s
ω
l
i
*, with n
=
t. Given s
1
=
s
ω
l
i
*
t, ω
l
i
*
=
u
l
,
s
y
l
,
j·t
ev is n-detectable if ∃
ω
l
i
∈
t such that (i) P
c
Ω
N
l
u
l
,
s
∉
L
in
N
l
∧
P
c
Ω
N
l
y
l
,
j
∈
L
out
N
l or (ii) P
c
Ω
N
l
u
l
,
s
∈
L
in
N
l
∧
P
c
Ω
N
l
y
l
,
j
∉
L
out
N
l or (iii) P
c
Ω
N
l
u
l
,
s
∈
L
in
N
l
∧
P
c
Ω
N
l
y
l
,
j
∈
L
out
N
l but t
ev
∉
a
,
b in n steps.Necessary and Sufficient Conditions for DetectabilityTheorem 17 (detectability).
Givens
ω
l
p, an event sequence ending with a fault event, ω
l
p, let t
1
,
t
2 be two observable events sequences, where s
,
t
1
∈
L
N
l
∧
t
1
,
t
2
∈
L
/
s; ω
l
p is detectable if P
t
Ω
N
l
s
t
1
≠
P
t
Ω
N
l
s
ω
l
p
t
2.Proof.
Ast
1
∈
L
N
l
/
s
∧
t
1
∈
L
N
l then s
t
1
∈
L
N
l. And as ω
l
p is a fault event then s
ω
l
p
t
2 is a fault trace of the s
t
D
C
Q
l, (L
f
i
=
s
ω
l
p
t
2). Give s
=
ω
l
0
,
…
,
ω
l
k and t
2
=
ω
l
q
,
…
,
ω
l
x.
Necessary Condition. If ω
l
p is detectable then P
t
Ω
N
l
s
t
1
≠
P
t
Ω
N
l
s
ω
l
p
t
2.
Ast
1
∈
L
N
l then, for all ω
l
i
∈
t
1
,
ω
l
i
∈
Ω
N
l. If ω
l
p is detectable then ∃
ω
l
i
*
∈
t
2
∣
ω
l
i
*
∈
Ω
o
l
∧
ω
l
i
*
∉
Ω
N
l (see Definition 16); therefore t
1
≠
t
2 and P
t
Ω
N
l
s
t
1
≠
P
t
Ω
N
l
s
ω
l
p
t
2.
Sufficient Condition. If P
t
Ω
N
l
s
t
1
≠
P
t
Ω
N
l
s
ω
l
p
t
2, then ω
l
p is detectable.
s
t
D
C
Q
l represents only observed languages. If s
t
1 and s
ω
l
p
t
2 are represented in a s
t
D
C
Q
l, then s
t
1 and s
t
2 must be observed event sequences.
Assuming thatP
t
Ω
N
l
s
t
1
=
P
t
Ω
N
l
s
ω
l
p
t
2, then t
2
∈
L
N
l and ω
l
p is not detectable.


## 5. Application Case

As application case, it has used the centralized air heating system, AHS; it has been identified as a set of st-IPNs in [33].The system includes three heating subsystems. Each heating subsystem has a fan creating an air flow that is heated with hot water. The water flow is controlled by pump-valve systems. Moreover, there are a central heater providing hot water to each heating subsystem and two valves (v
c
1 and v
c
2) controlling the water flow through the whole system. The system can be split into five subsystems (1, 2, 3, 4, and 5). Subsystems 3, 4, and 5 are the local heaters, subsystem 2 is the distribution subsystem (v
c
1 and v
c
2), and subsystem 1 is the main heating subsystem (heater, main pump (p
m), and reflux valve (v
r)). The heater works in three modes (
0,1
,
2
), each state is defined by the number of resistances it has activated; so modes 0, 1, and 2 will represent no activation of resistance, activation of h
1, and activation of both h
1 and h
2.The system has a set of sensors. Each subsysteml includes a flow sensor (F
l) that measures the presence or absence of flow. Nevertheless, flow level is affected when other subsystems are activated. So, a software sensor (N
F
l) is designed to measure the deviation over a normal operation flow taking into account the activation of other subsystems. The system also includes binary temperature sensors, pressure sensors, and a position sensor for valve V
c
1.The initial conditions in each subsystem are(4)
ω
1
0
=
v
¯
r
p
¯
g
v
¯
g
h
¯
1
h
¯
2
,
T
o
T
¯
1
T
¯
2
F
¯
1
=
u
1,0
y
1,8
;
ω
2
0
=
v
¯
c
1
v
¯
c
2
,
P
¯
o
F
¯
2
N
F
¯
2
=
u
2,0
y
2,0
;
ω
3
0
=
p
¯
3
v
¯
3
,
F
¯
3
N
F
¯
3
=
u
3,0
y
3,0
;
ω
4
0
=
p
¯
4
v
¯
4
,
F
¯
4
N
F
¯
4
=
u
4,0
y
4,0
;
ω
5
0
=
p
¯
5
v
¯
5
,
F
¯
5
N
F
¯
5
=
u
5,0
y
5,0
.The system globally starts with the external event “Son”; the heating subsystems are locally started with events “Ca3,” “Ca4,” and “Ca5.” These events are external events that change the controller strategy. Each combination of external events generates a system operation mode. For example, o
12
=
S
o
n
,
C
a
3
,
C
a
4
¯
,
C
a
5
¯.We have simulated the system, including some changes in the operation modes:o
0
–
o
8
–
o
12
–
o
8
–
o
0. That sequence means that “Son” works from time 1 to 85 and “Ca3” works from time 15 to 75.Step 1. The identified normal languages for each subsystem are:(5)
L
N
1
=
u
1,0
y
1,8
u
1,30
y
1,9
u
1,30
y
1,13
u
1,15
y
1,13
L
N
1
=
u
1,15
y
1,15
u
1,30
y
1,15
u
1,30
y
1,13
u
1,0
y
1,9
L
N
1
=
u
1,0
y
1,8
at
times
τ
0
,
τ
1
,
τ
2
,
τ
3
,
τ
5
,
τ
8
,
τ
9
,
τ
12
,
τ
13
,
L
N
2
=
u
2,0
y
2,0
at
time
τ
0
,
L
N
3
=
u
3,0
y
3,0
u
3,3
y
3,2
u
3,3
y
3,3
u
3,3
y
3,2
u
3,3
y
3,0
L
N
1
=
u
3,0
y
3,0
at
times
τ
0
,
τ
4
,
τ
6
,
τ
7
,
τ
10
,
τ
11
,
L
N
4
=
u
4,0
y
4,0
at
time
τ
0
,
L
N
5
=
u
5,0
y
5,0
at
time
τ
0
.The identified transition firing time density functions for eacho
o
m, δ
l are shown in Table 1.Table 1
Identified density functions for AHS system.
Transition
o
8
o
12
t
r
1,1
N(16.6, 0.51)
t
r
1,2
27
t
r
1,3
N
(115.1, 0.32)
t
r
1,4
12
t
r
1,5
N
(593, 1.5)
t
r
1,6
2
t
r
1,7
N
(91.5, 1.2)
t
r
1,8
9
t
r
1,9
1
t
r
3,1
N
(158.08, 2.52)
t
r
3,2
N
(26.93, 1.201)
t
r
3,3
N
(565.06, 1.201)
t
r
3,4
3
t
r
3,5
1Step 2. The set of the flow sensors is S
F
S
r
=
s
r
1,4
,
s
r
2,1
,
s
r
2,2
,
s
r
3,1
,
s
r
4,1
,
s
r
5,1.Generic fault in all places is assumed, in all involved subsystems of the identified operation modes sequence.Step 3. Assuming a fault in the main pump at time 60 min and a fault in the heater at time 70 min at subsystem 1, the observed event sequence at subsystem 1 is s
1
=
u
1,0
y
1,8
u
1,30
y
1,9
u
1,30
y
1,13
u
1,15
y
1,13
u
1,15
y
1,15
u
1,15
y
1,13
u
1,30
y
1,8
u
1,0
y
1,8
u
1,15
y
1,9, at times τ
0
,
τ
1
,
τ
2
,
τ
3
,
τ
5
,
τ
7
,
τ
9
,
τ
11
,
τ
12 with δ
=
0,17,27,114,12,454,268,39,95 and at subsystem 3: s
2
=
u
3,0
y
3,0
u
3,3
y
3,2
u
3,3
y
3,3
u
3,3
y
3,0
u
3,0
y
3,0, at times τ
0
,
τ
4
,
τ
6
,
τ
8
,
τ
10 with δ
=
0,159,28,520,46.Step 4Inputs. L
N
l, s
t
-
D
I
C
P
N
l.Initial Conditions. Consider ω
1
0
=
u
1,0
y
1,8
τ
0; ω
3
0
=
u
3,0
y
3,0
τ
0; φ
1
m
p
1,1
=
y
1,8
/
0000; m
p
1,1
=
N
1; φ
3
m
p
3,1
=
y
3,0
/
00; m
p
3,1
=
N
3.Inτ
1, ω
1
1
=
u
1,30
y
1,9
·
17; P
t
Ω
N
1
ω
1
1
=
u
1,30
y
1,9
·
17; then λ
1
t
r
1,1
=
u
1,30
·
f
t
t
r
1,1
,
8 and m
p
1,2
=
N
1 with φ
1
m
p
1,2
=
y
1,9
/
0001.Inτ
2, ω
1
2
=
u
1,30
y
1,13
·
27; P
t
Ω
N
1
ω
1
1
=
u
1,30
y
1,13
·
27; then λ
1
t
r
1,2
=
u
1,30
·
f
t
t
r
1,2
,
8 and m
p
1,3
=
N
1 with φ
1
m
p
1,3
=
y
1,13
/
0100.Inτ
3, ω
1
3
=
u
1,15
y
1,13
·
114; P
t
Ω
N
1
ω
1
3
=
u
1,15
y
1,13
·
114; then λ
1
t
r
1,3
=
u
1,15
·
f
t
t
r
1,3
,
12 and m
p
1,4
=
N
1 with φ
1
m
p
1,4
=
y
1,13
/
0000.Inτ
4, ω
3
4
=
u
3,3
y
3,2
·
159; P
t
Ω
N
3
ω
3
4
=
u
3,3
y
3,2
·
159; then λ
3
t
r
3,1
=
u
3,3
·
f
t
t
r
3,1
,
12 and m
p
3,2
=
N
3 with φ
3
m
p
3,2
=
y
3,2
/
10.Inτ
5, ω
1
5
=
u
1,15
y
1,15
·
12; P
t
Ω
N
1
ω
1
5
=
u
1,15
y
1,15
·
12; then λ
1
t
r
1,4
=
u
1,15
·
f
t
t
r
1,4
,
12 and m
p
1,5
=
N
1 with φ
1
m
p
1,5
=
y
1,15
/
0010.Inτ
6, ω
3
6
=
u
3,3
y
3,3
·
28; P
t
Ω
N
1
ω
3
6
=
u
3,3
y
3,3
·
28; then λ
3
t
r
3,2
=
u
1,3
·
f
t
t
r
3,2
,
12 and m
p
3,3
=
N
3 with φ
3
m
p
3,3
=
y
3,3
/
01.Inτ
7, ω
1
7
=
u
1,15
y
1,13
·
454; P
t
Ω
N
1
ω
1
7
=
ɛ; then ω
1
7 is a generic fault at the subsystem 1; t
proy
=
454; a new fault mode m
_
f
1 is added in t
r
1,10
∈
T
R
F
1, with p
r
e
=
0000
1,5
g
f
1
∧
N
1
000000, p
o
s
t
=
0000
1,5
g
f
1
0000
1,5
g
f
1
x and it adds a fault token to m
p
1
,
v
f
1
=
m
p
1,5
=
1,5
g
f
1 and m
p
1
,
i
f
1
=
1. This fault is added in Table 2.Table 2
Detected faults.
Fault
Subsystem
Place
Expecteds
r
Faults
r
Meaning
s
r
l
,
i
e
x
I
S
F
S
r
(1, 5)g
f
1
1
5
1111
1110
T
o
T
1
T
2
F
¯
1
s
r
1,4
s
r
1,4
(3, 3)g
f
1
3
3
10
00
F
¯
3
N
F
¯
3
s
r
3,1
s
r
1,4, s
r
3,1
(1, 5)g
f
2
1
5
1111
1101
T
o
T
1
T
¯
2
F
¯
1
s
r
1,3Algorithm
2
Execution. Consider s
r
l
,
i
e
x
=
s
r
1,4 and s
r
1,4
∈
S
F
S
r.Inτ
8, ω
3
8
=
u
3,3
y
3,0
·
520; P
t
Ω
N
3
ω
3
8
=
ɛ; then ω
3
8 is a generic fault at the subsystem 3; a new fault mode m
_
f
1 is added in t
r
3,6
∈
T
R
F
3, with p
r
e
=
00
3,3
g
f
1
∧
N
3
0000,   p
o
s
t
=
00
3,3
g
f
1
00
3,3
g
f
1
x and it adds a fault token to m
p
3
,
v
f
3
=
m
p
3,3
=
3,3
g
f
1 and m
p
3
,
i
f
3
=
1. This fault is added in Table 2.Algorithm
2
Execution. Consider s
r
l
,
i
e
x
=
s
r
3,1 and s
r
3,1
∈
S
F
S
r; then the detected generic fault is a propagation fault and therefore is eliminated.Inτ
9, ω
1
9
=
u
1,15
y
1,9
·
268; P
t
Ω
N
1
ω
1
9
=
ɛ; then ω
1
9 is a generic fault at the subsystem 1; t
proy
=
454
+
268; t
r
1,10
∈
T
R
F
1 is fired in mode m
_
f
2 with p
r
e
=
0000
1,5
g
f
1
∧
N
1
;
1,5
g
f
2
∧
N
1
000000, p
o
s
t
=
[
0000
1,5
g
f
1
;
1,5
g
f
2
0000
1,5
g
f
1
;
1,5
g
f
2
x
] and m
p
1
,
v
f
1
=
m
p
1,5
=
1,5
g
f
2 and m
p
1
,
i
f
1
=
2. This fault is added in Table 2.Algorithm
2
Execution. Consider g
f
2 is not a fault propagation.Thereforeω
1
0
ω
1
1
ω
1
2
ω
1
3
ω
1
5
ω
1
7 is a fault trace; that is, ω
1
0
ω
1
1
ω
1
2
ω
1
3
ω
1
5
ω
1
7
⊂
L
f
1.Interpretation. Based on Table 2, 1,5
g
f
1 is a detected fault that has happened in subsystem 1. It has been detected because there is no flow. Therefore the fault may have occurred due to a main pump fault since the sensor s
1,4 measures the flow after the pump. 3,3
g
f
1 is not fault and 1,5
g
f
2 is a fault in the heater.


## 6. Conclusions

The presented method detects and isolates faults in stochastic DES without previous behavior model. To achieve this goal a diagnoser that represents the system languages (normal and fault behaviors) is defined. The diagnoser is a deterministic language generator that avoids the combinatorial explosion of states. The proposed fault identification works online and it uses PN as the language generator. Moreover, the proposed structure generates stochastic timed languages. The st-DICPN has a structure without deadlocks and allows a detectability test based on the timed projection operation, which is defined, too. The diagnosis methodology guarantees the detection and isolation of nonmodeled faults. It has been shown that the system learns the fault languages, so the next time the same fault happens, the diagnoser will be able to conclude that the same fault has occurred.



---

*Source: 303107-2015-03-17.xml*