2 Dynamic constraint satisfaction: a critical review

The DCSP was originally formalized by Dechter and Dechter (Reference Dechter and Dechter1988). In this formalism, all variables have identical domains, and the set of constraints and variables is allowed to vary over time, thereby creating a sequence of CSPs. Adding variables and constraints are termed restrictions, and removing variables and constraints are termed relaxations. The focus in this work was on maintaining one or a set of solutions as the problem is changed. A restricted variation of the DCSP was introduced by Mittal and Falkenhainer (Reference Mittal and Falkenhainer1990). In their formalization, the set of variables and constraints is fixed, but the constraints are activated by variable assignments, that is, all of the variables in the scope of a constraint must be activated for the constraint to apply. The set of variables that must be assigned can be a function of other variables’ values. There is also a minimum subset condition to ensure no ‘extra’ variables are assigned. Thus, the problem does not change via some external entity adding variable and constraints, but the act of solving increases the set of required active variables, and thus constraints. The Disjunctive Temporal Network (DTN) introduced by Tsamardinos and Pollack (Reference Tsamardinos and Pollack2003) is focused on a discrete choice of which temporal constraint to apply to a pair of temporal variables. Changing the value of a discrete variable requires removing one temporal constraint and replacing it with another. An extension to Mittal and Falkenhainer’s DCSP was introduced by Soininen et al. (Reference Soininen, Gelle and Niemela1999) to allow disjunctive activity constraints (satisfaction of activity constraints implies some subset of variables must be assigned), include ‘null’ variable assignment, and change the definition of solution to a fixed point instead of minimum subset, leading to reduced computational complexity. An extension to the DCSP to support automated planning was introduced by Jónsson and Frank (Reference Jónsson and Frank2000). In addition to adding or removing variables and restricting or relaxing constraints, new values for existing variables may be added, or values of variables can be removed from the domains permanently. Adding new constraints and changing the scope of constraints was not considered. This approach is elaborated in Frank and Jónsson (Reference Frank and Jónsson2003).

We shall now describe some limitations with these formalisms for DCSPs. Previously, changes to CSPs were simply labeled restrictions (or relaxations) with no formal criteria to determine which is which. Consider adding a variable without constraints to a CSP. Compared with the previous CSP (without the new variable), a decision is now required in the new CSP where no decision was required before. The resulting transformation is labeled a restriction. However, the label is somewhat unintuitive; adding a variable with no constraints is not obviously restrictive, since adding a new variable X with domain size ⩾2 increases the number of assignments and the number of solutions but not the percentage of assignments that are solutions. In fact, the percentage of assignments that are solutions is left unchanged. That is because the new variable’s values are unconstrained and therefore increase both the number of assignments and the number of solutions by the same constant factor (namely |d(X)|).

The formalisms of DCSPs have not been extended to problems with costs and quality bounds. How is a problem of satisfiability transformed into an optimization problem? Does introducing optimization restrict or relax the problem? Suppose the problem is an optimization problem, and initially solutions below some cost are demanded. Over time, the cost bound is found to be too low, and the problem is changed by either increasing the cost bound, or by reducing (or eliminating) the cost of assignments associated with some constraints. Intuitively, making the cost bound higher might seem like a relaxation. Similarly, making some solutions have higher cost might seem like a restriction. If we are in an optimal setting with a cost bound defining the set of feasible solutions, then increasing the bound will increase the number of solutions, and decreasing cost will only reduce the number of solutions. However, if costs on single assignments or constraints are changed, but the cost bound defining solutions remains the same, it is not obvious a priori how many assignments’ costs will remain below the cost bound, and therefore whether the change is a restriction or a relaxation.

Finally, consider transforming a problem in which constraints cannot be waived into one where they can. This is a significant transformation; a new variable must be introduced, the scope of the waivable constraint must be changed, and the relations in the constraint extended. While the change is obviously a relaxation, existing DCSP formalisms lack good support for this change. In Jónsson and Frank (Reference Jónsson and Frank2000) such a change is not considered; while adding constraints was conceived of in Dechter and Dechter (Reference Dechter and Dechter1988), a change of scope was not, and must be synthesized from other primitives in the other formalisms. Other changes may not be so easily analyzed.

