Supervisory Control of a Class of Concurrent Discrete Event Systems Under Partial Observation

In this paper, we study supervisory control of a class of discrete event systems with simultaneous event occurrences, which we call concurrent discrete event systems, under partial observation. The behavior of the system is described by a language over the simultaneous event set. First, we prove that L_m(G)-closure, controllability, observability, and concurrent well-posedness of a specification language are necessary and sufficient conditions for the existence of a nonblocking supervisor. Next, we synthesize a supervisor that achieves the infimal closed, controllable, observable, and concurrently well-posed superlanguage of a specification language. Finally, we synthesize a supervisor that achieves a maximal closed, controllable, observable, and concurrently well-posed sublanguage of a closed specification language.     

Supervisory control using variable lookahead policies

This paper deals with the efficient on-line calculation of supervisory controls for discrete event systems (DES's) in the framework of limited lookahead control policies (or LLPs) that we introduced in previous papers. In the LLP scheme, the control action after a given trace of events has been executed is calculated on-line on the basis of anN-step ahead projection of the behavior of the DES. To compute these controls, one must calculate after the execution of each event the supremal controllable sublanguage of a finite language with respect to another finite larger language. In our previous work, we showed how the required supremal controllable sublanguage calculation can be performed by using a backward dynamic programming algorithm over the nodes of the tree representation of these two languages. In this paper, we pursue the same approach for the calculation of LLP controls, but instead we adopt a forward calculation procedure over theN-level tree of interest. This forward procedure improves upon previous work by avoiding the explicit consideration of all the nodes of theN-level tree, while still permitting tree-to-tree recursiveness as enabled events are executed by the system. The forward search ends whenever a control decision can be made unambiguously or whenever the boundary of theN-level tree is reached, whichever comes first. This motivates the name Variable Lookahead Policy (or VLP) for this implementation of the LLP supervisory control scheme. This paper presents a general VLP algorithm and studies the properties of several special cases of it. The paper also discusses the implementation of the VLP algorithms and presents computational results regarding the application of these algorithms to a time-varying DES.     

Formulas for a class of controllable and observable sublanguages larger than the supremal controllable and normal sublanguage

In this paper, we give some new methods for synthesis of controllers of discrete event dynamical systems (DEDS) with partial event informations. Given a regular target language L, we construct some effective computable algorithms for computing the controllable and observable sublanguages of L. We show that any one of these controllable and observable sublanguages obtained by our algorithms is larger than the supremal controllable and normal sublanguage of L.     

Online supervisor synthesis for partially observed discrete-eventsystems

A partial information supervisor that generates a class of closed controllable and observable sublanguages of a specified “legal” language is presented. This supervisor has the following features: 1) it can be implemented online (i.e., the disabled event set need only be computed once upon each event observation); 2) the computations of the disabled event set can be performed in O(mn) worst case complexity, where a is the number of states in the legal language generator and m is the number of events; 3) an online supervisor presented previously by Heymann and Lin (1993) is a special case of the new supervisor; and 4) all the languages generated by the new supervisor contain the supremal closed controllable and normal (supCCN) sublanguage of the legal language (in fact, they contain a language developed by Fa et al. (1993) that was shown to contain the supCCN sublanguage)     

Solvability of Centralized Supervisory Control Under Partial Observation

The problem of synthesizing a nontrivial controllable and observable sublanguage of a given non-prefix-closed language is addressed. This problem arises in supervisory control of discrete-event systems, when the objective is to synthesize safe nonblocking supervisors for partially observed systems. The decentralized version of this problem is known to be unsolvable. We show that the centralized version of this problem is solvable by presenting a new algorithm that synthesizes a nontrivial controllable and observable sublanguage of the given non-prefix-closed language, if one exists. We also show that the union of all nonblocking solutions to the associated supervisory control problem can be expressed as the union of all regular nonblocking solutions. This work was done when the first author was at the University of Michigan as a Ph.D. student.     

On computation of supremal controllable, normal sublanguages

