Cognitive psychology and artificial intelligence have provided valuable insights into the scope and limitations of human thought and behavior. As technology becomes more of a fixture in our daily routines, advances in artificial intelligence increasingly impact how we think and interact with others. This track is motivated by these two fronts of research: the basic theoretical integration of cognition and artificial intelligence; and its application to real-world domains. As such, the track will cover a wide range of issues. We welcomed submissions in any area where cognition and computers are mutually explored, but especially encouraged work in how humans and computers communicate or how artificial intelligence facilitates communication.

In this paper, we investigate the hybrid tractability of binary Quantified Constraint Satisfaction Problems (QCSPs). First, a basic tractable class of binary QCSPs is identified by using the broken-triangle property. In this class, the variable ordering for the broken-triangle property must be same as that in the prefix of the QCSP. Second, we break this restriction to allow that existentially quantified variables can be shifted within or out of their blocks, and thus identify some novel tractable classes by introducing the broken-angle property. Finally, we identify a more generalized tractable class, i.e., the min-of-max extendable class for QCSPs.

A natural and established way to restrict the constraint satisfaction problem is to fix the relations that can be used to pose constraints; such a family of relations is called a constraint language. In this article, we study arc consistency, a heavily investigated inference method, and three extensions thereof from the perspective of constraint languages. We conduct a comparison of the studied methods on the basis of which constraint languages they solve, and we present new polynomial-time tractability results for singleton arc consistency, the most powerful method studied.

We solve constraint satisfaction problems through translation to answer set programming (ASP). Our reformulations have the property that unit-propagation in the ASP solver achieves well defined local consistency properties like arc, bound and range consistency. Experiments demonstrate the computational value of this approach.

Bessiere et al. (AAAI'08) showed that several intractable global constraints can be efficiently propagated when certain natural problem parameters are small. In particular, the complete propagation of a global constraint is fixed-parameter tractable in k - the number of holes in domains - whenever bound consistency can be enforced in polynomial time; this applies to the global constraints AtMost-NValue and Extended Global Cardinality (EGC). In this paper we extend this line of research and introduce the concept of reduction to a problem kernel, a key concept of parameterized complexity, to the field of global constraints. In particular, we show that the consistency problem for AtMost-NValue constraints admits a linear time reduction to an equivalent instance on O(k^2) variables and domain values. This small kernel can be used to speed up the complete propagation of NValue constraints. We contrast this result by showing that the consistency problem for EGC constraints does not admit a reduction to a polynomial problem kernel unless the polynomial hierarchy collapses.

Heuristics are crucial tools in decreasing search effort in varied fields of AI. In order to be effective, a heuristic must be efficient to compute, as well as provide useful information to the search algorithm. However, some well-known heuristics which do well in reducing backtracking are so heavy that the gain of deploying them in a search algorithm might be outweighed by their overhead. We propose a rational metareasoning approach to decide when to deploy heuristics, using CSP backtracking search as a case study. In particular, a value of information approach is taken to adaptive deployment of solution-count estimation heuristics for value ordering. Empirical results show that indeed the proposed mechanism successfully balances the tradeoff between decreasing backtracking and heuristic computational overhead, resulting in a significant overall search time reduction.

Bound propagation is an important Artificial Intelligence technique used in Constraint Programming tools to deal with numerical constraints. It is typically embedded within a search procedure (branch and prune) and used at every node of the search tree to narrow down the search space, so it is critical that it be fast. The procedure invokes constraint propagators until a common fixpoint is reached, but the known algorithms for this have a pseudo-polynomial worst-case time complexity: they are fast indeed when the variables have a small numerical range, but they have the well-known problem of being prohibitively slow when these ranges are large. An important question is therefore whether strongly-polynomial algorithms exist that compute the common bound consistent fixpoint of a set of constraints. This paper answers this question. In particular we show that this fixpoint computation is in fact NP-complete, even when restricted to binary linear constraints.

We consider the problem of assessing the sustainability of alternative designs (e.g., for an urban environment) that are assembled from multiple components (e.g., water supply, transportation system, shopping centers, commercial spaces, parks). We model the sustainability of a design in terms of a set of sustainability attributes. Given the (qualitative) preferences and tradeoffs of decision makers over the sustainability attributes, we formulate the problem of identifying sustainable designs as the problem of finding the most preferred designs with respect to those preferences. We show how techniques for representing and reasoning with qualitative preferences can be used to identify the most preferred designs based on the decision maker’s stated preferences and tradeoffs.

Figure 1a first illustrates by the oval that a Cradle-to-cradle (C2C) design (McDonough & Braungart, critical problem in traditional design is that a product is designed 2002) recognizes that nothing short of full recycling of materials in isolation. In contrast, the products shown in the with no degradation in material quality is necessary square box of Figure 1b illustrate the concept of a product for long-term planet sustainability. C2C advocates looking family, where multiple products are designed within a system to the natural world as an ideal model of recycling, where of material use and reuse, which flows between product organic materials are continually recycled through processes lines. While there may still be materials that come from of decay and growth. They propose design methodology outside the family and there are materials that are byproducts that separates biological cycles and syntheticmaterial of the family production, a family design would seek cycles, enabling biological material to be reclaimed to minimize these and to exploit them in a still larger context.

Preference-based reasoning is a form of commonsense reasoning that makes many problems easier to express and sometimes more likely to have a solution. We present an approach to introduce preferences in the weight constraint construct, which is a very useful programming construct widely adopted in Answer Set Programming (ASP). We show the usefulness of the proposed extension, and we outline how to accordingly extend the ASP semantics.