Diagnosability of discrete event systems for temporary failures

Failure Detection and Diagnosis (FDD) using Discrete Event System (DES) framework is used for wide range of applications because of simplicity of both the model and associated algorithms. Initial research was focussed on permanent failures. Many systems exhibit temporary failures in the sense that system recovers to normal condition after failure. Contant et al. extended the event based DES framework, developed for permanent failure by Sampath et al. to handle temporary failures. Zad et al. developed a state based DES framework for permanent failures which has several advantages compared to the event based approach. In this paper, we extend the state based DES framework, developed for permanent failures, to handle temporary failures, maintaining the same order of complexity. The proposed DES framework has several advantages compared to that by Contant et al. namely, capability to detect failures that occur before starting execution of the diagnoser, same diagnoser for both temporary and permanent failures, etc.     

Failure diagnosis of discrete-event systems with linear-time temporal logic specifications

The paper studies failure diagnosis of discrete-event systems (DESs) with linear-time temporal logic (LTL) specifications. The LTL formulas are used for specifying failures in the system. The LTL-based specifications make the specification specifying process easier and more user-friendly than the formal language/automata-based specifications; and they can capture the failures representing the violation of both liveness and safety properties, whereas the prior formal language/automaton-based specifications can capture the failures representing the violation of only the safety properties (such as the occurrence of a faulty event or the arrival at a failed state). Prediagnosability and diagnosability of DESs in the temporal logic setting are defined. The problem of testing prediagnosability and diagnosability is reduced to the problem of model checking. An algorithm for the test of prediagnosability and diagnosability, and the synthesis of a diagnoser is obtained. The complexity of the algorithm is exponential in the length of each specification LTL formula, and polynomial in the number of system states and the number of specifications. The requirement of nonexistence of unobservable cycles in the system, which is needed for the diagnosis algorithms in prior methods to work, is relaxed. Finally, a simple example is given for illustration.     

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.     

Supervisor synthesis for discrete event systems under partial observation and arbitrary forbidden state specifications

In this paper, we consider the forbidden state problem in discrete event systems modeled by partially observed and partially controlled Petri nets. Assuming that the reverse net of the uncontrollable subnet of the Petri net is structurally bounded, we compute a set of weakly forbidden markings from which forbidden markings can be reached by firing a sequence of uncontrollable/unobservable transitions. We then use reduced consistent markings to represent the set of consistent markings for Petri nets with structurally bounded unobservable subnets. We determine the control policy by checking if the firing of a certain controllable transition will lead to a subsequent reduced consistent marking that belongs to the set of weakly forbidden markings; if so, we disable the corresponding controllable transition. This approach is shown to be minimally restrictive in the sense that it only disables behavior that can potentially lead to a forbidden marking. The setting in this paper generalizes previous work by studying supervisory control for partially observed and partially controlled Petri nets with a general labeling function and a finite number of arbitrary forbidden states. In contrast, most previous work focuses on either labeling functions that assign a unique label to each observable transition or forbidden states that are represented using linear inequalities. More importantly, we demonstrate that, in general, the separation between observation and control (as considered in previous work) may not hold in our setting.     

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

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

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.     

Detectability of networked discrete event systems

Detectability of discrete event systems, defined as the ability to determine the current and subsequent states, is very important in diagnosis, control, and many other applications. So far only detectability of non-networked discrete event systems has been defined and investigated. Non-networked discrete event systems assume that all the communications are reliable and instantaneous without any delays or losses. This assumption is often violated in networked systems. In this paper, we study detectability for networked discrete event systems. We investigate the impact of communication delays and losses on detectability. We define two classes of detectabilities: network detectability for determining the state of a networked discrete event systems and network D-detectability for distinguishing certain pairs of states of the systems. Necessary and sufficient conditions for network detectability and network D-detectability are derived. Methods to check network detectability and network D-detectability are also developed. Examples are given to illustrate the results.     

Observability of discrete event dynamic systems

A finite state automaton is adopted as a model for discrete event dynamic systems (DEDS). Observations are assumed to be a subset of the event alphabet. Observability is defined as having perfect knowledge of the current state at points in time separated by bounded numbers of transitions. A polynomial test for observability is given. It is shown that an observer may be constructed and implemented in polynomial time and space. A bound on the cardinality of the observer state space is also presented. A notion of resiliency is defined for observers, and a test for resilient observability and a procedure for the construction of a resilient observer are presented     

The predictability of discrete event systems

