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)     

Polynomial-time verification of diagnosability of partially observed discrete-event systems

The problem of verifying the properties of diagnosability and I-diagnosability is considered. We present new polynomial-time algorithms for deciding diagnosability and I-diagnosability. These algorithms are based on the construction of a nondeterministic automaton called a verifier.     

On supervisor reduction in discrete-event systems

A supervisory controller (supervisor) S for a discrete-event system can be modelled on a recognizer R for the language corresponding to the supervisory task to be accomplished. It is shown that simpler ‘reduced’ supervisors can be constructed by the use of covers of the state set of R; and that any mildly restricted supervisor is a reduction of R in this sense. The reduction procedure is time-exponential with respect to the size of the state set of R.     

NP-completeness of sensor selection problems arising in partially observed discrete-event systems

We consider the three properties of diagnosability, normality, and observability of discrete-event systems. In each case, we consider the problem of finding an observable event set with minimum cardinality such that the property under consideration holds. We prove that these search problems are computationally hard by showing that the corresponding decision problems are NP-complete.     

Delay-robustness in distributed control of timed discrete-event systems based on supervisor localisation

Recently, we studied communication delay in distributed control of untimed discrete-event systems based on supervisor localisation. We proposed a property called delay-robustness: the overall system behaviour controlled by distributed controllers with communication delay is logically equivalent to its delay-free counterpart. In this paper, we extend our previous work to timed discrete-event systems, in which communication delays are counted by a special clock event tick. First, we propose a timed channel model and define timed delay-robustness; for the latter, a verification procedure is presented. Next, if the delay-robust property does not hold, we introduce bounded delay-robustness, and present an algorithm to compute the maximal delay bound (measured by number of ticks) for transmitting a channelled event. Finally, we demonstrate delay-robustness on the example of an under-load tap-changing transformer.     

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.     

Robust and nonblocking supervisor for discrete-event systems withmodel uncertainty under partial observation

Addresses a robust and nonblocking supervisory control problem based on a framework of discrete-event systems with model uncertainty under partial observation. The uncertainty introduced in the paper is associated with internal and unobservable events occurring in systems. The paper presents a systematic method for modeling uncertainty described as a Δ-transition representing the internal and unobservable events. In particular, at a state with the assigned positive integer value p a system is assumed to experience at most a p-step state transition by the internal and unobservable event. Under the framework for model uncertainty, the paper presents necessary and sufficient conditions for the existence of a robust supervisor with the nonblocking property     

On the synthesis of safe control policies in decentralized control of discrete-event systems

State estimation and safe controller synthesis for a general form of decentralized control architecture for discrete-event systems is investigated. For this architecture, controllable events are assigned to be either "conjunctive" or "disjunctive." A new state estimator that accounts for past local control actions when calculating the set of estimated system states is presented. The new state estimator is applied to a previous general decentralized control law. The new control method generates a controlled language at least as large as that generated by the original method if a safety condition is satisfied. An algorithm for generating locally maximal control policies for a given state estimate is also discussed. The algorithm allows an amount of "steering" of the controlled system through an event priority mechanism.     

Supervisory control synthesis of discrete-event systems using a coordination scheme

Supervisory control of distributed DES with a global specification and local supervisors is a difficult problem. For global specifications, the equivalent conditions for local control synthesis to equal global control synthesis may not be met. This paper formulates and solves a control synthesis problem for a generator with a global specification and with a combination of a coordinator and local controllers. Conditional controllability is proven to be an equivalent condition for the existence of such a coordinated controller. A procedure to compute the least restrictive solution within our coordination control architecture is provided and conditions under which the result coincides with the supremal controllable sublanguage are stated.     

Hierarchical control of discrete-event systems

An abstract hierarchical control theory is developed for discrete-event systems, based on the concepts of control structures and observers. Control structure is an abstract generalization of the family of controllable sublanguages in the Ramadge-Wonham framework. We establish a general version of Zhong's hierarchical consistency by first achieving control consistency — preservation of control structures through the aggregation mapping in a two-level hierarchy. For a refinement of hierarchical consistency with preservation of nonblocking, the concept of observer is introduced via congruences on nondeterministic transition structures.     

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.     

Necessary conditions for control consistency in hierarchical control of discrete-event systems

