Dept. of Industrial and Enterprise Systems Engineering
http://hdl.handle.net/2142/16358
Sun, 24 May 2015 09:45:54 GMT2015-05-24T09:45:54ZVariations in the Forward Motion of Farm Tractors
http://hdl.handle.net/2142/76878
Variations in the Forward Motion of Farm Tractors
Engineering, Agricultural
Tue, 01 Jan 1974 00:00:00 GMThttp://hdl.handle.net/2142/768781974-01-01T00:00:00ZA Probabilistic-Approach to Trajectory Sensitivity
http://hdl.handle.net/2142/76877
A Probabilistic-Approach to Trajectory Sensitivity
Engineering, System Science
Mon, 01 Jan 1973 00:00:00 GMThttp://hdl.handle.net/2142/768771973-01-01T00:00:00ZSystem Simulation Output Analysis by Autoregressive-Integrated Moving Average Models
http://hdl.handle.net/2142/76876
System Simulation Output Analysis by Autoregressive-Integrated Moving Average Models
Engineering, Industrial
Sat, 01 Jan 1972 00:00:00 GMThttp://hdl.handle.net/2142/768761972-01-01T00:00:00ZClustering, coverage and aggregation methods for large networks
http://hdl.handle.net/2142/72930
Clustering, coverage and aggregation methods for large networks
The work in this thesis presents methods for clustering and aggregation of large dynamic networked systems, typically consisting of numerous units/subsystems with complex interactions. Networked system models are used in many scientific and real world applications, for example to describe functional relationships among neurons in the brain, to achieve consensus in the design of communication and controller actuation rules in multi-agent systems, and to estimate multiple service demands in web-based software systems in order to enhance service quality by web cluster relocation. The level of complexity in modeling, analysis, and control synthesis for these systems increases combinatorially with the number of constituent elements in the network. This thesis presents methods for obtaining concise aggregated representations of such systems, while capturing important and relevant interconnectivity information.
In the first part of this thesis, we develop a theoretical framework for aggregating systems that are represented by directed weighted graphs. In this framework, we formulate an optimization problem, with the goal of minimizing a dissimilarity function that captures the distance between the representative and the original graphs. We propose a class of dissimilarity measures and introduce the notion of composite graph sets allowing us to compare directed weighted graphs that contain different numbers of nodes. The dissimilarity measures capture node similarities based on node connectivity, and in the simplest case reduce to metrics previously defined for equal-sized undirected unweighted graphs. The representative graph is determined by systematically identifying and aggregating similar nodes of the original graph into supernodes, and then determining the inter supernode connectivities. The key challenge herein is in overcoming the computational complexity that arises in iteratively solving two combinatorial optimization problems corresponding to evaluating and minimizing the cost function (dissimilarity measure). In our formulation, using the composite graph sets, only a single optimization problem is needed in every iteration. Further, we introduce a maximum entropy based soft aggregation approach for node clustering, and propose a multi-scaled aggregation method whose central part incorporates the Deterministic Annealing algorithm. Specifically, we solve a sequence of relaxed minimization problems by allowing soft cluster associations; as we gradually decrease the level of softness, the solution for the original problem is approached. We discuss graph structures for which this aggregation method is provably effective, and provide comprehensive simulation examples demonstrating this efficacy.
As a special case, we study the reduction of Markov chains. By viewing a Markov chain as a directed weighted graph, the graph aggregation techniques we propose are directly applicable. If we consider nearly completely decomposable Markov chains, that is, chains whose transition matrices P can be written as a perturbation added to a completely decomposable (reducible) chain P*, i.e., P = P* + eC, then we provide sufficient conditions under which our method guarantees recovery of the decomposable sub-chain structure indicated by P*, thus yielding easily verifiable conditions to corroborate results given by perturbation theory. We then derive upper bound on how close the stationary distribution of aggregated Markov chain is to the aggregated stationary distribution of the original Markov chain. The effectiveness of this method has been demonstrated through numerous examples at a variety of scales. We further apply this aggregation method to reduce systems consisting of interactive stochastic processes that can be represented by graph models. In particular, we study seismic activities at different geological locations, with parametric generative models characterizing the influences among every location. In this scenario, ensemble interactions within the system can be discovered by clustering the underlying graph model.
In the second part of this thesis, we consider dynamic clustering and coverage problems. The goal is to use a small number of resources to provide continuous and sufficient coverage for a large number of moving objects. We integrate control-theoretic methods, specifically Lyapunov-based analysis, into our aggregation framework. Specifically, we adaptively compute the actuation rules for all resources to achieve the tracking objective, in addition to a set of optimal resource locations for fixed time-instances. For systems where moving objects are driven by acceleration fields, we show that a dynamic control is necessary to achieve dynamic coverage, and provide closed-form solutions for the resource dynamics. The algorithms we propose guarantee asymptotic tracking of cluster group dynamics, and we further establish continuity and boundedness of the corresponding control laws. The algorithm has been successfully applied to many systems with a large number of dynamic sites, and we provide examples in this thesis to corroborate the results.
Clustering; Maximum Entropy Principle; Dynamic Coverage Control; Deterministic Annealing
Wed, 21 Jan 2015 00:00:00 GMThttp://hdl.handle.net/2142/729302015-01-21T00:00:00ZCentralized and distributed resource allocation with applications to signal processing in communications
http://hdl.handle.net/2142/72870
Centralized and distributed resource allocation with applications to signal processing in communications
Nowadays, wired and wireless networks are used everywhere and everyday. With the increasing popularity of multiuser communication systems, their optimal performance has become a crucial field of study during the last decades. A factor that greatly determines such performance is the optimal allocation of the resources available to the agents in the network. This dissertation provides a set of optimization techniques applicable to rigorously address and deeply analyze multiuser resource allocation problems in different areas, ranging from signal processing, to communications and networking. More specifically, this work focuses on the three main topics that we briefly describe next.
First, we study the maximum sum-utility achieved when a noncooperative approach is used to allocate the spectrum in a communication system adopting a dynamic spectrum management framework. In particular, we turn our attention to the case in which the users in the system are endowed with infinite power budgets. This asymptotic analysis, based on the linear complementarity problem theory, leads us characterize the behavior of the system's utility as the power budget is increased toward infinity, and thus draw interesting conclusions on the efficiency of the Nash equilibrium and the Braess-type paradox, among others.
Second, we propose a novel class of distributed algorithms for the optimization of nonconvex and nonseparable sum-utility functions subject to convex coupling constraints. Even though, we focus on utility functions of the Difference of Convex (DC) type, further generalizations are possible. Moreover, the obtained iterative schemes are provable convergent to stationary points of such optimization problems. Among the different applications of our Successive Convex Approximationsbased algorithms, we direct our attention to a novel resource allocation problem in the emerging field of physical layer based security, and to the well-known MIMO (Multiple-Input-Multiple-Output) Cognitive Radio sum-rate maximization problem. For the former application, we develop a mathematically rigorous analysis of the nondifferentiable and nonconvex game (of the generalized type) proposed to optimally allocate the network resources in this context; and finally, we apply our algorithms to find relaxed equilibrium points of the mentioned game. For the second application, our theory provides, for the first time, a provable convergent algorithm.
The third major topic of this dissertation analyzes a multiuser maximization problem where the utility function has a particular structure, namely, it is the sum of continuous maximum functions, subject to private and coupling constraints. We follow two different approaches in order to design provable convergent algorithms to address this problem. These approaches are based on simpler reformulations of the nondifferentiable and nonconcave optimization problem of interest. A careful analysis relating such problems is also developed. The cited results pave the way to devise (possibly distributed) algorithms for different system designs in the context of physical layer based security, ranging from the secrecy sum-rate maximization to the Max-Min fairness problem. It is important to emphasize that, different from the simple networks models considered in the physical layer security literature, the system designs studied in this dissertation involve networks composed of multiple legitimate users and friendly jammers, and a single eavesdropper, where the main users communicate over multiple (either orthogonal or non-orthogonal) subchannels.
Finally, it is worth mentioning that most of the tools and results developed in this work are general enough to encompass applications in many fields different from those described above. This dissertation highlights how the introduction of optimization theory in different signal processing applications has motivated several significant developments in the former field, in particular in the area of multiuser distributed optimization. Future research directions are provided at the end of each chapter.
Distributed optimization; Resource allocation; Nash equilibrium; Game theory; Difference of convex programming; Nonconvex and nondifferentiable optimization; Successive convex approximation; Multiuser systems; Dynamic spectrum management; Cooperative physical layer security; Cognitive radio
Wed, 21 Jan 2015 00:00:00 GMThttp://hdl.handle.net/2142/728702015-01-21T00:00:00ZRecognizing expressive movement in arm gestures using Hidden Markov Models
http://hdl.handle.net/2142/72866
Recognizing expressive movement in arm gestures using Hidden Markov Models
Movement is one of the most basic human skills that used for communicating and interacting with the environment. Although we have an intuitive understanding of our gestures, it is hard to explain their quality. One would describe the human gestures as a collection of various actions for performing different tasks. True, but it does not explain how the tasks are performed, which is essential for having a more natural representation of movement. In this work we use Laban Movement Analysis (LMA), which is an analytic and experiential system for interpreting human body movement, to understand the expressive aspects of human gestures and we try to recognize them in hand movement using a supervised learning method with Hidden Markov Models (HMMs),;
We first define the weight, space, and time characteristics of movement, which are described as the Basic Effort Factors (BEF) in LMA and we construct a classifier for each BEF using HMMs. We use a Microsoft Kinect to capture the body movement and try to recognize the quality of each BEF in hand gestures. Various preprocessing are done on the motion data to extract features that can describe the movement qualities. We use a windowing technique to segment the gestures into smaller sequences and allow for continuous gesture recognition. Various experiments are done to identify the optimal features and the parameters of each model, and we also address different problems in implementing the models.;
Our research showed promising results in recognizing and distinguishing the BEFs of hand movement. The importance of this research is in developing systems that require deeper and more natural understanding of body movement, such as systems for recognizing musical gestures and dance, or producing computer animation.
Gesture Recognition; Laban Movement Analysis; Expressive Movement; Hidden Markov Models
Wed, 21 Jan 2015 00:00:00 GMThttp://hdl.handle.net/2142/728662015-01-21T00:00:00ZUncapacitated Lot-Sizing Problems With Setup Interactions
http://hdl.handle.net/2142/72551
Uncapacitated Lot-Sizing Problems With Setup Interactions
Lot-sizing problems focus on determining a minimal total production cost schedule. These production costs are generally composed of three components: a variable production cost, an inventory holding cost, and a setup cost. The optimal solution balances the holding costs against the setup and variable costs. In most of the research in this area, product interaction is incorporated by considering the products to be in competition for fixed production capacities. However, there exist problems in which distinct products are more closely coupled.; This dissertation focuses on the effect of setup interactions on the uncapacitated lot-sizing problem (ULSP) with time varying demand patterns. We consider three major instances of setup interactions in the ULSP: the Joint Replenishment Problem (JRP), the Weak Interaction Problem (WIP), and the Strong Interaction Problem (SIP). For each of the problems computational complexity boundaries are established. The general instance of all three problems is shown to be NP-Complete. Membership in this computationally intractable class of problems, necessitates the development of strong bounding techniques and effective branching rules which can be incorporated into an exact solution procedure. Each problem is formulated as a linear integer program. Different formulations are presented which exploit various properties of the problems. Relationships between the formulations and the problems are demonstrated.; A dual ascent procedure is developed for the JRP. The procedure exploits the structure of a Lagrangean dual of the problem. Efficient schemes are employed to solve the resulting sub-problems and to determine ascent directions. Branching rules and penalties based on the problem structure are incorporated into an exact numerical procedure. Testing indicates that these bounds can be used to obtain up to a tenfold improvement in performance over a well-known commercial solver (IBM/OSL). For the WIP, bounding procedures and heuristics are presented which yield near optimal solutions with minimal computational effort. Finally, bounding schemes based on a Lagrangean decomposition that result in a WIP are presented for the SIP. This new bounding technique is incorporated into an enumerative solution procedure which reduces the computational effort required to solve the SIP by 50 to 95 percent.
Engineering, Industrial; Operations Research
Fri, 01 Jan 1993 00:00:00 GMThttp://hdl.handle.net/2142/725511993-01-01T00:00:00ZDisjunctive normal formula based supervisory control policy for general Petri nets
http://hdl.handle.net/2142/50715
Disjunctive normal formula based supervisory control policy for general Petri nets
A Petri net (PN) is said to be live if it is possible to re any transition, although not
immediately, from every reachable marking. A liveness enforcing supervisory policy (LESP)
determines which controllable transition is to be prevented from ring at a marking, to
ensure the supervised Petri net (PN) is live.
A LESP is said to be minimally restrictive if the following property is true { if a minimally
restrictive LESP prevents the ring of a transition at a marking, then all other LESPs should
do the same.
We restrict our attention to a class of general Petri nets (PN) structures, where the
existence of an LESP for an instance initialized at a marking, implies the existence of an
LESP when the same instance is initialized with a larger initial marking. We show that the
minimally restrictive LESP for an instance N from this class is characterized by a collection of
boolean formulae f tc(N)gtc2Tc , where Tc is the set of controllable transitions in the PN. The
literals in tc(N) are true if and only if the token-load of speci c places meet a threshold.
Consequently, appropriately placed threshold-sensors, which detect if the token-load of a
place is greater than or equal to a predetermined threshold, provide su cient information
to implement the minimally restrictive LESP.
Petri Nets
Tue, 16 Sep 2014 00:00:00 GMThttp://hdl.handle.net/2142/507152014-09-16T00:00:00ZMilitary budget decisions: inferring trade-offs using decision analysis
http://hdl.handle.net/2142/50665
Military budget decisions: inferring trade-offs using decision analysis
This thesis uses a decision analytic framework to assess how the United States Army makes trade-offs involving monetary resources and the potential loss of human life. Data for the study looks at the Army budget for a four year period from 2008-2011, with a focus on spending for combat and suicide prevention, and the loss of life experienced in both areas. This data is used to answer two research questions: (i) Does available data suggest the Army makes consistent trade-offs between money and human life? (ii) How can value using inferred trade-offs be used for decisions relating to the Army budget?
To answer the research questions, a basic model is derived from the data. Curve-fitting of historical data is used to infer trade-offs, as a causal relationship is assumed to exist between the spending level and the loss of lives. For the purposes of this study, the best curve-fit is assumed to represent an indifference by the decision maker to increased spending along the line if it results in a corresponding decreased loss of life. In response to the first question, the model shows that there is the potential that the Army makes inconsistent trade-offs across these areas, and explores the possible implications if these trade-offs are truly inconsistent. After addressing the possible implications of the model developed, the model is used to address the second question by showing how a value-based model can be used for the decision of budget allocation for the Army, which is especially pressing given the recently imposed budget cap that impact the US Department of Defense. Limitations of the study are addressed, along with areas for future research to expand on the initial results presented in this study.
Decision Analysis; Military Decision Making; Trade-Off Analysis
Tue, 16 Sep 2014 00:00:00 GMThttp://hdl.handle.net/2142/506652014-09-16T00:00:00ZVisualization impacts on utility functions and multiattribute utility copula approach toward electronic product recovery techniques
http://hdl.handle.net/2142/50608
Visualization impacts on utility functions and multiattribute utility copula approach toward electronic product recovery techniques
This thesis provides an initial analysis incorporating two different decision fields: aircraft repair and end-of-life electronic product recovery. The relationship between visuals of aircraft damage and user manipulation of cost models were studied in relation to their effect on the user’s understanding of the decision problem. The analysis involved using metrics to show the understanding of the attributes, tradeoffs needed and any alterations to the preference function. Lifecycle analysis was conducted on cellphones in order to understand the impact that electronic waste can have on the environment. A multiattribute utility copula approach was used in analyzing the behavior of EOL processing activities on the part of an OEM. This decision-making tool was used in order to incorporate the firm’s preferences while accounting for uncertainty with the incoming disposed cellphone feedstock used for demonstration.
The results generated during this thesis work indicated several important issues. The use of damage visuals along with model interaction caused changes in valuation of attributes and willingness to make tradeoffs among them. There were also changes in the risk attitudes as shown by shifts in the utility curves between studies. This has implications for how visualization and interaction can be used to assess and direct risk behavior in many different fields. The lifecycle analysis results indicated areas of the cellphone that were most impactful on the environment. This baseline estimate also gave insight into possible redesign options based on minimization of negative environmental impact. The multiattribute utility copula approach results described a process of determining among different specific EOL processing activities. The extraction of sub-assemblies was determined as the best decision alternative to recapture value at the disposal stage of the product lifecycle. The copula structure can be used to take into account a firm’s preferences as well as attribute valuation providing a powerful straightforward tool for decision-making under uncertainty in various fields other than electronic product recovery options.
Product End-Of-Life Recovery; Remanufacturing; Utility Functions; Utility Copula
Tue, 16 Sep 2014 00:00:00 GMThttp://hdl.handle.net/2142/506082014-09-16T00:00:00Z