# Fault Diagnosis for Discrete Event Systems Using Partially Observed Petri Nets

Authors: Ye Dandan; Luo Jiliang; Su Hongye
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This study proposes a fault diagnosis method of discrete event systems on the basis of a Petri net model with partially observable transitions. Assume that the structure of the Petri net model and the initial marking are known, and the faults can be modeled by its unobservable transitions. One of the contributions of this work is the use of the structure information of Petri net to construct an online fault diagnoser which can describe the system behavior of normal or potential faults. By modeling the flow of tokens in particular places that contain fault information, the variation of tokens in these places may be calculated. The outputs and inputs of these places are determined to be enabled or not through analyzing some special structures. With the structure information, traversing all the states is not required. Furthermore, the computational complexity of the polynomial allows the model to meet real-time requirements. Another contribution of this work is to simplify the subnet model ahead of conducting the diagnostic process with the use of reduction rules. By removing some nodes that do not contain the necessary diagnostic information, the memory cost can be reduced.


---

## Body

## 1. Introduction

Fault diagnosis is a critical issue in most industrial systems when preserving the safety of equipment and human operators. This issue has been studied in numerous studies that concern discrete event systems [1–6]. Once a fault has been detected and identified, the control law needs to be modified to safely advance the operations.A discrete event system (DES) is a dynamic system which is driven by events. When a signal of a sensor or a movement of an executive device in the system is detected, the state of DES can be transformed automatically. Nowadays, DESs exist in so many intelligent systems including robot system, manufacturing system, and transportation system.In some previous literature, the fault diagnosis of DESs is discussed by several approaches based on models [7–10], such as automata models, which usually lead to constructing a diagnoser automaton. Moreover, the diagnoser can be applied to analyze some diagnosable properties of systems, i.e., to check whether detecting the occurrences of unobservable events associated with faults is possible by observing words with finite lengths.Although automata models are suitable for describing DESs, the size of the system would limit their application. The models explicitly determine all possible states and thus would result in some quite large models when the size of the systems grows. To avoid enumerating system states and the consequent enlargement of states, Petri nets are exploited to address fault diagnosis given their merits of graphical structure. Most of the recent studies on fault diagnosis are based on the analysis of Petri net reachability graph [11–14], the direct properties of Petri nets [15, 16], and structural analysis of Petri nets [17, 18].Given that the approach proposed in the present work is based on Petri nets, the past related studies are briefly recalled. Giua and Seatzu [19] presented a diagnostic approach to avoid the exhaustive enumeration of DES states and introduced basis marking and justifications, in which the markings consistent with actual observations are characterized and the set of unobservable transitions that enables the characterizations are established. Cabasino et al. [20] developed similar approaches, such as the modified basis reachability graph and the basis reachability diagnoser, to compress the construction of a state space of bounded Petri nets. Basile et al. [21] forwarded an approach for checking K-diagnosability with the use of the technique of the integer linear programming. Liu et al. [22] proposed a technique called an on-the-fly incremental diagnostic. It can be applied to analyze both the diagnosability and K-diagnosability of bounded and also live Petri nets. Ben et al. [23] used T-invariants to define the priorities of branch investigation and rapidly determine the existence of an indeterminate cycle. Hadjicostis and Verghese [24] introduced system redundancy to detect and then isolate the fault markings. Prock [25] proposed an online technique for fault diagnosis. It can monitor the number of tokens within the P-invariants. If the total number of tokens within P-invariants is changed, then the error can be detected. Ru et al. [26] presented a method to address DESs by conducting the partial observation of states and events on the basis of the transformation of partially observed Petri nets into labeled Petri nets. Dotoli et al. [12] presented an algorithm based on the definition and solution of integer linear programming problems. The algorithm was used to characterize the fault-behavior properties needed by the system to reduce online computational effort. Fabre et al. [27] proposed a net-unfolding approach to design an online asynchronous diagnoser that can avoid state explosion. However, the online computational effort of the proposed approach is high because of the online construction of the Petri net structure by means of the unfolding.It is easy to figure out that most of the previous methods cannot avoid the state explosion problem. The computational complexities of the proposed algorithms are exponential, and they are not suitable for online use with large intelligent systems.For avoiding the state explosion problem, an online fault diagnosis strategy is proposed in this paper on the basis of the structure information of partially observed Petri nets. A number of reduction rules are adopted to simplify the construction of special structures without having to change the diagnosability property of the system. More precisely, assuming that the structure of the Petri net model and the initial marking are known, the faults can be modeled by their unobservable transitions. Furthermore, any additional unobservable transition may be associated with system legal behavior. Then, an algorithm decides whether the system behavior is normal or has potential faults when observed sequences occur, and special paths are defined to depict the structure information of Petri nets. Furthermore, subnets that contain fault information are constructed to describe the flow situation of the tokens. Based on these tokens, some of the inputs or outputs of particular places, which are the inputs or outputs of fault transitions, are considered for enabling. Finally, the fault diagnoser determines the inherent fault behavior.The main advantages of the present work are as follows. Compared with the work of Fabre et al. [27], our algorithm does not require offline calculations using the structure information of Petri nets. Our method is also more likely applicable than that of Fabre et al. [27] for minimizing memory cost with the reduction rules. The diagnostic algorithm in this paper is with great advantage for avoiding the state explosion especially when looking for a reasonably efficient method for online use with large intelligent systems.The remainder of the paper is structured as follows. Section2 provides the basic definitions and notations. Section 3 presents the special structures used to describe the inherent fault information and the reduction rules applied to simplify the model. Section 3.5 specifies the algorithm for online fault diagnosis and proposes the fault diagnoser. Section 4 gives an example of an intelligent warehouse center to verify the algorithm. Section 5 draws the conclusions.


## 2. Preliminaries

This section introduces the basic characteristics of Petri nets. For the detailed discussion on Petri nets, refer to [28].


### 2.1. Basic Petri Net Notations

Definition 1.
A Petri net is a structure that can be described asN=P,T,Pre,Post, where(i)
P is the finite set of places(ii)
T is the finite set of transitions, and P∩T = ∅(iii)
Pre: P×T⟶ℕ is the pre-incidence function, where ℕ is the set of natural numbers(iv)
Post: T×P⟶ℕ is the post-incidence function, where ℕ is the set of natural numbers
The symbol•p•t is used for the pre-set of place p∈P (transition t∈T) and p••t is used for the post-set of place p∈P (transition t∈T), respectively; e.g., t• = p∈PPrep,t≠0.
The markingM of Petri net N is represented by P-vector, in which in each place p of P, a nonnegative number of tokens M : P⟶ℕ are assigned. Then, Mp is the number of tokens present in p with the marking M.
A Petri net system is a pairN,M0 where N is a connected graph with at least one place and one transition, while M0 is an initial marking of N. RN,M0 denotes the set of reachable markings of the net system N,M0.
Given the Petri netN and marking M, if and only if ∀p∈•t and Mp≥Prep,t, then we can say the transition t∈T is enabled in M. It is denoted as Mt. A transition t that is enabled may be fired to derive the marking M′=M+C·,t, where C = Post – Pre, and it is denoted as MtM′.
A firing sequence fromM is a sequence of transitions σ=t1t2⋯tk, such that Mt1M1t2M2⋯tkMk, which is denoted as MσMk. T∗ is a set of all sequences in a Petri net. An enabled sequence σ is denoted as Mσ, while ti∈σ implies that transition ti belongs to sequence σ. If and only if there exists a sequence σ and it satisfies M0σM′, then we can say the marking M′ is reachable from the initial marking M0.
SetT can be partitioned into disjointed sets of observable transitions (represented by filled sticks) and unobservable transitions (represented by empty sticks) referred to as To and Tuo, respectively. An observed sequence is ω=t1t2⋯tk, where t1,t2,…,tk∈To. In this paper, the fault events tf∈Tf are supposed to be unobservable, i.e., Tf⊆Tuo.Definition 2 (see.
[26]). A partially observed Petri net G is a 3-tuple N,Po,To, where(i)
N is a Petri net with n places and m transitions(ii)
Po is the set of observable places with Po⊂P(iii)
To is the set of observable transitions with To⊂T
In this paper, we assume the setPo=∅, which means all the places are unobserved.