Hierarchical consistency is an important concept in control theory of hierarchical discrete-event systems (DESs). In order to establish corresponding control structure in high level, Wong introduced (1990, 1994) the concept of control consistency, which implies hierarchical consistency. However, to check whether a hierarchical DES is control consistent is computationally expensive. In this note, we try to reduce the computational complexity. At first, the kernel condition of control consistency is divided into three simpler parts and computational complexity is analyzed. Further discussion is made to obtain some new necessary conditions for control consistency, by which one can easily verify whether a hierarchical DES is not control consistent.     

Supervisory control of concurrent discrete-event systems

When a discrele-event system P consists of several subsystems P₁,...,P_n which operate concurrently, a natural approach to the supervisory control problem is to synthesize a ‘local’ controller S_i , for each subsystem P_i , and operate the individually controlled subsystems S_i/P_i concurrently. Such an approach is called concurrent supervisory control and is closely related to decentralized supervisory control as studied by Cieslak et al. (1988) and Lin and Wonham (1988). In the present paper simple and easily computable conditions are developed which guarantee that concurrent supervisory control can achieve the optimal behaviour achievable by a global supervisor. To achieve this, two specific concurrent control strategies are introduced.     

Hierarchical control of timed discrete-event systems

An abstract hierarchical control theory is developed for a class of timed discrete-event systems (TDES) within the discrete-event control architectural framework proposed earlier by the authors. For this development, a control theory for TDES is introduced in the spirit of a prior theory of Brandin. A notion of time control structures is introduced, and on its basis a general property of hierarchical consistency is achieved by establishing control consistency — namely preservation of time control structures through the aggregation mapping in a two-level hierarchy.     

Modular supervisory control of discrete-event systems

A modular approach to the supervisory control of a class of discrete-event systems is formulated, and illustrated with an example. Discrete-event systems are modeled by automata together with a mechanism for enabling and disabling a subset of state transitions. The basic problem of interest is to ensure by appropriate supervision that the closed loop behavior of the system lies within a given legal behavior. Assuming this behavior can be decomposed into an intersection of component restrictions, we determine conditions under which it is possible to synthesize the appropriate control in a modular fashion. The work of this author was supported by NSERC (Canada) under Grant No. A-7399. The work of this author was supported by the National Science Foundation through Grant No. ECS-8504584.     

Supervisory control of timed discrete-event systems

The Ramadge-Wonham framework for control of discrete event systems is augmented with timing features by use of Ostroff's semantics for timed transition models. It is shown that the RW concept of controllability and the existence of maximally permissive supervisory controls can be suitably generalized. The enhanced setting admits subsystem composition and the concept of forcible event as an event that preempts the tick of a global clock. An example of a simple manufacturing cell illustrates how the new framework can be used to solve synthesis problems which may include logic-based, temporal and quantitative optimality specifications     

Similarity-based supervisory control of discrete-event systems

Due to the appearance of uncontrollable events in discrete-event systems, one may wish to replace the behavior leading to the uncontrollability of pre-specified language by some quite similar one. To capture this similarity, we introduce metric to traditional supervisory control theory and generalize the concept of original controllability to /spl lambda/-controllability, where /spl lambda/ indicates the similarity degree of two languages. A necessary and sufficient condition for a language to be /spl lambda/-controllable is provided. We then examine some properties of /spl lambda/-controllable languages and present an approach to optimizing a realization.     

Relative coobservability for decentralised supervisory control of discrete-event systems

In this paper, we study the concept of relative coobservability in decentralised supervisory control of discrete-event systems under partial observation. This extends our previous work on relative observability from a centralised setup to a decentralised one. A fundamental concept in decentralised supervisory control is coobservability (and its several variations); this property is not, however, closed under set union, and hence there generally does not exist the supremal element. Our proposed relative coobservability, although stronger than coobservability, is algebraically well behaved, and the supremal relatively coobservable sublanguage of a given language exists. We present a language-based algorithm to compute this supremal sublanguage; the algorithm allows straightforward implementation using off-the-shelf algorithms. Moreover, relative coobservability is weaker than conormality, which is also closed under set union; unlike conormality, relative coobservability imposes no constraint on disabling unobservable controllable events.