The Anatomy of Easy Problems: A Constraint-Satisfaction Formulation

Rina Dechter and Judea Pearl

Computer Sei~ Department, University of California, Los Angeles

ABSTRACf

This work aims towards the automatic generation of advice to guide the solution of difficult constraint­ satisfaction problems (CSPs). The advice is generated by consulting relaxed, easy models whicb are backtrack­ free.

We identify a subset of CSPs whose syntactic and semantic properties make them easy to solve. The syntac­ tic properties involve the structure of the constraint graph, while the semantic properties guarantee some lo­ cal consistencies among the constraints. In particular, problems supported by tree-like constraint graphs, and some width-2 graphs, can be easily solved and are there­ fore chosen as the target model for the relaxation scheme. Optimal algorithms for solving easy problems are presented and analyzed. Fmally, an efficient method is introduced for extracting advice from easy problems and using it to speedup the solution of hard problems.

I INTRODUCI/ON

A. Why study easy problems?

An important component of human problem­ solving expertise is the ability to use knowledge about solving easy problems to guide the solution of difficult ones. Only a few works in AI-- [12), [1)-- have attempt­ ed to equip machines with similar capabilities. Gaschnig [6), Guida et.al. [7], and Pearl [11] suggested that knowledge about easy problems could be instrumental in the mechanical discovery of heuristics. Accordingly, it should be possible to manipulate the representation of a difficult problem until it is transformed into an easy one, solve the easy problem, then use the solution to guide the search process in the original problem.

The implementation of this scheme requires three major steps: 1. simplification, 2. solution, 3. advice generation. Additionally, to perform the simplification step, we must have a simple, a-priori criterion for decid­ ing when a problem lends itself to easy solution.

·This work was supported in part by the National Science Foundation, Grant #MCS 81-14209.

This paper uses the domain of constraint­ satisfaction tasks to examine the feasibility of these three steps. lt establishes criteria for recognizing classes of easy problems, it provides special procedures for solving them, and it introduces an efficient method of extracting advice from them.

Constraint-satisfaction problems (CSP) involve the assignment of values to variables subject to a set of con­ straints. Understanding three-dimensional drawings, graph coloring, electronic circuit analysis, and truth maintenance systems are examples of CSP problems. These are normally solved by some version of backtrack searcb whicb may require exponential searcb time (for example, the graph colaring problem is known to be NP­ complete.)

In general, a problem is considered easy when its representation permits a solution in polynomial time. However, since we are dealing mainly with backtrack al­ gorithms, we will consider a CSP e&SJ if it can be solved by a backtrack-free procedure. Normally, a backtracking algorithm instantiates variables in a predetermined order, and for eacb next variable it chooses one value that is consistent with all previous assignments. H it doesn't fmd one, it backtracka to the previous variable, tries a new assignment for it, and continues from there. The al­ gorithm stops when all variables have been assigned values or when no new untried values are left for the fll'St variable. A backtrack-free searcb isonein which the backtracking algorithm completes without backtracking, thus producing a solution in time linear with the number of variables.

Most of our discussion is based on the concept of constraint-graphs [8] in whicb the nodes represent vari­ ables and the undirected arcs represent the existence of an explicit constraint between them. Freuder [5] has identified sufficient conditions for a constraint graph to yield a backtrack-free CSP, and has shown, for example, that tree-like constraint graphs can be made to satisfy these conditions, with a small amount of processing. Our main purpose here is to further study classes of con­ straint graphs lending themselves to backtrack-free solu­ tions and to devise efficient algorithms for solving them. Once these classes are identified they can be chosen as targets for a problern simplification scheme; oonstraints can be selectively deleted from the original specification so as to transform the original problern into a backtrack­ free one. The simplified problem can then provide advice on choices pending in the original problern. For example, we propose to use the "number of oonsistent solutions in the simplified problem" as a ~gure of merit t~ establish priority of value assignments m the backtracking search of the original problern. We show that this figure of m~­ it can be computed in time comparable to that _of finding a single solution to an easy problern. (For details regard­ ing the process of oonstraint-deletion see [2).)

B. Definitionsand Noml!nclature