In this paper, we present an algorithm for the computation of the controllable, normal sublanguage of a given language, encountered in the solution of the supervisory control of discrete-event systems under partial observation. The algorithm produces the desired result under certain assumptions on the plant and the event projection map. In particular, the plant has to be nonblocking. The advantage of the algorithm over the solution available in the literature is that it does not involve iterations on the supremal controllable sublanguage and supremal normal sublanguage operators.     

A MODIFIED METHOD FOR SUPERVISOR SPECIFICATION AND SYNTHESIS OF A CLASS OF DISCRETE EVENT SYSTEMS

In this paper, a model‐refining method is proposed to alleviate the complexity involved in specification interpretation of DES control problems. The legal constraint language is defined in terms of illegal states and events in contrast with constructing the automaton of the specification language. This method could provide a more intuitive view of the DES control problem and would be suitable for practical implementation. Two examples, which have commonly been used in the literature, are employed to show the efficiency of the proposed method. Further, under this framework, it is shown that the supremal controllable sublanguage can take a simpler form based on the concept of an illegal state set. A state‐based supervisor synthesis procedure is presented, and a simple example is provided.     

Characterizations and effective computation of supremal relatively observable sublanguages

Recently we proposed relative observability for supervisory control of discrete-event systems under partial observation. Relative observability is closed under set unions and hence there exists the supremal relatively observable sublanguage of a given language. In this paper we present a new characterization of relative observability, based on which an operator on languages is proposed whose largest fixpoint is the supremal relatively observable sublanguage. Iteratively applying this operator yields a monotone sequence of languages; exploiting the linguistic concept of support based on Nerode equivalence, we prove for regular languages that the sequence converges finitely to the supremal relatively observable sublanguage, and the operator is effectively computable. Moreover, for the purpose of control, we propose a second operator that in the regular case computes the supremal relatively observable and controllable sublanguage.     

Supervisory control using augmented languages in discrete event systems

This paper introduces the concept of an augmented (super) language of a specified language and studies its application to finite state supervisory control. First, we investigate several properties of an augmented language, especially related to controllability of the specified language. We propose an algorithm for the computation of a controllable sublanguage for which a finite state supervisor exists, using an augmented language, and show a sufficient condition for the controllable sublanguage to be supremal. It is shown, however, that such a finite state supervisor is sometimes blocking. Moreover, we discuss the relationship between the Wonham-Ramadge algorithm and our proposed one.     

On-line control of partially observed discrete event systems

It is well known that the design of supervisors for partially observed discrete-event systems is an NP-complete problem and hence computationally impractical. Furthermore, optimal supervisors for partially observed systems do not generally exist. Hence, the best supervisors that can be designed directly for operation under partial observation are the ones that generate the supremal normal (and controllable) sublanguage. In the present paper we show that a standard procedure exists by which any supervisor that has been designed for operation under full observation, can be modified to operate under partial observation. When the procedure is used to modify the optimal full-observation supervisor (i.e., the one that generates the supremal controllable language), the resultant modified supervisor is at least as efficient as the best one that can be designed directly (that generates the supremal normal sublanguage). The supervisor modification algorithm can be carried out on-line with linear computational complexity and hence makes the control under partial observation a computationally feasible procedure.     

Supervisory control of discrete event systems with communication delays and partial observations

This paper presents necessary and sufficient conditions for the existence of a nonblocking supervisor that achieves a given language specification for a discrete event system (DES) with communication delays and partial observations. In many practical situations, some uncontrollable events can subsequently occur before a proper control action is applied to the DES due to delays in sensing, communicating, and actuating. Moreover, some of the uncontrollable events may be unobservable. To achieve a given language specification in such situations, this paper presents a language property called delay observability which assures no confliction in making a decision for legal controllable events under partial observation and delay communication.     

Supervisory control of fuzzy discrete event systems.

To cope with situations in which a plant's dynamics are not precisely known, we consider the problem of supervisory control for a class of discrete event systems modeled by fuzzy automata. The behavior of such discrete event systems is described by fuzzy languages; the supervisors are event feedback and can only disable controllable events with any degree. In this new sense, we present a necessary and sufficient condition for a fuzzy language to be controllable. We also study the supremal controllable fuzzy sublanguage and the infimal controllable fuzzy superlanguage.     

Relative coobservability for decentralised supervisory control of discrete-event systems