3 Dynamic constraint satisfaction: a new formalism

Throughout the remainder of this paper, we assume CSPs variables all have finite discrete domains.

We now define DCSPs using the notion of transformations between CSPs.

In the spirit of Dechter and Dechter (Reference Dechter and Dechter1988) and Jónsson and Frank (Reference Jónsson and Frank2000), a DCSP allows an external entity to apply a (possibly infinite) sequence of the above transformations to a CSP, and request a solution after any subsequence of transformations. An example is shown in Figure 1.

Figure 1

Transformations. The set of all valid dynamic constraint satisfaction problem (DCSP) transformations. The dotted lines show valid transformations, but not the exact transformations of the DCSP in the figure

Unlike previous theories of transformations on DCSPs, the classes transformations on DCSPs cannot all be classified as restrictions, relaxations, or neutral:

The proof employs straightforward analysis of each class of transformation:

1. 1. X+: since |d(X _n+1)|=1, $L\left( {{\cal P}_{j} } \right){\equals}\left( {L\left( {{\cal P}_{i} } \right)} \right)\left( {\:\mid\!d\left( {X_{{n{\plus}1}} } \right)\!\mid\:} \right)\,{\equals}\,L\left( {{\cal P}_{i} } \right)$ . Similarly, $\left( {\prod\nolimits_{i{\equals}1}^n {\left| {d\left( {X_{i} } \right)} \right|} } \right)\left( {\left| {d\left( {X_{{n{\plus}1}} } \right)} \right|} \right)\,{\equals}} $ $\left \prod\nolimits_{i{\equals}1}^n {\left| {d\left( {X_{i} } \right)} \right|} $ . Adding a variable with a single value but not adding this value to any relations leaves the number of assignments and solutions unchanged, so the fraction of solutions is unchanged, hence this is a neutral transformation.

2. 2. X−: removing a variable with a single value that participates in no constraints leaves the number of assignments and solutions unchanged, so the fraction of solutions is unchanged, hence this is a neutral transformation.

3. 3. d+: we show that adding a value to a variable but leaving the relations unchanged increases the number of assignments and the number of solutions by the same factor. Let d+ change d(X _n ) w.l.o.g. (simplifies notation for the computation). Then the number of assignments increases by a factor of

   $${{\left( {\prod\nolimits_{i{\equals}1}^{n{\minus}1} {\left| {d\left( {X_{i} } \right)} \right|} } \right)\left( {\left( {\left| {d\left( {X_{n} } \right)} \right|{\plus}1} \right)} \right)} \over {\left( {\prod\nolimits_{i{\equals}1}^{n{\minus}1} {\left| {d\left( {X_{i} } \right)} \right|} } \right)\left( {\left| {d\left( {X_{n} } \right)} \right|} \right)}}\, {\equals}\,{{\left| {d\left( {X_{n} } \right)} \right|{\plus}1} \over {\left| {d\left( {X_{n} } \right)} \right|}}$$

   Next, recall values can only be added to variables not in the scope of any constraint. Let ${\cal Q}_{i} $ be ${\cal P}_{i} \, \, {\minus}\,\,X_{n} $ , that is, the CSP without variable X _n . Rewrite $L({\cal P}_{i} )\, {\equals}\,\left( {L\left( {{\cal Q}_{i} } \right)} \right)\left( {\left| {d\left( {X_{n} } \right)} \right|} \right)$ . So the number of solutions increases by a factor of

   $${{\left( {L\left( {{\cal Q}_{i} } \right)} \right)\left( {\left| {d(X_{n} ){\plus}1} \right|} \right)} \over {\left( {L\left( {{\cal Q}_{i} } \right)} \right)\left( {\left| {d\left( {X_{n} } \right)} \right|} \right)}}\, {\equals}\,{{\left| {d\left( {X_{n} } \right)} \right|{\plus}1} \over {\left| {d\left( {X_{n} } \right)} \right|}}$$
   which means the increase in the number of solutions and the number of assignments increase by the same factor, so the fraction of solutions remains unchanged.

4. 4. d−: removing a value from a variable domain leaves the fraction of solutions unchanged as argued above.