Deftnltlon 1 ([5]): An ordered constralnt grapb is a con­ straint graph in which the nodes are linearly ordered to reflect the sequence of variable assignments executed ~ the backtrack search algorithm. The widtb of a node 1S the number of arcs that leads from that node to previous nodes the widtb of an ordering is the maximum width of all 'nodes, and the widtb of a grapb is the minimum width of all the orderings of that graph.

Figure 1 presents three possible orderings of a oonstraint graph. The width of node C in the frrst order­ ing (from the left) is 2, while in the second ordering it is 1. The width of the frrst ordering is 2 while that of the second is 1. The width of the oonstraint graph is, there­ fore, 1. Freuder provided an effici.ent algorithm for find­ ing both the width of a graph and the ordering corresponding to this width. He further showed that a oonstraint graph is a tree iff it is of width 1.

Montanari [10) and Mackworth [8] have intro­ duced two kinds of local oonsistencies among oonstraints named arc conslstency and patb conslstency. Their de­ finitions assume that the graph is directed, i.e., each symmetric oonstraint is represented by two directed arcs.

Let D 1 stand for the domain of variable V;; Ru(x,y) stands for the assertion that (x,y) is permitted by the explici.t oonstraint Ru between V1 and v 1 .

Definition 2 ([8]): Directed arc (V1, v 1 ) is arc conslstent if for any value x E D 1 there is a value y E D 1 such that Ru(x,y)

Definition 3 ([10]): A path of length m through nodes (i0,;1, ··· ,im) is patb conslstent if for any value x E Dio and y E D;,. such that R~o~,.(x,y), there is a sequence of values z1ED 11 , ··· , Zm-lED;,._ 1 suchthat

R~o~,.may also be the universal relation e.g., permitting all possible pairs.

A constraint graph is arc (path) consistent if each of its directed arcs (paths) is arc (path) oonsistent. Achieving "arc-consistency" means deleting certain values from the domains of certain variables such that the resul­ tant graph will be arc-consistent, while still representing the same overall set of solutions. To achieve path­ oonsistency, certain pairs of values that were initially al­ lowed by the local oonstraints should be disallow~. Montanari and Mackworth have proposed polynomtat­ time algorithms for achieving arc-oonsistency and path consistency. In [9] it is shown that arc consistency can be achieved in O(ek 3 ) while path oonsistency can be achieved in O(n 3 P). n is the number of variables, k is the number of possible values, and e is the number of edges.

The following theorern is due to Freuder.

Theorem 1 [5]

• (a) lf the oonstraint graph has a width 1 (i.e. the con­ straint graph is a tree) and if it is arc oonsistent then it admits backtrack-free solutions.
• (b) lf the width of the oonstraint graph is 2 and it is also path oonsistent then it admits backtrack-free solutions.

The above theorem suggests that tree-like CSP'S (CSP's whose oonstraint graphs are trees) ~ be ~l~ed by first achieving arc oonsistency and then mstantiatmg the variables in an order which makes the graph have width 1. Since this backtrack-free instantiation tak~ O(ek) steps the whole problem can be solved in O(nk) and, therefore, tree-like CSP's are easy. The test for this property is also easily verifii!d; to check whether or not a given graph is a tree can be done by a regular O(n~ spanning tree algorithm.

It is important to note that a given CSP may have several equivalent representations, in the sense of acJ.n;llt­ ting the same set of solutions. Yet each representation may have a different oonstraint-graph, one of which may be a tree. However, testing whether a CSP has an equivalent tree representation and finding such a representation might be a very difficult task.

The second part of the theorern tempts us to COD­ elude that a width-2 oonstraint graph should admit a Backtrack-free solution after passing through a pathconsistency algorithm. In this case, however, the path consistency algorithm may add arcs to the graph and in­ crease its width beyond 2. This often happens when the algorithm deletes value-pairs from a pair of variables that were initially related by the universal constraint (having no connecting arc between them), and it is often the case that passage through a path-consistency algo­ rithm renders the constraint-graph complete. lt may happen, therefore, that no advantage could be taken of the fact that a CSP possesses a width-2 constraint graph if it is not already path consistent. We are not even sure whether width-2 suffices to preclude NP-completeness.

