Polynomial-time verification of diagnosability of fuzzy discrete event systems

A fuzzy approach to perform diagnosis of fuzzy discrete event systems(FDESs)is proposed by constructing diagnosers,which may more effectively cope with the problems of vagueness and fuzziness arising from failure diagnosis of fuzzy systems.However,the complexity of constructing this kind of diagnosers is exponential in the state space and the number of fuzzy events of the system.In this paper,we present an algorithm for verifying the diagnosability of FDESs based on the construction of a nondeterministic automaton called F-verifier instead of diagnosers.Both the construction of F-verifiers and the verification of diagnosability of FDESs can be realized with a polynomial-time complexity.     

Diagnosability of Fuzzy Discrete-Event Systems: A Fuzzy Approach

In order to more effectively cope with the real-world problems of vagueness, fuzzy discrete-event systems (FDESs) were proposed by Lin and Ying recently. Then we and Cao and Ying investigated the supervisory control of FDESs independently. In this paper, we are concerned with another important issue of FDESs, the failure diagnosis. More specifically: (1) we propose a ldquofuzzy diagnosabilityrdquo approach by introducing a fuzzy diagnosability function to characterize the diagnosability degree, which takes values in the interval [0,1] rather than { 0,1}; (2) based on the observability of events, we formalize the construction of the diagnosers that are used to perform fuzzy diagnosis; (3) a number of basic properties of the diagnosers are investigated. In particular, we present a necessary and sufficient condition for failure diagnosis of FDESs. Our results generalize the important consequences of the diagnosability for crisp discrete-event systems (DESs) introduced by Sampath et al. The newly proposed approach allows us to deal with the problem of diagnosability for both crisp DESs and FDESs; (4) in addition, a method for checking the fuzzy diagnosability for FDESs is proposed. Also, some examples are provided to illustrate the application of the diagnosability of FDESs.     

Diagnosability of fuzzy discrete event systems

In this paper, discrete event systems (DESs) are reformulated as fuzzy discrete event systems (FDESs) and fuzzy discrete event dynamical systems (FDEDSs). These frameworks include fuzzy states, events and IF-THEN rules. In these frameworks, all events occur at the same time with different membership degrees. Fuzzy states and events have been introduced to describe uncertainties that occur often in practical problems, such as fault diagnosis applications. To measure a diagnoser’s fault discrimination ability, a fuzzy diagnosability degree is proposed. If the diagnosability of the degree of the system yields one a diagnoser can be implemented to identify all possible fault types related to a system. For any degree less than one, researchers should not devote their time to distinguish all possible fault types correctly. Thus, two different diagnosability definitions FDEDS and FDES are introduced. Due to the specialized fuzzy rule-base embedded in the FDEDS, it is capable of representing a class of non-linear dynamic system. Computationally speaking, the framework of diagnosability of the FDEDS is structurally similar to the framework of diagnosability of a non-linear system. The crisp DES diagnosability has been turned into the term fuzzy diagnosability for the FDES. The newly proposed diagnosability definition allows us to define a degree of diagnosability in a class of non-linear systems. In addition, a simple fuzzy diagnosability checking method is introduced and some numerical examples are provided to illustrate this theoretical development. Finally, the potential applications of the proposed method are discussed.     

Design of light weight exact discrete event system diagnosers using measurement limitation: case study of electronic fuel injection system

Employing a state-based Discrete Event System (DES) modelling framework, this paper proposes a new fault diagnosis approach called measurement limitation-based abstract DES diagnosis (MLAD), which attempts to reduce state space complexity of the diagnosis process while simultaneously preserving full diagnosability. The MLAD approach carefully applies a set of distinct measurement limitation operations on the state variables of the original DES model based on fault compartmentalisation to obtain separate behaviourally abstracted DES models and corresponding abstract diagnosers with far lower state spaces. The set of measurement limitation operations are so designed that although, any single abstract diagnoser may compromise diagnosability in seclusion, the additive combination of all diagnosers running in parallel always ensures complete diagnosability. Effective measurement limitation also ensures that the combined state space of the abstract diagnosers is much lower than that of the single full diagnoser that may be derived from the original DES model. As a case study, we have employed MLAD to incorporate failure diagnosability in a practical electronic fuel injection system. Evaluations on standard practical benchmarks show that MLAD achieves significant reduction in state space as compared to conventional monolithic full diagnosis approaches.     

