Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2006. / Source: Dissertation Abstracts International, Volume: 67-07, Section: B, page: 3896. Adviser: Marco Caccamo. Includes bibliographical references (leaves 127-137) Available on microfilm from Pro Quest Information and Learning.

A partially observable Markov decision process (POMDP) is a model of planning and control that enables reasoning about actions with stochastic effects and observations that provide imperfect information. It has applications in diverse fields that include artificial intelligence, operations research and optimal control, although computational difficulties have limited its use. This thesis presents new dynamic-programming and heuristic-search algorithms for solving infinite-horizon POMDPs. These algorithms represent a plan or policy as a finite-state controller and exploit this representation to improve the efficiency of problem solving. One contribution of this thesis is an improved policy-iteration algorithm that searches in a policy space of finite-state controllers. It is based on a new interpretation of the dynamic-programming operator for POMDPs as the transformation of a finite-state controller into an improved finite-state controller. Empirically, it outperforms value iteration in solving infinite-horizon POMDPs. Dynamic-programming algorithms such as policy iteration and value iteration compute an optimal policy for every possible starting state. An advantage of heuristic search is that it can focus computation on finding an optimal policy for a single starting state. However, it has not been used before to find solutions with loops, that is, solutions that take the form of finite-state controllers. A second contribution of this thesis is to show how to generalize heuristic search to find policies that take this more general form. Three algorithms that use heuristic search to solve POMDPs are presented. Two solve special cases of the POMDP problem. The third solves the general POMDP problem by iteratively improving a finite-state controller in the same way as policy iteration, but focuses computation where it is most likely to improve the value of the controller for a starting state.

The discrete optimization technique called local search yields impressive results on many important combinatorial optimization problems. Its tendency to return solutions that are sub-optimal, however, remains a serious limitation of the approach. In this dissertation we propose and investigate a general technique that seeks to overcome this difficulty while maintaining the speed that makes local search an attractive approach. We focus on constrained problems which have an induced non-uniform neighborhood structure, and we examine three such problems experimentally. Our example set is: (1) a variant of Stock Cutting; (2) a precedence constrained routing problem; and (3) a weighted version of the latter. Using our techniques we have been able to improve significantly the quality of solutions found in each of these domains over that found by the traditional local search algorithm, with only modest increases in running time. Our technique is independent of problem domain and, therefore, is applicable to a wide variety of problems.

This dissertation considers a particular aspect of sequential decision making under uncertainty in which, at each stage, a decision-making agent operating in an uncertain world takes an action that elicits a reinforcement signal and causes the state of the world to change. Optimal learning is a pattern of behavior that yields the highest expected total reward over the entire duration of an agent's interaction with its uncertain world. The problem of determining an optimal learning strategy is a sort of meta-problem, with optimality defined with respect to a distribution of environments that the agent is likely to encounter. Given this prior uncertainty over possible environments, the optimal-learning agent must collect and use information in an intelligent way, balancing greedy exploitation of certainty-equivalent world models with exploratory actions aimed at discerning the true state of nature. My approach to approximating optimal learning strategies retains the full model of the sequential decision process that, in incorporating a Bayesian model for evolving uncertainty about unknown process parameters, takes the form of a Markov decision process defined over a set of “hyperstates” whose cardinality grows exponentially with the planning horizon. I develop computational procedures that retain the full Bayesian formulation, but sidestep intractability by utilizing techniques from reinforcement learning theory (specifically, Monte-Carlo simulation and the adoption of parameterized function approximators). By pursuing an approach that is grounded in a complete Bayesian world model, I develop algorithms that produce policies that exhibit performance gains over simple heuristics. Moreover, in contrast to many heuristics, the justification or legitimacy of the policies follows directly from the fact that they are clearly motivated by a complete characterization of the underlying decision problem to be solved. This dissertation's contributions include a reinforcement learning algorithm for estimating Gittins indices for multi-armed bandit problems, a Monte-Carlo gradient-based algorithm for approximating solutions to general problems of optimal learning, a gradient-based scheme for improving optimal learning policies instantiated as finite-state stochastic automata, and an investigation of diffusion processes as analytical models for evolving uncertainty.

We consider a class of resource control problems in communication systems, such as packet-switched networks and telephone networks, which consist of spatially distributed resources and multiple controllers. In the problems we examine, small units of work (messages, telephone calls) arrive randomly in large numbers to the system, utilize some resources and then leave. In controlling system parameters on-line for the optimal usage of these resources, it is often prohibitively expensive to pass around instantaneous state information to the controllers in order to facilitate dynamic scheduling and thus, what is desirable is optimization with respect to some long term statistics of the random system behavior. We study the case in which little is assumed about the effects of the control parameters on the networks' performance. In this case on-line measurements (prone to random errors or noise) can still be taken and used to help improve performance. A general technique for using such error-prone measurements to iteratively improve system performance, called stochastic approximation, has been advanced since the 50's and studied extensively. We study the use of resource allocation algorithms based on stochastic approximation, present a new stochastic approximation technique and demonstrate its use in a class of chosen problems. The new technique is shown to have several advantages, including the ability to handle estimator bias, which is prevalent in several known estimators. Both theoretical and experimental results have been obtained, including the case of multiple, asynchronously operating controllers and where control parameter constraints are unknown and must themselves be estimated.

