Guanghui Zhu
email: zhuguanghui86@gmail.com

Lei Feng
email: lfeng@kth.se

Zhiwu Li

Naiqi Wu
email: nqwu@must.edu.mo

Online Fault Diagnosis of Discrete Event Systems Modeled With Labeled Petri Nets Using an Overall Fault Status

come

Abstract-In this paper we present a fault diagnosis approach using labeled Petri nets, where the faults are modeled by unobservable transitions and the unobservable subnet is acyclic. In contrast to detecting the individual faults separately, a new specification called an overall fault status is introduced, which indicates the occurrence of faults from a global system perspective. Due to the introduction of the overall fault status, a more precise and informative diagnosis result can be provided and in some cases, the occurrence of some faults in a system can be detected before the actual faults are isolated, i.e., we are certain about the occurrence of faults but which faults have not been ascertained. An integer linear programming (ILP) problem is built according to the observed word. We prove that all transition sequences determined by solutions to the ILP problem constitute the set of sequences consistent with the observed word. By specifying different objective functions to the ILP problem, the diagnosis results of each individual fault and the overall fault status can be obtained. An online diagnosis algorithm is developed to implement the proposed diagnosis process, which reports the diagnosis results after the occurrence of every observable event.

Index Terms-Fault diagnosis, discrete event system, Petri net, integer linear programming, overall fault status.

I. INTRODUCTION

A. Position of the paper

With the development of contemporary information technology, the man-made mechanical and electronic systems that can be characterized as discrete event systems (DES) are becoming more and more complicated. To ensure their stable and correct operations, fault diagnosis has been an active research area in recent decades. A fault is a kind of event that causes a deviation in system's behavior such that the performance or throughput of the system is degraded. Fault diagnosis aims to detect and isolate a fault when it occurs such that it can be fixed and the system can recover from it.

The diagnosis of discrete event systems was originally discussed in [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF], [START_REF]Failure diagnosis using discrete-event models[END_REF] using an automaton model with faulty (unobservable) events, where a diagnoser, i.e., a deterministic finite automaton (DFA), is first built and then based on the observed sequence the diagnosis result can be directly obtained by checking the diagnoser. The authors also define the diagnosability of an automation model and provide a necessary and sufficient condition for diagnosability.

An alternative to automata for modeling DES is provided by Petri nets. Their structural properties offer a new perspective for supervisory control [START_REF] Chen | Compact supervisory control of discrete event systems by Petri nets with data inhibitor arcs[END_REF], [START_REF] Chen | On the enforcement of a class of nonlinear constraints on Petri nets[END_REF], model identification [START_REF] Zhu | Model-based fault identification of discrete event systems using partially observed Petri nets[END_REF], [START_REF] Giua | Identification of free-labeled Petri nets via integer programming[END_REF], performance optimization [START_REF] He | Performance optimization for timed weighted marked graphs under infinite server semantics[END_REF], and knowledge discovery [START_REF] Van Der Aalst | Process Discovery: An Introduction[END_REF], [START_REF] Zhang | A learning-based synthesis approach to the supremal nonblocking supervisor of discrete-event systems[END_REF]. In addition, the state equation of a Petri net provides a linear algebraic technique to deal with the issue of state estimation [START_REF] Ma | Basis marking representation of Petri net reachability spaces and its application to the reachability problem[END_REF]- [START_REF] Li | Minimum initial marking estimation in labeled Petri nets[END_REF], which is always more efficient than exhaustively enumerating the reachability graph. In particular, we in this paper deal with the fault diagnosis issue using Petri nets.

In the context of Petri nets, Prock [START_REF] Prock | A new technique for fault detection using Petri nets[END_REF] proposed a diagnosis approach for a nuclear power plant by monitoring the number of tokens residing in places associated with P-invariants in a Petri net. Wu and Hadjicostis [START_REF] Wu | Algebraic approaches for fault identification in discrete-event systems[END_REF] developed an algebraic approach for fault diagnosis, where both place and transition faults are defined. By introducing additional places into a net, a redundant Petri net can be obtained. The place and/or transition faults can be detected by inspecting the current marking of the redundant net. Ramírez-Treviño et al. [START_REF] Ramírez-Treviño | Online fault diagnosis of discrete event systems. A Petri net-based approach[END_REF] proposed a modeling methodology to build an interpreted Petri net (IPN) model of a system and then a fault detection algorithm based on the built IPN is provided. Benveniste et al. [START_REF] Benveniste | Diagnosis of asynchronous discrete-event systems: a net unfolding approach[END_REF] reported a net unfolding approach to explore the diagnosis of asynchronous systems, which can be used in a distributed environment.

On the other hand, there is a deluge of studies that use Petri nets by explicitly modeling faults of a system as unobservable transitions [START_REF] Zaytoon | Overview of fault diagnosis methods for discrete event systems[END_REF], i.e, Petri nets, called faulty Petri nets, that contain not only regular but faulty behavior of a system. Genc et al. [START_REF] Genc | Distributed diagnosis of discrete-event systems using Petri nets[END_REF] originally extended the event-based diagnosis using automata to the case of faulty Petri nets. They construct a diagnoser, i.e., a labeled Petri net, according to the original net model of a system and a diagnosis result can be provided online when observing an event. The main drawback of this approach is the computational complexity due to the reachability analysis at each step. Giua and Seatzu [START_REF] Giua | Fault detection for discrete event systems using Petri nets with unobservable transitions[END_REF] proposed a basis-marking-based approach. By means of basis markings and the corresponding justifications, the enumeration of paths in a reachability graph can be avoided. Cabasino et al. [START_REF] Cabasino | Fault detection for discrete event systems using Petri nets with unobservable transitions[END_REF]- [START_REF] Cabasino | Decentralized diagnosis of discrete-event systems using labeled Petri nets[END_REF] extended this approach to the case of labeled Petri nets, i.e., nets where two or more transitions can share the same label. They develop a basis reachability graph (BRG), which can be built off-line and provides an efficient method for online diagnosis. In [START_REF] Basile | An efficient approach for online diagnosis of discrete event systems[END_REF], Basile et al. defined a new type of marking with negative elements, called g-marking, and proposed an online diagnosis algorithm based on it. Integer linear programming (ILP) is a typical technique to deal with the issue of state estimation in a Petri net. An online diagnosis approach using ILP is reported in [START_REF] Dotoli | On-line fault detection in discrete event systems by Petri nets and integer linear programming[END_REF]. More specifically, the authors first build an integer linear programming model without objective function according to the observed transition sequence. Then, by assigning different objective functions to it, the occurrence of a fault can be detected. Ru et al. [START_REF] Ru | Fault diagnosis in discrete event systems modeled by partially observed Petri nets[END_REF] addressed the issue of fault diagnosis using a partially observed Petri net (POPN), where a POPN is first converted into a labeled net and then an algorithm based on the reachability graph is proposed.

B. Motivation

In a faulty Petri net model, faults are explicitly modeled as unobservable transitions and the transition set T is divided into two disjoint subsets T o and T u with T = T o ∪ T u , where T o denotes the set of observable transitions and T u the set of unobservable transitions. Transitions t 1 ∈ T o and t 2 ∈ T u are assigned a label from the event set E and an empty string ε, respectively. In general, the diagnosis result provided by approaches based on faulty Petri nets [START_REF] Basile | State estimation and fault diagnosis of labeled time Petri net systems with unobservable transitions[END_REF], [START_REF] Giua | Fault detection for discrete event systems using Petri nets with unobservable transitions[END_REF]- [START_REF] Cabasino | Discrete event diagnosis using labeled Petri nets. An application to manufacturing systems[END_REF], [START_REF] Basile | An efficient approach for online diagnosis of discrete event systems[END_REF], [START_REF] Wang | Diagnosis of time Petri nets using fault diagnosis graph[END_REF] can be represented by a function ∆ :

