Robust nonblocking supervisory control of discrete-event systems under partial observation

In this paper, we examine the problem of robust nonblocking supervisory control. In the problem considered here, the exact model of the plant is not known but is assumed to be among a finite set of possible models. For each plant model a legal marked behavior is assumed given. We extend previous results for the case of control with full observation to the case of control under partial observation where only a subset of events are observable. Furthermore, we remove the limitations of previous results on ensuring the nonblocking property of the plant under supervision. We characterize the entire set of solutions of the robust control problem and obtain a set of necessary and sufficient conditions for the existence of a solution for the problem. As an illustrative example, we use our results on robust control to solve a fault recovery problem.     

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.     

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.     

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.     

Similarity-based supervisory control of discrete-event systems

Due to the appearance of uncontrollable events in discrete-event systems, one may wish to replace the behavior leading to the uncontrollability of pre-specified language by some quite similar one. To capture this similarity, we introduce metric to traditional supervisory control theory and generalize the concept of original controllability to /spl lambda/-controllability, where /spl lambda/ indicates the similarity degree of two languages. A necessary and sufficient condition for a language to be /spl lambda/-controllable is provided. We then examine some properties of /spl lambda/-controllable languages and present an approach to optimizing a realization.     

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     

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.     

Robust nonblocking supervisory control of discrete-event systems

In this note, we generalize a robust supervisory control framework to deal with marked languages. We show how to synthesize a supervisor to control a family of plant models, each with its own specification. The solution we obtain is the most general in that it provides the closest approximation to the supremal controllable sublanguage for each plant/specification pair. We end the note by extending these results to deal with timed discrete-event systems.     

Computing observers from observation policies in discrete-event systems

This paper considers partially-observed discrete-event systems modeled by finite-state automata. The observation of event occurrences is associated with the transitions of the automaton model. That is, whether or not an event occurrence is observed is state-dependent, i.e., it depends on the transition in which the event label appears. This is in contrast to the case when observations are static and an event is either observed or not observed at every state in which it can occur. We refer to the set of transitions whose associated events are observed as an observation policy. Given an automaton model and an observation policy, we consider the problem of computing a deterministic generator of the language of event sequences that are observed using the automaton model and observation policy (i.e., an observer). Such a generator is useful, e.g., in problems of sensor activation for providing a deterministic mapping from event observations to sensor activation decisions when the decision to activate an event’s sensor is initially modeled as an observation policy. We propose an abstraction of the automaton model that may be used to represent an observer in certain cases. We illustrate cases where this abstraction accurately represents an observer when there is no ambiguity as to which event occurrences are observed following two observationally-identical strings. For the most general case considered, we demonstrate that verifying if the case holds is PSPACE-complete.     

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.     

Decentralized control and coordination of discrete-event systemswith partial observation

Decentralized supervision and coordination are studied for partially observed discrete-event systems. The authors' (1988) previous results on decentralized supervision and supervision under partial observation are extended by incorporating both these features in the control structure. In addition, a concept of coordination is introduced, and conditions for the existence of a coordinating supervisor are established. It is concluded that decentralized supervision will be easier to design and implement that centralized supervision; under suitable conditions it will be equivalent with respect to overall closed-loop system behavior. In achieving this equivalence a key role is played by the linguistic property of normality. As shown by an illustrative example, the results have application to such complex systems as manufacturing systems, which the qualitative modeling framework adopted     

Supervisory control of real-time discrete-event systems usinglattice theory

The behaviour of timed discrete-event systems (DES's) can be described by sequences of event occurrence times. These sequences can be ordered to form a lattice. Since logical (untimed) DES behaviours described by regular languages also form a lattice, questions of controllability for timed DES's may be treated in much the same manner as they are for untimed systems. In this paper we establish conditions for the controllability of timed DES performance specification which are expressed as inequations on the lattice of sequences. These specifications may take the form of sets of acceptable event occurrence times, maximum or minimum occurrence times, or limits on the separation times between events. Optimal behaviours are found as extremal solutions to these inequations using fixed point results for lattices     

Optimal sensor selection for discrete-event systems with partial observation

For discrete-event systems under partial observation, we study the problem of selection of an optimal set of sensors that can provide sufficient yet minimal events observation information. The sufficiency of the observed information is captured as the fulfillment of a desired formal property. Selection of sensors can be viewed as a selection of an observation mask and also of an equivalence class of events. A sensor set is called optimal if any coarser selection of the corresponding equivalence class of events results in some significant loss of the events observation information. We study an optimal selection of sensors over the set of general "nonprojection" observation masks. We show that this problem is NP hard in general. For mask-monotonic properties, we present a "top-down" and a "bottom-up" algorithm each of polynomial complexity. We show that observerness is not mask-monotonic. We show that the computational complexity can be further improved if the property is preserved under the projection via an intermediary observation mask that is an observer. Our results are obtained in a general setting so that they can be adapted for an optimal selection of sensors for a variety of applications.     

Supervisory control of the structured dynamic discrete-event systems

A new model is developed and studied in this paper—structured dynamic discrete event systems as a theoretical foundation for designing the supervisory control over the set of autonomous components. The composition of the model is defined and the question of a supervisor’s existence (the controllability of the given specification)is studied. Besides, there were stated the basic stages of the design technology in the framework of the introduced controllability analysis model and the supervisors synthesis method.     

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.     

Distributed supervisory control of discrete-event systems with communication delay

This paper identifies a property of delay-robustness in distributed supervisory control of discrete-event systems (DES) with communication delays. In previous work a distributed supervisory control problem has been investigated on the assumption that inter-agent communications take place with negligible delay. From an applications viewpoint it is desirable to relax this constraint and identify communicating distributed controllers which are delay-robust, namely logically equivalent to their delay-free counterparts. For this we introduce inter-agent channels modeled as 2-state automata, compute the overall system behavior, and present an effective computational test for delay-robustness. From the test it typically results that the given delay-free distributed control is delay-robust with respect to certain communicated events, but not for all, thus distinguishing events which are not delay-critical from those that are. The approach is illustrated by a workcell model with three communicating agents.     

Optimality of static control policies in some discrete-event systems

We consider a class of discrete-event systems (DES) that involves the control of resources allocated to tasks under real-time constraints. This is motivated by power-limited wireless environments such as sensor networks, where the objective is to minimize energy consumption while guaranteeing that task deadlines are always met. In obtaining optimal offline controllers for such systems, we prove that simple static control gives the unique optimal solution. The result is of interest because it asserts the optimality of a simple controller that does not require any data collection or processing in environments where the cost of such actions is high.