Abstract--In the paper arguments are given why the concept of static evaluation has the potential to be a useful extension to Monte Carlo tree search. A new concept of modeling static evaluation through a dynamical system is introduced and strengths and weaknesses are discussed. The general suitability of this approach is demonstrated. The concept of Monte-Carlo simulations applied to Go [1] combined with the UCT algorithm [2], [3], which is a tree search method based on Upper Confidence Bounds (UCB) (see e.g. The detailed tournament report [8] of the program MoGo playing against professional and amateur players reveals strengths and weaknesses of MoGo which are typical for programs that perform a Monte Carlo tree search (MCTS). Programs performing MCTS can utilize ever increasing computing power but in their pure form without extra Go knowledge the ratio log(increase in needed computing power) / (increase in strength) is too big to get to professional strength on large boards in the foreseeable future. Therefore in recent years Go knowledge has been incorporated either in form of heuristics, or pattern databases learned from professional games or from self-play. Although treesearch was naturally slowed down the playing strength increased further. With all of this tremendous progress of MCTS compared to the knowledge based era of computer Go summarized in [9], [10], [11], it needs good reasons to start work on a static evaluation function (SE) in Go. One indicator that more Go knowledge needs to be added is that, compared with human playing strength the playing level of current programs decreases as board size increases from 9 9 to 13 13 and then to 19 19. The principal difficulties of deriving knowledge and applying it become more relevant as knowledge is increasingly used in MCTS. Knowledge that is not 100% accurate reduces the scalability of the program when enough computing power is available for global search to replace increasingly the approximate Go knowledge which then becomes less useful or even less accurate than knowledge coming from search. It is difficult to combine knowledge on a high level if it comes from different sources, like from pattern and from local searches. It is one of the reasons of the originally surprising success of pure MCTS that it only uses knowledge from one source (statistics of simulations) without the need of merging different types of knowledge.

The elastic net was introduced as a heuristic algorithm for combinatorial optimisation and has been applied, among other problems, to biological modelling. It has an energy function which trades off a fitness term against a tension term. In the original formulation of the algorithm the tension term was implicitly based on a first-order derivative. In this paper we generalise the elastic net model to an arbitrary quadratic tension term, e.g. derived from a discretised differential operator, and give an efficient learning algorithm. We refer to these as generalised elastic nets (GENs). We give a theoretical analysis of the tension term for 1D nets with periodic boundary conditions, and show that the model is sensitive to the choice of finite difference scheme that represents the discretised derivative. We illustrate some of these issues in the context of cortical map models, by relating the choice of tension term to a cortical interaction function. In particular, we prove that this interaction takes the form of a Mexican hat for the original elastic net, and of progressively more oscillatory Mexican hats for higher-order derivatives. The results apply not only to generalised elastic nets but also to other methods using discrete differential penalties, and are expected to be useful in other areas, such as data analysis, computer graphics and optimisation problems.

Discovering latent connections between seemingly unconnected documents and constructing "stories" from scattered pieces of evidence are staple tasks in intelligence analysis. We have worked with government intelligence analysts to understand the strategies they use to make connections. Beyond techniques like clustering that aim to provide an initial broad summary of large document collections, an important goal of analysts in this domain is to assimilate and synthesize fine grained information from a smaller set of foraged documents. Further, analysts' domain expertise is crucial because it provides rich contextual background for making connections and thus the goal of KDD is to augment human discovery capabilities, not supplant it. We describe a visual analytics system we have built - Analyst's Workspace (AW) - that integrates browsing tools with a storytelling algorithm in a large screen display environment. AW helps analysts systematically construct stories of desired fidelity from document collections and helps marshall evidence as longer stories are constructed.

In this paper we present a principled planner based approach to the active visual object search problem in unknown environments. We make use of a hierarchical planner that combines the strength of decision theory and heuristics. Furthermore, our object search approach leverages on the conceptual spatial knowledge in the form of object co-occurrences and semantic place categorisation. A hierarchical model for representing object locations is presented with which the planner is able to perform indirect search. Finally we present real world experiments to show the feasibility of the approach.

This paper proposes a new challenging optimization problem, called COOLING-AWARE WORKLOADPLACEMENT PROBLEM, that looks for a workload placement that optimizes the overall data center power consumption given by the sum of the server power consumption and of the computer room air conditioner power consumption. We formulate CWPP as a Mixed Integer Non Linear Problem using a cross-interferencematrix that links the workload placement to the cold airtemperature. Since state-of-the-art Mixed Integer Non Linear solvers can solve to optimality only the smallest instances, we devised two heuristics to obtain good feasible solutions: (i) a heuristic algorithm based on an integer linear relaxation of the problem, and (ii) a VariableNeighborhood Search algorithm. Both heuristic algorithms are evaluated against the best lower bounds obtained with a Mixed Integer Non Linear solver. Preliminary computational results show that both heuristics provide solutions that have a small percentage gap from the optimal solutions.

The focus of my research is an agent-based system for optimizing spatial arrangements of plants on a landscape to maximize their growth and minimize their water use. The optimization criteria include a natural phenomenon known as facilitation, which is observed in water-scarce environments when larger shrubs serve as benefactors to smaller annuals by generating conditions that protect them from harsh afternoon sun. In my modeling and optimization system each plant is an agent with growth requirements. A plant agent's fitness at a given location is defined by a fitness function that includes those growth requirements and a penalty term designed to force facilitation. The landscape design is formulated as a combinatorial optimization problem with a discrete set of locations for each plant on a grid, a fixed number of plants, and a fitness function that defines the performance of a plant at a location. To evaluate the effectiveness of this approach, I applied a variety of search strategies, including simulated annealing and a new agent-based approach that mimics how plant communities evolve over time, to different collections of simulated plant types and landscapes and compared the fitness scores and spatial arrangments in the solutions. The fitness scores from the search strategies were comparable. The search strategies produced different spatial distributions of the larger plants, and all designs exhibited facilitation and lower water use.

Search algorithms often suffer from exploring areas which eventually are not part of the shortest path from the start to a goal. Usually it is the purpose of the heuristic function to guide the search algorithm such that it will ignore as much as possible of these areas. We consider other, non-heuristic methods that can be used to prune the search space to make search even faster. We present two algorithms: one for search in graphs that fit in memory, and in which we will need to perform many searches, and another, which improves the search time of planning problems that contain symmetries.

We report on an emerging application focused on the design of resilient long reach passive optical networks using combinatorial optimisation techniques. The objective of the application is to determine the optimal position and capacity of a set of metro nodes. We specifically consider dual parented networks whereby each customer must be associated with two metro nodes. An important property of such a placement is resilience to single node failure. Therefore excess capacity should be provided at each metro node in order to ensure that customers can be redistributed amongst the metro sites. Our application, as well as finding optimal node placements, can compute the minimum level of excess capacity on all metro nodes. In this paper we present three alternative approaches to optimal metro node placement.We present a detailed analysisof the impact of different placement approaches on the distribution of excess capacity throughout the network. We show that preferential distributions occur in practice, based on a case-study in Ireland. Finally we show that load and excess capacity provision are independent of each other.

Researchers have established the value of hands-on learning with tangible artifacts in mathematics and related fields. Inspired by this work, an assignment was developed for an undergraduate/graduate Artificial Intelligence course to introduce students to the formal representation of search. Students analyzed a familiar board game — e.g., Rush Hour or peg solitaire — using the standard approach to modeling an uninformed search process. The assignment was well-received by students, and analysis of their work yielded unexpected insights into the challenges students face in understanding how the formal problem model interacts with search algorithms. This paper introduces the theoretical motivations for the work, analyzes student work products, and makes recommendations for future extensions.

Various operational control systems (OCS) are naturally modeled as Markov Decision Processes. OCS often enjoy access to predictions of future events that have substantial impact on their operations. For example, reliable forecasts of extreme weather conditions are widely available, and such events can affect typical request patterns for customer response management systems, the flight and service time of airplanes, or the supply and demand patterns for electricity. The space of exogenous events impacting OCS can be very large, prohibiting their modeling within the MDP; moreover, for many of these exogenous events there is no useful predictive, probabilistic model. Realtime predictions, however, possibly with a short lead-time, are often available. In this work we motivate a model which combines offline MDP infinite horizon planning with realtime adjustments given specific predictions of future exogenous events, and suggest a framework in which such predictions are captured and trigger real-time planning problems. We propose a number of variants of existing MDP solution algorithms, adapted to this context, and evaluate them empirically.