A Comparison of ATMS and CSP Techniques

1 Introduction

Both constraint satisfaction techniques and truth main­ tenance systems are used widely in artificial intelligence applications. A variety of refinements have been devel­ oped to avoid the thrashing behavior that often accompa­ nies them. This paper demonstrates that the intuitions underlying these refinements are essentially similar. In particular, Mackworth's [13] notions of node, arc, path consistency, Freuder's [11] k-consistency, and Dechter and Pearl's [1] directed k-consistency for constraint satisfac­ tion problems(CSPs) and techniques for assumption-based truth maintenance (ATMS) [4, 5] are encompassed by a few propositional resolution rules. This paper shows that in many cases the constraint networks produced by the standard local consistency algorithms are identical to ones produced by the ATMS for the same input constraint net­ work. A longer version of this paper (10] explores these issues in far greater detail.

This paper details how both CSP techniques and ATMS's are based on a few resolution rules. By out­ lining the relationship between these two sets of tech­ niques, a connection in terminology and algorithms is es­ tablished between two distinct subfields of artificial intel­ ligence. This holds the promise that any advance in one subfield is easily communicated to the other. At the mo­ ment both have incorporated essentially the same intu­ itions. However, we hope that this synthesis will lead to faster progress on these issues of mutual interest.

1.1 Search vs. Inference

Although CSP and ATMS tasks seem, on the surface, to b very different, both require combining two distinct mode of reasoning to minimize overall computational cost t complete tasks. In the following sections we define mo precisely what ATMS's and CSPs are. Before diving int those details, we address the frameworks within which CS and ATMS techniques are used.

CSPs are typically solved by backtrack search. How ever, as Mackworth [13] demonstrated, backtracking suf fers from numerous maladies often making it "grotesque! inefficient." Mackworth pointed out that if the constraint are preprocessed then many of backtracking's maladies ca be eliminated. This preprocessing involves tightening (vic local consistency algorithms) the initial constraints so tha backtracking detects futile states earlier leading to fewe backtracks. Freuder [11] generalized Mackworth 's result and showed that with sufficient preprocessing most or al of the futile backtracks can be avoided. However, the ex pense of the preprocessing to avoid all futile backtrack typically outweighs the cost of the futile backtracks in th first place. A fundamental issue for CSP solvers is to de termine how much preprocessing is necessary to minimiz~ total effort (preprocessing plus backtracking).

An ATMS task cannot be so cleanly stated as a CSP. In stead an ATMS is always used interactively with some kin of inference engine. The inference engine is roughly analo gous to the backtracker while the ATMS is roughly analo gous to the module which enforces CSP local consistency The inference engine supplies the ATMS with a stream o clauses (as opposed to a CSP where the input problem i fixed) and queries about those clauses. The most typica query the inference engine makes is whether a particula set of propositional symbols is consistent (i.e., is part o a global solution). Ensuring that the ATMS never replie~ that a set is consistent when it is not is computationall disastrous in practice. However, answering that a set i consistent when in fact it is not results in futile inferenc engine effort on that set of assumptions.

We thus see that ATMS and CSP techniques embod the same computational trade-offs. Futile backtracking i analogous to futile inference engine work, but avoiding al futile backtracking or all futile inference engine work is to expensive also. Thus, the CSP local consistency algorithm are motivated by exactly the same set of problem solvin concerns as the ATMS algorithms. But even more surpris­ ing, most of the CSP local consistency algorithms them­ selves have almost identical analogs in the ATMS frame work.

Due to the nature of the ATMS task, all ATMS algo­ rithms are incremental. CSP techniques are typically use to solve completely specified problems, and need not be in cremental. However, many of the CSP local consistency al­ gorithms can easily be made incremental. (Although some CSP algorithms take explicit advantage of the fact that the problem is completely specified a priori.) ATMS tech­ niques are more general, not because of their inherent in­ crementality, but rather that they can directly solve any task stated propositionally. For example, every CSP can be conveniently expressed as an ATMS problem, but not every ATMS problem can be conveniently expressed as a CSP. This gives the ATMS the flexibility that it can in­ tersperse solving a CSP with other kinds of propositional reasoning. The the local consistency intuitions underlying CSP techniques thus have a more general manifestation within the ATMS framework.

