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
17 results
Search Results
Item Distributed subgradient method under random communication topology - the e(2009-09) Matei, Ion; Baras, John; Baras, JohnIn this note we study the performance metrics (rate of convergence and guaranteed region of convergence) of a multi-agent subgradient method for optimizing a sum of convex functions. We assume that the agents exchange information according to a communication topology modeled as a random graph, independent of other time instances. Under a strong convexity type of assumption, we express the performance metrics directly as functions of the estimates of the optimal decision vector. We emphasize how the probability distribution of the random graph affects the upper bounds on the performance metrics. This provide a guide for tuning the parameters of the communication protocol such that good performance of the multi-agent subgradient method is ensured. We perform the tuning of the protocol parameters for two communication scenarios. In the first scenario, we assume a randomized scheme for link activation with no-error transmissions while in the second scenario we use a pre-established order of transmissions but we consider the interference effect. Both these scenarios are applied on a small world type of topology.Item Convergence Results for Ant Routing Algorithms via Stochastic Approximation and Optimization(2007) Purkayastha, Punyaslok; Baras, John S.``Ant algorithms'' have been proposed to solve a variety of problems arising in optimization and distributed control. They form a subset of the larger class of ``Swarm Intelligence'' algorithms. The central idea is that a "swarm" of relatively simple agents can interact through simple mechanisms and collectively solve complex problems. Instances that exemplify the above idea abound in nature. The abilities of ant colonies to collectively accomplish complex tasks have served as sources of inspiration for the design of ``Ant algorithms''. Examples of ``Ant algorithms'' are the set of ``Ant Routing'' algorithms that have been proposed for communication networks. We analyze in this paper Ant Routing Algorithms for packet-switched wireline networks. The algorithm retains most of the salient and attractive features of Ant Routing Algorithms. The scheme is a multiple path probabilistic routing scheme, that is fully adaptive and distributed. Using methods from adaptive algorithms and stochastic approximation, we show that the evolution of the link delay estimates can be closely tracked by a deterministic ODE system. A study of the equilibrium points of the ODE gives us the equilibrium behavior of the routing algorithm, in particular, the equilibrium routing probabilities, and mean delays in the links under equilibrium. We also show that the fixed-point equations that the equilibrium routing probabilities satisfy are actually the necessary and sufficient conditions of an appropriate optimization problem. Simulations supporting the analytical results are provided.Item Binary Rewriter Writer Software Manual(2007-08-21) Malloy, MichaelIn traditional software development, the developer would use a compiler to translate a high-level language program (Java, C++, etc.) into a binary executable program. In recent years, new research has introduced a new concept called the Binary Rewriter. The Binary Rewriter takes a binary executable program as input, performs some form of optimization, and then outputs an improved binary executable program. The improved binary executable program performs the same function as the original, but some aspect of the new executable is able to perform better than the original. The Binary Rewriter can optimize programs to improve security, to improve runtime and real-time bounds, to reduce energy use, or to improve reliability. The Binary Rewriter has three main components: the reader, the optimizer, and the writer. The reader reads in a binary executable program and translates it into an ISA-independent Intermediate Format (IF). The optimizer then takes the Intermediate Format code and enhances it for increased security, reliability, etc. Once the optimization stage is complete, the writer uses the improved Intermediate Format code to produce an improved binary executable file. During my ten week internship with The Institute for Systems Research, it was my duty to begin the implementation of the third component, the writer. This manual will provide you with a detailed description of the writer section of the Binary Rewriter. NOTE: This document is currently unavailable pending completion of a larger research projectItem Measuring Ground Delay Program Effectiveness Using the Rate Control Index(2000) Ball, Michael O.; Hoffman, Robert L.; Ball, Michael O.; ISR; NEXTORThe objective of Air Traffic Flow Management is to maintain safe and efficient use of airspace and airports by regulating the flow of traffic. In this paper, we introduce a single-valued metric for post-operatively rating the performance of achieved traffic flow against targeted traffic flow. We provide variations on the metric, one of which factors out stochastic conditions upon which a plan is formulated, and show how these improve on current traffic control analysis techniques. The core of the metric is intuitive and simple, yet leads to an interesting optimization problem that can be efficiently solved via dynamic programming. Numerical results of the metric are given as well as a sample of the type of analysis that should follow a low rating by the metric. Although this metric was originally developed to rate the performance of Ground Delay Programs, it is equally applicable to any setting in which the flow of discrete objects such as vehicles is controlled and later evaluated.Item The Rate Control Index for Traffic Flow(2000) Ball, Michael O.; Hoffman, Robert L.; Ball, Michael O.; ISR; NEXTORThe objective of Air Traffic Flow Management is to maintain safe and efficient use of airspace and airports by regulating theflow of traffic. In this paper, we introduce a single-valued metric for post-operatively rating the performance ofachieved traffic flow against targeted traffic flow. We provide variations on the metric, one of which factors out stochastic conditions upon which a plan is formulated, and show how those improve on current traffic control analysis techniques.The core of the metric is intuitive and simple, yet leads to an interesting optimization problem that can be efficiently solved via dynamic programming. Numerical results of the metric are given as well as a sample of the type of analysis that should follow a low rating by the metric.
Although this metric was originally developed to rate the performance of GroundDelay Programs, it is equally applicable to any setting in which the flow of discrete objects such as vehicles is controlled and later evaluated.
Item Robot Formations: Learning Minimum-Length Paths on Uneven Terrain(2000) Hristu, Dimitrios; ISR; CDCSSWe discuss a prototypeproblem involving terrain exploration and learning by formations ofautonomous vehicles. We investigate an algorithm forcoordinating multiple robots whose task is to find the shortest pathbetween a fixed pair of start and target locations, without access toa "global" map containing those locations.Odometry information alone isnot sufficient for minimizing path length if the terrain is uneven orif it includes obstacles. We generalize existing results on a simplecontrol law, also known as "local pursuit," which is appropriate inthe context of formations and which requires limited interactionbetween vehicles.
Our algorithm is iterative and converges to alocally optimal path. We include simulations and experimentsillustrating the performance of the proposed strategy.
The research and scientific content in this material has been published in the IEEE Mediterranean Conference on Control and Automation, July 2000. Item Generalized Inverses for Finite-Horizon Tracking(2000) Hristu, Dimitrios; ISR; CDCSSControl and communication issues aretraditionally "decoupled" in discussions of decision and controlproblems, as this simplifies the analysis and generally works well forclassical models. This fundamental assumption deserves re-examinationas control applications spread into new areas where system complexityis significant. Such areas include the coordinated control of aerialvehicles (UAVs), MEMS devices, multi-joint manipulators and othersettings where many systems must share the attention of adecision-maker. We consider a new class ofsampled-data systems (termed "computer-controlled systems") thatoffer the possibility of jointly optimizing between control andcommunication goals. Computer-controlled LTI systems can be viewed aslinear operators between appropriate inner-product spaces. Thegeneralized inverses of these operators are used to solve a class offinite-horizon tracking problems.This work was presented at the IEEE Conf. on Decision and Control, Dec. 1999. Item A Tool Optimization Interface for a Semiconductor Manufacturing System(2000) Thomas, Ryan; Herrmann, Jeffrey W.; ISRThis paper will serve as the documentation for the Tool Optimization codeof the HSE software. The purpose of the software is, simply, to enable auser to optimize a factory's tool selection. This will be added to theexisting Factory Administrator which enables users to understand theeffects of changes in many parts of the manufacturing process (i.e. Temperatures, Pressures, etc.).To accomplish this an interface was designed via the DELPHI programminglanguage that can take inputs from a user as well as factory details froman Excel spreadsheet, run simulations, determine an optimal toolconfiguration, and output this data as easily as possible to the user.
The Interface will guide the Simulation as many times as needed to performits gradient analysis. After the program is complete, it determines a bestcase tool configuration that meets the user's throughput while maintainingto his budget. The interface will output how many of each tool to purchaseas well the best possible tool allocation (usage) for each tool.
Item The Intelligent Process Planner and Scheduler(2000) Thompson, Carl P.; Herrmann, Jeffrey W.; Lin, Edward; Fleischer, Mark; Mathur, Vidit; ISRThis report is an account of an undergraduate student participating for two months in the research and development of a web-based, planning and scheduling application. The content contains details of web-application architecture, analysis of development environments, and aspects of a scheduling application's components. Also discussed is a student's perspective on the use of web-based technology in the information age.Item Improving Cluster Tool Performance by Finding the Optimal Sequence and Cyclic Sequence of Wafer Handler Moves(2000) Nguyen, Manh-Quan Tam; Herrmann, Jeffrey; ISRThe research aims to develop algorithms that can minimize the total lot processing time (makespan) of cluster tools used for semiconductor manufacturing. Previous research focuses on finding an optimal sequence of wafer handler moves in a cluster tool that has one process chamber in each stage. In practice, if the number of chambers in a stage is more than one, either a pre-specified sequence of moves is given in advance or a dispatching rule is applied. No previous work has addressed the problem of finding an optimal sequence of wafer handler moves to improve performance of cluster tools with more than one chamber in a stage. Cluster tools are highly integrated machines that can perform a sequence of semiconductor manufacturing processes. The performance of cluster tools becomes increasingly important as the semiconductor industry produces larger wafers with smaller device geometry. Some factors that motivate the use of cluster tools, instead of stand-alone tools, include increased yield and throughput, less contamination, and less human intervention. In this research, the cluster tool is modeled as a manufacturing system with a material handling system (wafer handler). The model specifies all constraints that a feasible sequence of wafer handler moves must satisfy. The thesis develops two cluster tool scheduling algorithms. Given the lot size, the wafer handler move time, the in-chamber processing times, and the tool configuration the first algorithm, based on a complete forward branch-and-bound algorithm, searches for an optimal solution from the set of all feasible sequences of wafer handler moves. The second algorithm, a truncated branch-and-bound algorithm, quickly searches for the best solution from the set of feasible cyclic sequences of wafer handler moves. For simple tool configurations, analytical makespan models are also derived. The results show that, in many cases, the search algorithms can significantly reduce the total lot processing time. This reduces tool utilization, reduces manufacturing cycle times, and increases tool capacity.