A Polynomial Algorithm for Diagnosability Analysis of Discrete Event Systems

Introduction

Detection of faults and their isolation by fault diagnosis systems is of principal importance for complex systems composed of multiple components whose safety and reliability need to be ensured. The failure diagnosis problem has received considerable attention in the discrete event system (DES) framework. Fault diagnosis has been firstly studied using automata, and then has also been addressed by Petri nets approaches. Diagnosis of DESs uses the observable inputs and outputs of the system under supervision to detect and isolate the source of failure using diagnosers. The diagnoser is a finite state machine (FSM) built from the FSM model of the system. Figure 1 depicts the principle of the diagnoser construction. The diagnoser performs diagnostics when it observes the behavior of the system. Figure 2 illustrates the use of a diagnoser to perform the diagnostic of a DES. However, the exactness of the diagnoser depends on the diagnosability of the system, i.e. the property that every fault can be correctly detected from the observable events of the system after its occurrence no later than a bounded number of events.

Figure 1.

Principle of the diagnoser construction

Figure 2.

The DES diagnosis approach

The exhaustive literature for DES diagnosis can be classified as centralized, decentralized or distributed according to the architectures for diagnosis. The centralized approach (e.g. Lin, 1994; Sampath et al., 1995; Zad et al., 2003; Simeu-Abazi et al., 2010; Gascard & Simeu-Abazi, 2013) requires the construction of a global model of the behavior of the system as well as a global diagnoser. The decentralized and distributed approaches require the construction of a local diagnoser at each component. Each local diagnoser has a partial observation of the whole system to be diagnosed.

In the distributed diagnosis approach (e.g. Baroni et al., 1999; Benveniste et al., 2003; Jiroveanu & Boel, 2006; Genc & Lafortune, 2007; Aramburo-Liz et al., 2008), the local diagnosers communicate with each other. In a decentralized diagnosis architecture (e.g. Pencolé & Cordier, 2005; Qiu & Kumar, 2006; Contant et al., 2006; Wang et al., 2007), each local diagnoser makes local diagnoses without communicating with the other local diagnosers. The local diagnoses made by the various local diagnosers may or may not be fused in order to issue a global diagnosis.

In this paper, we study the diagnosability problem of DESs modeled as automata in the context of centralized systems. We give a didactic presentation of an algorithm for checking diagnosability that requires polynomial time in the number of states of the system (Gascard et al., 2014). Our complexity is the same of Yoo and Lafortune (2002) in the worst-case but is smaller in the average case.

The paper is organized as follows. First we introduce the preliminaries and give the formal definition of diagnosability of DES. Next section presents the related works concerning the diagnosability analysis of DESs in the centralized framework. Then we present our main result which is a check for diagnosability and illustrate the obtained result before the concluding remarks.

Preliminaries

In this section we present our model of untimed discrete-event system and the notion of diagnosability of DESs.