### 2.2. Subnets and Projections

In this part we present the definitions of subnets and projections.Definition 3 (see.
[29]). Given a Petri net N=P,T,Pre,Post, N′=P′,T′,Pre′,Post′ is a T′-induced subnet on N, where T′⊆T, P′=•T′∪T′•, and Pre′ and Post′ are the restrictions of Pre and Post to P′ and T′, respectively.Definition 4 (see .
[30]). Given a Petri net N, a path is an oriented sequence which is alternately comprised of the nodes of the Petri net N, denoted as π.
Consider a subnetN′ and a path π in a Petri net. π is outside of N′ if and only if all nodes of π do not belong to N′, denoted as π≠≪N′.Definition 5.
Given a set of transitionsR and a sequence σ in a Petri net, ρσ,R is the projection of transitions in σ on R.Example 1.
Ifσ=t1t2ε3t4ε5t6, where t1t2t4t6 are observable and ε3ε5 are unobservable, and set R=To, then ρσ,R=t1t2t4t6.


### 2.3. Basic Assumptions

In this part, some assumptions exploited in this study are presented in advance.Assumption 1.
No cycle of unobservable transitions exists.Assumption 2.
The Petri netN that models the DES and the initial marking m0 are known.Assumption 3.
Once a fault occurs, the system would remain to be faulty infinitely. Then, we call these faults permanent.
Assumption1 is commonly adopted in the field of fault diagnosis of Petri net models, whereas Assumptions 2 and 3 correspond to levels of system knowledge.


## 2.1. Basic Petri Net Notations

Definition 1.
A Petri net is a structure that can be described asN=P,T,Pre,Post, where(i)
P is the finite set of places(ii)
T is the finite set of transitions, and P∩T = ∅(iii)
Pre: P×T⟶ℕ is the pre-incidence function, where ℕ is the set of natural numbers(iv)
Post: T×P⟶ℕ is the post-incidence function, where ℕ is the set of natural numbers
The symbol•p•t is used for the pre-set of place p∈P (transition t∈T) and p••t is used for the post-set of place p∈P (transition t∈T), respectively; e.g., t• = p∈PPrep,t≠0.
The markingM of Petri net N is represented by P-vector, in which in each place p of P, a nonnegative number of tokens M : P⟶ℕ are assigned. Then, Mp is the number of tokens present in p with the marking M.
A Petri net system is a pairN,M0 where N is a connected graph with at least one place and one transition, while M0 is an initial marking of N. RN,M0 denotes the set of reachable markings of the net system N,M0.
Given the Petri netN and marking M, if and only if ∀p∈•t and Mp≥Prep,t, then we can say the transition t∈T is enabled in M. It is denoted as Mt. A transition t that is enabled may be fired to derive the marking M′=M+C·,t, where C = Post – Pre, and it is denoted as MtM′.
A firing sequence fromM is a sequence of transitions σ=t1t2⋯tk, such that Mt1M1t2M2⋯tkMk, which is denoted as MσMk. T∗ is a set of all sequences in a Petri net. An enabled sequence σ is denoted as Mσ, while ti∈σ implies that transition ti belongs to sequence σ. If and only if there exists a sequence σ and it satisfies M0σM′, then we can say the marking M′ is reachable from the initial marking M0.
SetT can be partitioned into disjointed sets of observable transitions (represented by filled sticks) and unobservable transitions (represented by empty sticks) referred to as To and Tuo, respectively. An observed sequence is ω=t1t2⋯tk, where t1,t2,…,tk∈To. In this paper, the fault events tf∈Tf are supposed to be unobservable, i.e., Tf⊆Tuo.Definition 2 (see.
[26]). A partially observed Petri net G is a 3-tuple N,Po,To, where(i)
N is a Petri net with n places and m transitions(ii)
Po is the set of observable places with Po⊂P(iii)
To is the set of observable transitions with To⊂T
In this paper, we assume the setPo=∅, which means all the places are unobserved.


## 2.2. Subnets and Projections

In this part we present the definitions of subnets and projections.Definition 3 (see.
[29]). Given a Petri net N=P,T,Pre,Post, N′=P′,T′,Pre′,Post′ is a T′-induced subnet on N, where T′⊆T, P′=•T′∪T′•, and Pre′ and Post′ are the restrictions of Pre and Post to P′ and T′, respectively.Definition 4 (see .
[30]). Given a Petri net N, a path is an oriented sequence which is alternately comprised of the nodes of the Petri net N, denoted as π.
Consider a subnetN′ and a path π in a Petri net. π is outside of N′ if and only if all nodes of π do not belong to N′, denoted as π≠≪N′.Definition 5.
Given a set of transitionsR and a sequence σ in a Petri net, ρσ,R is the projection of transitions in σ on R.Example 1.
Ifσ=t1t2ε3t4ε5t6, where t1t2t4t6 are observable and ε3ε5 are unobservable, and set R=To, then ρσ,R=t1t2t4t6.


## 2.3. Basic Assumptions

In this part, some assumptions exploited in this study are presented in advance.Assumption 1.
No cycle of unobservable transitions exists.Assumption 2.
The Petri netN that models the DES and the initial marking m0 are known.Assumption 3.
Once a fault occurs, the system would remain to be faulty infinitely. Then, we call these faults permanent.
Assumption1 is commonly adopted in the field of fault diagnosis of Petri net models, whereas Assumptions 2 and 3 correspond to levels of system knowledge.


## 3. Special Structures and Reduction Rules

In this section, we focus on some special structures of Petri net and its reduction rules.


### 3.1. Special Structures

Definition 6.
Given a placep and a path in a Petri net model, this path is defined as an observable path of this place p, denoted as πp, if it satisfies the following:(i)
Its beginning node (or end node) is placep and its end node (or beginning node) is an observable transition(ii)
The rest of its transitions are unobservableDefinition 7.
Given a placep in a Petri net N, if πp exists, an observed subnet of place p is denoted as SNp which is only comprised of all πp.
Consider a partially observed Petri netN and a place p. Assume that the number of nodes in N is m+n and the number of nodes in SNp is r. Obviously r≤m+n and the computational complexity of constructing SNp is polynomial.Definition 8.
Given a placep in a Petri net N, a SNp is defined as a diagnosable subnet of place p, denoted as DSNp, if it satisfies the following:(i)
Any places insideSNp cannot be connected to any transitions outside SNp(ii)
Any unobservable transitions insideSNp cannot be the inputs of any places outside SNpExample 2.
The yellow pathp4ε3p3t2 is an observable path of place p1, namely, πp1, as shown in Figure 1.Figure 1
A partially observed Petri net.Example 3.
Figure2 is an observed subnet of place p4, namely, SNp4. It is also a DSNp4.
For a fault transitiontf, its inputs and outputs are •tf and tf•. If a place p∈•tf (or p∈tf•), then we use p⟶f (or p←f) for brief writing.Figure 2
An observed subnet of placep4.Definition 9.
Given a fault transitiontf, a path πp←f is called a fault observable path of p←f, if it satisfies the following:(i)
The beginning node ofπp←f is p←f(ii)
πp←f contains tfDefinition 10.
Given a fault transitiontf, a path πp⟶f is called a fault observable path of p⟶f, if it satisfies the following:(i)
The beginning node ofπp⟶f is p⟶f(ii)
πp⟶f contains tfDefinition 11.
Given aDSNp←f in a Petri net N, FDSNp←f is called a fault-diagnosable subnet of place p←f, if it satisfies the following:(i)
FDSNp←f is a part of DSNp←f(ii)
πp←f does not belong to FDSNp←fDefinition 12.
Given aDSNp←f in a Petri net N, FDSNp←f is called a fault-diagnosable subnet of place p⟶f, if it satisfies the following:(i)
FDSNp←f is a part of DSNp←f(ii)
πp⟶f does not belong to FDSNp←fExample 4.
Placep4 is the output of fault f1 and Figure 3 is a fault-diagnosable subnet FDSNp4.Figure 3
A fault-diagnosable subnet ofp4.


