Controllability of predicates and languages in discrete-event systems

In discrete-event systems, two control techniques, called supervisory control and state feedback logic, are applicable if control specifications are given in terms of predicates on the set of states. The concepts of controllability for both techniques has been proposed for the analysis and design of these techniques. First it is shown that controllability of the legal language for a given predicate is equivalent to that for the corresponding reachability set. Next we deal with the relationship between the supremal controllable subpredicate of the predicate and the supremal controllable sublanguage of the corresponding legal language     

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     

On supervisor reduction in discrete-event systems

A supervisory controller (supervisor) S for a discrete-event system can be modelled on a recognizer R for the language corresponding to the supervisory task to be accomplished. It is shown that simpler ‘reduced’ supervisors can be constructed by the use of covers of the state set of R; and that any mildly restricted supervisor is a reduction of R in this sense. The reduction procedure is time-exponential with respect to the size of the state set of R.     

Performance extrapolation in discrete-event systems simulation

The use of simulation as an engineering tool to design complex computer stochastic systems is often inhibited by cost. Extensive computer processing is needed to recompute performance functions for changes in input parameters. Moreover, simulation models are often subject to errors caused by the input data in estimating the parameters of the input distributions. The ‘;what if analysis is needed to establish confidence in a models validity with respect to small changes in the system’s parameters. To solve the ‘what if problem for several scenarios requires a separate simulation run for each scenario. A method to estimate the performance for several scenarios using a single simulation run based on the efficient score function is developed. The approximate function is an exponential random function which is tangential to the performance function in expectation. We study the algorithm's properties and examine the validity of the estimates based on this single run procedure by performing some experimental studies on some simple queueing and pert models. Implementation ‘details’ necessary to package this method with existing simulation software are provided. Finally, there is a set of recommended directions for future research     

Hierarchical control of discrete-event systems

An abstract hierarchical control theory is developed for discrete-event systems, based on the concepts of control structures and observers. Control structure is an abstract generalization of the family of controllable sublanguages in the Ramadge-Wonham framework. We establish a general version of Zhong's hierarchical consistency by first achieving control consistency — preservation of control structures through the aggregation mapping in a two-level hierarchy. For a refinement of hierarchical consistency with preservation of nonblocking, the concept of observer is introduced via congruences on nondeterministic transition structures.     

Active diagnosis of discrete-event systems

The need for accurate and timely diagnosis of system failures and the advantages of automated diagnostic systems are well appreciated. However, diagnosability considerations are often not explicitly taken into account in the system design. In particular, design of the controller and that of the diagnostic subsystem are decoupled, and this may significantly affect the diagnosability properties of a system. The authors present an integrated approach to control and diagnosis. More specifically, they present an approach for the design of diagnosable systems by appropriate design of the system controller. This problem, which they refer to as the active diagnosis problem, is studied in the framework of discrete-event systems (DESs); it is based on prior and new results on the theory of diagnosis for DESs and on existing results in supervisory control under partial observations. They formulate the active diagnosis problem as a supervisory control problem where the legal language is an “appropriate” regular sublanguage of the regular language generated by the system. They present an iterative procedure for determining the supremal controllable, observable, and diagnosable sublanguage of the legal language and for obtaining the supervisor that synthesizes this language. This procedure provides both a controller that ensures diagnosability of the closed-loop system and a diagnoser for online failure diagnosis. The procedure can be implemented using finite-state machines and is guaranteed to converge in a finite number of iterations. The authors illustrate their approach using a simple pump-valve system     

Diagnosability of stochastic discrete-event systems

We investigate diagnosability of stochastic discrete-event systems. We define the notions of A- and AA-diagnosability for stochastic automata; these notions are weaker than the corresponding notion of diagnosability for logical automata introduced by Sampath et al. Through the construction of a stochastic diagnoser, we determine offline conditions necessary and sufficient to guarantee A-diagnosability and sufficient to guarantee AA-diagnosability. We also show how the stochastic diagnoser can be used for on-line diagnosis of failure events. We illustrate the results through two examples from HVAC systems.     

On d-inversion in interruptive timed discrete-event systems

The authors consider the problem of extracting event lifetimes from partial observations of an interruptive timed discrete-event system. The extraction of the lifetime of an occurring event is based on observations of all previous transitions and d-subsequent transitions. We refer to this notion as d-inversion. We give necessary and sufficient structural conditions for an event to be d-invertible in a given system     

Queue reduction in discrete-event systems by relabeling

The customer population of entities potentially requesting to join a queue for service often have identical structure, i.e., the same state set and isomorphic transitions. The state size of the automaton modeling a queue will grow rapidly with increase of the size of this population. However, by relabeling the queue arrival events and service events to the same symbols respectively, the automaton model of a queue will be converted to the structure of a buffer, which is proved to be independent of the total size of the customer population, as long as the queue size is held fixed. We propose the model of a dynamic buffer to embody order and shift of a queue. The result is applied to a manufacturing facility with a dynamic buffer to manage the repair of broken down machines.     

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

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

Supervision localization of timed discrete-event systems

