This paper focuses on the fault diagnosis problem of systems modeled with P-time labeled Petri nets with partial information. Indeed, the set of transitions is partitioned into those labeled with the empty string ǫ called silent (as their firin cannot be detected) including the faulty transitions and the observable ones. The proposed approach is based on the synthesis of a function called diagnoser allowing to determine the diagnosis state of the system based on the current observation. The novelty of the developed approach resides in the fact that, although the time factor is considered as intervals, the diagnoser is computed thanks to the underlying untimed Petri net structure of the P-time labeled model considered. Furthermore, the method relies on the schedulability analysis of particular firin sequences exhibited by the analysis of the obtained diagnoser and does not require the building of the state class graph.
The correct behavior of a real-world application is the
ultimate requirement, particularly for systems such as
communication protocols, manufacturing and real-time
systems. Indeed, a drift from an expected behavior can
be of crucial importance and can even lead, in extreme
cases, to severe consequences including human losses. So,
knowing the current state of a system in order to take the
appropriate decisions and determining the malfunction of
a system component are nowadays fundamental issues.
From a practical point of view, associating a dedicated
sensor to each variable of interest in order to monitor
its internal state is inconceivable. This restriction, due to
economical or physical accessibility reasons leads to a
system analysis in presence of uncertainties as the state
information cannot be directly obtained. This particularity
has gave rise to the introduction of the observers paradigm
in the classical system theory. Indeed, an observer can
be viewed as a mechanism allowing to estimate or
reconstruct the internal state of a system based on some
measurements. From a discrete event dynamic systems
point of view and more precisely from a Petri net (PN on
short) perspective this issue corresponds to the estimation
of a PN marking based on some event observations.
Thus, being given a sequence of observed events (called
word or trace) the challenge consists in determining if a
fault has occurred, eventually or for sure!
It can be noticed that the problems of fault diagnosis
has receive extensive attention these recent years and
particularly in the framework of automata models and
regular languages (
A preliminary version of this paper was presented in
(
In particular, the following four assumptions are made:
1. the net structure and the initial marking are known,
2. the fault model is known,
3. the underlying untimed PN, of the P-TLPN
considered is bounded,
4. the Petri net induced by the set of unobservable
transitions does not contain circuit of null length.
Note that this latter assumption is adopted to exclude
the situation where an infinit of actions may take place
in a finit amount of time: it prevents the net induced
by the set of unobservable transitions from being Zeno
(
The paper is organized as follows: after an overview of the relevant literature in the next section, a brief reminder of the basics of untimed Petri nets followed by a formal definitio of P-time labeled Petri nets is realized in the third section. Section four covers the procedure of estimation and the construction of the state observer. The schedulability analysis of the occurrence sequence highlighted by the state observer and its application to the estimation problem are studied in the fift section. In the sixth section the fault diagnosis problem is solved. Section seven presents an illustration of the developed method and the last section concludes the paper and gives suggestions for future research.
For discrete event system (DES) state estimation has
been addressed by several researchers. For instance, in
(
In the framework of fault detection or fault diagnosis
several approaches can also be found in the literature
fault diagnosis is closed to the state estimation problem.
Note that a complete survey of fault diagnosis methods
for DES can be found in (
In a recent paper, the authors in (
The authors in (
The reader unfamiliar with Petri nets can refer to (
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. The preset and postset of a node X ∈ P ∪ T are denoted ◦X and X◦. A marking is a vector M : P → N that assigns to each place of a P/T net a non-negative integer number of tokens, represented by black dots. M (p) is the marking of place p.
A net system hN ; M0i is a net N with an initial marking M0. A transition t is marking enabled at M if M ≥ P re(·, t). A transition t enabled at M may fire yielding the marking M ′ = M + C(·, t). We write M [σ > to denote that the sequence of transitions σ is enabled at M , and we write M [σ > M ′ to denote that the firin of σ yields M ′. A marking M is reachable in hN ; M0i iff there exists a firin sequence σ such that M0[σ > M . 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[σ >} with T ⋆ the Kleene closure of set T i.e. the set of all firin sequences of elements of T of arbitrary length, including the empty sequence λ. The notation σ′σ will correspond to the firin sequence σ′ followed by firin sequence σ, i.e., the concatenation operation ; σ′ is the prefi of firin sequence σ′σ. The set of all markings reachable from M0 define the reachability set of hN ; M0i and is denoted R(N, M0). Given a net N = (P, T, P re, P ost) and a subset Ts ⊆ T , the Ts-induced subnet of N is the net Ns = (P, Ts, P res, P osts) where P res and P osts are the restrictions of P re and P ost to Ts. So, the net Ns is obtained from N by removing all transitions in T \ Ts, it is denoted also by Ns∠Ts N .
A labels mapping LM is associated to each transition of the net considered as follows
LM : T → Ω S {ǫ} , with Ω a finit alphabet and ǫ the empty string. In the proposed approach, the set of transitions is partitioned into two sets: observable transitions whose firin can be detected by an external observer, denoted as To and unobservable transitions whose firin cannot be detected, denoted as Tu with T = To∪Tu and To∩Tu = ∅. More precisely, the following stands: • Tu = {t ∈ T |LM(t) = ǫ}, transitions in Tu are also called silent, • To = {t ∈ T |LM(t) 6= ǫ} (i.e., To is the set of transitions labeled with a symbol in Ω).
In the proposed approach, the same label ζ ∈ Ω can be shared by several transitions, i.e., two transitions ti, tj with ti 6= tj will be called indistinguishable if:
LM(ti) = LM(tj ) = ζ.
The extension of the label mapping can be realized over sequences, LM : T ⋆ → Ω⋆, recursively as follows: 1. LM(ti) = ζ ∈ Ω if ti ∈ To, 2. LM(ti) = ǫ if ti ∈ Tu, 3. let σ ∈ T ⋆ and ti ∈ T then LM(σti) =
LM(σ)LM(ti), 4. LM(λ) = ǫ where λ is the empty sequence.
Definitio 1 The formal definitio of a P-TPN (
A token in place pi will be considered in the enabledness of the output transitions of this place if it has stayed for ai time units at least and bi at the most. Consequently, the token must leave pi, at the latest, when its operation duration becomes bi. After this duration bi, the token will be ”dead” and will no longer be considered in the enabledness of the transitions. According to the strong firin mode, a transition in a P-TPN, is forced to fir unless it is disabled by the firin of another conflictin transition. Let consider αi the clock associated with the token denoted i ∈ T K of the P-TPN (T K being the set of tokens of the P-TPN considered). υ is a valuation of the system, i.e., a mapping associating to each token i of the P-TPN, an element of (R≥0), υi, representing the time elapsed since the token i has been created (i.e., the valuation of the clock αi). So, υ ∈ (R≥0)T K with the notation AX representing the set of mappings from X to A. 0 is the initial valuation with ∀i, 0i = 0 The semantics of a P-TPN can be define as a Timed Transition System (TTS). A state of the TTS is a couple s = (M, υ) where M is a marking and υ a valuation of the system.
Definitio 2 The semantics of a P-TPN hN ; Ii is define by the Timed Transition System SN = (Q, {q0} , Σ, −→): 1. Q = NP × (Q≥0)T K 2. q0 = (M0, 0) 3. Σ = T 4. −→∈ Q × (Σ ∪ Q≥0) × Q • The continuous transition is define ∀d ∈ R≥0 by: υ′ = υ + d.
∀ token k in ps ⇒ υk′ ≤ bs. (M, υ) →d (M, υ′) iff (M, υ) →ti (M ′, υ′) iff: Finally, given a sequence of labels (a word) ω ∈ Ω⋆, it is denoted by ωk the kth element in ω and the number of elements of ω is denoted by |ω|. For a ∈ Ω, we write a ∈ ω if there exists k ≥ 1 such that ωk = a (i.e., a is an element of the word ω).
Furthermore, let ω1, ω2, . . . , ωn be n sequences of labels (i.e., wi ∈ Ω⋆, 1 ≤ i ≤ n), the notation ω = ω1ω2 . . . ωn will be the concatenation of ω1, ω2, . . . , ωn.
The next section recalls the procedure (
The goal of the observer is to give the current state estimate of the system based on the information of the observed traces. The state of the observer will consist in a set of states the model can be in after a label observation. The following set will be associated to any observed word ω (i.e., the observed labels sequence): • L(ω) is the set containing all sequences of transitions that are consistent with ω, i.e., the set of all possible firin sequences that produce observation ω.
In general, if ω is an observed word, the associated firin sequence σ ∈ LM−1(ω) is not necessarily fireabl on the net as some unobservable transitions should be interleaved to obtain a fireabl sequence that produce ω.
Definitio 4 Let N be a P-TLPN with T = To ∪ Tu. The following operator is defined • The projection over To is Po : T ⋆ → To⋆ define as: – Po(λ) = λ, – for all σ ∈ T ⋆ and t ∈ T, Po(σt) = Po(σ)t if t ∈ To and Po(σt) = Po(σ) otherwise (with λ representing the empty sequence).
Given a sequence σ ∈ L(N, M0), ω = LM(Po(σ)) denotes the corresponding observed word.
Definitio 5 Let N be a P-TLPN with T = To ∪ Tu and ω ∈ Ω⋆ be an observed word. L(ω) is define as: L(ω) = Po−1(LM−1(ω)) ∩ {σ ∈ L(N, M0)|LM(Po(σ)) = ω}, L(N, M0) = i.e., the set of firin sequences consistent with ω ∈ Ω⋆. Definitio 6 Let N be a P-TLPN with T = To ∪ Tu and ω ∈ Ω⋆ be an observed word. C(ω) is define as: C(ω) = {M ∈ R(N, M0)|∃σ ∈ L(ω) : M0[σ > M }, i.e., the set of markings consistent with ω.
• The discrete transition is define ∀ti ∈ T by: M ≥◦ ti. ∀ token k in pl, υk ≤ bl. ∀ ps ∈◦ ti,∀ token k in ps involved in ti’s firin : Tk[max(0, as − υk), (bs − υk)] 6= ∅. M ′ = M −◦ ti + ti◦. ∀ token r, υr′ = 0 if created by ti. υr otherwise.
The dynamic evolution of a P-TPN depends on the timing situation of each token. Indeed, each token will be associated with a potential firin interval (or dynamic interval) which can be different from its static one. For instance, consider place pi with static interval [ai, bi], let a token arrive in place pi at absolute time τ . At τ its potential firin interval will correspond to [ai, bi]. At time τ + c with c ≤ bi the dynamic interval of the considered token will become [max(ai − c, 0), bi − c]. It can be noticed that a token is considered as dead when its dynamic interval becomes [0, 0].
Definitio 3 A P-time labeled Petri net (P-TLPN on short) over an alphabet Ω is a triple hN, I, LMi where hN, Ii is a P-TPN and LM : T → Ω S {ǫ} is a labeling function.
So, being given an observed word ω, L(ω) is the set of sequences that may have fire while C(ω) is the set of markings in which the system may actually be.
Definitio 7 Let N be a P-TLPN with T = To ∪ Tu, the unobservable reachability mapping U R, which enables to fin the markings reachable from a given marking Mi, following the firin of all unobservable sequences is define as: U R : Nm → 2Nm , Mi → U R(Mi) {Mj ∈ Nm|∃σu ∈ Tu⋆, Mi[σu > Mj } , = with 2Nm the power set of the markings of the PN considered.
Let Ni and Nj be two nodes of the graphical representation of the state observer (associated respectively to the states yi and yj of the observer) such that it exists a directed arc linking Ni to Nj (Ni → Nj , i.e., Ni is a predecessor of Nj ) labeled with ak with ak ∈ Ω as illustrated on Figure2.
Ni ak
Nj
Definitio 8 The state observer for the partially observable P-TLPN N with initial marking M0 and T = To ∪Tu is define by the 5-tuple (Yso, Eso, fso, y0, ςso) where: • Yso is the set of states of the state observer, • Eso = Ω is the set of labels (associated to the observable events), • ςso : Yso → 2R(N,M0) is a function associating to each state yso ∈ Yso a set of reachable markings, • y0 is the initial state of the state observer and ςso(y0) = SEM (N0) ∪ SSM (N0), • fso : Yso × Es⋆o → Yso is the transition function define as : for yl ∈ Yso a state of the observer and ω ∈ Es⋆o a string of observable labels fso(y0, ω) = yl if ςso(yl) ∈/ ∅ where ςso(yl) = nMl : M0 →τ Ml ∧ LM(Po(τ )) = ωo = SEM (Nl) ∪ SSM (Nl).
With the two sets SSM and SEM define as follows:
• SEM (Nj ), the Set of Entry Markings of Nj , SEM (Nj ) = {Ms ∈ Nj |∃Mu ∈ Ni, tk ∈ To, ak ∈ Ω, LM(tk) = ak : Mu[tk > Ms} • SSM (Nj ), the Set of Shadow Markings of Nj , SSM (Nj ) = {Ms ∈ Nj |∃Mu ∈ SEM (Nj ), σu ∈ Tu⋆ : Mu[σu > Ms} or equivalently, SSM (Nj ) = U R(SEM (Nj )). Intuitively, for a given node Ns of the state observer, after the observation of the word ω, the set SEM (Ns) ∪ SSM (Ns) represents the set of markings that are consistent with the current observed word (i.e., C(ω)). The other nodes can be computed recursively as explained in the following.
1. The state observer starts in the initial state y0 and its associated initial node N0 is composed of SEM (N0) = {M0} and SSM (N0) = U R(M0). 2. as soon as a label ak (associated with an observable transition tk ∈ To) is observed a new state yl of the observer is calculated yielding a new node Nl: • the set of entry markings of node Nl is obtained by investigating the set of markings resulting from the firin of transition tk starting from any marking (SEM ∪ SSM ) of
N0, • the set of shadow markings of Nl corresponds to the set of markings obtained by the firin of all unobservable sequences of transitions starting from any entry marking of Nl, 3. return to 2 with the newly calculated state as the initial state.
Definitio 10 Let Ni and Nj be two nodes of the state observer, Ni and Nj are said to be equivalent (Ni ⇔ Nj ) if and only if: SEM (Ni) = SEM (Nj ) and SSM (Ni) = SSM (Nj ). Proposition 1 Two nodes Ni and Nj of the state observer will be equivalent if and only if, the following holds: SEM (Ni) = SEM (Nj ).
Definitio 11 Given a marking Mi ∈ R(N, M0) and a transition tf ∈ To (associated with a label lf ∈ Ω, i.e., LM(tf ) = lf ), the set of candidate sequences denoted CS(Mi, tf ) is the set of firin sequences, composed of the unique fina observable transition tf , which can occur from Mi, i.e.: CS(Mi, tf ) = {s.tf |s ∈ Tu⋆ ∪ λ, tf ∈ To : Mi[s.tf >}. With respect to the timing constraints to be satisfied candidate sequences can be in the state possible or impossible.
As Nu∠Tu N (i.e., the Petri net induced by the set of
unobservable transitions) is not Zeno by assumption, it
is ensured that the time is diverging with regard to the
length of the firin sequences, thus, the set of candidate
sequences from a marking is necessarily finit (at the
instant of observation) and it can be investigated. The
following section addresses the schedulability analysis
(
Let σ = tatbtc . . . tq be a firin sequence of length s
(denoted |σ| = s). The jth fire transition of σ will
be associated with the jth firin instant (
For instance on Figure 3, (x2 + x3) is the time elapsed between the firs firin instant (associated with transition ta) and the third one (transition tc).
firing of ta firing of tb firing of tc
firing of tq x1 x2 x3
In a P-TPN, the sojourn time (i.e., the amount of time that a token has been waiting in a place) is counted up as soon as the token has been dropped in the place as seen previously. To compute the firin instants, this approach requires that a token is identifie by three parameters: the place that contains it, the information of its creation instant and of its consumption one.
Function T OK is define with this purpose assuming that a FIFO queuing policy in the net is used in the sequel: T OK:N × (N \ {0}) × T ⋆ → ℘(P )), T OK(j, n, σ) = {p ∈ P |p contains a token created by the jth firin instant and consumed by the nth one in firin sequence σ}.
With ℘(P ) the set of subsets of P (also noted 2P ). When it is clear from the context σ will be omitted in the notation of T OK(.).
When the weight of the P-TPN arcs is element of N, T OK(j, n) is a multi-set. For the sake of simplicity, only ordinary P-TPN are considered (the arcs weight are element of {0, 1}).
Tokens, with the same creation instant, located in different places and involved in the same transition firin may mutually constrained their sojourn time, the following quantities, Dsmin and Dsmax, are introduced in order to evaluate the contribution of these tokens. So, Dsmin represents their availability in order to participate to this firin and similarly, Dsmax expresses the fact that they all must be prevented from dying (with [ai, bi] the static interval associated with the place pi).
Dsmin(j, n) = Dsmax(j, n) = emlsaex0(aifi)T, Oi K|p(ji,n∈)T=OK∅ (j, n) , emlsine (+bi)∞, iif|TpOi∈K(TjO,nK)(=j, n∅) .
The definitio of the following set SEN (q), allowing to determine the creation instants of tokens involved in the qth firin instant, is also necessary:
SEN (q) = {u|T OK(u, q) ⊂ ( °tq)} To express more simply the obtained results, the definitio of the following coefficient is required: cuq = djk = 0Dsmin(u, q) ieflsue ∈ SEN (q) , Dsmax(j, k) if T OK(j, k) 6= ∅ +∞ else With, ∀(j, k) ∈ [0, q − 1] × [1, q], j ∈/ SEN (q) and k 6= q, then cjk = 0, and ∀k ∈ [0, q], xk ≥ 0.
The following proposition is finall obtained: Proposition 2 A sequence of transitions σ = t1t2....tq is schedulable (i.e., it may be fi ed respectively at firin instants 1, 2, . . . , q) if and only if there exist x1 ≥ 0, x2 ≥ 0,..., xq ≥ 0 such that: j q c0k ≤ x1 ≤ d0k, k = 1, ..., n k=m2,a..x.,n (c0k, c1k + x1) ≤ x1 + x2 ≤ k=m2,i.n..,n (d0k, d1k + x1) . . . In the sequel this system will be denoted as Sσ(q) or simply Sσ when it is clear from the context.
Definitio 12 The firin space at the qth firin instant, associated with a firin sequence σ, denoted by F Sσ(q) is the set of non negative vectors (x1, ..., xq) such that the fi st, the second, . . . and the qth firin conditions are satisfied Thus, a firin sequence σ = t1t2....tq is schedulable if and only if its associated firin space F Sσ(q) is non-empty.
Thanks to this characterization of a firin sequence, the
Zenoness property can be checked by evaluating the
minimal duration of the circuit of unobservable transitions
under consideration (for instance, by minimizing the sum
of the xi associated with the considered transitions).
Definitio 13 A P-TLPN Nr firin schedule, will be a
i
sequence of ordered pairs (ti, P xk) ; transition ti
k=0
i
fi able at time ( P xk), obtained from the state reached
k=0
by starting from Nr initial state and firin the transitions
tj , 1 ≤ j < i, in the schedule at the given times.
Finally, as in (
Indeed, in the considered sequence, label ai is observed at absolute time τi (i ≥ 1) and τ1 ≤ τ2 . . . ≤ τn.
Now all the required material for the proposed method is given, the principle is presented as follows: • starting from the initial state, once a label af will be observed at the absolute time τf , • the set of associated observable event Taf {t ∈ To|LM(t) = af } will be evaluated, = • then, ∀tf ∈ Taf the set of feasible candidate sequences CS(M0, tf ) will be computed, • a switch from node N0 to node Nf (created by the observation of label af ) is realized in the state observer, • for each σf ∈ CS(M0, tf ) (with Po(σf ) = tf ) the associated linear system Sσf will be constructed, • and each σf will be checked for schedulability with the following additional constraint:
P|iσ=f0| xi = τf .
Thanks to these considerations it is ensured that sequence σf is schedulable and the firin of tf occurs at τf . Once a firin sequence is proved to be possible the set of markings the system can be in is then determined.
Let denote by F EAS(N0, tf ) the set of schedulable firin sequences from node N0 ending with the unique observable transition tf (it is a subset of the set of candidate sequences).
F EAS(N0, tf ) = {σ ∈ CS(M0, tf )|F Sσ(|σ|) augmented with P|iσ=|0 xi = τf is non-emptyo. Furthermore, based on the knowledge of the schedulable candidate firin sequences only a subset of the set of entry markings of node Nf (resulting from the firin of transition tf ), denoted SEM ′(Nf ), will be considered for the next step.
It holds: SEM ′(Nf ) = {M ∈ SEM (Nf )|M0[σ > M, σ ∈ F EAS(N0, tf )}.
With SEM ′(Nf ) ⊆ SEM (Nf ).
Afterwards, if another label ax is observed at absolute time τx then: • The set of associated observable event Tax = {t ∈ To|LM(t) = ax} will be evaluated, • then, ∀tx ∈ Tax the set of feasible candidate sequences CS(Mi, tx) will be computed with Mi ∈ SEM ′(Nf ), • a switch from node Nf to node Nx is realized in the state observer, • for each feasible firin sequence (on the underlying untimed PN) σf′ σx (i.e., M0[σf′ σx >) with σx ∈ CS(Mi, tx) and σf′ ∈ F EAS(N0, tf ) the associated linear system Sσf′ σx will be constructed.
determined in the previous step with label af observed at τf and Po(σf′ σx) = tf tx. • each previously determined σf′ σx will be checked for schedulability with the following additional constraint:
P|iσ=f′0|+|σx| xi = τx. ensuring that the firin of tx occurs at τx.
And so on, the same method is iteratively applied with respect to the current observation.
So, more formally the following principle is obtained: let ωobs be an observed word (i.e., a sequence of labels ωobs = a1a2a3 . . . aiai+1 . . . ∈ Ω⋆) and let Ni (i ≥ 1) be the node of the associated state observer obtained after the observation of label ai ∈ ωobs detected at absolute time τi, as illustrated on the following figur (Figure 4).
N0
N1
N2 a1 a2
Ni .... ai
P|k̟=|0 xk = τi+1 is non-emptyo.
With firin sequence ̟ F EAS(Ns−1, ts), s ∈ t1t2t3 . . . titi+1.
More precisely: = σ1σ2 . . . σiσ where σs ∈
{1, . . . , i} and Po(̟) = Po(σj ) = tj , j ∈ {1, . . . , i} with LM(tj ) = aj . SEM ′(Ni+1) = {M ∈ SEM (Ni+1)|Mk[σ > M, σ ∈ F EAS(Ni, ti+1), Mk ∈ SEM (Ni)}.
resulting from the firin of schedulable firin sequences with respect to the current observation.
Roughly speaking, F EAS(Ni, tk) is the set of candidate sequences of node Ni ending with tk and which can be completed by schedulable sub-sequences into a schedulable firin sequence starting from the initial marking of the P-TLPN considered.
So, by this way it is ensured that the feasible firin sequences associated with the observed timelabel sequence ((a1, τ1), (a2, τ2) . . . (ai+1, τi+1)) are effectively computed.
In the next section, addressing the fault diagnosis problem of a P-TLPN system, this set will be used to evaluate the state diagnosis associated with an observed TLS.
The set of unobservable transitions is partitioned into two subsets, Tu = Tf ∪ Treg where the set Tf includes all the fault transitions (modeling anomalous or faulty behavior) while Treg includes all unobservable transitions which correspond to regular events. Furthermore, the set Tf is partitioned into r different subsets Tfi , where i = 1, . . . , r, that models the different fault classes.
Definitio 14 Let hN ; M0i be a net system with labeling function LM : T → Ω S {ǫ} , where N = (P, T, P re, P ost) and T = To ∪ Tu. Let consider the TLS ωt = ((a1, τ1), (a2, τ2) . . . (an, τn)) associated with the state observer of Figure 4.
Let define P(M0, ωt) = {σ ∈ T ⋆|M0[σ >, σ = σ1σ2 . . . σn : LM(σi) = ai, i = 1, . . . , n, σs ∈ F EAS(Ns−1, ts), LM(ts) = as, s = 1, . . . , n} Indeed, σ can be viewed as a concatenation of subsequences, namely σi, i ≥ 1. Each subsequence σi is of the form s.ti with s ∈ Tu⋆, LM(ti) = ai and absolute firin instant of ti is τi.
So, it holds: σi ∈ CS(Mb, ti) with Mb ∈ SEM ′(Ni−1).
Definitio 15 A diagnoser is a function Γ : [Ω × Q+]⋆ × Tf1, Tf2, . . . , Tfr → {N, U, F } that associates with each observed time-label sequence ωt and each fault class Tfi , where i = 1, . . . , r, a diagnosis state.
• Γ(ωt, Tfi ) = N if ∀σ ∈ P(M0, ωt) and ∀tf ∈ T i , f it is tf ∈/ σ.
In such a case the ith fault cannot have occurred, because none of the firin sequences consistent with the considered observation contains a fault transition of class i. • Γ(ωt, Tfi ) = U if: 1. ∃σ ∈ tf ∈ σ,
2. ∃σ′ ∈ P(M0, ωt) such that ∀tf ∈ Tfi , it is tf ∈/ σ′.
In such a case a fault transition of class i may have occurred or not, the diagnosis is in this case, uncertain. • Γ(ωt, Tfi ) = F if ∀σ ∈ P(M0, ωt), ∃tf ∈ Tfi such that tf ∈ σ.
In such a case the fault of class i must have occurred, because all firabl sequences consistent with the considered observation contains at least one fault transition of class i.
Let consider the P-TLPN of Figure1 with Tu = {t4, t5, t6, t7}, To = {t1, t2, t3}, Ω = {a, b}. It holds LM(t1) = a, LM(t2) = LM(t3) = b (transitions t2 and t3 are indistinguishable). Furthermore, Tf1 = {t5} and Tf2 = {t7}, i.e., there are two fault classes.
N0
SEM [10000]
b P(M0, ωt) = {ω1, ω2} with ω1 = t4t1t2 and ω2 = t4t1t6t7t3.
We have (according to the notations of definitio 14): • ω1 = σ1σ2 with σ1 = t4t1 and σ2 = t2, • ω2 = σ1σ2 with σ1 = t4t1 and σ2 = t6t7t3. The two obtained candidate sequences are feasible with regard to the timing constraints. Indeed, the two associated firin schedules can be, for instance, considered respectively for ω1 and ω2: • ((t4, 1), (t1, 2), (t2, 5)), • ((t4, 1), (t1, 2), (t6, 2), (t7, 3), (t3, 5)).
It holds t7 ∈ Tf2 and t7 ∈ ω2 (t7 ∈/ ω1), and t5 ∈ T 1, f t5 ∈/ ω1, t5 ∈/ ω2.
So, Γ(ωt, Tf1) = N and Γ(ωt, Tf2) = U .
It means, that according to the previous observed time label sequence ωt, it is known for sure that the fault of class 1 (corresponding to fault transition t5) cannot have occurred while fault transition t7 ∈ Tf2 may have occurred (via ω2).
If the observed TLS corresponds to ωt = (b, 1), it is easy to verify that P(M0, ωt) = {ω3} with ω3 = t5t2 (the associated firin schedule is ((t5, 1), (t2, 1))) and consequently, Γ(ωt, Tf1) = F and Γ(ωt, Tf2) = N (i.e., a fault of class Tf1 occurs for sure and a fault of the second class cannot have occurred).
In the next section an illustrative example is presented where the Tu-induced subnet is cyclic.
Let consider the P-TLPN of Figure 6 with To = {t2, t5}, Tu = {t1, t3, t4, t6, t7}, Tf = {t6} and LM(t2) = a, LM(t5) = b. The Tu-induced subnet contains the cycle (p3 − t4 − p4 − t6 − p3). The state observer is depicted on Figure 7, it consists of three nodes X0, X1 and X2. If the observed word is ω = (a, b) then the set of possible associated firin sequences is of the form t1t2t4(t6t4)⋆t5 with the ⋆ after the subsequence (t6t4) (derived from the t4 Kleene star operator) indicating that it is allowed to occur from zero time to infinitel . Thanks to the time instant of occurrence of each label the set of feasible associated firin sequences is necessarily finite For instance if the TLS considered is: ωt = ((a, 3), (b, 6)) then P(M0, ωt) = {ω1} with ω1 = t1t2t4t5. The associated firin space F Sω1 (|ω1|) augmented with the following constraints: • x1 +x2 = 3 (absolute firin instant of transition t2), • x1 + x2 + x3 + x4 = 6 (absolute firin instant of transition t5), is non-empty.
It holds: ω1 = σ1σ2 with σ1 = t1t2 and σ2 = t4t5 and an example of firin schedule is: ̟ = ((t1, 1), (t2, 3), (t4, 5), (t5, 6)), and it is unique with respect to the static intervals of the P-TLPN places. So, it is easy to see that Γ(ωt, Tf ) = N and the faulty transition t6 cannot have occurred. If the TLS considered is now: ωt = ((a, 3), (b, 9)) then Γ(ωt, Tf ) = U , as the computation of the set P(M0, ωt) leads to the following possible firin schedules (with the same observable projection), one containing the faulty transition and the other one not: • ̟1 = ((t1, 1), (t2, 3), (t4, 5), (t5, 9)), • ̟2 = ((t1, 1), (t2, 3), (t4, 5), (t6, 6), (t4, 8), (t5, 9)).
(t2, 14)).
If the TLS considered is now: ωt = ((a, 3), (a, 14)) then Γ(ωt, Tf ) = F . Indeed, the computation of the set P(M0, ωt) leads to the following possible firin schedule containing the faulty transition:
• ̟2 = ((t1, 1), (t2, 3), (t4, 5), (t6, 10), (t3, 12), In this case the faulty transition occurs with certainty thanks to the timing structure of the P-TLPN considered and the occurrence date of the observed labels.
In this paper, a new methodology allowing to analyze the fault diagnosis of systems modeled by P-time labeled Petri nets is developed. It is based on the construction of a function called diagnoser which associates with each observation and each fault class a diagnosis state. This diagnoser is obtained thanks to the synthesis of a state observer which is an automaton allowing to estimate the set of markings in which the system may be, being given a sequence of observed labels.
Furthermore, the considered state observer is computed on the basis of the untimed underlying Petri net of the P-time labeled PN considered. This particularity allows to avoid the combinatorial state space explosion problem usually associated with the consideration of the time factor modeled as time intervals.
Thanks to a schedulability analysis technique, the feasibility of the candidate firin sequences associated with the observed time-label sequence is evaluated via linear programming techniques.
An issue currently being investigated is the extension of the method to test the diagnosability property of P-TLPN systems, i.e., is the fault can be detected within a finit number of steps after its occurrence ?