In the following section we give weaker definitions of arc and path consistency which are also sufficient for guaranteeing backtrack-free solutions but have two ad­ vantages over those defmed by Montanari (10] and Mackworth [8):

1. They can be achieved more efficiently, and
2. They add fewer arcs to the constraint-graph, thus preserving the graph width in a !arger classes of problems.

II ALGORJTHMS FOR ACHIEVING DIRECIIONAL CONSISIENCY

A. Case ofWidth-1

In constraint-graphs which are trees, full arc­ consistency is more than what is actually required for enabling backtrack-free solutions. For example, if the constraint graph in figure 2 is ordered by (V1,V2,V3,V4), nothing is gained by making the directed arc (V3,V1) con­ sistent.

FIGURE2

To ensure backtrack-free assignment, we need only make sure that any value assigned to variable V1 will have at least one consistent value in D3· This can be achieved by making only the directed arc (V 1, V 3) consistent, regard­ less of whether (V 3 ,V1) is consistent. We therefore see that arc-consistency is required only w.r.t. a single direc­ tion, the one specified by the order in which the back­ track algorithm will later choose variables for instantia­ tions. This motivates the following definitions.

Dermltion: Given an order d on the constraint graph R,

we say that R is d-arc-consistent if all the directed edges which follow the order d are arc-consisterit.

Theorem 2:

Let d be a width-1 order of an ordered constraint-tree, T. If T is d-arc-consistent then the backtrack search along the order d is backtrack-free.

proof:

Suppose Vt.V2, ··· , V~; were already instantiated. The variable V H 1 is connected to at most one previous vari­ able (follows from the width-1 property), say V;, which was assigned the value v;. Since the directed arc (V;,Vi;+1) is along the order d, its arc-consistency implies the existence of a value vi:+1 such that the pair (v;,vi;+ 1 ) is permitted by the constraint R1(Hl)· Thus, the assign­ ment of vi:+ 1 is consistent with all previous assignments.

0

An algorithm for achieving directional arc­ consistency for any ordered constraint graph is given next (The order d =(Vt.V2, ··· ,Vn) is assumed)

DAC· d-arc-conslstenq

1. begin
2. For i=n to 1 by -1 do
3. Foreach arc (V 1 ,V;);j < i do
4. REVISE(V 1 , V;)
5. end
6. end
7. end

The algorithm REVISE(V 1 , V;), given in [8], deletes values from the domain D 1 until the directed arc (V 1 , V;) is arc-consistent.

REVISE(V 1 , V;)

1. begin
2. For each x E D 1 do
3. if there is no value y E D; s.t. R 1 ;(x,y) then
4. delete x from D 1
5. end

1. end

To prove that the algorithm achieves d-arc­ consistency we have to show that upon termination, any arc (V 1 ,V;) along d (j < i), is arc-consistent. The algo­ rithm revises each d-directed arc once. It remains to be shown that the consistency of an already processed arc is not violated by the processing of coming arcs. Let arc (V 1 , V;) (j < i) be an arc just processed by REVISE(V 1 ,V 1 ). To destroy the consistency of (V 1 ,V1) some values sbould be deleted from the domain of V1 during the continuation of the algorithm. However, ac­ cording to the order by which REVISE is performed from this point on, only lower indcxed variables may bave their set of values updated. Therefore, once a directed arc is made arc-consistent its consistency will not be violated.

The algorithm AC-3 [8] that achieves full arc-consistency is given for referenc::e:

AC-3

• l.begin

2. Q- { (V;,Vj) I (V;,Vj) E arc:s, i * j}

3. while Q is not empty do

4.

5.