5. 5. r+: adding a tuple to a relation may not increase the number of solutions, as the tuple may be excluded by other relations. However, adding a unique tuple to a relation cannot decrease the number of solutions. The number of assignments does not change, so the fraction of solutions cannot decrease; hence this is either a neutral transformation or a relaxation.

6. 6. r−: removing a unique tuple from a relation cannot increase the number of solutions. The number of assignments does not change, so the fraction of solutions cannot increase, hence this is a neutral transformation or a restriction.

7. 7. C+: adding a constraint with the relation consisting of all assignments to the variables in the scope leaves the fraction of solutions unchanged, hence this is a neutral transformation.

8. 8. C−: removing a constraint whose relation consists of all assignments to the variables in the scope leaves the fraction of solutions unchanged, hence this is a neutral transformation.

Definition 3 can now be used to classify a single transformation, and also to evaluate a sequence of transformations. We now have a principled definition of restriction and relaxation in terms of the fraction of solutions. We also have finer-grained and more precisely characterized transformations than previous formalisms. We see that transformations need not be restrictions or relaxations, and that some transformations previously identified as restrictions or relaxations are classified differently using our new definition. For example, adding a variable is considered a restriction in Dechter and Dechter (Reference Dechter and Dechter1988) but is neither a restriction nor a relaxation according to the new classification.

Theorem 1 holds regardless of whether the definition of restriction or relaxation uses the number or fraction of solutions. This is summarized in the table below. Recall from Definition 3 that $L({\cal P})$ is the number of solutions, and $L_{p} ({\cal P})$ is the fraction of solutions.

The table shows that only a small number of transformations actually change the set of solutions in a meaningful way. Consider the transformation τ=d+ (i.e. adds values to d(X _i )). Since X _i cannot be involved in any constraints, no relations in existing constraints are modified, and no constraints are added, all of the new values participate in solutions to ${\cal P}_{j} $ . However, every solution to ${\cal P}_{i} $ is a solution to ${\cal P}_{j} $ . In a sense, the transformation is trivial, in that little work is required to keep up with this ‘restriction’. Similarly, the transformation d− (removing a value) modifies a variable that is not in any relations, and thus reduces the number of assignments, and the solutions are reduced by the same fraction. The only non-trivial transformations are those in which the set of tuples in an existing relation are modified.

It is possible to synthesize the previously defined restrictions and relaxations from a sequence of these new, primitive transformations. We provide a specific example in Figure 2 of adding a variable to the scope of a constraint to support waiving the original constraint. In this figure some of the transformations have been combined for brevity. This transformation is contrasted to the transformation of simply removing a constraint from the variables. The complex sequence of removing the old constraint and replacing it in this case could be made slightly easier via a neutral transformation +S that increases the scope of a variable and extends the old relations with new ones allowing every value of the newly in-scope variable; similarly, the transformation −S is permitted to remove the scope of any variable all of whose values are allowed in the relation on the variables that will remain in scope.

Figure 2

Extending a constraint to allow waiving violations by variable assignment during solving (top) versus removing a constraint (bottom)

4 Extending dynamic constraint satisfaction problems to optimization problems

We now show how to extend the notion of DCSPs to optimization problems; more precisely, we address problems in which assignments have costs, and there is a cost bound defining the set of feasible solutions. We choose the partial constraint satisfaction problems (PCSPs) formalism to extend the analysis of dynamic constraint satisfaction. PCSPs were originally defined by Freuder and Wallace (Reference Freuder and Wallace1992). While more modern formalisms such as soft constraints defined over semirings (Bistarelli et al., Reference Bistarelli, Montanari and Rossi1995) have more expressive power and more sophisticated theoretical grounding, we will develop the theory of DCSPs using PCSPs for simplicity. PCSPs extend CSPs by adding a cost function that maps a relation to a real value, and the goal is to find an assignment of values such that the sum of costs does not exceed a bount B:

