On the language generated under fully decentralized supervision

This paper studies the language generated under fully decentralized supervision proposed by Kozak and Wonham (1995). The author assumes that desirable behavior is specified as a closed language. A closed-form expression for the language generated under fully decentralized supervision is presented. It is shown that the generated language is larger than the supremal closed, controllable, and strongly decomposable sublanguage. Moreover, a necessary and sufficient condition is derived for the generated language to be the supremal closed and controllable sublanguage     

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.     

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.     

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

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.     

An algorithm for computing the mask value of the supremal normalsublanguage of a legal language

We consider the problem of finding the mask value of the supremal normal sublanguage L_R of some given language L. We describe a straightforward algorithmic solution that can be applied to existing off-line procedures for determining the supremal controllable and normal sublanguage of L and that does not require an explicit calculation of L _R. This problem is fundamental because it is related to the supervisory control problem under partial observation. Our algorithm applies only to closed languages     

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)     

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.     

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.     

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     

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.     

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.     

A modified normality condition for decentralized supervisory control of discrete event systems

In this paper, we study nonblocking decentralized supervisory control of discrete event systems. We introduce a modified normality condition defined in terms of a modified natural projection map. The modified normality condition is weaker than the original one and stronger than the co-observability condition. Moreover, it is preserved under union. Given a marked language specification, there exists a nonblocking decentralized supervisor for the supremal sublanguage which satisfies L_m(G)-closure, controllability, and modified normality. Such a decentralized supervisor is more permissive than the one which achieves the supremal L_m(G)-closed, controllable, and normal sublanguage.     

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     

On supremal languages of classes of sublanguages that arise in supervisor synthesis problems with partial observation

This paper characterizes the class of closed and (M, N)-recognizable languages in terms of certain structural aspects of relevant automata. This characterization leads to algorithms that effectively compute the supremal (M, N)-recognizable sublanguage of a given language. One of these algorithms is used, in an alternating manner with an algorithm which yields the supremal (∑_u, N)-invariant resulting algorithm is proved. An example illustrates the use of these algorithms. This research was supported in part by the Air Force Office of Scientific Research under Grant No. AFOSR-86-0029, in part by the National Science Foundation under Grant No. ECS-8412100, and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract No. F49620-86-C-0045     

Supervisory control of deterministic Petri nets with regularspecification languages

Algorithms for computing a minimally restrictive control in the context of supervisory control of discrete-event systems have been well developed when both the plant and the desired behaviour are given as regular languages. In this paper the authors extend such prior results by presenting an algorithm for computing a minimally restrictive control when the plant behaviour is a deterministic Petri net language and the desired behaviour is a regular language. As part of the development of the algorithm, the authors establish the following results that are of independent interest: i) the problem of determining whether a given deterministic Petri net language is controllable with respect to another deterministic Petri net language is reducible to a reachability problem of Petri nets and ii) the problem of synthesizing the minimally restrictive supervisor so that the controlled system generates the supremal controllable sublanguage is reducible to a forbidden marking problem. In particular, the authors can directly identify the set of forbidden markings without having to construct any reachability tree     

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.     

非阻塞监控器设计中的语言优化方法

本文研究在设计非阻塞监控器时所涉及到的语言的优化方法，首先给出了Ｌｍ（Ｇ）闭语言的计算公式，然后提出了能控Ｌｍ（Ｇ）闭子语言的逐级优化途径，对于目前获得的部分优化语言的封闭解进行了总结，并对各语言类之间的关系进行了分析。     

Supervisory control of partially observed discrete event systems with arbitrary control patterns

In this paper, we study supervisory control of partially observed discrete event systems with arbitrary control patterns. First, we present a necessary and sufficient condition for the existence of a supervisor for a given non-empty and closed language K. Next, we consider the case where the language K does not satisfy the condition. We prove that there always exists its infimal superlanguage for which there exists a supervisor when the set Gamma of control patterns is closed under intersection. This infimal superlanguage is the optimal solution larger than K. On the other hand, when Gamma is closed under union, there does not necessarily exist its supremal sublanguage for which there exists a supervisor. In other words, the optimal solution smaller than K does not exist in general. So, in this case, we present a suboptimal solution smaller than K.