Perturbation analysis and the automaton and language model are approaches developed recently for the study of discrete-event systems (DESs). The prediction of a trajectory of a new system is the essential idea of perturbation analysis. The automaton theory models a trajectory of a DES by a string in a particular language. The author formulates the trajectory prediction as a projection of a string onto a language. A sufficient condition is found for one language to be predictable from another language. Examples are given to show the application of this concept     

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.     

A unified frame work for discrete event systems

Early fault detection and isolation minimize cost and processing time of industrial systems. The main purpose of this paper is to introduce a novel delta-marking idea to design a generalized interpreted Petri net-based fault detection and isolation scheme (IPN-based diagnoser) for all PN models. This idea overcomes the event detectability problem that restricts the performance of the conventional dignosers to certain types of Petri net model. Furthermore, a unified framework for a discrete event system that comprises a PN-based model, a PN-based supervisor, and a PN-based diagnoser of a process under consideration, is built in this paper. In addition, this paper addresses some issues for industrial systems modeling and supervision. A rapid thermal process (RTP) is used as an industrial process to test the proposed unified framework after revising its PN-model. This scheme is not only developed for RTPs, but also can be employed for industrial processes with certain modifications depending on the nature of their structures. Simulation results have confirmed the effectiveness of the proposed unified framework.     

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.     

Finitely recursive process models for discrete event systems

A class of discrete-event models called finitely recursive processes (FRP) is introduced. These models are motivated by problems in supervisory control, while some of the formal structure is based on C.A.R. Hoare's (1985) communicating sequential processes. Although only preliminary work is presented, it is believed that for many problems it offers a formalism that is superior to that of finite-state machines recently introduced in control theory. Simple examples illustrate the calculus of operators for FRPs. A more complex exercise is worked out to show how the formalism is used to construct a scheme for handling connections in a data network. This preliminary work needs to be extended in several directions, especially in directions that can assist implementation of real controllers based on the FRP formalism. Some specific suggestions towards this end are made     

Modeling discrete event scalable network systems

Scalability in simulation tools is one of the most important traits to measure performance of software. The reason is that today’s Internet is the main instance of a large-scale and highly complex system. Simulation of Internet-scale network systems has to be supported by any simulation tool. Despite this fact, many network simulators lacks support for building large models. In this work, in order to propose a new approach for scalability issue in network simulation tools, a network simulator is developed based on behavior of honeybees and high performance DEVS, modular and hierarchical system theoretic approach. A biologically-inspired discrete event modeling approach is described for studying networks’ scalability and performance traits. Since natural systems can offer important concepts for modeling network systems, key adaptive and emergent attributes of honeybees and their societal properties are incorporated into a set of simulation models that are developed using the discrete event system specification approach. Large-scale network models are simulated and evaluated to show the benefits of nature-inspired network models.     

On controlling prioritized discrete event systems with real-time constraints

We study a class of prioritized Discrete Event Systems (DESs) that involve the control of resources allocated to tasks under real-time constraints. Our work is motivated by applications in communication systems, computing systems, and manufacturing systems where the objective is to minimize energy consumption while guaranteeing that task deadlines are always met. In the off-line setting, we discover several structural properties of the optimal sample path of such DESs. Using the structural properties, we also propose a greedy algorithm which is shown numerically near optimal. For on-line control, we design a Receding Horizon (RH) controller. Using worst-case estimation, the RH control is able to guarantee feasibility (when the off-line problem is feasible) and achieve good performance.     

On condition/event systems with discrete state realizations

This paper introduces condition/event (C/E) systems as a class of continuous-time discrete event dynamic systems (DEDS) with two types of discrete-valued input and output signals:condition signals andevent signals. In applications such as discrete control, C/E systems provide an intuitive continuous-time modeling framework amenable to block diagram representation. In this paper we consider C/E systems with discrete state realizations, and study the relationship between continuous-time C/E systems and untimed models of their sequential inputoutput behavior called C/E languages. We show that C/E systems with discrete state realizations are necessarilytime-change invariant (Theorem 3.1), which means the ensemble of admissible continuous-time input-output behaviors is completely characterized by the C/E language for the system (Theorem 4.1). It is also shown that deterministic C/E systems with discrete state realizations are necessarily discrete-time (clocked) systems (Corollary 3.1), and that finite discrete state realizations exist for a C/E system only if its related C/E language has a finite state generator (Theorem 4.2). Finally, we develop equivalent discrete-state realizations for C/E systems resulting from cascade and feedback interconnections. The paper concludes with a discussion of several directions for future research.Please direct correspondence concerning this paper to B.H. Krogh at the above address.