We will refer to f as the cost of a relation, since solutions must have a cumulative value below B. This definition allows the cost function of PCSPs with partially defined relations (i.e. f defined on a subset of d(X _j1)× … × d(X _jk )) to be well defined; specifically, an assignment x with a projection π(x, S _j ) not equal to any r _jh contributes nothing to the cost of the assignment. This ‘inverts’ the semantics of relations in the DCSP, in which the satisfying relations are enumerated; now the relations imposing a ‘cost’ are enumerated, and only these relations may eliminate solutions. The PCSP formulation generalizes naturally to constrained optimization problems, in which an assignment minimizing the cost is desired, but solutions exceeding the cost are forbidden. Alternatively, if B is arbitrarily large and minimum cost solutions are desired, the resulting problem is similar to the MAX-CSP (Wallace, Reference Wallace1996).

In order to extend DCSPs to optimization problems, we must add some new transformations. First, we must be able to change the cost of any tuple in a PCSP:

Strictly speaking, adding and removing constraints and tuples from relations are different for CSPs and PCSPs. In order to avoid confusion we add new notation for these transformations when applied to PCSPs.

The transformations X+, X−, d+, d− are identical to their DCSP counterparts.

We now show how a CSP ${\cal P}_{i} $ can be transformed into a PCSP ${\cal P}_{j} $ . Doing so requires transforming C _j , or more specifically, $R_{j} \in{\cal P}_{i} $ , into $(R^{\prime}_{J} ,\,f_{j} )\in{\cal P}_{j} $ . For each $r_{{j_{h} }} \in d \left( {X_{{j_{1} }} } \right){\times}\,\ldots\,{\times}d\left( {X_{{j_{k} }} } \right)$ such that $r_{{j_{h} }} \, \notin \, R_{j} $ , add $r_{{j_{h} }} $ with $f\left( {r_{{j_{h} }} } \right)\, {\equals}\,1$ to $R_j^\prime $ . Let B=1. Let x be a satisfying assignment to ${\cal P}_{i} $ . Then $\pi \left( {x,\,S_{i} } \right)\, {\notin} \,R_{j}^{\prime} $ , and therefore contributes 0 to the sum $\mathop{\sum}\nolimits_{r_{{j_{h} }} \,\mid\:\exists C_{j} \,\pi \,\left( {x,\,S_{j} } \right)\, {\equals}\,r_{j} _{{_{h} }} } {f\left( {r_{{j_{h} }} } \right)} $ by definition. For each solution x to the original CSP, the sum is therefore below the bound 1. Any other assignment has a sum of at least 1 and therefore does not satisfy the inequality. We can then replace R _j with $R_{j}^{\prime} $ as the relation for C _j in the new PCSP. We call this new transformation v+. Similarly, we can define the inverse transformation v− which can only be performed if $\forall C_{j} \, \forall r_{{j_{h} }} \in C_{j} f\left( {r_{{j_{h} }} } \right)\, {\equals}\,1$ and B=1. These transformations are neutral, in the sense that all satisfying assignments continue to satisfy. The transformation is polynomial time in the size of the (P)CSP. As noted above, the transformation ‘inverts’ the set of tuples in the relations, since we add the tuples that will exceed the cost bound and therefore ‘violate’ the constraints.

Note: while the presence of elements of the relations with $f\left( {r_{{j_{h} }} } \right)\, {\equals}\,0$ may seem unnecessary (as well as a waste of space) in a PCSP, these relations are made explicit to simplify the description of the transformation s+ followed by f+, or f− followed by s−.

Finally, consider a transformation to increase or decrease B. This transformation arises naturally in branch-and-bound search, and may also arise during modeling. Is this equivalent to a series of transformations +f, −f? Trivially, the answer is no. Making a single change +f, −f can introduce a small change to the solutions that is impossible to mimic with a change to B, as shown in Figure 3.

Figure 3

Changes to solutions via f+ ,f− may not be achievable via a change to B. This partial constraint satisfaction problem (top left) is a transformed constraint satisfaction problem allowing no constraint ‘violations’ (i.e. the only solution has accumulated cost 0). Changing B from 1 to 2 (top right) allows one ‘violation’, thereby introducing three new solutions. This is the minimum number of new solutions that can be achieved. By contrast, if f(r _{2, 4}) of constraint C ₂ is changed from 1 to 0.9 (bottom) then one new solution is introduced

