Robust and fault-tolerant supervisory control of discrete event systems with partial observation and model uncertainty

This paper proposes the notions of faults and failures in discrete event systems (DESs) with partial observation. They are associated with controllability and an observability property. The proposed notions are used to address the notion of tolerable fault event sequences which represents fault-tolerant behaviour of systems as a desired specification. A robust and fault-tolerant supervisor is a controller which is robust to model uncertainty and guarantees fault-tolerant behaviour of a system. In this paper we present necessary and sufficient conditions for the existence of a robust and fault-tolerant supervisor. The developed conditions capture the concepts of controllability and observability which are cores in the control of DESs with partial observation     

连续计时离散事件系统监控及其可观性

本文提出了一种带有连续时间变量的离散事件系统(称为计时离散事件系统)结构模型.通过讨论计时语言的性质,如封闭性、可控性以及可观性,研究了计时离散事件系统的监控综合问题,并基于这些性质,分别提出了计时离散事件系统在完全可观与部分可观条件下监控器存在的充要条件.     

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.     

The infimal prefix-closed and observable superlanguange of a given language

The supervisory control of discrete-event systems under partial observation is examined. In particular, the condition of observability needed to solve the two main existing problems is investigated. A fixed-point characterization of observability is given and is shown to yield an effective test for observability where the system under consideration is specified by regular languages. A formula for the infimal prefix-closed observable superlanguage of a given language is presented. Where the system is specified by regular languages, the formula for the infimal observable language is effectively computable.     

Observability and decentralized control of fuzzy discrete-event systems

Fuzzy discrete-event systems as a generalization of (crisp) discrete-event systems have been introduced in order that it is possible to effectively represent uncertainty, imprecision, and vagueness arising from the dynamic of systems. A fuzzy discrete-event system has been modeled by a fuzzy automaton; its behavior is described in terms of the fuzzy language generated by the automaton. In this paper, we are concerned with the supervisory control problem for fuzzy discrete-event systems with partial observation. Observability, normality, and co-observability of crisp languages are extended to fuzzy languages. It is shown that the observability, together with controllability, of the desired fuzzy language is a necessary and sufficient condition for the existence of a partially observable fuzzy supervisor. When a decentralized solution is desired, it is proved that there exist local fuzzy supervisors if and only if the fuzzy language to be synthesized is controllable and co-observable. Moreover, the infimal controllable and observable fuzzy superlanguage, and the supremal controllable and normal fuzzy sublanguage are also discussed. Simple examples are provided to illustrate the theoretical development.     

Safe diagnosability for fault-tolerant supervision of discrete-event systems

The problem of achieving fault-tolerant supervision of discrete-event systems is considered from the viewpoint of safe and timely diagnosis of unobservable faults. To this end, the new property of safe diagnosability is introduced and studied. Standard definitions of diagnosability of discrete-event systems deal with the problem of detecting the occurrence of unobservable fault events using model-based inferencing from observed sequences of events. In safe diagnosability, it is required in addition that fault detection occur prior to the execution of a given set of forbidden strings in the failed mode of operation of the system. For instance, this constraint could be required to prevent local faults from developing into failures that could cause safety hazards. If the system is safe diagnosable, reconfiguration actions could be forced upon the detection of faults prior to the execution of unsafe behaviour, thus achieving the objective of fault-tolerant supervision. Necessary and sufficient conditions for safe diagnosability are derived. In addition, the problem of explicitly considering safe diagnosability in controller design, termed “active safe diagnosis problem”, is formulated and solved. A brief discussion of safe diagnosability for timed models of discrete-event systems is also provided.     

A Framework for Fault-Tolerant Control of Discrete Event Systems