select and delete arc (V1, V".) from Q

REVISE(V1,V".)

1. if REVISE(VbV".) caused any change then

7. Q- Q U {(V;,Vi;)I(V1,Vk) E arc:s, i 'i k,m}

7. end

8. end

The complexity of AC-3, achieving full arc-consistency, is O(ek 3 ). By com~, the directional arc-consistency algorithm takes ek steps since the REVISE algorithm, taking 1 2 tests, is applied to every arc cxactly onc::e. It is also optimal, because even to verify directional arc­ consistency each arc sbould be inspected onc::e, and that takes 1 2 tests. Note that wben the constraint grapb is a tree, the complexity of the directional arc-consistency al­ gorithm is O(nk~.

Theorem 3:

A tree-li.ke CSP can be solved in O(nk~ steps and this is optimal.

proof:

Given that we know that the constraint grapb is a tree, finding an orderthat will render it of width-1 takes O(n) steps. A width-1 tree-CSP can be made d-arc-consistent in n·k 2 steps, using the DAC algorithm. The backtrack­ free solution on the resultant tree is found in O(nk). Fmding a solution to tree-li.ke CSP's takes, therefore, O(nk) + O(nk~ + O(n) = O(nk~. This complexity is also optimal sinc::e any algorithm for solving a tree-li.ke problern must cxamine each constraint at least onc::e, and each such examination may take in the worst case 1 2 ( especially wben no solution exist and the constraints permit very few pain of values).

0

Interestingly, if we apply DAC w.r.t. order d and then DAC w.r.t. the reverse order we get a full arc­ consistency for trees. We can, _ therefore, achieve full arc-consistency on trees in O(nk~. Algorithm AC-3, on the other band, can be sbown to have a worst case per­ formanc::e on trees of O(nk 3 ). On general graphs, bowev­ er, the (full) arc-consistency algorithm cannot be im­ proved, and the AC-3 algorithm is optimal (see [2]) .

Retuming to our primary aim of studying easy problems, we now sbow bow advic::e can be generated for solving a difficult CSP using a relaxed tree-li.ke approxi­ mation. Suppose that we want to solve an n variables CSP using a backtrack procedure with V 1> V 2, ··· , V" as the order of instantiation. Let V1 be the variable to in­ stantiate next, with v 1 1ov 12 , ··· , vik the possible candi­ date values. To minimize backtracking we should fJISt try values which are li.kely to Iead to a consistent solution but, sinc::e this li.kelihood is not known in advanc::e, we may estimate it, instead, by counting the number of con­ sistent solutions that each candidate admits in some re­ laxed problem. We generate a relaxed tree-li.ke problern by deleting some of the explicit constraints given, then count the number of consistent solutions containing each of the possible k assignments, and finally use these counts as a figure of merit for scheduling the various as­ signments. In the following we sbow bow the counting of consistent solutions can be imbedded within the d­ arc-consistency algorithm, DAC, on trees.

Any width-1 order, d, on a constraint tree deter­ mines a directed tree in which a parent always precedes its children in d ( arcs are directed from the parent to its children). Let N(v11) stands for the number of solutions in the subtree rooted at v 1 , consistent with the assign­ ment of v11 to v 1 · It can be sbown that N(.) satisfies the following recurrenc::e:

From this recurrence it is clear that the computation of N(v11) may follow the exact same steps as in DAC; simul­ taneously with testing that a given value v 1 t> is consistent with each of its children nodes, we simply transfer from each child of v 1 to v11 the sum total of the counts comput­ ed for the child's values that are consistent with v 11 · The overall value of N(v11) will be computed later on by mul­ tiplying together the summations obtained from each of the children. Thus, counting the number of solutions in a tree with n variables takes O(nk~, the same as establisb­ ing directional arc-consistency.

B. Ca.se of Width-2

Order information can also facilitate backtrack­ free search on width-2 problems by making path­ consistency algorithms directional.

Montanari bad sbown that if a network of con­ straints is consistent w.r.t. all paths of length 2 (in the complete network) then it is path-consistent. Similarly we will sbow that directional path-consistency w.r.t. length-2

paths is sufficient to obtain a backtrack-free search on a width-2 problems.

Def"mitlon: A constraint graph, R, ordered w.r.t. order d = (Vl>V2, ··· , V"), is d-path-consistent if for cvery pair of values (x,y), nV1 and yEV 1 s.t. Rij(x,y) and i<j, there exist a value zEV1,1c>j s.t R;t(x,z) and R~: 1 (z,y) for every 1c > iJ.

Theorem 4:

Let d be a width-2 order of an ordered constraint graph. If R is directional arc and path-consistent w.r.t. d then it is backtrack-free.

proof:

To ensure that a width-2 ordered constraint graph will be backtrack-free it is required that the next variable tobe instantiated will have values that are consistent with pre­ vious chosen values. Suppose V1oV2, ··· , V~: were al­ ready instantiated. The variable VA:+ 1 is connected to at most two previous variables (follows from the width-2 property). If it is connected to V1 and v 1 , iJ, < lc, then directional path consistency implies that for any assign­ ment of values to V1, v 1 there exists a consistent assign­ ment for VA:+ 1· If VA:+1 is connected to one previous vari­ able, then directional arc-consistency ensures the cx­ istence of a consistent assignment.

0

An algorithm for achieving directional path­ consistency on any ordered graph will have to manage not only the changes made to the constraints but also the changes made to the graph, i.e., the arcs which are ad­ ded to it. To describe the algorithm we use a representa­ tion in which a constraint Rii is given by a matrix whose rows and columns correspond to the values of the two variables, and the entries are 0, and 1 for disallowed and allowed pairs, respectively. The matrix Ru whose off­ diagonal values are 0, represents the set of values per­ mitted for variable V 1 · Two operation on relations are needed: lntersection and Composition.

Intersedion: If two constraints, R 'iJ and R " 11 should hold simultaneously, then their intersection R11 is written: RiJ = R'11 & R"ii· and the entries in the corresponding matrices combine, term by term, by a logical A.

Compositlon: Suppose relation R 12 holds between V1 and V 2 and R 23 between V2 and V3 then the induced relation transmitted by V2 is the composite relation R13 and it is defmed by the matrix multiplication

Given a network of constraints R = (V ,E) and an order d = (V1,V2, ... , V"), we next describe an algo­ rithm which achieves path-consistency w.r.t. this order.

DPC-d-path-collllstency

Step (2a) is the equivalent of the REVISE(i,lc) pro­ cedure, and it pedorms the directional arc-consistency. Step (2b) updates the constraints between pairs of vari­ ables transmitted by a third variable which is higher in the order d. If V1, v1, i J . < 1c are not connected to V t then the relation between the ftnt two variables is not af­ fected by V1 at all. If only one variable, V 1 , is connected to V~:, the effect of V1 on the constraint (V 1 , v 1 ) will be computed by step (2a) of the algorithm. The only time a variable V~: affects the constraints between pairs of ear­ lier variables is if it is connected to both. It is in this case only that a new arc may be added to the graph.

The complexity of the directional-path-consistency algorithm is O(n 3 1c 3 ). For variable V 1 the number of times the inner loop, (2b), is executed in at most (i-1) 2 12 (the number of different pairs less then i), and each step is of order lc 3 . The computation of loop (2a) is completely dominated by the computation of (2b), and can be ig­ nored. Therefore, the overall complexity is

Applying directional-path-consistency to a width-2 graph may increase its width and therefore, does not guarantee backtrack-free solutions. Consequently, it is useful to defme the following subclass of width-2 CSP problems.

Definition: A constraint graph is reguln width-1 if there exists a width-2 ordering of the graph which remains width-2 after applying d-path-consistency, DPC.

A ring constitutes an example of a regular width-2 graph. Figure 3 shows an ordering of a ring's ~es and the graph resulting from applying the DPC algonthm to the ring. Both graphs are of width-2.

Theorem 5:

A regular width-2 CSP can be solved in O(n 3 k 3 ).

Proof:

Regular width-2 problern can be solved by first applying the DPC algorithm and then performing a backtrack-free search on the resulting graph. The fmt takes O(n 3 k 3 ) steps and the seamd O(ek) steps.

D

The main problern with the preceding approach is whether a regular width-2 CSP can be recognized from the properties of its constraint graph. One promising ap­ proach is to identify nonseparable romponents of the graph and aU its separation vertices [4).

definition: A connected graph G(V ,E) is said to have a separation vertex v if there exist vertices a and b, such that aU the paths connecting a and b pass through v. A graph wbich has a separation vertex is called separable, and one wbich has none is called nonseparable.

An O(!EI) algorithm for finding aU the nonseparable romponents and the separation vertices is given in [4). It is also shown that the connectivity structure between the nonseparable romponents and the separation vertices, has a tree structure.

The following points can be made:

1. Given any ordered constraint graph in wbich the separation vertices and the nonseparable rom­ ponents are identified, the directi~al. path­ consistency algorithm adds arcs only wtthin each romponent.
2. Let R be a graph and SR be the tree in wbich the nonseparable romponents C1,C2, ·.. ,C, and the separating vertices V1,V2, ···· V 1 are represented by nodes. A width-1 orderin~ of RS dictat~ a partial order on R,ds, in wbich each separating vertex precede aU the vertices in its children rom­ ponents of SR. 1t can be shown that if there exist a d 3 ordering on R such that each nonseparable romponent is regular-width-2 then the total order­ ing is regular width-2.

As a corollary of these two points we oonclude that a tree of simple rings is regular width-2.

ID SUMMARY AND CONCLUSIONS

Tbis paper examines the process of harnessing easy problems to help in the solution of ~plex constraint-satisfaction problems. Of the three mam steps involved in tbis process -- simplification, solution, and advice generation -- we ooncentrated on the following:

1. The simplification part: we have devised crite~a for recognizing easy problems based on therr underlying constraint graphs. The characteristics that meet these criteria can be used as goals for simplifying romplex problems by deleting some of their constraints. The introduction of directional­ ity into the notions of arc and path consistency en­ able us to extend the class of recognizable easy problems beyond trees, to include regular width-2 problems.
2. The solution part: using directionality we were able to devise improved algorithms for solving simplified problems and to demoostrate their op­ timality. In particular, it is shown that tree­ structured problems can be solved in O(nk~ steps, and regular width-2 problems in O(n 3 k 3 ) steps.
3. The advice generation part: we have demonstrated a simple method of extracting advice from easy problems to help a backtracking algorithm decide between pending options of value assignments. The method involves approximating the remaining part of a constraint-satisfaction task by a tree­ structured problem, and counting the number of solutions consistent with each pending assignment. These counts can be obtained efficiently and can be used as figures of merit to rate the promise of­ fered by each option.

In experiments, fully reported in [2], we rompared the performance of a regular backtrack algorithm (RBf) with Advised Backtrack (ABT) on a set of randomly generated CSP problems. Initial results showed that the quality of the advice generated on the basis of a full spanning tree was sufficient to cut down substantially the number of backtrackings, typically from about 50 to 0-3. In many cases, however, the number of consistency checks required for generating tbis advice made the overall computational work bigher then that of RBT. We interpreted tbis result to mean that the advi~ g~nera~ed was too precise in the sense that further slDlplification should be attempted to cut down the work spent on ad­ vice generation. For that reason we experimented with advice generated by partially developed trees, namely, only a limited number, l, of nodes were spanned by the advising tree. The parameter l governs the strength of the advice, l=l, ... ,n. Figure 4 shows the performance of AHf as a function of l on a typical problem. The two criteria by wbich performance was judged were the number of backtracldnp performed and the number of conslstency checks i.e the nurober of times any two values were tested for consistency w.r.t. some con­ straint. For comparison, the results for RBr are shown at the point I= 1 (by triangle points). The numbers label­ ing points on the graph ind.icate the amount of backtrack­ ings. Typically the amount of backtracking was consider­ ably smaller in ABf then in RBr even for weak advice, however the total work invested in full advise (using all nodes in the tree) was not always worthwhile and a weaker advice was sufficient. The d.ip in the curve represents an optimal balance between the effort spent in generating advice and the amount of backtracking it saves.

Although the primary discussion in this paper has focused on guiding the selection of values within a gi.ven variable, the properties of tree-structured networks can also be exploited to optimize the ordering of variables. One such scheme, which promises unusual possibilities, is based on the following observation: H, in the oourse of a backtrack search, we remove from the constraint graph the nodes corresponding to already instantiated variables and fmd that the remaining subgraph is a tree, then the rest of the search can be completed in linear time (e.g., using the DAC algorithm of Section ß). Consequently, the aim of ordering the variables should be to instantiate, as quickly as possible, a set of variables that cut all cy­ cles in the network. lndeed, if we identify m variables which form such a cycle-cutset, the entire CSP can be solved in at most O(k"'nk~ steps; we simply solve the trees resulting from each of the k"' possible instantiations of the variables in the cutset. Thus, in networks where the ratio n/m is large, enormous savings can be realized using simple heuristics for selecting near-minimal cycle­ cutsets.