具有多项式时间复杂性的离散事件系统安全诊断

离散事件系统的故障诊断能将已发生的不可观故障事件及时诊断出来,但往往容易忽略故障诊断期间系统的安全性.为解决这一问题,提出了一种具有多项式时间复杂性的安全故障诊断方法.先对离散事件系统的安全可诊断性进行了形式化,再通过构造一个非法语言识别器对系统被禁止操作序列进行识别,并在此基础上构建了一个对系统实施安全诊断的安全验证器,得到了一个关于离散事件系统安全可诊断性的充分必要条件,实现了对系统的安全故障诊断.同时,通过对安全验证器的构建与安全可诊断性的判定的复杂性分析,得到了该安全故障诊断方法可在多项式时间内实现等结论.     

Diagnosability of discrete-event systems

Fault detection and isolation is a crucial and challenging task in the automatic control of large complex systems. We propose a discrete-event system (DES) approach to the problem of failure diagnosis. We introduce two related notions of diagnosability of DES's in the framework of formal languages and compare diagnosability with the related notions of observability and invertibility. We present a systematic procedure for detection and isolation of failure events using diagnosers and provide necessary and sufficient conditions for a language to be diagnosable. The diagnoser performs diagnostics using online observations of the system behavior; it is also used to state and verify off-line the necessary and sufficient conditions for diagnosability. These conditions are stated on the diagnoser or variations thereof. The approach to failure diagnosis presented in this paper is applicable to systems that fall naturally in the class of DES's; moreover, for the purpose of diagnosis, most continuous variable dynamic systems can be viewed as DES's at a higher level of abstraction     

A polynomial algorithm for testing diagnosability of discrete-eventsystems

Failure diagnosis in large and complex systems is a critical task. In the realm of discrete-event systems, Sampath et al. (1995) proposed a language based failure diagnosis approach. They introduced the diagnosability for discrete-event systems and gave a method for testing the diagnosability by first constructing a diagnoser for the system. The complexity of this method of testing diagnosability is exponential in the number of states of the system and doubly exponential in the number of failure types. We give an algorithm for testing diagnosability that does not construct a diagnoser for the system, and its complexity is of fourth order in the number of states of the system and linear in the number of the failure types     

Diagnosability of Discrete Event Systems with Modular Structure

The diagnosis of unobservable faults in large and complex discrete event systems modeled by parallel composition of automata is considered. A modular approach is developed for diagnosing such systems. The notion of modular diagnosability is introduced and the corresponding necessary and sufficient conditions to ensure it are presented. The verification of modular diagnosability is performed by a new algorithm that incrementally exploits the modular structure of the system to save on computational effort. The correctness of the algorithm is proved. Online diagnosis of modularly diagnosable systems is achieved using only local diagnosers. *Olivier Contant is now working at Microsoft Corporation.     

Predictability of event occurrences in partially-observed discrete-event systems

This paper studies the problem of predicting occurrences of a significant event in a partially-observed discrete-event system. The predictability of occurrences of an event in a system is defined in the context of formal languages. The predictability of a language is a stronger condition than the diagnosability of the language. Two necessary and sufficient conditions for predictability of occurrences of an event in systems modeled by regular languages are presented. Both conditions can be algorithmically tested. The first condition employs diagnosers. The second condition employs verifiers and results in a polynomial-time (in the number of states) complexity test for verification of predictability. When predictability holds, diagnosers can be used online to predict the significant event.     

Distributed Diagnosis Under Bounded-Delay Communication of Immediately Forwarded Local Observations

We study distributed failure diagnosis under a -bounded communication delay, where each local site transmits its observations to other sites immediately after each observation and the transmitted observation is received within at most more event executions of the plant. A notion of diagnosability is introduced so that any failure can be diagnosed within a bounded delay of its occurrence by one of the local sites using its own observations and the -bounded delayed observations received from other local sites. The local sites communicate among each other using an ldquoimmediate observation passing (iop)rdquo protocol, forwarding any observation immediately up on its occurrence. We construct models for the -bounded communication delay and use them to extend the system and nonfault specification models for capturing the effect of bounded-delay communication. By using the extended system and specification models, the distributed diagnosis problem under the immediate observation passing protocol is then converted to a decentralized diagnosis problem of our previous work, where the results are applied for verifying diagnosability and for synthesizing local diagnosers. Methods by which complexity of testing diagnosability and of online diagnosis can be reduced are presented. Finally, we compare the notions of diagnosability, codiagnosability, and diagnosability.     

