The Upper Confidence Bounds (UCB) algorithm is a well-known near-optimal strategy for the stochastic multi-armed bandit problem. Its extensions to trees, such as the Upper Confidence Tree (UCT) algorithm, have resulted in good solutions to the problem of Go. This paper introduces DUCT, a distributed algorithm inspired by UCT, for solving Distributed Constraint Optimization Problems (DCOP). Bounds on the solution quality are provided, and experiments show that, compared to existing DCOP approaches, DUCT is able to solve very large problems much more efficiently, or to find significantly higher quality solutions.

Table constraints are very important in constraint programming as they are present in many real problems from areas such as configuration and databases. As a result, numerous specialized algorithms that achieve generalized arc consistency (GAC) on table constraints have been proposed. Since these algorithms achieve GAC, they operate on one constraint at a time. In this paper we propose an efficient algorithm for table constraints that achieves a stronger local consistency than GAC. This algorithm, called maxRPWC+, is based on the local consistency maxRPWC and allows the efficient handling of intersecting table constraints. Experimental results from benchmark problems demonstrate that maxRPWC+ is clearly more robust than a state-of-the-art GAC algorithm in classes of problems with interleaved table constraints, being orders of magnitude faster in some of these classes.

A var(a) v} to v. If cpt(a, b) T then the two assignments (points) a, b are compatible and {a, b} is a compatibility In a In a CSP instance the aim is to determine the existence pattern, the compatibility of a pair of points a, b such that of an assignment of values to variables such that a set var(a) var(b) and (a, b) / E is undefined. A fundamental research question is the identification of tractable subproblems A binary CSP instance is a pattern 〈V, A, var, E, cpt〉 of CSP.

In maintaining consistencies, such as GAC*, FDGAC* and weak EDGAC*, for global cost functions, Weighted CSP (WCSP) solvers rely on the projection and extension operations, which entail the computation of the cost functions' minima.  Tractability of this minimum computation is essential for efficient execution. Since projections/extensions modify the cost functions, an important issue is tractable projection-safety , concerning whether minimum cost computation remains tractable after projections/extensions. In this paper, we prove that tractable projection-safety is always possible for projections/extensions to/from the nullary cost function ( W 0 ), and always impossible for projections/extensions to/from n -ary cost functions for n > = 2.  When n = 1, the answer is indefinite.  We give a simple negative example, while Lee and Leung's flow-based projection-safe cost functions are also tractable projection-safe. We propose polynomially decomposable cost functions, which are amenable to tractable minimum computation.  We further prove that the polynomial decomposability property is unaffected by projections/extensionsto/from unary cost functions.  Thus, polynomially decomposable cost functions are tractable projection-safe.  We show that the SOFT_AMONG, SOFT_REGULAR, SOFT_GRAMMAR and MAX_WEIGHT/MIN_WEIGHT are polynomially decomposable.  They are embedded in a WCSP solver for extensive experiments to confirm the feasibility and efficiency of our proposal.

This paper presents a prototype system called SFplanner which uses an automated planning technique to generate workflows for reconfiguring a computing infrastructure. The system allows an administrator to specify a configuration task which consists of current state, desired state and global constraints. This task is compiled to a grounded finite-domain representation as the input for the standard (unmodified) Fast-Downward planner in order to automatically generate a workflow. The execution of the workflow will bring the system into the desired state, preserving the global constraints at every stage of the workflow.

In an Artificial Intelligence course, a basic concept is Constraint Satisfaction (CS), which is acknowledged as a hard domain for teachers to teach and student to understand. In this paper, we present a game-based learning approach to assist students in learning CS algorithms, such as arc consistency and search algorithms, for problem solving in an easy, interactive and motivating way. Preliminary valuation has showed promising results.

Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set constraint satisfaction problems (set CSPs). Such problems are frequently intractable, but there are several important set CSPs that are known to be polynomial-time tractable. We introduce a large class of set CSPs that can be solved in quadratic time. Our class, which we call EI, contains all previously known tractable set CSPs, but also some new ones that are of crucial importance for example in description logics. The class of EI set constraints has an elegant universal-algebraic characterization, which we use to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem.

The paper introduces mixed networks, a new framework for expressing and reasoning with probabilistic and deterministic information. The framework combines belief networks with constraint networks, defining the semantics and graphical representation. We also introduce the AND/OR search space for graphical models, and develop a new linear space search algorithm. This provides the basis for understanding the benefits of processing the constraint information separately, resulting in the pruning of the search space. When the constraint part is tractable or has a small number of solutions, using the mixed representation can be exponentially more effective than using pure belief networks which odel constraints as conditional probability tables.

We consider the challenge of preference elicitation in systems that help users discover the most desirable item(s) within a given database. Past work on preference elicitation focused on structured models that provide a factored representation of users' preferences. Such models require less information to construct and support efficient reasoning algorithms. This paper makes two substantial contributions to this area: (1) Strong representation theorems for factored value functions. (2) A methodology that utilizes our representation results to address the problem of optimal item selection.

The complexity of a reasoning task over a graphical model is tied to the induced width of the underlying graph. It is well-known that the conditioning (assigning values) on a subset of variables yields a subproblem of the reduced complexity where instantiated variables are removed. If the assigned variables constitute a cycle-cutset, the rest of the network is singly-connected and therefore can be solved by linear propagation algorithms. A w-cutset is a generalization of a cycle-cutset defined as a subset of nodes such that the subgraph with cutset nodes removed has induced-width of w or less. In this paper we address the problem of finding a minimal w-cutset in a graph. We relate the problem to that of finding the minimal w-cutset of a treedecomposition. The latter can be mapped to the well-known set multi-cover problem. This relationship yields a proof of NP-completeness on one hand and a greedy algorithm for finding a w-cutset of a tree decomposition on the other. Empirical evaluation of the algorithms is presented.