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.     

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.     

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     

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 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.     

Opacity of discrete-event systems under nondeterministic observation mechanism

For some practical systems modeled by discrete-event systems (DESs), the event observation mechanism may be no longer static/fixed due to sensor faults/failures, packet loss, and/or measurement uncertainties. It is required to redefine the observations of events. Therefore, it is interesting to reconsider the opacity in the context of abnormal conditions as mentioned. In this paper, we extend notions of initial-state opacity (ISO), current-state opacity (CSO), and initial-and-final-state opacity (IFSO) in a standard setting to an advanced framework of nondeterministic observations (i.e., the event-observation mechanism is state-dependent and nondeterministic) by taking the output-observation-equivalence instead of the natural projection-equivalence into account. To efficiently verify them, we construct three new matrix-based information structures in this advanced framework called an initial-state estimator, a current-state estimator, and an initial-and-final-state estimator using the Boolean semi-tensor product (BSTP) theory. Accordingly, the matrix-based criteria for verifying these three types of opacity are given, respectively. Computational complexity analysis as well as illustrative examples are also provided for the proposed results.     

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.     

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.     

Supervisor localisation for large-scale discrete-event systems under partial observation

ABSTRACT

Recently we developed partial-observation supervisor localisation, a top-down approach to distributed control of discrete-event systems (DES) under partial observation. Its essence is the decomposition of the partial-observation monolithic supervisor into partial-observation local controllers for individual controllable events. In this paper, we extend the partial-observation supervisor localisation to large-scale DES, for which the monolithic supervisor may be incomputable. Specifically, we first employ an efficient heterarchical supervisor synthesis procedure to compute a heterarchical array of partial-observation decentralised supervisors and partial-observation coordinators. Then, we localise each of these supervisors/coordinators into partial-observation local controllers. This procedure suggests a systematic approach to the distributed control of large-scale DES under partial observation. The results are illustrated by a system of automatic guided vehicles serving a manufacturing workcell.     

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.     

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     

Online control of discrete-event systems: A survey

In control theory, as in other areas of engineering research, there is an inherent tension between the breadth of a technique’s applicability and its mathematical tractability. For the area of discrete-event systems (DES), this manifested itself in a theory of supervisory control that originally provided correct-by-construction guarantees for offline solutions to a restricted kind of deterministic process. Follow-on work extended the reach of these techniques to a number of new settings, notably the development of online control without sacrificing any of the original DES performance guarantees. The ability to enact online control opened the door to applying DES techniques to the adaptive control processes presented by modern technologies: processes with dynamic and time-varying natures, whose characteristics may be understood poorly or not at all. Although many works have built on the seminal work of online control in DES, we believe that these ideas have not reached their full potential due to the difficulty in translating them to adjacent fields. In this survey, we look back at 30 years of research concerning the online control of DES and closely related limited lookahead policies with an eye to making the works accessible to practitioners in the broader control theory and artificial intelligence communities. We conclude with some thoughts on future research directions for the further development and application of online DES control techniques to problems requiring intelligent control in our modern world.     

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.