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.     

On deadlock-free modular supervisory control of discrete-eventsystems

In this paper the problem of synthesizing deadlock-free modular supervisors for discrete-event systems is discussed. By introducing the d-invariant relation between a pair of supervisors, it is shown that when the control objective is described in terms of intersection of two languages, a necessary and sufficient condition for the modular supervisor to be deadlock-free is that this pair of subsupervisors satisfies a d-invariant relation. A procedure for synthesizing the deadlock-free modular supervisor is presented. Some issues concerning deadlock-free modular supervisory control are also discussed     

On the supervisory control of multiagent product systems

In this note, we use the formal framework of multiagent (MA) product systems (introduced and developed in previous works) for the analysis of complex systems. The results of this note constitute a natural extension of the classical supervisory control results for scalar systems to the more general MA product system case. The notion of MA controllability is introduced and is shown to essentially constitute a necessary and sufficient condition for the synthesis of an MA supervisor.     

On optimal supervisory control with trimness of controlled systems

In this paper, we propose a design algorithm for an optimal supervisor for guaranteeing the trimness of the controlled system. We generalize the earlier work of Kumar and Grag based on the induced flow network of a given discrete event system. Specifically, the proposed algorithm is directly applicable to a discrete event system and minimizes the net cost of the optimal supervisor, which ensures that the controlled system is a trim generator with a polynomial-order computational complexity.     

Sampled-data supervisory control

This paper focuses on the issues related to the implementation of theoretical timed discrete-event systems (TDES) supervisors, and the concurrency and timing delay issues involved. In particular, we examine issues related to implementing TDES as sampled-data (SD) controllers. An SD controller is driven by a periodic clock and sees the system as a series of inputs and outputs. On each clock edge (tick event), it samples its inputs, changes state, and updates its outputs. We identify a set of existing TDES properties that will be useful to our work, but not sufficient. We extend the TDES controllability definition to a new definition, SD controllability, which captures several new properties that will be useful in dealing with concurrency issues, as well as make it easier to translate a TDES supervisor into an SD controller. We present controllability and non-blocking results for SD controllers.     

On supervisory control of mobile platform on four swivel wheels

A mobile robotic platform with four driving swivel wheels, whose centers are situated at the vertices of a rectangle, is considered. Each of the wheels can rotate about its horizontal axis in a common way, and the plane of the wheel situated in a fork can turn with respect to the platform about the perpendicular axis. These turns and rotations of four wheels are performed using eight drives. The platform can move, perform translational and rotational motion without wheel slip if and only if the fork orientation and wheel angular velocities satisfy certain relations. This study presents the relations to which program values of fork turning angles and wheel angular velocities calculated for automatic control of the platform motion or operator control should satisfy. The scheme of supervisory (with an operator) control of the platform motion and its virtual analogue are described.     

On the supervisory control of multi-agent product systems: Controllability properties

Multi-Agent (MA) product systems were defined in [I. Romanovski, P.E. Caines, On the supervisory control of multi-agent products systems, IEEE Trans. Automated Control 51(5) (2006)] where the notion of an MA controllable vector language specification was introduced and necessary and sufficient conditions for the existence of a supervisor for such a specification were derived. In this paper we present a set of results about the controllability of an MA product system and its components. In particular, we obtain an algorithm for finding the infimal MA-controllable superlanguage inf_MA(K) of a given vector (language) specification K w.r.t. an MA product system G and establish that in fact . It is proven that there is an algorithmic procedure for the recursive construction of MA supervisors when additional automata are added to a system via the MA product. Controllability properties of component structures (such as standard controllability and MA controllability of projections) are considered. Several examples are given to illustrate the results of the paper.     

On the complexity of supervisory control design in the RW framework

The time complexity of supervisory control design for a general class of problems is studied. It is shown to be very unlikely that a polynomial-time algorithm can be found when either (1) the plant is composed of m components running concurrently or (2) the set of legal behaviors is given by the intersection of n legal specifications. That is to say, in general, there is no way to avoid constructing a state space which has size exponential in m+n. It is suggested that, rather than discouraging future work in the field, this result should point researchers to more fruitful directions, namely, studying special cases of the problem, where certain structural properties possessed by the plant or specification lend themselves to more efficient algorithms for designing supervisory controls. As no background on the subject of computational complexity is assumed, we have tried to explain all the borrowed material in basic terms, so that this paper may serve as a tutorial for a system engineer not familiar with the subject.     

On the control of sequential machines with disturbances

