Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
10 results
Search Results
Item A Discrete Event Systems Approach for Protocol Conversion(1997) Kumar, Ratnesh; Nelvagal, S.; Marcus, Steven I.; ISRA Protocol mismatch occurs when heterogeneous networks try to communicate with each other. Such mismatches are inevitable due to the proliferation of a multitude of networking architectures, hardware, and software on one hand, and the need for global connectivity on the other hand. In order to circumvent this problem the solution of protocol conversion has been proposed. In this paper we present a systematic approach to protocol conversion using the theory of supervisory control of discrete event systems, which was partially first addressed by Inan. We study the problem of designing a converter for a given mismatched pair of protocols, using their specifications, and the specifications for the channel and the user services. We introduce the notion of converter languages and use it to obtain a necessary and sufficient condition for the existence of protocol converter and present an effective algorithm for computing it whenever it exists.Item Probabilistic Language Framework for Stochastic Discrete Event Systems(1996) Garg, Vijay K.; Kumar, Ratnesh; Marcus, Steven I.; ISRWe introduce the notion of probabilistic languages to describe the qualitative behavior of stochastic discrete event systems. Regular language operators such as choice, concatenation, and Kleene-closure have been defined in the setting of probabilistic language to allow modeling of complex systems in terms of simpler ones. The set of probabilistic languages is closed under such operators thus forming an algebra. It also is a complete partial order under a natural ordering in which the operators are continuous. Hence recursive equations can be solved in this algebra. This fact is alternatively derived by using contraction mapping theorem on the set of probabilistic languages which is shown to be a complete metric space. The notion of regularity of probabilistic languages has also been identified. We show that this formalism is also useful in describing system performances such as completion time, reliability, etc. and present techniques for computing them.Item Design of Protocol Converters: A Discrete Event Systems Approach(1995) Kumar, Ratnesh; Nelvagal, S.; Marcus, Steven I.; ISRA protocol mismatch occurs when heterogeneous networks try to communicate with each other. Such mismatches are inevitable due to the proliferation of a multitude of networking architectures, hardware and software on one hand, and the need for global connectivity on the other hand. Global standardization of protocols will avoid such problems, but it may take years to be agreed upon, leaving communication problems for the present. So the alternative solution of protocol conversion has been proposed. In this paper we present a systematic approach to protocol conversion using the recent theory of supervisory control of discrete event systems. We study the problem of designing a converter for a given mismatched pair of protocols, using their specifications and the specifications for the channel and the user services. We introduce the notion of converter languages, use it obtain a necessary and sufficient condition for the existence of protocol converter and present an effective algorithm for computing it whenever it exists.Item Extension Based Limited Lookahead Supervision of Discrete Event Systems(1995) Kumar, Ratnesh; Cheung, Hok M.; Marcus, Steven I.; ISRSupervisory control of discrete event systems using limited lookahead has been studied by Chung-Lafortune-Lin, where control is computed by truncating the plant behavior up to the limited lookahead window. We present a different approach in which the control is computed by extending the plant behavior by arbitrary traces beyond the limited lookahead window. The proposed supervisor avoids the notion of pending traces. Consequently the need for considering either a conservative or an optimistic attitude regarding pending traces (as in the work of Chung- Lafortune-Lin) does not arise. It was shown that an optimistic attitude may result in violation of the desired specifications. We demonstrate here that a conservative attitude may result in a restrictive control policy by showing that in some cases the proposed supervisor is less restrictive than the conservative attitude-based supervisor. Moreover, the proposed approach uses the notion of relative closure to construct the supervisor so that it is non-blocking even when the desired behavior is not relative closed (Chung-Lafortune-Lin assume relative closure). Finally, the proposed supervisor possesses all the desirable properties that a conservative attitude based supervisor of Chung-Lafortune-Lin possesses. We illustrate our approach by applying it to concurrency control in database management systems.Item A New Framework for Supervisory Control of Discrete Event Systems(1995) Shayman, M.A.; Kumar, Ratnesh; ISRWe propose a new framework for supervisory control design for discrete event systems. Some of the features of the proposed approach are: (i) By associating control and observation capabilities and limitations with the plant as well as the supervisor, it models reactive systems, and also treats plant and supervisory processes in a symmetric way. (ii) By introducing a single general interconnection operation, called masked composition, it permits open-loop as well as closed-loop control. (iii) By viewing the uncontrollability of events as corresponding to a projection-type control mask, and considering more general nonprojection-type control as well as observation masks, it treats the controllability and observability of events in a unified way. (iv) It applies to both deterministic and nondeterministic plant models and supervisory design. The sublanguages of a given language that are realizable under control are closed under union. Hence, the supremal realizable sublanguage always exists. In addition, it yields conditions under which existence of a non-deterministic supervisor implies existence of a deterministic supervisor. (v) By encapsulating control and observation masks with process logic to form process objects, and using a single type of interconnection operator to build complex process objects out of simpler component process objects, it provides a foundation for an object-oriented approach to discrete event control.Item Finite Buffer Realization of Input-Output Discrete Event Systems(1994) Kumar, Ratnesh; Garg, Vijay K.; Marcus, Steven I.; ISRMany discrete event systems (DESs) such as manufacturing systems, data base management systems, communication networks, traffic systems, etc., can be modeled as input-output discrete event systems (I/O DESs). In this paper we formulate and study the problem of stable realization of such systems in the logical setting. Given an input and an output language describing the sequences of events that occur at the input and the output, respectively, of an I/O DES, we study whether it is possible to realize the system as a unit consisting of a given set of buffers of finite capacity, called a dispatching unit. The notions of stable, conditionally stable, dispatchable and conditionally dispatchable units are introduced as existence of stable (or input-output bounded), and causal (or prefix preserving) input- output maps, and effectively computable necessary and sufficient conditions for testing them are obtained.Item Non-blocking Supervisory Control of Nondeterministic Systems via Prioritized, Synchronization(1993) Kumar, Ratnesh; Shayman, M.A.; ISRIn a previous paper [15], we 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. The specifications considered in [15] were given by prefix-closed languages. In this paper, we extend the theory of trajectory models and prioritized synchronous composition to include markings so that non-closed specifications and issues such as blocking can be addressed. It is shown that the usual notion of non-blocking, called language model non- blocking, is inadequate in the setting of nondeterministic systems, and a stronger notion, called trajectory model non- blocking, is introduced. Necessary and sufficient conditions for the existence of non-marking and language model non-blocking as well as trajectory model non-blocking supervisors is obtained for nondeterministic systems in the presence of driven events. We also show that our approach is also suitable for modular supervisory control.Item Supervisory Control of Nondeterministic Systems with Driven Events via Prioritized Synchronization and Trajectory Models(1992) Shayman, M.A.; Kumar, Ratnesh; ISRWe study the supervisory control of nondeterministic discrete event dynamical systems (DEDS's) with driven events in the setting of prioritized synchronization and trajectory models introduced by Heymann. Prioritized synchronization captures the notions of controllable, uncontrollable, and driven events in a natural way, and we use it for constructing supervisory controllers. The trajectory model is used for characterizing the behavior of nondeterministic DEDS's since it is a sufficiently detailed model (in contrast to the less detailed language or failures models), and serves as a language congruence with respect to the operation of prioritized synchronization. We obtain results concerning controllability and observability in this general setting.Item Stable Behavior and Stabilizing Supervisor for Discrete Event Dynamical Systems(1991) Kumar, Ratnesh; Garg, Vijay K.; Marcus, Steven I.; ISRThe paper studies stability and stabilizability of Discrete event Dynamical Systems (DEDS's) in the framework of Ramadge and Wonham. We define stability and stabilizability in terms of the behavior of the DEDS's, i.e. the language generated by the state machines (SM's) used to model the DEDS. The notions of stability and stabilizability of DEDS's have been presented in a more general setting than in earlier works where they are defined in terms of legal and illegal states rather than languages. The notion of reversal of languages is used to provide algorithms for determining the stability and stabilizability of a given system.Item Predicates and Predicate Transformers for Supervisory Control of Discrete Event Dynamical Systems(1991) Kumar, Ratnesh; Garg, Vijay K.; Marcus, Steven I.; ISRMost discrete event system models are based on defining the alphabet set or the set of events as a fundamental concept. In this paper, we take an alternative view of treating the state space as the fundamental concept. We approach the problem of controlling discrete event systems by using predicates and predicate transformers. Predicates have the advantage that they can concisely characterize an infinite state space. The notion of controllability of a predicate is defined, and the supervisory predicate control problem introduced in this paper is solved. A closed form expression for the weakest controllable predicate is obtained. The problem of controlling discrete event systems under incomplete state observation is also considered and observability of predicates is defined. Techniques for finding external solutions of boolean equations is used to derive minimally restrictive supervisors.