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     

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.     

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.     

Fault diagnosis in discrete time hybrid systems - A case study

A method of analysing diagnosability of discrete time hybrid systems (DTHS), which are similar to the simple n-rate timed automata [R. Alur, C. Courcoubetis, T.A. Henzinger, P. Ho, Hybrid automata: an algorithmic approach to the specification and verification of hybrid systems, in: Hybrid Systems, LNCS 736, Springer Verlag, 1993, pp. 209-229], has been proposed. A state based fault modeling formalism is used. The properties of the DTHS model, under measurement limitations due to inadequacy or non-availability of sensors, are discussed. A definition of diagnosability for DTHS models has been adopted from the one proposed in [M. Sampath, R. Sengupta, S. Lafortune, K. Sinnamohideen, D. Teneketzis, Diagnosability of discrete-event systems, IEEE Transactions on Automatic Control 40 (9) (1995) 1555-1575] for discrete-event system (DES) models. Based on the measurement limited DTHS models, an algorithm for construction of a diagnoser is presented. It is next demonstrated through an example of a chemical reaction chamber that the diagnosability condition (over the diagnoser), which has been shown to be necessary and sufficient for DES diagnosability, fails to hold for many systems. This is so because the abstraction employed in DES modeling obliterates an important feature of the transitions namely fairness. Exploiting the explicit continuous dynamics of the DTHS models, the fairness of transitions is identified and used to demonstrate diagnosability. The diagnosability condition over the diagnoser is suitably modified to encompass the situations typified by the example.     

Access point selection in heterogeneous wireless networks using belief propagation

The next generation wireless network will be composed by various heterogenous wireless access networks,such as cellular network,worldwide interoperability for microwave access(WiMAX),wireless local area network(WLAN),etc.Different access networks cooperatively provide high-bandwidth connectivity with bandwidth guarantees.This paper proposes a utility-based access point selection scheme,which selects an accessible point for each user,such that the bandwidth requirement of each user is satisfied,and also the defined utility function is maximized.Due to the NP-complete nature of the problem,the existing proposals apply the greedy method to find a solution.We find that belief propagation is an efficient tool to solve this problem,and thus,we derive the same optimization objective in a new way,and then draw a factor graph representation which describes our combinatorial optimization problem.Afterwards,we develop the belief propagation algorithm,and show that our algorithm converges.Finally,we conduct numerical experiments to evaluate the convergency and accuracy of the belief propagation in load balancing problem.     

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.     

On‐the‐Fly and Incremental Technique for Fault Diagnosis of Discrete Event Systems Modeled by Labeled Petri Nets

In this paper, we develop an on‐the‐fly and incremental technique for fault diagnosis of discrete event systems modeled by labeled Petri nets, in order to tackle the combinatorial explosion problem. K‐diagnosability, diagnosability, K_min (the minimum K ensuring diagnosability) and on‐line diagnosis are solved on the basis of the on‐the‐fly and incremental building of two structures, called respectively fault marking graph and fault marking set graph, in parallel. We build on existing results, namely those establishing necessary and sufficient conditions for diagnosability, but we bring mechanisms to make the checking of such conditions potentially more efficient. We show that, in general, analyzing or even building the whole reachability graph is unnecessary to analyze diagnosability and build an on‐line diagnoser. Our technique was implemented in a prototype tool called OF‐PENDA, and a railway level crossing benchmark is used to make a comparative discussion pertaining to efficiency in terms of time and memory relative to some existing approaches.     

离散事件系统基于模式的安全故障诊断

基于模式的故障诊断方法能将触发系统故障的事件串诊断出来,但在诊断期间系统仍然可能执行被禁止的不安全操作.为此,提出了一种离散事件系统基于S型和T型模式的安全诊断方法.先对离散事件系统基于模式的安全可诊断性进行形式化,再通过构造非法语言识别器和安全诊断器对系统发生的故障模式实施安全诊断,最后分别得到了一个关于S型和T型模式的系统安全可诊断性的充分必要条件,实现了离散事件系统基于模式的安全故障诊断.     

含大时滞和噪声的网络化控制系统的最优故障诊断

研究含大测量时滞和噪声的网络控制系统(Networked control systems, NCS)的故障诊断问题, 提出一种新的基于无时滞转换方法的最优故障诊断器的设计方法. 该方法首先构造一个隐含故障状态的增广系统, 并利用无时滞转换方法将含有测量时滞的网络控制系统转换为无时滞系统. 然后给出了故障的可诊断性判据, 并利用对偶原理将最优故障诊断器的设计问题转换为状态反馈控制器设计问题. 最后, 通过构造一种满足二次型性能指标的最优故障诊断器, 实现了故障的实时诊断. 仿真示例验证了该方法的可行性和有效性.     

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.     

Designing Distributed Diagnosers for Complex Continuous Systems

