Automating the Construction of Patchers That Satisfy Global Constraints

1 Introduction

In this paper, we address part of the problem of compil­ ing a declarative representation of a class of problems and knowledge relevant to solving it into an efficient problem-solving system.

Example domain. We will use the domain of hou1e floorplanning to illustrate several domain-independent ideas for addressing this research problem. Floorplans are arrangements of rectangular rooms in a rectangu­ lar house space. Rooms and houses are aligned with an integer-valued grid of points in a plane. The con­ straints in Figure 1 define a particular clau of floorplan­ ning problems. The number of rooms, the dimensions of the house space, and minimum values for room lengths and widths are problem-1pecijic parameters. [Liew and Tong, 1987] has shown how to automatically construct a simple but inefficient generate-and-test algorithm that solves particular problems for a problem class such as this one. Given the length and width of the house, and n, the number of rooms, the algorithm generates n room rectangles, and then tests the candidate solution against each of the above constraints. Failure results in chrono­ logical backtracking.

Constraint incorporation. Various methods have been developed for automatically improving the effi­ ciency of a generate-and-test al~orithm [Mostow 1 1983, Tappel, 1980, Braudaway, 1988]. One of the best im­ provements is to completely incorpomte the constraints in the generator, that is, to modify the generator so that it only produces objects satisfying the constraints. When a constraint has been completely incorporated, the test corresponding to the constraint can be removed. The method described in [Braudaway, 1988] completely in­ corporates those constraints which are local to individual room generation (Cl - C4), or that can be localized to the set of rooms generated thus far (C5).

Unfortunately, the more global constraints (e.g., C6) are not readily incorporated into generators by such methods. Modifying a generator that only generates a solution part (e.g., an individual room) generally is in­ sufficient to guarantee satisfaction of a constraint on the entire solution.

The research problem. We define local constraints to be those which can be incorporated into a solution generator in such a way that the resulting generator runs in polynomial time. Global constraints are constraints that are not local. Our research is aimed at constructing an efficient procedural embedding for global constraints:

GIVEN

a set CSET of constraints on the solution; declara­ tively represented domain knowledge elucidating the constraints CSET; a constrained generator in which all constraints in CSET' CCSET have been completely incorporated;

FIND

a procedural embedding of the unincorporated con­ straints CSET - CSET' such that the resulting algo­ rithm is significantly more efficient than embedding CSET - CSET' solely as tests.

The domain knowledge is provided by a human knowl­ edge engineer, whose task we aim to simplify by only requiring that the knowledge be in a declarative form. Our method requires knowledge about the solution part hierarchy (e.g., solutions are floorplans; floorplans are houses having rooms as parts; rooms have four parame­ ters as parts: length, width, xCoord, and yCoord), solu­ tion part typing (e.g., rooms and houses are rectangles; the xCoord of a room is a coordinate; rooms and grid­ points inside rooms are space-filling units; the house and gridpoints inside the house are space units, 1 and generic knowledge (e.g., definitions of predicates such as inside; items of type "coordinate" can take on any integer value between [-maxlnt,maxlnt]).

The constrained generator is produced by the RICK knowledge compiler described in [Braudaway, 1989]; CSET - CSET' are constraints which that compiler could not completely incorporate.

In this paper, we illustrate a method that optimizes a generate-and-test floorplanner into a generate-test-and­ patch floorplanner. When a candidate solution fails to satisfy a global constraint, it is passed to a patcher, which hillclimbs its way to solutions that are increasingly better with respect to that constraint. For instance, fail­ ure to satisfy the constraint C6 means the house space contains "holes" unassigned to any room. The patcher incrementally reduces the amount of unassigned space by extending rooms.

2 Categorization of global constraints

The English statement of C6, "The rooms must com­ pletely fill the house space", seems "global" in that it appears we must simultaneously consider all the rooms to determine whether it is satisfied. However, when we express the constraint more formally: 2

1 The utility of this kind of domain knowledge will become clear in section 3.

VF ,P {floorplan(F) 1\ gridpoint(P,F) 1\ inside(P,house,F)(C6) =} 3R (room(R,F) 1\ inside(P,R,F}]}