We study supervisor localization for real-time discrete-event systems (DES) in the Brandin–Wonham framework of timed supervisory control. We view a real-time DES as comprised of asynchronous agents which are coupled through imposed logical and temporal specifications; the essence of supervisor localization is the decomposition of monolithic (global) control action into local control strategies for these individual agents. This study extends our previous work on supervisor localization for untimed DES, in that monolithic timed control action typically includes not only disabling action as in the untimed case, but also “clock preempting” action which enforces prescribed temporal behavior. The latter action is executed by a class of special events, called “forcible” events; accordingly, we localize monolithic preemptive action with respect to these events. We demonstrate the new features of timed supervisor localization with a manufacturing cell case study and discuss a distributed control implementation.     

Supervisory control of concurrent discrete-event systems

When a discrele-event system P consists of several subsystems P₁,...,P_n which operate concurrently, a natural approach to the supervisory control problem is to synthesize a ‘local’ controller S_i , for each subsystem P_i , and operate the individually controlled subsystems S_i/P_i concurrently. Such an approach is called concurrent supervisory control and is closely related to decentralized supervisory control as studied by Cieslak et al. (1988) and Lin and Wonham (1988). In the present paper simple and easily computable conditions are developed which guarantee that concurrent supervisory control can achieve the optimal behaviour achievable by a global supervisor. To achieve this, two specific concurrent control strategies are introduced.     

Hierarchical control of timed discrete-event systems

An abstract hierarchical control theory is developed for a class of timed discrete-event systems (TDES) within the discrete-event control architectural framework proposed earlier by the authors. For this development, a control theory for TDES is introduced in the spirit of a prior theory of Brandin. A notion of time control structures is introduced, and on its basis a general property of hierarchical consistency is achieved by establishing control consistency — namely preservation of time control structures through the aggregation mapping in a two-level hierarchy.     

Pade approximation for stochastic discrete-event systems

We show that Pade approximation can be effectively used for approximation of performance functions in discrete-event systems. The method is (1) obtaining the MacLaurin coefficients of the performance function and (2) finding a Pade approximant from the MacLaurin coefficients and use it to approximate the function. We use the method with the expected number of renewals in a random interval, GI/G/1 systems, and inventory systems. The results are very good     

Modular supervisory control of discrete-event systems

A modular approach to the supervisory control of a class of discrete-event systems is formulated, and illustrated with an example. Discrete-event systems are modeled by automata together with a mechanism for enabling and disabling a subset of state transitions. The basic problem of interest is to ensure by appropriate supervision that the closed loop behavior of the system lies within a given legal behavior. Assuming this behavior can be decomposed into an intersection of component restrictions, we determine conditions under which it is possible to synthesize the appropriate control in a modular fashion. The work of this author was supported by NSERC (Canada) under Grant No. A-7399. The work of this author was supported by the National Science Foundation through Grant No. ECS-8504584.     

Sample-path analysis of stochastic discrete-event systems

This paper presents a unified sample-path approach for deriving distribution-free relations between performance measures for stochastic discrete-event systems extending previous results for discrete-state processes to processes with a general state space. A unique feature of our approach is that all our results are shown to follow from a single fundamental theorem: the sample-path version of the renewal-reward theorem (Y=X). As an elementary consequence of this theorem, we derive a version of the rate-conservation law under conditions more general than previously given in the literature. We then focus on relations between continuous-time state frequencies and frequencies at the points of an imbedded point process, giving necessary and sufficient conditions for theASTA (Arrivals See Time Averages), conditionalASTA, and reversedASTA properties. In addition, we provide a unified approach for proving various relations involving forward and backward recurrence times. Finally, we give sufficient conditions for rate stability of an input-output system and apply these results to obtain an elementary proof of the relation between the workload and attained-waiting-time processes in aG/G/l queue.Research was partially supported by the National Science Foundation under Grant no. DDM-8719825. The government of the United States of America has certain rights in this material. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The research of this author was also partially supported by a grant from Centre International des Étudiants et Stagiares (C.I.E.S.) while he was visiting INRIA, Sophia-Antipolis, Valbonne, France (1991–92).     

Supervisory control of timed discrete-event systems

The Ramadge-Wonham framework for control of discrete event systems is augmented with timing features by use of Ostroff's semantics for timed transition models. It is shown that the RW concept of controllability and the existence of maximally permissive supervisory controls can be suitably generalized. The enhanced setting admits subsystem composition and the concept of forcible event as an event that preempts the tick of a global clock. An example of a simple manufacturing cell illustrates how the new framework can be used to solve synthesis problems which may include logic-based, temporal and quantitative optimality specifications     

Reduced supervisors for timed discrete-event systems

The design of reduced supervisors, suboptimal but easier to compute, is placed in a general perspective. From this vantage point, we consider a timed discrete-event system, and compute a reduced supervisor based on an abstraction of the plant model in which time is measured with a slower clock. Such a model is simpler than the original, but has richer untimed behavior. Thus, a time-independent specification met by the closed-loop reduced system is also met by the original system when controlled by the same supervisor. The idea is illustrated with a simple example.