- This talk focuses on on-line fault diagnosis of discrete event systems based on Petri nets. In particular a diagnosis approach based on the notion of basis markings and justifications is discussed. This concept allows us to represent the reachability space in a compact manner, i.e., it requires to enumerate only a subset of the reachability space. Arbitrary labeled Petri nets are considered as the reference model. Some results on diagnosability analysis are finally recalled.
Failure detection and isolation in industrial systems is a subject that has received a lot of attention in the past few decades. A failure is defined to be any deviation of a system from its normal or intended behavior. Diagnosis is the process of detecting an abnormality in the system behavior and isolating the cause or the source of this abnormality.
The first contributions in the discrete event systems
framework have been proposed in the context of automata by
Sampath et al. [
More recently, Petri net (PN) models have been used in
the context of diagnosis [
In this talk we recall an approach we proposed in [
Note that the approach here presented, as most of the approaches dealing with diagnosis of discrete event systems, assumes that the faulty behavior is completely known, thus a fault model is available.
The last part of the talk is devoted to briefly recall some results on diagnosability analysis that may also be applied to unbounded nets.
A Place/Transition net (P/T net) is a structure N = (P, T, P re, P ost), where P is a set of m places; T is a set of n transitions; P re : P × T → N and P ost : P × T → N are the pre– and post– incidence functions that specify the arcs; C = P ost − P re is the incidence matrix.
A marking is a vector M : P → N that assigns to each place of a P/T net a nonnegative integer number of tokens, represented by black dots. The marking of place p is denoted as M (p). A P/T system or net system ⟨N, M0⟩ is a net N with an initial marking M0. A transition t is enabled at M iff M ≥ P re(· , t) and may fire yielding the marking M ′ = M + C(· , t). One writes M [σ⟩ to denote that the sequence of transitions σ = tj1 · · · tjk is enabled at M , and M [σ⟩ M ′ to denote that the firing of σ yields M ′. One writes t ∈ σ to denote that a transition t is contained in σ.
The set of all sequences that are enabled at the initial marking M0 is denoted L(N, M0), i.e., L(N, M0) = {σ ∈ T ∗ | M0[σ⟩}.
Given a sequence σ ∈ T ∗, let π : T ∗ → Nn be the function that associates to σ a vector y ∈ Nn, called the firing vector of σ. In particular, y = π(σ) is such that y(t) = k if the transition t is contained k times in σ.
A marking M is reachable in ⟨N, M0⟩ iff there exists a firing sequence σ such that M0 [σ⟩ M . The set of all markings reachable from M0 defines the reachability set of ⟨N, M0⟩ and is denoted R(N, M0).
A PN having no directed circuits is called acyclic. A net system ⟨N, M0⟩ is bounded if there exists a positive constant k such that, for M ∈ R(N, M0), M (p) ≤ k.
The association between sensors and transitions can be captured by a labeling function L : T → L ∪ {ε} assigns to each transition t ∈ T either a symbol from a given alphabet L or the empty string ε.
The set of transitions whose label is ε is denoted as Tu, i.e., Tu = {t ∈ T | L(t) = ε}. Transitions in Tu are called unobservable or silent. To denotes the set of transitions labeled with a symbol in L. Transitions in To are called observable because when they fire their label can be observed. Note that we assume that the same label l ∈ L can be associated to more than one transition. In particular, two transitions t1, t2 ∈ To are called undistinguishable if they share the same label, i.e., L(t1) = L(t2). The set of transitions sharing the same label l are denoted as Tl.
In the following let Cu (Co) be the restriction of the incidence matrix to Tu (To) and nu and no, respectively, be the cardinality of the above sets. Moreover, given a sequence σ ∈ T ∗, Pu(σ), resp., Po(σ), denotes the projection of σ over Tu, resp., To.
The word w of events associated to sequence σ is w = Po(σ).
Definition 2.1: [
In plain words, given an observation w, S(w) is the set of sequences that may have fired, while C(w) is the set of markings in which the system may actually be.
Example 2.2: Consider the PN in Fig. 1. Assume To = {t1, t2, t3, t4, t5, t6, t7} and Tu = {ε8, ε9, ε10, ε11, ε12, ε13}, where for a better understanding unobservable transitions have been denoted εi rather than ti. The labeling function is defined as follows: L(t1) = a, L(t2) = L(t3) = b, L(t4) = L(t5) = c, L(t6) = L(t7) = d.
First consider w = ab. The set of firing sequences that is consistent with w is S(w) = {t1t2, t1t2ε8, t1t2ε8ε9, t1t2ε8ε9ε10, t1t2ε8ε11}, and the set of markings consistent with w is C(w) = {[0 0 1 0 0 0 0 1 0 0 0]T , [0 0 0 1 0 0 0 1 0 0 0]T , [0 0 0 0 1 0 0 1 0 0 0]T , [0 1 0 0 0 0 0 1 0 0 0]T , [0 0 0 0 0 1 0 1 0 0 0]T }.
If w = acd is considered the set of firing sequences that are consistent with w is S(w) = {t1t5t6, t1t5ε12ε13t7}, and the set of markings consistent with w is C(w) = {[0 1 0 0 0 0 0 1 0 0 0]T }. Thus two different firing sequences may have fired (the second one also involving silent transitions), but they both lead to the same marking.
Definition 2.3: Given a net N = (P, T, P re, P ost), and a subset T ′ ⊆ T of its transitions, let us define the T ′−induced subnet of N as the new net N ′ = (P, T ′, P re′, P ost′) where P re′, P ost′ are the restrictions of P re, P ost to T ′. The net N ′ can be thought as obtained from N removing all transitions in T \ T ′. Let us also write N ′ ≺T ′ N .
III. CHARACTERIZATION OF THE SET OF CONSISTENT
MARKINGS
Definition 3.1: [
c
Fig. 1. The PN system considered in Sections II to IV.
Y (M, t) = π(Σ(M, t)) be the e-vectors (or explanation vectors), i.e., firing vectors associated to the explanations.
Thus Σ(M, t) is the set of unobservable sequences whose firing at M enables t. Among the above sequences select those whose firing vector is minimal. The firing vector of these sequences are called minimal e-vectors.
Definition 3.2: [
Example 3.3: Consider the PN in Fig. 1 previously introduced in Example 2.2. It holds that Σ(M0, t1) = {ε}. Then Σ(M0, t2) = ∅. Finally, let M = [ 0 0 1 0 0 0 0 1 0 0 0 ]T , it holds that Σ(M, t5) = {ε, ε8, ε8ε9, ε8ε11, ε8ε9ε10}, while Σmin(M, t5) = {ε}. It follows that Y (M, t5) = {[0 0 0 0 0 0]T , [1 0 0 0 0 0]T , [1 1 0 0 0 0]T , [1 0 0 1 0 0]T , [1 1 1 0 0 0]T }, and Ymin(M, t5) = {[0 0 0 0 0 0]T }.
Definition 3.4: [
o [∃σ ∈ S(w) : σo = Po(σ), σu = Pu(σ)]∧ [̸ ∃σ′ ∈ S(w) : σo = Po(σ′), σu′ = Pu(σ′)∧ π(σu′) π(σu)]} be the set of pairs (sequence σo ∈ To∗ with L(σo) = w, corresponding justification of w).
In simple words, Jˆ(w) is the set of pairs whose first element is the sequence σo ∈ To∗ labeled w and whose second element is the corresponding sequence of unobservable transitions interleaved with σo whose firing enables σo and whose firing vector is minimal. The firing vectors of these sequences are called j-vectors.
Example 3.5: Consider the PN in Fig. 1 previously introduced in Example 2.2. It is Jˆ(ab) = {(t1t2, ε)} and Jˆ(acd) = {(t1t5t6, ε), (t1t5t7, ε12ε13)}.
The main difference among minimal explanations and
justifications is that the first ones are functions of a generic
marking M and transition t, while justifications are functions
of the initial marking M0 and w. Moreover, as shown in [
Definition 3.6: [
Obviously, because in general more than one justification exists for a word w (the set Jˆ(w) is generally not a singleton), the basis marking may be not unique as well.
Definition 3.7: [
M(w) = {(M, y) | (∃σ ∈ S(w) : M0[σ⟩M ) ∧ (∃(σo, σu) ∈ Jˆ(w) : σo = Po(σ),
σu = Pu(σ), y = π(σu))} be the set of pairs (basis marking, relative j-vector) that are consistent with w ∈ L∗.
Note that the set M(w) does not keep into account the
sequences of observable transitions that may have actually
fired. It only keeps track of the basis markings that can be
reached and of the firing vectors relative to sequences of
unobservable transitions that have fired to reach them. Indeed,
this is the information really significant when performing
diagnosis. The notion of M(w) is fundamental to provide a
recursive way to compute the set of minimal explanations.
Under the assumption of acyclicity of the unobservable
subnet, the set M(w) can be easily constructed following
a simple algorithm in [
Definition 3.8: [
Note that if the net system is bounded then the set Mbasis is finite being the set of basis markings a subset of the reachability set.
Theorem 3.9: [
Mb ∈ Mbasis(w)}.
The above result shows that the set C(w) can be characterized in linear algebraic terms given the set Mbasis(w), thus not requiring exhaustive enumeration. This is the main advantage of the approach here presented.
Assume that the set of unobservable transitions is partitioned into two subsets, namely Tu = Tf ∪ Treg where Tf includes all fault transitions (modeling anomalous or fault behavior), while Treg includes all transitions relative to unobservable but regular events. The set Tf is further partitioned into r different subsets T i , where i = 1, . . . , r, that model the f different fault classes. Usually, fault transitions that belong to the same fault class are transitions that represent similar physical faulty behavior.
Definition 4.1: [
• ∆(w, Tfi ) = 0 if for all σ ∈ S(w) and for all tf ∈ Tfi it holds tf ̸∈ σ.
In such a case the ith fault cannot have occurred, because none of the firing sequences consistent with the observation contains fault transitions of class i.
• ∆(w, Tfi ) = 1 if: (i) there exist σ ∈ S(w) and tf ∈ Tfi such that tf ∈ σ but (ii) for all (σo, σu) ∈ Jˆ(w) and for all tf ∈ Tfi it holds that tf ̸∈ σu.
In such a case a fault transition of class i may have occurred but is not contained in any justification of w.
• ∆(w, Tfi ) = 2 if there exist (σo, σu), (σo′, σu′) ∈ Jˆ(w) such that (i) there exists tf ∈ Tfi such that tf ∈ σu; (ii) for all tf ∈ T i , tf ̸∈ σ′ .
f u
In such a case a fault transition of class i is contained in one (but not in all) justification of w.
• ∆(w, Tfi ) = 3 if for all σ ∈ S(w) there exists tf ∈ Tfi such that tf ∈ σ.
In such a case the ith fault must have occurred, because all firable sequences consistent with the observation contain at least one fault in T i .
f
Example 4.2: Consider the PN in Fig. 1 previously introduced in Example 2.2. Let Tf = {ε11, ε12}. Assume that the two fault transitions belong to different fault classes, i.e., Tf1 = {ε11} and Tf2 = {ε12}.
Let us observe w = a. Then ∆(w, Tf1) = ∆(w, Tf2) = 0, being Jˆ(w) = {(t1, ε)} and S(w) = {t1}. In simple words no fault of both fault classes may have occurred.
Let us observe w = ab. Then ∆(w, Tf1) = 1 and ∆(w, Tf2) = 0, being Jˆ(w) = {(t1t2, ε)} and S(w) = {t1t2, t1t2ε8, t1t2ε8ε9, t1t2ε8ε9ε10, t1t2ε8ε11}. This means that a fault of the first fault class may have occurred (firing the sequence t1t2ε8ε11) but it is not contained in any justification of ab, while no fault of the second fault class can have occurred.
Now, consider w = abb. In this case ∆(w, Tf1) = 2 and ∆(w, Tf2) = 0, being Jˆ(w) and = {(t1t2t2, ε8ε9ε10), (t1t2t3, ε8ε11)} S(w)={t1t2ε8ε9ε10t2, t1t2ε8ε9ε10t2ε8, t1t2ε8ε9ε10t2ε8ε9, t1t2ε8ε9ε10t2ε8ε9ε10, t1t2ε8ε9ε10t2ε8ε11, t1t2ε8ε11t3}. This means that no fault of the second fault class can have occurred, while a fault of the first fault class may have occurred since one justification does not contain ε11 and one justification contains it.
Finally, consider w = abbccc. In this case ∆(w, Tf1) = 3 and ∆(w, Tf2) = 1. In fact since Jˆ(w) = {(t1t2t3t5t4t4, ε8ε11), (t1t2t3t4t5t4, ε8ε11), (t1t2t3t4t4t5, ε8ε11), (t1t2t3t4t4t4, ε8ε11)} a fault of the first fault class must have occurred, while a fault of the second fault class may have occurred (e.g. t1t2ε8ε11t3t4t4t5ε12) but it is not contained in any justification of w.
Proposition 4.3: [
• ∆(w, Tfi ) = 2 iff there exist (M, y) ∈ M(w) and (M ′, y′) ∈ M(w) such that: (i) there exists tf ∈ Tfi such that y(tf ) > 0, (ii) for all tf ∈ T i , y′(tf ) = 0.
f • ∆(w, Tfi ) = 3 iff for all (M, y) ∈ M(w) there exists tf ∈ Tfi such that y(tf ) > 0.
In [
Remark 4.4: As proved in [
In the diagnosis framework two different problems can be
solved: the problem of diagnosis and the problem of
diagnosability. As explained in detail in the above sections, solving
a problem of diagnosis means that to each observed string
of events is associated a diagnosis state, such as “normal” or
“faulty” or “uncertain”. Solving a problem of diagnosability
is equivalent to determine if the system is diagnosable,
i.e., to determine if, once a fault has occurred, the system
can detect its occurrence in a finite number of steps. We
addressed this problem in two different settings, depending
on the boundedness of the net system. In particular, in [
Moreover, in [
To the best of our knowledge, this is the first time that necessary and sufficient conditions for diagnosability and Kdiagnosability of labeled unbounded Petri nets are presented.
In this talk an on-line approach for fault diagnosis of discrete event systems based on labeled Petri nets has been discussed. Some results on diagnosability analysis have also been recalled, that also apply to unbounded nets.
Several are the future lines of research in this framework. One of the most important is the relaxation of the assumption that the fault model is perfectly known, as well as the initial state of the system. Moreover, it is interesting to investigate how the problems of on-line fault diagnosis and diagnosability analysis can take advantage from information coming timing associated with transitions. Finally, due to the complexity of current systems, it is important to develop efficient distributed and/or decentralized approaches.