We introduce a framework for fault-tolerant supervisory control of discrete-event systems. Given a plant, possessing both faulty and nonfaulty behavior, and a submodel for just the nonfaulty part, the goal of fault-tolerant supervisory control is to enforce a certain specification for the nonfaulty plant and another (perhaps more liberal) specification for the overall plant, and further to ensure that the plant recovers from any fault within a bounded delay so that following the recovery the system state is equivalent to a nonfaulty state (as if no fault ever happened). The specification for the overall plant is more liberal compared to the one for the nonfaulty part since a degraded performance may be allowed after a fault has occurred. We formulate this notion of fault-tolerant supervisory control and provide a necessary and sufficient condition for the existence of such a supervisor. The condition involves the usual notions of controllability, observability and relative-closure, together with the notion of stability. An example of a power system is provided to illustrate the framework. We also propose a weaker notion of fault-tolerance where following the recovery, the system state is simulated by some nonfaulty state, i.e., behaviors following the recovery are also the behaviors from some faulty state. Also, we formulate the corresponding notion of weakly fault-tolerant supervisory control and present a necessary and sufficient condition (involving the notion of language-stability) for the its existence. We also introduce the notion of nonuniformly-bounded fault-tolerance (and its weak version) where the delay-bound for recovery is not uniformly bounded over the set of faulty traces, and show that when the plant model has finitely many states, this more general notion of fault-tolerance coincides with the one in which the delay-bound for recovery is uniformly bounded.     

Characterizing intransitive noninterference for 3-domain security policies with observability

This note introduces a new algorithmic approach to the problem of checking the property of intransitive noninterference (INI) using discrete-event systems (DESs) tools and concepts. INI property is widely used in formal verification of security problems in computer systems and protocols. The approach consists of two phases: First, a new property called iP-observability (observability based on a purge function) is introduced to capture INI. We prove that a system satisfies INI if and only if it is iP-observable. Second, a relation between iP-observability and P-observability (observability as used in DES) is established by transforming the automaton modeling a system/protocol into an automaton where P-observability (and, hence, iP-observability) can be determined. This allows us to check INI by checking P-observability, which can be done efficiently. Our approach can be used for all systems/protocols with three domains or levels, which is sufficient for most noninterference problems for cryptographic protocols and systems.     

Characterizations and effective computation of supremal relatively observable sublanguages

Recently we proposed relative observability for supervisory control of discrete-event systems under partial observation. Relative observability is closed under set unions and hence there exists the supremal relatively observable sublanguage of a given language. In this paper we present a new characterization of relative observability, based on which an operator on languages is proposed whose largest fixpoint is the supremal relatively observable sublanguage. Iteratively applying this operator yields a monotone sequence of languages; exploiting the linguistic concept of support based on Nerode equivalence, we prove for regular languages that the sequence converges finitely to the supremal relatively observable sublanguage, and the operator is effectively computable. Moreover, for the purpose of control, we propose a second operator that in the regular case computes the supremal relatively observable and controllable sublanguage.     

Observable augmented systems for sensitivity analysis of Markov andsemi-Markov processes

Previous work by the authors (1989) on sensitivity analysis of discrete-event systems (DESs), where an augmented chain approach for estimating performance sensitivities from a single nominal sample path was developed, is extended. In contrast to existing methods, this approach can be applied to cases involving discrete (e.g. integer-valued) parameters such as queue capacities or routing thresholds. However, the basic method is limited by some rather restrictive observability conditions. These conditions are relaxed through an observability transformation which generalizes the method's applicability. Direct extensions to more general (non-Markovian) DES are also presented via a simplified generalized semi-Markov process reformulation of the approach. Experimental verification of the techniques is included     

A discussion of fault-tolerant supervisory control in terms of formal languages

A system is fault tolerant if it remains functional after the occurrence of a fault. Given a plant subject to a fault, fault-tolerant control requires the controller to form a fault-tolerant closed-loop system. For the systematic design of a fault-tolerant controller, typical input data consists of the plant dynamics including the effect of the faults under consideration and a formal performance requirement with a possible allowance for degraded performance after the fault. For its obvious practical relevance, the synthesis of fault-tolerant controllers has received extensive attention in the literature, however, with a particular focus on continuous-variable systems. The present paper addresses discrete-event systems and provides an overview on fault-tolerant supervisory control. The discussion is held in terms of formal languages to uniformly present approaches to passive fault-tolerance, active fault-tolerance, post-fault recovery and fault hiding.     

Diagnosis of timed automata: Theory and application to the DAMADICS actuator benchmark problem

This paper concerns the problem of fault diagnosis in discrete-event systems which are represented by timed automata. The diagnostic algorithm for timed automata detects and identifies faults in the system based on the investigation whether the measured input and output sequences are consistent with the timed automaton. This diagnostic approach can be applied spontaneously to the discrete-event system since no a priori information about the initial state of the system is required. It is shown in the paper how the timed automaton which represents the DAMADICS actuator can be obtained and how the diagnostic algorithm based on the timed automaton is applied to detect and identify actuator faults. A representative diagnostic result is presented and discussed to illustrate the effectiveness of the method.     

