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.     

Mutually nonblocking supervisory control of discrete event systems

A single maximally permissive and nonblocking supervisor to simultaneously fulfill several marked specifications pertaining to a single plant is investigated. Given a plant G and two marked specification languages K₁ and K₂, a supervisor S is said to be (K₁,K₂)-mutually nonblocking if (for i,j=1,2)

Full-size image

. This means that when the closed-loop system marks a trace of K_i, then it is always able to continue to a trace of K_j, also marked in the closed-loop system. Thus, the controlled system can execute traces within one specification while always being able to continue a trace of the other and hence not blocking the other specification. A complete, globally nonblocking and (K₁,K₂)-mutually nonblocking supervisor such that L_m(G || S)K₁K₂ exists if and only if there exists a controllable mutually nonblocking sublanguage of the union of the specifications. There does exist a supremal such language. Furthermore, in the case that each specification is nonconflicting with respect to the prefix-closure of the other, this supremal language can be calculated by expressing it as the union of the supremal prefix-bounded sublanguages of the respective specifications. Finally, we show that the multiply nonblocking supervision of Thistle, Malhame, Hoang and Lafortune ((1997). Internal Report, Dept. de genie electrique et de genie informatique, Ecole Polytechnique de Montreal, Canada) is equivalent to globally and mutually nonblocking supervision.     

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.     

Robust and adaptive supervisory control of discrete event systems

Both robust and adaptive supervisory control in discrete-event systems are discussed. It is assumed that the system G to be controlled is not known exactly. It is only known either that it belongs to a set or that it has certain lower and upper bounds. The task of robust supervision is to synthesize a supervisor that realizes a given desired behavior for all possible G. A necessary and sufficient condition for the existence of such a robust supervisor is derived. Based on this condition, a robust supervisory control and observation problem of synthesizing a robust supervisor whose behavior is both legal and acceptable is solved. Adaptive supervision is discussed. As the system progresses, the information on occurrences of events may help to resolve or reduce uncertainties     

Decentralized supervisory control of nondeterministic discrete event systems: The existence condition of a robust and nonblocking supervisor

This paper addresses a decentralized supervisory control problem for an uncertain discrete event system (DES) modeled by a set of possible nondeterministic automata with unidentified internal events. For a given language specification, we present the existence condition of a robust and nonblocking decentralized supervisor that achieves this specification for any nondeterministic model in the set. In particular, we show that the given language specification can be achieved based on the properties of its controllability and coobservability with respect to the overall nominal behavior of the uncertain DES. It is further shown that the existence of a nonblocking decentralized supervisor can be examined with a trajectory model of the language specification.     

Robust and fault-tolerant supervisory control of discrete event systems with partial observation and model uncertainty

This paper proposes the notions of faults and failures in discrete event systems (DESs) with partial observation. They are associated with controllability and an observability property. The proposed notions are used to address the notion of tolerable fault event sequences which represents fault-tolerant behaviour of systems as a desired specification. A robust and fault-tolerant supervisor is a controller which is robust to model uncertainty and guarantees fault-tolerant behaviour of a system. In this paper we present necessary and sufficient conditions for the existence of a robust and fault-tolerant supervisor. The developed conditions capture the concepts of controllability and observability which are cores in the control of DESs with partial observation     

Robust supervisory control of a class of timed discrete event systems under partial observation

This paper studies robust supervisory control of timed discrete event systems proposed by Brandin and Wonham. Given a set of possible models which includes the exact model of the plant, the objective is to synthesize a robust supervisor such that it achieves legal behavior for all possible models. We show that controllability for each possible model and observability for a suitably defined aggregate model are necessary and sufficient conditions for the existence of a solution to the robust supervisory control problem. Moreover, when there does not exist a solution, a maximally permissive robust supervisor is synthesized under the assumption that all controllable events are observable.     

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