E * ×T f → {0, 1, 2}
, where E is the set of events associated with a faulty net, T f = {f 1 , . . . , f n f } ⊆ T u is the set of n f fault transitions, and 0, 1 and 2 denote that fault transition f i ∈ T f does not occur for sure, f i may occur and f i occurs with certainty, respectively. For example, assuming that the observed sequence is ω, ∆(ω, f 1 ) = 1 indicates that f 1 may (possibly) occur till the observation of ω.

We next provide an example to show the motivation of introducing an overall fault status. Consider the net in Fig. 1 that models a plant producing bolts and nuts. This plant has two production lines: one (upper part) produces mini-size bolts and nuts and the other (lower part) produces mediumsize ones. In Fig. 1, we have

E = {a, b, c, d}, T u = {t 2 , t 3 , t 6 , t 9 , f 1 , f 2 , f 3 }, T f = {f 1 , f 2 , f 3 }, T a = {t 1 , t 8 },
T b = {t 5 , t 7 , t 10 }, T c = {t 4 , t 11 }, and T d = {t 12 }. The unobservable transitions are represented as gray bars (fault transitions f 1 , f 2 and f 3 are colored red), and T x denotes the set of transitions labeled x with x ∈ {a, b, c, d}. It is significant to design an algorithm to solve the following problem.

Problem 1. Consider the net shown in Fig. 1 and assume that the observed sequence is ω = abb. Does the plant modeled by this net run normally till the observation of ω? (i.e., have some faults occurred in the plant?)

The existing approaches for fault diagnosis, such as those in [START_REF] Basile | State estimation and fault diagnosis of labeled time Petri net systems with unobservable transitions[END_REF], [START_REF] Giua | Fault detection for discrete event systems using Petri nets with unobservable transitions[END_REF], [START_REF] Cabasino | Discrete event diagnosis using labeled Petri nets. An application to manufacturing systems[END_REF], [START_REF] Basile | An efficient approach for online diagnosis of discrete event systems[END_REF], [START_REF] Wang | Diagnosis of time Petri nets using fault diagnosis graph[END_REF], provide an ambiguous answer to Problem 1 only. The procedure in [START_REF] Cabasino | Discrete event diagnosis using labeled Petri nets. An application to manufacturing systems[END_REF], [START_REF] Basile | An efficient approach for online diagnosis of discrete event systems[END_REF], [START_REF] Wang | Diagnosis of time Petri nets using fault diagnosis graph[END_REF] to solve Problem 1 can be summarized as follows.

Step 1: Compute the diagnosis results of f 1 , f 2 and f 3 , respectively, and obtain that ∆(ω,

f 1 ) = 1, ∆(ω, f 2 ) = 1, and ∆(ω, f 3 ) = 0.
Step 2: Because of the ambiguous diagnoses of f 1 and f 2 , one cannot unambiguously determine the occurrence of faults and only an answer that the plant may run abnormally can be provided.

In fact, the exact answer is that the plant runs abnormally and one of f 1 and f 2 necessarily occurs. This situation can be explained by Fig. 2(a), where the symbol ε denotes an empty string. As a part of reachability graph of the net shown in Fig. 1, it shows all transition sequences consistent with ω. In Fig. 2(a), M 0 is the initial marking, and M ω1 and M ω2 are the markings reachable by firing the sequences consistent with ω = abb. We observe that each path from M 0 to M ω1 or M ω2 either goes through f 1 or f 2 , i.e., there is no path that passes none of faults. Fig. 2(a) can be condensed as Fig. 2(b) which shows all the paths more intuitively. By considering all possible evolutions of the plant consistent with the observation abb, there does not exist a possibility that no fault occurs since each path contains a fault transition. This implies that a fault must occur till the observation of abb and the plant does not run normally. This paper will provide a more precise and informative solution to Problem 1 by extending the existing diagnosis function. The new diagnosis function is defined as ∆ : E * × T f S → {0, 1, 2}, where T f S = T f ∪ {F} and F stands for the overall fault status. In contrast to detecting the individual fault separately, the overall fault status indicates the occurrence of faults from a global system perspective. In particular, ∆(ω, F) = 0 denotes that a system is running normally, ∆(ω, F) = 1 some faults may occur in the system, and 2 some faults must have occurred. Note that, in some cases, the diagnosis of F, i.e., ∆(ω, F), can be directly inferred from ∆(ω, f i ) with i = 1 . . . n f . However, in other cases, novel methodologies have to be proposed to compute ∆(ω, F).

t1 ( a ) t 8 ( a ) t 2 ( e ) t 3 ( e ) t 3 ( e ) f 1 t2 ( e ) t 5 (b) t 2 (e) f 1 t 3 (e) t 5 ( b ) t 3 (e) f 1 t 5 ( b ) t 5 ( b ) t 5 (b) t 9 (e) t 10 (b) f 2 t 7 (b) M 0 M w1 M w2 f 1 f 1 f 1 f 2 M 0 M w1 M w2 (a) (b)
Due to the use of the overall fault status, in some cases, one can detect the occurrence of faults before the actual faults are isolated. Let us consider the net in Fig. 1 again. The diagnosis results for observed words ω's are listed in Table I, where ∆(ω, F) denotes the diagnosis of the overall fault status. We observe that for ω = a, both f 1 and f 2 do not occur. For ω = abb, both f 1 and f 2 may occur, as indicated by ∆(abb, f 1 ) = 1 and ∆(abb, f 2 ) = 1. However, ∆(abb, F) = 2 implies that at least one fault must occur in the plant even if the diagnoses of f 1 and f 2 are ambiguous, i.e., we detect the occurrence of faults before the definite diagnosis of individual fault transition.

f 1 0 1 1 . . . 2 f 2 0 0 1 . . . 0 f 3 0 0 0 . . . 0 F 0 1 2 . . . 2
This is particularly meaningful for a system that needs to respond to failures in time. For example, consider an aircraft with five faults from f 1 to f 5 . If we detect that ∆(ω, f 1 ) = 1, ∆(ω, f 2 ) = 1, ∆(ω, f i ) = 0 for i = 3, . . . , 5, and ∆(ω, F) = 2, some faults must occur in the aircraft though we cannot determine which faults occur at present. The captain of the aircraft can deal with this situation immediately before an unambiguous fault is reported.

However, for systems that can tolerate failures, we can wait for a longer observation of an event sequence in order to exactly find the faults with less cost. For example, some components of a system are hard to access and one should exactly identify the location of a fault before taking any corrective action that may involve component inspection and replacement [START_REF]Failure diagnosis using discrete-event models[END_REF]. If the occurrence of faults in a system is detected according to the overall fault status F and the exact faults cannot be currently ascertained, we can consider the following two ways to find the exact faults:

(1) Observe continuously the output of a net till a sufficiently long sequence is observed if the net is diagnosable (see Section V);

(2) Stop the real-world system and inspect all the faults f 's with ∆(ω, f ) = 1 one by one. The first way provides exact fault locations such that they can be fixed in a short time. But a long wait may be needed to precisely identify the faults. For example, considering Fig. 1 and Table I, we detect the occurrence of faults (∆(abb, F) = 2) but cannot determine that the fault is f 1 or f 2 when ω = abb. If the plant continues to run and the observed word is ω = abbacba, we then conclude that fault f 1 must happen (∆(ω, f 1 ) = 2) and f 2 not (∆(ω, f 2 ) = 0). On the other hand, for the second way, one has to stop (part of) the plant and further test it to find the faulty components. This will possibly reduce the throughput of the plant and increase the cost of isolating faults.