### 3.2. Reduction Rules

The basic structures of Petri nets are and-joint, and-split, or-joint, or-split, loop, and sequence, as shown in Figure4. Some reduction rules based on these structures were already proposed in [31, 32]. However, in the rule (i) in [31, 32], the authors did not consider the inherent fault information on the unobservable transition, and the rules (ii) and (iii) are not mentioned.Figure 4
Six structures of Petri net.However, not all rules can preserve the diagnosability property. To overcome this limitation, a few other simple rules are proposed as shown in Figure5.Figure 5
Reduction rules applied to Petri net.


#### 3.2.1. Fusion of Places in Vertical (Figure5(a))

If there exists a transition between two places that is normal and unobservable, and it has one input and output, then this transition can be omitted and two places can be merged into a new place for reducing the number of nodes in the net. The marking of the new place is the sum of the markings of two previous places.


#### 3.2.2. Fusion of Transitions in Parallel (Figure5(b))

If there are several transitions with the same one input and output, and they are all normal and unobservable, then these transitions can be merged into one transition that is normal and unobservable. The new initial marking stays the same.


#### 3.2.3. Fusion of Places in Parallel (Figure5(c))

If there are several places with the same one input and output, then these places can be merged into one place. The marking of this place is the minimal of the several ones.Example 5.
As shown in Figure3, FDSNp4 and f2 are a fault transition that contains fault information. By using reduction rule i), places p7 and p2 are merged and transition ε3 can be suppressed. Thus, transition f2 cannot be reduced because it contains fault information. The reduced model is shown in Figure 6.Figure 6
The reduced Petri net model.Theorem 1.
With the use of the above reduction rules, the diagnosability of the reduced Petri net is consistent with that of the initial version.Proof.
If the initial Petri net is not diagnosable, then the two sequences ofσ1 and σ2 exist with the same observation. Furthermore, faults exist in σ2 but not in σ1. After the fault occurs, σ2 can be arbitrarily long. Let a regular and also unobservable transition ε be contained in σ1σ2, and this transition ε can be removed with the use of some previous reduction rules. The observation of this reduced sequence σ1∗σ2∗ is retained even removing the transition ε. Therefore, the system is still not diagnosable.
If the initial Petri net is diagnosable, then no two sequences ofσ1 and σ2 exist with the same observation. Furthermore, faults exist in σ2 but not in σ1. After the fault occurs, σ2 can be arbitrarily long. Let a regular and also unobservable transition ε be contained in σ1σ2, and this transition ε can be removed with the use of some previous reduction rules. The observation of this reduced sequence σ1∗σ2∗ is retained (i.e., not observable). Therefore, the system is still diagnosable.


### 3.3. Level Functions

Definition 13.
Given two transitionst1 and t2 in a Petri net system, if •t1=t2•, transition t1 is called the up-transition of t2, and transition t2 is called the down-transition of t1.Definition 14.
Given a pathπp, if its end node is place p, this path is called the up-observable path of p, denoted as πup.Definition 15.
Given a pathπp, if its beginning node is p, this path is called the down-observable path of p, denoted as πdp.
With the reduction rules, several unobservable transitions without fault information may be reduced. However, some unobservable transitions cannot be reduced. In reduction rule (i), if transitionε contains fault information, then places pi and pj cannot be merged. Thus reduction rule (i) needs to be modified. If pi is the output or input of a fault transition, then the new marking in the reduced model is M^pi=Mpj and M^pj=0. If pj is the output or input of the fault transition, then the new marking in the reduced model is M^pi=Mpj and M^pj=0.Definition 16.
Given a fault transitiontf and a place p, T^p is called the up-transition set of place p if all the transitions of t∈T^p satisfy t∈πup.Definition 17.
Given a fault transitiontf and a place p, Tˇp is called the down-transition set of place p if all the transitions of t∈Tˇp satisfy t∈πdp.Definition 18.
Given aFDSNp⟶f, K:T^p⟶f⟶ℕ is called the up-level function of p⟶f and for all t∈T^p⟶f satisfies(1)Kt=0,ift∈To,Kt′+1,ift∈Tuandt′∈T^p⟶f.And t′ is the up-transition of t.Definition 19.
Given aFDSNp←f, K:T^p←f⟶ℕ is called the up-level function of p←f and for all t∈T^p←f satisfies(2)Kt=0,ift∈To,Kt′+1,ift∈Tuandt′∈T^p←f.And t′ is the up-transition of t.Definition 20.
Given aFDSNp⟶f, K:Tˇp⟶f⟶ℕ is called the down-level function of p⟶f and for all t∈Tˇp⟶f satisfies(3)Ht=0,ift∈To,Ht′+1,ift∈Tuandt′∈Tˇp⟶f.And t′ is the down-transition of t.Definition 21.
Given aFDSNp←f, K:Tˇp←f⟶ℕ is called the down-level function of p←f and for all t∈Tˇp←f satisfies(4)Ht=0,ift∈To,Ht′+1,ift∈Tuandt′∈Tˇp←f.And t′ is the down-transition of t.
Based on Definitions13 to 21, the transitions in FDSNp⟶f (or FDSNp⟶f) can therefore be classified.


### 3.4. Maximal Number of Flow-In and Minimal Number of Flow-Out