Maximally permissive coordinated distributed supervisory control of nondeterministic discrete-event systems

In supervisor synthesis for discrete-event systems achieving nonblockingness is a major challenge for a large system. To overcome it we present an approach to synthesize a deterministic coordinated distributed supervisor under partial observation, where the plant is modeled by a collection of nondeterministic finite-state automata and the requirement is modeled by a collection of deterministic finite-state automata. Then we provide a sufficient condition to ensure the maximal permissiveness of a coordinated distributed supervisor generated by the proposed synthesis approach.     

Coinduction in Control of Partially Observed Discrete-Event Systems

Coalgebra and coinduction provide new results and insights for the supervisory control of discrete-event systems (DES) with partial observations. In the case of full observations, coinduction has been used to define a new operation on languages called supervised product, which represents the tuple of languages of the supervised system. The first language acts as a supervisor and the second as an open-loop system (plant). We show first that the supervised product is equal to the infimal controllable superlanguage of the supervisor's (specification) language with respect to the plant language. This can be generalized to the partial observation case, where the supervised product is shown to be equal to the infimal controllable and observable superlanguage. A modification on the supervised product is presented, which corresponds to the control policy for with the issue of observability is separated from the issue of controllability. The operation defined by coinduction is shown to be equal to the infimal observable superlanguage.     

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.     

Relative coobservability for decentralised supervisory control of discrete-event systems

In this paper, we study the concept of relative coobservability in decentralised supervisory control of discrete-event systems under partial observation. This extends our previous work on relative observability from a centralised setup to a decentralised one. A fundamental concept in decentralised supervisory control is coobservability (and its several variations); this property is not, however, closed under set union, and hence there generally does not exist the supremal element. Our proposed relative coobservability, although stronger than coobservability, is algebraically well behaved, and the supremal relatively coobservable sublanguage of a given language exists. We present a language-based algorithm to compute this supremal sublanguage; the algorithm allows straightforward implementation using off-the-shelf algorithms. Moreover, relative coobservability is weaker than conormality, which is also closed under set union; unlike conormality, relative coobservability imposes no constraint on disabling unobservable controllable events.     

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     

具有Neumann边界的分布参数切换系统的容错控制

本文研究了一类具有Neumann边界条件的分布参数切换系统的容错控制问题.当执行器失效或部分失效时,运用Lyapunov函数法和Green公式,获得了闭环切换系统混杂状态反馈容错控制器存在的充分条件.然后运用线性矩阵不等式将容错控制器设计问题转化为一组线性矩阵不等式求可行解的问题,因而可以借助MATLAB中线性矩阵不等式工具箱来完成.同时,运用Poincare不等式减少控制系统设计的保守性.最后通过数值算例,验证所提出设计方法的有效性.     

Polynomial synthesis of supervisor for partially observed discrete-event systems by allowing nondeterminism in control

We study the supervisory control of discrete-event systems (DESs) under partial observation using nondeterministic supervisors. We formally define a nondeterministic control policy and also a control & observation compatible nondeterministic state machine and prove their equivalence. The control action of a nondeterministic supervisor is chosen online, nondeterministically from among a set of choices determined offline. Also, the control action can be changed online nondeterministically (prior to any new observation) in accordance with choices determined offline. The online choices, once made, can be used to affect the set of control action choices in future. We show that when control is exercised using a nondeterministic supervisor, the specification language is required to satisfy a weaker notion of observability, which we define in terms of recognizability and achievability. Achievability serves as necessary and sufficient condition for the existence of a nondeterministic supervisor, and it is weaker than controllability and observability combined. When all events are controllable, achievability reduces to recognizability. We show that both existence, and synthesis of nondeterministic supervisors can be determined polynomially. (For deterministic supervisors, only existence can be determined polynomially.) Both achievability and recognizability are preserved under union, and also under intersection (when restricted over prefix-closed languages). Using the intersection closure property we derive a necessary and sufficient condition for the range control problem for the prefix-closed case. Unlike the deterministic supervisory setting where the complexity of existence is exponential, our existence condition is polynomially verifiable, and also a supervisor can be polynomially synthesized.