When performing diagnosis in a system, we will first try to detect any abnormal behavior of the system based on the observation. If the behavior is found to be abnormal, we will refine the diagnosis by using new observations and possibly further testing the system until the faulty components are found [START_REF] Hamscher | Readings in Model-Based Diagnosis[END_REF]. In this paper, a framework to isolate and fix faults in a system is proposed based on the overall fault status F. This framework is appropriate for faults that cause significant changes in the system state but do not bring the system to a halt. In a real-world system, the overall fault status F can be viewed as a fault indicator light that has three colors of green (∆(ω, F) = 0), yellow (∆(ω, F) = 1), and red (∆(ω, F) = 2). If the light is green, it implies that the system is running normally and no fault is detected. Whereas a red light indicates that one or more faults have occurred and then one can check ∆(ω, f i ) with i = 1, . . . , n f to localize and fix the faults. Graphically, the diagnosis flow can be described by Fig. 3.

Start

Set light to green, w = e

Wait for observation of event e

w=we, compute D(w, fi) and D(w, F) and write to running log, set color of light by D(w, F)

Running log example:

a b c f 1 0 0 1 f 2 0 1 1 F 0 1 2

Start

Reset and start system

Light is red?

Wait for some time As shown in Fig. 3, there are two processes in the system: diagnosis process and supervision process. The diagnosis process makes a diagnosis when observing an event and enters the diagnosis result into a log file (see Fig. 3(a)). Note that a plant may continue to run and record the diagnosis result even if some faults have occurred. The supervision process monitors the operation of the plant and decides whether to stop it to fix faults when the indicator light is red (see Fig. 3(b)).

C. Contribution

In this paper, we extend the approach in [START_REF] Dotoli | On-line fault detection in discrete event systems by Petri nets and integer linear programming[END_REF] to explore an improved diagnosis algorithm based on labeled Petri nets and the overall fault status. As done in the literature [START_REF] Cabasino | Fault detection for discrete event systems using Petri nets with unobservable transitions[END_REF], [START_REF] Basile | An efficient approach for online diagnosis of discrete event systems[END_REF], the approach in [START_REF] Dotoli | On-line fault detection in discrete event systems by Petri nets and integer linear programming[END_REF] can only be used for a special class of labeled Petri nets, i.e., nets in which each observable transition is assigned a unique label. We first extend the approach in [START_REF] Dotoli | On-line fault detection in discrete event systems by Petri nets and integer linear programming[END_REF] to the case of a labeled Petri net with an arbitrary labeling function, i.e., two or more transitions can share the same label, and then propose some new theoretical results to compute ∆(ω, F). An online diagnosis approach is presented, which implements the diagnosis process described in Fig. 3(a).

Note that Fanti et al. [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] also extend the approach in [START_REF] Dotoli | On-line fault detection in discrete event systems by Petri nets and integer linear programming[END_REF] to the case of a labeled Petri net. They first build an ILP problem based on a transition sequence σ o ∈ T * o using a special class of labeled Petri net where an observable transition is assigned a unique label. Then, for an observed word ω ∈ E * , they exhaustively enumerate all possible sequences σ o 's with σ o ∈ T * o whose projections on E are ω and, for each sequence σ o , solve a number of ILP problems built from it to perform online diagnosis. For an observed word ω, there may exist a lot of transition sequences σ o 's whose projection on E are ω. Thus, a large number of ILP problems may need to be solved according to the approach in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF], which is infeasible in general due to prohibitive computational cost.

Different from the work in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF], we in this paper extend and improve the approach in [START_REF] Dotoli | On-line fault detection in discrete event systems by Petri nets and integer linear programming[END_REF] from a different perspective. Specifically, our extension is completely based on labeled Petri nets and an ILP problem is constructed based on the observed word ω not a transition sequence σ o ∈ T * o . Compared with the approach in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF], the number of times of solving ILP problems of our approach is usually considerably small when perform diagnosis for an observed word (see Section VI for an example).

The main contributions of the paper can be summarized as follows.

(1) We introduce a new diagnosis specification called an overall fault status and extend the diagnosis function such that a more precise and informative diagnosis result can be provided. (2) We extend and improve the approach in [START_REF] Dotoli | On-line fault detection in discrete event systems by Petri nets and integer linear programming[END_REF] to the case of general labeled Petri nets, i.e., nets where two or more transitions can share the same label. Different from the extension in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF], we do not need to enumerate all possible sequences of observable transitions consistent with an observed word ω ∈ E * and just solve an ILP problem built according to ω to perform diagnosis. (3) In contrast to the work in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF], our approach is usually more efficient, demonstrated by extensive experimental studies (see Section VI). This paper is organized in seven sections. We in Section I review the related literature and show the motivation of introducing the overall fault status. The basic definitions and preliminaries on Petri nets are recalled in Section II.

Section III defines the problem on which this paper focuses. In Section IV, a solution based on integer linear programming is proposed. Section V discusses the relationship between the diagnosability and the overall fault status. We present an example to compare the proposed approach with the one in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] in Section VI. Finally, we conclude the paper in Section VII.

II. PRELIMINARIES

This section recalls the Petri net formalism and some preliminary results used throughout the paper. The readers can refer to [START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF] and [START_REF] Cassandras | Introduction to discrete event systems[END_REF] for more details on Petri nets. We denote by N the set of non-negative integers.

A. Basics of Petri nets

A Petri net is a four-tuple N = (P, T, P re, P ost), where P = {p 1 , . . . , p m } is a set of m places, T = {t 1 , . . . , t n } is a set of n transitions with P ∪ T = ∅ and P ∩ T = ∅, P re : P × T → N and P ost : P × T → N are the preand post-incidence matrices, respectively, which specify the structure of the net. Graphically, places and transitions are represented by circles and bars, respectively. For each arc with weight γ from place p (transition t) to transition t (place p), it holds P re(p, t) = γ (P ost(p, t) = γ). The other elements of P re and P ost are 0. The incidence matrix of a net is denoted by C = P ost -P re. A Petri net is said to be acyclic if there is no directed cycle.

For a transition t ∈ T , its preset is defined as • t = {p ∈ P | P re(p, t) > 0}, and its postset is defined as t

• = {p ∈ P | P ost(p, t) > 0}. A transition t is said to be a source transition if • t = ∅.
A marking of a Petri net is a vector M : P → N, and M (p) indicates the number of tokens, pictorially denoted by black dots, in place p. We use

