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
Search Results
Item The MDLe Engine -- A Software Tool for Hybrid Motion Control(2000) Hristu, Dimitrios; Krishnaprasad, Perinkulam S.; Andersson, Sean B.; Zhang, F.; Sodre, P.; D'Anna, L.; ISR; CDCSSOne of the important but often overlooked practical challenges in motion control for robotics and other autonomous machines has to do with the implementation of theoretical tools into software that will allow the system to interact effectively with the physical world. More often than not motion control programs are machine-specific and not reusable, even when the underlying algorithm does not require any changes.The work on Motion Description Languages (MDL) has been an effort to formalize a general-purpose robot programming language that allows one to incorporate both switching logic and differential equations. Extended MDL (MDLe) is a device-independent programming language for hybrid motion control, accommodating hybrid controllers, multi-robot interactions and robot-to-robot communications.
The purpose of this paper is to describe the "MDLe engine," a software tool that implements the MDLe language.
We have designed a basic compiler/software foundation for writing MDLe code. We provide a brief description of the MDLe syntax, implementation architecture, and functionality. Sample programs are presented together with the results of their execution on a set of physical and simulated mobile robots.
Item Fast Evaluation of Demagnetizing Field in Three Dimensional Micromagnetics using Multipole Approximation(2000) Tan, X.; Baras, John S.; Krishnaprasad, Perinkulam S.; Baras, John S.; Krishnaprasad, Perinkulam S.; ISR; CDCSSComputational micromagnetics in three dimensions is of increasing interest with the development of magnetostrictive sensors andactuators. In solving the Landau-Lifshitz-Gilbert (LLG) equation, the governing equation of magnetic dynamics for ferromagnetic materials, we need to evaluate the effective field. The effective field consists of several terms, among which the demagnetizing field is of long-range nature.Evaluating the demagnetizing field directly requires work of O(N^2) for a grid of N cells and thus it is the bottleneck in computational micromagnetics. A fast hierarchical algorithm using multipole approximation is developed to evaluate the demagnetizing field. We first construct a mesh hierarchy and divide the grid into boxes of different levels. The lowest level box is the whole grid while the highest level boxes are just cells. The approximate field contribution from the cells contained in a box is characterized by the box attributes, which are obtained via multipole approximation. The algorithm computes field contributions from remote cells using attributes of appropriate boxes containing those cells, and it computes contributions from adjacent cells directly. Numerical results have shown that the algorithm requires work of O(NlogN) and at the same time it achieves high accuracy. It makes micromagnetic simulation in three dimensions feasible.
Item A Hierarchical Structure For Finite Horizon Dynamic Programming Problems(2000) Zhang, Chang; Baras, John S.; Baras, John S.; ISR; CSHCNIn dynamic programming (Markov decision) problems, hierarchicalstructure (aggregation) is usually used to simplify computation. Most research on aggregation ofMarkov decision problems is limited to the infinite horizon case, which has good tracking ability. However, in reallife, finite horizon stochastic shortest path problems are oftenencountered.In this paper, we propose a hierarchical structure to solve finite horizon stochastic shortest pathproblems in parallel. In general, the approach reducesthe time complexity of the original problem to a logarithm level, which hassignificant practical meaning.
Item Fair Allocation of Discrete Bandwidth Layers in Multicast Networks(1999) Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISRWe study fairness when receivers in a multicast network can not subscribeto fractional layers. This case arises whenthe source hierarchically encodes its signal and the hierarchical structureis predetermined. Unlike the case of the fractional layer allocation,which has been studied extensively in a previous work, bandwidth canbe allocated in discrete chunks only. Fairness issues becomevastly different. Computation of lexicographically optimal rateallocation becomes NP-hard in this case, while lexicographicallyoptimal rate allocation is polynomial complexity computablewhen fractional layers can be allocated. Furthermore, maxmin fair rate vector may not exist in this case.We introducea new notion of fairness, maximal fairness.We propose a polynomialcomplexity algorithm for computation of maximally fair ratesallocated to various source-destination pairs. Even though, maximal fairnessis a weaker notion of fairness, itcoincides with lexicographic optimality and maxmin fairness, when maxmin fair rate allocation exists. So the algorithmfor computing maximally fair rate allocation computes maxmin fairrate allocation, when the latter exists.Item Architecture, Design, Simulation and Performance Evaluation for Implementing ALAX -- The ATM LAN Access Switch Integrating the IEEE 1355 Serial Bus(1997) Charleston, Giles C.; Makowski, A.; ISR; CSHCNIEEE 1355 is a serial bus standard for Heterogeneous Inter Connect (HIC) developed for "enabling high-performance, scalable, modular and parallel systems to be built with low system integration cost." However to date, few systems have been built around this standard specification. In this thesis, we propose ALAX -- an internetworking switching device based on IEEE 1355. The aim of the thesis is two-fold. First, we discuss and summarize research works leading to the architecture, design and simulation development for ALAX; we synthesize and analyze relevant data collected from the simulation experiments of the 4- port model of ALAX (i.e., 4-by-4 with four input and output queues) -- these activities were conducted during the 2-year length of the project. Secondly, we expand the original 4-by-4 size of the ALAX simulation model into 8-, 12- and 16-port models and present and interpret the outcomes. Thus, overall we establish a performance assessment of the ALAX switch, and also identify several critical design measurements to support the ALAX prototype implementation. We review progresses made in Local Area Networks (LANs) where traditional software-enabled bridges or routers are being replaced in many instances by hardware-enabled switches to enhance network performance. Within that context, ATM (Asynchronous Transfer Mode) technology emerges as an alternative for the next generation of high-speed LANs. Hence, ALAX incarnates our effective approach to build an ATM-LAN interface using a suitable switching platform. ALAX currently provides the capability to conveniently interconnect legacy Ethernet and ATM- based networks. Its distributed architecture features a multi- processor environment of T9000 transputers with parallel processing capability, a 32-by-32 way non-blocking crossbar fabric (C104 chipset) partitioned into Transport (i.e., Data) and Control planes, and many other modules interlaced with IEEE 1355- based connectors. It also employs existing and emerging protocols such as LANE (LAN Emulation), IEEE 802.3 and SNMP (Simple Network Management Protocol). We provide the component breakdown of the ALAX simulation model based on Optimized Network Engineering Tools (OPNET). The critical parameters for the study are acceptable processor speeds and queuing sizes of shared memory buffer at each switch port. The performance metric used is the end-to-end packet delay. Finally, we end the thesis with conclusive recommendations pertaining to performance and design measurement, and a brief summary of areas for further research study.Item An Integrated Rapid Prototyping and Vacuum Casting System for Medical Applications(1997) Surana, Rena; ISREvaluation of products in the design stage has played a critical role in product development. Methods to build functional prototypes have been a deciding factor for designverification. As an emerging technology, rapid prototyping is revolutionizingthe process of building prototypes. However, material limitations and highcosts call for further expansion of this technology focusing on batch productionof prototypes with material options.Recognizing the challenge to produce multiple prototypes, this thesisresearch aims to integrate three state-of-the-art technologies: 3D solid modeling, rapid prototyping, and vacuum casting. A system architecture combining hardwareand computer software is designed and implemented.
The system utilizes computergraphics to construct a 3D model of an object through visualitzion. A softwaresystem, Maestro, processes a CAD file, generates support structures, and creates slice data to build prototypes by a stereolithography process. Thebuilt part serves as a master pattern for creation of a silicone rubber mold in a vacuum environment. This vacuum environment creates a material flow ratethat ensures replicas with superior quality in regards to surface finish anddimensional accuracy. This mold is then used to cast multiple replicas ofthe master pattern.
The unique contribution of this research is the application of thedeveloped system to meet a specific need in medical research - an effort torestore sight in blind individuals by implanting electordes in the visualcortex. Six replcas of a monkey skull are produced for surgeions to practicesurgical procedures. Image data obtained from CT scans of a mondkey head are successfully used to contruct a 3D solid model to fabricate a batch of six functional prototypes. The superior quality of these replicas hasoffered a unique opportunity for exploratory surgery in efforts to restoresight.
Item Mathematical Programming Algorithms for Regression-based Nonlinear Filtering in IRN(1997) Sidiropoulos, N.D.; Bro, R.; ISRConstrained regression problems appear in the context of optimal nonlinear filtering, as well as in a variety of other contexts, e.g., chromatographic analysis in chemometrics and manufacturing, and spectral estimation. This paper presents novel mathematical programming algorithms for some important constrained regression problems in IRN . For brevity, we focus on four key problems, namely, locally monotonic regression (the optimal counterpart of iterated median filtering), and the related problem of piecewise monotonic regression, runlength-constrained regression (a useful segmentation and edge detection technique), and uni- and oligo- modal regression (of interest in chromatography and spectral estimation). The proposed algorithms are exact and efficient, and they also naturally suggest slightly suboptimal but very fast approximate algorithms, which may be preferable in practice.Item Two-Path Subsets: Efficient Counting and Applications to Performability Analysis(1996) Ball, Michael O.; Hagstrom, Jane N.; Provan, J. Scott; ISRThe problem of computing preformability probabilities in stochastic PERT and flow networks is studied when the networks is ﲭinimally designed to withstand any two component failures. Polynomial-time algorithms to compute preformability when the network is planar -- the nonplanar versions being NP-hard -- solve related ﲴwo-path subset problems. Given an acyclic graph with weights on the arcs, the algorithms compute the total weight of all subsets of arcs that are contained in (1) two source-sink paths or (2) two arc-disjoint source-sink paths. A polynomial algorithm is given for (1), and for (2) in the case where the graph is a source-sink planar k-flow graph, that is edge-minimal with respect to supporting k units of flow.Item Residue Calculus and Effective Nullstellensatz(1996) Berenstein, Carlos A.; Yger, A.; ISRWe provide new tools to compute multidimensional residues for rational functions, even over fields of positive characteristic. As a corollary one obtains solutions of the Betout equation for polynomials over a ring with a site that have almost optimal estimates for degree and size.Item Integrated Manufacturing Facility Design(1995) Ioannou, George; Minis, I.; ISRThis dissertation addresses for the first time the integrated problem of designing the manufacturing shop layout concurrently with its material handling system. Specifically, this study provides a method to derive shop designs that are economic to set up and efficient to operate. In doing so, it considers the following highly interrelated issues: i) The topology of the material flow network, ii) the transporter fleet size and routing, and iii) the layout of the resource groups on the shop floor. The design problem is modeled by a comprehensive mathematical program which captures critical practical concerns such as investment and operational costs, traffic congestion, and transporter capacities. The model is decomposed into three NP- hard subproblems by fixing and/or aggregating variables and constraints. The first subproblem is the generic multi-commodity fixed charge capacitated network design, for which an improved lower bound is derived based on a dual ascent method. This problem is solved by three heuristics that provide near-optimal network designs. The second subproblem concerns the transporter routing, which is a special case of the distance-constrained vehicle routing problem. For the transporter routing problem near-optimal solutions are derived in polynomial time by two efficient heuristics with bounded worst-case performance. Tight lower bounds are provided by solutions to the assignment problem. An integrated method combines the most effective heuristics for the material handling system design subproblems with a simulated annealing scheme to solve the global shop design problem. Our novel approach addresses simultaneously most major decisions involved in manufacturing shop design, and provides globally near optimal solutions. The method is applied to the redesign of the shop of a large manufacturer, and generates a particularly attractive production system design reducing significantly both investment and operational costs, while providing for smooth system operation.