Wear and tear from sustained operations cause systems to degrade and develop faults. Online fault diagnosis schemes are necessary to ensure safe operation and avoid catastrophic situations, but centralized diagnosis approaches have large memory and communication requirements, scale poorly, and create single points of failure. To overcome these problems, we propose an online, distributed, model-based diagnosis scheme for isolating abrupt faults in large continuous systems. This paper presents two algorithms for designing the local diagnosers and analyzes their time and space complexity. The first algorithm assumes the subsystem structure is known and constructs a local diagnoser for each subsystem. The second algorithm creates the partition structure and local diagnosers simultaneously. We demonstrate the effectiveness of our approach by applying it to the Advanced Water Recovery System developed at the NASA Johnson Space Center.     

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.     

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.

     

Verification of robust diagnosability for partially observed discrete event systems

In this paper, we study robust failure diagnosis of discrete event systems. Given a set of possible models, each of which has its own nonfailure specification, we consider the existence of a single diagnoser such that, for all possible models, it detects any occurrence of a failure within a uniformly bounded number of steps. We call such a diagnoser a robust diagnoser. We introduce a notion of robust diagnosability, and prove that it serves as a necessary and sufficient condition for the existence of a robust diagnoser. We then present an algorithm for verifying the robust diagnosability condition.     

Centralized Modular Diagnosis and the Phenomenon of Coupling

This paper studies modular decomposition as an approach for failure diagnosis based on Discrete Event Systems. This paper also analyses the problem of coupling produced in the implementation of centralized modular diagnosers, as coupled diagnosers cannot carry out their own diagnosis task, when there is a failure in another subsystem sharing a common energy or material flow. In addition, we propose a method to avoid diagnoser coupling, by means of decoupling functions using non-local information with respect to the coupled diagnoser and generated in the diagnoser where the failure has been isolated.     

Resilient Fault Diagnosis Under Imperfect Observations–A Need for Industry 4.0 Era

In smart industrial systems, in many cases, a fault can be captured as an event to represent the distinct nature of subsequent changes. Event-based fault diagnosis techniques are capable model-based methods for diagnosing faults from a sequence of observable events executed by the system under diagnosis. Most event-based diagnosis techniques rely on perfect observations of observable events. However, in practice, it is common to miss an observable event due to a problem in sensor-readings or communication/transmission channels. This paper develops a fault diagnosis tool, referred to as diagnoser, which can robustly detect, locate, and isolate occurred faults. The developed diagnoser is resilient against missed observations. A missed observation is detected from its successive sequence of events. Upon detecting a missed observation, the developed diagnoser automatically resets and then, asynchronously resumes the diagnosis process. This is achieved solely based on post-reset/activation observations and without interrupting the performance of the system under diagnosis. New concepts of asynchronous detectability and asynchronous diagnosability are introduced. It is shown that if asynchronous detectability and asynchronous diagnosability hold, the proposed diagnoser is capable of diagnosing occurred faults under imperfect observations. The proposed technique is applied to diagnose faults in a manufacturing process. Illustrative examples are provided to explain the details of the proposed algorithm. The result paves the way towards fostering resilient cyber-physical systems in Industry 4.0 context.      

Sensor placement for diagnosability

The concept of diagnostic accuracy is examined and redefined to support specific criteria for sensor placement. If the correctness of diagnoser operation is assumed, then any failure to diagnose accurately must be attributable to an inadequacy of sensor data. Inaccuracy in diagnoses can be expressed solely in terms of additional candidates whose faults cannot be ruled out. With ambiguity as the determiner of the quality of a diagnosis, user-defined diagnosability requirements can be expressed in terms of the types and instances of components which are permissible exceptions to perfect diagnosis. This requires a working diagnoser and a simulator, along with sets of system configurations, component fault modes, potentially measurable parameters, and uniqueness requirements for fault isolation. From these, the diagnosability of individual components can be determined for a particular attached subset of the available sensors. An optimum sensor assignment is one that satisfies the most requirements with a fixed number of sensors or, conversely, that minimizes the sensor requirements to achieve a given threshold of diagnosability. The considerable complexity of this search is reduced by exploiting sensor set minimality, structural knowledge, and diagnosis-free extension to the system level. Global optimization and sensor allocation do not add to the number of diagnoses required for diagnosability analysis. Finally, corrective measures are discussed for use when residual costs remain too high, or when redundancy is too low.In support of NASA's Marshall Space Flight Center and the Space Station Freedom Advanced Development Program under NASA contract number NAS 8-37200.     

赋时离散事件系统的安全诊断

针对一类计时或非计时自动机模型,研究其赋时离散事件系统(TDES)故障诊断的安全性问题.首先对TDES的安全可诊断性进行形式化;然后通过构造一个非法语言识别器对被禁止危险操作序列进行识别,在此基础上构建一个安全诊断器,提出一种基于安全诊断器的安全诊断方法,并得到一个关于TDES安全可诊断性的充分必要条件,从而实现TDES的安全故障诊断.     

Abstraction-based verification of codiagnosability for discrete event systems

In this paper, we investigate the verification of codiagnosability for discrete event systems (DES). That is, it is desired to ascertain if the occurrence of system faults can be detected based on the information of multiple local sites that partially observe the overall DES. As an improvement of existing codiagnosability tests that resort to the original DES with a potentially computationally infeasible state space, we propose a method that employs an abstracted system model on a smaller state space for the codiagnosability verification. Furthermore, we show that this abstraction can be computed without explicitly evaluating the state space of the original model in the practical case where the DES is composed of multiple subsystems.