we notice that the constraint is only existentially (and not universally) quantified over rooms R. Ignoring Cl through C5 would allow C6 to be satisfied by a single room that covered the entire house. What is more ac­ curately called a "global" constraint is the conjunction: C7 ¢:> C3 1\ C5 1\ C6. Together, these three constraints define a covering relationship that must be satisfied. C6, by itself, could also be called "global" with respect to a constrained generator in which C3 and C5 have already been incorporated.

One of our major long-term goals is to construct global constraint schema· or normal forms for a diverse range of global constraints. Such constraint schemas may con­ tain multiple components (e.g., Figure 2 contains three components). A successful match of a constraint schema S to a set of constraints occurs when each schema com­ ponent matches a constraint in the set. The conjunction of the matching constraints (e.g., C7) is "a global con­ straint of type S". Constraint schemas S can have asso­ ciated knowledge for helping to construct a patcher that eventually produces a solution that satisfies a constraint of typeS.

In this paper, we focus on global constraints that can be viewed as constraints on global resources. In par­ ticular, certain parts of our approach are currently re­ stricted to fit two generic global constraint schemas: quota-meeting constraints and covering constraints.

Quota-meeting constraints. Quota-meeting con­ straints have the following schema:

where quota is an integer, quota~O, t is a given unit type, and the number of units of type t is always less than or equal to quota. Quota-meeting constraints re­ quire that the solution contain exactly quota units of type t. C7 is an example of a constraint from which we can construct another constraint CS such that CS and C7 are logically equivalent and CS matches QNF (Quota Normal Form); for instance, CS could be "the number of gridpoints in the filled part of the house must equal the total number of grid points in the house."

Covering constraints. Satisfying a covering con­ straint involves constructing an assignment:

Assign units of type TsF to units of type T 5 so that the units of type Ts are covered.

We will call units of type TsF space-filling units, and units of type Ts space units. Covering constraints have the normal form given in Figure 2, consisting of the conjunction of three constraints. The number of space units and space-filling units is finite, all candidate solu­ tions share the same set of space units, and the space­ filling units (and how they are assigned) varies, depend­ ing on the solution. The predicate corresponds defines the . assignment. Examples of constraints that could be matched to SNF (Space-filling Normal Form) include: "All available jobs must be assigned a person to carry them out"; "All available time slots must be assigned a job"; etc.

2 We will use the notational convention of capitalizing vari­ able names.

C7 can be written in SNF form because C3, C5, and C6 can be shown to match II, I, and III, respectively. Af­ ter being re-written in SNF, C7 is a covering constraint where the space units are the gridpoints in the house rectangle, and the space-filling units are the gridpoints in all the rooms. The assignment is the obvious one: if a room gridpoint is "on top of" a house gridpoint, the two gridpoints correspond.

Constraint schemas, logically equivalent con­ straints, and reformulation procedures. Given any constraint C,. of type SNF, we can construct a logically equivalent constraint C, of type QNF. This is because SNF-II and SNF-III together imply that the total num­ ber of space units and the total number of space-filling units must be the same (call it n); if C,. is satisfied, then all the space units have been covered by space-filling units and therefore the number of covered space units is n. Thus by defining C11 to be "The number of covered space units equals the total number of space units", C, is implied by C,. and C, matches the QNF schema. Con­ versely, if C, is true, then all the space units have been covered, and covering constraint C,. is satisfied.

Thus we can associate with schema SNF a procedure that takes a constraint matching SNF and constructs a logically equivalent constraint matching QNF. The use of such procedures will be demonstrated in the next section.

3 Incremental Construction of a Patcher

Our approach to the research problem is to compile the unincorporated constraints into a knowledge-based solu­ tion patcher. The key steps in our approach are now outlined (see also [Voigt, 1988]). We have begun im­ plementing this method in a program called MENDER. We illustrate the steps of our approach on the constraint C6, and presume the existence of a constrained generator in which constraints Cl through C5 have already been completely incorporated.

STEP 1. Extract an evaluation function from the global constraint. Constraints per se are predi­ cates; when they are evaluatable, they are either "satis­ fied" or "not satisfied". A key to making effective use of a global constraint is to be able to recognize the degree to which it has been satisfied (e.g., to what degree has the house space been filled by rooms?). Thus we want to convert a predicate into an evaluation function, which can be used to guide a hillclimbing patcher.

Some constraint schemas (e.g., QNF) contain proce­ dures for creating an evaluation function corresponding to a constraint (or set of constraints) that fit the schema. However, we may discover that a constraint C,. is ex­ pressed in a form that does match a schema S (e.g., SNF), but S does not contain a procedure for construct­ ing an evaluation function.

However, S may have an associated procedure for con­ structing a constraint C, that is logically equivalent to C,. but which matches S', a constraint schema that does contain a procedure for constructing an evaluation func­ tion f measuring improvement with respect to satisfac­ tion of c,. The important observation is that, iff takes on its maximum value only in states when C11 is true, then f will also aid in hillclimbing to a solution that completely satisfies C,., because C, and C,. are logically equivalent. The purpose of the patcher, is to eventually produce a state in which C,. is completely true. Thus we don't insist that C,. necessarily become "more and more true" as f increases its value, so long as C,. is completely true when f takes on its maximum value.

We will now illustrate these points by matching con­ straints to the SNF schema, re-expressing them in QNF, and then constructing an evaluation function.

He-expressing constraints to match SNF. Because of the large number of possible matches, syntactic match­ ing is used to suggest plausible constraint/constraint schema component matches in a cost-effective manner. The matching leaves in the parse trees of these plausible matches correspond to theorems which are then proved to verify that the constraint fits the constraint schema (see, e.g., Figure 3).

We illustrate this process by matching constraint C6 against the components of the SNF schema. In general, schema components can contain special cases. If the prototypical case fails to match, the special cases are tried. C6 does not match any of the SNF prototypical components. However, it does match a special case of SNF-III (see Figure 3):

where the space units and space filling units are drawn from the same set of objects, and corresponds(X,Y,S) is equals(X,Y).

The fit of C6 to SNF-III' is then confirmed by proving the three theorems suggested by the match, using the domain knowledge indicating that house gridpoints are space units and room gridpoints are apace-filling units.

Since one component of SNF has been successfully matched, the search for matches next tries to find do­ main constraints to match the remaining components. It finds that C3 matches SNF-II and C5 matches SNF-I.

T2. gridpoint(P,F) f\ inside(P,house,F) => spaceUnit(P,F)

T.3 3R [room(R,F) /\ inside(R,P,F)] => spaceFillingUnit(P,F)

Figure 4: Converting predicates into types with cardi­ nality

Matching has thus constructed constraint C7 (the con­ junction of C3, C5, C6) and shown that it fits the SNF schema.

He-expressing SNF constraints to match QNF. Our method next re-expresses C7 to match QNF using the following pre-compiled correspondence between SNF and QNF:

setOf(spaceFillingUnit(X,S)) unitsOIType(T,S) ca.rdinality(setOf(spaceUnit(Y,S))) quota

The re-expression is done by converting predicate defini­ tions into type definitions and then finding an expression for the cardinality of these types, as illustrated in Figure 4. The first half of re-expressing constraint C7 in QNF is thus given by:

ca.rdinality(unitsOIType( t4,s ))

= cardinality(setOf(spaceFillingUnit(X,s)))

= l::ReroonuinJioorpr .. ,. 1 length(R,f) X width(R,f)

In a similar, tightly focused manner, we derive the other half (not shown here):

quota = cardinality( set Of( space Unit(Y ,s))) = length(house,f) x width(house,f)

Finally, the QNF schema contains the information that the desired evaluation function f(S) is given by f(S) = cardinality(unitsOIType(t4,S)). The derived evaluation function for measuring progress in satisfying C7 is "the number of gridpoints in the filled part of the house":

STEP 2. Eliminate <parameter,direction> pairs that do not immediately improve a solution with respect to the evaluation function. We as­ sume the patcher eventually constructed by this method will make patching move6 that vary only one parame­ ter value at a time, either increasing or decreasing its value by some quantity. This patcher will hillclimb, thus requiring repeated improvement of the solution with re­ spect to the evaluation function. We could easily con­ struct an "unintelligent" patcher which simply allows any parameter to be varied, in any direction, by any amount. In the ftoorplanning example, these parame­ ters and directions are:

±~xCoord(R), ±~yCoord(R), ±~length(R), ±~width(R)

Such a patcher wastes time repeatedly determining that most patching moves do not improve the solution.

Fortunately, in many cases, we can prove (at compile time) that changing certain parameters in certain direc­ tions (e.g. increasing) never (immediately) improves the solution. The "theorems" we would like to prove take a very restricted form:

VS [state(S) ::? f(S) ::; f(patch(S ,Par))]

where patch(S,Par) is the result of applying the patcher to parameter Par in state S. Where we can prove such theorems, we achieve a compile time speed-up by sim­ ply not including these patching moves in the patcher. The number of such prunable "silly parameter changes" tends to increase if we assume that certain local problem constraints (i.e. the ones that can be fully incorporated by other methods, as, for example, in [Braudaway, 1988)) are true before the patching move and must remain true after the patching move.

For example, suppose we assume that constraints Cl through C5 must hold before and after the patching move. We can then prove that the following patching moves will not (immediately) improve the solution:

±~xCoord(R), ±~yCoord(R), -~length(R), -~width(R)

Moving a room l(by changing either its x or y coor­ dinates) will keep fixed the amount of the house that is filled, since the room is not allowed to overlap any other rooms, or be placed outside the house. Shrink­ ing a room (by decreasing either its length or its width) will decrease the amount of the house that is filled. After constructing proofs that reflect these observations (based on the definitions of the predicates), the incorporation method constrains the patcher to the only moves left, +Alength(R) and +Awidth(R).

STEP 3. Re-express the evaluation function in relative and local terms. We can re-express the eval­ uation function f for a patched solution, patch(S,Par), as:

where Af is the improvement due to the patch. Rewrit­ ing this, we have:

The value of Af for a length-increasing patch of room R is derived to be:

~f(F ,patch(F ,length(R,F))) = width(R,F) X ~lengthl(R,F)

We compute Af for each possible patching move. In this manner, we can evaluate potential patches without having to execute them. This will be needed for doing greedy patching, which is described in STEP 5.

STEP 4. Construct a patcher in which the lo­ cal constraints have been incorporated. Because we assumed in STEP 2 that the patching moves do not violate any completely incorporated constraints, we must restrict the parameter value modifications of the patcher so as to guarantee this. The patcher has several compo­ nents, one for each modifiable parameter. The "increase room length" component of the patcher must ensure that the longer room is still inside the house (C3), still does not overlap another room (C5), still is adjacent to the house boundary (C4), and still has dimensions at least minValuelong (Cl,C2). Cl and C2 are obviously always true; C4 is guaranteed to be true because the <X,Y> corner has not been moved off the house boundary.

The RICK program [Braudaway, 1989] automatically constructs a constrained generator in which several local constraints have been incorporated. A function g(Par,F) constructed by RICK at compile time is attached to each floorplan parameter's range; this function dynam­ ically recomputes the legal values for that parameter. The patcher is constructed by modifying the constrained generator produced by RICK. The patcher differs from the constrained generator only in that the range of legal patching moves in a particular direction (+/-)is the sub­ set of the range of legal moves (computed by g(Par ,F)) bounded by (but not including) the current value and varying in the desired direction as far as possible, while still satisfying the incorporated constraints (C3 and C5).

STEP 5. Convert the patcher into a greedy patcher. STEP 2 of this method only determines desir­ able directions for changing parameter values, but does not constrain the amount by which the parameter value should be varied. One easily implementable idea is to take a greedy approach; for a particular parameter, a greedy patcher simply tries values from that parameter's legal range, in decrea1ing order of improvement with re­ spect to the evaluation function. From the re-expressed evaluation function created in STEP 3, we see that, for a proposed increase in the length of room r in state s, <r,Alength>, the change in evaluation function value is:

Since Af is proportional to Alength(r,s) (width(r) is not changed by the patch), the greatest evaluation func­ tion change occurs when the length change is greatest. Thus, the greedy patcher is made to select values in de­ creasing order of length. If Af had been inver1ely pro­ portional to width(r,s) then the greedy patcher would be designed to select values in increasing order. In either of these special cases, no extra work is required to sort the parameter range values using the evaluation function. More generally, we can compile an expression for com­ puting Af and sorting the range elements at run time.

STEP 6. Offset the negative aspects of the greedy patcher by trying to prevent · blocking moves. The major problem with a greedy strategy is that it neglects to check for long-term negative conse­ quences. Thus, as is illustrated in Figure 5, extending room Rl as far as possible to the right inadvertently block· room R5 from being extended maximally in the downward direction. Unfortunately, the shaded area in Figure 5 is a hole that is only fillable by extending R5 into it. The problem with a greedy strategy is that it may solve one subproblem (e.g. filling in pa:rt of a hole) at the expense of rendering some later subproblem un­ solvable.

Fortunately, we can offset some of the negative aspects of a greedy patching strategy by including a look-ahead component in the strategy. The purpose of this com­ ponent is to detect patching subproblems that can only be solved by a 1ingle move in one way (e.g. a maxi­ mal increase in the width of room R5). A1 1oon a· we detect that some patching move has this property, we make that move, to prevent other patching moves from inadvertently blocking such a necessary move. We will call such moves block-preventing move1. For example, the unsolvable patching subproblem in Figure 5 (a) can be avoided only by extending R5 down to R4 (see Figure

5 (b)).

Description of the look-ahead component. Given a covering constraint, the function of the patcher derived in STEP 1 through STEP 5 is to construct a complete assignment: "Assign space-filling units of type T sF to space units of type Ts so that the units of type Ts are covered." The space units are invariant (e.g., the gridpoints in the house), while the space-filling units are created (and implicitly assigned) by the generator and patcher. We use a data structureD (e.g., an array) that contains a single element for each space unit. D will rep­ resent the current assignment. Before trying to detect possible block-preventing moves, we initialize D so that the space units currently filled by rooms are recorded. Making a patch move involves marking those space units in D that are filled in by the patch move; in particular, we place pointers to the patching move itself in the ap­ propriate elements of D. We detect space units that can only be filled in by a single patching move in two steps. First, we update D to reflect the result of applying all patches applicable in the current state to the current state; then we look for elements of D that only have one associated patching move.

Construction of the look-ahead component. The most difficult part of automatically compiling the look-ahead component is to construct procedures that define and maintain the data structure D. Compiling a procedure for defining . D is relatively straightforward. The car­ dinality C of the space units is presumed to be fixed and was computed in STEP 1. For our example, C is length(house,s)xwidth(house,s). D is an array with C records (one for each space umt), each having a "space unit" field ( containin~ a pointer to the space unit that that record represents) and a "space fillers" field (a list of all space-filling units covering that space unit) . Compil­ ing a procedure to initialize D is based on the following information determined in STEP 1:

The values for the "space unit" fields of the elements in D are initialized from this set.

Compiling a procedure for maintaining D is based on the following information determined in STEP 1:

setOf[spaceFillingUnit(P,s)) = URef'oonuinfloOPpla.nfPEt3(R,f)

From this we determine the change in the covering re­ sulting from applying a patch:

After each patch, the maintenance procedure com­ putes the above set difference. For each space-filling unit in the set difference, it looks for the element D[i] contain­ ing the corresponding space unit. (Automatic program­ ming techniques such as in [Kant and Barstow, 1978] can be used to optimize this operation.) It then adds the current patch to the value of D[i]'s "space fillers" field.

Figure 6: Relative performance of algorithms

4 Empirical Results

We empirically evaluated and compared the perfor­ mances of generate-and-test, generate-test-and-patch, generate-test-and-greedy-patch, and generate-test-and­ greedy-patch with block-preventing patches on a test set of floorplans in which the rooms did not entirely fill the house area. We manually constructed the test set of floorplans to have varying degrees of difficulty (which we defined as the length of the 1horte1t path of patching op­ erations that would convert the floorplan into one that filled the house). In our study, the degree of difficulty of the example floorplans ranged between 1 and 4. The rel­ ative performances of the algorithms were measured by the number of node1 (floorplans) generated before find­ ing a solution. Note that the cost of generating a node can be shown to take time polynomial in the area of the house.

The graph in Figure 6 clearly depicts that the three generate-test-and-patch algorithms explore consistently fewer nodes than generate-and-test. Generate-test-and­ greedy patch with block-preventing patches performed best. For the examined degrees of difficulty, the number of generated nodes increased only linearly, reflecting the fact that block prevention succeeded in totally eliminat­ ing backtracking. Although block prevention may not achieve total elimination of backtracking in general, we have demonstrated its potential for significantly reduc­ ing backtracking.

5 Contributions and Limitations

Contributions. The approach we have presented is based on viewing satisfaction of a global constraint as an optimization process. The hillclimbing process is con­ fined to points in the space of "feasible solutions" (i.e., those which satisfy the incorporated local constraints). The novel contribution of this paper is an approach to automatically compiling a global constraint satisfier (a

"patcher") that is based on this hillclimbing viewpoint. To help relate our work to that of others, we can think of the compilation method as involving two major phases: (STEP 1) derive an evaluation function that (implicitly) defines a simple, operational patcher which varies one so­ lution parameter value at a time; and (STEP 2 through STEP 6) optimize the patcher in various ways. We now discuss work related to each of these two phases.

1. Constructing evaluation functions. Much research has focused on constructing evaluation functions for al­ gorithms (e.g., A*) that search .tate ·pace· (e.g., [Pearl, 1983]). These approaches derive evaluation functions from abstractions of state space operator preconditions. In contrast, our patcher moves in a parameter value ·pace, where there are no restrictions on how to move from one state to another; the moves are not restricted by a given set of operators. Thus in some sense, our problem involves not only constructing an evaluation function, but also a set of patching operators to help restrict the search for a satisfactory solution. STEP 1 of our method constructs the evaluation function, based on categorizing the goal-defining conditions (constraints) into one of several generic classes. STEP 2 through STEP 6 can be thought of as constructing implicitly de­ fined patching operators that take restricted forms (e.g. "greedily increase the length of room R"). Note that ou; approach to constructing evaluation functions could be applied to state space problems like the 8-puzzle. It would involve successfully classifying a problem into a known generic type (e.g., part re-configuration), and having associated with such generic problem types a procedure for constructing an evaluation function (e.g., "number of misplaced parts") .
2. Optimizing the hillclimbing algorithm. Our research on constructing hill-climbing patchers is similar to other recent work [Lowry, 1987] on designing efficient opti­ mization algorithms. Lowry illustrates his approach by deriving the simplex method for solving linear optimiza­ tion problems. His derivation greatly exploits the fact that the space of feasible solutions is convez. If that space were not convex (e.g., as in the nonlinear floor­ planning problem), many difficulties would arise: the feas~ble region is not necessarily connected (e.g., con­ stramts such as C5 are disjunctions); it is not always ~ossible to reach an optimal state starting from any fea­ stble state; etc. For such spaces, a more robust patcher must be constructed.

Limitations and future research. We are in the process of implementing this method in the MENDER program, and applying it to global constraints drawn from the house floorplanning domain. The research in this paper ~as focused on covering constraints; the future research wtll flesh out the taxonomy of global constraint schenias that our approach can handle. Currently, we have worked out the details of STEP 1 and STEP 6 only for the class of covering global constraints. STEP 2 through STEP 5, however, are expressed in terms in­ dependent of a particular type of constraint; they may therefore apply to global constraints generally.

6 Conclusions

We have developed a method for procedurally embed­ ding global constraints (that degrade the performance of generate-and-test algorithms) into a generate-test-and­ patch algorithm. We have shown how the generate-test­ and-patch algorithm can be further improved by allowing "greedy" patches, and by equipping the patcher with a mechanism for heuristically detecting block-preventing moves.

We have empirically shown that generate-test-and­ patch algorithms are more efficient than generate-and­ test for satisfying a covering constraint in the context of a simple house floorplanning task; we used a manu­ ally constructed set oftest examples of varying difficulty. Using the same examples, we also demonstrated that fur­ ther performance improvement is possible using a greedy patching strategy, and block-preventing patches to offset the disadvantages of greed.

Acknowledgements. We are grateful to Lou Stein­ berg, Jack Mostow, and Don Smith for their helpful comments. We would also like to thank the members of the KBSDE group, the Knowledge Compilation Sem­ inar, and the Rutgers AI/Design Project.