Decentralized fault diagnosis approach without a global model for fault diagnosis of discrete event systems

Diagnosability property ensures that a predefined set of faults are diagnosable by a centralized diagnoser built using a global model of the system, while co-diagnosability guarantees that these faults are diagnosed in decentralized manner using a set of local diagnosers. A fault must be diagnosed by at least one local diagnoser by using its proper local observation of the system. The aim of using decentralized diagnosis approaches is to overcome the space complexity and weak robustness of centralized diagnosis approaches while at the same time preserving the diagnostic capability of a centralized diagnosis. However, co-diagnosability property is stronger than diagnosability property. If a system is co-diagnosable, then it is diagnosable, while a diagnosable system does not ensure that it is co-diagnosable. Therefore, the challenge of decentralized diagnosis approaches is to perform local diagnosis and to verify that it is equivalent to the centralized one without the need for a global model. In this paper, an approach is proposed to obtain co-diagnosable decentralized diagnosis structure of discrete event systems without the use of a global model. This approach is based on the synchronization of local diagnosis decisions in order to solve the ambiguity between local diagnosers. This synchronization allows obtaining local diagnosis equivalent to the global one without the use of a global model.     

From classic observability to a simple fuzzy observability for fuzzy discrete-event systems

In order to determine uncertainties from restricted available information, fuzzy discrete-event systems (FDESs), or fuzzy discrete-event dynamic systems (FDEDSs), were recently proposed. These frameworks include fuzzy states and events occurring simultaneously with different membership degrees. Fuzzy states and events have been used to describe uncertainties that occur often in practical problems, such as treatment planning for HIV/AIDS patients, sensory information processing for robotic control, and fault diagnosis problems. In order to measure information associated with FDESs or FDEDSs, the classical discrete event system (DES) observability has been turned into fuzzy observability for FDESs or FDEDSs. The newly proposed method allows ease of defining degrees of observability so that uncertainties in FDESs or FDEDSs can be dealt with effectively. This gives an opportunity to design better decision-making systems. To calculate the observability degree, a simple fuzzy observability checking method is introduced, and two examples are elaborated upon to illustrate the presented method. Finally, the newly proposed method is tested on a heating, ventilating, and air-conditioning (HVAC) system.     

A new algorithm for testing diagnosability of fuzzy discrete event systems

Failure diagnosis and detection of fuzzy discrete event systems play a significant role in the study of complex systems. In this paper, we investigate the diagnosability of fuzzy discrete event systems by proposing a new algorithm based on the concept of undistinguishable strings. Moreover, a necessary and sufficient condition for fuzzy diagnosability is obtained in terms of certain properties of the diagnoser, which is constructed with respect to the minimal observable event. The computing process to check the diagnosability of fuzzy DESs and some examples serving to illuminate the applications are developed and described.     

Robust diagnosis of discrete event systems against intermittent loss of observations

In the usual approaches to fault diagnosis of discrete event systems it is assumed that not only all sensors work properly but also all information reported by sensors always reaches the diagnoser. Any bad sensor operation or communication failure between sensors and the diagnoser can be regarded as loss of observations of events initially assumed as observable. In such situations, it may be possible that either the diagnoser stands still or report some wrong information regarding the fault occurrence. In this paper we assume that intermittent loss of observations may occur and we propose an automaton model based on a new language operation (language dilation) that takes it into account. We refer to this problem as robust diagnosability against intermittent loss of observations (or simply robust diagnosability, where the context allows). We present a necessary and sufficient condition for robust diagnosability in terms of the language generated by the original automaton and propose two tests for robust language diagnosability, one that deploys diagnosers and another one that uses verifiers. We also extend the results to robust codiagnosability against intermittent loss of observations.     

On Decidability of Distributed Diagnosis Under Unbounded-Delay Communication