研究了混合信息下的分散监控综合问题.首先提出δ-可观察(hδ-可观察)可控闭语言是(状态部分可观察下)状态反馈综合解存在的充要条件,并由此得到n-联合可观察、可控闭的系统约束是保证混合分散监控器存在的充要条件,进而得到纯分散监控器(控制器)存在的充要条件为n-可观察(n-hδ-可观察)可控闭语言被满足.最后,又通过研究系统约束与混合约束的关系,提出混合分散监控器存在的充分条件是可观察、可控闭语言与可观察可控谓词被满足.     

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

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

Grid automata and supervisory control of dense real-time discrete event systems

We present a generalization of the classical supervisory control theory for discrete event systems to a setting of dense real-time systems modeled by Alur and Dill timed automata. The main problem involved is that in general the state space of a timed automaton is (uncountably) infinite. The solution is to reduce the dense time transition system to an appropriate finite discrete subautomaton, the grid automaton, which contains enough information to deal with the timed supervisory control problem (TSCP). The plant and the specifications region graphs are sampled for a granularity defined in a way that each state has an outgoing transition labeled with the same time amount. We redefine the controllability concept in the context of grid automata, and we provide necessary and sufficient solvability conditions under which the optimal solution to centralized supervisory control problems in timed discrete event systems under full observation can be obtained. The enhanced setting admits subsystem composition and the concept of forcible event. A simple example illustrates how the new method can be used to solve the TSCP.     

A pseudometric in supervisory control of probabilistic discrete event systems

The focus of this paper is the pseudometric used as a key concept in our previous work on optimal supervisory control of probabilistic discrete event systems. The pseudometric is employed to measure the behavioural similarity between probabilistic systems, and initially was defined as a greatest fixed point of a monotone function. This paper further characterizes the pseudometric. First, it gives a logical characterization of the pseudometric so that the distance between two systems is measured by a formula that distinguishes between the systems the most. A trace characterization of the pseudometric is then derived from the logical characterization, characterizing the similarity between systems from a language perspective. Further, the solution of the problem of approximation of a given probabilistic generator with another generator of a prespecified structure is suggested such that the new model is as close as possible to the original one in the pseudometric. The significance of the approximation is then discussed, especially with respect to previous work on optimal supervisory control of probabilistic discrete event systems.     

Hierarchical supervisory control of discrete event systems with model uncertainty

This paper addresses the problem of hierarchical control of discrete event systems with model uncertainty. To achieve the hierarchical consistency under model uncertainty, we derive the conditions on the properties of the information channel between a low level and a high level and the structure of the low level system with model uncertainty. The feasibility of the results obtained is demonstrated in the hierarchical control of a work cell.     

Design of nonblocking modular supervisors using event priorityfunctions

A new scheme for the modular control of discrete event systems is presented and studied. This scheme, called modular control with priorities (MCP), is an extension of earlier works on modular control in the realm of the supervisory control theory of discrete event systems. The key feature of this scheme is the use of a priority mechanism based on the priority functions of individual supervisors in the process of combining the control actions of individual supervisors. This approach is motivated by both theoretical and practical considerations. The main objective is to use priority functions to mitigate or eliminate the problem of blocking that originates in conventional modular control. In this paper, we first show how to design individual supervisors so that they can operate under MCP. We then show how MCP operates and discuss the resulting properties of this approach. Finally, we present several algorithms for priority assignment to obtain nonblocking behavior under MCP. A motivating example from the area of telecommunications is given     

On tolerable and desirable behaviors in supervisory control of discrete event systems