Memory system design is important for providing high reliability and availability. This dissertation presents a memory architecture to support checkpoints that can improve reliability, and also algorithms to improve recoverable virtual memory. In addition, two novel techniques of reliability analysis are presented that account for program and operating system behavior. Checkpoint and rollback recovery is a method that allows a system to tolerate a failure by periodically saving the state and, if an error occurs, rolling back to the prior checkpoint. A technique is proposed that embeds the support for checkpoint and rollback recovery directly into the virtual memory translation hardware. A system with both highly reliable and normal memory enables recoverable virtual memory by placing modified data in the highly reliable memory and read-only data in normal memory. Hybrid algorithms are proposed for use in systems with multiple classes of physical memory; that is, one virtual memory policy for the highly reliable memory and one for the normal memory. These techniques are analyzed with a trace-driven simulation. Reliability analysis of memories and their relationship to system reliability is an important aspect of system design. The dynamic aspects of the memory are very important. Two aspects studied here are memory usage patterns by a program and the memory allocation by the operating system. A new model is developed for the successful execution of a program taking into account memory reference patterns. This is contrasted against traditional memory reliability calculations showing that the actual reliability may be more optimistic when program behavior is considered. A new theory to explain correlations between increased workloads and increased failure rates is proposed. The tradeoffs in performance and reliability for memory management policies (e.g., virtual or cache memory) are studied as a function of the block-miss reload time. A very small percentage of the memory is found to contribute to a majority of the unreliability. Techniques are proposed to dramatically improve the reliability (i.e., an algorithm called selective scrubbing and the use of very small amounts of highly reliable memory).

The technologies of Artificial Intelligence enable the application of many new techniques to address some of the more difficult unstructured problems that exist in various manufacturing domains. This dissertation explores the issue of how differing views of reality can be simultaneously represented and interpreted within one modelling environment. The domain of investigation is the determination of manufacturing strategy in a large global industrial firm. The focus of the research is on the reasonableness of arguments from descriptive models of the manufacturing enterprise. Dealing with differing views on reality simultaneously, involves consideration of which factors are reasonable premises to argue from, which factors should be ignored, what is the appropriate level of aggregation in the model and how should conflicting evidence be reconciled. The architecture described in this dissertation is based on applying alternative reasoning methods to available information and then looking at the attributes of the alternative conclusions that are reached. In this manner, diverse and likely inconsistent knowledge such as budgets, plans, expectations, causal models, correlational models and historical knowledge are integrated and interpreted within a planning system. In discussing the architecture, the dissertation describes a declarative representation language for constructing models of large scale industrial enterprises. It describes a useful set of reasoning operators that represent some of the typical approaches used by strategic planners. It describes the overall control architecture that applies reasoning operators, reconciliation operators and that maintains dependency between final hypotheses, intermediate hypotheses and the evidence on which they depend. It also describes the nature of self-awareness by the system and how explanation is generated. Finally, field tests using the modelling paradigm, the strengths and weaknesses of the architecture as well as open research issues are all discussed.

Le but de cette thèse est de proposer des méthodes de gestion des approvisionnements adaptées à des contextes particuliers afin de minimiser les coûts logistiques engendrés dans un réseau logistique multi produits, multi niveaux confronté à une demande probabiliste. Au cours de cette thèse, nous nous sommes attachés à : - Proposer des méthodes de gestion des stocks et du transport pour des familles de produits dans différents contextes : o Une première politique de réapprovisionnement est proposée pour une famille de produits caractérisée par une demande aléatoire et répétitive. Cette politique est définie par un niveau de commande et par un niveau de ré-complètement de stock pour chaque produit et une période de réapprovisionnement. Dès qu'un produit atteint le niveau de commande, un réapprovisionnement de tous les produits de la famille est déclenché. o Une deuxième politique de réapprovisionnement est proposée pour une famille de produits caractérisée par une demande très aléatoire et ponctuelle. Cette politique est basée sur les ruptures de stock. A chaque rupture d'un produit présent dans le stock il y a déclenchement d'un réapprovisionnement de tous les produits de la famille. - Proposer une méthode de classification multicritères afin de constituer des groupes de produits relevant d'une politique donnée, chaque classe ou famille regroupant des produits réagissant identiquement. Cette classification des produits en familles homogènes permet d'identifier les caractéristiques déterminantes dans le choix des méthodes de gestion de stock et de transport. - Analyser et comparer les performances de ces deux politiques d'approvisionnement par rapport à des politiques de référence, ainsi que leur sensibilité au regard de quelques paramètres discriminants : variabilité de la demande ; coût des produits ; coût des commandes urgentes...

Cette thèse d'Habilitation à Diriger des Recherches revient sur une dizaine d'années de contributions théoriques et pratiques à l'optimisation combinatoire, contributions dont le domaine d'application privilégié est l'optimisation des systèmes de télécommunications (principalement les autocommutateurs pour la téléphonie cellulaire) et informatiques (en particulier les architectures de processeur parallèles, dites multi-cœurs). Ces travaux se caractérisent également par la résolution bout-en-bout de nombreux cas d'applications industriels concrets et difficiles, de la modélisation mathématique initiale jusqu'à la mise en œuvre d'algorithmes de résolution opérationnels en passant par les développements théoriques nécessaires à leurs fondements.

Notre problème consiste à déterminer le nombre de grands rectangles identiques nécessaires pour ranger une liste de rectangles sans modifier leur orientation. Nous proposons des méthodes pour calculer des bornes inférieures pour ce problème, essentiellement basée sur le concept de fonctions dual-réalisables. Nous proposons aussi deux méthodes exactes de type énumératives. L'une permet de déterminer si un ensemble de rectangles peut être contenu dans un rectangle unique. Elle repose sur une nouvelle relaxation du problème. La deuxième méthode permet de résoudre le problème général de bin packing en deux dimensions. Elle calcule pour cela une décomposition itérative de l'ensemble des rectangles à placer.