Definition 22 (see [19]).
Given an observed sequenceω in a Petri net, set Mω=MM0σM,ρσ,To=ω,σ∈T∗ is called a consistent marking set of ω.Definition 23.
Given an observed sequenceω in a Petri net, if ∃ω′=ρT^p,ω, the maximal number of flow-in of place p with ω is θp,ω: = maxMp−M0p, and M∈Mω′.
Consider a placep and an observed sequence ω, and assume the maximal capacity of p is k. The maximal number of flow-in of p must satisfy θp,ω≤k.
Algorithm1 is used for calculating the maximal number of flow-in of place p⟶f (or p←f).
Algorithm1 is proposed on the basis of the inherent structure information of the given partially observed Petri net. Subsequently, we illustrate the algorithm with the input place of fault transition p⟶f. We also apply the reduction rules and calculate all the up-level functions in FDSNp⟶f. The tokens flow into FDSNp⟶f and the observable transitions in πup⟶f are fired. The level function and marking are updated. After the transitions with the new level function are fired, new transitions are once again fired. The level function and marking will stop to update only after the tokens move into p⟶f. At this phase, the variation of Mp⟶f is the maximal number of flow-in of p⟶f.
Assume that the number of inputs ofp⟶f is m. Each πup⟶f has p nodes, where 1≤q≤m. The length of the observed sequence is g. The complexity of calculating the maximal number of flow-in of place p⟶f is ∏1≤i≤mp−1·m·g.Algorithm 1: Computation of the maximal number of flow-in.
Input: FDSNp⟶f, an observed sequence ω, initial marking M0Output: θp⟶f,ω(1)for each t∈T^p⟶fdo(2)  deriveKt(3)end for(4) leti = 0, M=M0(5)Ti=t∈T^p⟶fKt=i(6) letT=Ti(7)ifT≠∅then(8)if transition t is enabled with the marking Mthen(9)   letM=M+C·,t, go to 8(10)else(11)   letT=T−t, go to 7(12)end if(13)else(14)  leti = i+1(15)end if(16)ifi≤K•p⟶fthen(17)  go to 5(18)else(19)  letθp⟶f,ω=Mp⟶f−M0p⟶f(20)end if(21) end the algorithmCorollary 1.
InFDSNp⟶f, if πup⟶f contains an or-split structure, then the maximal number of flow-in of p⟶f (or p←f) cannot be calculated using Algorithm 1.Proof.
The or-split structure comprises a single placep and multiple outputs. When the number of tokens in place p is known, we cannot know with certainty the exact times in which each output is fired, which means that the number of tokens that flow into other places cannot be calculated. Furthermore, because of the uncertain number of tokens in FDSNp⟶f, the maximal number of flow-in of p⟶f cannot be calculated.Definition 24.
Given an observed sequenceω in a Petri net, if ∃ω′′=ρTˇp,ω, the minimal number of flow-out of place p with ω is δp,ω: = minMp−M0p, M∈Mω′′.
Algorithm2 is used for calculating the minimal number of flow-out of place p⟶f (or p←f).
Algorithm2 is proposed on the basis of the inherent structure information of the given partially observed Petri net. Subsequently, we illustrate the algorithm with the input place of fault transition p⟶f. With the use of reduction rules, the down-level functions in FDSNp⟶f should be calculated. For any observable transition t belonging to an observed sequence ω′′, if its firing time is less than the number of tokens in its inputs, then M′=M+C·,t should be calculated. If the firing time is more than the number of tokens in the inputs, then the unobservable transitions with down-level function Ht+1 need to be fired to supplement the tokens in the inputs of transition t. By parity of reasoning, the unobservable transitions with highest down-level function, •p⟶f is fired to supplement the tokens in the inputs of t. After the observed sequence is fired, the number of supplements is the minimal number of flow-out of place p⟶f.
Assume that the number of outputs ofp⟶f is n. Each πdp⟶f has q nodes, where 1≤q≤n. The length of the observed sequence is k. The complexity of calculating the minimal number of flow-out of place p⟶f is ∏1≤j≤nq−1·n·k.Algorithm 2: Computation of the minimal number of flow-out.
Input: FDSNp⟶f, an observed sequence ω, initial marking M0Output: δp⟶f,ω(1)for each t∈Tˇp⟶fdo(2)  deriveHt(3)end for(4)ω′′=ρTˇp⟶fHt=i(5) letT=Ti, M=M0, i=0, q=0(6)ifω′′ is an empty string then(7)  letδp⟶f,ω=q(8)else(9)fort∈ω′′, and t is the first transition of ω′′do(10)ift is enabled at Mthen(11)   letM=M+C·,t(12)else(13)ifi = 1 then(14)    go to 23(15)else(16)    leti = i − 1(17)end if(18)end if(19)end for(20)end if(21) letω′′=ω′′−t, go to 6(22) leti = i − 1(23)ifi=Hp⟶f•then(24)fort∈Tdo(25)ift is enabled at M, q = q + 1 then(26)    letM=M+C·,t, go to 6(27)else(28)    letδp⟶f,ω=q(29)end if(30)end for(31)else(32)fort∈Tdo(33)ift is enabled at Mthen(34)    letM=M+C·,t, go to 6(35)else(36)    letT=T−t(37)end if(38)end for(39)end if(40)ifT=∅then(41)  leti = i+1, go to 23(42)else(43)fort∈Tdo(44)ift is enabled at Mthen(45)    letM=M+C·,t, go to 6(46)else(47)    letT=T−t(48)end if(49)end for(50)end if(51) leti = i+1, go to 23(52)fort∈Tdo(53)ift is enabled at M, q = q+1 then(54)   letM=M+C·,t, go to 6(55)else(56)   letδp⟶f,ω=q(57)end if(58)end for(59) end the algorithmCorollary 2.
InFDSNp⟶f, if πdp⟶f contains an or-joint structure, then the minimal number of flow-out of p⟶f (or p←f) cannot be calculated using Algorithm 2.Proof.
The or-joint structure comprises a single placep and multiple inputs. When the number of tokens in place p is known, we cannot know with certainty the exact times in which each input is fired, which means that the number of tokens that flow out of other places cannot be calculated. Furthermore, because of the uncertain number of tokens in FDSNp⟶f, the minimal number of the flow-out cannot be calculated.


### 3.5. Online Fault Diagnosis

In this part, we deal with the problem of specifying a diagnoser that can detect observable transitions regardless of a normal or faulty system behavior.Definition 25.
Given an observed sequenceω in a Petri net N, Φp,ω: = maxMp is called the maximal retention number of place p with ω.Corollary 3.
Given a fault transitiontf and an observed sequence ω in a FDSNp⟶f, Φp⟶f,ω=θp⟶f,ω−δp⟶f,ω+M0p, M0 is the initial marking of the reduced model.Proof.
InFDSNp⟶f, the initial number of tokens in place p⟶f is M0p⟶f when the reduction rules are applied. After all of the unobservable transitions in πup⟶f are fired, the maximal number of flow-in is θp⟶f,ω=Mp⟶f−M0p⟶f and the new marking is M. Then, all the unobservable transitions in πdp⟶f are fired, and the new marking is M′′ and the minimal number of flow-out is δp⟶f,ω=Mp⟶f−M′p⟶f. The maximal retention number of p⟶f is(5)Φp⟶f,ω=M′p⟶f=Mp⟶f−M0p⟶f−Mp⟶f−M′p⟶f+M0p⟶=θp⟶f,ω−δp⟶f,ω+M0p.Definition 26.
A diagnoser is a functionΔ:To∗×Tf⟶0,1,2. For each observed sequence ω, the following sets hold:(i)
ForΔω,tf=0, the behavior of the system is normal during the observed sequence ω(ii)
ForΔω,tf=1, the behavior is ambiguous(iii)
ForΔω,tf=2, the behavior of the system is faulty at the observed sequence ωTheorem 1.
Given a fault transitiontf and an observed sequence ω in a Petri net, if there exists a FDSNp←f and a FDSNp←f, and no or-split structure exists in πup⟶f and πup←f, and no or-joint structure exists in πdp⟶f and πd≪p←f, then the following are satisfied:(i)
For existingp⟶f, Φp⟶f,ω=0, which leads to Δω,tf=0(ii)
For allp⟶f, Φp⟶f,ω≠0, Φp⟶f,ω≥0, which leads to Δω,tf=1(iii)
For allp←f, Φp←f,ω<0, which leads to Δω,tf=2Proof.
For a fault transitiontf, when the FDSNp⟶f and the FDSNp←f exist, the maximal number of flow-in and the minimal number of flow-out of places p⟶f and p←f may be calculated. Then, according to Corollary 3, the corresponding maximal retention numbers are Φp⟶f,ω and Φp←f,ω. For all places p←f, Φp⟶f,ω=0 means that the increment of tokens in p⟶f equals the initial number of tokens in p⟶f, and no tokens are left in p⟶f with the new marking. The fault transition tf is therefore not enabled and faults cannot occur. Meanwhile, for all places p←f, Φp←f,ω<0 means that the number of flow-out is more than the sum of flow-in and the initial number, but this condition is unreasonable for a Petri net system. Therefore, a fault transition tf needs to occur to supplement the missing number of tokens in place p←f. If Φp⟶f,ω≠0 and Φp⟶f,ω≥0, then the fault transition tf is enabled. Although we cannot decide whether the transition is fired or not, faults may still occur.
When states are increased, the computational complexity of the fault diagnosis becomes high. The computational complexity of calculating the maximal retention number in placesp⟶f and p←f determines the computational complexity of deriving the diagnoser function Δ. Furthermore, the computational complexity of calculating the maximal number of flow-in and minimal number of flow-out was proposed before. Thus the computational complexity of deriving the function Δ is also a polynomial, which allows the method to meet real-time requirements.Example 7.
Consider the partially observed Petri net model as described in Figure1. To=t1,t2,t3 and Tuo=ε1,ε2,ε3,ε4, and the fault transitions are Tf=ε1,ε2. For the fault transition 1, its input and output are p1 and p4, and the FDSNp1 and FDSNp4 can be derived, as shown in Figure 7. After using the modified reduction rule (i), the reduced model can be constructed as shown in Figure 8. M0p1=1, and M0p4=1. Given an observed sequence ω=t1t2t3, on the basis of Algorithms 1–3, we can derive(6)θp1,ω=1,δp1,ω=0,θp4,ω=0,δp4,ω=2,Φp1,ω=2,Φp4,ω=−1,Δω,ε1=2.
The fault transitionε1 must occur. In a similar manner, we can derive Φp5,ω=0, Φp7,ω=0, Δω,ε2=0, and the fault transition ε2 must not occur.Figure 7
FDSNp1 and FDSNp4.Figure 8
The reducedFDSNp1 and FDSNp4.Algorithm 3: Online fault diagnosis.
Input: Petri net system, the fault transition tf, an observed sequence ωOutput:Δω,tf(1)ifFDSNp⟶f and FDSNp←f exist then(2)for all p⟶fdo(3)   deriveθp⟶f,ω and δp⟶f,ω(4)end for(5)for all p←fdo(6)   deriveθp←f,ω and δp←f,ω(7)end for(8)else(9)  end the algorithm(10)end if(11) deriveΦp⟶f,ω and Φp←f,ω(12) deriveΔω,tf


