On controllability of discrete event systems in a behavioral framework

The purpose of this paper is to investigate the controllability and the achievability of discrete event systems within a behavioral framework. Based on the notion of Willems’ behavioral controllability [1, 2], we introduce a new concept related to the controllability of discrete event systems. By using the controllability proposed here and the notion related to achievable behaviors [3, 4], we show that the behavioral controllability for a given specification with respect to language is equivalent to the existence of a controller, so that an interconnected system satisfies the specification exactly. A proposed controller here is represented by the intersection of the behavior of a given plant and that of a given (controllable) specification. We also clarify that our controllers for a given specification fit the properties of well-known supervisory controllers proposed and developed by Ramadge and Wonham [5]. The text was submitted by the authors in English.     

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

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

Testing controllability and constructibility in discrete linear systems

A simple criterion for complete controllability and constructibility of discrete-time linear constant systems is given in terms of left and right coprimeness of certain polynomial matrices.     

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.     

On controllability and pursuit problems in linear discrete systems

Linear discrete controlled systems and linear discrete pursuit games are considered in the problem where the control vector of the pursuer is subject to a geometrical constraint and the control of the pursued object is subject an integral constraint. Necessary and sufficient conditions of solvability of the 0-controllability problem and that of coming together at the zero point are proved by way of constructive selection of the control vector.     

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.     

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     

Distributed inversion in timed discrete event systems

We consider a discrete event system (DES) modeled by a timed automaton with partial state and event observations. We view the system as an input-output system, where the input is a sequence of event lifetimes, and the output is the resulting sequence of events, states, and transition epochs. We consider the problem of extracting event lifetimes (input) from observations of the output trajectory, which we callinversion. We give necessary and sufficient conditions forinvertibility, and an algorithm that extracts event lifetimes from any given output observation of an invertible system. We describe a distributed timed DES model based on the prioritized synchronous product of subsystems, and study the inversion problem in this framework. We show that invertibility in the subsystems implies invertibility in the global system. To illustrate our results, we provide an example of a tandem network.     

Probabilistic system opacity in discrete event systems

In many emerging security applications, a system designer frequently needs to ensure that a certain property of a given system (that may reveal important details about the system’s operation) be kept secret (opaque) to outside observers (eavesdroppers). Motivated by such applications, several researchers have formalized, analyzed, and described methods to verify notions of opacity in discrete event systems of interest. This paper introduces and analyzes a notion of opacity in systems that can be modeled as probabilistic finite automata or hidden Markov models. We consider a setting where a user needs to choose a specific hidden Markov model (HMM) out of m possible (different) HMMs, but would like to “hide” the true system from eavesdroppers, by not allowing them to have an arbitrary level of confidence as to which system has been chosen. We describe necessary and sufficient conditions (that can be checked with polynomial complexity), under which the intruder cannot distinguish the true HMM, namely, the intruder cannot achieve a level of certainty about its decision, which is above a certain threshold that we can a priori compute.     

Decision making in fuzzy discrete event systems

The primary goal of the study presented in this paper is to develop a novel and comprehensive approach to decision making using fuzzy discrete event systems (FDES) and to apply such an approach to real-world problems. At the theoretical front, we develop a new control architecture of FDES as a way of decision making, which includes a FDES decision model, a fuzzy objective generator for generating optimal control objectives, and a control scheme using both disablement and enforcement. We develop an online approach to dealing with the optimal control problem efficiently. As an application, we apply the approach to HIV/AIDS treatment planning, a technical challenge since AIDS is one of the most complex diseases to treat. We build a FDES decision model for HIV/AIDS treatment based on expert’s knowledge, treatment guidelines, clinic trials, patient database statistics, and other available information. Our preliminary retrospective evaluation shows that the approach is capable of generating optimal control objectives for real patients in our AIDS clinic database and is able to apply our online approach to deciding an optimal treatment regimen for each patient. In the process, we have developed methods to resolve the following two new theoretical issues that have not been addressed in the literature: (1) the optimal control problem has state dependent performance index and hence it is not monotonic, (2) the state space of a FDES is infinite.     

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.     

Decentralized failure diagnosis of discrete event systems

