<p> Service Oriented Architectures (SOA) are an emerging software engineering discipline that builds software systems and applications by connecting and integrating well-defined, distributed, reusable software service instances. SOA can speed development time and reduce costs by encouraging reuse, but this new service paradigm presents significant challenges. Many SOA applications are dependent upon service instances maintained by vendors and/or separate organizations. Applications and composed services using disparate providers typically demonstrate limited autonomy with contemporary SOA approaches. Availability may also suffer with the proliferation of possible points of failure&mdash;restoration of functionality often depends upon intervention by human administrators. </p><p> Autonomic computing is a set of technologies that enables self-management of computer systems. When applied to SOA systems, autonomic computing can provide automatic detection of faults and take restorative action. Additionally, autonomic computing techniques possess optimization capabilities that can leverage the features of SOA (e.g., loose coupling) to enable peak performance in the SOA system's operation. This dissertation demonstrates that autonomic computing techniques can help SOA systems maintain high levels of usefulness and usability. </p><p> This dissertation presents a centralized autonomic controller framework to manage SOA systems in dynamic service environments. The centralized autonomic controller framework can be enhanced through a second meta-optimization framework that automates the selection of optimization algorithms used in the autonomic controller. A third framework for autonomic meta-controllers can study, learn, adjust, and improve the optimization procedures of the autonomic controller at run-time. Within this framework, two different types of meta-controllers were developed. The <b>Overall Best</b> meta-controller tracks overall performance of different optimization procedures. <b>Context Best</b> meta-controllers attempt to determine the best optimization procedure for the current optimization problem. Three separate Context Best meta-controllers were implemented using different machine learning techniques: 1) K-Nearest Neighbor (<b>KNN MC</b>), 2) Support Vector Machines (SVM) trained offline (<b>Offline SVM</b>), and 3) SVM trained online (<b>Online SVM</b>). </p><p> A detailed set of experiments demonstrated the effectiveness and scalability of the approaches. Autonomic controllers of SOA systems successfully maintained performance on systems with 15, 25, 40, and 65 components. The <b>Overall Best</b> meta-controller successfully identified the best optimization technique and provided excellent performance at all levels of scale. Among the <b>Context Best</b> meta-controllers, the <b>Online SVM</b> meta-controller was tested on the 40 component system and performed better than the <b>Overall Best</b> meta-controller at a 95% confidence level. Evidence indicates that the <b>Online SVM</b> was successfully learning which optimization procedures were best applied to encountered optimization problems. The <b>KNN MC</b> and <b>Offline SVM</b> were less successful. The <b>KNN MC</b> struggled because the KNN algorithm does not account for the asymmetric cost of prediction errors. The <b>Offline SVM</b> was unable to predict the correct optimization procedure with sufficient accuracy&mdash;this was likely due to the challenge of building a relevant offline training set. The meta-optimization framework, which was tested on the 65 component system, successfully improved the optimization techniques used by the autonomic controller. </p><p> The meta-optimization and meta-controller frameworks described in this dissertation have broad applicability in autonomic computing and related fields. This dissertation also details a technique for measuring the overlap of two populations of points, establishes an approach for using penalty weights to address one-sided overfitting by SVM on asymmetric data sets, and develops a set of high performance data structure and heuristic search templates for C++.</p>

<p> Real-Time Strategy games have become a new frontier of artificial intelligence research. Advances in real-time strategy game AI, like with chess and checkers before, will significantly advance the state of the art in AI research. This thesis aims to investigate using heuristic search algorithms to generate effective micro behaviors in combat scenarios for real-time strategy games. <i> Macro</i> and <i>micro</i> management are two key aspects of real-time strategy games. While good macro helps a player collect more resources and build more units, good micro helps a player win skirmishes against equal numbers of opponent units or win even when outnumbered. In this research, we use influence maps and potential fields as a basis representation to evolve micro behaviors. We first compare genetic algorithms against two types of hill climbers for generating competitive unit micro management. Second, we investigated the use of case-injected genetic algorithms to quickly and reliably generate high quality micro behaviors. Then we compactly encoded micro behaviors including influence maps, potential fields, and reactive control into fourteen parameters and used genetic algorithms to search for a complete micro bot, <i> ECSLBot.</i> We compare the performance of our ECSLBot with two state of the art bots, <i>UAlbertaBot</i> and <i>Nova,</i> on several skirmish scenarios in a popular real-time strategy game <i>StarCraft. </i> The results show that the ECSLBot tuned by genetic algorithms outperforms UAlbertaBot and Nova in kiting efficiency, target selection, and fleeing. In addition, the same approach works to create competitive micro behaviors in another game <i>SeaCraft.</i> Using parallelized genetic algorithms to evolve parameters in SeaCraft we are able to speed up the evolutionary process from twenty one hours to nine minutes. We believe this work provides evidence that genetic algorithms and our representation may be a viable approach to creating effective micro behaviors for winning skirmishes in real-time strategy games.</p>