## 3.1. Special Structures

Definition 6.
Given a placep and a path in a Petri net model, this path is defined as an observable path of this place p, denoted as πp, if it satisfies the following:(i)
Its beginning node (or end node) is placep and its end node (or beginning node) is an observable transition(ii)
The rest of its transitions are unobservableDefinition 7.
Given a placep in a Petri net N, if πp exists, an observed subnet of place p is denoted as SNp which is only comprised of all πp.
Consider a partially observed Petri netN and a place p. Assume that the number of nodes in N is m+n and the number of nodes in SNp is r. Obviously r≤m+n and the computational complexity of constructing SNp is polynomial.Definition 8.
Given a placep in a Petri net N, a SNp is defined as a diagnosable subnet of place p, denoted as DSNp, if it satisfies the following:(i)
Any places insideSNp cannot be connected to any transitions outside SNp(ii)
Any unobservable transitions insideSNp cannot be the inputs of any places outside SNpExample 2.
The yellow pathp4ε3p3t2 is an observable path of place p1, namely, πp1, as shown in Figure 1.Figure 1
A partially observed Petri net.Example 3.
Figure2 is an observed subnet of place p4, namely, SNp4. It is also a DSNp4.
For a fault transitiontf, its inputs and outputs are •tf and tf•. If a place p∈•tf (or p∈tf•), then we use p⟶f (or p←f) for brief writing.Figure 2
An observed subnet of placep4.Definition 9.
Given a fault transitiontf, a path πp←f is called a fault observable path of p←f, if it satisfies the following:(i)
The beginning node ofπp←f is p←f(ii)
πp←f contains tfDefinition 10.
Given a fault transitiontf, a path πp⟶f is called a fault observable path of p⟶f, if it satisfies the following:(i)
The beginning node ofπp⟶f is p⟶f(ii)
πp⟶f contains tfDefinition 11.
Given aDSNp←f in a Petri net N, FDSNp←f is called a fault-diagnosable subnet of place p←f, if it satisfies the following:(i)
FDSNp←f is a part of DSNp←f(ii)
πp←f does not belong to FDSNp←fDefinition 12.
Given aDSNp←f in a Petri net N, FDSNp←f is called a fault-diagnosable subnet of place p⟶f, if it satisfies the following:(i)
FDSNp←f is a part of DSNp←f(ii)
πp⟶f does not belong to FDSNp←fExample 4.
Placep4 is the output of fault f1 and Figure 3 is a fault-diagnosable subnet FDSNp4.Figure 3
A fault-diagnosable subnet ofp4.


## 3.2. Reduction Rules

The basic structures of Petri nets are and-joint, and-split, or-joint, or-split, loop, and sequence, as shown in Figure4. Some reduction rules based on these structures were already proposed in [31, 32]. However, in the rule (i) in [31, 32], the authors did not consider the inherent fault information on the unobservable transition, and the rules (ii) and (iii) are not mentioned.Figure 4
Six structures of Petri net.However, not all rules can preserve the diagnosability property. To overcome this limitation, a few other simple rules are proposed as shown in Figure5.Figure 5
Reduction rules applied to Petri net.


### 3.2.1. Fusion of Places in Vertical (Figure5(a))

If there exists a transition between two places that is normal and unobservable, and it has one input and output, then this transition can be omitted and two places can be merged into a new place for reducing the number of nodes in the net. The marking of the new place is the sum of the markings of two previous places.


### 3.2.2. Fusion of Transitions in Parallel (Figure5(b))

If there are several transitions with the same one input and output, and they are all normal and unobservable, then these transitions can be merged into one transition that is normal and unobservable. The new initial marking stays the same.


### 3.2.3. Fusion of Places in Parallel (Figure5(c))

If there are several places with the same one input and output, then these places can be merged into one place. The marking of this place is the minimal of the several ones.Example 5.
As shown in Figure3, FDSNp4 and f2 are a fault transition that contains fault information. By using reduction rule i), places p7 and p2 are merged and transition ε3 can be suppressed. Thus, transition f2 cannot be reduced because it contains fault information. The reduced model is shown in Figure 6.Figure 6
The reduced Petri net model.Theorem 1.
With the use of the above reduction rules, the diagnosability of the reduced Petri net is consistent with that of the initial version.Proof.
If the initial Petri net is not diagnosable, then the two sequences ofσ1 and σ2 exist with the same observation. Furthermore, faults exist in σ2 but not in σ1. After the fault occurs, σ2 can be arbitrarily long. Let a regular and also unobservable transition ε be contained in σ1σ2, and this transition ε can be removed with the use of some previous reduction rules. The observation of this reduced sequence σ1∗σ2∗ is retained even removing the transition ε. Therefore, the system is still not diagnosable.
If the initial Petri net is diagnosable, then no two sequences ofσ1 and σ2 exist with the same observation. Furthermore, faults exist in σ2 but not in σ1. After the fault occurs, σ2 can be arbitrarily long. Let a regular and also unobservable transition ε be contained in σ1σ2, and this transition ε can be removed with the use of some previous reduction rules. The observation of this reduced sequence σ1∗σ2∗ is retained (i.e., not observable). Therefore, the system is still diagnosable.