By contrast, can changes to the solutions due to changes to B be accomplished by a set of changes +f, −f? The trivial answer is yes.

Recall the criteria for x to be a solution to a PCSP is $\mathop{\sum}\nolimits_{r_{{j_{h} }} \,\mid\: \exists C_{j} \,\pi \,\left( {x,\,S_{j} } \right)\, {\equals}\,r_{j} _{{_{h} }} } {f\left( {r_{{j_{h} }} } \right)} {\rm \,\lt\,}B{\rm }$ . If we transform B to B+b to admit more solutions, we can instead scale each $f\left( {r_{{j_{h} }} } \right)$ by a factor of ${B \over {B{\plus}b}}$ and achieve an identical result. To show the cost of the solutions after these transformations satisfy the old bound:

The same argument holds for assignments that are not solutions, and if we reduce B. Notice that the ranking of optimal solutions is also preserved.

While transforming the bounds can, in fact, be simulated by transformations f+, f−, the fact that the required transformations impact every tuple in every constraint makes for a somewhat indiscriminate transformation. This justifies the inclusion of more concise bounds changes in our list of transformations.

In Figure 4 we show the transformations from CSPs to PCSPs, and between PCSPs.

Figure 4

Transformations between constraint satisfaction problems and partial constraint satisfaction problems. Set of all valid transformations. The dotted one shows a valid transform but not the exact evolution of the dynamic constraint satisfaction problem in the figure

Increasing the cost of a tuple f+ or decreasing the bound b− may not decrease the number of solutions or fraction of solutions, but they cannot increase the number or fraction of solutions. Vice versa, decreasing the cost of a tuple f− or increasing the bound b+ may not increase the number of solutions or fraction of solutions, but they cannot decrease the number or fraction of solutions. The transformations for PCSPs are shown in the table below.

5 Planning using dynamic constraint satisfaction problems: discussion

As described in the introduction, some planners already use a DCSP framework during search. In this section, we discuss how this new formalization of DCSPs could be used for planning, both as a foundation for search and also during planning model development.

Recall that a Simple Temporal Constraint has the form a⩽|X _i −X _j |⩽b. A Disjunctive Temporal Constraint has scope X _i , X _j , X _k ; d(X _k ) is a finite discrete set, and d(X _i )=d(X _j )=Ƶ. For each x _k ∈d(X _k ) there is a pair of constants a _x , b _x ; the constraint has the form (X _k =x _k )⇒(a _x ⩽|X _i −X _j |⩽b _x ). What happens if a new assignment X _k =x _k is made in a DTN during search after determining that the previous value y _k resulted in a temporal constraint violation? One approach is to have the planner maintain the mapping between discrete values of the variable X _k and a Simple Temporal Network by transforms C+, C− executed during search. When a violation is detected during search and assignment X _k =y _k is revoked, the violated Simple Temporal Constraint (a _y ⩽|X _i −X _j |⩽b _y ) is removed, as described in Figure 2 (bottom); when assignment X _k =x _k is made, the new constraint (a _x ⩽|X _i −X _j |⩽b _x ) is added. This approach is used in several planners (e.g. Ghallab & Laurelle, Reference Ghallab and Laurelle1994; Frank & Jónsson, Reference Frank and Jónsson2003); by contrast, the approach in Do and Kambhampati (Reference Do and Kambhampati2000) is to construct the CSP incrementally and extract actions from the solution. The potential advantage of the new approach is early detection of no-goods as relations are added to constraints. However, this comes at the price of adding individual relations during search, which is impractical for large discrete constraints, and impossible for continuous constraints.

