Diagnosability of fair discrete event systems

Failure diagnosability has been widely studied using discrete event system (DES) models. It is, however, shown in this work by means of a counterexample that the diagnosability condition, which has been shown to be necessary and sufficient in the DES context, fails to hold for many real‐world hybrid systems. This is because the abstraction employed in formulating the DES models obliterates the continuous dynamics. In the present work, a new failure diagnosability mechanism has been developed for discrete time hybrid system (DTHS) models to alleviate this problem. A new diagnosability condition is proposed and its necessity and sufficiency with respect to the diagnosability definition are established formally. Finally, the method of A‐diagnosability, which can also be used to circumvent this problem and which needs additional probabilistic information for diagnosability analysis, has been shown to have a higher computational complexity than the DTHS model based method proposed in this paper. Further, it is also highlighted that the DTHS model based diagnosability analysis technique is capable of diagnosing faults that degrade the temporal performance of the system, which cannot be handled by the A‐diagnosability analysis mechanism. Copyright © 2008 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

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.     

基于不确定观测下离散事件系统可诊断性的研究

在实际应用系统中,由于传感器故障、传感器限制和网络中的数据包丢失等原因,事件的可观测值变得不确定,使得观测系统行为变得尤为复杂。针对离散事件系统中,同个事件串可能有多个观测值以及不同状态下同个事件观测值也可能不同的问题,提出一种不确定观测下故障诊断验证的方法。首先对不确定观测的离散事件系统的可诊断性进行形式化,然后构建出用于上述故障诊断验证的验证器;基于验证器提出了系统基于不确定观测下可诊断的充要条件及验证算法;最后,实例说明不确定观测下故障诊断验证算法的应用。与现有研究相比,提出的方法对故障事件的观测值没有约束,可以为0个或多个观测值,使此方法应用的场景更为广泛。     

Diagnosability of discrete event systems subject to permanent sensor failures

This paper considers a failure diagnosis problem for discrete event systems subject to permanent sensor failures. A notion of diagnosability subject to permanent sensor failures is introduced with respect to a certain nondeterministic observation mask. For its verification, an aggregated Mealy automaton with a deterministic and state-dependent observation mask is defined. It is shown that the diagnosability of the aggregated Mealy automaton is equivalent to the diagnosability of the original system subject to permanent sensor failures. Then, a method for verifying the diagnosability of the aggregated Mealy automaton is presented. Moreover, the delay bound within which the occurrence of any failure string can be detected subject to permanent sensor failures is computed.     

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.     

State observability and condition observability for a class of interacting discrete event systems

This paper introduces the concepts of state observability and condition observability for condition systems, a class of systems composed of discrete state components which interact via discrete binary signals called conditions. Given a set of externally observed conditions, state observability implies that the state of the system can be determined from the observations, and condition observability implies that all unobserved input and output conditions of the system can be determined from the observations. In this paper, we present a class of systems which is state observable and condition observable. We present a method to synthesize an observer system to provide state and condition signal estimates for a single component subsystem.     

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 discrete event systems and its applications

As man-made systems become more and more complex, diagnostics of component failures is no longer an easy task that can be performed based on experience and intuition. Therefore, it is important to develop a systematic approach to diagnostic problems. Diagnostics can be done either on-line or off-line. By on-line diagnostics, we mean diagnostics performed while the system to be diagnosed is in normal operation. On the other hand, in off-line diagnostics, the system is not in normal operation. We will study both on-line and off-line diagnostics in this paper and identify main features and differences of these two types of diagnostics. We will also introduce the concept of diagnosability and study its properties, all in the framework of discrete event systems. This study is motivated by diagnostic problems in the automotive industry and we will emphasize its applications.     

离散事件系统N步稳定性分析

讨论基于自动机/形式语言模型的离散事件系统(DES)稳定性问题,引入了确定性离散事件系统N步稳定性定义,并得到了稳定性的判据定理,推导了具体的算法实现。该算法具有多项式复杂度。     

On the static output feedback stabilisation of discrete event dynamic systems based upon the approach of semi-tensor product of matrices

In this paper, the static output feedback stabilisation of discrete event dynamic systems (DEDSs) is investigated via the semi-tensor product (STP) of matrices. Firstly, the dynamics of DEDSs modelled by deterministic Moore-type finite automata are converted into an matrix expression in the STP frame. Secondly, necessary and sufficient conditions for the existence of a static output feedback control pattern, stabilising the controlled discrete event dynamic systems to some equilibrium point, are given, and constructive algorithms to seek the static output feedback control pattern including an effective specific solution algorithm and an analytic solution algorithm are proposed. Thirdly, the equilibrium-based static output feedback stabilisation of DEDSs is extended to the set-based static output feedback stabilisation and necessary and sufficient conditions and constructive algorithms to seek the corresponding control pattern are provided. Finally, some examples are presented to illustrate the effectiveness of the proposed approach.     

Diagnosability Analysis of a Class of Hierarchical State Machines

