Robust and nonblocking supervisory control of nondeterministicdiscrete event systems using trajectory models

This note considers the robust supervisory control problems of uncertain nondeterministic discrete-event systems (DESs). The uncertain DES to be controlled is assumed to be modeled as a set of some possible nondeterministic automata. Then, the control objective is to achieve a given language specification and guarantee the nonblockingness of any nondeterministic automata of the set which are controlled by a robust nonblocking supervisor. Based on trajectory models, this note presents the necessary and sufficient conditions for the existence of a robust nonblocking supervisor for a given uncertain nondeterministic DES     

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.     

Bisimilarity Control of Partially Observed Deterministic Systems

Control for safety and nonblockingness using a deterministic supervisor requires the specification language be controllable and observable (under the setting that marking is also decided by a supervisor). We argue that there exist cases where the above properties do not hold, yet a safe and nonblocking control can be synthesized by allowing the supervisor to be nondeterministic. Use of a nondeterministic supervisor yields a controlled system that is nondeterministic for which a language equivalence only preserve the safety but not the nonblocking property, and so instead we require the stronger equivalence of bisimilarity (which preserves "sequential" behavior such as safety as well as "branching" behavior such as nonblockingness). This motivates us to consider control of deterministic systems for achieving bisimulation equivalence to possibly nondeterministic specifications. We introduce the notions of state-achievability (SA) and state-achievability-bisimilar (SAB) as part of the existence condition, and develop effective algorithms for verify the existence conditions as well as for synthesizing a supervisor when the existence condition holds. We show that the complexity of verifying the existence of a controller is polynomial, whereas that of computing a controller (when one exists) is singly exponential. The proposed approach can be applied to enforce any property that depends on branching and sequential behavior.     

Supervisory control of discrete event systems with communication delays and partial observations

This paper presents necessary and sufficient conditions for the existence of a nonblocking supervisor that achieves a given language specification for a discrete event system (DES) with communication delays and partial observations. In many practical situations, some uncontrollable events can subsequently occur before a proper control action is applied to the DES due to delays in sensing, communicating, and actuating. Moreover, some of the uncontrollable events may be unobservable. To achieve a given language specification in such situations, this paper presents a language property called delay observability which assures no confliction in making a decision for legal controllable events under partial observation and delay communication.     

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.     

Reliable Decentralized Supervisory Control For Marked Language Specifications

We consider a discrete event system controlled by a decentralized supervisor consisting of n local supervisors. In our previous work, we have studied reliable decentralized supervisory control for closed language specifications. In this paper, we extend this work to the specifications given by marked languages. A decentralized supervisor is said to be k‐reliable (1 ∞ k ∞ n) if it exactly achieves a specification language without blocking under possible failures of any less than or equal to n ‐ k local supervisors. We present necessary and sufficient conditions for the existence of a k‐reliable decentralized supervisor. Then we define a weaker version of k‐reliability, called weak k‐reliability, by relaxing the nonblocking requirement. We obtain necessary and sufficient conditions for the existence of a weakly k‐reliable decentralized supervisor. Moreover, we propose an iterative scheme for computing a sublanguage of a specification for which the existence conditions of a weakly k‐reliable decentralized supervisor are satisfied.     

Reliable decentralized supervisory control of discrete eventsystems

