Institute for Systems Research
Permanent URI for this communityhttp://hdl.handle.net/1903/4375
Browse
33 results
Search Results
Item Estimation of Hidden Markov Models for Partially Observed Risk Sensitive Control Problems(1997) Frankpitt, Bernard A.; Baras, John S.; ISRWe look at the problem of estimation for partially observed, risk-sensitive control problems with finite state, input and output sets, and receding horizon. We describe architectures for risk sensitive controllers, and estimation, and we state conditions under which both the estimated model converges to the true model, and the control policy will converge to the optimal risk sensitive policy.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 Modeling and Analysis of Real-Time Database Systems in the Framework of Discrete Event Systems(1995) Ghosh, Anunoy; Marcus, S.I.; ISRReal-time systems are currently an active area of research currently, motivated by the potential of widespread applicability in areas like stock trading, network management, air traffic control, robotics and factory automation. Since these systems deal with large quantities of information, real-time systems are being coupled with database systems to aid in the efficient storage, processing and retrieval of data. Such database systems are called Real-Time Database Systems (RTDBS).The problem of concurrency control and scheduling of transactions in real time database systems is studied in the framework of discrete event dynamical systems (DEDS) modeled by deterministic finite automata (DFAs). Concurrency control and scheduling are separated into two different modules (a logical DEDS model for the CC module and a heuristic implementation of a scheduler) to allow modular analysis of various combinations of concurrency control and scheduling algorithms. The model is developed analytically using the theory of discrete event dynamical systems. Subsequently the design of a simulation software is reported that uses this model to simulate transaction execution for a (concurrency controller, scheduler) pair. Finally, we show that our approach can also be viewed as a special case of a supervisory control theory (SCT) synthesis technique. The goal of this thesis is to demonstrate the applicability of DEDS theory as a powerful tool in modeling and analyzing transaction models in real time database systems and to show potential applications of modern SCT techniques in this area.
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 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 Complexity of Production Management in a Petri Net Environment(1994) Proth, J-M.; Minis, Ioannis; ISRThe objective of this paper is to show that Petri nets facilitate a comprehensive approach to production management and reduce the complexity of the problems involved at the expense of some constraints imposed on the decision making systems.The first part of the paper focuses on cyclic manufacturing systems. For this type of systems, it is always possible to propose an event graph model which represents both the physical and the decision making systems. We use such a model to propose a near-optimal scheduling algorithm that maximizes productivity while minimizing the work-in-process (WIP) in the deterministic case.
The approach used for non-cyclic manufacturing systems is different in the sense that only the manufacturing processes (i.e. the physical part of the system) and the related constraints are modeled using Petri nets. We use such a Petri net model to propose a short-term planning process which results in a trade- off between the computation burden the level of resource utilization. the short-term planning models is then enhanced to obtain the scheduling model. The latter is used to develop an efficient scheduling algorithm that is able to satisfy the requirements imposed by short-term planning.