Incremental hierarchical construction of modular supervisors for discrete-event systems

Adoption of the supervisory control framework introduced by Ramadge and Wonham has been slowed somewhat by the problem of state space explosion that arises in systems of the scale common to most industrial applications. Hierarchical and modular approaches have been explored historically as means for addressing this problem. The limitations of these approaches include that a ‘consistent’ hierarchy is often difficult to achieve, and that modular supervisors often conflict with each other when acting in conjunction. This paper offers an approach that addresses some of these issues by incrementally building modular supervisors that are nonconflicting by construction. Abstractions are employed to make the procedure more computationally feasible. Proof is given showing the set of modular supervisors generated in this manner meet given specifications without blocking. Furthermore, examples are provided that demonstrate the reduction in complexity that this approach provides.     

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     

On the control of discrete-event dynamical systems

We study a class of problems related to the supervisory control of a discrete-event system (DES), as formulated by Ramadge and Wonham, and we focus on the computational effort required for their solution. While the problem of supervisory control of a perfectly observed DES may be easily solved by dynamic programming, the problem becomes intractable (in the sense of complexity theory) when imperfectly observed systems are considered. Research supported by the Army Research Office (Grant No. DAAL03-86-K-0171) and by an NSF PYI award, with matching funds from Bellcore Inc.     

Discrete events and general systems theory

A new formal approach to the qualitative modelling of general time systems is introduced. The formalism is suitable for general non-deterministic systems with non-numerically valued inputs and outputs, e.g. for discrete event systems. The following basic concepts of systems theory, observability, causality, determinism and interconnections of systems, are defined using an input-output approach to the modelling. The concept of the state is introduced as a secondary one. A general definition of the discrete event systems is given. Some fundamental properties of systems are proved. A real-time extension of the supervisory control problem given by Ramadge and Wonham is formulated. Seven examples are provided.     

Implementation of supervisory control using extended finite-state machines

This article aims at bridging the gap between traditional designs to discrete-event control problems and supervisory control theory of Ramadge and Wonham. We propose to implement supervisory control by extending the plant's finite state machine with Boolean variables, guard formulas and updating functions. Boolean variables are used to encode the supervisor's states, event observation is captured by a set of Boolean functions that update the value of variables, and control is introduced by guarding events with Boolean formulas. The framework developed in this work is fundamental in our ongoing research on communication between supervisors in a distributed discrete-event system.     

The synthesis and PLC implementation of hybrid modular supervisors for real time control of an experimental manufacturing system

In this paper, synthesis and PLC based implementation of hybrid modular supervisors for real time supervisory control of an experimental manufacturing system are proposed. The hybrid approach couples Ramadge–Wonham (RW) supervisors in the form of automata to uncontrolled PN models through inhibitor arcs. The RW supervisors can be obtained in monolithic or modular forms. In the monolithic case, there is only a single supervisor that has complex structure and huge number of states and events. The modularity of supervisors provides simple and small control structures compared to monolithic ones. Modular hybrid approach offers fewer states for the PLC implementation of the hybrid controller with less memory requirements. The applicability and effectiveness of the modular hybrid approach are demonstrated by the PLC based real-time control of an experimental manufacturing system for different cases. The obtained results show that modular supervisors require less memory space compared to monolithic counterparts.     

Modular supervisory control for multi-floor manufacturing processes

Due to space availability limitations and high land costs, there is an increasing development of multi-floor manufacturing (MFM) systems in urban and industrial areas. The problem of coordination in a multi-floor manufacturing process, in the Ramadge Wonham framework, is introduced. The manufacturing chain of each floor and the elevator system are modeled in the form of finite deterministic automata. The models of the multi-floor manufacturing process are parametric with respect to the number of floors and the number of manufacturing machines on each floor. The coordination desired performance is formulated in the form of desired regular languages in analytic forms. The languages are realized by appropriate supervisors in the form of finite deterministic automata. The models of the supervisors are also parametric with respect to the number of floors and the number of manufacturing machines on each floor. The total control of the coordination of the multi-floor manufacturing process is accomplished via a modular supervisory control architecture. The complexity of the supervisors as well as the complexity of the total modular supervisory architecture are determined in analytic forms with respect to the number of floors and the number of manufacturing machines on each floor. The special case of a two floor manufacturing process is presented as an illustrative example.     

