The infimal closed controllable superlanguage and its applicationin supervisory control

The supervisory control of discrete-event systems is investigated for the case in which nonblocking solutions are deemed inadequate because they are too conservative. For this purpose the infimal closed controllable superlanguage of a given language is studied. Two characterizations of the superlanguage are given, some of its properties are presented, and algorithms for its computation in the general case and in the regular case are proposed. An algorithm for the computation of the supremal controllable sublanguage is presented. It is shown that the computation of the infimal closed controllable superlanguage plays a central role in problems that involve a tradeoff between satisficing and blocking. The completely satisficing solution in supervisory control is characterized, and a general control problem called the supervisory control problem with blocking is introduced     

The infimal prefix-closed and observable superlanguange of a given language

The supervisory control of discrete-event systems under partial observation is examined. In particular, the condition of observability needed to solve the two main existing problems is investigated. A fixed-point characterization of observability is given and is shown to yield an effective test for observability where the system under consideration is specified by regular languages. A formula for the infimal prefix-closed observable superlanguage of a given language is presented. Where the system is specified by regular languages, the formula for the infimal observable language is effectively computable.     

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.     

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.     

Modular Control of Discrete-Event Systems With Coalgebra

Modular supervisory control of discrete-event systems, where the overall system is a synchronous (parallel) product of subsystems, is considered. The main results of this paper are formulations of sufficient conditions for the compatibility between the synchronous product and various operations stemming from supervisory control as supervised product and supremal controllable sublanguages. These results are generalized to the case of modules with partial observations: e.g., modular computation of supremal normal sublanguages is studied. Coalgebraic techniques based on the coinduction proof principle are used in our main results. Sufficient conditions are derived for modular to equal global control synthesis. An algorithmic procedure for checking the new conditions is proposed and the computational benefit of the modular approach is discussed and illustrated by comparing the time complexity of modular and monolithic computation.     

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

Control of Discrete-Event Systems with Partial Observations Using Coalgebra and Coinduction

Control of discrete-event systems with partial observations is treated by concepts and results of coalgebra and coinduction. Coalgebra is part of abstract algebra and enables a generalization of the computer science concept of bisimulation. It can be applied to automata theory and then provides a powerful algebraic tool to treat problems of supervisory control. A framework for control of discrete-event systems with partial observations is formulated in terms of coalgebra. The contributions to control theory are besides the framework, algorithms for supremal normal and supremal normal and controllable sublanguages of the plant.     

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)     

离散事件系统的混合可靠分散监控

在研究基于混合信息的分散监控时,由于部分监控器与部分控制器发生失败,故提出了一种新型的混合可靠分散监控问题.通过修改局部可控事件集与不可控事件集,提出新的可控语言与可靠联合可观察语言定义,进而得到混合可靠分散监控器存在的充分必要条件就是整体约束语言是可靠联合可观察,可控闭的.之后,又通过研究整体约束与混合子约束之间的关系,给出了判别混合可靠分散监控器存在的一个充分条件,即混合子约束分别满足基于谓词的可观察,可控性与基于语言的联合可观察,可控封闭性.     

Bisimilarity control of partially observed nondeterministic discrete event systems and a test algorithm

In this paper, the bisimilarity control of discrete event systems (DESs) under partial observations is investigated, where the plant and the specification are allowed to be nondeterministic. A notation of simulation-based controllability and a synchronization scheme for the supervised system are formalized based on the simulation relation between the specification and the plant. It is shown that the existence of bisimilarity supervisors is characterized by the notions of the simulation-based controllability and the language observability, which extends the traditional results of supervisory control from language equivalence to bisimulation equivalence. In addition, a polynomial algorithm to test the simulation-based controllability is developed by constructing a computing tree. This algorithm together with the test of language observability can be used to check the existence of bisimilarity supervisors.     

Maximizing robustness of supervisors for partially observed discrete event systems

