174 research outputs found
Linear regulator design for stochastic systems by a multiple time scales method
No full textBibliography: leaves 10-11.NASA Grant NGL-22-009-124, and ERDA Grant ERDA-E(49)-2087.Demosthenis Teneketzis, Nils R. Sandell, Jr
Perturbation methods in decentralized stochastic control
No full textBibliography: p.195-197.The research was conducted under grant NGL-22-009-124, grant AFOSR-72-2273, and grant ERDA-E (49-18)-2087. Originally presented as the author's thesis, (M.S.), M.I.T. Dept. of Electrical Engineering and Computer Science, 1976.by Demosthenis Teneketzis
Communication in decentralized control
No full textThesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1980.MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING.Includes bibliographical references.by Demosthenis Teneketzis.Ph.D
Optimal stochastic scheduling and routing in queueing networks.
No full textQueueing networks are extensively used in the study of systems such as communication, computer, and manufacturing networks. Presently there exists some conceptual understanding of many underlying issues of network performance; yet, there remain fundamental issues that are not well understood and need to be investigated. Such issues are related to efficient network resource utilization and routing under imperfect information. In this dissertation we investigate stochastic scheduling, resource allocation and dynamic routing problems arising in queueing networks. We determine optimal policies or derive qualitative properties of optimal policies for the problems described below. We study the problem of optimally scheduling time-critical tasks in multi-class queueing systems. Two different versions of the problem are considered: (i) If the service of a task does not begin by a certain deadline, the task is lost and a fixed cost is incurred; and (ii) if the service of a task is completed at a time other than a certain due date, a penalty proportional to the earliness or tardiness is incurred. We determine properties of dynamic nonidling strategies that minimize infinite horizon expected costs. Next we consider the problem of optimally scheduling tasks in a multi-server system consisting of two interconnected queues. Tasks incur an instantaneous holding cost during the time they remain in the system. We establish sufficient conditions on the service times, the holding costs, and the interconnection process under which it is possible to explicitly determine the strategy that minimizes the total expected discounted cost. Finally we investigate the following decentralized routing problem. We consider a queueing system consisting of two service stations and two controllers, one in front of each station. Customers arriving at a controller's site are to be routed to one of the two stations. Each controller has perfect knowledge of the queue length in its own station and receives information about the other station's queue length with delay of one time unit. We explicitly determine the controllers' routing strategies that minimize the customers' total flowtime.PhDElectrical Engineering: SystemsUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/104185/1/9501012.pdfDescription of 9501012.pdf : Restricted to UM users only
A market-based approach to optimal resource allocation in integrated-services connection-oriented networks.
No full textIn this dissertation we investigate the admission and resource allocation control in a single shared physical network that supports applications with different input traffic characteristics and different quality of service (QoS) requirements. The contribution of the thesis is in two areas: (1) the mapping of end-to-end QoS guarantees into network resources; and (2) the employment of economic market methods to implement network resource allocations that fulfill certain objective functions. In the first part of the thesis we consider an Asynchronous Transfer Mode (ATM) network that provides services to users every T units of time. We assume that bandwidth and buffers are reserved to each connection, at the links along its route. Users' preferences are summarized by exponential demand functions, and each user is allowed to request only one type of service. Input traffic is characterized by the maximum input rate and an upper bound on the burstiness curve. We specify the set of resources needed to guarantee a maximum percentage of cell loss and a maximum end-to-end cell delay, and we incorporate those as constraints into the following static optimization problem: determine the amount, price and required resources for each type of service, that maximize the sum of network's revenue and users' surplus. We prove the existence of a solution, and we suggest an iterative procedure that interprets the solution and satisfies the informational constraints imposed by the structure of the network. In the second part of the thesis we assume that the mapping of QoS into network resources is given, and we formulate an optimization problem that is more general than the optimization problem presented in the first part of the thesis. Users' preferences are summarized by means of their utility functions, and each user is allowed to request many types of service. The objective is to find the number of connections and the corresponding resources, that maximize the sum of the utilities. We prove the existence of a solution and we describe a competitive market economy that consists of four types of agents, and leads to an allocation that is arbitrarily close to a solution of the optimization problem.PhDApplied SciencesComputer scienceElectrical engineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/131553/2/9910006.pd
Optimal stochastic scheduling of queueing networks: Switching costs and partial information.
No full textThis dissertation addresses two fundamental resource allocation issues encountered in a variety of network systems: scheduling subject to (1) penalties for changes of server allocation (switching penalties) and (2) partial information. We focus on the characterization of optimal dynamic control policies, thereby reducing the search and/or computation required to determine an optimal control strategy. Our treatment of the first issue, switching penalties, begins with complete information. Consider a system of parallel queues without arrivals for which service periods in a particular node are i.i.d. In addition to holding costs in each node, a set-up switching cost (or set-up time) is incurred at each instant the server processes a job in a queue different than the previous one. We prove that an index rule is optimal and derive the closed form indices associated with each queue. The analysis of parallel queues is used to address problems with connected queues and switching penalties. In this case, a queue may send jobs to another queue, thus forming a forest network. We determine conditions on the holding costs and service distributions for which exhaustive service is optimal. That is, the server never leaves a queue while jobs remain in it. We treat both switching costs and partial information in the context of scheduling a passenger shuttle or, more abstractly, a batch server. We analyze two problems. In the first, we consider dispatching a single finite capacity shuttle between two terminals. The controller observes perfectly the terminal at which it waits, but obtains only delayed observations of the other. In the second problem, we consider the dispatching of an infinite capacity shuttle on a fixed ring of N terminals. Customers boarding at one terminal depart at the next terminal. The controller observes the present terminal, but has no recent observations of the other terminals since its last visit to them. For both of these shuttle scheduling problems, we prove optimality and monotonicity of threshold policies.PhDElectrical Engineering: SystemsUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/103326/1/9308470.pdfDescription of 9308470.pdf : Restricted to UM users only
Optimal resource allocation and routing in wireless networks.
No full textWe are in a time of fundamental change in the world's telecommunications infrastructure, with the nature and quantity of information transmission undergoing major transformation. With expanding interest in mobile access to this communications infrastructure has come rapid growth in the number of users of wireless communication networks. The backbone of this growth has been single-hop networks, such as cellular systems, in which service areas are under the central control of a base station. More recently, researchers began investigating ad hoc wireless networks, which operate without a central controller, with each node acting as a network router. In this dissertation, we formulate models for both kinds of wireless networks, and develop optimal policies (protocols) under a variety of system assumptions. First, we formulate a problem in single-hop resource (multi-channel) allocation for wireless networks, under general arrival and connectivity processes at each mobile node. We provide conditions sufficient to guarantee the optimality of an index policy for this problem. We then refine the aforementioned sufficient conditions under additional assumptions on the arrival and connectivity processes. Next, we define a problem which both extends and restricts the previous model. The extension is to include a switching cost when server (channel) allocation changes; this cost models the penalty paid when a communications resource is moved between customers. The restriction is to include only one server in the model. We provide conditions sufficient to guarantee the optimality of an index policy for this problem. Finally, we present a time-invariant stochastic model for routing in ad hoc wireless networks, and we discuss the design decisions leading to this model. We first view the routing problem as a problem of centralized control, and prove optimality of an index policy. Then, we demonstrate that this index policy can be implemented in a distributed manner. We add quality of service considerations by allowing time-varying system parameters, and provide conditions under which we can specify an optimal policy for the time-varying system. We define three distributed algorithms, and prove each computes an optimal routing policy for the time-invariant problem. With these distributed algorithms, the original goal of finding an optimal decentralized protocol is attained.PhDApplied SciencesElectrical engineeringSystems scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/123491/2/3000999.pd
Decentralized resource allocation mechanisms in networks.
No full textOne of the main challenges in the development of communication networks is the design of resource allocation strategies which guarantee the delivery of different services, each with its own Quality of Service (QoS) requirement, and maximize some performance criterion (e.g. the network's utility to its users). The challenge in determining such resource allocation strategies comes from the fact that networks are informationally decentralized systems, consisting of two type of agents: users and network. Each user has preferences over the set of services offered by the network. These preferences are usually expressed by a utility function. A user's utility function is its own private information. Each user requests services so as to maximize its utility function and is unaware as well as uninterested in the method used for the delivery of the requested services. Furthermore each user is unaware of the set of other users requesting network services. The network (network manager) knows the network topology and the network's resources (e.g. link capacities, buffer size at each node) but is unaware of the number of users that may request services, as well as the users' utilities. In this thesis we investigate some of the key features of decentralized resource allocation mechanisms in the context of network problems. The main contributions of this thesis are: (1) the development of goal realizing resource allocation pricing mechanisms for (i) unicast networks with routing and Quality of Service requirements, and (ii) multi-rate multicast; (2) the proof that the above pricing mechanisms have a message space of dimensionality which is a lower bound for the dimensionality of the message spaces of all goal realizing and regular mechanisms; and (3) the proof that for a large class of environments the above pricing mechanisms are informationally efficient.PhDApplied SciencesElectrical engineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/124571/2/3150099.pd
Asymptotically efficient control schemes for stochastic adaptive optimization problems.
No full textThe principal characteristic of stochastic adaptive optimization problems is the uncertainty in the system model. Consequently, the feedback control scheme to be employed cannot depend on the knowledge of the exact system model, but has to work well over a family of models. In order to do so the control scheme has two, often conflicting, objectives: (1) gathering information for identifying the uncertain system model, and (2) controlling the system optimally on the basis of whatever information is available up to the present. Assuming that we know how to solve the optimization problem when the system model is known, we now need to investigate the additional cost (called learning loss) that we incur due to the implicit on-line learning task involved when the system model is not completely known. In particular, we need to develop efficient learning strategies so as to minimize the rate at which the learning loss accumulates. The first part of this thesis investigates the multi-armed bandit problem with switching cost. We construct what we call block allocation schemes that, while maintaining the required rate of experimentation, manage to reduce the number of switches to an order of magnitude less than the learning loss itself, thereby equalling the asymptotic performance of the optimal schemes for the problem without switching cost. The second part of the thesis addresses the adaptive control of i.i.d. processes and Markov chains by first viewing them as multi-armed bandit problems where the arms are the control actions and stationary control laws respectively. However, the arms so identified are statistically dependent, unlike the arms in the multi-armed bandit problem. This statistical dependence makes the lower bound on the learning loss, that we obtain, and the adaptive control scheme, that we construct to achieve that lower bound, much more complicated. The idea of learning in a control environment is central to many problems in stochastic systems. By studying the problems described above, we are able to find optimal rates of learning in a framework broad enough to capture the essential features of many real problems in resource allocation, stochastic scheduling, manufacturing automation, communication networks, and communication systems.PhDApplied SciencesElectrical engineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/128243/2/8906986.pd
Applications of stochastic techniques to partially observed discrete event systems.
No full textIn order to address questions like fault diagnosis and optimization in large, complex systems, it is necessary to have a proper understanding of how information develops in such systems and what information is necessary in order to solve particular problems. Such a treatment of information is well developed in the theory of stochastic systems, but less so in the theory of discrete-event systems (DES). In this thesis we apply facets of stochastic systems theory to DES. Three distinct major problems are considered. The first is the question of diagnosability of stochastic DES. The notions of A- and AA-diagnosability are defined for stochastic automata and conditions for A- and AA-diagnosability are determined through the construction of a stochastic diagnoser. The second problem, the active acquisition of information problem, relates to how to optimally schedule measurements so as to minimize the observation cost necessary to control a system or diagnose a failure within it. A cost is incurred each instant a sensor is activated in an attempt to observe an event, and the objective is to minimize either the worst-case cost (for logical DES) or expected cost (stochastic DES) required in order to detect a failure. The solution of this problem requires properly defining an information state for DES and the construction of a proper sequence of information sigma-fields. Dynamic programming used the information sigma-fields to find an optimal solution. The final problem concerns intrusion detection in centralized and decentralized supervisory control systems. The control action implemented by a supervisor may fail as a result of an intruder interfering with the system's performance and, as a result, strings that the supervisor wished to disable may be executed. Conditions for ensuring that all illegal strings can be disabled in the presence of intrusion are presented. A language measure technique is used to assess the potential damage an intruder can cause. Optimal control specifications are determined by constructing appropriate information states and using dynamic programming.PhDApplied SciencesElectrical engineeringSystems scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/125903/2/3224764.pd
- …
