Nonblocking supervisory control of timed discrete event systems under communication delays: The existence conditions

This paper addresses the problem of nonblocking supervisory control of timed discrete event systems under communication delays based on the framework proposed by Brandin and Wonham. For such a system, a supervisory control command could be applied to the system after some time-delay limited by a finite bound corresponding to the maximal number of tick occurrences, and some uncontrollable events may unexpectedly occur within this time-delay. This paper presents the necessary and sufficient conditions for the existence of a nonblocking supervisor that can achieve a given language specification in consideration of such delayed communications.     

Decentralized supervisory control of discrete event systems with communication delays based on conjunctive and permissive decision structures

In many practical discrete event systems (DESs), some unexpected and uncontrollable events can subsequently occur before a proper control action is actually applied to a plant due to communication delays. For such DESs, this paper investigates necessary and sufficient conditions for the existence of a nonblocking decentralized supervisor that can correctly achieve a given language specification when the decentralized supervisor is assumed to have a conjunctive and permissive decision structure. In particular, this paper presents a notion of delay-coobservability for a given language specification and shows that it is a key condition for the existence of such a decentralized supervisor.     

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.     

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.     

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.     

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.     

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.     

Delay-coobservability and its algebraic properties for the decentralized supervisory control of discrete event systems with communication delays

In networked control systems, uncontrollable events may unexpectedly occur at a plant before a proper control command is applied to it due to communication delays. In this paper, we address the problem of decentralized supervisory control under such communication delays based on the C&P (conjunctive and permissive) and D&A (disjunctive and antipermissive) decision architecture. In particular, for the existence of a decentralized supervisor, we present the notion of delay-coobservability of a given language specification and a polynomial-time algorithm for verifying it. In addition, algebraic properties of the delay-coobservability are investigated. We further present a synthesis method of the decentralized supervisor for practical usefulness.     

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’?     

Decentralized control of networked discrete event systems with communication delays

In many practical systems, supervisory control is not performed by one centralized supervisor, but by multiple local supervisors. When communication networks are used in such a system as the medium of information transmission, the communication channels between local supervisors and the system to be controlled will unavoidably result in communication delays. This paper investigates how to use these local supervisors to control the system in order to satisfy given specifications even under communication delays. The specifications are described by two languages: a minimal required language which specifies the minimal required performance that the supervised system must have and a maximal admissible language which specifies the maximal boundary that the supervised system must be in. The results show that if the control problem is solvable, then there exists the minimal control policy which can be calculated based on state estimates. Furthermore, we derive algorithms to check whether the control problem is solvable or not.     

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.     

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.     

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.     

Decentralized global robust stabilization of a class of interconnected minimum-phase nonlinear systems

This paper focuses on a class of large-scale interconnected minimum-phase nonlinear systems with parameter uncertainty and nonlinear interconnections. The uncertain parameters are allowed to be time-varying and enter the systems nonlinearly. The interconnections are bounded by nonlinear functions of states. The problem we address is to design a decentralized robust controller such that the closed-loop large-scale interconnected nonlinear system is globally asymptotically stable for all admissible uncertain parameters and interconnections. It is shown that decentralized global robust stabilization of the system can be achieved using a control law obtained by a recursive design method together with an appropriate Lyapunov function.     

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.     

Decentralized state feedback control of discrete event systems

In this paper, we consider decentralized state feedback control of discrete event systems with a (global) control specification given by a predicate. In this framework, instead of a global state feedback, each local state feedback controls a part of the system according to local information so that global behaviors satisfy the global control specification. We introduce the notion of n-observability of predicates, and present necessary and sufficient conditions for the existence of a decentralized state feedback which achieves the global control specification.     

Control of large scale discrete event systems: Task allocation and coordination

To control a large scale discrete event system, decentralized control and hierarchical control can be used, where several local supervisors are used to control events in local sites and a coordinator is used to coordinate the local supervisors. Two important problems that need to be solved in such a control architecture are task allocation and coordination. That is, how to allocate tasks to the supervisors, and how to coordinate those tasks. We propose and solve a task allocation problem of assigning tasks to the local supervisors and a minimal intervention problem of coordinating tasks so that the intervention by the coordinator is minimal.     

Diagnosability of discrete event systems and its applications

As man-made systems become more and more complex, diagnostics of component failures is no longer an easy task that can be performed based on experience and intuition. Therefore, it is important to develop a systematic approach to diagnostic problems. Diagnostics can be done either on-line or off-line. By on-line diagnostics, we mean diagnostics performed while the system to be diagnosed is in normal operation. On the other hand, in off-line diagnostics, the system is not in normal operation. We will study both on-line and off-line diagnostics in this paper and identify main features and differences of these two types of diagnostics. We will also introduce the concept of diagnosability and study its properties, all in the framework of discrete event systems. This study is motivated by diagnostic problems in the automotive industry and we will emphasize its applications.