## 3.2.1. Fusion of Places in Vertical (Figure5(a))

If there exists a transition between two places that is normal and unobservable, and it has one input and output, then this transition can be omitted and two places can be merged into a new place for reducing the number of nodes in the net. The marking of the new place is the sum of the markings of two previous places.


## 3.2.2. Fusion of Transitions in Parallel (Figure5(b))

If there are several transitions with the same one input and output, and they are all normal and unobservable, then these transitions can be merged into one transition that is normal and unobservable. The new initial marking stays the same.


## 3.2.3. Fusion of Places in Parallel (Figure5(c))

If there are several places with the same one input and output, then these places can be merged into one place. The marking of this place is the minimal of the several ones.Example 5.
As shown in Figure3, FDSNp4 and f2 are a fault transition that contains fault information. By using reduction rule i), places p7 and p2 are merged and transition ε3 can be suppressed. Thus, transition f2 cannot be reduced because it contains fault information. The reduced model is shown in Figure 6.Figure 6
The reduced Petri net model.Theorem 1.
With the use of the above reduction rules, the diagnosability of the reduced Petri net is consistent with that of the initial version.Proof.
If the initial Petri net is not diagnosable, then the two sequences ofσ1 and σ2 exist with the same observation. Furthermore, faults exist in σ2 but not in σ1. After the fault occurs, σ2 can be arbitrarily long. Let a regular and also unobservable transition ε be contained in σ1σ2, and this transition ε can be removed with the use of some previous reduction rules. The observation of this reduced sequence σ1∗σ2∗ is retained even removing the transition ε. Therefore, the system is still not diagnosable.
If the initial Petri net is diagnosable, then no two sequences ofσ1 and σ2 exist with the same observation. Furthermore, faults exist in σ2 but not in σ1. After the fault occurs, σ2 can be arbitrarily long. Let a regular and also unobservable transition ε be contained in σ1σ2, and this transition ε can be removed with the use of some previous reduction rules. The observation of this reduced sequence σ1∗σ2∗ is retained (i.e., not observable). Therefore, the system is still diagnosable.


## 3.3. Level Functions

Definition 13.
Given two transitionst1 and t2 in a Petri net system, if •t1=t2•, transition t1 is called the up-transition of t2, and transition t2 is called the down-transition of t1.Definition 14.
Given a pathπp, if its end node is place p, this path is called the up-observable path of p, denoted as πup.Definition 15.
Given a pathπp, if its beginning node is p, this path is called the down-observable path of p, denoted as πdp.
With the reduction rules, several unobservable transitions without fault information may be reduced. However, some unobservable transitions cannot be reduced. In reduction rule (i), if transitionε contains fault information, then places pi and pj cannot be merged. Thus reduction rule (i) needs to be modified. If pi is the output or input of a fault transition, then the new marking in the reduced model is M^pi=Mpj and M^pj=0. If pj is the output or input of the fault transition, then the new marking in the reduced model is M^pi=Mpj and M^pj=0.Definition 16.
Given a fault transitiontf and a place p, T^p is called the up-transition set of place p if all the transitions of t∈T^p satisfy t∈πup.Definition 17.
Given a fault transitiontf and a place p, Tˇp is called the down-transition set of place p if all the transitions of t∈Tˇp satisfy t∈πdp.Definition 18.
Given aFDSNp⟶f, K:T^p⟶f⟶ℕ is called the up-level function of p⟶f and for all t∈T^p⟶f satisfies(1)Kt=0,ift∈To,Kt′+1,ift∈Tuandt′∈T^p⟶f.And t′ is the up-transition of t.Definition 19.
Given aFDSNp←f, K:T^p←f⟶ℕ is called the up-level function of p←f and for all t∈T^p←f satisfies(2)Kt=0,ift∈To,Kt′+1,ift∈Tuandt′∈T^p←f.And t′ is the up-transition of t.Definition 20.
Given aFDSNp⟶f, K:Tˇp⟶f⟶ℕ is called the down-level function of p⟶f and for all t∈Tˇp⟶f satisfies(3)Ht=0,ift∈To,Ht′+1,ift∈Tuandt′∈Tˇp⟶f.And t′ is the down-transition of t.Definition 21.
Given aFDSNp←f, K:Tˇp←f⟶ℕ is called the down-level function of p←f and for all t∈Tˇp←f satisfies(4)Ht=0,ift∈To,Ht′+1,ift∈Tuandt′∈Tˇp←f.And t′ is the down-transition of t.
Based on Definitions13 to 21, the transitions in FDSNp⟶f (or FDSNp⟶f) can therefore be classified.


## 3.4. Maximal Number of Flow-In and Minimal Number of Flow-Out