A Note on the Properties of the Supremal Controllable Sublanguage in Pushdown Systems

Consider an event alphabet Sigma. The supervisory control theory of Ramadge and Wonham asks the question: given a plant model G with language L_M (G) sube Sigma* and another language K sube L_M (G), is there a supervisor phi such that L_M (phi/G) = K? Ramadge and Wonham showed that a necessary condition for this to be true is the so-called controllability of K with respect to L_M (G). They showed that when G is a finite-state automaton and K is a regular language (also generated by a finite state automaton), then there is a regular supremal controllable sublanguage sup_C (K) sube K that is effectively constructable from generators of K and G. In this paper, we show: 1) there is an algorithm to compute the supremal controllable sublanguage of a prefix closed K accepted by a deterministic pushdown automaton (DPDA) when the plant language is also prefix closed and accepted by a finite state automaton and 2) in this case, we show that this supremal controllable sublanguage is also accepted by a DPDA.     

Control of large discrete event systems: constructive algorithms

An automata-based theory has been developed by W.M. Wonham and P.J. Ramadge (SMIA J. Control Optimiz. vol.25, p.206-30, 637-59, 1987) and their associates. Its practical implementation in large real-life systems requires automatic programming schemes, which yield supervisory control programs, and models of the controlled system's behavior (for the purpose of performance analysis). The available data for these constructions would normally consist of a set of local structural models and local operational requirements. In the present study, the authors illuminate the relationship between local and global models and outline some of the basic elements of such schemes based on integration of local data     

Control of vector discrete-event systems. I. The base model

A vector discrete-event system (VDES) is a discrete-event system model in which the system state is represented by a vector with integer components, and state transitions by integer vector addition. The authors investigate such structures from the viewpoint of control theory. The objective is to specialize to VDES the general automation-based control theory of P.J. Ramadge and W.M. Wonham (1987) and W.M. Wonham and P.J. Ramadge (1988). It is shown that within the VDES framework a useful class of control systems can be compactly modeled, and some of the associated control problems of Ramadge and Wonham can be more efficiently solved     

A note on deciding controllability in pushdown systems

Consider an event alphabet /spl Sigma/. The supervisory control theory of Ramadge and Wonham asks the question, given a plant model G, with language K L/sub M/(G)/spl sube//spl Sigma//sup */ and another language K/spl sube/ L/sub M/(G), is there a supervisor /spl psi/ such that L/sub M/(/spl psi//G)=K. Ramadge and Wonham showed that a necessary condition for this to be true is the so-called controllability of K with respect to L/sub M/(G). They showed that when G is a finite state automaton and K is a regular language (also generated by a finite state automaton), then the controllability property was decidable for K. The class of languages generated by pushdown automata properly includes the regular languages. They are accepted by finite state machines coupled with pushdown stack memory. This makes them interesting candidates as supervisory languages, since the supervisor will have nonfinite memory. In this note, we show the following: i) If S is a specification given by a deterministic pushdown automaton and L is generated by a finite state machine, then there is an algorithm to decide whether K=S/spl cap/L is controllable with respect to L. ii) It is undecidable for an arbitrary specification S generated by a nondeterministic pushdown automaton and plant language L generated by a finite state machine whether K=S/spl cap/L is controllable with respect to L.     

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.     

受控离散事件过程（CDEP）的一种代数分析方法

本文在文［１～３］的基础上，提出了受控离散事件过程（ＣＤＥＰ）的一种代数分析方法，弥补了Ｒａｍａｄｇｅ和Ｗｏｎｈａｍ［１～３］的理论对具体系统的应用缺乏可操作性的缺陷，使得对ＣＤＥＰ动态过程的分析变得更为直观，同时也使控制器的设计过程更具可操作性．     