By decentralized diagnosis we mean diagnosis using multiple diagnosers, each possessing its own set of sensors, without involving any communication among diagnosers or to any coordinators. The notion of decentralized diagnosis is formalized by introducing the notion of codiagnosability that requires that a failure be detected by one of the diagnosers within a bounded delay. Algorithms of complexity polynomial in the size of the system and the nonfault specification are provided for: 1) testing codiagnosability, 2) computing the bound in delay of diagnosis, 3) offline synthesis of individual diagnosers, and 4) online diagnosis using them. The notion of codiagnosability and the above algorithms are initially presented in a setting of a specification language (violation of which represents a fault) and are later specialized to the case where faults are modeled as the occurrences of certain events. The notion of strong codiagnosability is also introduced to capture the ability of being certain about both the failure as well as the nonfailure conditions in a system within a bounded delay.     

Information-efficient control of discrete event stochastic systems

A state of a discrete event stochastic system (DESS) can be represented by a tuple of time-varying discrete parameters. The authors have extended the theory of controlled discrete event systems developed by Ramadge, Wonham and other researchers to stochastic modeling and performance measurement. This work presents some important characteristics of the DESS model. The problem of making the most efficient use of information-processing resources (sensors, computer capacity, etc.) in a special class of controlled systems is stated in a new, two-stage format. The format is used to develop a heuristic solution procedure of the problem. Finally, we perform a brief discussion of the model applicability to real-life design of automatic supervisors     

Constraint-based modeling of discrete event dynamic systems

Numerous frameworks dedicated to the modeling of discrete event dynamic systems have been proposed to deal with programming, simulation, validation, situation tracking, or decision tasks: automata, Petri nets, Markov chains, synchronous languages, temporal logics, event and situation calculi, STRIPS…All these frameworks present significant similarities, but none offers the flexibility of more generic frameworks such as logic or constraints. In this article, we propose a generic constraint-based framework for the modeling of discrete event dynamic systems, whose basic components are state, event, and time attributes, as well as constraints on these attributes, and which we refer to as CNT for Constraint Network on Timelines. The main strength of such a framework is that it allows any kind of constraint to be defined on state, event, and time attributes. Moreover, its great flexibility allows it to subsume existing apparently different frameworks such as automata, timed automata, Petri nets, and classical frameworks used in planning and scheduling.     

On the controllability of a class of discrete bilinear systems

The subject of this paper is the controllability of a class of time invariant discrete bilinear systems. Bilinear systems are classified into two categories: homogeneous and inhomogeneous. Necessity as well as the sufficiency results are obtained by means of decomposing the bilinear system into a linear system and a multiplicative feedback. Byproducts of the decomposition are the notions of multiplicative feedback compensation and the multiplicative feedback with bias compensation which may prove to be alternatives for the classical linear feedback compensation.     

On the controllability of discrete linear systems with output feedback

A discrete time linear systemx_{t+1}= Ax_{t} + Bu_{t'}y = Cx_{t'}, with output feedbacku_{t} = G_{t}y_{t'}, call be regarded as a nonlinear system with "control" Gt. Weak sufficient conditions are given for the existence of a finite sequence of gains for which every initial state can be driven to the origin. For a one input, one output system, the question of what terminal states can be reached from a given initial state is resolved. It is shown that an important ingredient for these problems is the semigroup of integers generated by the set{k:cA^{k-1}b neq 0, 1 leq k leq k leq 3n}(for a single input, single output system of dimensionn). It is also natural to use a pair of "canonical forms," in the guise of polynomials, to represent states. One is useful for input considerations and the other for output considerations. For output feedback problems one must further distinguish between two polynomials which are equivalent in the sense that they represent the same state. This is due to the fact that some polynomials are ill-conditioned in that they would have us use a nonzero input when the output vanishes.     

Decentralized state feedback control of discrete event systems

In this paper, we consider decentralized state feedback control of discrete event systems with a (global) control specification given by a predicate. In this framework, instead of a global state feedback, each local state feedback controls a part of the system according to local information so that global behaviors satisfy the global control specification. We introduce the notion of n-observability of predicates, and present necessary and sufficient conditions for the existence of a decentralized state feedback which achieves the global control specification.