This paper addresses the problem of fault detection and isolation for a particular class of discrete event dynamical systems called hierarchical finite state machines (HFSMs). A new version of the property of diagnosability for discrete event systems tailored to HFSMs is introduced. This notion, called L₁-diagnosability, captures the possibility of detecting an unobservable fault event using only high level observations of the behavior of an HFSM. Algorithms for testing L₁-diagnosability are presented. In addition, new methodologies are presented for studying the diagnosability properties of HFSMs that are not L₁-diagnosable. These methodologies avoid the complete expansion of an HFSM into its corresponding flat automaton by focusing the expansion on problematic indeterminate cycles only in the associated extended diagnoser.

An optimal effective controller for discrete event systems

An approach to the online synthesis of an optimal effective controller for discrete event systems is presented. The optimal effective controller can achieve the prescribed (cumulative) effectiveness measure while minimizing the total cost incurred for the execution of events. This approach is constructed over a generalized control framework for automata‐based discrete event systems, which allows event enforcement in addition to the (original) event disablement/enablement as the control mechanism. The optimal effective control policy generated by this approach is proved to be the least restrictive among all the possible optimal effective control policies for the given online expansion tree of the system behavior. Copyright © 2008 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Formal approach to fault diagnosis in distributed discrete event systems with OBDD

In this paper, we study the fault diagnosis problem for distributed discrete event systems. The model assumes that the system is composed of distributed components which are modeled in labeled Petri nets and interact with each other via sets of common resources (places). Further, a component’s own access to a common resource is an observable event. Based on the diagnoser approach proposed by Sampath et al., a distributed fault diagnosis algorithm with communication is presented. The distributed algorithm assumes that the local diagnosis process can exchange messages upon the occurrence of observable events. We prove the distributed diagnosis algorithm is correct in the sense that it recovers the same diagnostic information as the centralized diagnosis algorithm. Furthermore, we introduce the ordered binary decision diagrams (OBDD) in order to manage the state explosion problem in state estimation of the system.     

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.     

On optimal control of a class of partially observed discrete event systems

We are interested in a new class of optimal control problems for discrete event systems. We adopt the formalism of supervisory control theory (Proc. IEEE 77(1) (1989) 81) and model the system as a finite state machine (FSM). Our control problem is characterized by the presence of uncontrollable as well as unobservable events, the notion of occurrence and control costs for events and a worst-case objective function. We first derive an observer for the partially unobservable FSM, which allows us to construct an approximation of the unobservable trajectory costs. We then define the performance measure on this observer rather than on the original FSM itself. We then use the algorithm presented in Sengupta and Lafortune (SIAM J. Control Optim. 36(2) (1998)) to synthesize an optimal submachine of the C-observer. This submachine leads to the desired supervisor for the system.     

The concept of residuals for fault localization in discrete event systems

In this paper an approach for fault localization in closed-loop Discrete Event Systems is proposed. The presented diagnosis method allows fault localization using a fault-free system model to describe the expected system behavior. Via a systematic comparison of the observed and the expected behavior, a fault can be detected and a set of fault candidates is determined. Inspired by residuals known from diagnosis in continuous systems, different set operations are introduced to generate the fault candidate set. After fault detection and a first fault localization, a procedure is given to render the fault localization more precisely by an analysis of the further observed system behavior. Special emphasis is given to the use of identified models for the fault-free system behavior. The approach is explained using a laboratory manufacturing facility.     

Optimal sensor activation for diagnosing discrete event systems

The problem of dynamic sensor activation for event diagnosis in partially observed discrete event systems is considered. Diagnostic agents are able to activate sensors dynamically during the evolution of the system. Sensor activation policies for diagnostic agents are functions that determine which sensors are to be activated after the occurrence of a trace of events. The sensor activation policy must satisfy the property of diagnosability of centralized systems or codiagnosability of decentralized systems. A policy is said to be minimal if there is no other policy, with strictly less sensor activation, that achieves diagnosability or codiagnosability. To compute minimal policies, we propose language partition methods that lead to efficient computational algorithms. Specifically, we define “window-based” language partitions for scalable algorithms to compute minimal policies. By refining partitions, one is able to refine the solution space over which minimal solutions are computed at the expense of more computation. Thus a compromise can be achieved between fineness of solution and complexity of computation.     

不完备离散事件系统的可诊断性

在离散事件系统的建模过程中,由于系统行为的复杂,存在物理系统向逻辑系统映射的不完全性,因此产生了不完备模型的概念.提出在模型不完备的前提下,判断模型可诊断性的方法.提出可诊断性的在线判定方法,同时将不完备的行为加入模型,使模型完备.用经典的双树方法判断离线可诊断性,根据观测序列的时序及语言的前缀判断并处理不完备行为.提出判定不完备行为的方法,向模型中添加不完备行为,并根据不完备行为增量地在双树中判定在线可诊断性.通过在线的可诊断性判定,当前系统能够得到在有限观测内唯一判定故障发生与否的结论.该方法适用于具有离散性质的系统.     

基于Petri网诊断器的离散事件系统模式故障的在线诊断

本文研究基于Petri网诊断器的离散事件系统模式故障的在线诊断问题.先构建一种用于模式故障在线诊断的自动机,给出了基于这种自动机的在线诊断方法.然后将自动机转换为Petri网并进一步构造了可用于S型模式故障或T型模式故障在线诊断的Petri网诊断器,提出了基于Petri网诊断器的模式故障在线诊断算法.通过分析算法的复杂性,得到了该算法具有多项式空间复杂性的结论.