一类混杂系统的建模与控制器设计

研究一类离散事件系统和连接时间系统相混合的混杂系统建模与控制器设计问题。首先用不同的模型方法建立混杂系统的层次模型，分析连续时间系统状态空间的离散化和系统的可控性；在此基础上利用ＤＥＳ监控理论设计控制器，以规范系统的时域和逻辑行为。最后的示例表明了层次模型与控制算法的有效性。     

Nonblocking supervisory control of timed discrete event systems under communication delays: The existence conditions

This paper addresses the problem of nonblocking supervisory control of timed discrete event systems under communication delays based on the framework proposed by Brandin and Wonham. For such a system, a supervisory control command could be applied to the system after some time-delay limited by a finite bound corresponding to the maximal number of tick occurrences, and some uncontrollable events may unexpectedly occur within this time-delay. This paper presents the necessary and sufficient conditions for the existence of a nonblocking supervisor that can achieve a given language specification in consideration of such delayed communications.     

A New Class of Supervisors for Timed Discrete Event Systems Under Partial Observation

Brandin and Wonham have developed a supervisory control framework for timed discrete event systems (TDESs) in order to deal with not only logical specifications but also temporal specifications. Lin and Wonham have extended this framework to the partial observation case, and presented necessary and sufficient conditions for the existence of a nonblocking supervisor under partial observation. In this paper, we define a new class of supervisors for TDESs under partial observation. We then present necessary and sufficient conditions for the existence of a nonblocking supervisor defined in this paper. These existence conditions of our supervisor are weaker than those of Lin and Wonham's supervisor. Note, however, that the price that must be paid to weaken the existence conditions is the higher computational cost. Moreover, given a closed regular language, we study computation of a sublanguage that satisfies the existence conditions of our supervisor. We present an algorithm for computing such a sublanguage larger than the supremal closed, controllable, and normal sublanguage.     

Translation of output constraint into event constraint in the control of discrete event systems

When the desired behaviour of a controlled discrete event system (Ramadge and Wonham 1987) is specified by the sequence of the states or the sequence of a subset of the states, in order to formulate the specification given by natural language it is much more convenient to use the output constraint than the event constraint. However, the event constraint is easier to handle when constructing the controller. In this paper, a translator that translates output constraints into event constraints is defined and constructed, allowing us to formulate the desired behaviour of a discrete event system with output constraints.     

Language-measure-theoretic optimal control of probabilistic finite-state systems

Supervisory control theory for discrete event systems, introduced by Ramadge and Wonham, is based on a non-probabilistic formal language framework. However, models for physical processes inherently involve modelling errors and noise-corrupted observations, implying that any practical finite-state approximation would require consideration of event occurrence probabilities. Building on the concept of signed real measure of regular languages, this paper formulates a comprehensive theory for optimal control of finite-state probabilistic processes. It is shown that the resulting discrete-event supervisor is optimal in the sense of elementwise maximizing the renormalized langauge measure vector for the controlled plant behaviour and is efficiently computable. The theoretical results are validated through several examples including the simulation of an engineering problem.     

Controllability and control-invariance in discrete-event systems

Recently, for discrete-event systems modelled by automata, Ramadge and Wonham (1987 a, b) have proposed two control techniques called ‘supervisory control’ and ‘state feedback logic’. If control specifications are given in terms of predicates on the set of states, both techniques are applicable. This paper discusses the relationship between these techniques. It is shown that the language accepted by the discrete-event system with maximally permissive feedback is equal to the supremal controllable language if the predicate is control invariant. Moreover, it is shown that the predicate is control invariant if there exists a controllable language with a certain condition on the set of reachable states, but the converse does not hold in general     

Why Event Observation: Observability Revisited

In this paper, we revisit observability defined in Lin and Wonham (1988a). We show that although the original definition is intended for event observation with projection, its significance goes beyond its original intent. Specifically, we show that (1) supervisory control with state observation can be studied in terms of event observation; (2) supervisory control problems with event mask can be converted to problems with event projection; and (3) nondeterminism is closely related to unobservability.