Technology
Approximate Uni-Directional Benders Decomposition
Burt, Christina Naomi (The University of Melbourne) | Lipovetzky, Nir (The University of Melbourne) | Pearce, Adrian R (The University of Melbourne) | Stuckey, Peter J (The University of Melbourne)
We examine a decomposition approach to find good quality feasible solutions. In particular, we studya method to reduce the search-space by decomposing a problem into two partitions, where the second partition (i.e., the subproblem) contains the fixed solution of the first (i.e., the master). This type of approach is usually motivated by the presence of two sub-problems that are each more easily solved by different methods. Our work is motivated by methods for which it is nontrivial to return a strong `no-good', `Benders feasibility', or 'optimality' cut. Instead, we focus our attention on a uni-directional decomposition approach. Instead of providing a relaxation of the sub-problem for the master problem, as in Benders decomposition, we provide an approximation of the sub-problem. Thus, we aim at finding good quality feasible solutions in the first iteration. While the quality of the approximation itself affects the impact of this approach, we illustrate that even using a simple approximation can havestrong positive impact on two examples: the Travelling Purchaser Problem and a Mine Planning Problem.
State Space Abstraction in Artificial Intelligence and Operations Research
Holte, Robert C. (University of Alberta) | Fan, Gaojian (University of Alberta)
In this paper we compare the abstraction methods used for state space search and planning in Artificial Intelligence with the state space relaxation methods used in Operations Research for various optimization problems such as the Travelling Salesman problem (TSP). Although developed independently, these methods are based on exactly the same general idea: lower bounds on distances in a given state space can be derived by computing exact distances in a ``simplified" state space. Our aim is to describe these methods so that the two communities understand what each other has done and can begin to work together.
Interactive Multi-Consumer Power Cooperatives with Learning and Axiomatic Cost and Risk Disaggregation
Ehsanfar, Abbas (Stevens Institute of Technology) | Heydari, Babak (Stevens Institute of Technology)
This paper introduces a novel autonomous interactive learning cooperative (ILCP) who receives expected value and variance of load from consumers and participates in the electricity market on their behalf. Using an axiomatic approach, the share of each consumer's payment as well as its weight in calculating the modification of total day-ahead load are formulated. This scheme applies double-seasonal smoothing exponential, a recent load forecasting technique, and a classifier for real-time to day-ahead price direction forecasting (Gaussian Naรฏve Bayes). In addition to this, the ILCP employs interactive cooperative algorithms for both trading cooperative and consumer side. The ILCP scheme is investigated and its performance is compared to those of non-cooperative real-time pricing (RTP), LCP (non-interactive learning cooperative) and CP (non-interactive non-learning cooperative). The developed system was implemented using PJM(world's largest ย wholesale electricity market) real-time and day-ahead data for 2013 and half of 2014; real load profiles were selected from a set of 579 residential and commercial consumers, and weather data were applied to forecasting electricity price direction. We demonstrate the advantages of ILCP to lower the average electricity cost and to reduce unit price variations.
Cyc and the Big C: Reading that Produces and Uses Hypotheses about Complex Molecular Biology Mechanisms
Witbrock, Michael (Cycorp Inc) | Pittman, Karen (Cycorp Inc.) | Moszkowicz, Jessica (Cycorp Inc.) | Beck, Andrew (Cycorp Inc.) | Schneider, Dave (Cycorp Inc.) | Lenat, Douglas (Cycorp Inc.)
Systems biology, the study of the intricate, ramified, com-plex and interacting mechanisms underlying life, often proves too complex for unaided human understanding, even by groups of people working together. This difficulty is ex-acerbated by the high volume of publications in molecular biology. The Big C (โCโ for Cyc) is a system designed to (semi-)automatically acquire, integrate, and use complex mechanism models, specifically related to cancer biology, via automated reading and a hyper-detailed refinement pro-cess resting on Cycโs logical representations and powerful inference mechanisms. We aim to assist cancer research and treatment by achieving elements of biologist-level reason-ing, but with the scale and attention to detail that only com-puter implementations can provide.
A Trust Establishment Model in Multi-Agent Systems
Aref, Abdullah (University of Ottawa) | Tran, Thomas (University of Ottawa)
In open multi-agent systems, often, agents interact with each other to meet their objectives. Trust is, therefore, considered essential to make such interactions useful. However, trust is a complex, multifaceted concept and includes more than just evaluating otherโs honesty. Many trust evaluation models have been proposed and implemented in different areas; most of them focused on creating algorithms for trusters to model the honesty of trustees in order to make effective decisions about which trustees to select. However, slight consideration is paid to trust establishment. This work describes a trust establishment model that goes beyond trust evaluation to outline actions to guide trustees (instead of trustors). The model uses a multicriteria method for measuring and analysing needs of trusters and evaluates the satisfaction level of trusters based on their values and expressed preferences. Using the feedback from trusters, trustees attempt to modify their behavior in order to achieve higher confidence levels as part of their plans to be selected as partners of other agents in the community for future interactions. Simulation results indicate that trustees can become more trusted if they adjust their behaviour based of satisfaction feedback from trusters.
NOTES2: Networks-of-Traces for Epidemic Spread Simulations
Liu, Sicong (Arizona State University) | Garg, Yash (Arizona State University) | Candan, K. Selcuk (Arizona State University) | Sapino, Maria Luisa (University of Torino) | Chowell-Puente, Gerardo (Arizona State University)
Decision making and intervention against infectious diseases require analysis of large volumes of data, including demographic data, contact networks, age-specific contact rates, mobility networks, and healthcare and control intervention data and models. In this paper, we present our Networks-Of-Traces for Epidemic Spread Simulations (NOTES2) model and system which aim at assisting experts and helping them explore existing simulation trace data sets. NOTES2 supports analysis and indexing of simulation data sets as well as parameter and feature analysis, including identification of unknown dependencies across the input parameters and output variables spanning the different layers of the observation and simulation data.
A Proposal for Behavior Prediction via Estimating Agentsโ Evaluation Functions Using Prior Observations of Behavior
Loftin, Robert Tyler (North Carolina State University) | Roberts, David L. (North Carolina State University)
In this work we present a theoretical approach (not currently implemented), to the problem of predicting agent behavior. The ultimate goal of this work is to learn models that can be used to predict the future actions of intelligent agents, based on previously recorded data on those agentsโ behavior. We believe that we can improve the predictive accuracy of our models by assuming that an agent reasons about the actions it takes, and trying to explicitly model that reasoning process. Here, we model an agentโs reasoning process as a form of Monte-Carlo search, and attempt to learn a state evaluation function that, when used with this planning algorithm, yields a similar distribution of actions given the current state of the world as we observe in the data. While it is simple to simulate Monte-Carlo search given an evaluation function, it is much more difficult to determine an evaluation function that will generate a certain behavior. Here we will use Expectation-Maximization to find a maximum likelihood estimate of the parameters of the evaluation function, treating the actual steps taken in planning each action as unobserved data.
Termination Approximation: Continuous State Decomposition for Hierarchical Reinforcement Learning
Harris, Sean (University of New South Wales) | Hengst, Bernhard (University of New South Wales) | Pagnucco, Maurice (University of New South Wales)
This paper presents a divide-and-conquer decomposition for solving continuous state reinforcement learning problems. The contribution lies in a method for stitching together continuous state subtasks in a near-seamless manner along wide continuous boundaries. We introduce the concept of Termination Approximation where the set of subtask termination states are covered by goal sets to generate a set of subtask option policies. The approach employs hierarchical reinforcement learning methods and exploits any underlying repetition in continuous problems to allow reuse of the option policies both within a problem and across related problems. The approach is illustrated using a series of challenging racecar problems.
Designing a Portfolio of Parameter Configurations for Online Algorithm Selection
Gunawan, Aldy (Singapore Management University) | Lau, Hoong Chuin (Singapore Management University) | Misir, Mustafa (Singapore Management University)
Algorithm portfolios seek to determine an effective set of algorithms that can be used within an algorithm selection framework to solve problems. A limited number of these portfolio studies focus on generating different versions of a target algorithm using different parameter configurations. In this paper, we employ a Design of Experiments (DOE) approach to determine a promising range of values for each parameter of an algorithm. These ranges are further processed to determine a portfolio of parameter configurations, which would be used within two online Algorithm Selection approaches for solving different instances of a given combinatorial optimization problem effectively. We apply our approach on a Simulated Annealing-Tabu Search (SA-TS) hybrid algorithm for solving the Quadratic Assignment Problem (QAP) as well as an Iterated Local Search (ILS) on the Travelling Salesman Problem (TSP). We also generate a portfolio of parameter configurations using best-of-breed parameter tuning approaches directly for the comparison purpose. Experimental results show that our approach lead to improvements over best-of-breed parameter tuning approaches.