We consider a robust supervisory control problem to synthesize a supervisor for the nominal plant model which maximizes robustness. Cury and Krogh have first addressed this problem by unnecessarily restricting the upper bound of the legal behavior. In our previous work, we have solved the problem without restricting the upper bound of the legal behavior when the specification is described by prefix-closed languages. In this paper, we extend our previous work to the partial (event) observation case. First, we synthesize a supervisor that maximizes robustness. This result shows that robustness can be optimized under partial observation, while permissiveness cannot be optimized in general. We next consider a special case where all the controllable events are observable. In this special case, we synthesize a maximally permissive supervisor for the nominal plant model which maximizes not only the robustness but also permissiveness for the maximal set of admissible plant variations.     

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.     

Reconfigurability of behavioural specifications for manufacturing systems

Reconfigurable manufacturing systems (RMS) support flexibility in the product variety and the configuration of the manufacturing system itself in order to enable quick adjustments to new products and production requirements. As a consequence, an essential feature of RMS is their ability to rapidly modify the control strategy during run-time. In this paper, the particular problem of changing the specified operation of a RMS, whose logical behaviour is modelled as a finite state automaton, is addressed. The notion of reconfigurability of specifications (RoS) is introduced and it is shown that the stated reconfiguration problem can be formulated as a controlled language convergence problem. In addition, algorithms for the verification of RoS and the construction of a reconfiguration supervisor are proposed. The supervisor is realised in a modular way which facilitates the extension by new configurations. Finally, it is shown that a supremal nonblocking and controllable strict subautomaton of the plant automaton that fulfils RoS exists in case RoS is violated for the plant automaton itself and an algorithm for the computation of this strict subautomaton is presented. The developed concepts and results are illustrated by a manufacturing cell example.     

Robust optimal control of regular languages

This paper presents an algorithm for robust optimal control of regular languages under specified uncertainty bounds on the event cost parameters of the language measure that has been recently reported in literature. The performance index for the proposed robust optimal policy is obtained by combining the measure of the supervised plant language with uncertainty. The performance of a controller is represented by the language measure of the supervised plant and is minimized over the given range of event cost uncertainties. Synthesis of the robust optimal supervisory control policy requires at most n iterations, where n is the number of states of the deterministic finite-state automaton (DFSA) model, generated from the regular language of the unsupervised plant behavior. The computational complexity of the control synthesis method is polynomial in n.     

Dynamical consistency in hierarchical supervisory control

A hierarchical control theory is presented founded upon the trace-dynamical consistency property, which is an extension of the notion of dynamical consistency (DC) to the supervisory case of automata with disablable transitions. Partitions of a system state space are considered for which both the trace-DC and the (non-blocking) in-block controllability (IBC) conditions hold; it is shown that low-level non-blocking controllable languages project up to such languages in the high-level system, and that, when the (non-blocking) IBC condition also holds, high-level non-blocking controllable languages map down to such languages in the low-level system. It is demonstrated that the resulting pairs of low-level and high-level languages satisfy a version of the hierarchical consistency condition found in the existing language-based hierarchical supervisory control theory. The structures produced in the formulation of hierarchical control in this paper permit efficient regulator design (and, in particular, repeated re-design) for hierarchy-compatible language specifications; such specifications consist of low-level languages whose maximal controllable sublanguages are realizable by a combination of a high-level (possibly history-dependent) regulator and a set of (state-dependent) low-level regulators (specified block-wise). An algorithm is proposed which facilitates the construction of (non-blocking) IBC partitions of systems with vocalized states. Examples are presented, including a material transfer line with re-entrant flow and a double queue     

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.     

Prefix-primitive annihilators of languages under some operations

This paper studies some properties of prefix-primitive annihilators of languages under the catenation, shuffle product and bi-catenation operations. We prove that for every finite language L under the catenation operation, the left prefix-primitive annihilator of L is not equal to the right prefix-primitive annihilator of L, the left prefix-primitive annihilator of languages is not regular for any finite language, and the left prefix-primitive annihilator of any thin languages is not empty. Moreover, we also characterize the prefix-primitive annihilators of non-empty language under the shuffle product and bi-catenation operations over the alphabet with two letters.     

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     

The infimal controllable and N-observable superpredicate of a givenpredicate

Addresses a decentralized state feedback control problem in discrete-event systems. The problem requires that the set of reachable states in the closed-loop system is in the given admissible range. In particular, the authors investigate the existence of the infimal solution, that is, the infimal controllable and n-observable superpredicate of the minimally acceptable behavior