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 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 Fast Map: A Fast Algorithms for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets(1994) Faloutsos, Christos; Lin, King-Ip D.; ISRA very promising idea for fast searching in traditional and multimedia databases is to map objects into points in k-d space, using k feature-extraction functions, provided by a domain expert [Jag91]. Thus, we can subsequently use highly fine-tuned spatial access methods (SAMs), to answer several types of queries, including the uery By Example' type (which translates to a range query); the ll pairs' query (which translates to a spatial join [BKSS94]); the nearest-neighbor or best match query, etc.However, designing feature extraction functions can be hard. It is relatively easier for a domain expert to assess the similarity/distance of two objects. Given only the distance information though, it is not obvious how to map objects into points.
This is exactly the topic of this paper. We describe a fast algorithm to map objects into points in some k- dimensional space ( k is user-defined), such that the dis-similarities are preserved. There are two benefits from this mapping: (a) efficient retrieval, in conjunction with a SAM, ad discussed before and (b) visualization and data-mining: the objects can now be plotted as points in 2-d or 3-d space, revealing potential clusters, correlations among attributes and other regularities that data-mining is looking for.
We introduce an older method from pattern recognition, namely, multi-Dimentional Scaling (MIDS) [Tor52]; although unsuitable for indexing, we use it as yardstick for our method. Then, we propose a much faster algorithm to solve the problem in hand, while in addition it allows for indexing. Experiments on real and synthetic data indeed show that the proposed algorithm is significantly faster than MIDS, (being linear, as opposed to quadratic, on the database size N), while it manages to preserve distances and the overall structure of the data-set.
Item Hierarchical Production Planning for Complex Manufacturing(1994) Mehra, Anshu; Minis, Ioannis; Proth, J.M.; ISRA hierarchical approach to production planning for complex manufacturing systems is presented. A single facility comprising of a number of work-centers that produce multiple part types is considered. The planning horizon includes a sequence of time periods, and the demand for all part types is assumed to be known. The production planning problem consists of minimizing the holding costs for all part types as well as the work-in- process, and the backlogging cost for the end items. We present a two- level hierarchy that is based on aggregating parts to part families, work-centers to manufacturing cells and time periods to aggregate time periods. The solution at the aggregate level is imposed as a constraint to the detailed level problem which employs a decomposition based on manufacturing cells. This architecture uses a rolling horizon strategy to perform the production management function. We have employed perturbation analysis techniques to adjust certain parameters of the optimization problems at the detailed level to reach a near- optimal detailed production plan.Item A Practical Method for Design of Hybrid-Type Production Facilities(1994) Harhalakis, George; Lu, Thomas C.; Minis, Ioannis; Nagi, R.; ISRA comprehensive methodology for the design of hybrid-type production shops that comprise both manufacturing cells and individual workcenters is presented. It targets the minimization of the material handling effort within the shop and comprises four basic steps: (1) identification of candidate manufacturing cells, (2) evaluation and selection of the cells to be implemented, (3) determination of the intra-cell layout, and (4) determination of the shop layout. For the cell formation step the ICTMM technique has been enhanced to cater for important practical issues. The layout of each significant cell is determined by a simulated annealing (SA)-based algorithm. Once the sizes and shapes of the selected cells are known, the shop layout is determined by a similar algorithm. The resulting hybrid shop consists of the selected cells and the remaining machines. The methodology has been implemented in an integrated software system and has been applied to redesign the shop of a large manufacturer of radar antennas.Item Hierarchical Modeling Approach for Production Planning(1992) Harhalakis, George; Nagi, R.; Proth, J.M.; ISRProduction management problems are complex owing to large dimensionality, wide variety of decisions of varying scope, focus and time-horizon, and disturbances. A hierarchical approach to these problems is a way to address this complexity, wherein the global problem is decomposed into a series of top-down sub- problems. We advocate that a single planning architecture cannot be employed for all planning problems. We propose a multi-layer hierarchical decomposition which is dependent on the complexity of the problem, and identify the factors influencing complexity. A systematic stepwise design approach for the construction of the hierarchy and inputs required are presented. The subsequent operation of the hierarchy in an unreliable environment is also explained. Aggregation schemes for model reduction have been developed and blended with a time-scale decomposition of activities to provide the theoretical foundation of the architecture. It is also hoped that this methodology can be applied to other such large-scale complex decision making problems.Item Design and Operation of Hierarchical Production Management Systems(1991) Nagi, R.; Harhalakis, G.; ISRProduction Planning Management and Control of a production system subject to random events are challenging problems. A multi-layer hierarchical approach to tactical and aggregate production planning problems is proposed, wherein the architecture is strongly based on the specific physical system, applicable controls and the complexity of the decision making problem at hand. We address the design and operation of such Hierarchical production Management Systems (HPMS). Regarding the design aspect, we start by developing schemes for product, machine and temporal aggregation; consistency and controllability issues in the hierarchy have been addressed in the aggregation/disaggregation schemes. These three aggregation schemes for model reduction have been developed and incorporated to the time-scale decomposition of activities, in order to provide a solid theoretical foundation of the architecture. We then proceed to a systematic stepwise design approach for the construction of the hierarchy. It provides the appropriate number of layers and an associated Model as well as Decision Making Problem (DMP) at each level. A model is defined by entities, attributes, links and domains, while a DMP is defined by a set of possible controls (decisions), constraints, and optimality criteria to be optimized over a planning horizon. The operation of the hierarchy consists of a topdown computation of controls, which calls for the resolution of an optimization problem at each level of the hierarchy. The solution of any problem in sequence determines some parameters in the subsequent problem. We detail the mechanism for top-down constraint propagation, which is important in ensuring consistency of criteria and feasibility. The execution then involves the bottom-up feedbacks, and a revision in the plan is carried out if necessary. In particular, the rolling horizon mechanism, and the reaction of the hierarchy to random events has been detailed. A generic job-shop example has been employed to present the design and operation of the HPMS. It is hoped that this methodology can be applied to other types of large-scale complex decision making problems.Item Manufacturing Cell Design Using Simulated Annealing: an Industrial Application(1990) Harhalakis, George; Proth, J.M.; Xie, X.L.; ISRIn this paper, we give a brief summary of simulated annealing procedures used to solve combinatorial optimization problems. We then present the manufacturing cell design problem which consists of designing cells of limited size in order to minimize inter- cell traffic. We show how to use a SA approach to obtain a good, if not optimum, solution to this problem. Finally, we apply this approach to an industrial problem and compare the results to the ones obtained using the so-called twofold heuristic algorithm.