The problem of controlling a sequential machine under the influence of disturbances is considered. A methodology is developed for the design of controllers that guarantees that the effect of a 'small' disturbance on the performance of the controlled machine remains 'small'. The methodology is based on a theory of fraction representations of sequential machines reminiscent of the general theory of fraction representations of nonlinear systems.     

Multi-level hierarchical interface-based supervisory control

Hierarchical Interface-Based Supervisory Control employs interfaces that allow properties of a monolithic system to be verified through local analysis. By avoiding the need to verify properties globally, significant computational savings can be achieved. In this paper we provide local requirements for a multi-level architecture employing command-pair type interfaces. This multi-level architecture allows for a greater reduction in complexity and improved reconfigurability over the two-level case that has been previously studied since it allows the global system to be partitioned into smaller modules. This paper also provides results for synthesizing supervisors in the multi-level architecture that are locally maximally permissive with respect to a given specification and set of interfaces.     

Control situations in supervisory control

It is widely acknowledged that the safe and efficient supervisory control of complex dynamic systems requires that human operators are capable of checking the state of the controlled system against given performance criteria. In addition, it is important to consider how changes in the state of the controlled system and its environment influence the control situation: the possibility of bringing about system state changes by performing control actions on the controlled system (the control possibilities), and the requirements for bringing about appropriate state changes in the controlled system (the control requirements). This paper addresses fundamental problems related to the design of human-machine systems that can track changes in control situations. Based on a theoretical analysis of control actions, a generic structure is proposed for control situations. The issues of how to specify control situations and how to derive changes in the control situation, based on a representation of the work domain, are also addressed, using examples.

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.     

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.     

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.     

Dynamical consistency in hierarchical supervisory control

A hierarchical control theory is presented founded upon the trace-dynamical consistency property, which is an extension of the notion of dynamical consistency (DC) to the supervisory case of automata with disablable transitions. Partitions of a system state space are considered for which both the trace-DC and the (non-blocking) in-block controllability (IBC) conditions hold; it is shown that low-level non-blocking controllable languages project up to such languages in the high-level system, and that, when the (non-blocking) IBC condition also holds, high-level non-blocking controllable languages map down to such languages in the low-level system. It is demonstrated that the resulting pairs of low-level and high-level languages satisfy a version of the hierarchical consistency condition found in the existing language-based hierarchical supervisory control theory. The structures produced in the formulation of hierarchical control in this paper permit efficient regulator design (and, in particular, repeated re-design) for hierarchy-compatible language specifications; such specifications consist of low-level languages whose maximal controllable sublanguages are realizable by a combination of a high-level (possibly history-dependent) regulator and a set of (state-dependent) low-level regulators (specified block-wise). An algorithm is proposed which facilitates the construction of (non-blocking) IBC partitions of systems with vocalized states. Examples are presented, including a material transfer line with re-entrant flow and a double queue     

Decentralized supervisory control with communicating controllers

The decentralized control problem for discrete-event systems addressed in this paper is that of several communicating supervisory controllers, each with different information, working in concert to exactly achieve a given legal sublanguage of the uncontrolled system's language model. A novel information structure model is presented for dealing with this class of problems. Existence results are given for the cases of when controllers do and do not anticipate future communications, and a synthesis procedure is given for the case when controllers do not anticipate communications. Several conditions for optimality of communication policies are presented, and it is shown that the synthesis procedure yields solutions, when they exist for this class of controllers, that are optimal with respect to one of these conditions     

Optimal supervisory control under partial observation

In this paper, we formulate the optimal supervisory control problem (OSCP) under partial observation and propose an algorithm to design the optimal nonblocking supervisor (ONS). In addition, we introduce an extended net cost including the observation cost of the events which is taken into account for the cost of setting up a mechanism to sense the events and solve the OSCP with the extended net cost.     

Multi-model unfalsified adaptive switching supervisory control

The paper studies how on-line inferring stability of a potential control-loop consisting of an uncertain plant interconnected in feedback with a candidate controller using plant I/O pairs recorded while the plant is possibly driven by a different controller. In such a context, a convenient tool to work with is to resort to the conceptual entity of a virtual reference (VR). The adopted approach consists of embedding, in the so-called unfalsified adaptive switching control schemes based on VR, a family of nominal models pairwise associated with the given candidate controllers. The result is that the supervised switching mechanism can moderate the chance that destabilizing controllers be switched-on and, hence, reduce both the magnitude and time durations of “learning” transients after start-up, while, in contrast with pre-existing multi-model based methods, stability in-the-large is guaranteed under the minimal conceivable assumption that a stabilizing candidate controller exist.