The past decade has witnessed the rapid emergence of the We consider a central task in combinatorial materials discovery, field of human computation, along with numerous successful namely the problem of identifying the crystalline applications. Human computation is motivated by problems phases of inorganic compounds based on an analysis of for which automated algorithms cannot yet exceed high-intensity X-ray patterns. In our approach, we integrate human performance (Von Ahn 2005). Indeed, some tasks a state-of-the-art optimization framework based on are naturally and truly easy for humans, while they remain constraint reasoning with a human computation component.

We are focusing on bound constrained global optimization problems, whose objective functions are computationally expensive black-box functions and have multiple local minima. The recently popular Metric Stochastic Response Surface (MSRS) algorithm proposed by \cite{Regis2007SRBF} based on adaptive or sequential learning based on response surfaces is revisited and further extended for better performance in case of higher dimensional problems. Specifically, we propose a new way to generate the candidate points which the next function evaluation point is picked from according to the metric criteria, based on a new definition of distance, and prove the global convergence of the corresponding. Correspondingly, a more adaptive implementation of MSRS, named "SO-SA", is presented. "SO-SA" is is more likely to perturb those most sensitive coordinates when generating the candidate points, instead of perturbing all coordinates simultaneously. Numerical experiments on both synthetic problems and real problems demonstrate the advantages of our new algorithm, compared with many state of the art alternatives.}

This paper introduces a novel encoding of Model Based Diagnosis (MBD) to Boolean Satisfaction (SAT) focusing on minimal cardinality diagnosis. The encoding is based on a combination of sophisticated MBD preprocessing algorithms and the application of a SAT compiler which optimizes the encoding to provide more succinct CNF representations than obtained with previous works. Experimental evidence indicates that our approach is superior to all published algorithms for minimal cardinality MBD. In particular, we can determine, for the first time, minimal cardinality diagnoses for the entire standard ISCAS-85 and 74XXX benchmarks. Our results open the way to improve the state-of-the-art on a range of similar MBD problems.

It is widely acknowledged that stochastic local search (SLS) algorithms can efficiently find models for satisfiable instances of the satisfiability (SAT) problem, especially for random k-SAT instances. However, compared to random 3-SAT instances where SLS algorithms have shown great success, random k-SAT instances with long clauses remain very difficult. Recently, the notion of second level score, denoted as "score_2", was proposed for improving SLS algorithms on long-clause SAT instances, and was first used in the powerful CCASat solver as a tie breaker. In this paper, we propose three new scoring functions based on score_2. Despite their simplicity, these functions are very effective for solving random k-SAT with long clauses. The first function combines score and score_2, and the second one additionally integrates the diversification property "age". These two functions are used in developing a new SLS algorithm called CScoreSAT. Experimental results on large random 5-SAT and 7-SAT instances near phase transition show that CScoreSAT significantly outperforms previous SLS solvers. However, CScoreSAT cannot rival its competitors on random k-SAT instances at phase transition. We improve CScoreSAT for such instances by another scoring function which combines score_2 with age. The resulting algorithm HScoreSAT exhibits state-of-the-art performance on random k-SAT (k>3) instances at phase transition. We also study the computation of score_2, including its implementation and computational complexity.

This paper deals with the problem of classical planning for multiple cooperative agents who have private information about their local state and capabilities they do not want to reveal. Two main approaches have recently been proposed to solve this type of problem -- one is based on reduction to distributed constraint satisfaction, and the other on partial-order planning techniques. In classical single-agent planning, constraint-based and partial-order planning techniques are currently dominated by heuristic forward search. The question arises whether it is possible to formulate a distributed heuristic forward search algorithm for privacy-preserving classical multi-agent planning. Our work provides a positive answer to this question in the form of a general approach to distributed state-space search in which each agent performs only the part of the state expansion relevant to it. The resulting algorithms are simple and efficient -- outperforming previous algorithms by orders of magnitude -- while offering similar flexibility to that of forward-search algorithms for single-agent planning. Furthermore, one particular variant of our general approach yields a distributed version of the A* algorithm that is the first cost-optimal distributed algorithm for privacy-preserving planning.

This work establishes distribution-free upper and lower bounds on the minimax label complexity of active learning with general hypothesis classes, under various noise models. The results reveal a number of surprising facts. In particular, under the noise model of Tsybakov (2004), the minimax label complexity of active learning with a VC class is always asymptotically smaller than that of passive learning, and is typically significantly smaller than the best previously-published upper bounds in the active learning literature. In high-noise regimes, it turns out that all active learning problems of a given VC dimension have roughly the same minimax label complexity, which contrasts with well-known results for bounded noise. In low-noise regimes, we find that the label complexity is well-characterized by a simple combinatorial complexity measure we call the star number. Interestingly, we find that almost all of the complexity measures previously explored in the active learning literature have worst-case values exactly equal to the star number. We also propose new active learning strategies that nearly achieve these minimax label complexities.

The algorithm selection problem is concerned with selecting the best algorithm to solve a given problem instance on a case-by-case basis. It has become especially relevant in the last decade, with researchers increasingly investigating how to identify the most suitable existing algorithm for solving a problem instance instead of developing new algorithms. This survey presents an overview of this work focusing on the contributions made in the area of combinatorial search problems, where algorithm selection techniques have achieved significant performance improvements. We unify and organise the vast literature according to criteria that determine algorithm selection systems in practice.

From an AI point of view, Real-Time Strategy (RTS) games are hard because they have enormous state spaces, they are real-time and partially observable. In this paper, we explore an approach to deploy game-tree search in RTS games by using game state abstraction, and explore the effect of using different abstractions over the game state. Different abstractions capture different parts of the game state, and result in different branching factors when used for game-tree search algorithms. We evaluate the different representations using Monte Carlo Tree Search in the context of StarCraft.

Platformer games let players solve real-time, physics-based puzzles by jumping and moving around to reach different goals. Designing levels for this context is a non-trivial task; the placement of well-timed jumps, moving platforms, in- teresting traps, etc., has a complex relationship to in-game challenge and the existence of possible solutions. In this work, we describe three different search algorithms (A⋆, MCTS and RRT) that could be used to simulate player be- haviour in the platformer domain. We evaluate and compare the three approaches applied to three non-trivial levels, show- ing a possible iterative workflow of use to designers, and re- search progress in designing search algorithms for platformer games.

This document contains a summary of research performed by the author on the topic of search algorithms for games. An outline of the problems being addressed is provided, along with the progress already made, and planned future work. The specific subjects studied are: parallelizing UCT search on GPUs, the development of a hierarchical search framework for Real-Time Strategy (RTS) games and the building placement problem in RTS games. We propose to take advantage of different parallel architectures to help solve these problems.