A second potential use is in the incremental modeling of a planning domain. Simple planning problems (linear STRIPS planning in which all preconditions are positive) do not require sophisticated analysis using constraints; adding preconditions and negative effects cannot increase the number of plans, and adding positive effects cannot decrease the number of plans. However, more complex planning and scheduling problems (including negative preconditions and partial orders in STRIPS planning) may benefit from this new framework at modeling time. A recent line of research known as Model-Lite Planning due to Kambhampati (Reference Kambhampati2007) contemplates early-stage models for criticism as opposed to planning. A formalism such as the one proposed here could be used for such a purpose. Suppose new conditions or effects are added to some activity as part of the modeling process. Is the change a restriction or relaxation? Is it easy to tell immediately? If the change is not obvious, or perhaps even if it is, informing the modeler of the consequences of such a change at modeling time may be valuable. In Frank (Reference Frank2014) an analysis of changes to STRIPS models and the resulting CSP using the approach in Do and Kambhampati (Reference Do and Kambhampati2000) reveals that some domain model changes can lead to multiple restrictions and relaxations of the resulting CSP, making it hard to know if plans are being added or removed. Specifically, adding effects to actions can lead to additional constraints (e.g. static mutexes) but also eliminate constraints (establishing conditions not true in the initial state).

A third use of the new formalism is to analyze the transformation of planning as satisfiability into an optimization problem at modeling time, for example, using the v+ transformation. Early in model development it may not be apparent whether the right problem is a satisficing or optimization problem; a ‘push-button’ option to change the problem offers significant advantages. Consider, for instance, integrating a simple report on the consequences of adding or removing conditions and effects to a tool such as itSimple, described in Vaquero et al. (Reference Vaquero, Romero, Tonidanel and Silva2007), for use in a plan or model critique phase of Model-Lite planning. Feedback for simple situations like adding or removing conditions and effects, as analyzed in the earlier version of this paper (Frank, Reference Frank2014), may provide value, as would analysis when satisficing problems are transformed into optimization problems. However, successful application of this idea is complicated by two factors. The first, and more minor problem, is that, as described, the PCSP framework proposed in this paper uses a cost upper bound; while some planning problems are naturally posed in terms of action cost (e.g. Keyder & Geffner, Reference Keyder and Geffner2008), others may be better formalized as problems of maximizing the benefit of achieved goals (e.g. van den Briel et al., Reference van den Briel, Vossen and Kambhampati2004). Addressing problems of maximizing benefit requires a minor change in the PCSP framework. The second, more difficult problem, is to find a suitable DCSP representation of the planning problem for representing plans with costs. For instance, while it might be possible to create a CSP formulation with costs incurred if goals are not achieved, it may be hard to do so for makespan minimization objectives.

6 Conclusions and future work

In this paper, we present a new classification of dynamic constraint satisfaction transformations based on a quantifiable criteria: the change in the fraction of solutions $\Delta L_{p} \left( {\cal P} \right)$ . This criteria can be used to evaluate elementary transformations of a CSP as well as sequences of transformations. We identify a core set of transformations from which all other transformations can be constructed. We extend the notion of transformations to include optimization problems. The resulting transformations are shown to consist of restrictions, relaxations, and neutral transformations. For optimization problems, classes of transformations may contain more than one type of transformation. We identify a complete set of transformations that can transform a problem from a satisficing problem to an optimization problem, or back.

There are a variety of avenues for future work in this area. Principle among them is extending this framework to richer constraint satisfaction formalisms. While the analysis works for finite domain constraints where enumeration of solutions is straightforward, extension to constraints over integers or reals is a new challenge. In addition, while CSPs should be transformable to more sophisticated soft constraints frameworks, for example, semirings, there may be surprises here, and a thorough analysis should be performed.

The analysis of DCSP transformations using the new framework contains no real surprises when compared with previous CSP theories. The most complex transformation, adding or removing the satisfying tuples in a relation, have the most impact on the solutions, but are the hardest to analyze. The most interesting question from the point of view of computational complexity is whether or not deconstructing a transformation into its primitive parts helps ‘eager’ propagation. Unfortunately there are no easy answers to this question.

The impact of the new formalism on planning is an open question. The most interesting potential use is for support during model development, by identifying model changes that add or remove plans. However, numerous design questions must be answered to apply the framework. How would such information be provided to a modeler? What can modelers do with this information when it is provided? Different planning to CSP encodings, such as those described in Banerjee (Reference Banerjee2009) or van den Briel et al. (Reference van den Briel, Sanchez Nigenda, Do and Kambhampati2005), may lead to different results than those described in the earlier version of this paper (Frank, Reference Frank2014). Extending the analysis for modeling to include more complex formalisms such as time, resources, domain axioms, disjunctive preconditions and conditional effects will extend the power of the approach.