x 1 p 1 + • • • + x m p m to denote the marking [x 1 , . . . , x m ] T for economy of space. A net system N, M 0 is a Petri net N with an initial marking M 0 . A transition t ∈ T is enabled at marking M if for all p ∈ • t, M (p) ≥ P re(p, t), which is denoted by M [t . An enabled transition t at M can fire yielding a new marking M such that M = M + C(•, t), which is denoted by M [t M .
For a transition sequence σ ∈ T * and a marking M , M [σ denotes that σ is enabled at marking M and M [σ M denotes that a new marking M is reachable from M after firing σ. The set of all the markings reachable from M 0 is denoted by R(N, M 0 ), called the reachability set of a Petri net. The set of transition sequences enabled at the initial marking M 0 is defined as

L(N, M 0 ) = {σ ∈ T * | M 0 [σ }
which is called the language of Petri net system N, M 0 .

We define a function π : T * → N n that maps a transition sequence σ ∈ T * to n-dimensional column vector y = π(σ), called firing vector, such that y(t) = k if transition t appears k times in σ. Write t ∈ σ to denote that t is contained in σ.

Given M 0 [σ M , we have

M = M 0 + C • π(σ). (1)
Eq. ( 1), called the state equation, shows that there exists a non-negative integer vector y such that M = M 0 + C • y if M is reachable from M 0 , which is a necessary but not sufficient condition for the reachability of marking M from M 0 . However, for an acyclic net, it is necessary and sufficient, as verified by the following result.

Theorem 1. [START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF] Let N, M 0 be an acyclic Petri net. A marking M ≥ 0 is reachable from M 0 if and only if (iff) there exists a non-negative integer vector y satisfying M = M 0 + C • y.

B. Labeled Petri net

Given a Petri net N = (P, T, P re, P ost) and the event set E, a labeling function λ : T → E ∪ {ε} assigns to each transition t ∈ T either a symbol from the event set E or an empty string ε. In the case of no confusion, a labeled Petri net in this paper refers to a net with an arbitrary labeling function, i.e., two or more transitions can share the same label. A Petri net system N, M 0 with a labeling function λ : T → E ∪ {ε} is called a labeled Petri net system, denoted by N, M 0 , E, λ .

A transition t is said to be unobservable or silent if it is associated with the label ε, i.e., λ(t) = ε. The set of unobservable transitions is denoted by T u = {t ∈ T | λ(t) = ε} with cardinality n u . All other transitions whose labels come from event set E constitute the set of observable transitions

T o = {t ∈ T | λ(t) = ε} with cardinality n o . Thus, set T is divided into two disjoint subsets T o and T u with T = T o ∪ T u .
For a faulty Petri net, the faults are always modeled by unobservable transitions and accordingly the set of unobservable transitions is also divided into two disjoint subsets T reg and T f , i.e., T u = T reg ∪ T f , where T reg denotes the set of regular unobservable transitions and T f the set of n f fault transitions. We use T e = {t ∈ T | λ(t) = e} to represent the set of transitions with the same label e ∈ E.

Analogous to the definition of function π, for each sequence

σ o ∈ T * o , we define a function π o : T * o → N no such that y = π o (σ o ) and y(t) = k if t ∈ T o appears k times in σ o .
Similarly, the function π u : T * u → N nu associates a sequence σ u ∈ T * u with an n u -dimensional vector π u (σ u ). We extend the definition of labeling function λ to a sequence σt ∈ T * such that λ(σt) = λ(σ)λ(t), i.e., for a sequence σ ∈ T * , ω = λ(σ) is an observed word composed of the labels of observable transitions contained in σ. The set of observed words in a labeled Petri net system N, M 0 , E, λ is defined as

L E (N, M 0 ) = {ω ∈ E * | σ ∈ L(N, M 0 ), ω = λ(σ)}.
Given a transition sequence σ, we use ←σ to denote the last transition in σ. For example, if σ = t 1 t 2 t 3 , we have ←σ = t 3 . For an observed word ω ∈ L E (N, M 0 ), the set

C(ω) = {σ ∈ T * | σ ∈ L(N, M 0 ), λ(σ) = ω}
denotes all sequences that are consistent with ω and

← - C (ω) = {σ ∈ T * | σ ∈ C(ω), ← - σ ∈ T o }
stands for the consistent transition sequences whose last transitions are observable, i.e., the sequences with observable tails.

Accordingly, the set of markings that are reachable by firing the consistent transition sequences with observable tails is defined as

← - D (ω) = {M ∈ N m | σ ∈ ← - C (ω), M 0 [σ M }.
Example 1. Consider the net shown in Fig. 1 and a part of its reachability graph shown in Fig. 2. If the observed word is ω = a, then it is readily verified that

C(ω) = {t 1 , t 1 t 2 , t 1 t 2 f 1 , t 1 t 2 f 1 t 3 , t 1 t 2 t 3 , t 1 t 2 t 3 f 1 , t 1 t 3 , t 1 t 3 t 2 , t 1 t 3 t 2 f 1 , t 8 , t 8 t 9 } and ← - C (ω) = {t 1 , t 8 }.
On the other hand, for ω = abb, we have

← - D (ω) = {M ω1 , M ω2 }.
Definition 1. Given a net N = (P, T, P re, P ost) and a subset of transitions T ⊆ T , the T -induced subnet of N is a Petri net N = (P, T , P re , P ost ), where P re and P ost are the restrictions of P re and P ost to P × T , respectively, i.e., the net N is obtained by removing all transitions in T \ T from N .

Given a net N = (P, T, P re, P ost) with T = T o ∪ T u , according to Definition 1, one can readily obtain from N the observable subnet N o = (P, T o , P re o , P ost o ) and the unobservable subnet N u = (P, T u , P re u , P ost u ). Moreover, the incidence matrices of nets N o and N u are denoted by C o = P ost o -P re o and C u = P ost u -P re u , respectively. Note that, as in the literature [START_REF] Cabasino | Fault detection for discrete event systems using Petri nets with unobservable transitions[END_REF], [START_REF] Basile | An efficient approach for online diagnosis of discrete event systems[END_REF], [START_REF] Dotoli | On-line fault detection in discrete event systems by Petri nets and integer linear programming[END_REF], this paper assumes that the unobservable subnet is acyclic.

III. PROBLEM STATEMENT

Fault diagnosis consists in determining if faults have occurred in a system according to the observed system output, such as the observed word ω in a Petri net. As done in the literature, we can design a diagnoser, i.e., a diagnosis function, to show the diagnosis result. For a labeled Petri net with event set E, a diagnoser is a function ∆ : E * × T f → {0, 1, 2} such that a fault f ∈ T f does not occur if ∆(ω, f ) = 0, may occur if 1, and necessarily occurs if 2. Next, we provide the formal definition of diagnosis function ∆. Definition 2. Let N, M 0 , E, λ be a labeled Petri net system. The diagnosis function ∆ :

E * × T f → {0, 1, 2} associates an observed word ω ∈ L E (N, M 0 ) and a fault f ∈ T f with a diagnosis state such that (1) ∆(ω, f ) = 0 if for all σ ∈ ← - C (ω), f / ∈ σ, i.e.
, each path consistent with ω in the reachability graph does not pass fault transition f . (2) ∆(ω, f ) = 1 if there exist σ 1 , σ 2 ∈ ← -C (ω) such that f / ∈ σ 1 and f ∈ σ 2 , i.e., there exist two paths, one of which passes f and the other does not.

(3) ∆(ω, f ) = 2 if for all σ ∈ ← - C (ω), f ∈ σ.
Note that some existing studies [START_REF] Giua | Fault detection for discrete event systems using Petri nets with unobservable transitions[END_REF], [START_REF] Cabasino | Fault detection for discrete event systems using Petri nets with unobservable transitions[END_REF] additionally consider the possible fault transitions after the last observed event of ω when performing diagnosis, i.e., the definition of ∆ is based on C(ω) not ← -C (ω). However, we in this paper do not adopt this setting and detect only the fault transitions occurring before the last event of ω in order to be consistent with the seminal work in [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF].

From Definition 2, we observe that the diagnoser ∆ only concerns if an individual fault f ∈ T f has occurred during the system evolution and there is no information to indicate the overall system fault state, i.e., the diagnosis results of all fault transitions cannot completely describe the fault state of the system. To overcome this, we introduce the notion of the overall fault status F in Subsection I-B.

A diagnostic Petri net system N, M 0 , E, λ, F is a labeled Petri net system N, M 0 , E, λ with an overall fault status F. For N, M 0 , E, λ, F , the diagnosis function is extended as ∆ : E * × T f S → {0, 1, 2}, where T f S = T f ∪ {F }. The diagnosis of F is defined as follows.

Definition 3. Let N, M 0 , E, λ, F be a diagnostic Petri net system. For an observed word ω ∈ L E (N, M 0 ), the diagnosis of F is represented by a diagnosis function ∆ :

E * × T f S → {0, 1, 2} such that (1) ∆(ω, F) = 0 if for all σ ∈ ← - C (ω) and for all f ∈ T f , f / ∈ σ. (2) ∆(ω, F) = 1 if there exist σ 1 , σ 2 ∈ ← - C (ω) such that (i) for all f ∈ T f , f / ∈ σ 1 and (ii) there exists f ∈ T f , f ∈ σ 2 . (3) ∆(ω, F) = 2 if for all σ ∈ ← - C (ω), there exists f ∈ T f such that f ∈ σ.
In some cases, the value of ∆(ω, F) can be directly deduced from ∆(ω, f i ). We provide the following proposition to formalize this situation. However, when there exist two or more f 's such that ∆(ω, f ) = 1, we have to figure out a new method to compute ∆(ω, F). Proposition 1. Given a diagnostic Petri net system N, M 0 , E, λ, F and an observed word ω ∈ L E (N, M 0 ), the following statements hold:

(1) ∆(ω, F) = 0 if for all f ∈ T f , ∆(ω, f ) = 0, (2) ∆(ω, F) = 2 if there exists f ∈ T f such that ∆(ω, f ) = 2, (3) ∆(ω, F) = 1 if there exists only one f ∈ T f such that ∆(ω, f ) = 1 and ∆(ω, f ) = 0 for other faults f ∈ T f .
Proof. The conclusions (1) and ( 2) can be directly derived from Definitions 2 and 3. For (3), since there is one f ∈ T f such that ∆(ω, f ) = 1, there exist two paths σ 1 , σ 2 ∈ ← -C (ω) satisfying f ∈ σ 1 and f / ∈ σ 2 . Moreover, for any other fault transition f , it holds ∆(ω, f ) = 0. Thus, we have f / ∈ σ 2 for each f ∈ T f , i.e., ∆(ω, F) = 1.

The conclusion (3) in Proposition 1 provides a straightforward method to compute ∆(ω, F) in the case that there is only one f ∈ T f satisfying ∆(ω, f ) = 1 (for all f ∈ T f \ {f }, ∆(ω, f ) = 0). However, for the case that there are two or more f 's such that ∆(ω, f ) = 1, Corollary 3 has to be employed to compute ∆(ω, F). The Lines 14-19 of Algorithm 1 show the use of Proposition 1 when performing diagnosis of F.

Next, we formally define the problem considered in this paper. In Section IV, an algorithm based on integer linear programming is provided to solve this problem.

Problem 2 (Online diagnosis). Given a diagnostic Petri net system N, M 0 , E, λ, F with T = T o ∪ T u and T u = T reg ∪ T f , let the observed word ω be null initially. The diagnosis problem consists in computing ∆(ω, f ) and ∆(ω, F) for each observed event e during the evolution of the system, where ω = ωe, f ∈ T f , and F is the overall fault status.

By Definitions 2 and 3, we know that an intuitive method to solve Problem 2 is to analyze the reachability graph of a net. However, this is usually infeasible because of its huge size. In order to avoid analyzing the reachability graph, an integer linear programming technique is often used for a Petri net. We next present an ILP-based solution to Problem 2.

IV. ILP-BASED SOLUTION

In [START_REF] Dotoli | On-line fault detection in discrete event systems by Petri nets and integer linear programming[END_REF], an approach based on ILP is proposed for fault diagnosis using Petri nets in which each observable transition is associated with a unique label. In this paper, we introduce the overall fault status and extend this approach to the case of a labeled Petri net. First, we give a theorem that is the cornerstone of the proposed ILP-based approach.

Theorem 2. Given a labeled Petri net N, M 0 , E, λ and an observed word ω = e 1 e 2 . . . e h ∈ L E (N, M 0 ), there exists a sequence σ = σ u1 t α1 . . . σ u h t α h ∈ ← -C (ω) if and only if there exist vectors y i and binary variables z ei j with i = 1, . . . , h and j = 1, . . . , n ei satisfying the following equation

                                                   M 0 + C u • i γ=1 y γ + i-1 γ=1 ne γ δ=1 C(•, t eγ δ ) • (1 -z eγ δ ) -P re(•, t ei 1 ) ≥ -z ei 1 • K . . . M 0 + C u • i γ=1 y γ + i-1 γ=1 ne γ δ=1 C(•, t eγ δ ) • (1 -z eγ δ ) -P re(•, t ei ne i ) ≥ -z ei ne i • K z ei 1 + . . . + z ei ne i = n ei -1 T ei = {t ei 1 , . . . , t ei ne i } y i ∈ N nu z ei 1 , . . . , z ei ne i ∈ {0, 1} i = 1, . . . , h, (2)
where h ∈ N is the length of the observed word, n ei is the cardinality of set T ei , σ ui ∈ T * u , t αi ∈ T ei , y i = π u (σ ui ) is a firing vector, and K is a sufficiently large positive integer.

Proof. For i = 1, . . . , h, Eq. ( 2) contains h groups of constraints. (if ) For i = 1, we obtain the first group of constraints shown as follows:

         M 0 + C u • y 1 -P re(•, t e1 1 ) ≥ -z e1 1 • K . . . M 0 + C u • y 1 -P re(•, t e1 ne 1 ) ≥ -z e1 ne 1 • K z e1 1 + . . . + z e1 ne 1 = n e1 -1 Since z e1
k with k = 1, . . . , n e1 are binary variables, there must exist a variable with value 0 among them. Without loss of generality, we assume z e1 1 = 0. Then we have

M 0 + C u • y 1 ≥ P re(•, t e1
1 ). Considering that the unobservable subnet is acyclic, there exists a transition sequence σ u1 ∈ T * u such that

y 1 = π u (σ u1 ) and M 0 [σ u1 t e1 1 . It is clear that σ u1 t e1 1 ∈
← -C (e 1 ) holds.

For i = 2, we obtain the second group of constraints:

                   M 0 +C u • (y 1 + y 2 ) + C(•, t e1 1 )(1 -z e1 1 ) + . . . + C(•, t e1 ne 1 )(1 -z e1 ne 1 ) -P re(•, t e2 1 ) ≥ -z e2 1 • K . . . M 0 +C u • (y 1 + y 2 ) + C(•, t e1 1 )(1 -z e1 1 ) + . . . + C(•, t e1 ne 1 )(1 -z e1 ne 1 ) -P re(•, t e2 ne 2 ) ≥ -z e2 ne 2 • K z e2 1 + . . . + z e2 ne 2 = n e2 -1
We know that z e1 1 = 0 and z e1 k = 1 with k = 2, . . . , n e1 . Moreover, analogous to the situation of i = 1, we assume z e2 1 = 0. Thus, we have

M 0 +C u •y 1 +C(•, t e1 1 )+C u •y 2 ≥ P re(•, t e2 1 ). Since there exists a sequence σ u1 satisfying M 0 [σ u1 t e1 1 M 1 and y 1 = π u (σ u1 ), M 1 +C u •y 2 ≥ P re(•, t e2
1 ) holds. Being the unobservable subnet acyclic, there exists σ u2 ∈ T * u such that M 1 [σ u2 t e2 1 and y 2 = π u (σ u2 ). Thus we conclude that there exists σ = σ u1 t e1 1 σ u2 t e2 1 satisfying M 0 [σ and σ ∈ ← -C (e 1 e 2 ). If the theorem is true for i = k -1 with 2 ≤ k ≤ h, we next prove that it holds for i = k. For i = k, without loss of generality, we assume z ej 1 = 0 with j = 1, . . . , k. Then, it holds

M 0 + C u • k γ=1 y γ + k-1 γ=1 C(•, t eγ 1 ) ≥ P re(•, t e k 1 )
.

Moreover, we have already known that

y i = π u (σ ui ) with i = 1, . . . , k -1 and M 0 [σ u1 t α1 . . . σ u k-1 t α k-1 M k-1 . Thus, M k-1 + C u • y k ≥ P re(•, t e k 1 )
≥ 0 holds. Since the unobservable subnet is acyclic, there exists a sequence

σ u k ∈ T * u such that M k-1 [σ u k t e k 1 M k . Thus, it holds σ u1 t α1 . . . σ u k-1 t α k-1 σ u k t α k ∈ ← - C (e 1 .
. . e k ), i.e., we prove by induction that there exists a sequence σ = σ u1 t α1 . . . σ u h t α h ∈ ← -C (ω). (only if ) For the observed word ω = e 1 e 2 . . . e h , if there exists a sequence σ = σ u1 t α1 . . . σ u h t α h ∈ ← -C (ω), a solution to Eq. ( 2) can be found as follows. First, we set y i = π u (σ ui ) for i = 1, . . . , h. Second, since t αi ∈ T ei , without loss of generality, we assume t ei 1 = t αi and then it holds z ei 1 = 0 and z ei i = 1 for i = 2, . . . , n ei . Thus, there exist y i and z ei j with i = 1, . . . , h and j = 1, . . . , n ei satisfying Eq. ( 2).

On the basis of Theorem 2, we can infer that all sequences σ's corresponding to the solutions to Eq. ( 2) constitute the set ← -C (ω). Thus, by associating an objective function with Eq. ( 2), we can determine if a fault has occurred or not. In the following, three corollaries based on Theorem 2 are provided to describe this.

Corollary 1. Given a labeled Petri net N, M 0 , E, λ and an observed word ω = e 1 e 2 . . . e h , then for each f ∈ T f , ∆(ω, f ) = 0 if ILPP 1 admits a solution γ = 0.

ILPP 1:    γ = max h i=1 y i (f ) s.t. Eq. (2)
Proof. If γ = 0, by checking all possible solutions to Eq. ( 2), there does not exist y i such that

y i (f ) > 0. By Theorem 2, each σ ui in σ = σ u1 t α1 . . . σ u h t α h ∈ ← - C (ω) does not contain f , i.e., for all σ ∈ ← - C (ω), f / ∈ σ, which implies ∆(ω, f ) = 0.
Corollary 2. Given a labeled Petri net N, M 0 , E, λ and an observed word ω = e 1 e 2 . . . e h , for each f ∈ T f , ∆(ω, f ) = 2 if ILPP 2 admits a solution γ > 0.

ILPP 2:    γ = min h i=1 y i (f ) s.t. Eq. (2)
Proof. If γ > 0, then there exists at least one y i in solutions to Eq. ( 2) such that y i (f ) > 0, i.e., for all σ ∈ ← -

C (ω), f ∈ σ, which indicates ∆(ω, f ) = 2.
For an observed word ω and each f ∈ T f , Corollaries 1 and 2 are devoted to computing the value of ∆(ω, f ). On the other hand, for the overall fault status F, we can compute ∆(ω, F) according to Proposition 1 and the following corollary.

Corollary 3. Given a diagnostic Petri net system N, M 0 , E, λ, F and an observed word ω = e 1 e 2 . . . e h , ∆(ω, F) = 2 if ILPP 3 admits γ > 0 and ∆(ω, F) = 0 or 1 if γ = 0.

ILPP 3:    γ = min 1 1×n f • h i=1 y i (T f ) s.t. Eq. (2)
Proof. Note that objective function h i=1 y i (T f ) denotes the sum of projections of n u -dimensional column vectors y i 's over the set T f . If γ = 0, there exists a group of unobservable sequences σ ui corresponding to y i with i = 1 . . . h such that σ = σ u1 t α1 . . . σ u h t α h and f / ∈ σ for each f ∈ T f , i.e., there exists at least one path which passes none of fault transitions in the reachability graph from M 0 to ← -D (ω). Thus, in this case, ∆(ω, F) = 0 or 1 according to Definition 3. On the contrary, if γ > 0, there does not exist such a path, i.e., each path must pass one or more fault transitions. Thus, we have ∆(ω, F) = 2. Now, an online algorithm to Problem 2 can be provided. Algorithm 1 describes the basic steps of how to perform diagnosis in a labeled Petri net by using the ILP technique only. The correctness of this algorithm is ensured by Proposition 1 and Corollaries 1, 2 and 3.

We briefly illustrate how Algorithm 1 works. It is described in C-like syntax. For example, we use the symbol "=" to represent an assignment operation and "==" to indicate that two variables are equal. In Line 1, R = 0 n f is an n fdimensional column vector that records the diagnosis result of each f ∈ T f . For a fault f , its diagnosis is denoted by R(f ). Note that n f is the cardinality of set T f . Variable s represents the diagnosis of the overall fault status F, i.e., ∆(ω, F). The diagnosis results R and s are written into a log file in Line 26. We in Section I discuss how to use the log file to refine the diagnosis result (see Fig. 3(b)). The value of ∆(ω, f ) with f ∈ T f , i.e., R(f ), is first computed by Lines 4-13 according to Corollaries 1 and 2. In some cases, ∆(ω, F) can be directly derived from R (see Proposition 1 for details). Thus by Lines 26 Output R and s and write them into log file; Goto 2; 14-19, we compute ∆(ω, F) according to the diagnosis of each f ∈ T f , i.e., R. If ∆(ω, F) cannot be directly obtained by R, we have to solve ILPP 3 to determine ∆(ω, F) according to Corollary 3 (Lines 21-25). When the algorithm completes the diagnosis of the current step, it returns to Line 2 to wait for a new observed event.

The main computational cost of Algorithm 1 stems from the solutions of ILPPs 1, 2, 3. As known, solving an integer linear programming problem is NP-hard. Further, the computational cost mainly depends on its size,, i.e., the number of integer variables and constraints. We next analyze the size of the programming problem Eq. [START_REF]Failure diagnosis using discrete-event models[END_REF].

For ω = e 1 . . . e h , it is readily to verify that the number of variables in Eq. ( 2) can be represented as

I = (n u + n e1 ) + (n u + n e2 ) + . . . + (n u + n e h ) = h • n u + (n e1 + . . . + n e h ) ≈ h • (n u + n f ),
where

n u = |T u | 1 , n f = |T f |, n ei = |T ei |. Eq. (2) contains h 1 | • | denotes the cardinality of a set.
groups of constraints and (n u + n ei ) denotes the number of variables in the ith group. Specifically, n u denotes the length of vector y i and n ei the number of binary variables, i.e., z ei 1 , . . . , z ei ne i

. At the same time, the number of constraints is represented as

J = (m • n e1 + 1) + . . . + (m • n e h + 1) = m • (n e1 + . . . + n e h ) + h ≈ h • (m • n f + 1),
where m is the number of places in a labeled Petri net. For e i ∈ ω, there are n ei transitions whose labels are e i . Thus for the ith group of constraints, it contains m•n ei +1 constraints in scalar form, where "1" denotes the constraint z ei 1 +. . .+z ei

ne i = n ei -1.
In summary, the number of variables and constraints in Eq. ( 2) is linear in the length of the observed word. If the observed word is very long, we may not be able to obtain the diagnosis result in real time. However, the approach based on ILP is straightforward and easy to implement, and can be used as a basis to develop more efficient approaches. II, where, for each event e i , there is a column which lists the diagnosis result and running time corresponding to e i . For example, considering e 3 = b (i.e., ω = e 1 e 2 e 3 = abb), the diagnosis results are ∆(ω, f 1 ) = 1, ∆(ω, f 2 ) = 1, ∆(ω, f 3 ) = 0, and ∆(ω, F) = 2 and the running time is 0.0209s. Note that the time is obtained by executing a MATLAB procedure with GUROBI solver (academic license) [START_REF] Optimizer | [END_REF] on a laptop computer with Intel i5-4200M 2.5GHz processor and 8G DDR3 1600Hz RAM.

V. DIAGNOSABILITY AND OVERALL FAULT STATUS

The diagnosability of a Petri net is discussed in [START_REF] Cabasino | Diagnosability of bounded petri nets[END_REF]- [START_REF] Basile | On k-diagnosability of Petri nets via integer linear programming[END_REF]. If a fault f is diagnosable, then the occurrence of f can be detected in a finite number of steps. Given a Petri net language L, its post-language after a transition sequence σ ∈ L is defined as L/σ = {τ ∈ T * | στ ∈ L}. Formally, the diagnosability of f is defined as follows. Definition 4. [START_REF]Diagnosability of discrete-event systems using labeled Petri nets[END_REF] Given a labeled net N, M 0 , E, λ , a fault transition f is diagnosable if there exists an integer

K ∈ N such that ∀σ = σf ∈ L(N, M 0 ), ∀τ ∈ L(N, M 0 )/σ with |τ | > K ⇒ ∀σ ∈ ← - C (λ(στ )), f ∈ σ , where σ ∈ L(N, M 0 ).
If all fault transitions of a Petri net system are diagnosable, then the Petri net system is said to be diagnosable. For a diagnosable labeled Petri net, we have the following proposition.

Proposition 2. Consider a diagnosable labeled Petri net system N, M 0 , E, λ with an overall fault status F. For each sequence σf σ ∈ L(N, M 0 ), it holds ∆(ω, F) = 2, where σ ∈ T * , f ∈ T f , σ ∈ T * with |σ | > K, and ω = λ(σf σ ).

Proof. Since f is diagnosable, for each σ 1 ∈ ← -C (ω), it holds f ∈ σ 1 . Thus, we have ∆(ω, F) = 2 by Definition 3.

In plain words, when a system is running, a fault f ∈ T f occurs and the process continues. After K steps, we are sure that f has occurred according to the observation ω. Thus,

∆(ω, f ) = 2 is true, which implies ∆(ω, F) = 2.
Only when the Petri net model of a system is diagnosable (or I-diagnosable [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF]), can the diagnosis algorithms detect unambiguously which faults have occurred. However, due to the use of overall fault status F, even if a net model of a system is not diagnosable, it is possible to detect the occurrence of faults in the system though we do not know exactly which fault occurs. An example is provided to clarify this. Example 3. Consider the net shown in Fig. 4, where T u = {t 6 , f 1 , f 2 } and T f = {f 1 , f 2 }. According to Definition 4, both f 1 and f 2 are not diagnosable. Assume that the observed word is ω = (abb)(abb) • • • . Then it holds ∆(ω, f 1 ) = ∆(ω, f 2 ) = 1, i.e., the diagnosis results of f 1 and f 2 are ambiguous for infinite ω. However, for ω = abb, it holds ∆(ω , F) = 2, i.e., when observing only abb, we have already known that some faults occur in the system. In this case, although we are sure that at least a fault has occurred, we are unable to exactly identify which faults have occurred. In real-world systems, a possible strategy is to stop the plant and inspect the faults one by one.

VI. CASE STUDY

We in this section explore the computational overhead of the proposed algorithm and compare its efficiency with the one shown in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] by an example. Consider the labeled Petri net shown in Fig. 5 that is originally introduced in [START_REF] Genc | Distributed diagnosis of discrete-event systems using Petri nets[END_REF] and slightly modified in this paper, where Let α = 10 and β = 10, and assume that the observed word is ω = ae(aeg) 10 gggg, where (aeg) 10 represents that the sequence aeg repeats 10 times. When observing an event, we make a diagnosis using Algorithm 1. The running time of Algorithm 1 for each observed event is shown in Fig. 6, where the x-axis represents the index of each event in sequence ω. We have shown in Section IV that the size of programming model Eq. ( 2) is linear with respect to the length of the observed word. However, the difficulty of a generic ILP problem always increases exponentially with respect to its size, which is verified by Fig. 6. This implies that one probably cannot obtain the diagnosis result in real time if the observed sequence is very long. However, integer linear programming is a standard mathematical tool for diagnosis of Petri nets based on which some new approaches can be developed to overcome the complexity issue, which will be done in our subsequent work.

T u = {t 1 , f 1 , t 4 , t 11 , f 2 }, T f = {f 1 , f 2 }, T a = {t 3 , t
Fanti et al. [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] also proposed an algorithm for fault diagnosis using labeled Petri nets and integer linear programming. However, the key idea is different from us. They first build an integer programming problem according to a transition sequence σ ∈ T * o not an observed word ω ∈ E * . Then, for an observed word ω, they explore all possible sequences of observable transitions whose projections over E are equal to ω. The size of the programming problem in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] is smaller than the one in this paper. However, it has to be solved more times to obtain the diagnosis result.

The output and computational process of the algorithm proposed by Fanti et al. [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] are different from ours. In order to compare the efficiency of these two algorithms, we have to modify one of them to make them have the same input and output. We here choose to modify Fanti's algorithm, though it is completely feasible to modify our algorithm (note that modifying our algorithm will lose some diagnostic information). The details of the modification of Fanti's algorithm is discussed in Appendix A and this section mainly focuses on the comparison of these two algorithms. On the other hand, our algorithm, i.e., Algorithm 1, and the modified version of Fanti's algorithm are both implemented in MATLAB language. The readers can refer to [START_REF] Zhu | Matlab programs for this paper[END_REF] for the source code.

Consider the net in Fig. 5 again and assume that α = β = 7. If the observed word is ω = ae(aeg) 7 gggg, the comparison of these two algorithms is shown in Table III. The first row lists all events in ω. The second row shows the number of times to solve the programming problems defined in this paper when performing diagnosis using the proposed algorithm. The third row shows the number of times to solve the programming problems defined in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] when dealing with the diagnosis issue using the algorithm (modified version) developed in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF]. The fourth and fifth rows demonstrate the running time of diagnosis algorithms proposed by us and Fanti et al. [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF], respectively. The running time is tested using GUROBI solver [START_REF] Optimizer | [END_REF] on a laptop computer with Intel i5-4200M 2.5GHz processor and 8G DDR3 1600Hz RAM. The sixth row lists the diagnosis result for each event, which is represented as a row vector [a b c] such that ∆(ω, f 1 ) = a, ∆(ω, f 2 ) = b, and ∆(ω, F) = c. Note that the diagnosis of the fourth event from the last is [1 1 2], i.e., we detect the occurrence of faults (∆(ω, F) = 2) before the exact faults are ascertained. The detailed comparison of running time is also illustrated by Fig. 7. We observe that our approach is more efficient in this example. Fig. 7. Comparison of our approach with the one in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF].

VII. CONCLUSION

This paper addresses the problem of fault diagnosis by formulating and solving ILP problems. The main contributions consist in introducing the overall fault status and proposing an online diagnosis algorithm based on labeled Petri nets, in which two or more transitions can share the same label. The overall fault status provides a more informative diagnosis result, i.e., not only every fault but also the global system fault status can be detected. In addition, we show that, in some cases, a definite conclusion on the occurrence of faults in a system can be given even if the system is not diagnosable. We also compare the efficiency of the proposed approach with the one in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] by a case study and the result shows that our approach is usually more efficient.

In future work, we plan to extend and modify the other diagnosis approaches, such as those in [START_REF] Basile | An efficient approach for online diagnosis of discrete event systems[END_REF] and [START_REF] Giua | Fault detection for discrete event systems using Petri nets with unobservable transitions[END_REF], to make them have a uniform interface. Then, we will develop a software package to compare their efficiency. On the other hand, we will explore the use of an overall fault status in a distributed environment.

1] [1 0 1] [1 1 1] • • • • • • • • • • • • • • • [1 1 2] [0 2 2] • • • • • •

Fig. 1 .

 1 Fig. 1. A plant model producing bolts and nuts.

Fig. 2 .

 2 Fig. 2. (a) All paths consistent with abb and (b) an intuitive representation of (a).

f∆

  (ω, f ) ω a ab abb . . . abbacba

Fig. 3 .

 3 Fig. 3. (a) Diagnosis process and (b) supervision process

Algorithm 1 : 5 Set γ 1 6 if γ 1 == 0 then 7 R 8 else 9 Set γ 2 10 if γ 2 > 0 then 11 R 13 R 21 Set γ 3 22 if γ 3 > 0 then 23 s 25 s

 15161789210211132132232325 Online fault diagnosis using a diagnostic Petri net systemInput: A diagnostic Petri net system N, M 0 , E, λ, F Output: The diagnosis result for each observed event e ∈ E 1 ω = ε, R = 0 n f , s = 0; 2 Wait until a new event e is observed; 3 ω = ωe; 4 for each f ∈ T f do be the maximal objective value of ILPP 1; (f ) = ∆(ω, f ) = 0; be the minimal objective value of ILPP 2;(f ) = ∆(ω, f ) = 2; 12 else (f ) = ∆(ω, f ) = 1; 14 if R == 0 then15 s = ∆(ω, F) = 0; 16 else if there exists an entry r in vector R such that r == 2 then 17 s = ∆(ω, F) = 2; 18 else if there exists only an entry r in vector R such that r == 1 then 19 s = ∆(ω, F) = 1; 20 else be the minimal objective value of ILPP 3; = ∆(ω, F) = 2; 24 else = ∆(ω, F) = 1;

Example 2 .

 2 Let us consider the net shown in Fig. 1. Assume that the observed word is ω = abba. The diagnosis result and running time are shown in Table

Fig. 5 .

 5 Fig. 5. A Petri net for case study.

Fig. 6 .

 6 Fig. 6. Running time for each observed event.

  Online Fault Diagnosis of Discrete Event Systems Modeled With Labeled Petri Nets Using an Overall Fault Status Guanghui Zhu, Student Member, IEEE, Lei Feng, Zhiwu Li, Fellow, IEEE, Naiqi Wu, Senior Member, IEEE

TABLE I DIAGNOSIS

 I RESULTS FOR OBSERVED WORD ω.

TABLE II DIAGNOSIS

 II RESULT AND RUNNING TIME FOR EXAMPLE 2.

  5 , t 6 , t 8 }, T e = {t 7 , t 9 , t 10 , t 12 }, T h = {t 16 }, T g = {t 14 , t 15 , t 17 }. The initial marking is M 0 = p 1 + αp 2 + βp 3 , where α and β are two variables denoting the numbers of tokens in p 2 and p 3 , respectively.

				t 4	p 7	t 8 (a)	p 11	t 12 (e)	p 15	t 16 (h)
		t 1	p 4
	p 1			t 5 (a)	p 8	t 9 (e)	p 12	f 2
		f 1	p 5	t 6 (a)	p 9	t 10 (e)	p 13	t 14 (g)	p 16	t 17 (g)
	p 2
	a	t 3 (a)	p 6	t 7 (e)	p 10	t 11	p 14	t 15 (g)
	p 3
	b

TABLE III COMPARISON

 III OF OUR APPROACH WITH THE ONE IN[START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF].

	event	a	e	a	e	g	• • •	e	g	g	g	g	g
	solving times I	3	3	5	5	5	• • •	5	5	5	3	3	3
	solving times II	8	22	27	39	41	• • • 5591 7512	10652	9988	9973 18583
	running time I (s)	0.02	0.01	0.02	0.04 0.04 • • •	1.07	1.10	1.21	1.73	1.98	2.23
	running time II (s)	0.03	0.05	0.08	0.10 0.09 • • • 23.52 32.63	51.80	49.97	44.57 87.89
	diagnosis result	[1 0

This work was supported in part by the National Natural Science Foundation of China under Grant Nos. 61873342 and 61703321, in part by the Science and Technology Development Fund, MSAR, under Grant Nos. 122/2017/A3 and 106/2016/A3, and in part by the 2017 Sino-French Cai Yuanpei Program.

APPENDIX A MODIFICATION DETAILS OF THE ALGORITHM IN

 [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF]The centralized fault diagnosis algorithm proposed in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] has a different output with the one in this paper and thus we need to modify it, keeping the key idea unchanged, to compare its efficiency with our approach. We first briefly recall the ILP problem defined in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] based on a sequence σ o ∈ T * o . Given a sequence of observable transitions denoted by σ o = t α1 t α2 • • • t α h , the ILP problem without objective function can be defined as

By specifying different objective functions to Eq. ( 3), we obtain three ILP models:

ILPP 5:

ILPP 6:

On the basis of these ILP problems, the Fault Detection Algorithm (FDA) proposed in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] (see Fig. 2 in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF]) is modified as Algorithm 2 which takes a transition sequence σ o ∈ T * o as input. At the same time, the Diagnoser Algorithm (DA) proposed in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF] (see Fig. 3 in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF]) is modified as Algorithm 3 which enumerates all sequences of observable transitions consistent with an observed word and repetitively calls Algorithm 2. The data shown in rows 3 and 5 of Table III is computed by executing Algorithm 3. The readers can inspect the souce code [START_REF] Zhu | Matlab programs for this paper[END_REF] for the details.

Note that the symbol ⊗ (not mentioned in [START_REF] Fanti | Fault detection by labeled Petri nets in centralized and distributed approaches[END_REF]) in Line 11 of Algorithm 3 is another contribution of this paper, which is a binary operation defined in Table IV and very appropriate to compute the combination of diagnosis results of transition sequences σ o 's consistent with an observed word ω. We will extend the approaches shown in [START_REF] Giua | Fault detection for discrete event systems using Petri nets with unobservable transitions[END_REF] and [START_REF] Basile | An efficient approach for online diagnosis of discrete event systems[END_REF] to the case of labeled Petri nets using this symbol in the subsequent research. We next show the formal definition of symbol ⊗ and prove its correctness.

Analogous to the labeling function λ, we define a new function τ : 3) has no feasible solution then 3 χ = false; return R, s and χ (terminate the procedure);