We formulate and solve a new supervisory control problem for discrete event systems. The objective is to design a logical controller—or supervisor—such that the discrete event system satisfies a given set of requirements that involve event ordering. The controller must deal with a limited amount of controllability in the form of uncontrollable events. Our problem formulation considers that the requirements for the behavior (i.e., set of traces) of the controlled system are specified in terms of a desired behavior and a larger tolerated behavior. Due to the uncontrollable events, one may wish to tolerate behavior that sometimes exceeds the ideal desired behavior if overall this results in achieving more of the desired behavior. The general solution of our problem is completely characterized. The nonblocking solution is also analyzed in detail. This solution requires the study of a new class of controllable languages. Several results are proved about this class of languages. Algorithms to compute certain languages of interest within this class are also presented.Research supported in part by the National Science Foundation under grants ECS-8707671, ECS-9057967, and ECS-9008947.     

Reliable supervisory control for general architecture of decentralized discrete event systems

In this paper, we investigate the reliable decentralized supervisory control of discrete event systems (DESs) under the general architecture, where the decision for controllable events is a combination of the conjunctive and disjunctive fusion rules. By reliable control, we mean that the performance of closed-loop systems will not be degraded even in the face of possible failures of some local supervisors. The main contributions are twofold. First, a necessary and sufficient condition for the existence of a k-reliable decentralized supervisor under the general architecture is presented after introducing notions of -controllability and k-reliable -coobservability. Second, a polynomial-time algorithm to verify the reliable -coobservability of a specification is proposed.     

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.     

Modular nonblocking state feedback control of discrete event systems and its application to dynamic oligopolistic markets

This article addresses a modular state feedback supervisory control problem where two local controllers should achieve a common control objective against another local controller. Each local controller has its own control objective described as a predicate. This article also addresses a nonblocking modular control problem in which a discrete event system controlled by three local controllers tends to reach the common marked states of two local controllers that are, however, prohibited by the third local controller. For a case study, we apply the proposed theory to an oligopolistic market composed of two firms and one government. Two oligopolistic firms have a common objective to maximise their total profit through collusion. However, the government prevents them from engaging in collusion. We show that the modular supervisory control theory presented in this article can be used to solve the problem of ‘how can the firms maximise their total profit against the intervention of government’?     

Robust supervisory control of timed discrete event systems under partial observation based on eligible time bounds: The existence conditions

This paper addresses a supervisory control problem for uncertain timed discrete event systems (DESs) under partial observation. An uncertain timed DES to be controlled is represented by a set of possible timed models based on the framework of Brandin and Wonham [(1994). Supervisory control of timed discrete event systems. IEEE Transactions on Automatic Control, 39(2), 329-342]. To avoid the state space explosion problem caused by tick events in the timed models, a notion of eligible time bounds is proposed for a single timed model obtained from the set of all possible timed models. Based on this notion, we present the necessary and sufficient conditions for the existence of a robust supervisor achieving a given language specification for the single timed model. Moreover, we show that the robust supervisor can also achieve the specification for any timed model in the set.     

Predictive models of human supervisory control behavioral patterns using hidden semi-Markov models

Behavioral models of human operators engaged in complex, time-critical high-risk domains, such as those typical in Human Supervisory Control (HSC) settings, are of great value because of the high cost of operator failure. We propose that Hidden Semi-Markov Models (HSMMs) can be employed to model behaviors of operators in HSC settings where there is some intermittent human interaction with a system via a set of external controls. While regular Hidden Markov Models (HMMs) can be used to model operator behavior, HSMMs are particularly suited to time-critical supervisory control domains due to their explicit representation of state duration. Using HSMMs, we demonstrate in an unmanned vehicle supervisory control environment that such models can accurately predict future operator behavior both in terms of states and durations.     

Real-time preemptive scheduling of sporadic tasks based on supervisory control of discrete event systems

This paper presents a preemptive scheduling scheme for real-time systems with sporadic tasks based on the supervisory control theory of discrete event systems. In particular, we present a systematic method of computing a schedulable language that includes all achievable sequences that meet the given deadlines of accepted sporadic tasks. A supervisor that achieves the schedulable language corresponds to a scheduler that can secure the deadlines of all accepted tasks. We further show that the schedulable language includes the decisions on whether a scheduler accepts or rejects a newly arrived sporadic task.