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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

State observability and condition observability for a class of interacting discrete event systems

This paper introduces the concepts of state observability and condition observability for condition systems, a class of systems composed of discrete state components which interact via discrete binary signals called conditions. Given a set of externally observed conditions, state observability implies that the state of the system can be determined from the observations, and condition observability implies that all unobserved input and output conditions of the system can be determined from the observations. In this paper, we present a class of systems which is state observable and condition observable. We present a method to synthesize an observer system to provide state and condition signal estimates for a single component subsystem.     

Recursive computation of limited lookahead supervisory controls for discrete event systems

We continue the study of limited lookahead policies in supervisory control of discrete event systems undertaken in a previous paper. On-line control of discrete event systems using limited lookahead policies requires, after the execution of each event, the calculation of the supremal controllable sublanguage of a given language with respect to another larger language. These two languages are finite and represented by their tree generators, where one tree is a subtree of the other. These trees change dynamically from step to step, where one step is the execution of one event by the system. We show in this paper how to perform this calculation in a recursive manner, in the sense that the calculation for a new pair of trees can make use of the calculation for the preceding pair, thus substantially reducing the amount of computation that has to be done on-line. In order to make such a recursive procedure possible from step to step, we show how the calculation for a single step (i.e., for a given pair of trees) can itself be performed recursively by means of a backward dynamic programming algorithm on the vertices of the larger tree. These two nested recursive procedures are also extended to the limited lookahead version of the supervisory control problem with tolerance.Research supported in part by the National Science Foundation under grants ECS-9057967 and ECS-9008947. The first two authors also acknowledge support from GE and DEC.     

Maximally permissive mutually and globally nonblocking supervision with application to switching control

A supervisor is said to be mutually nonblocking with respect to a pair of specifications if upon completing a task in any of the specifications, it can continue on to complete the task in the other specification, i.e., the two specifications do not block each other. The notion of mutually nonblocking supervisor was introduced in Fabian and Kumar [2000. Automatica, 36(12), 1863-1869]. In this paper, we present an algorithm of polynomial complexity for computing a maximally permissive mutually and globally nonblocking supervisor. In case such a supervisor does not exist, we present a technique for relaxing the specifications for which a supervisor exists. The algorithms are based on a notion of attractability, and as a special case offer a new way of computing the maximally permissive nonblocking supervisors. The results are then applied to design of maximally permissive switching supervisors so as to allow for switching between the specifications at any time while the system is executing.     

An algebraic approach to supervisory control

Supervisory control problems are formulated in terms of a process model where the mechanism of control is expressed in terms of an algebraic operator with the plant and supervision processes as its arguments. The solution subspaces for supervisory processes restrict the observation and the control capability of supervision. The main result corresponds to decentralized marked supervision under partial observations, and specific cases are derived from this result in a unified, algebraic way. The result and its derivation demonstrate the relative simplicity of the algebraic process formulation.     

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.