=Paper=
{{Paper
|id=Vol-1431/paper2
|storemode=property
|title=Fault Diagnosis of P-Time Labeled Petri net Systems
|pdfUrl=https://ceur-ws.org/Vol-1431/paper2.pdf
|volume=Vol-1431
|dblpUrl=https://dblp.org/rec/conf/vecos/Bonhomme15
}}
==Fault Diagnosis of P-Time Labeled Petri net Systems==
https://ceur-ws.org/Vol-1431/paper2.pdf
Fault Diagnosis of P-Time Labeled Petri Net
Systems
Patrice Bonhomme
University François-rabelais
CNRS, LI EA 6300, OC ERL CNRS 6305
64 avenue Jean Portalis
37200 Tours
France
bonhomme@univ-tours.fr
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.
Discrete event systems. Petri nets. Time labeled systems. Observability. State estimation. Fault diagnosis.
1. INTRODUCTION Thus, being given a sequence of observed events (called
word or trace) the challenge consists in determining if a
The correct behavior of a real-world application is the fault has occurred, eventually or for sure!
ultimate requirement, particularly for systems such as
communication protocols, manufacturing and real-time It can be noticed that the problems of fault diagnosis
systems. Indeed, a drift from an expected behavior can has receive extensive attention these recent years and
be of crucial importance and can even lead, in extreme particularly in the framework of automata models and
cases, to severe consequences including human losses. So, regular languages (Sampath et al. (1995), Cassandras and
knowing the current state of a system in order to take the Lafortune (2008), Lin (1994), Cassez and Tripakis (2008))
appropriate decisions and determining the malfunction of but there are few studies in the time discrete event systems
a system component are nowadays fundamental issues. context.
From a practical point of view, associating a dedicated A preliminary version of this paper was presented in
sensor to each variable of interest in order to monitor (Bonhomme (2014)) where an approach allowing to
its internal state is inconceivable. This restriction, due to estimate the marking of a P-time labeled Petri net (P-
economical or physical accessibility reasons leads to a TLPN) system based on the observation of particular
system analysis in presence of uncertainties as the state labels was presented. The plant observation is given by
information cannot be directly obtained. This particularity a set of labels whose occurrence can be detected/observed
has gave rise to the introduction of the observers paradigm by an external agent (called observer or estimator) - these
in the classical system theory. Indeed, an observer can particular labels are associated to observable transitions.
be viewed as a mechanism allowing to estimate or The other transitions, the unobservable ones (called silent
reconstruct the internal state of a system based on some transitions) are labeled with the empty string ǫ.
measurements. From a discrete event dynamic systems
point of view and more precisely from a Petri net (PN on In this extended and enriched version, a fault diagnosis
short) perspective this issue corresponds to the estimation problem is solved thanks to the introduction of a function
of a PN marking based on some event observations. called diagnoser which associates to each observation
a diagnosis state. In the proposed technique the set of
unobservable transitions is further partitioned into the
set of faulty transitions and the set of regular ones. The Note that a complete survey of fault diagnosis methods
regular transitions are unobservable and non faulty. for DES can be found in (Zaytoon and Lafortune (2013)).
In (Cabasino et al. (2010)) the authors proposed a
The proposed approach does not require the state class diagnosis approach based on the concept of basis marking
graph construction and consequently it is designed to and justificatio under the acyclicity assumption of the
alleviate the state space explosion problem. Indeed, the unobservable subnet of the system considered. Intuitively,
construction of the considered state observer is based on for an observed sequence (word) ω, a justificatio can be
the analysis of the underlying untimed PN structure of the thought as the set of minimal (in terms of firin vector)
P-time labeled PN considered. unobservable transitions interleaved with ω necessary to
complete ω into a fireabl sequence on the net considered,
In particular, the following four assumptions are made: from the initial marking. They extended their work in
(Cabasino et al. (2014)) to provide a diagnosability
1. the net structure and the initial marking are known,
approach for bounded labeled PN by introducing two
2. the fault model is known, graphs, namely the modifie basis reachability graph
(MBRG) and the basis reachability diagnoser (obtained
3. the underlying untimed PN, of the P-TLPN from the MBRG). Necessary and sufficien conditions for
considered is bounded, diagnosability are given but the construction of the two
graphs is of exponential complexity with respect to the
4. the Petri net induced by the set of unobservable
structure of the PN considered and its initial marking.
transitions does not contain circuit of null length.
There are relatively few works in this topic in the time
Note that this latter assumption is adopted to exclude
discrete event systems scheme where the time factor is
the situation where an infinit of actions may take place
modeled as intervals, so, numerous problems are still
in a finit amount of time: it prevents the net induced
open. Concerning the time Petri net model of Merlin
by the set of unobservable transitions from being Zeno
(Merlin and Faber (1976)), the authors in (Basile et al.
(Hadjidj et al. (2007)) which is in contradiction with a
(2013)) proposed a procedure for estimating the marking
diagnosability scheme. In addition, there is no assumption
of the model in presence of unobservable transitions. They
on the backward conflic freeness of the subnet induced
introduced a modifie state class graph which captures
by the set of unobservable transitions as in (Giua et al.
the required information on the possible evolution of the
(2007)).
system starting from a given initial marking. Thanks to
The paper is organized as follows: after an overview this graph, being given a timed sequence and a time
of the relevant literature in the next section, a brief instant, the set of markings consistent with the current
reminder of the basics of untimed Petri nets followed by a observation is determined via integer linear programming
formal definitio of P-time labeled Petri nets is realized techniques. The approach is restricted to bounded time
in the third section. Section four covers the procedure Petri nets.
of estimation and the construction of the state observer.
In a recent paper, the authors in (Basile et al. (2015))
The schedulability analysis of the occurrence sequence
extend the previously mentioned approach developed in
highlighted by the state observer and its application to the
(Basile et al. (2013)) to deal with the state estimation and
estimation problem are studied in the fift section. In the
the fault diagnosis problem for systems modeled by time
sixth section the fault diagnosis problem is solved. Section
PN augmented with labels.
seven presents an illustration of the developed method and
the last section concludes the paper and gives suggestions The authors in (Wang et al. (2013)), thanks to a fault
for future research. diagnosis graph (FDG) which is a truncation of the
conventional state class graph (SCG) (Berthomieu and
2. LITERATURE REVIEW Diaz (1991)), developed an online technique for the
fault diagnosis of systems modeled by unlabeled time
For discrete event system (DES) state estimation has Petri nets. The FDG is constructed incrementally with
been addressed by several researchers. For instance, in respect to the current observation and its number of states
(Giua et al. (2007)) the authors deal with the marking can be, in the worst case, the same as the one of the
estimation of a labeled Petri net system. Thanks to traditional state class graph. Indeed, the FDG is obtained
structural assumptions on the subnet induced by the set from the SCG by only keeping the information required
of unobservable transitions, they propose an algebraic for the evaluation of the fault states and the authors
characterization of the set of consistent markings once a concentrate on the sequence information and remove the
sequence is observed. irrelevant state classes (i.e., which are not used in the fault
diagnosis). Intuitively, the state classes which are obtained
In the framework of fault detection or fault diagnosis after the firin of an unobservable transition are discarded
several approaches can also be found in the literature - as the diagnosis state is updated after an observation.
fault diagnosis is closed to the state estimation problem.
The acyclicity assumption of the subnet induced by the In the proposed approach, the set of transitions is
unobservable transitions is also considered. The authors partitioned into two sets: observable transitions whose
further extend the method in (Wang et al. (2014)) by using firin can be detected by an external observer, denoted
reduction rules and model checking techniques. as To and unobservable transitions whose firin cannot be
detected, denoted as Tu with T = To ∪Tu and To ∩Tu = ∅.
3. PETRI NETS More precisely, the following stands:
3.1. Untimed Petri Nets • Tu = {t ∈ T |LM(t) = ǫ}, transitions in Tu are
The reader unfamiliar with Petri nets can refer to (Murata also called silent,
(1989)), in the following only the basic notions are • To = {t ∈ T |LM(t) 6= ǫ} (i.e., To is the set of
recalled. transitions labeled with a symbol in Ω).
A Place/Transition net (P/T net) is a structure N = In the proposed approach, the same label ζ ∈ Ω can be
(P, T, P re, P ost), where P is a set of m places; T is a set shared by several transitions, i.e., two transitions ti , tj
of n transitions. P re : P ×T → N and P ost : P ×T → N with ti 6= tj will be called indistinguishable if:
are the pre and post incidence functions that specify the
arcs; C = P ost − P re is the incidence matrix. The preset LM(ti ) = LM(tj ) = ζ.
and postset of a node X ∈ P ∪ T are denoted ◦ X and
X ◦ . A marking is a vector M : P → N that assigns to The extension of the label mapping can be realized over
each place of a P/T net a non-negative integer number of sequences, LM : T ⋆ → Ω⋆ , recursively as follows:
tokens, represented by black dots. M (p) is the marking of
place p. 1. LM(ti ) = ζ ∈ Ω if ti ∈ To ,
A net system hN ; M0 i is a net N with an initial marking 2. LM(ti ) = ǫ if ti ∈ Tu ,
M0 . A transition t is marking enabled at M if M ≥
P re(·, t). A transition t enabled at M may fire yielding 3. let σ ∈ T ⋆ and ti ∈ T then LM(σti ) =
the marking M ′ = M + C(·, t). We write M [σ > to LM(σ)LM(ti ),
denote that the sequence of transitions σ is enabled at M , 4. LM(λ) = ǫ where λ is the empty sequence.
and we write M [σ > M ′ to denote that the firin of σ
yields M ′ . A marking M is reachable in hN ; M0 i iff there 3.3. P-time Petri Nets
exists a firin sequence σ such that M0 [σ > M .
Definitio 1 The formal definitio of a P-TPN (Khansa
The set of all sequences that are enabled at the initial et al. (1996)) is given by a pair hN ; Ii where:
marking M0 is denoted L(N, M0 ) i.e., L(N, M0 ) =
{σ ∈ T ⋆ |M0 [σ >} with T ⋆ the Kleene closure of set T • N is a marked Place/Transition net (a P/T net
i.e. the set of all firin sequences of elements of T of system augmented with a marking)
arbitrary length, including the empty sequence λ. The
notation σ ′ σ will correspond to the firin sequence σ ′ • P → (Q+ ∪ {0}) × (Q+ ∪ {∞}),
followed by firin sequence σ, i.e., the concatenation • pi → I(pi ) = [ai , bi ] with 0 ≤ ai ≤ bi
operation ; σ ′ is the prefi of firin sequence σ ′ σ.
With:
The set of all markings reachable from M0 define the
reachability set of hN ; M0 i and is denoted R(N, M0 ). • P : the set of places of the net N ,
Given a net N = (P, T, P re, P ost) and a subset • Q+ : the set of positive rational numbers,
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 • Ii define the static interval of the operation
restrictions of P re and P ost to Ts . So, the net Ns is duration of a token in a place pi .
obtained from N by removing all transitions in T \ Ts ,
it is denoted also by Ns ∠Ts N . A token in place pi will be considered in the enabledness
of the output transitions of this place if it has stayed for
3.2. Labels mapping ai time units at least and bi at the most. Consequently,
the token must leave pi, at the latest, when its operation
A labels mapping LM is associated to each transition of duration becomes bi . After this duration bi , the token
the net considered as follows will be ”dead” and will no longer be considered in the
S enabledness of the transitions. According to the strong
LM : T → Ω {ǫ} , firin mode, a transition in a P-TPN, is forced to fir unless
it is disabled by the firin of another conflictin transition.
with Ω a finit alphabet and ǫ the empty string.
Let consider αi the clock associated with the token Finally, given a sequence of labels (a word) ω ∈ Ω⋆ , it
denoted i ∈ T K of the P-TPN (T K being the set of is denoted by ω k the k th element in ω and the number
tokens of the P-TPN considered). υ is a valuation of the of elements of ω is denoted by |ω|. For a ∈ Ω, we write
system, i.e., a mapping associating to each token i of a ∈ ω if there exists k ≥ 1 such that ω k = a (i.e., a is an
the P-TPN, an element of (R≥0 ), υi , representing the element of the word ω).
time elapsed since the token i has been created (i.e., the
valuation of the clock αi ). So, υ ∈ (R≥0 )T K with the Furthermore, let ω1 , ω2 , . . . , ωn be n sequences of labels
notation AX representing the set of mappings from X to (i.e., wi ∈ Ω⋆ , 1 ≤ i ≤ n), the notation ω = ω1 ω2 . . . ωn
A. 0 is the initial valuation with ∀i, 0i = 0 will be the concatenation of ω1 , ω2 , . . . , ωn .
The semantics of a P-TPN can be define as a Timed The next section recalls the procedure (Bonhomme
Transition System (TTS). A state of the TTS is a couple (2015)) to construct the state observer.
s = (M, υ) where M is a marking and υ a valuation of
the system.
4. ESTIMATION PROCEDURE
Definitio 2 The semantics of a P-TPN hN ; Ii is define The goal of the observer is to give the current state
by the Timed Transition System SN = (Q, {q0 } , Σ, −→): estimate of the system based on the information of the
observed traces. The state of the observer will consist in a
1. Q = NP × (Q≥0 )T K
set of states the model can be in after a label observation.
2. q0 = (M0 , 0)
The following set will be associated to any observed word
3. Σ = T ω (i.e., the observed labels sequence):
4. −→∈ Q × (Σ ∪ Q≥0 ) × Q • L(ω) is the set containing all sequences of
transitions that are consistent with ω, i.e., the
• The continuous transition is define ∀d ∈ R≥0 by: set of all possible firin sequences that produce
′ observation ω.
d υ = υ + d.
(M, υ) → (M, υ ′ ) iff
∀ token k in ps ⇒ υk′ ≤ bs . In general, if ω is an observed word, the associated firin
sequence σ ∈ LM−1 (ω) is not necessarily fireabl on the
• The discrete transition is define ∀ti ∈ T by:
net as some unobservable transitions should be interleaved
t to obtain a fireabl sequence that produce ω.
i
(M, υ) → (M ′ , υ ′ ) iff:
Definitio 4 Let N be a P-TLPN with T = To ∪ Tu . The
M ≥ ◦ ti . following operator is defined
∀ token k in pl , υk ≤ bl .
• The projection over To is Po : T ⋆ → To⋆ define as:
Tps ∈ ti ,∀ token k in ps involved in ti ’s firin :
◦
∀
[max(0, as − υk ), (bs − υk )] 6= ∅. – Po (λ) = λ,
k′
= M − ◦ ti + ti .
◦
M – for all σ ∈ T ⋆ and t ∈ T, Po (σt) = Po (σ)t if
0 if created by ti .
∀ token r, υr′ = t ∈ To and Po (σt) = Po (σ) otherwise (with
υr otherwise.
λ representing the empty sequence).
The dynamic evolution of a P-TPN depends on the Given a sequence σ ∈ L(N, M0 ), ω = LM(Po (σ))
timing situation of each token. Indeed, each token will denotes the corresponding observed word.
be associated with a potential firin interval (or dynamic
interval) which can be different from its static one. For Definitio 5 Let N be a P-TLPN with T = To ∪ Tu and
instance, consider place pi with static interval [ai , bi ], ω ∈ Ω⋆ be an observed word. L(ω) is define as:
let a token arrive in place pi at absolute time τ . At τ
its potential firin interval will correspond to [ai , bi ]. At L(ω) = Po−1 (LM−1 (ω)) ∩ L(N, M0 ) =
time τ + c with c ≤ bi the dynamic interval of the {σ ∈ L(N, M0 )|LM(Po (σ)) = ω},
considered token will become [max(ai − c, 0), bi − c].
It can be noticed that a token is considered as dead when i.e., the set of firin sequences consistent with ω ∈ Ω⋆ .
its dynamic interval becomes [0, 0].
Definitio 6 Let N be a P-TLPN with T = To ∪ Tu and
Definitio 3 A P-time labeled Petri net (P-TLPN on ω ∈ Ω⋆ be an observed word. C(ω) is define as:
short) over an alphabet Ω is a triple hN,
S I, LMi where C(ω) = {M ∈ R(N, M0 )|∃σ ∈ L(ω) : M0 [σ > M },
hN, Ii is a P-TPN and LM : T → Ω {ǫ} is a labeling
function. i.e., the set of markings consistent with ω.
So, being given an observed word ω, L(ω) is the set of • ςso : Yso → 2R(N,M0 ) is a function associating to
sequences that may have fire while C(ω) is the set of each state yso ∈ Yso a set of reachable markings,
markings in which the system may actually be.
• y0 is the initial state of the state observer and
t5 ςso (y0 ) = SEM (N0 ) ∪ SSM (N0 ),
[1, 3]
P1
P2 [1, 2]
a
[0, 6] t6 P4
t7 P5 • fso : Yso × Eso ⋆
→ Yso is the transition function
define as :
for yl ∈ Yso a state of the observer and
t4 t1
P3 [1, 3] [2, 4]
a string of observable labels
t2
⋆
b
ω ∈ Eso
b fnso (y0 , ω) = yl if ςso (yl ) ∈
/ ∅ where
o ςso (yl ) =
t3 τ
Ml : M0 → Ml ∧ LM(Po (τ )) = ω =
Figure 1: P-TLPN model. SEM (Nl ) ∪ SSM (Nl ).
Let consider the P-TLPN of Figure 1 with Tu = With the two sets SSM and SEM define as follows:
{t4 , t5 , t6 , t7 }, To = {t1 , t2 , t3 }, Ω = {a, b}. It holds
LM(t1 ) = a, LM(t2 ) = LM(t3 ) = b (transitions t2 Definitio 9 Sets SSM and SEM
and t3 are indistinguishable) and LM(ti ) = ǫ, ∀ti ∈ Tu .
• SEM (Nj ), the Set of Entry Markings of Nj ,
If the observed word is ω = ab then LM−1 (ω) =
{t1 t2 , t1 t3 } and L(ω) = {t4 t1 t2 , t4 t1 t6 t7 t3 } and C(ω) =
[10000]. SEM (Nj ) = {Ms ∈ Nj |∃Mu ∈ Ni , tk ∈ To ,
Definitio 7 Let N be a P-TLPN with T = To ∪ Tu , the ak ∈ Ω, LM(tk ) = ak : Mu [tk > Ms }
unobservable reachability mapping UR, which enables
to fin the markings reachable from a given marking • SSM (Nj ), the Set of Shadow Markings of Nj ,
Mi , following the firin of all unobservable sequences is
define as:
SSM (Nj ) = {Ms ∈ Nj |∃Mu ∈ SEM (Nj ),
UR : Nm → 2N ,
m
σu ∈ Tu⋆ : Mu [σu > Ms }
Mi → UR(Mi ) =
{Mj ∈ Nm |∃σu ∈ Tu⋆ , Mi [σu > Mj } , or equivalently, SSM (Nj ) = U R(SEM (Nj )).
m
with 2N the power set of the markings of the PN
considered. Intuitively, for a given node Ns of the state observer,
after the observation of the word ω, the set SEM (Ns ) ∪
4.1. State observer SSM (Ns ) represents the set of markings that are
consistent with the current observed word (i.e., C(ω)). The
Let Ni and Nj be two nodes of the graphical representa- other nodes can be computed recursively as explained in
tion of the state observer (associated respectively to the the following.
states yi and yj of the observer) such that it exists a
directed arc linking Ni to Nj (Ni → Nj , i.e., Ni is 1. The state observer starts in the initial state y0
a predecessor of Nj ) labeled with ak with ak ∈ Ω as and its associated initial node N0 is composed of
illustrated on Figure2. SEM (N0 ) = {M0 } and SSM (N0 ) = U R(M0 ).
Nj 2. as soon as a label ak (associated with an observable
transition tk ∈ To ) is observed a new state yl of the
Ni
ak
observer is calculated yielding a new node Nl :
• the set of entry markings of node Nl is
Figure 2: nodes of the state observer.
obtained by investigating the set of markings
resulting from the firin of transition tk
Definitio 8 The state observer for the partially observ- starting from any marking (SEM ∪ SSM ) of
able P-TLPN N with initial marking M0 and T = To ∪Tu N0 ,
is define by the 5-tuple (Yso , Eso , fso , y0 , ςso ) where:
• the set of shadow markings of Nl corresponds
• Yso is the set of states of the state observer, to the set of markings obtained by the firin
of all unobservable sequences of transitions
• Eso = Ω is the set of labels (associated to the starting from any entry marking of Nl ,
observable events),
3. return to 2 with the newly calculated state as the as soon as the token has been dropped in the place as seen
initial state. previously. To compute the firin instants, this approach
requires that a token is identifie by three parameters:
Definitio 10 Let Ni and Nj be two nodes of the state the place that contains it, the information of its creation
observer, Ni and Nj are said to be equivalent (Ni ⇔ Nj ) instant and of its consumption one.
if and only if:
Function T OK is define with this purpose assuming that
SEM (Ni ) = SEM (Nj ) and SSM (Ni ) = SSM (Nj ). a FIFO queuing policy in the net is used in the sequel:
Proposition 1 Two nodes Ni and Nj of the state observer T OK:N × (N \ {0}) × T ⋆ → ℘(P )),
will be equivalent if and only if, the following holds:
T OK(j, n, σ) = {p ∈ P |p contains a token created by
SEM (Ni ) = SEM (Nj ). the j th firin instant and consumed by the nth one in firin
sequence σ}.
Definitio 11 Given a marking Mi ∈ R(N, M0 ) and a
transition tf ∈ To (associated with a label lf ∈ Ω, i.e., With ℘(P ) the set of subsets of P (also noted 2P ).
LM(tf ) = lf ), the set of candidate sequences denoted
CS(Mi , tf ) is the set of firin sequences, composed of When it is clear from the context σ will be omitted in the
the unique fina observable transition tf , which can occur notation of T OK(.).
from Mi , i.e.:
When the weight of the P-TPN arcs is element of N,
CS(Mi , tf ) = {s.tf |s ∈ Tu⋆ ∪ λ, tf ∈ To : Mi [s.tf >}. T OK(j, n) is a multi-set. For the sake of simplicity,
only ordinary P-TPN are considered (the arcs weight are
With respect to the timing constraints to be satisfied element of {0, 1}).
candidate sequences can be in the state possible or
impossible. Tokens, with the same creation instant, located in different
places and involved in the same transition firin may
As Nu ∠Tu N (i.e., the Petri net induced by the set of mutually constrained their sojourn time, the following
unobservable transitions) is not Zeno by assumption, it quantities, Dsmin and Dsmax, are introduced in order
is ensured that the time is diverging with regard to the to evaluate the contribution of these tokens. So, Dsmin
length of the firin sequences, thus, the set of candidate represents their availability in order to participate to this
sequences from a marking is necessarily finit (at the firin and similarly, Dsmax expresses the fact that they
instant of observation) and it can be investigated. The all must be prevented from dying (with [ai , bi ] the static
following section addresses the schedulability analysis interval associated with the place pi ).
(Bonhomme (2013b)) of an occurrence sequence (i.e., a
max (ai ), i | pi ∈ T OK(j, n)
procedure verifying if the considered firin sequence can Dsmin(j, n) = ,
occur without any violation of timing constraints) and its else 0 if T OK(j,n) = ∅
application to the estimation problem.
min (bi ), i | pi ∈ T OK(j, n)
Dsmax(j, n) = .
else + ∞ if T OK(j,n) = ∅
5. SCHEDULABILITY ANALYSIS AND
ESTIMATION The definitio of the following set SEN (q), allowing to
Let σ = ta tb tc . . . tq be a firin sequence of length s determine the creation instants of tokens involved in the
(denoted |σ| = s). The j th fire transition of σ will q th firin instant, is also necessary:
be associated with the j th firin instant (Bonhomme
(2013a)). A variable xi will represent the elapsed time SEN (q) = {u|T OK(u, q) ⊂ ( °tq )}
between the (i − 1)th firin instant and the ith one (with
x0 = 0). To express more simply the obtained results, the definitio
of the following coefficient is required:
For instance on Figure 3, (x2 + x3 ) is the time elapsed
Dsmin(u, q) if u ∈ SEN (q)
between the firs firin instant (associated with transition cuq = ,
ta ) and the third one (transition tc ). 0 else
Dsmax(j, k) if T OK(j, k) 6= ∅
firing of ta firing of tb firing of tc firing of tq
djk =
x1 x2 x3 .........
xs +∞ else
Figure 3: Firing instants. With, ∀(j, k) ∈ [0, q − 1] × [1, q], j ∈
/ SEN (q) and k 6=
q, then cjk = 0, and ∀k ∈ [0, q], xk ≥ 0.
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 The following proposition is finall obtained:
Proposition 2 A sequence of transitions σ = t1 t2 ....tq • for each σf ∈ CS(M0 , tf ) (with Po (σf ) = tf ) the
is schedulable (i.e., it may be fi ed respectively at firin associated linear system Sσf will be constructed,
instants 1, 2, . . . , q) if and only if there exist x1 ≥ 0,
x2 ≥ 0,..., xq ≥ 0 such that: • and each σf will be checked for schedulability with
the following additional constraint:
c0k ≤ x1 ≤ d0k , k = 1, ..., n
P|σf |
i=0 xi = τf .
max (c0k , c1k + x1 ) ≤ x1 + x2 ≤ min (d0k , d1k + x1 )
k=2,...,n k=2,...,n
...
j
X q
X j
X Thanks to these considerations it is ensured that sequence
max (cjk + xs ) ≤ min (djk + xs ) σf is schedulable and the firin of tf occurs at τf . Once a
xs ≤
j=0,...,q−1
j=0,...,q−1
s=0 s=0 s=0
k=q,...,n k=q,...,n
firin sequence is proved to be possible the set of markings
the system can be in is then determined.
In the sequel this system will be denoted as Sσ (q) or
simply Sσ when it is clear from the context. Let denote by F EAS(N0 , tf ) the set of schedulable
firin sequences from node N0 ending with the unique
Definitio 12 The firin space at the q th firin instant,
observable transition tf (it is a subset of the set of
associated with a firin sequence σ, denoted by FS σ (q)
candidate sequences).
is the set of non negative vectors (x1 , ..., xq ) such that
the fi st, the second, . . . and the q th firin conditions F EAS(N0 , tf ) = {σ ∈ CS(M0 , tf )|FS σ (|σ|)
are satisfied Thus, a firin sequence σ = t1 t2 ....tq
is schedulable if and only if its associated firin space P|σ| o
augmented with x = τ is non-empty .
FS σ (q) is non-empty. i=0 i f
Thanks to this characterization of a firin sequence, the Furthermore, based on the knowledge of the schedulable
Zenoness property can be checked by evaluating the candidate firin sequences only a subset of the set of
minimal duration of the circuit of unobservable transitions entry markings of node Nf (resulting from the firin of
under consideration (for instance, by minimizing the sum transition tf ), denoted SEM ′ (Nf ), will be considered for
of the xi associated with the considered transitions). the next step.
It holds:
Definitio 13 A P-TLPN Nr firin schedule, will be a
i SEM ′ (Nf ) = {M ∈ SEM (Nf )|M0 [σ > M,
sequence of ordered pairs (ti , xk ) ; transition ti
P
k=0 σ ∈ F EAS(N0 , tf )}.
i
fi able at time ( xk ), obtained from the state reached
P
k=0 With SEM ′ (Nf ) ⊆ SEM (Nf ).
by starting from Nr initial state and firin the transitions
tj , 1 ≤ j < i, in the schedule at the given times. Afterwards, if another label ax is observed at absolute
time τx then:
Finally, as in (Basile et al. (2015)), let denote:
• The set of associated observable event Tax =
ωt = ((a1 , τ1 ), (a2 , τ2 ) . . . (an , τn )) ∈ (Ω × Q+ )⋆ , {t ∈ To |LM(t) = ax } will be evaluated,
a time-label sequence (TLS), i.e., a sequence of pairs • then, ∀tx ∈ Tax the set of feasible candidate
(observed label-time instant). sequences CS(Mi , tx ) will be computed with Mi ∈
SEM ′ (Nf ),
Indeed, in the considered sequence, label ai is observed at
absolute time τi (i ≥ 1) and τ1 ≤ τ2 . . . ≤ τn . • a switch from node Nf to node Nx is realized in the
state observer,
Now all the required material for the proposed method is • for each feasible firin sequence (on the underlying
given, the principle is presented as follows: untimed PN) σf′ σx (i.e., M0 [σf′ σx >) with
σx ∈ CS(Mi , tx ) and σf′ ∈ F EAS(N0 , tf ) the
• starting from the initial state, once a label af will be
associated linear system Sσf′ σx will be constructed.
observed at the absolute time τf ,
It is recalled that σf′ is a schedulable firin sequence
• the set of associated observable event Taf =
determined in the previous step with label af
{t ∈ To |LM(t) = af } will be evaluated,
observed at τf and Po (σf′ σx ) = tf tx .
• then, ∀tf ∈ Taf the set of feasible candidate
• each previously determined σf′ σx will be checked
sequences CS(M0 , tf ) will be computed,
for schedulability with the following additional
• a switch from node N0 to node Nf (created by constraint:
the observation of label af ) is realized in the state P|σf′ |+|σx |
observer, i=0 x i = τx .
ensuring that the firin of tx occurs at τx . can be completed by schedulable sub-sequences into
a schedulable firin sequence starting from the initial
And so on, the same method is iteratively applied with marking of the P-TLPN considered.
respect to the current observation.
So, by this way it is ensured that the feasible
So, more formally the following principle is obtained: firin sequences associated with the observed time-
let ωobs be an observed word (i.e., a sequence of labels label sequence ((a1 , τ1 ), (a2 , τ2 ) . . . (ai+1 , τi+1 )) are
ωobs = a1 a2 a3 . . . ai ai+1 . . . ∈ Ω⋆ ) and let Ni (i ≥ 1) effectively computed.
be the node of the associated state observer obtained after
the observation of label ai ∈ ωobs detected at absolute In the next section, addressing the fault diagnosis problem
time τi , as illustrated on the following figur (Figure 4). of a P-TLPN system, this set will be used to evaluate the
state diagnosis associated with an observed TLS.
N0 N1 N2 Ni
a1 a2 ai a i+1
.... ....
6. FAULT DIAGNOSIS
Figure 4: Observable sequence. The set of unobservable transitions is partitioned into two
subsets, Tu = Tf ∪ Treg where the set Tf includes all the
The associated sets F EAS and SEM ′ are computed as fault transitions (modeling anomalous or faulty behavior)
follows: while Treg includes all unobservable transitions which
correspond to regular events. Furthermore, the set Tf is
Let t1 ∈ Ta1 = {t ∈ To |LM(t) = a1 }, partitioned into r different subsets Tfi , where i = 1, . . . , r,
that models the different fault classes.
F EAS(N0 , t1 ) = {σ ∈ CS(M0 , t1 )|FS σ (|σ|) augmented
P|σ| o Definitio 14 Let hN ; M0 i be a net S system with labeling
with k=0 xk = τ1 is non-empty . function LM : T → Ω {ǫ} , 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
SEM ′ (N0 ) = SEM (N0 ) = {M0 } and
state observer of Figure 4.
SEM ′ (N1 ) = {M ∈ SEM (N1 )|M0 [σ > M,
Let define
σ ∈ F EAS(N0 , t1 )}.
(M0 , ωt ) = {σ ∈ T ⋆ |M0 [σ >, σ = σ1 σ2 . . . σn :
P
∀i > 0,
LM(σi ) = ai , i = 1, . . . , n, σs ∈ F EAS(Ns−1 , ts ),
Let LM(ti+1 ) = ai+1 ,
LM(ts ) = as , s = 1, . . . , n}
′
F EAS(Ni , ti+1 ) = {σ ∈ CS(Mb , ti+1 )|Mb ∈ SEM (Ni ),
Indeed, σ can be viewed as a concatenation of
M0 [̟ >, FS ̟ (|̟|) augmented subsequences, namely σi , i ≥ 1. Each subsequence σi is
o with
P|̟| of the form s.ti with s ∈ Tu⋆ , LM(ti ) = ai and absolute
x
k=0 k = τ i+1 is non-empty .
firin instant of ti is τi .
So, it holds:
With firin sequence ̟ = σ1 σ2 . . . σi σ where σs ∈
F EAS(Ns−1 , ts ), s ∈ {1, . . . , i} and Po (̟) = σi ∈ CS(Mb , ti ) with Mb ∈ SEM ′ (Ni−1 ).
t1 t2 t3 . . . ti ti+1 .
Definitio 15 A diagnoser is a function
More precisely:
Po (σj ) = tj , j ∈ {1, . . . , i} with LM(tj ) = aj .
Γ : [Ω × Q+ ]⋆ × Tf1 , Tf2 , . . . , Tfr → {N, U, F }
′
SEM (Ni+1 ) = {M ∈ SEM (Ni+1 )|Mk [σ > M,
σ ∈ F EAS(Ni , ti+1 ), Mk ∈ SEM (Ni )}. that associates with each observed time-label sequence ωt
and each fault class Tfi , where i = 1, . . . , r, a diagnosis
SEM ′ (Ni ) is the set of entry markings of node Ni state.
resulting from the firin of schedulable firin sequences
• Γ(ωt , Tfi ) = N if ∀σ ∈ (M0 , ωt ) and ∀tf ∈ Tfi ,
P
with respect to the current observation.
it is tf ∈
/ σ.
Roughly speaking, F EAS(Ni , tk ) is the set of candidate In such a case the ith fault cannot have occurred,
sequences of node Ni ending with tk and which because none of the firin sequences consistent
with the considered observation contains a fault It holds t7 ∈ Tf2 and t7 ∈ ω2 (t7 ∈
/ ω1 ), and t5 ∈ Tf1 ,
transition of class i. t5 ∈ / ω2 .
/ ω1 , t5 ∈
• Γ(ωt , Tfi ) = U if: So, Γ(ωt , Tf1 ) = N and Γ(ωt , Tf2 ) = U .
1. ∃σ ∈ (M0 , ωt ) and tf ∈ Tfi such that
P
It means, that according to the previous observed time
tf ∈ σ,
label sequence ωt , it is known for sure that the fault of
2. ∃σ ′ ∈ (M0 , ωt ) such that ∀tf ∈ Tfi , it is
P
class 1 (corresponding to fault transition t5 ) cannot have
tf ∈/ σ′ . occurred while fault transition t7 ∈ Tf2 may have occurred
In such a case a fault transition of class i may (via ω2 ).
have occurred or not, the diagnosis is in this case,
uncertain. If the observed TLS P corresponds to ωt = (b, 1), it is
easy to verify that (M0 , ωt ) = {ω3 } with ω3 = t5 t2
• Γ(ωt , Tfi ) = F if ∀σ ∈ (M0 , ωt ), ∃tf ∈ Tfi such (the associated firin schedule is ((t5 , 1), (t2 , 1))) and
P
that tf ∈ σ. consequently, Γ(ωt , Tf1 ) = F and Γ(ωt , Tf2 ) = N (i.e., a
In such a case the fault of class i must have fault of class Tf1 occurs for sure and a fault of the second
occurred, because all firabl sequences consistent class cannot have occurred).
with the considered observation contains at least
one fault transition of class i. In the next section an illustrative example is presented
where the Tu -induced subnet is cyclic.
Let consider the P-TLPN of Figure1 with Tu =
{t4 , t5 , t6 , t7 }, To = {t1 , t2 , t3 }, Ω = {a, b}. It holds
7. ILLUSTRATIVE EXAMPLE
LM(t1 ) = a, LM(t2 ) = LM(t3 ) = b (transitions t2
and t3 are indistinguishable). Furthermore, Tf1 = {t5 } and Let consider the P-TLPN of Figure 6 with To = {t2 , t5 },
Tf2 = {t7 }, i.e., there are two fault classes. Tu = {t1 , t3 , t4 , t6 , t7 }, Tf = {t6 } and LM(t2 ) =
a, LM(t5 ) = b. The Tu -induced subnet contains the cycle
b (p3 − t4 − p4 − t6 − p3 ).
N1
N0 a SSM
SSM SEM P1
SEM
[01000] [00010]
[00100] [1, 3]
[00100]
[10000] [00001] t1
[00010]
[00001] P2
b
[2, 8]
Figure 5: State observer. a
t2
[1, 12]
P4 [10, 15]
The corresponding state observer with two nodes is
[2, 2]
P3 t5 b
t4
depicted on Figure 5. t3 P5
t3 t7
Let consider the following observed TLS ωt = t6
((a, 2), (b, 5)) then:
Figure 6: P-TLPN with a cyclic Tu -induced subnet.
(M0 , ωt ) = {ω1 , ω2 } with ω1 = t4 t1 t2 and ω2 =
P
t4 t1 t6 t7 t3 .
The state observer is depicted on Figure 7, it consists of
We have (according to the notations of definitio 14): three nodes X0 , X1 and X2 .
• ω1 = σ1 σ2 with σ1 = t4 t1 and σ2 = t2 , X1
a
X2 b
X0
SEM SSM SEM SSM
• ω2 = σ1 σ2 with σ1 = t4 t1 and σ2 = t6 t7 t3 . SEM SSM
[01000] [01000]
a b
[10000] [01000] [00100] [00010] [00001] [00100]
The two obtained candidate sequences are feasible [00100] [00010]
with regard to the timing constraints. Indeed, the a
two associated firin schedules can be, for instance,
considered respectively for ω1 and ω2 : Figure 7: State observer of the P-TLPN of Figure 6.
• ((t4 , 1), (t1 , 2), (t2 , 5)),
If the observed word is ω = (a, b) then the set of possible
• ((t4 , 1), (t1 , 2), (t6 , 2), (t7 , 3), (t3 , 5)). associated firin sequences is of the form t1 t2 t4 (t6 t4 )⋆ t5
with the ⋆ after the subsequence (t6 t4 ) (derived from the
Kleene star operator) indicating that it is allowed to occur observer which is an automaton allowing to estimate the
from zero time to infinitel . Thanks to the time instant set of markings in which the system may be, being given
of occurrence of each label the set of feasible associated a sequence of observed labels.
firin sequences is necessarily finite
Furthermore, the considered state observer is computed
For instance if the TLS considered is: on the basis of the untimed underlying Petri net of the
P-time labeled PN considered. This particularity allows
ωt = ((a, 3), (b, 6)) then (M0 , ωt ) = {ω1 } with to avoid the combinatorial state space explosion problem
P
ω1 = t1 t2 t4 t5 . The associated firin space FS ω1 (|ω1 |) usually associated with the consideration of the time
augmented with the following constraints: factor modeled as time intervals.
• x1 +x2 = 3 (absolute firin instant of transition t2 ), Thanks to a schedulability analysis technique, the
feasibility of the candidate firin sequences associated
• x1 + x2 + x3 + x4 = 6 (absolute firin instant of
with the observed time-label sequence is evaluated via
transition t5 ),
linear programming techniques.
is non-empty.
An issue currently being investigated is the extension of
It holds: the method to test the diagnosability property of P-TLPN
systems, i.e., is the fault can be detected within a finit
ω1 = σ1 σ2 with σ1 = t1 t2 and σ2 = t4 t5 and an example number of steps after its occurrence ?
of firin schedule is:
̟ = ((t1 , 1), (t2 , 3), (t4 , 5), (t5 , 6)), REFERENCES
and it is unique with respect to the static intervals of the Basile, F., M. Cabasino, and C. Seatzu (2015, April). State
P-TLPN places. So, it is easy to see that Γ(ωt , Tf ) = N estimation and fault diagnosis of labeled time petri
and the faulty transition t6 cannot have occurred. net systems with unobservable transitions. Automatic
Control, IEEE Transactions on 60(4), 997–1009.
If the TLS considered is now: ωt = ((a, 3), P (b, 9)) then
Basile, F., M. P. Cabasino, and C. Seatzu (2013). Marking
Γ(ωt , Tf ) = U , as the computation of the set (M0 , ωt )
estimation of time Petri nets with unobservable
leads to the following possible firin schedules (with the
transitions. In IEEE Emerging Technologies and
same observable projection), one containing the faulty
Factory Automation (ETFA), pp. 1–7.
transition and the other one not:
Berthomieu, B. and M. Diaz (1991, March). Modeling
• ̟1 = ((t1 , 1), (t2 , 3), (t4 , 5), (t5 , 9)), and verificatio of time dependent systems using time
• ̟2 = ((t1 , 1), (t2 , 3), (t4 , 5), (t6 , 6), (t4 , 8), petri nets. IEEE Trans. Softw. Eng. 17(3), 259–273.
(t5 , 9)). Bonhomme, P. (2013a). Scheduling and control of real-
time systems based on a token player approach. Journal
If the TLS considered is now: ωt = ((a, 3), (a, 14)) of Discrete Event Dynamic Systems 23(2), 197–209.
then
P Γ(ωt , Tf ) = F . Indeed, the computation of the set
(M0 , ωt ) leads to the following possible firin schedule Bonhomme, P. (2013b). Towards a new schedulability
containing the faulty transition: technique of real-time systems modeled by p-time Petri
nets. International Journal of Advanced Manufacturing
• ̟2 = ((t1 , 1), (t2 , 3), (t4 , 5), (t6 , 10), (t3 , 12), Technology 67(1-4), 759–769.
(t2 , 14)). Bonhomme, P. (2014). Estimation of p-time labeled petri
nets with unobservable transitions. In Proceedings
In this case the faulty transition occurs with certainty of the 2014 IEEE Emerging Technology and Factory
thanks to the timing structure of the P-TLPN considered Automation, ETFA 2014, Barcelona, Spain, September
and the occurrence date of the observed labels. 16-19, 2014, pp. 1–8.
Bonhomme, P. (2015). Marking estimation of P-time Petri
8. CONCLUSION AND PERSPECTIVES nets with unobservable transitions. IEEE Transactions
on Systems, Man, and Cybernetics: Systems 45(3), 508–
In this paper, a new methodology allowing to analyze
518.
the fault diagnosis of systems modeled by P-time labeled
Petri nets is developed. It is based on the construction of Cabasino, M., A. Giua, and C. Seatzu (2010). Fault
a function called diagnoser which associates with each detection for discrete event systems using Petri nets
observation and each fault class a diagnosis state. This with unobservable transitions. Automatica 46(9), 1531–
diagnoser is obtained thanks to the synthesis of a state 1539.
Cabasino, M. P., A. Giua, and C. Seatzu (2014).
Diagnosability of discrete event systems using labeled
Petri nets. IEEE Transactions on Automation Science
and Engineering 11(1), 144–153.
Cassandras, C. G. and S. Lafortune (2008). Introduction
to Discrete Event Systems. Springer-Verlag New York,
Inc.
Cassez, F. and S. Tripakis (2008). Fault diagnosis with
dynamic observers. In Discrete Event Systems, 2008.
WODES 2008. 9th International Workshop on, pp. 212–
217.
Giua, A., C. Seatzu, and D. Corona (2007). Marking
estimation of Petri nets with silent transitions. IEEE
Transactions on Automatic Control 52(9), 1695–1699.
Hadjidj, R., H. Boucheneb, and D. Hadjidj (2007).
Zenoness detection and timed model checking for real
time systems. In VECoS’07, pp. 120–134.
Khansa, W., J. P. Denat, and S. Collart-Dutilleul (1996).
P-time Petri nets for manufacturing systems. In
WODES’96, Edinburgh UK, pp. 94–102.
Lin, F. (1994). Diagnosability of discrete event
systems and its applications. Discrete Event Dynamic
Systems 4(2), 197–212.
Merlin, P. and D. Faber (1976). Recoverability of
communication protocols-implications of a theoretical
study. IEEE Trans. Comm. 24(9), 381–404.
Murata, T. (1989). Petri nets, properties, analysis and
applications. Proceedings of the IEEE 77, 541–580.
Sampath, M., R. Sengupta, S. Lafortune, K. Sinnamo-
hideen, and D. Teneketzis (1995). Diagnosability of
discrete-event systems. IEEE Transactions on Auto-
matic Control 40(9), 15551575.
Wang, X., C. Mahulea, and M. Silva (2013, 07/2013).
Fault diagnosis graph of time petri nets. In ECC’13:
European Control Conference, Zurich, Switzerland.
Wang, X., C. Mahulea, and M. Silva (2014). Model
checking on fault diagnosis graph. In 12th International
Workshop on Discrete Event Systems, WODES 2014,
Cachan, France, May 14-16, 2014., pp. 434–439.
Zaytoon, J. and S. Lafortune (2013). Overview of fault
diagnosis methods for discrete event systems. Annual
Reviews in Control 37(2), 308 – 320.