12 if R == 0 then 13 s = ∆(ω, F) = 0; 14 else if there exists r in vector R such that r == 2 then 15 s = ∆(ω, F) = 2; 16 else if there exists only r in vector R such that r == 1 then

the projection of σ ∈ T * on the set of observable transitions. For an observed word ω ∈ L E (N, M 0 ), we denote

the set of observable projections of transition sequences consistent with ω.

Proposition 3. Given a diagnostic net system N, M 0 , E, λ, F and an observed word ω ∈ E * , for

where k = |T (ω)|, {ν 1 , . . . , ν k } = T (ω), and ⊗ : {0, 1, 2} × {0, 1, 2} → {0, 1, 2} is a binary operation defined in Table IV.

Proof. For f ∈ T f ∪ {F} and ν ∈ T (ω), we can compute ∆(ν, f ) according to Algorithm 2. T (ω) denotes all sequences of observable transitions whose projections on E are ω.

Assume that there are only two items ν 1 and ν 2 in T (ω).

there is no fault f to occur in paths consistent with ν 1 and ν 2 according to Definition 2, and thus we have ∆(ω, f ) = 0.

On the other hand, if ∆ 1 = 0 and ∆ 2 = 2, there is no fault f in paths consistent with ν 1 but fault f must occur in all paths consistent with ν 2 . Thus, ∆(ω, f ) = 1 is true according to Definition 2. Following a similar procedure, we obtain Table IV for each f ∈ T f ∪{F} according to Definitions 2 and 3. If T (ω) contains more than two elements, Eq. ( 4) is readily verified.