Definition 22 (see [19]).
Given an observed sequenceω in a Petri net, set Mω=MM0σM,ρσ,To=ω,σ∈T∗ is called a consistent marking set of ω.Definition 23.
Given an observed sequenceω in a Petri net, if ∃ω′=ρT^p,ω, the maximal number of flow-in of place p with ω is θp,ω: = maxMp−M0p, and M∈Mω′.
Consider a placep and an observed sequence ω, and assume the maximal capacity of p is k. The maximal number of flow-in of p must satisfy θp,ω≤k.
Algorithm1 is used for calculating the maximal number of flow-in of place p⟶f (or p←f).
Algorithm1 is proposed on the basis of the inherent structure information of the given partially observed Petri net. Subsequently, we illustrate the algorithm with the input place of fault transition p⟶f. We also apply the reduction rules and calculate all the up-level functions in FDSNp⟶f. The tokens flow into FDSNp⟶f and the observable transitions in πup⟶f are fired. The level function and marking are updated. After the transitions with the new level function are fired, new transitions are once again fired. The level function and marking will stop to update only after the tokens move into p⟶f. At this phase, the variation of Mp⟶f is the maximal number of flow-in of p⟶f.
Assume that the number of inputs ofp⟶f is m. Each πup⟶f has p nodes, where 1≤q≤m. The length of the observed sequence is g. The complexity of calculating the maximal number of flow-in of place p⟶f is ∏1≤i≤mp−1·m·g.Algorithm 1: Computation of the maximal number of flow-in.
Input: FDSNp⟶f, an observed sequence ω, initial marking M0Output: θp⟶f,ω(1)for each t∈T^p⟶fdo(2)  deriveKt(3)end for(4) leti = 0, M=M0(5)Ti=t∈T^p⟶fKt=i(6) letT=Ti(7)ifT≠∅then(8)if transition t is enabled with the marking Mthen(9)   letM=M+C·,t, go to 8(10)else(11)   letT=T−t, go to 7(12)end if(13)else(14)  leti = i+1(15)end if(16)ifi≤K•p⟶fthen(17)  go to 5(18)else(19)  letθp⟶f,ω=Mp⟶f−M0p⟶f(20)end if(21) end the algorithmCorollary 1.
InFDSNp⟶f, if πup⟶f contains an or-split structure, then the maximal number of flow-in of p⟶f (or p←f) cannot be calculated using Algorithm 1.Proof.
The or-split structure comprises a single placep and multiple outputs. When the number of tokens in place p is known, we cannot know with certainty the exact times in which each output is fired, which means that the number of tokens that flow into other places cannot be calculated. Furthermore, because of the uncertain number of tokens in FDSNp⟶f, the maximal number of flow-in of p⟶f cannot be calculated.Definition 24.
Given an observed sequenceω in a Petri net, if ∃ω′′=ρTˇp,ω, the minimal number of flow-out of place p with ω is δp,ω: = minMp−M0p, M∈Mω′′.
Algorithm2 is used for calculating the minimal number of flow-out of place p⟶f (or p←f).
Algorithm2 is proposed on the basis of the inherent structure information of the given partially observed Petri net. Subsequently, we illustrate the algorithm with the input place of fault transition p⟶f. With the use of reduction rules, the down-level functions in FDSNp⟶f should be calculated. For any observable transition t belonging to an observed sequence ω′′, if its firing time is less than the number of tokens in its inputs, then M′=M+C·,t should be calculated. If the firing time is more than the number of tokens in the inputs, then the unobservable transitions with down-level function Ht+1 need to be fired to supplement the tokens in the inputs of transition t. By parity of reasoning, the unobservable transitions with highest down-level function, •p⟶f is fired to supplement the tokens in the inputs of t. After the observed sequence is fired, the number of supplements is the minimal number of flow-out of place p⟶f.
Assume that the number of outputs ofp⟶f is n. Each πdp⟶f has q nodes, where 1≤q≤n. The length of the observed sequence is k. The complexity of calculating the minimal number of flow-out of place p⟶f is ∏1≤j≤nq−1·n·k.Algorithm 2: Computation of the minimal number of flow-out.
Input: FDSNp⟶f, an observed sequence ω, initial marking M0Output: δp⟶f,ω(1)for each t∈Tˇp⟶fdo(2)  deriveHt(3)end for(4)ω′′=ρTˇp⟶fHt=i(5) letT=Ti, M=M0, i=0, q=0(6)ifω′′ is an empty string then(7)  letδp⟶f,ω=q(8)else(9)fort∈ω′′, and t is the first transition of ω′′do(10)ift is enabled at Mthen(11)   letM=M+C·,t(12)else(13)ifi = 1 then(14)    go to 23(15)else(16)    leti = i − 1(17)end if(18)end if(19)end for(20)end if(21) letω′′=ω′′−t, go to 6(22) leti = i − 1(23)ifi=Hp⟶f•then(24)fort∈Tdo(25)ift is enabled at M, q = q + 1 then(26)    letM=M+C·,t, go to 6(27)else(28)    letδp⟶f,ω=q(29)end if(30)end for(31)else(32)fort∈Tdo(33)ift is enabled at Mthen(34)    letM=M+C·,t, go to 6(35)else(36)    letT=T−t(37)end if(38)end for(39)end if(40)ifT=∅then(41)  leti = i+1, go to 23(42)else(43)fort∈Tdo(44)ift is enabled at Mthen(45)    letM=M+C·,t, go to 6(46)else(47)    letT=T−t(48)end if(49)end for(50)end if(51) leti = i+1, go to 23(52)fort∈Tdo(53)ift is enabled at M, q = q+1 then(54)   letM=M+C·,t, go to 6(55)else(56)   letδp⟶f,ω=q(57)end if(58)end for(59) end the algorithmCorollary 2.
InFDSNp⟶f, if πdp⟶f contains an or-joint structure, then the minimal number of flow-out of p⟶f (or p←f) cannot be calculated using Algorithm 2.Proof.
The or-joint structure comprises a single placep and multiple inputs. When the number of tokens in place p is known, we cannot know with certainty the exact times in which each input is fired, which means that the number of tokens that flow out of other places cannot be calculated. Furthermore, because of the uncertain number of tokens in FDSNp⟶f, the minimal number of the flow-out cannot be calculated.


## 3.5. Online Fault Diagnosis

In this part, we deal with the problem of specifying a diagnoser that can detect observable transitions regardless of a normal or faulty system behavior.Definition 25.
Given an observed sequenceω in a Petri net N, Φp,ω: = maxMp is called the maximal retention number of place p with ω.Corollary 3.
Given a fault transitiontf and an observed sequence ω in a FDSNp⟶f, Φp⟶f,ω=θp⟶f,ω−δp⟶f,ω+M0p, M0 is the initial marking of the reduced model.Proof.
InFDSNp⟶f, the initial number of tokens in place p⟶f is M0p⟶f when the reduction rules are applied. After all of the unobservable transitions in πup⟶f are fired, the maximal number of flow-in is θp⟶f,ω=Mp⟶f−M0p⟶f and the new marking is M. Then, all the unobservable transitions in πdp⟶f are fired, and the new marking is M′′ and the minimal number of flow-out is δp⟶f,ω=Mp⟶f−M′p⟶f. The maximal retention number of p⟶f is(5)Φp⟶f,ω=M′p⟶f=Mp⟶f−M0p⟶f−Mp⟶f−M′p⟶f+M0p⟶=θp⟶f,ω−δp⟶f,ω+M0p.Definition 26.
A diagnoser is a functionΔ:To∗×Tf⟶0,1,2. For each observed sequence ω, the following sets hold:(i)
ForΔω,tf=0, the behavior of the system is normal during the observed sequence ω(ii)
ForΔω,tf=1, the behavior is ambiguous(iii)
ForΔω,tf=2, the behavior of the system is faulty at the observed sequence ωTheorem 1.
Given a fault transitiontf and an observed sequence ω in a Petri net, if there exists a FDSNp←f and a FDSNp←f, and no or-split structure exists in πup⟶f and πup←f, and no or-joint structure exists in πdp⟶f and πd≪p←f, then the following are satisfied:(i)
For existingp⟶f, Φp⟶f,ω=0, which leads to Δω,tf=0(ii)
For allp⟶f, Φp⟶f,ω≠0, Φp⟶f,ω≥0, which leads to Δω,tf=1(iii)
For allp←f, Φp←f,ω<0, which leads to Δω,tf=2Proof.
For a fault transitiontf, when the FDSNp⟶f and the FDSNp←f exist, the maximal number of flow-in and the minimal number of flow-out of places p⟶f and p←f may be calculated. Then, according to Corollary 3, the corresponding maximal retention numbers are Φp⟶f,ω and Φp←f,ω. For all places p←f, Φp⟶f,ω=0 means that the increment of tokens in p⟶f equals the initial number of tokens in p⟶f, and no tokens are left in p⟶f with the new marking. The fault transition tf is therefore not enabled and faults cannot occur. Meanwhile, for all places p←f, Φp←f,ω<0 means that the number of flow-out is more than the sum of flow-in and the initial number, but this condition is unreasonable for a Petri net system. Therefore, a fault transition tf needs to occur to supplement the missing number of tokens in place p←f. If Φp⟶f,ω≠0 and Φp⟶f,ω≥0, then the fault transition tf is enabled. Although we cannot decide whether the transition is fired or not, faults may still occur.
When states are increased, the computational complexity of the fault diagnosis becomes high. The computational complexity of calculating the maximal retention number in placesp⟶f and p←f determines the computational complexity of deriving the diagnoser function Δ. Furthermore, the computational complexity of calculating the maximal number of flow-in and minimal number of flow-out was proposed before. Thus the computational complexity of deriving the function Δ is also a polynomial, which allows the method to meet real-time requirements.Example 7.
Consider the partially observed Petri net model as described in Figure1. To=t1,t2,t3 and Tuo=ε1,ε2,ε3,ε4, and the fault transitions are Tf=ε1,ε2. For the fault transition 1, its input and output are p1 and p4, and the FDSNp1 and FDSNp4 can be derived, as shown in Figure 7. After using the modified reduction rule (i), the reduced model can be constructed as shown in Figure 8. M0p1=1, and M0p4=1. Given an observed sequence ω=t1t2t3, on the basis of Algorithms 1–3, we can derive(6)θp1,ω=1,δp1,ω=0,θp4,ω=0,δp4,ω=2,Φp1,ω=2,Φp4,ω=−1,Δω,ε1=2.
The fault transitionε1 must occur. In a similar manner, we can derive Φp5,ω=0, Φp7,ω=0, Δω,ε2=0, and the fault transition ε2 must not occur.Figure 7
FDSNp1 and FDSNp4.Figure 8
The reducedFDSNp1 and FDSNp4.Algorithm 3: Online fault diagnosis.
Input: Petri net system, the fault transition tf, an observed sequence ωOutput:Δω,tf(1)ifFDSNp⟶f and FDSNp←f exist then(2)for all p⟶fdo(3)   deriveθp⟶f,ω and δp⟶f,ω(4)end for(5)for all p←fdo(6)   deriveθp←f,ω and δp←f,ω(7)end for(8)else(9)  end the algorithm(10)end if(11) deriveΦp⟶f,ω and Φp←f,ω(12) deriveΔω,tf


