A Polynomial Algorithm for Diagnosability Analysis of Discrete Event Systems

A Polynomial Algorithm for Diagnosability Analysis of Discrete Event Systems

Eric Gascard (G-SCOP Laboratory, Grenoble Alpes University, Grenoble, France), Zineb Simeu-Abazi (G-SCOP Laboratory, Grenoble Alpes University, Grenoble, France), and Bérangère Suiphon (G-SCOP Laboratory, Grenoble Alpes University, Grenoble, France)
DOI: 10.4018/IJARAS.2015070101
OnDemand PDF Download:
No Current Special Offers


The paper deals with the definition of procedure that enables one to determine, for a given plant, if all faults can be detected and located after a finite sequence of observable events. More formally, the diagnosability is 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. In this paper, the diagnosability problem of Discrete Event Systems (DESs) is studied. As modeling tool, finite-state automaton in an event-based framework is used. A necessary and sufficient condition of diagnosability of such systems is proposed. The results proposed in this paper allow checking the diagnosability of discrete event systems in an efficient way, i.e. in polynomial time.
Article Preview


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.



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

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 7: 1 Issue (2016)
Volume 6: 2 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing