Generalizing Inconsistency Learning for Constraint Satisfaction

1 Introduction

1.1 Overview

Constraint satisfaction problems ( CSPs) involve finding values for problem variables subject to constraints on which combinations of values are allowed. They have many applications in artificial intelligence, ranging from design to diagnosis, language understanding to machine vision. A solution is an assignment of a value to each variable such that all the constraints are simultaneously satisfied. A constraint on a subset of k variables can be regarded as a set of k-tuples of values, where each k­ tuple represents an inconsistent choice of values for those variables.

In addition to the inconsistencies in the constraints that are given to define the problem, there are implicit inconsistencies, that become apparent during the search for a solution. In general, a k-tuple of values is incon­ sistent, or a nogood 1 , if it does not appear in any solution. Solution methods are commonly based on back­ track search. When a failure is encountered during search, there are "learning" methods that can identify and record an individual nogood "responsible" for the failure. While the inference methods employed to ex­ tract the nogoods may be relatively sophisticated, the actual learning tends to be rather primitive. There is little if any of the generalized learning from examples or background knowledge that has been employed so suc­ cessfully in the machine learning community. (There are other interesting applications of learning methods to constraint satisfaction, to synthesize heuristics or al­ gorithms, but we focus here on learning additional con­ straint information.)

*This material is based on work supported by the National Science Foundation under Grant No. IRI-9207633

I We only consider global nogoods, whose inconsistency does not depend on a context of other choices.

As a simple, motivating example of generalized learn­ ing consider five vertices, A, B, C, D and E in a coloring problem with a great many vertices and three colors: red, blue and green. Suppose that there are no edges among these five, but that each of them is connected to vertex F. A person trying to color the vertices in lexical or­ der would observe that while there are no edges between vertices A, B and C, nevertheless there is an implied constraint that if A is red and B is blue, then C cannot be green. A CSP search algorithm could make the same observation. A standard CSP learning algorithm could learn and remember that the triple of values (red, blue, green) for the triple of variables (A, B, C) is inconsis­ tent. A person, however, would be likely to generalize that learning:

• A person could recognize that D and E cannot be green either, when A is red and B blue.
• When encountering a similar configuration among other variables elsewhere in the problem, the per­ son could recognize that this situation had been en­ countered before.
• A person would understand that the specific colors involved are not critical, they could be black, orange and brown.
• A person might even observe that a similar situation exists when four colors are available (or n colors).

In this paper we introduce a basic form of general­ ized learning. The principle behind it is this: when a subproblem "learning environment" can be mapped onto another subproblem encountered later in the search with an "inconsistency preserving mapping", then the original learned nogood generalizes to the new situation.

Of course, finding such mappings could easily become more computationally expensive than solving the orig­ inal problem. To apply the general insight we need to identify learning contexts that are general enough to be interesting, but restricted enough to make generalization cost effective. We identify a basic context that meets these criteria (which encompasses, in particular, the first two examples of generalization listed above), and then begin to relax the restrictions.

We validate the utility of generalization in two spe­ cific contexts. We start by considering "coloring" prob­ lems in which the single permitted constraint is inequal­ ity. These "constraints of difference" [Regin, 1994] are of considerable interest, and in fact model basic coloring, scheduling and resource allocation problems. Next we add the ordering constraints: <, >, ~' ~. =.

1.2 Relation to Previous Work

There is a stream of work on CSP nogood learning (see [Frost and Dechter, 1994; Schiex and Verfaillie, 1993] for recent examples) with connections to truth main­ tenance (e.g. [Smith and Kelleher, 1988]). There is a stream of work on CSP symmetry (see [Ellman, 1993; Puget, 1993] for recent examples), which extends at least as far back as ([Fillmore and Williamson, 1974]). One of the current authors did some tentative work earlier on subgraph isomorphism in constraint graphs [Freuder, 1984]. Benhamou [Benhamou, 1994] uses symmetrical values and search branches to improve CSP algorithms.

The current work brings these two streams together, using isomorphic mappings to generalize learned no­ goods. We find local mappings, dynamically during search, between subproblems, in which some of the vari­ ables have been instantiated to specific value choices. The pruning done by the basic form of generalization that we implement would be subsumed by some forms of look-ahead (though not by forward checking alone) [Har­ alick and Elliott, 1980]. However, generalization accom­ plishes the pruning in a more targeted manner; our ex­ perimental results show that generalization can be more cost effective than the additional look-ahead.

2 Principle

Generalization will be based on inconsistency preserv­ ing mappings. A mapping takes a value/variable pair, e.g. red/ A, value red for variable A, into another value/variable pair. An inconsistency preserving map­ ping, f, from a source subproblem, S, to a destination subproblem, D, is a function from the value/variable pairs of S into the value/variable pairs of D, such that if any v/V is inconsistent with any u/U inS, then f(v/V) will be inconsistent with f(u/U) in D. Clearly, inconsistency preserving mappings can permit us to generalize the ap­ plication of learned nogoods by mapping a nogood ac­ quired in one subproblem into a situation encountered in another subproblem.

Just as clearly, looking for these mappings could eas­ ily be computationally counterproductive. We can focus our attention along a number of axes: semantic, syntac­ tic and pragmatic. We choose a very restricted starting point on each of these axes, to establish a basic model of generalization learning, and then begin to move out­ ward. We begin with with value-identity mappings such that a value/variable pair, v/V, can only map into a pair, v /U, involving the same value. We assume that in a given problem all variable domains are the same, and all the given constraints are the same, and binary (involves only two variables). We use the fundamental "deadend learning" context to establish the structure of the source subproblem, and the basic backtrack search structure to propose destination subproblems.

Instances of the prototypical source and destination problems, with an inconsistency preserving mapping be­ tween them, are shown in Figure 1. The source sub­ problem consists of a hub variable and k spoke vari­ ables. Each spoke variable domain has been reduced to a single value; all these values are deemed mutually consistent by the given problem constraints. Every value in the hub variable domain is inconsistent with at least one of the spoke variable values. This is the basic CSP deadend learning situation, in which we record that the spoke variable values (or some subset of them) form a learned nogood. 2 Here, for simplicity, we assume that the hub variable in the destination problem corresponds to the current variable in the search, the one for which we are about to choose an instantiation. The values from k-1 of the spoke variables in the source map into k-1 previously chosen values in the destination. The kth source spoke variable corresponds to a "future" unin­ stantiated variable at the destination. Applying the dis­ covered generalization is done by pruning the value in the source subproblem corresponding to the value at the kth spoke variable. (Note that there may be additional "past", instantiated variables, or future, uninstantiated ones that constrain the current variable. The other fu­ ture variables offer additional opportunities for general­ ization pruning.)

Given the assumptions that we have made here, it is easy to see that this is an inconsistency preserving mapping, and that to discover it all we have to do is observe that k-1 of the source spoke values appear in instantiated variables that share a constraint with the current variable in the destination subproblem. (For ex­ ample, there may be constraints between spoke variables in the source, but they are irrelvant now since the spoke variable values are all mutually consistent.) Discovering source problems requires essentially the same effort as deadend learning; the effort expended in looking for an opportunity to generalize is strictly circumscribed.

In the next sections we will implement and evaluate this basic generalization mechanism. We start by consid­ ering "coloring" problems in which the single permitted constraint is inequality. These problems precisely fit the basic model we have just introduced. Next we add the ordering constraints. This motivates us to relax the re­ strictions of the basic model. We observe that mappings will be inconsistency preserving as before as long as the constraints in the destination are more restrictive than the corresponding constraints in the source (e.g. "<" is more restrictive than "~"). We also move beyond value­ identity mapping in this context.

2 In more advanced learning the deadend can consist of a subproblem rather than a single variable. This is beyond the scope of the present paper; however, we believe we can generalize such advanced learning, and avoid combinatorial explosion by limiting the size of the failed subproblem.

3 N ogood Learning and Generalization

Generalization can, of course, be used with a variety of CSP algorithms. In the present paper, a forward check­ ing engine is used to evaluate the effect of adding gen­ eralization. As part of the overall comparison nogood learning without generalization [Dechter, 199Qj [Schiex and Verfaillie, 1993] is also considered.

We first describe our nogood learning procedure, and then discuss the ways in which learning based on gen­ eralized nogoods differs from it. When nogood learning is used with forward checking, preclusion based on k-ary nogoods is performed in tandem with ordinary preclu­ sion (Figure 2). (In "ordinary preclusion", values in fu­ ture (uninstantiated) domains that are inconsistent with the latest value chosen for instantiation are discarded, or precluded.) For fixed order search, k-ary nogoods are ordered by their variables in accordance with the search order . Each nogood is associated with the penultimate variable in its ordered set. At this point in search, a match with previous assignments, plus the value cur­ rently being considered for the current variable, allows preclusion of the domain of the last variable in the no­ good.

Two variants of nogood learning will be considered. One is based on the set of variables that are adjacent to one that has been wiped out. This is the procedure that [Frost and Dechter, 1994] call graph-based nogood learning. The other is based on the preclusion set, i.e., the variables whose assignments led to deletions of values in the domain that has been wiped out. This is called the jump-back set by [Frost and Dechter, 1994] and the killer set by [Schiex and Verfaillie, 1993]. In neither case is the nogood set minimalized. (But for coloring prob­ lems the preclusion set is a minimal nogood.) Nogoods associated with one variable are checked in order of the most recently discovered. (A few tests were made with the reverse order, with similar results.)

Search: Choose an uninstantiated variable v; for each value a in domain d; if there is a nogood associated with v; perform k-ary preclusion if no wipeout, perform ordinary preclusion if wipeout occurs set up nogood associated with next to last variable in preclusion set K-ary Preclusion: for each nogood associated with v; test whether current assignments to nogood variables 1 to k - 1 equal corresponding nogood values if nogood matches current assignments delete nogood value from domain of kth variable in nogood

Figure 2: Scheme for Nogood Learning.

In the algorithms discussed here nogood building is based solely on ordinary preclusion. Thus, results of preclusion due to k-ary nogoods are not used. This would have required further elaborations to search for the relevant variables and to combine them properly. Since the nogoods will be larger than ones based on ordi­ nary preclusion, they are probably not as useful. This is because the probability that a nogood matches a current partial assignment decreases as the size of the no good in­ creases. Some overhead is incurred because the program has to check that domain wipeout did not involve k-ary nogoods.

The procedure for building generalized nogoods is sim­ ilar to that used for ordinary nogood learning (Figure 3). Nogoods are built following wipeout of a domain. But in this case the nogood consists of a set of disallowed val­ ues (one per domain) together with the conditions under which they are disallowed. In the general case these con­ ditions are: the type of constraint and the original set of values in the domain that was wiped out. If a particu­ lar condition is consistent for the entire problem, then it does not need to be specified. For example, if the original domains of the problem are identical, then a nogood will hold for any subproblem having the necessary pattern of constraints. If both the domains and the constraints are constant for a problem, then only the values need to be specified.

For coloring problems, inconsistency mapping was done so that the hub variables were the uninstantiated (i .e., future) variables adjacent to the variable currently considered for instantiation. In other words, generaliza­ tion was based on a look-ahead by one procedure. In coloring problems, if the current variable itself is used as the hub, then preclusion based on nogoods is completely redundant with ordinary preclusion. This is because no­ good preclusion will apply only in those cases where the domain of the current variable has been reduced to the one value that can be precluded from the adjacent do­ mains. But, then, the value in the current domain will also preclude the same values from the adjacent domains, with the same (total) number of constraint checks. Since look-ahead by one proved to be a successful strategy, it was used with all sets of problems.

Search:

Choose an uninstantiated variable v; for each value a in domain d; if there is a nogood associated with v; perform 'adjacent' k-ary preclusion if no wipeout, perform ordinary preclusion if wipeout occurs set up nogood associated with next to last variable in preclusion set

Adjacent K-ary Preclusion: For each variable Vj (of sufficient degree) adjacent to v; perform generalized k-ary preclusion

Generalized K-ary Preclusion:

for each generalized nogood test current assignments of instantiated variables adjacent to Vj to determine applicability if k - 1 nogood values can be matched with current assignments for each uninstantiated variable adjacent to Vj delete kth nogood value from domain of that variable

Figure 3: Scheme for Generalized Nogood Learning (with look-ahead by one) .

As with ordinary nogood learning, variants based on adjacency sets and on preclusion sets were included in the tests. In connection with adjacency sets, two further cases are considered. In the first, there is no attempt to minimalize the set of nogoods and all are used in at­ tempting to preclude values. The second case involved minimalization. For nogood learning this is probablr. too expensive [Dechter, 1990; Frost and Dechter, 1994 . But, if there is only one set of generalized nogoods, as in the cases considered here, minimalization may be cost­ effective.

4 Experimental Tests

4.1 Problems Tested

Generalization in k-coloring problems is carried out as described in the previous section. If a nogood is discov­ ered during search, it can be used with any variable hav­ ing k or more adjacent variables, to delete values from some of the adjacent nodes. Of course, some procedures (those based on adjacency sets) may discover nogoods that are multisets of the k colors, and these can be gen­ eralized in the same fashion .

For problems with ordering constraints based on rela­ tional operators ( "relop" problems), no goods are discov­ ered in the same fashion as with coloring problems. For ordinary nogood learning, use of nogoods during search is also identical. However, in order to generalize prop­ erly, information about constraints must be considered in addition to nogood values. In the general case these nogoods are applied according to the mapping princi­ ples described in Section 2. This means that each con­ straint associated with a nogood value must match (by subsumption) a constraint in the subproblem being con­ sidered, and that the nogood value must not be more constraining than the current instantiation.

For example, suppose that the domains of a problem are all {1, 2, 3, 4} and that the assignment for variable v; must be greater or equal to the value of variable Vk, and the assignment for variable Vj must be equal to the value of v.~;. In this case, assigning values 3 and 4, respec­ tively, to v; and Vj results in a wipeout of the domain of v.~;. This nogood can be represented by the tuple , ((~ 3) (= 4)), whose elements can be thought of as partial Lisp expressions with the second argument unspecified. In addition to matching any subproblem with the same constraints and values, the first element of this nogood will match an assignment of 2 to a variable associated with a ~ constraint, an assignment of 3 to a variable with a > constraint, and so forth.

Clearly, the effort to find a general match in this case may be too costly. In particular, finding an adequate mapping may require backtracking when a nogood ele­ ment can be matched to more than one element in the subproblem. However, the comparison criteria can be tightened, and search effort may still be reduced with acceptable overhead. For example, the comparison can be discontinued if a nogood element does not match any of the remaining instantiations, to avoid backtracking. In addition, matches can be restricted to identity map­ ping of constraints (here, exact matches for the relational operators). And, in addition to these matching strate­ gies, targeting strategies can be used to limit the number of contexts that are checked for mapping. In sum, what generalization offers in this context is a set of opportu­ nities for nogood matching with attendant tradeoffs be­ tween search reduction and complexity of the additional computation.

4.2 Experimental Methods

Coloring problems had either three or four colors. Three­ color problems had 100 variables and an expected graph density of 0.02, 0.03 or 0.04; Four-color problems had 70 variables and an expected density of 0.09. (Here, density is measured in terms of edges added to a spanning tree.) The 3-color densities span the critical region for problem complexity. In accordance with this, problem difficulty increases from 0.02 to 0.03 density, and decreases again at 0.04 density. The percentage of problems with solu­ tions at successively higher densities was 98, 12 and 0. Four-color problems were also in the critical region; 56 percent of these problems had solutions.

Relop problems had 45 variables and expected densi­ ties of 0.01 and 0.02. The percentage of problems with solutions at successively higher densities was 46 and 4.

Both types of problem were generated according to a random model for arc inclusion. Construction began with a spanning tree in which successive nodes were cho­ sen at random and connected at random to nodes already in the tree. Then each remaining edge was chosen with a probability equal to the expected density. For relop problems, the type of each constraint was chosen at ran­ dom from among the six possibilities. Fifty problems were generated for each sample.

The basic experimental comparison was with forward checking. In these experiments, each algorithm was run with a fixed variable ordering based on (maximum) de­ gree of a node in the constraint graph for the CSP. (We are currently implementing dynamic ordering by mini­ mal domain size; this should still allow improvement due to nogood learning, as [Frost and Dechter, 1994] have shown.) Forward checking with look-ahead (FC+LA-1) was also tested to determine the effect of this proce­ dure, which was used with generalized nogood testing. Look-ahead was done using distance bounded relaxation [Freuder and Wallace, 1991] with distance = 1, which was the same as the distance used with the nogood algo­ rithms. Results were also compared with two of the most powerful techniques for solving CSPs: forward check­ ing with conflict-based backjumping (FC-CBJ) [Prosser, 1993] and maintained arc consistency (MAC3) [Sabin and Freuder, 1994]. In the latter case, an AC-3-Iike pro­ cedure was used to maintain arc consistency, in order to have a measure (consistency checks) that allowed com­ parison with the other algorithms.

Note. Entries are sample means. FC+LA-1 times are for a slower implementation than the others.

For coloring problems, both ordinary and generalized nogood learning (NG and GenNG or Gen in the tables) were tested using either adjacency sets or preclusion sets ("adj" and "precl" in tables); adjacency sets were either full or minimalized when used with generalized nogoods. For relop problems, testing was done with preclusion sets only. The following types of generalization were also tested: (i) simple identity matching (GenNG-id) , (ii) identity matching of constraints (relational opera­ tors) and set/subset matching of values (GenNG-idop), (iii) set/subset matching of both operators and values. For the last two categories, a kind of minimalization was also carried out, according to the following procedure. If k-1 elements in two nogoods were identical, the kth elements were matched for operators. If both operators were in the set {>, ~} or in { <, ~}, then the element whose value was more inclusive was retained.

Three measures of performance were used : backtracks, constraint checks and total search time. The number of backtracks, i.e., the number of times the values in a do­ main were exhausted causing search to back up, is an indication of the size of the search tree. Number of con­ sistency (or constraint) checks often gives a better overall view of performance. All algorithms did some consis­ tency checking as part of the preclusion done by forward checking. Algorithms that incorporated nogood learning also checked k-ary nogoods. Algorithms that employed look-ahead also did consistency testing between values in domains of future, uninstantiated variables. N atu­ rally, k-ary constraint checks differ from ordinary con­ straint checks in the time required, and the time required to test ordinary nogoods is different from the time to test generalized nogoods. For these problems simple no­ good testing was faster than ordinary constraint check­ ing, partly because the nogoods were small and look-up operations were simpler. (Rapidity of failure when test­ ing successive nogood variables may also have been a factor.) Generalized nogood testing was more involved, since the set of variables and their order were not known in advance; hence, this operation was slower than ordi­ nary constraint checking. (These differences are most evident in the data of Table 2.)

Experiments were run on a DEC Alpha (DEC 3000 M300LX). Algorithms were coded in Common Lisp, us­ ing Lispworks by Harlequin . All solutions were tested for validity; in addition, solutions produced by the new algorithms described in this paper were compared with those produced by a version offorward checking that has been thoroughly tested in previous work. (All of these algorithms should find the same first solution to a prob­ lem if the same variable and value orderings are used.)

Note. Means for 50 problems. Backtracks and constraint checks in thousands. Times in sec. Abbreviations for al­ gorithms in text .

4.3 Results

Coloring Problems

For all problem sets, nogood learning improved on for­ ward checking alone (Figures 4-5, Tables 1-2) . In most cases generalized nogood learning was better than or­ dinary nogood learning; the only exception was for 3color problems with expected density = 0.02 (see Table 1). Comparisons involving look-ahead show that this technique may have been partly responsible for the im­ provement found with generalized nogood learning, but the latter was superior to straight look-ahead in situ­ ations in which it was also better than ordinary no­ good learning. Generalized nogood learning also out­ performed forward checking with conflict-directed back­ jumping or maintained arc consistency on most problem sets, including those in the critical complexity regions.

As would be expected, minimalizing nogoods reduced the number of constraint checks. Timing data also indicate that overall performance was improved, so that minimalization used with generalized nogood learning was cost-effective in this case. Using preclusion sets was more effective than using adjacency sets for both ordi­ nary and generalized nogood learning, and this difference was greater for the harder 4-color problems. But for gen­ eralized nogood learning, minimalization made the two almost identical with respect to search time and mea­ sured operations.

Relop Problems

For these problems, nogood learning was again supe­ rior to forward checking alone (Figure 6) . The effect of using generalized nogoods depended on the charac­ ter of the match and the use of minimalization. With pure identity matching, performance was actually worse, showing that a simple matching strategy corresponding to the one used with coloring problems was not suffi­ cient in this case. More sophisticated matching based on set/subset relations was much more successful, and performance was further improved by the minimaliza­ tion procedure. (Examination of data structures during runs confirmed that this procedure did reduce the prolif­ eration of nogoods found during search.) Although the results were not as good as those for ordinary nogood learning, they show that generalization can improve on the basic forward checking engine even for problems with a fairly complicated pattern of constraints.

The targeting strategies mentioned at the end of Sec­ tion 4.1 have not yet been implemented and these may improve performance further. In particular, a simple 'match and store' strategy, in which matching nogoods are stored in a manner similar to ordinary nogoods, may reduce the amount of redundant matching during search.

5 Conclusion

By using inference, background knowledge, and recog­ nizing structural similarities within and among prob­ lems, we can potentially leverage our learning power. We have identified a basic principle that supports gen­ eralized learning, and begun to identify specific contexts in which the principle can be profitably applied.