We at the NASA laboratory believed that our best work came when we simultaneously advanced AI theory and provided immediately usable solutions for current NASA problems. “Solving Large-Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repair Method,” by Steve Minton, Mark Johnston, Andy Phillips, and Phil Laird clearly achieved both. It proved that local search and repair was applicable to a wide class of constraint satisfaction problems and clearly explicated the theory behind that proof.

In this report, we propose a quick survey of the currently known techniques for encoding a Boolean cardinality constraint into a CNF formula, and we discuss about the relevance of these encodings. We also propose models to facilitate analysis and design of CNF encodings for Boolean constraints.

GNU Prolog is a general-purpose implementation of the Prolog language, which distinguishes itself from most other systems by being, above all else, a native-code compiler which produces standalone executables which don't rely on any byte-code emulator or meta-interpreter. Other aspects which stand out include the explicit organization of the Prolog system as a multipass compiler, where intermediate representations are materialized, in Unix compiler tradition. GNU Prolog also includes an extensible and high-performance finite domain constraint solver, integrated with the Prolog language but implemented using independent lower-level mechanisms. This article discusses the main issues involved in designing and implementing GNU Prolog: requirements, system organization, performance and portability issues as well as its position with respect to other Prolog system implementations and the ISO standardization initiative.

To assist scientists in data analysis tasks, we have developed semantic workflow representations that support automatic constraint propagation and reasoning algorithms to manage constraints among the individual workflow steps. Semantic constraints can be used to represent requirements of input datasets as well as best practices for the method represented in a workflow. We demonstrate how the Wings workflow system uses semantic workflows to assist users in creating workflows while validating that the workflows comply with the requirements of the software components and datasets. Wings reasons over semantic workflow representations that consist of both a traditional dataflow graph as well as a network of constraints on the data and components of the workflow.

Attitudes play a significant role in determining how individuals process information and behave. In this paper we have developed a new computational model of population wide attitude change that captures the social level: how individuals interact and communicate information, and the cognitive level: how attitudes and concept interact with each other. The model captures the cognitive aspect by representing each individuals as a parallel constraint satisfaction network. The dynamics of this model are explored through a simple attitude change experiment where we vary the social network and distribution of attitudes in a population.

The cardinal direction calculus (CDC) proposed by Goyal and Egenhofer is a very expressive qualitative calculus for directional information of extended objects. Early work has shown that consistency checking of complete networks of basic CDC constraints is tractable while reasoning with the CDC in general is NP-hard. This paper shows, however, if allowing some constraints unspecified, then consistency checking of possibly incomplete networks of basic CDC constraints is already intractable. This draws a sharp boundary between the tractable and intractable subclasses of the CDC. The result is achieved by a reduction from the well-known 3-SAT problem.

An important issue in Qualitative Spatial Reasoning is the representation of relative direction. In this paper we present simple geometric rules that enable reasoning about relative direction between oriented points. This framework, the Oriented Point Algebra OPRA_m, has a scalable granularity m. We develop a simple algorithm for computing the OPRA_m composition tables and prove its correctness. Using a composition table, algebraic closure for a set of OPRA statements is sufficient to solve spatial navigation tasks. And it turns out that scalable granularity is useful in these navigation tasks.

Substitutability, interchangeability and related concepts in Constraint Programming were introduced approximately twenty years ago and have given rise to considerable subsequent research. We survey this work, classify, and relate the different concepts, and indicate directions for future work, in particular with respect to making connections with research into symmetry breaking. This paper is a condensed version of a larger work in progress.

AAAI/SIGART Doctoral Consortium, and the second AAAI Educational Advances in Artificial Intelligence Symposium, to name only a few of the AAAI is pleased to present the 2011 Spring Symposium Series, to highlights. For complete information be held Monday through Wednesday, March 21-23, 2011, at on these programs, including Tutorial Stanford University.

We use a reactive planning language, ABL (Mateas and Stern 2002), to easily express hierarchical patterns of Creating a good level is a time consuming and iterative geometry that can be incorporated into the level, and also process: designers will typically play a level themselves a monitor and react to designer changes. The geometric number of times before showing it to anyone else, simply relationships between level components are given to a to check that it is playable and meets their expectations constraint solver, Choco (Choco Team 2008), as a set of (Castillo and Novak 2008). Making a change to a small constraints that must be satisfied, thus ensuring that the section of a level, such as moving a single piece of generator will never produce an unplayable level. A geometry, can have a wide impact and require much of the diagram desc rastructure is shown in rest of the level to be modified as well.