Set variables in constraint satisfaction problems (CSPs) are typically propagated by enforcing set bounds consistency together with cardinality reasoning, which uses some inference rules involving the cardinality of a set variable to produce more prunings than set bounds propagation alone. Multiset variables are a generalization of set variables by allowing the elements to have repetitions. In this paper, we generalize cardinality reasoning for multiset variables. In addition, we propose to exploit the variety of a multiset — the number of distinct elements in it — to improve modeling expressiveness and further enhance constraint propagation. We derive a number of inference rules involving the varieties of multiset variables. The rules interact varieties with the traditional components of multiset variables (such as cardinalities) to obtain stronger propagation. We also demonstrate how to apply the rules to perform variety reasoning on some common multiset constraints. Experimental results show that performing variety reasoning on top of cardinality reasoning can effectively reduce more search space and achieve better runtime in solving multiset CSPs.

We introduce planning games, a study of interactions of self-motivated agents in automated planning settings. Planning games extend STRIPS-like models of single-agent planning to systems of multiple self-interested agents, providing a rich class of structured games that capture subtle forms of local interactions. We consider two basic models of planning games and adapt game-theoretic solution concepts to these models.  In both models, agents may need to cooperate in order to achieve their goals, but are assumed to do so only in order to increase their net benefit. For each model we study the computational problem of finding a stable solution and provide efficient algorithms for systems exhibiting acyclic interaction structure.

The computing industry is currently facing a major architectural shift. Extra computing power is not coming anymore from higher processor frequencies, but from a growing number of computing cores and processors. For AI, and constraint solving in particular, this raises the question of how to scale current solving techniques to massively parallel architectures. While prior work focusses mostly on small scale parallel constraint solving, we conduct the first study on scalability of constraint solving on 100 processors and beyond in this paper. We propose techniques that are simple to apply and show empirically that they scale surprisingly well. These techniques establish a performance baseline for parallel constraint solving technologies against which more sophisticated parallel algorithms need to  compete  in the future.

Open forms of global constraints allow the addition of new variables to an argument during the execution of a constraint program.  Such forms are needed for difficult constraint programming problems where problem construction and problem solving are interleaved.  However, in general, filtering that is sound for a global constraint can be unsound when the constraint is open.  This paper provides a simple characterization, called contractibility, of the constraints where filtering remains sound when the constraint is open.  With this characterization we can easily determine whether a constraint is contractible or not.  In the latter case,  we can use it to derive the strongest contractible approximation to the constraint.  We demonstrate how specific algorithms for some closed contractible constraints are easily adapted to open constraints.

In this paper we approach the problem of reasoning with quantified Boolean formulas (QBFs) by combining search and resolution, and by switching between them according to structural properties of QBFs. We provide empirical evidence that QBFs which cannot be solved by search or resolution alone, can be solved by combining them, and that our approach makes a proof-of-concept implementation competitive with current QBF solvers.

The main result of this paper is to show that the problem of instantiating a finite and path-consistent constraint network of lines in the Euclidean space is NP-complete. Indeed, we already know that reasoning with lines in the Euclidean space is NP-hard. In order to prove that this problem is NP-complete, we first establish that a particular instance  of this problem can be solved by a nondeterministic polynomial-time algorithm, and then we show that solving any finite and path-consistent constraint network of lines in the Euclidean space is at most as difficult as solving that instance.

Powerful consistency techniques, such as AC* and FDAC*, have been developed for Weighted Constraint Satisfaction Problems (WCSPs) to reduce the space in solution search, but are restricted to only unary and binary constraints.  On the other hand, van Hoeve et al developed efficient graph-based algorithms for handling soft constraints as classical constraint optimization problems. We prove that naively incorporating van Hoeve's method into the WCSP framework can enforce a strong form of varnothing-Inverse Consistency, which can prune infeasible values and deduce good lower bound estimates.  We further show how Van Hoeve's method can be modified so as to handle cost projection and extension to maintain the stronger AC* and FDAC* generalized for non-binary constraints.  Using the soft allDifferent constraint as a testbed, preliminary results demonstrate that our proposal gives improvements up to an order of magnitude both in terms of time and pruning.

This paper presents a new analysis of dynamic constraint satisfaction problems (DCSPs) with finite domains and a new approach to solving them. We first show that even very small changes in a CSP, in the form of addition of constraints or changes in constraint relations, can have profound effects on search performance. These effects are reflected in the amenability of the problem to different forms of heuristic action as well as overall quality of search. In addition, classical DCSP methods perform poorly on these problems because there are sometimes no solutions similar to the original one found. We then show that the same changes do not markedly affect the locations of the major sources of contention in the problem. A technique for iterated sampling that performs a careful assessment of this property and uses the information during subsequent search, performs well even when it only uses information based on the original problem in the DCSP sequence. The result is a new approach to solving DCSPs that is based on a robust strategy for ordering variables rather than on robust solutions.

Qualitative constraint calculi are representation formalisms that allow for efficient reasoning about spatial and temporal information. Many of the calculi discussed in the field of Qualitative Spatial and Temporal Reasoning can be defined as combinations of other, simpler and more compact formalisms. On the other hand, existing calculi can be combined to a new formalism in which one can represent, and reason about, different aspects of a domain at the same time. For example, Gerevini and Renz presented a loose combination of the region connection calculus RCC-8 and the point algebra: the resulting formalism integrates topological and qualitative size relations between spatially extended objects. In this paper we compare the approach by Gerevini and Renz to a method that generates a new qualitative calculus by exploiting the semantic interdependencies between the component calculi. We will compare these two methods and analyze some formal relationships between a combined calculus and its components. The paper is completed by an empirical case study in which the reasoning performance of the suggested methods is compared on random test instances.

We study constraint satisfaction problems on the so-called 'planted' random ensemble. We show that for a certain class of problems, e.g. graph coloring, many of the properties of the usual random ensemble are quantitatively identical in the planted random ensemble. We study the structural phase transitions, and the easy/hard/easy pattern in the average computational complexity. We also discuss the finite temperature phase diagram, finding a close connection with the liquid/glass/solid phenomenology.