In this paper, we study the concept of relative coobservability in decentralised supervisory control of discrete-event systems under partial observation. This extends our previous work on relative observability from a centralised setup to a decentralised one. A fundamental concept in decentralised supervisory control is coobservability (and its several variations); this property is not, however, closed under set union, and hence there generally does not exist the supremal element. Our proposed relative coobservability, although stronger than coobservability, is algebraically well behaved, and the supremal relatively coobservable sublanguage of a given language exists. We present a language-based algorithm to compute this supremal sublanguage; the algorithm allows straightforward implementation using off-the-shelf algorithms. Moreover, relative coobservability is weaker than conormality, which is also closed under set union; unlike conormality, relative coobservability imposes no constraint on disabling unobservable controllable events.     

Bisimulation, the Supervisory Control Problem and Strong Model Matching for Finite State Machines

A fundamental relationship between the controllability of a language with respect to another language and a set of uncontrollable events in the Supervisory Control Theory initiated by (Ramadge and Wonham, 1989) and bisimulation of automata models is derived. The theoretical results relating bisimulation to controllability support an efficient solution to the Basic Supervisory Control Problem. Using (Fernandez, 1990) generalization of the partition refinement algorithm of (Paige and Tarjan, 1987), it is possible to find a partition which represents the supremal controllable sublanguage of an automaton with respect to the language of another automaton and a set of events in a worst-case running time of O( m log(n)), where m is the number of transitions and n is the number of states. Utilizing the bisimulation property of language controllability and derived relationships between automata languages and input/output finite-state machine behaviors, a precise relationship is formally derived between Supervisory Control Theory and the system-theoretic problem posed by (DiBenedetto et al., 1994) called Strong Input/Output FSM Model Matching. Specifically, it is proven that in deterministic settings instances of each problem can be mapped to the other framework and solved.     

Supervisor Synthesis for Real-Time Discrete Event Systems

This paper introduces a formal framework to logically analyze and control real-time discrete event systems (RTDESs). Time Petri nets are extended to controlled time Petri nets (CtlTPNs) to model the dynamics of RTDESs that can be controlled by real-time supervisors. The logical behaviors of CtlTPNs are represented by control class graphs (CCGs) which are untimed automata with timing and control information in their state transition labels. We prove that the CCG corresponding to a CtlTPN expresses completely the logical behavior of the CtlTPN. The real-time supervisor is based on a nondeterministic logical supervisor for the CCG, including the delay for control computations to ensure the supervisor is acceptable in a true real-time environment. We prove the existence of a unique maximal controllable sublanguage of a given specification language and present an algorithm to construct the sublanguage. We also prove that the real-time supervisor meets the prespecified real-time behavior and present an online control algorithm to implement real-time supervisors. The concepts and algorithms are illustrated for an example of packet reception processes in a communication network.     

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.     

On the supremal controllable sublanguage in the discrete-eventmodel of nondeterministic hybrid control systems

This paper is concerned with the logical control of hybrid control systems (HCS). It is assumed that a discrete-event system (DES) plant model has already been extracted from the continuous-time plant. The problem of hybrid control system design can then be solved by applying logical DES controller synthesis techniques to the extracted DES plant. Traditional DES synthesis methods, however, are not always applicable since the extracted plant DES will often exhibit nondeterministic transitions. This paper presents an extension of certain DES controller synthesis techniques to the nondeterministic control automaton found in HCS. In particular, this paper derives a formula computing the supremal controllable sublanguage of a given specification language under the assumption that the DES plant exhibits nondeterministic transitions     

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.     

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.     

Distributed computation of supremal conditionally controllable sublanguages

In this paper, we further develop the coordination control framework for discrete-event systems with both complete and partial observations. First, a weaker sufficient condition for the computation of the supremal conditionally controllable sublanguage and conditionally normal sublanguage is presented. Then we show that this condition can be imposed by synthesising a-posteriori supervisors. The paper further generalises the previous study by considering general, non-prefix-closed languages. Moreover, we prove that for prefix-closed languages the supremal conditionally controllable sublanguage and conditionally normal sublanguage can always be computed in the distributed way without any restrictive conditions we have used in the past.