Computer Science Theses and Dissertations
http://hdl.handle.net/1903/2756
2016-05-29T19:02:18ZModel-Predictive Strategy Generation for Multi-Agent Pursuit-Evasion Games
http://hdl.handle.net/1903/17299
Model-Predictive Strategy Generation for Multi-Agent Pursuit-Evasion Games
Raboin, Eric James
Multi-agent pursuit-evasion games can be used to model a variety of different real world problems including surveillance, search-and-rescue, and defense-related scenarios. However, many pursuit-evasion problems are computationally difficult, which can be problematic for domains with complex geometry or large numbers of agents. To compound matters further, practical applications often require planning methods to operate under high levels of uncertainty or meet strict running-time requirements. These challenges strongly suggest that heuristic methods are needed to address pursuit-evasion problems in the real world.
In this dissertation I present heuristic planning techniques for three related problem domains: visibility-based pursuit-evasion, target following with differential motion constraints, and distributed asset guarding with unmanned sea-surface vehicles. For these domains, I demonstrate that heuristic techniques based on problem relaxation and model-predictive simulation can be used to efficiently perform low-level control action selection, motion goal selection, and high-level task allocation.
In particular, I introduce a polynomial-time algorithm for control action selection in visibility-based pursuit-evasion games, where a team of pursuers must minimize uncertainty about the location of an evader. The algorithm uses problem relaxation to estimate future states of the game. I also show how to incorporate a probabilistic opponent model learned from interaction traces of prior games into the algorithm. I verify experimentally that by performing Monte Carlo sampling over the learned model to estimate the location of the evader, the algorithm performs better than existing planning approaches based on worst-case analysis.
Next, I introduce an algorithm for motion goal selection in pursuit-evasion scenarios with unmanned boats. I show how a probabilistic model accounting for differential motion constraints can be used to project the future positions of the target boat. Motion goals for the pursuer boat can then be selected based on those projections. I verify experimentally that motion goals selected with this technique are better optimized for travel time and proximity to the target boat when compared to motion goals selected based on the current position of the target boat.
Finally, I introduce a task-allocation technique for a team of unmanned sea-surface vehicles (USVs) responsible for guarding a high-valued asset. The team of USVs must intercept and block a set of hostile intruder boats before they reach the asset. The algorithm uses model-predictive simulation to estimate the value of high-level task assignments, which are then realized by a set of learned low-level behaviors. I show experimentally that using model-predictive simulations based on Monte-Carlo sampling is more effective than hand-coded evaluation heuristics.
2015-01-01T00:00:00ZDiffusion, Infection and Social (Information) Network Database
http://hdl.handle.net/1903/17296
Diffusion, Infection and Social (Information) Network Database
Kang, Chanhyun
Research to analyze diffusive phenomena over large rich datasets has received considerable attention in recent years. Moreover, with the appearance and proliferation of online social network services, social (information) network analysis and mining techniques have become closely intertwined with the analysis of diffusive and infection phenomena. In this dissertation, we suggest various analysis and mining techniques to solve problems related to diffusive and infection phenomena over social (information) networks built from various datasets in diverse areas. This research makes five contributions. The first contribution is about influence analysis in social networks for which we suggest two new centrality measures, Diffusion Centrality and Covertness Centrality. Diffusion Centrality quantifies the influence of vertices in social networks with respect to a given diffusion model which explains how a diffusive property is spreading. Covertness Centrality quantifies how well a vertex can communicate (diffuse information) with (to) others and hide in networks as a common vertex w.r.t. a set of centrality measures. The second contribution is about network simplification problems to scale up analysis techniques for very large networks. For this topic, two techniques, CoarseNet and Coarsened Back and Forth (CBAF), are suggested in order to find a succinct representation of networks while preserving key characteristics for diffusion processes on that network. The third contribution is about social network databases. We propose a new network model, STUN (Spatio-Temporal Uncertain Networks), whose edges are characterized with uncertainty, space, and time, and develop a graph index structure to retrieve graph patterns over the network efficiently. The fourth contribution develops epidemic models and ensembles to predict the number of malware infections in countries using past detection history. In our fifth contribution, we also develop methods to predict financial crises of countries using financial connectedness among countries.
2015-01-01T00:00:00ZANALYSIS OF STEADY-STATE AND DYNAMICAL RADIALLY-SYMMETRIC PROBLEMS OF NONLINEAR VISCOELASTICITY
http://hdl.handle.net/1903/17278
ANALYSIS OF STEADY-STATE AND DYNAMICAL RADIALLY-SYMMETRIC PROBLEMS OF NONLINEAR VISCOELASTICITY
Stepanov, Alexey
This thesis treats radially symmetric steady states and radially symmetric motions of nonlinearly elastic and viscoelastic plates and shells subject to dead-load and hydrostatic pressures on their boundaries and with the plate subject to centrifugal force. The plates and shells are described by specializations of the exact (nonlinear) equations of three-dimensional continuum mechanics. The treatment in every case is very general and encompasses large classes of constitutive functions (characterizing the material response).
We first treat the radially symmetric steady states of plates and shells and the radially symmetric steady rotations of plates. We show that the existence, multiplicity, and qualitative behavior of solutions for problems accounting for the live loads due to hydrostatic pressure and centrifugal force depend critically on the material properties of the bodies, physically reasonable refined descriptions of which are given and examined here with great care, and on the nature of boundary conditions.The treatment here, giving new and sharp results, employs several different mathematical tools, ranging from phase-plane analysis to the mathematically more sophisticated direct methods of the Calculus of Variations, fixed-point theorems, and global continuation methods, each of which has different strengths and weaknesses for handling intrinsic difficulties in the mechanics.
We then treat the initial-boundary-value problems for the radially symmetric motions of annular plates and spherical shells that consist of a nonlinearly viscoelastic material of strain-rate type. We discuss a range of physically natural constitutive equations. We first show that when the material is strong in a suitable sense relative to externally applied loads, solutions exist for all time, depend continuously on the data, and consequently are unique. We study the role of the constitutive restrictions and that of the regularity of the data in ensuring the preclusion of a total compression and of an infinite extension for finite time. We then show that when the material is not sufficiently strong then under certain conditions on the (hydrostatic) pressure terms there are globally defined unbounded solutions and there are solutions that blow up in finite time.
The practical importance of these results is that for each problem involving live loads they furnish thresholds in material response delimiting materials for which solutions are ill behaved. A mathematical or numerical study limited to a particular class of materials may dangerously indicate well-behaved solutions when there are other realistic materials for which solutions are ill behaved. Moreover this work furnishes so-called trivial solutions for the subsequent study (not given here) of bifurcation of stable equilibrium configurations from these trivial solutions.
2015-01-01T00:00:00ZAlgorithms and Generalizations for the Lovasz Local Lemma
http://hdl.handle.net/1903/17276
Algorithms and Generalizations for the Lovasz Local Lemma
Harris, David
The Lovasz Local Lemma (LLL) is a cornerstone principle of the probabilistic method for combinatorics. This shows that one can avoid a large of set of “bad-events” (forbidden configurations of variables), provided the local conditions are satisfied. The original probabilistic formulation of this principle did not give efficient algorithms. A breakthrough result of Moser & Tardos led to an framework based on resampling
variables which turns nearly all applications of the LLL into efficient algorithms. We extend and generalize the algorithm of Moser & Tardos in a variety of ways.
We show tighter bounds on the complexity of the Moser-Tardos algorithm, particularly its parallel form. We also give a new, faster parallel algorithm for the LLL.
We show that in some cases, the Moser-Tardos algorithm can converge even thoughthe LLL itself does not apply; we give a new criterion (comparable to the LLL) for determining when this occurs. This leads to improved bounds for k-SAT and hypergraph coloring among other applications.
We describe an extension of the Moser-Tardos algorithm based on partial resampling, and use this to obtain better bounds for problems involving sums of independent random variables, such as column-sparse packing and packet-routing. We describe a variant of the partial resampling algorithm specialized to approximating column-sparse covering integer programs, a generalization of set-cover. We also give hardness reductions and integrality gaps, showing that our partial resampling based algorithm obtains nearly optimal approximation factors.
We give a variant of the Moser-Tardos algorithm for random permutations, one of the few cases of the LLL not covered by the original algorithm of Moser & Tardos. We use this to develop the first constructive algorithms for Latin transversals and hypergraph packing, including parallel algorithms.
We analyze the distribution of variables induced by the Moser-Tardos algorithm. We show it has a random-like structure, which can be used to accelerate the Moser-Tardos algorithm itself as well as to cover problems such as MAX k-SAT in which we only partially avoid bad-events.
2015-01-01T00:00:00Z