Institute for Systems Research
Permanent URI for this communityhttp://hdl.handle.net/1903/4375
Browse
9 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 Risk-Sensitive Optimal Control of Hidden Markov Models: Structural Results(1996) Fernandez-Gaucherand, Emmanuel; Marcus, Steven I.; ISRWe consider a risk-sensitive optimal control problem for hidden Markov models (HMM), i.e. controlled Markov chains where state information is only available to the controller via an output (message) process. Building upon recent results by Baras, James and Elliott, we report in this paper result of an investigation on the nature and structure of risk-sensitive controllers. The question we pose is: How does risk-sensitivity manifest itself in the structure of a controller? We present the dynamic programming equations for risk-sensitive control of HMMs and show a number of structural properties of the value function (e.g., concavity and piecewise linearity) and the optimal risk-sensitive controller, and compare these to the corresponding results for the risk- neutral case. Furthermore, we show that indeed the risk-sensitive controller and its corresponding information state converge to the known solutions for the risk-neutral situation, as the risk factor goes to zero. We also study the infinite and general risk aversion cases. In addition, we present a particular case study of a popular benchmark machine replacement problem.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 Risk-Sensitive Optimal Control of Hidden Markov Models: A Case Study(1994) Fernandez-Gaucherand, Emmanuel; Marcus, Steven I.; ISRWe consider a risk-sensitive optimal control problem for hidden Markov models (HMM). Building upon recent results by Baras, James and Elliott, we investigate the structure of risk-sensitive controllers for HMM, via an examination of a popular benchmark problem. We obtain new results on the structure of the risk- sensitive controller by first proving concavity and piecewise linearity of the value function. Furthermore, we compare the structure of risk-sensitive and risk-neutral controllers.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 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.