We consider a discrete event system controlled by a decentralized supervisor consisting of n local supervisors, and formulate a new decentralized supervisory control problem, called a reliable decentralized supervisory control problem. A decentralized supervisor is said to be k-reliable (1相似文献   

Polynomial synthesis of supervisor for partially observed discrete-event systems by allowing nondeterminism in control

We study the supervisory control of discrete-event systems (DESs) under partial observation using nondeterministic supervisors. We formally define a nondeterministic control policy and also a control & observation compatible nondeterministic state machine and prove their equivalence. The control action of a nondeterministic supervisor is chosen online, nondeterministically from among a set of choices determined offline. Also, the control action can be changed online nondeterministically (prior to any new observation) in accordance with choices determined offline. The online choices, once made, can be used to affect the set of control action choices in future. We show that when control is exercised using a nondeterministic supervisor, the specification language is required to satisfy a weaker notion of observability, which we define in terms of recognizability and achievability. Achievability serves as necessary and sufficient condition for the existence of a nondeterministic supervisor, and it is weaker than controllability and observability combined. When all events are controllable, achievability reduces to recognizability. We show that both existence, and synthesis of nondeterministic supervisors can be determined polynomially. (For deterministic supervisors, only existence can be determined polynomially.) Both achievability and recognizability are preserved under union, and also under intersection (when restricted over prefix-closed languages). Using the intersection closure property we derive a necessary and sufficient condition for the range control problem for the prefix-closed case. Unlike the deterministic supervisory setting where the complexity of existence is exponential, our existence condition is polynomially verifiable, and also a supervisor can be polynomially synthesized.     

Nonblocking supervisory control of nondeterministic systems viaprioritized synchronization

Shayman and Kumar (1995) showed that supervisory control of nondeterministic discrete-event systems, in the presence of driven events, can be achieved using prioritized synchronous composition as a mechanism of control, and trajectory models as a modeling formalism, first introduced by Heymann (1990). The specifications considered in this earlier work were given by prefix-closed languages. In this paper, we extend this work to include markings so that nonclosed specifications and issues such as blocking can be addressed. It is shown that the usual notion of nonblocking, called language model nonblocking, may not be adequate in the setting of nondeterministic systems, and a stronger notion, called trajectory model nonblocking, is introduced. Necessary and sufficient conditions for the existence of language model nonblocking as well as trajectory model nonblocking supervisors are obtained for nondeterministic systems in the presence of driven events in terms of extended controllability and relative-closure conditions and a new condition called the trajectory-closure condition     

Control of nondeterministic discrete-event systems for bisimulation equivalence

Most prior work on supervisory control of discrete event systems is for achieving deterministic specifications, expressed as formal languages. In this paper we study supervisory control for achieving nondeterministic specifications. Such specifications are useful when designing a system at a higher level of abstraction so that lower level details of system and its specification are omitted to obtain higher level models that may be nondeterministic. Nondeterministic specifications are also meaningful when the system to be controlled has a nondeterministic model due to the lack of information (caused for example by partial observation or unmodeled dynamics). Language equivalence is not an adequate notion of behavioral equivalence for nondeterministic systems, and instead we use the finest known notion of equivalence, namely the bisimulation equivalence. Choice of bisimulation equivalence is also supported by the fact that bisimulation equivalence specification is equivalent to a specification in the temporal logic of /spl mu/-calculus that subsumes the complete branching-time logic CTL*. Given nondeterministic models of system and its specification, we study the design of a supervisor (possibly nondeterministic) such that the controlled system is bisimilar to the specification. We obtain a small model theorem showing that a supervisor exists if and only if it exists over a certain finite state space, namely the power set of Cartesian product of system and specification state spaces. Also, the notion of state-controllability is introduced as part of a necessary and sufficient condition for the existence of a supervisor. In the special case of deterministic systems, we provide an existence condition that can be verified polynomially in both system and specification states, when the existence condition holds.     

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.     

Synthesis of supervisory controllers for hybrid systems based onapproximating automata

The paper concerns the synthesis of supervisory controllers for a class of continuous-time hybrid systems with discrete-valued input signals that select differential inclusions for continuous-valued state trajectories and event-valued output signals generated by threshold crossings in the continuous state space, the supervisor is allowed to switch the input signal value when threshold events are observed. The objective is to synthesize a nonblocking supervisor such that the set of possible sequences of control and threshold event pairs for the closed-loop system lies between given upper and lower bounds in the sense of set containment. We show how this problem can be converted into a supervisor synthesis problem for a standard controlled discrete-event system (DES). A finite representation may not exist for the exact DES model of the hybrid system, however. To circumvent this difficulty, we present an algorithm for constructing finite-state Muller automata that accept outer approximations to the exact controlled threshold-event language, and we demonstrate that supervisors that solve the synthesis problem for the approximating automata achieve the control specifications when applied to the original hybrid system     

On the supremal controllable sublanguage in the discrete-eventmodel of nondeterministic hybrid control systems

This paper is concerned with the logical control of hybrid control systems (HCS). It is assumed that a discrete-event system (DES) plant model has already been extracted from the continuous-time plant. The problem of hybrid control system design can then be solved by applying logical DES controller synthesis techniques to the extracted DES plant. Traditional DES synthesis methods, however, are not always applicable since the extracted plant DES will often exhibit nondeterministic transitions. This paper presents an extension of certain DES controller synthesis techniques to the nondeterministic control automaton found in HCS. In particular, this paper derives a formula computing the supremal controllable sublanguage of a given specification language under the assumption that the DES plant exhibits nondeterministic transitions     

Existence and Verification for Decentralized Nondeterministic Discrete‐Event Systems Under Bisimulation Equivalence

In this paper, we study the decentralized control problem for nondeterministic discrete‐event systems (DESs) under bisimulation equivalence. In order to exactly achieve the desired specification in the sense of bisimulation equivalence, we present a synchronous composition for the supervised system based on the simulation relation between the specification and the plant. After introducing the notions of simulation‐based controllability and simulation‐based coobservability, we present the necessary and sufficient condition for the existence of a decentralized supervisor such that the controlled system is bisimilar to the specification, and an algorithm for verifying the simulation‐based coobservability is proposed by constructing a computational tree.     

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.     

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.     

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.     

Synthesis of Inference-Based Decentralized Control for Discrete Event Systems

In our past work, we presented a framework for the decentralized control of discrete event systems involving inferencing over ambiguities, about the system state, of various local decision makers. Using the knowledge of the self-ambiguity and those of the others, each local control decision is tagged with a certain ambiguity level (level zero being the minimum and representing no ambiguity). A global control decision is taken to be a "winning" local control decision, i.e., one with a minimum ambiguity level. For the existence of a decentralized supervisor, so that for each controllable event the ambiguity levels of all winning disablement or enablement decisions are bounded by some number N (such a supervisor is termed N-inferring), the notion of N- inference-observability was introduced. When the given specification fails to satisfy the iV-inference-observability property, an iV-inferring supervisor achieving the entire specification does not exist. We first show that the class of iV-inference-observable sublanguages is not closed under union implying that the supremal N- inference-observable sublanguage need not exist. We next provide a technique for synthesizing an N -inferring decentralized supervisor that achieves an N -inference-observable sublanguage of the specification. The sublanguage achieved equals the specification language when the specification itself is iV-inference-observable. A formula for the synthesized sublanguage is also presented. For the special cases of N = 0 and N = 1, the proposed supervisor achieves the same language as those reported in [25], [31] (for N = 0) and [32] (for N = 1). The synthesized supervisor is parameterized by N (the parameter bounding the ambiguity level), and as N is increased, the supervisor becomes strictly more permissive in general. Thus, a user can choose N based on the degree of permissiveness and the degree of computational complexity desired.     

Supervisor direct synthesis method for a structured discrete dynamical system

We present an implementation method for a supervisor of a discrete event system (DES) structured in a special way. Such a DES has the following characteristic features: the language generator is represented by a set of finite automata, the language model is extended with a new type of events called “expected,” and the specification is defined as a sequence of control commands. The primary advantage of our method is that it uses structural knowledge of the event stream in order to construct a supervisor. Thus, we achieve linear dependence of the supervisor’s size in the input data.     

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.