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

On supervisory control of sequential behaviors

The authors address the supervisory synthesis problem of controlling the sequential behaviors of discrete-event dynamical systems (DEDSs) under complete and partial information through the use of synchronous composition of the plants and the supervisors. The authors present the notion of complete languages, discuss some of its algebraic properties, and show its close relation to ω-languages. The authors prove that the supremal (closed) complete and controllable sublanguage of a given language exists, and present an algorithm to compute it. They present a closed-form expression for the supremal ω-controllable sublanguage of a given ω-language in terms of the supremal (closed) complete and controllable sublanguage. This closed-form expression suggests that certain operations on a given ω-language can alternatively be achieved by performing certain other similar operations on its prefix (which is a finite language) and then taking the limit (to obtain the desired ω-language). A necessary and sufficient condition for the existence of a supervisor in case of partial observation is presented in terms of ω-observability. Notion of ω-normality is also introduced, and a closed-form expression for the supremal ω-normal sublanguage, in terms of the supremal closed, complete, and normal sublanguage, is presented     

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

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     

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 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 learning-based synthesis approach todecentralized supervisory control of discrete event systems with unknown plants

In this paper, we consider the problem of automatic synthesis of decentralized supervisor for uncertain discrete event systems. In particular, we study the case when the uncontrolled plant is unknown a priori. To deal with the unknown plants, we first characterize the conormality of prefix-closed regular languages and propose formulas for computing the supremal conormal sublanguages; then sufficient conditions for the existence of decentralized supervisors are given in terms of language controllability and conormality and a learning-based algorithm to synthesize the supervisor automatically is proposed. Moreover, the paper also studies the on-line decentralized supervisory control of concurrent discrete event systems that are composed of multiple interacting unknown modules. We use the concept of modular controllability to characterize the necessary and sufficient conditions for the existence of the local supervisors, which consist of a set of local supervisor modules, one for each plant module and which determines its control actions based on the locally observed behaviors, and an on-line learning-based local synthesis algorithm is also presented. The correctness and convergence of the proposed algorithms are proved, and their implementation are illustrated through examples.     

Supervisor Reduction for Discrete-Event Systems

In supervisory control theory (SCT) the supremal supervisor (representing the supremal controllable sublanguage) typically has a large state size (of order the product of state sizes of the plant and specification automata). In this paper, we propose an algorithm which can significantly reduce supervisor size while preserving control action. We also show that finding a supervisor of minimal size is NP-hard.     

Blocking and controllability of Petri nets in supervisory control

This note discusses the use of Petri net languages in supervisory control theory. First it is shown that the trimming of an unbounded Petri net is not always possible and a new class of Petri net languages, that may be generated by nonblocking nets, is defined. Secondly, necessary and sufficient conditions for the existence of a Petri net supervisor, under the hypothesis that the system's behavior and the legal behavior are both Petri net languages, are derived. Finally, by means of an example, it is shown that Petri net languages are not closed under the supremal controllable sublanguage operator     

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     

离散事件系统的一种N步在线监控策略

文中给出了离散事件系统的一种N步在线监控策略.其特点是控制策略取决于系统当前运行的N步后继运行投影或预测,无需计算非能控语言的上限能控子语言,通过适当选取N,仍可保证系统的最优运行.同时还给出了与之相关的一些理论结果.     

计算DES监控中优于闭可识别语言的闭可观子语言

本文给出一种求闭能观子语言的算法，该算法经ｍ步（系统中离散事件个数）收敛；并且证明无论对系统中事件如何排序，由该算法求出的闭能观子语言总包含最大闭可识别子语言。     

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     

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     

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.     

Decidability and closure properties of weak Petri net languages insupervisory control

We extend the class of control problems that can be modeled by Petri nets considering the notion of weak terminal behavior. Deterministic weak languages represent closed-loop terminal behaviors that may be enforced by nonblocking Petri net supervisors if controllable. The class of deterministic weak PN languages is not closed under the supremal controllable sublanguage operator     

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