In this note we show that the problem of distributed diagnosis under unbounded communication delay is decidable when there is no inferencing involved among the diagnosers. The notion of joint_infin-diagnosability is introduced to capture the diagnosability property in this setting. We show the equivalence of joint_infin-diagnosability and codiagnosability, which captures the diagnosability property in the decentralized setting (i.e., one involving no communication). Thus the decidability result follows from the decidability of codiagnosability established in a previous paper. We also show that the property of joint_infin-diagnosability is stronger than decentralized-diagnosability introduced in a previous paper     

Sufficient Structural Conditions for Diagnosability and Heuristic Diagnoser Design in Timed Continuous Petri Nets

This work is concerned with a structural characterization of the diagnosability property in Timed Continuous Petri Nets (TCPNs) systems under infinite server semantics. Regarding this problem, three novel results are presented. The first one is the introduction of structural sufficient conditions for diagnosability in TCPNs, which are based on the concepts of relative degree, system distinguishability, and parameter identification. To this aim, the concept of a simple directed path from other works is extended to diagnosable directed paths. These new paths include attribution-places, pre-join-places and post-join-places, which allows to deal with multiple non-concurrent tokens-leak faults, and enlarging the class of systems that can be analyzed. Based on these structural conditions, a novel methodology to place a reduced number of sensors that guarantees the net diagnosability is proposed. Finally, a diagnoser based on a modified Differential Evolution algorithm is presented, which introduces individual searching sets in orthogonal spaces to diagnose (detect, locate, and identify) faults when an error is detected, avoiding the use of a bank of diagnosers of other approaches. The effectiveness and applicability of the main results are illustrated through an illustrative example.

     

模糊离散事件系统基于验证器的模式故障诊断

针对模糊系统在运行过程中可能出现由多个事件触发的故障,研究模糊离散事件系统模式故障的诊断问题,提出一种基于验证器的模式故障诊断方法.先对模糊离散事件系统中最常见的模式故障,引入S类型模式故障和T类型模式故障两个概念,再分别对模糊离散事件系统的S类型和T类型模式故障的可诊断性进行形式化.为验证模糊系统模式故障的可诊断性,构造一个验证器自动机,并得到一个关于模糊离散事件系统模式故障可诊断性的充分必要条件,实现对模糊系统模式故障的诊断.     

Codiagnosability of networked discrete event systems subject to communication delays and intermittent loss of observation

Failure diagnosis is a crucial task in modern industrial systems, and several works in the literature address this problem by modeling the system as a Discrete-Event System (DES). Most of them assume perfect communication between sensors and diagnosers, i.e., no loss of observation of events, or event communication delays between the measurement sites and the diagnosers. However, industrial systems can be large and physically distributed, in which cases, communication networks are used to provide an efficient way to establish communication between devices. In diagnosis systems, the use of networks can introduce delays in the communication of event occurrences from measurement sites to the local diagnosers, leading to an incorrect observation of the order of occurrence of events generated by the system and, as a consequence, to an incorrect diagnosis decision by the local diagnoser. In this paper, we address the problem of decentralized diagnosis of networked Discrete-Event Systems subject to event communication delays, and we introduce the definition of network codiagnosability of the language generated by a DES subject to both event communication delays and intermittent loss of observation, and present necessary and sufficient conditions for a language to be network codiagnosable, for short. We also propose an algorithm to verify this property.     

Diagnosis of Intermittent Faults

The diagnosis of intermittent faults in dynamic systems modeled as discrete event systems is considered. In many systems, faulty behavior often occurs intermittently, with fault events followed by corresponding reset events for these faults, followed by new occurrences of fault events, and so forth. Since these events are usually unobservable, it is necessary to develop diagnostic methodologies for intermittent faults. Prior methodologies for detection and isolation of permanent faults are no longer adequate in the context of intermittent faults, since they do not account explicitly for the dynamic behavior of these faults. This paper addresses this issue by: (i) proposing a modeling methodology for discrete event systems with intermittent faults; (ii) introducing new notions of diagnosability associated with fault and reset events; and (iii) developing necessary and sufficient conditions, in terms of the system model and the set of observable events, for these notions of diagnosability. The definitions of diagnosability are complementary and capture desired objectives regarding the detection and identification of faults, resets, and the current system status (namely, is the fault present or absent). The associated necessary and sufficient conditions are based upon the technique of diagnosers introduced in earlier work, albeit the structure of the diagnosers needs to be enhanced to capture the dynamic nature of faults in the system model. The diagnosability conditions are verifiable in polynomial time in the number of states of the diagnosers.