2 Definitions

2.1 CSPs

For more details, Mackworth [14] presents an excellent in­ troduction to CSPs. A constraint satisfaction problem (CSP) is specified by a set of variables x 1 , ... , Xn and a set of constraints on subsets of these variables limiting the val­ ues they can take on. Cijk ... notates the constraint among variables Xi,Xj , XJ.:, ....

If the constraint places no limitations on its variables, it is called universal. By convention, universal constraints are not explicitly represented. Every variable Xi is re­ stricted to a finite set Di of values {ail, ... , ainJ. The language in which these constraints are stated, or the costs of determining whether a set of values satisfies a constraint are typically not addressed in the CSP literature. We ad­ dress those in section 10.

The constraint satisfaction task consists of finding all sets of values a1j" ... , an in for x1, ... , Xn that simultane­ ously satisfy all the given constraints. Two CSPs are equiv­ alent if they both have the same set of solutions. Unlike much of the CSP literature we always consider the general case where the constraints can be n-ary and asymmetric.

Consider the following example from Freuder [11]. We are given the variables x 1 , x 2 , x 3 with domains D1 ={a, b}, D2 = { e,!}, and D3 = { c, d, g} and binary constraints (specified extensionally by their allowed tuples) c12 = {be,bf}, C13 = {bc,bd,bg}, and C23 = {ed,fg}. This CSP has two solutions:

Every CSP .is characterized by a constraint network which, in general, is a hypergraph in which the vertices rep­ resent variables and the hyperedges represent constraints. All the CSP local consistency algorithms operate by trans­ forming constraint networks into equivalent but (hope­ fully) simpler ones.

2.2 ATMS

The input to the ATMS is a set of propositional literals C, a set propositional ciauses C constructed from those literals, and a distinguished set of assumptions A C C. The task of the ATMS can be succinctly characterized as finding all prime implicates mentioning at most one non-assumption literal (i.e., in C- A) [16]. However, for the purposes of this paper we characterize (equivalently) the ATMS in the terms of [4].

An environment is a subset of A. An environment E is inconsistent (called nogood) if the union of E with C is not satisfiable. Nogood X is subsumed by nogood Y if the assumptions of Y are a proper subset of those of X. A choose is a clause whose literals are all assumptions and is often written choose{A1, ··· , Am}- ChooseR is subsumed by choose S if the assumptions of S are a proper subset of those of R. A literal/ is said to hold in environment E if I follows from the union of E and C under the rules of propositional logic. A nogood is minimal (with respect to subset) if it contains no others as a subset .

The ATMS problem is to find all minimal nogoods and to identify for every literal I E C a set of environments { E1 , ... , E1.:} (called the /abe~ having the four properties:

1. [Soundness.] I holds in each Ei.
2. [Consistency.] Ei is not nogood.
3. [Completeness.] Every consistent environment E in which 1 holds is a superset of some Ei.
4. [Minimality.] No Ei is a proper subset of any other.

All ATMS algorithms maintain an auxiliary set N of un­ subsumed nogoods. For an ideal ATMS N is exactly the set of minimal nogoods. However, identifying all minimal nogoods is expensive and thus, in practice, ATMS algo­ rithms usually identify only some of the nogoods, thereby (only) foregoing the above consistency property but at great improvement in efficiency. All ATMS algorithms en­ sure a weakened form of consistency:

2. [Consistency'.] Ei is not subsumed by N.

3 Propositional encoding of CSPs

A CSP is encoded as a set of propositional clauses. We re­ fer to the mapping of constraint networks to a clause sets C as C = !1(CN). For every Xi we introduce a proposi­ tional symbol for every possible value aij E Di. We write these propositional symbols as x : a which represents the proposition that x = a. The constraints are formulated as a set of clauses C in terms of these propositional symbols as follows. For each variable Xi we include in C the posi­ tive clause (i.e., a choose) which states that every variable must have a value:

In addition, we specify that a variable can have at most one value; for every Xi, for every aij, for every ail.: such that k f. j we include in C the binary negative clause:

Every constraint Cz in the constraint network is en­ coded as follows. For every tuple [t 1 , ... , tm] of assign­ ments to the variables of Z we need a formula disallowing that conjunction:

which in clausal form is:

We have encoded the three conditions which define a constraint problem: every variable has a value, no variable can have more than one value, and no combination of vari­ able assignments violates any constraint. Therefore, every complete assignment of truth values to the propositional symbols which satisfies every clause in C, corresponds to a solution to the original CSP. Conversely, every solution to the CSP corresponds to an assignment of truth values to the propositional symbols which satisfies every clause of C.

3.1 Example continued

We were given the variables x1, x2, x3 with domains D1 = {a, b}, D2 = {e,f}, and D3 = {c,d,g} and binary con­ straints c12 = {be, bf}, c13 = {be, bd, bg }, and c23 = {ed,Jg} . C consists of the following clause set. Each vari­ able must have a value:

X1:a V X1 :b, X2:e V X2:/, X3:C V X3:d V X3:g The negative clauses stating that each variable can have only one value:

3.2 CSP-Propositional mapping

Every constraint network C N has a unique encoding C = !:::..( C N) as a set of clauses. The inverse, C N = !:::.. - 1 (C) exists only under the following conditions:

1. All clauses are either positive or negative.
2. Every symbol appears in at most one positive clause.
3. For every pair of symbols in every positive clause, the binary negative clause of these two symbols is in the clause set.
4. No negative clause of three or more literals contains two symbols occurring in the same positive clause.

The following defines t::..- 1: (1) every positive clause de­ fines a variable and (2) every negative clause mentioning only symbols which occur in positive clauses but which does not mention two symbols from the same positive clause indicates a disallowed combination for the constraint among the variables of the symbols. Note that for every constraint network CN: CN = ~:::..- 1 (/:l.(CN)).

3.3 Backtrack search

Both ATMS and CSP techniques exploit backtrack search for identifying global solutions. The following is a simple generic backtrack algorithm for constructing solutions to a CSP encoded as a set of clauses C. Let Subsumed?(S, C) be a function which checks whether the negative clause constructed from the symbols of S is subsumed by C (equivalently, the function checks whether interpreting the symbols of S to be true falsifies any clause of C). Let the global variable b count the number of backtracks (i.e., the number of times BT was called without producing a solu­ tion). b is initialized to be 0.

ALGORITHM BT(S, C):

1. [Termination check] If every variable has a value inS, then markS as a solution and return.
2. [Subsumption check] Pick a variable x; which does not have a value in S. If Subsumed?(S U { x;:a;i}) holds for every value a;;, then set b = b + 1 and return.
3. [Iterate] For every j, unless Subsumed?(SU{x;:a;j}) call BT(S U { x;:a;i} ).

Note that BT implicitly incorporates the binary negative clauses involving elements of the same variable.

Unfortunately, using BT to find all solutions can in­ volve an enormous amount of often futile [4, 13] backtrack­ ing (i.e., b will be very large) . Both ATMS and CSP al­ gorithms incorporate the strategy which, in propositional terms, amounts to constructing additional clauses, entailed by C. Adding to C a clause entailed by it, can only re­ duce the number of backtracks required to find a solu­ tion. Adding all clauses to C entailed by it, guarantees backtrack-free search.

4 Propositional inference rules

All ATMS and CSP local consistency techniques can be viewed as implementing a few basic resolution rules. All of these inference rules change the clause set, preserving the set of global solutions, but improving the efficiency of the backtrack search used to find the solutions. This section presents a set of inference rules referred to as I which we use in subsequent sections to characterize the ATMS and CSP local consistency algorithms. The names of these rules are chosen for compatibility with the equiv­ alent ATMS rules.

HO: This rule removes subsumed clauses from C. If clause D E C is subsumed by some other clause E E C, then D is removed from C.

H3: A unit resolution rule:

A1 V · · · V Am replaces the antecedent disjunction

H5: This rule does the main work. N(f3) indicates the negative clause with symbols {3. Given a set of negative clauses N(a;):

H5 can a generate a very large number of clauses, therefore it is useful to define two restrictions of H5.

H5-k: H5 restricted to only infer negative clauses below size k. The basic intuition behind this restriction is that it reduces overall computational complexity by reducing the number of clauses H5 introduces. In addition, when H5 is used as part of search, smaller clauses are more valuable than larger ones because they provide more pruning. Given a set of negative clauses N ( o:;):

(Note that the rule will only apply to lo:;l ~ k.)

5 Local consistency conditions

The local consistency algorithms enforce local consistency conditions by adding clauses. These added clauses reduce the backtracking needed to find solutions.

In discussing these theorems it is important recognize that the constraints in a constraint network, by construc­ tion, do not contain spurious information. For example, if a constraint network has the constraint c12 = { ab }, then necessarily a E D1 and b E D2 · Thus, all CSP local consis­ tency algorithms implicitly incorporate a limited form of subsumption: when an element is removed from a domain of some variable, all constraints referring to that variable are simplified to no longer to refer to the deleted element . (Note that this happens automatically if constraints are represented by allowed combinations, however, how a con­ straint is represented is not specified in the CSP approach.)

5.1 Node consistency

Node consistency ensures that the singleton constraint C;(X) for every node i and any value X E D; . Node consistency ensures that all unary constraints are used to delete disallowed domain elements . In the clausal encod­ ing, the domain of a variable is represented by a single disjunction and unary constraints appear as singleton neg­ ative clauses .

Theorem 1 A constraint netw~rk C N is node consistent iff no application of H3 to C = !:!J..( CN) produces a clause.

5.2 Arc consistency

Arc consistency is ambiguously defined in the CSP litera­ ture. Here we adopt the definition of [14] which is slightly stronger than the one in [13] . Note that arc consistency does not necessarily imply node consistency, although all so-called arc consistency algorithms in the literature en­ force node consistency as well. Arc consistency ensures that for every pair of nodes i and j, for every value X E D; there exists a value Y E Di which is not excluded by C;i. (To avoid double subscripts, I write x for x; and y for Xj.)

Theorem 2 A constraint network CN is arc consistent iff no application of H5-2 to C = !:!J..(CN) produces a singleton negative clause.

Proof. Let the Y, be the elements of Dj . This is represented by the disjunction:

Suppose that there were some value X E D; such that every value Y E Di was excluded by C;i. These exclusions are represented by binary negative clauses.

Thus, there must exist a set of binary negative clauses all of which contain x:X and each of the possible values y:Y:

Applying H5-2 to these binary clauses we obtain the singleton negative clause -,x:X.

The converse is straight forward .

5.3 Path consistency

As with arc consistency, path consistency is also ambigu­ ously defined. We adopt the stronger definition of path consistency from [14] : if for every three nodes r, s and t if for every value X E Dr and Z E D, not excluded by the constraint between nodes Crt there exists a value Y E D, such that the values X and Y are not excluded by Cr·, and the values Y and Z are not excluded by C,,.

Theorem 3 A constraint network CN is path consistent iff no application of H5-3 to C = !:!J..(CN) produces a binary clause not subsumed by C.

5.4 k-consistency

[10] generalizes the preceding result to obtain:

Theorem 4 A constraint network C N is strongly k­ consistent iff no application of H5-k to C = !:!J..(CN) in­ troduces a new clause not subsumed by C.

6 Local consistency algorithms

All ATMS and CSP local consistency algorithms employ some subset of the inference rules I (from section 4) to modify the clause set C to achieve local consistency. Given the theorems of the preceding section and the set of in­ ference rules I, the following useful algorithmic properties hold for a clausal encoding of a CSP.

Proposition 5 Given any subset of inference rules from I , any order of application will lead to the same resulting clause set as long as the clause set closed under those rules.

Proposition 6 Any algorithm incorporating any subset of inference rules from I achieves node consistency as long as the resulting clause set is closed under H3.

Proposition 7 Any algorithm incorporating any subset of inference rules from I achieves node and arc consistency as long as the resulting clause set is closed under H3 and H5-2.

Proposition 8 Any algorithm incorporating any subset of inference rules from I achieves node, arc and path consis­ tency as long as the resulting clause set is closed under H3 and H5-3.

Proposition 9 Any algorithm incorporating any subset of inference rules from I achieves strong k-consistency as long as the resulting clause set is closed under H5-k.

6.1 The importance of the algorithms

The basic motivation for applying the local consistency al­ gorithms to constraint networks is to reduce or even totally eliminate the number of backtracks required to identify the solutions. This issue is extensively discussed in the CSP literature. A general result from Freuder stated in propo­ sitional terms is:

Theorem 10 If the clause set C = tl(CN) is closed un­ der H5, then the solutions can be found via backtrack-free search.

The local consistency conditions are similarly important to ATMS operations - often backtrack search is used to construct problem solutions. The local consistency con­ ditions however play an even more central role in ATMS functioning. Fundamental to the ATMS is its ability to ef­ ficiently answer queries whether the conjunction of a set of symbols is known to be inconsistent. If the ATMS replies that the symbol set is consistent when, in actual fact, it is not, the inference engine may perform an unbounded amount of futile work. Therefore, it is important that the ATMS answer such queries correctly. If the clause set is closed under H5, then the ATMS can correctly answer the queries by a simple subsumption test with N.

Extensive experience with the ATMS has shown that closing the initial clause set under H5 usually yields a total increase in overall problem-solving effort. This is because the inference engine effort saved by correctly answering the queries is outweighed by the computational effort of closing the clause set under H5. Usually, it is globally optimal to close the clause set under H5-k for some small value of k. These conditions, of course, correspond to the ATMS notions of arc and path consistency.

7 CSP algorithms

Both ([13] and [14]) definitions of local consistency admit more ambiguity than first meets the eye. Consider just the simple case of achieving node consistency. A node consis­ tency algorithm converts a constraint network to an equiv­ alent one which is node consistent. Unfortunately, there may be a very large number of equivalent networks which are node consistent. The node consistency condition, al­ though well-defined, does not specify which of these net­ works a node consistency algorithm must find. Although rarely specified, all consistency algorithms incrementally remove local consistency violations by minimally tighten­ ing the constraints to find an equivalent consistent network meeting the local consistency condition.

The common CSP local consistency algorithms can be analyzed in terms of the inference rules of I. The node consistency algorithm NC-1 repeatedly applies rule H3.

Theorem 11 Executing NC-1 to constraint network CN has the same result as applying .tl- 1 to the closure of tl(CN) under H3 and H5-2.

All arc consistency algorithms close the clause set under H3 and H5-2, applying H3 first whenever possible. The different arc consistency algorithms do various amounts of bookkeeping to prevent futile applications of H5-2.

Theorem 12 Executing AC-1, AC-2, or AC-3 to con­ straint network CN has the same result as applying .tl- 1 to the closure of tl(CN) under H3 and H5-2.

Analogously, the path consistency algorithms close the clause set under H3 and H5-3.

Theorem 13 Executing PC-1 or PC-2 to constraint net­ work CN has the same result as applying .tl- 1 to the clo­ sure of tl(CN) under H3 and H5-3.

8 ATMS algorithms

The ATMS contains a variety of mechanisms to maintain node labels which we do not discuss here. Instead, this paper focuses on ATMS techniques to construct nogoods entailed by C. The ATMS represents the clauses as N a set of nogoods (i.e., negative clauses) and V a set of chooses (i.e., positive clauses) where every symbol representing an assignment is an ATMS assumption. As · the ATMS ex­ plicitly represents clauses it can directly incorporate the inference rules I. All versions of the ATMS algorithms incorporate some subset of these inference rules.

8.1 Efficiency considerations

All ATMS algorithms incorporate the subsumption rule HO. The motivation for incorporating HO is that there are an exponential number of potential clauses to construct, but, on average, the subsumption rule will eliminate most of them from the clause set. Therefore, in all ATMS algo­ rithms HO is always performed first.

Property 5 of section 4 guarantees that the application order of inference rules is irrelevant. Therefore ATMS im­ plementations order the application of inference rules to minimize total effort. The basic intuitions behind the or­ dering heuristics are that H5 is extremely expensive and should always be applied last and to smaller nogoods first -smaller nogoods should be discovered first as they sub­ sume far more higher-order nogoods which the algorithm might futilely have to process.

It should be noted that neither rules HO or H3 are nec­ essary to ensure backtrack free search. Both are included for efficiency considerations. Note that the use of rule HO makes the overall algorithm adaptive- it allows an ATMS algorithm to dynamically adapt the set of nogoods to re­ solve as it eliminates nogoods from consideration.

8.2 ATMS algorithm

Whenever a nogood becomes subsumed, as well as being removed from N it is removed from all pending queues, and all processing on it is halted. The algorithm maintains a queue L of pending nogoods ordered by size, initially L is all new nogoods of size k or less. In usual practice RE­ SOLVE is invoked after every atomic ATMS operation.

ALGORITHM RESOLVE:

1. [Unit preference for H5] If there is a singleton choose, its single literal is set to true, and every nogood ng mentioning the literal is replaced by a new nogood with that literal deleted.
2. If L is empty, return. Pick and remove ng a smallest nogood from L. If L is empty, return.
3. If ng is the empty nogood, halt. The constraints are unsatisfiable.
4. [H3] If ng is a singleton, it is removed from the choose(s) in which it appears. All processed un-

subsumed nogoods which mention elements in these chooses are requeued on L. Go to step 1.

1. (H5) For every element e of ng, find its choose(s) d, and for each element of d collect all the processed un­ subsumed nogoods in which it appears. Iteratively, pick one of these nogoods for each element of d, union their elements, and delete the elements of d. Each new set thus constructed is a new nogood ng*. If this ng* is subsumed, do nothing. Otherwise, insert it into the nogood data-base and in L if it is of size less than k.
2. Go to step 1.

Although this algorithm is designed to identify smaller no­ goods first , it cannot guarantee this. For example, while processing nogoods of size four, it might produce a new nogood of size three. Note that organizing the search to process smaller nogoods first is equivalent to organizing the search to process smaller constraints first . Thus we can guarantee that if the above algorithm has ever processed a nogood of size m, that it has processed every constraint of size l < m.

The following is the execution trace of the first few itera­ tions of the algorithm applied to our example (with k = n). Initially, both the nogood data-base and L consist of the following. For clarity the binary nogoods involving ele­ ments of the same variable are left out. Chooses and no­ goods are printed out as sets of symbols.

Initial nogoods: { {x2 :e, x3 :c}, {x2 :f, X3 :c}, {x2 :f, X3: d}, { X2:e , X3:g}, { X1 :a, X3:C }, { X1 :a, X3 :d}, { X1 :a, X3:g }, { X1 : a,x2:e}, {x1:a, x2:f}}

Picking: { x2:e, x3:c}

Picking: { x2:f, x3:c}

Resolving the nogoods {x2:e , x3:c} and {x2:f,x3:c} with choose {x2:e, x2:!} gives the new nogood {x3:c} .

Inserting { x3 :c} into the new the no good data base re­ moves the subsumed, { {x2:e, x3 :c}, {x2:f, X3:c}, {x1:a, x3: c}} , leaving the nogoods, {{x3 :c}, {x2 :f, x3:d}, {x2:e, x3: g}, { X1 :a, X3:d}, { X1:a , X3:g}, { X1:a, X2 :e}, { X1:a, X2:f} }. Picking: { x3:c}

Eliminating it from the choose: { x3:c, x3 :d, x3:g}.

9 Comparison of algorithms

Due to the fact the ATMS always performs subsumption, different constraint networks may be represented by the same N and V . Suppose constraint C123 disallowed the combination abc and constraint c12 disallowed the combi­ nation ab . After encoding the constraints as nogoods, the ATMS throwsaway the nogood abc because it is subsumed by ab. Hence the same V and N corresponds to (at least) two equivalent constraint networks - one in which c123 allows abc and another which does not. To avoid these difficulties we define the following:

Definition 14 A constraint network is irredundant if ev­ ery tuple T of assignments disallowed by every constraint Cz is not disallowed by some other constraint Cy where Yc z .

Definition 15 The irredundant form of a constraint net­ work is an equivalent irredundant network formed by re­ peatedly removing excluded tuples in higher-order con­ straints also excluded by lower-order constraints.

Given clause set C we can always construct an equivalent irredundant constraint network as follows. If a clause set C is closed under HO, then C N = Ll- 1 (C) is irredundant.

9.1 Comparison of results

As a consequence of propositions 6, 7 and 8 (see section 4) the constraint network represented by (i.e., via Ll- 1 ) a set of clauses is node, arc and path consistent after the ATMS algorithm has been executed for k = 1, 2, 3 respectively.

The standard ATMS algorithms always apply H5 to unit chooses immediately. This unit preference strategy is, in my experience, always worth it. However, the CSP al­ gorithms do not incorporate this strategy for H5 (even though they incorporate, as the ATMS does, the unit res­ olution rule H3). As a consequence of the ATMS's unit preference strategy, the irredundant form of the constraint network produced by a CSP algorithm is not necessarily the same as the one produced (via Ll- 1 ) by an ATMS algorithm. For example, running the standard node con­ sistency algorithm NC leaves the network Dx ={A}, Dy = { B, C}, Cxy = {A, C} unchanged because it is already node consistent. However, after processing with k = 1 the ATMS has reduced the network to Dx = {A}, Dy = {C}. However, we could delete step 1 from RESOLVE (step 5 would deduce the same nogood later anyway). So modified, the irredundant form of the constraint network produced by the standard node and arc consistency algorithms is the same (via Ll- 1 ) as the ATMS produces with k = 1 and 2 respectively.

The comparison with path consistency is more difficult. Instead of dwelling on path consistency, it is more useful to consider the generalized notion of k-consistency. The ir­ redundant form of the network produced by Freuder's syn­ thesis algorithm (11) is the same (via Ll- 1 ) as RESOLVE with step 1 disabled.

See [10) for a comparison of the computational complex­ ities.

10 Comparison of the approaches

In this paper we have focused on ATMS concerns which re­ late to CSPs. However, an ATMS is a very general problem solver facility which provides far more functionality than any CSP algorithm. For example, constructing explana­ tions, doing differential diagnosis, interleaving formulation and solving, etc. As a consequence, it is unlikely that an implementation of a constraint solver using the ATMS would use much of the encoding of 3.1. The CSP frame­ work is not concerned with where the constraints come from nor with the cost of evaluating constraint predicates on assignment tuples. The CSP framework also does not permit dynamic reconstruction of the constraint problem. These, among others, are important problem solving is­ sues. Thus, ATMS usage is oriented towards adaptively minimizing the number of constraints constructed, mini­ mizing predicate evaluations, and minimizing variable do­ mam s1zes.

10.1 Limiting predicate evaluations

Suppose that the problem at hand is a fixed CSP, except that it is extremely expensive to determine whether a set of values satisfy some constraint predicate C. For simplicity we assume that all such determinations are equally costly.

Consider the CSP discussed earlier: Variables x1 , x2 , x3 with domains D1 = {a,b}, D2 = {e,f}, and D3 = {c,d,g} and binary constraints c12 = {be,bf}, c13 = {bc,bd,bg}, and C23 = {ed,fg}. Encoding the problem as a CSP re­ quires evaluating every predicate on every combination of values. Thus C12 requires 4 evaluations, C13 requires 6 evaluations, and C23 requires 6 as well. Suppose that the ATMS-based problem solver searches for a solution by first instantiating C23, then C13, and then C12· This corre­ sponds to the ATMS execution trace presented in section 8.2. None of 6 evaluations of C13 can be avoided. How­ ever, after evaluating c13, c is determined to be inconsis­ tent, therefore constraint C13 need not be evaluated on ac or be (in general if any combination of values has been proven inconsistent by previous constraints it need not be tried). After doing the 4 remaining evaluations of C13 , a is determined to be inconsistent. Hence, C12 need only be evaluated on be and bf. Thus, the ATMS has saved 4 of the 16 expensive predicate evaluations. For more complex CSP tasks, for example if there were thousands of con­ straints mentioning x 1 , x2 , and combinations of other vari­ ables, the ATMS strategy yields far greater performance improvements. One could imagine a lazy CSP which evalu­ ated predicates as needed, but unless some technique (such as perhaps adaptive consistency) is used to control the con­ straints examined, not enough would be gained.

So far (as in section 3.3) we have been viewing back­ tracking as a post-processing technique to be invoked af­ ter the constraints (or clauses) have been processed by a local consistency algorithm. Particularly in the ATMS framework, local consistency calculations are easily inter­ mingled with backtracking. In fact, backtracking can be used as a control technique to limit unnecessary evalua­ tion of constraint predicates (7]. The combination of back­ tracking and the ATMS resolution rules produces as good a dependency-directed backtracking scheme as is possible (given the presumption that no additional reasoning over unevaluated predicates is permitted, i.e., given no addi­ tional information other than the clauses which the ATMS has been provided by the inference engine). Most ATMS solvers for CSP-like problems will incorporate some form of backtracking to control the evaluation of predicates. This is discussed in detail in (7].

10.2 Constraint propagation

CSP algorithms typically represent constraints by the ex­ tension of the allowed or disallowed combinations of values. Most constraints cannot be efficiently encoded this way. Suppose that we were given the constraint x = y + 1 and the fact that x and y had 10000 values each. In this case it is better not to encode both x and y as ATMS chooses as the encoding of section 3.1 would. Neither would it be reasonable to encode the constraint in terms of its allowed combinations. Rather, only y should be encoded as a vari­ able, and problem-solver rules should be attached to it such that if a value were obtained for it a value is computed for x as well. This idea is called constraint propagation. In the ATMS framework the values for x would be encoded as a set of non-assumption nodes and as the search encountered y's values, justifications would be installed for the nodes of x. Most constraints and constraint variables should be encoded this way instead of as described in section 3.1.

This approach maximizes the use of ATMS justification­ handling facilities which are efficient, minimizes the num­ ber of assumptions necessary to encode a CSP, and min­ imizes the use of the relatively inefficient hyperresolution rules.

If constraints are properly (6] encoded as justifications and problem-solving rules, then neither soundness nor completeness is lost. A great deal of efficiency is gained and the reasoning that underlies the construction of the constraints is explicit and under the control of the problem solver. Taking a bird's-eye view of constraint propagation applied to CSPs we recognize that, it transforms a CSP into a smaller and more tractable one but doing so un­ der explicit problem solving control such that search and predicate evaluation is minimized.

11 Acknowledgments

This paper profited greatly from lengthy discussions with John Lamping, Alan Mackworth and Ramin Zabih. Also, Daniel G. Bobrow, Rina Dechter, Mike Dixon, Ken Forbus, Felix Frayman, Ken Kahn, Sanjay Mittal, Judea Pearl, Raymond Reiter, Jeffrey Siskind, Mark Stefik, and Brian Williams provided valuable comments on this paper.