A parallel plan is a sequence of sets of actions such that any ordering of actions in the sets gives a traditional sequential plan. Parallel planning was popularized by the Graphplan algorithm and it is one of the key components of successful SAT-based planers. SAT-based planners have recently begun to exploit multi-valued state variables – an area which seems traditionally more suited for constraint-based planners – and they improved their performance further. In this paper we propose a novel view of constraint-based planning that uses parallel plans and multi-valued state variables. Rather than starting with the planning graph structure like other parallel planners, this novel approach is based on the idea of timelines and their synchronization.

The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. Cases of the constraint satisfaction problem appear in many fields of study, including artificial intelligence, spatial and temporal reasoning, logic, combinatorics, and algebra. Indeed, the constraint satisfaction problem is flexible in that it admits a number of equivalent formulations. In this paper, we work with the formulation as the relational homomorphism problem: given two similar relational structures A and B, does there exist a homomorphism from A to B? In this formulation, one can view each relation of A as containing variable tuples that are constrained together, and the corresponding relation of B as containing the permissible values for the variable tuples [18]. The constraint satisfaction problem is in general NPhard; this general intractability has motivated the study of restricted versions of the CSP that have various desirable complexity and algorithmic properties.

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.

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.

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.

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.

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.