## 4. Example

An intelligent warehouse center is provided as an example. It is used to sort and consolidate the goods in some supply chain systems. The sorting operation is performed with an automated guided vehicle (AGV) as described in Figure9, which is similar to the conveyor network studied in [4].Figure 9
The sorting operation of an AGV.The intelligent warehouse center can be described in simplified form as follows: First, the AGV will cross seven areas (for example,A1 to A7). In these areas, some different operations are designated before the AGV returns to A1. Then, two types of parts A and B will be transferred by the AGV from a loading station (for example, A1) to the buffers B1 (Z3) and B2 (A5), respectively. After that, there is a bar code reader named R. It would distinguish between these parts and then transfers the information to the supervisor. Through activating these two switches of sw1 and sw2, the supervisor can direct the parts toward the corresponding buffer. Once the switch sw1 is activated, a part would move toward B1 (i.e., a part of type 1 can be detected). Similarly, once the switch sw2 is activated, a part would move toward B2 (i.e., a part of type 2 can be detected). Finally, the AGV would move to the other areas when the process of driving a part to B1 (or B2) is finished. In the end, it would return to A1. When the sensors s3, s5, and s7 are contacted, it indicates that the AGV has entered the areas A3, A5, and A7. In this model of the intelligent warehouse center, two different classes of faults are considered. The first one is when a part of type 1 exits the system, it exits through the buffer B2 but not the buffer B1, and then, we say a fault f1 (T12) occurs. The second one is when the AGV starts a cycle but without any part loading, and then, we say a fault of class f2 (T1) occurs.The Petri net systemP,T,M0 with the initial marking M0=100000010000T is used to model the system. The normal behaviors are represented by transitions T2 to T11 as shown in Figure 10 (full and black lines), whereas the faulty behaviors are denoted by the unobservable transitions T1 and T12, as shown in Figure 10 (dashed and red lines). Unobservable transitions are represented by empty sticks. The significance of transitions and places is listed in Table 1.Figure 10
Partially observed Petri net model of sorting operation with an AGV.Table 1
Nodes of partially observed Petri net model of sorting operation with an AGV.
P/TSignificanceP1−P7AGV in areaA1−A7P8AGV is available to take a new partP9−P10Switchsw1 (resp., sw2) is activatedP11−P12Output buffersB1-B2T2−T7Operations in areaA2–A7 are overT8−T9AGV exits the loading station with a part of type 1 (resp., 2)T10−T11A part exits the system and is stored in bufferB1 (resp., B2)T1Faultf2: AGV exits the loading station without any partT12Faultf1: a part of type 1 activates the switch sw2With the use of reduction rule (i), the diagnosable subnet of this model can be derived as shown in Figure11. The input of fault transition f1 is place P9, and the output is P10. The input of fault transition f2 is place P1, and the output is P2.Figure 11
The reduced model of sorting operation with an AGV.Consider an observed sequenceω=T2T4. In Figure 7, the initial markings are M0P1=1, M0P2=0, M0P9=0, and M0P10=0. Transition T2 is fired once, and θP2,ω=0, δP2,ω=1, δP2,ω=1; θP1,ω=0, δP1,ω=0, and ΦP1,ω=1. ΔT2,f2=2, and thus, the fault f2 must occur. Moreover, θP10,ω=0, δP10,ω=0, ΦP10,ω=0; θP9,ω=0, δP9,ω=0, and ΦP9,ω=0. ΔT2,f1=0, and thus, the fault f1 must not occur.Consider an observed sequenceω=T2T8. We can derive θP2,ω=1, δP2,ω=1, ΦP2,ω=0; θP1,ω=0, δP1,ω=1, and ΦP1,ω=0. ΔT2,f2=0, and thus, the fault f2 must not occur. In addition, θP10,ω=0, δP10,ω=0, ΦP10,ω=0; θP9,ω=1, δP9,ω=0, and ΦP9,ω=1. ΔT2,f1=1, and the fault f1 may occur.Consider an observed sequenceω=T2T8T11. We can derive θP2,ω=1, δP2,ω=1, ΦP2,ω=0; θP1,ω=0, δP1,ω=1, and ΦP1,ω=0. ΔT2,f2=0, and thus, the fault f2 must not occur. In addition, θP10,ω=0, δP10,ω=1, ΦP10,ω=−1; θP9,ω=1, δP9,ω=0, and ΦP9,ω=1. ΔT2,f1=2, and the fault f1 must occur.We simulate some more sequences with Algorithm3, and partially, details of the situations are listed in Tables 2 and 3.Table 2
Fault situations with an observed sequenceω.
ωΦP9,ωΦP10,ωΔω,f1T2000T2T8101T2T8T111−12T2T8T11T61−12T2T8T11T6T82−12Table 3
Fault situations with an observed sequenceω.
ωΦP2,ωΦP1,ωΔω,f2T2−112T2T8000T2T8T11000T2T8T11T6011T2T8T11T6T8100The structure of the Petri net is much simpler than that of the method using the reachability graph, as shown in Figure11. The number of state markings (polynomial) is also decreased. By considering another method with basis markings, if the observable string is T2T4, then the possible occurring sequences are T1T2T3T4, T1T2T3T4T5, T7T1T2T3T4, and T7T1T2T3T4T5, the results of which are the same as our method. In the basis marking method, the larger the structure of the Petri net is, the higher the occurring sequences will be, which leads to a more complex computation. This limitation is avoided effectively in the present work because not all of the possible occurring sequences are collected; i.e., we only focus on the inputs and outputs of the fault transitions and calculate the number of tokens that flow in or out. Consequently, we can diagnose the faulty behavior in the polynomial level.


## 5. Conclusions and Future Work

This work addresses the problem of fault diagnosis of DESs and proposes an online diagnoser on the basis of the partially observed Petri net. The online computation is formulated on a net structure and applied with reduction rules. The method involves an observed sequence of system events, which then is used as basis for deciding online whether the system behavior is normal, faulty, or uncertain. To achieve the goals, the maximal number of flow-in and the minimal number of flow-out are introduced. By calculating the maximal and minimal numbers for some reduced subnets, the maximal retention number of placesp⟶f and p←f can be obtained, which means that the number of tokens in places p⟶f and p←f can be determined after an observed sequence is fired. Subsequently, the fault transition is enabled (or not). The entire process is formulated using the appropriate reduced subnets with fault information, and it permits to reduce the computational effort to solve the fault diagnosis problem at the price of a small memory increase, which meets the real-time requirement.Several directions are considered in our future work. First, we want to explore additional reduction rules for the fault diagnosis problem of DESs. In such a case, the structure of the Petri net can be further elaborated. In addition, we plan to explain in detail the relationship between transitions and places given the above special structure. Finally, we will likely extend the proposed method to labeled Petri nets in the nondeterminism context.



---

*Source: 2392904-2020-06-26.xml*