<p> Action selection for an autonomous agent was studied within the confines of truck task scheduling. An experimental setup was established to compare a naive selection approach, a simple market-based optimization approach, and a learning-assisted market-based optimization over a series of scenarios with varying complexity. For sufficiently complex scenarios, the results showed that learning was able to improve the performance of the truck by delaying delivery to a given site until it was the most protable action available. This research adds to the existing autonomous planning research by demonstrating a novel approach for planning under resource constraints. This approach improves upon an existing market-based optimization technique through the use of on-line reinforcement learning for market adjustment.</p>

<p> This thesis addresses the problem of performing probabilistic inference in stochastic systems where the probability mass is far from uniformly distributed among all possible outcomes. Such <i>near-deterministic</i> systems arise in several real-world applications. For example, in human physiology, the widely varying evolution rates of physiological variables make certain trajectories much more likely than others; in natural language, a very small fraction of all possible word sequences accounts for a disproportionately high amount of probability under a language model. In such settings, it is often possible to obtain significant computational savings by focusing on the outcomes where the probability mass is concentrated. This contrasts with existing algorithms in probabilistic inference---such as junction tree, sum product, and belief propagation algorithms---which are well-tuned to exploit conditional independence relations. </p><p> The first topic addressed in this thesis is the structure of discrete-time temporal graphical models of near-deterministic stochastic processes. We show how the structure depends on the ratios between the size of the time step and the effective rates of change of the variables. We also prove that accurate approximations can often be obtained by sparse structures even for very large time steps. Besides providing an intuitive reason for causal sparsity in discrete temporal models, the sparsity also speeds up inference. </p><p> The next contribution is an eigenvalue algorithm for a linear factored system (e.g., dynamic Bayesian network), where existing algorithms do not scale since the size of the system is exponential in the number of variables. Using a combination of graphical model inference algorithms and numerical methods for spectral analysis, we propose an approximate spectral algorithm which operates in the factored representation and is exponentially faster than previous algorithms. </p><p> The third contribution is a temporally abstracted Viterbi (TAV) algorithm. Starting with a spatio-temporally abstracted coarse representation of the original problem, the TAV algorithm iteratively refines the search space for the Viterbi path via spatial and temporal refinements. The algorithm is guaranteed to converge to the optimal solution with the use of admissible heuristic costs in the abstract levels and is much faster than the Viterbi algorithm for near-deterministic systems. </p><p> The fourth contribution is a hierarchical image/video segmentation algorithm, that shares some of the ideas used in the TAV algorithm. A supervoxel tree provides the abstraction hierarchy for this application. The algorithm starts working with the coarsest level supervoxels, and refines portions of the tree which are likely to have multiple labels. Several existing segmentation algorithms can be used to solve the energy minimization problem in each iteration, and admissible heuristic costs once again guarantee optimality. Since large contiguous patches exist in images and videos, this approach is more computationally efficient than solving the problem at the finest level of supervoxels. </p><p> The final contribution is a family of Markov Chain Monte Carlo (MCMC) algorithms for near-deterministic systems when there exists an efficient algorithm to sample solutions for the corresponding deterministic problem. In such a case, a generic MCMC algorithm's performance worsens as the problem becomes more deterministic despite the existence of the efficient algorithm in the deterministic limit. MCMC algorithms designed using our methodology can bridge this gap. </p><p> The computational speedups we obtain through the various new algorithms presented in this thesis show that it is indeed possible to exploit near-determinism in probabilistic systems. Near-determinism, much like conditional independence, is a potential (and promising) source of computational savings for both exact and approximate inference. It is a direction that warrants more understanding and better generalized algorithms.</p>

Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2006. / Source: Dissertation Abstracts International, Volume: 68-02, Section: B, page: 1090. Adviser: Gul Agha. Includes bibliographical references (leaves 190-205) Available on microfilm from Pro Quest Information and Learning.

Thesis (PH.D.) -- Syracuse University, 2007. / "Publication number AAT 3266311"

Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2007. / Source: Dissertation Abstracts International, Volume: 68-11, Section: B, page: 7454. Adviser: Sylvian R. Ray. Includes bibliographical references (leaves 105-113) Available on microfilm from Pro Quest Information and Learning.

Thesis (Ph.D.)--Indiana University, Dept. of Computer Science, 2007. / Title from PDF t.p. (viewed Nov. 3, 2008). Source: Dissertation Abstracts International, Volume: 68-08, Section: B, page: 5349.

Thesis (Ph.D.)--Indiana University, Dept. of Computer Science, 2007.

Thesis (Ph. D.)--University of Illinois at Urbana-Champaign, 2008. / Source: Dissertation Abstracts International, Volume: 69-05, Section: B, page: 3089. Adviser: Jean Ponce. Includes bibliographical references (leaves 113-120). Available on microfilm from Pro Quest Information and Learning.