This work proposes new approximate (and exact) inference methods for reasoning about an important and hard-to-compute property of the solution space of combinatorial problems, namely clusters of solutions. We introduce an approximate method that first reformulates the constraint satisfaction problem (CSP) as a "factor graph" over an extended set of variable domains, approximates the number of clusters using an exponential size expression defined over this factor graph, and then estimates the value of this expression using message passing techniques, specifically an extension of the belief propagation (BP) algorithm. We provide formal exactness results as well as an empirical evaluation attesting to the accuracy of our method in counting the number of solution clusters.

Knowledge compilation is a valuable tool for dealing with the computational intractability of propositional reasoning. In knowledge compilation, a representation in a source language is typically compiled into a target language in order to perform some reasoning task in polynomial time. One particularly popular target language is Deterministic Decomposable Negation Normal Form (d-DNNF). d-DNNF supports efficient reasoning for tasks such as consistency checking and model counting, and as such it has proven a useful representation language for Bayesian inference, conformant planning, and diagnosis. In this paper, we exploit recent advances in #SAT solving in order to produce a new state-of-the-art CNF → d-DNNF compiler. We evaluate the properties and performance of our compiler relative to C2D, the de facto standard for compiling to d-DNNF. Empirical results demonstrate that our compiler is generally one order of magnitude faster than C2D on typical benchmark problems while yielding a d-DNNF representation of comparable size.

Constraint satisfaction problems are mathematical models of real-world problems. In contrast to randomly generated artificial problems, real-world problems usually have non-random structure. Knowledge about that structure, when identified in advance, can make search to find solutions more effective. This paper introduces DrawCSP, a visualization program that can show both the original and the discovered structure of constraint satisfaction problems. DrawCSP provides insight into both search algorithm design and into the challenges real-world problems present.

This paper investigates how readily an unsolvable constraint satisfaction problem can be reformulated so that it becomes solvable. We investigate small changes in the definitions of the problemís constraints, changes that alter neither the structure of its constraint graph nor the tightness of its constraints. Our results show that structured and unstructured problems respond differently to such changes, as do easy and difficult problems taken from the same problem class. Several plausible explanations for this behavior are discussed.

One approach to combining ASP and CP is to integrate There are several approaches to representing and solving theory-specific predicates into propositional formulas (motivated constraint satisfaction problems: constraint programming by SMT), and to extend the ASP solver's decision (CP; Dechter 2003, Rossi, van Beek, and Walsh 2006), answer engine with a higher level proof procedure (Baselice, set programming (ASP; Baral 2003), propositional satisfiability Bonatti, and Gelfond 2005; Mellarkod and Gelfond 2008; checking (SAT; Biere et al. 2009), its extension Gebser, Ostrowski, and Schaub 2009). However, the resulting to satisfiability modulo theories (SMT; Nieuwenhuis, Oliveras, systems have a number of limitations. First, they are and Tinelli 2006), and many more. Each has its particular tied to particular ASP and CP solvers. Second, the support strengths: for example, CP systems support global constraints, for global constraints is limited. Third, communication between ASP systems permit recursive definitions and offer the ASP and CP solver is restricted. Alternative techniques, default negation, whilst SAT solvers often exploit very such as reformulating constraints into ASP have received efficient implementations.

Inductive Logic Programming (ILP) deals with the problem of finding a hypothesis covering positive examples and excluding negative examples, where both hypotheses and examples are expressed in first-order logic. In this paper we employ constraint satisfaction techniques to model and solve a problem known as template ILP consistency, which assumes that the structure of a hypothesis is known and the task is to find a unification of the contained variables such that no negative example is subsumed by the hypothesis and all positive examples are subsumed.

Approximation (WARA-2010), scheduled to be held on July Topics of interest for this AAAI workshop include all 12, 2010 in Atlanta, Georgia, USA in conjunction with aspects of abstraction, reformulation and approximation, AAAI-10, aims to provide a forum for intensive interaction including (but not limited to) the following: new techniques among researchers in all areas of artificial intelligence for automatically constructing and selecting appropriate and computer science with an interest in the different aspects ARA methods; frameworks that unify and classify of abstraction, reformulation, and approximation techniques. ARA techniques; empirical and theoretical studies of the The goal and scope of this workshop are similar to costs and benefits of ARA; applications of ARA to search, an independent symposium called SARA. The diverse backgrounds constraint satisfaction, deterministic and probabilistic planning, of participants of previous SARA symposia has led theorem proving, logic programming, game playing, to a rich and lively exchange of ideas, allowed the comparison parallel and distributed search, distributed data and knowledge of goals, techniques, and paradigms, and helped identify bases, internet search and navigation, knowledge compilation, important research issues and engineering hurdles. This knowledge acquisition, knowledge reformulation, workshop continues to do the same.

Dynamic executio n is a flexible plan execution technique in which a plan executive schedules and executes tasks dynamically at runtime in response to disturbances in order to satisfy plan constraints. In this paper, we extend dynamic execution to temporally and spatially flexible plans which, 1) execute tasks conditionally based on runtime state, and 2) support error recovery for anticipated runtime constraint violations. To accomplish these goals, we broaden our focus from dynamic execution of flexible plans to dynamic execution of flexible reactive programs. First, we introduce the Reactive Model-based Programming Language (RMPL) which, in addition to modeling temporal and spatial flexibility, includes three reactive programming language constructs: conditional execution, iteration, and exception handling. Then, we develop a probabilistic particle-sampling based dynamic execution algorithm which reasons efficiently over future program states to schedule tasks dynamically at runtime in order to satisfy program constraints. In addition, the algorithm monitors its own progress and notifies the executive if at any time the likelihood of successful program execution drops below a specified probability bound, δ.

The Model AI Assignments session seeks to gather and disseminate the best assignment designs of the Artificial Intelligence (AI) Education community. Recognizing that assignments form the core of student learning experience, we here present abstracts of eight AI assignments that are easily adoptable, playfully engaging, and flexible for a variety of instructor needs.

When agents are acting together, they may need a simple mechanism to decide on joint actions. One possibility is to have the agents express their preferences in the form of a ballot and use a voting rule to decide the winning action(s). Unfortunately, agents may try to manipulate such an election by misreporting their preferences. Fortunately, it has been shown that it is NP-hard to compute how to manipulate a number of different voting rules. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. To address this issue, I suggest studying empirically if computational complexity is in practice a barrier to manipulation. The basic tool used in my investigations is the identification of computational "phase transitions". Such an approach has been fruitful in identifying hard instances of propositional satisfiability and other NP-hard problems. I show that phase transition behaviour gives insight into the hardness of manipulating voting rules, increasing concern that computational complexity is indeed any sort of barrier. Finally, I look at the problem of computing manipulation of other, related problems like stable marriage and tournament problems.