Fault detection for discrete event systems using Petri nets with unobservable transitions

Abstract

In this paper we present a fault detection approach for discrete event systems using Petri nets. We assume that some of the transitions of the net are unobservable, including all those transitions that model faulty behaviors. Our diagnosis approach is based on the notions of basis marking and justification, that allow us to characterize the set of markings that are consistent with the actual observation, and the set of unobservable transitions whose firing enable it. This approach applies to all net systems whose unobservable subnet is acyclic. If the net system is also bounded the proposed approach may be significantly simplified by moving the most burdensome part of the procedure off-line, thanks to the construction of a graph, called the basis reachability graph.

Introduction

The diagnosis of discrete event systems is a research area that has received a lot of attention in the last years and has been motivated by the practical need of ensuring the correct and safe functioning of large complex systems. In the context of automata Sampath et al., 1995, Sampath et al., 1996 propose an approach to failure diagnosis where the system is modeled as a nondeterministic automaton in which the failures are treated as unobservable events. In Sampath et al. (1995) they provide a definition of diagnosability in the framework of formal languages and establish necessary and sufficient conditions for diagnosability. Moreover, in Sampath, Lafortune, and Teneketzis (1998) present an integrated approach to control and diagnosis. More specifically, the authors present an approach for the design of diagnosable systems by the appropriate design of the system’s controller and this approach is called active diagnosis. They formulate the active diagnosis problem as a supervisory control problem. In Debouk, Lafortune, and Teneketzis (2000) propose a coordinated decentralized architecture consisting of two local sites communicating with a coordinator that is responsible for diagnosing the failures occurring in the system. In Boel and van Schuppen (2002) address the problem of synthesizing communication protocols and failure diagnosis algorithms for decentralized failure diagnosis of DES with costly communication between diagnosers. In Zad, Kwong, and Wonham (2003) a state-based approach for on-line passive fault diagnosis is presented.

More recently, Petri net models have been used in the context of diagnosis due to their intrinsically distributed nature where the notions of state (i.e., marking) and action (i.e., transition) are local. This has often been an asset to reduce the computational complexity involved in solving a diagnosis problem. Among the first pioneering works dealing with Petri nets (PNs), we recall the approach of Prock that proposes an on-line technique for fault detection that is based on monitoring the number of tokens residing into $P$-invariants (Prock, 1991). In Genc and Lafortune (2007) propose a diagnoser on the basis of a modular approach that performs the diagnosis of faults in each module. In Benveniste, Fabre, Haar, and Jard (2003) present a net unfolding approach for designing an on-line asynchronous diagnoser. In Basile, Chiacchio, and De Tommasi (2009) present a diagnosis approach where the diagnoser is built on-line by defining and solving integer linear programming problems. In Dotoli, Fanti, and Mangini (2008), in order to avoid the redesign and the redefinition of the diagnoser when the structure of the system changes, Dotoli et al. propose a diagnoser that works on-line.

The main difference between the diagnosis approach presented here and the approaches cited above is the concept of basis marking. This concept allows us to represent the reachability space in a compact manner, i.e., our approach requires to enumerate only a subset of the reachability space. More specifically, in this paper we deal with the failure diagnosis of discrete event systems modeled by place/transition nets. We assume that faults are modeled by unobservable transitions, but there may also exist other transitions that represent legal behaviors and are unobservable as well. Thus we assume that the set of transitions can be partitioned as $T=T_o\cup T_u$ where $T_o$ is the set of observable transitions, and $T_u$ is the set of unobservable transitions. The set of fault transitions is denoted $T_f$ and satisfies $T_f\subseteq T_u$.

The set of fault transitions is further partitioned into $r$ subsets, $T_f^i,i=1,\dots ,r$, each one corresponding to a fault class. We are not interested in distinguishing among transitions within the same class, but we want to detect the class of faults that has occurred, or that may have occurred, given the observed behavior, i.e., the sequence of transitions that has been observed.

We associate two different sets to any observed word $w$, i.e., to any sequence of observed transitions:

• $\mathcal{L}\left(w\right)$ is the set containing all sequences of transitions that are consistent with $w$, i.e., the set of all possible firing sequences that produce observation $w$.

• $\mathcal{J}\left(w\right)$ is the set of justifications, i.e., the set of all minimal sequences of unobservable transitions (namely those sequences of unobservable transitions whose firing vector is minimal) interleaved with $w$ and whose firing enables $w$.¹

Note, in fact, that even if a word $w\in T_o^{\ast }$ is observed, in general the sequence $\sigma =w$ is not firable on the net, i.e., it cannot occur at the initial marking: it is necessary to interleave it with a sequence ${\sigma }_u$ of unobservable events to obtain a firable sequence $\sigma$ that produces the observed word $w$. $\mathcal{J}\left(w\right)$ is the set of all sequences ${\sigma }_u$ that are minimal, i.e., that have a minimal firing vector.

Now, given a fault class $T_f^i$ and an observation $w$, we distinguish the following four cases, each one corresponding to an increasing level of alarm (the diagnosis state varies from 0 to 3).

(0) No sequence in $\mathcal{L}\left(w\right)$ contains a transition in $T_f^i$, thus no fault in the $i$th class has occurred.

(1) Some transitions in $T_f^i$ may have fired but none of them was contained in a justification of $w$.

(2) Some transitions in $T_f^i$ may have fired and are contained in some of the justifications of $w$. However, not all justifications of $w$ contain transitions in $T_f^i$.

(3) All justifications of $w$ contain transitions in $T_f^i$, thus a fault must have occurred.

We provide a fault detection procedure that enables us to evaluate, for any observed word and any fault class, the corresponding diagnosis state. This procedure may be carried out by simply performing matrix multiplications and evaluating the feasibility of certain integer constraint sets. Such a procedure may be applied to all net systems whose unobservable subnet is acyclic. This assumption, that is analogous to the classical hypothesis in the theory of automata where no cycle of unobservable events can appear, allows us to: (a) study the reachability of the unobservable subnet with the state equation; (b) give an easy algorithm for the computation of the firing vectors relative to justifications. In particular, (a) implies that we can distinguish between the diagnosis states 0 and 1 in an efficient way.

The most burdensome part of the proposed procedure consists in evaluating the feasibility of a finite number of integer constraint sets. We show that in the case of bounded net systems this computation may be performed off-line. An oriented graph, that we call a basis reachability graph (BRG) may be constructed, that summarizes all the information required for diagnosis. Therefore, given any observable word $w$, for any fault class $T_f^i$ we may evaluate the corresponding diagnosis state, by simply looking at the BRG.

This paper builds on our previous results in Corona, Giua, and Seatzu (2007) where an observer for nets with silent transitions was designed under two structural assumptions, namely the unobservable subnet is acyclic and backward conflict-free. In such a case the set of markings that are consistent with the actual observation $\mathcal{C}\left(w\right)$, namely the set of markings that can be reached from the initial marking firing the observed word $w$ interleaved with sequences of unobservable transitions that enable $w$, may be characterized by a finite set of linear algebraic constraints whose structure is fixed, and does not depend on the length of the observed word $w$. In this paper we show that a finite linear algebraic characterization of the set $\mathcal{C}\left(w\right)$ may still be given, but the number of constraints is not fixed and depends in general on the word $w$. This requires a generalization of the notion of basis marking with respect to Corona et al. (2007). In particular, here we extend this notion to arbitrary nets. This makes a completely different characterization necessary in terms of new original notions such as justifications, minimal explanations. Moreover, no mention of the diagnosis problem was done in Corona et al. (2007).