Domain Dependence in Parallel Constraint Satisfaction

1 Introduction

When a problem domain is known in advance, it is pos­ sible to exploit characteristics of the domain in order to simplify algorithms working within that domain. In AI this approach has often been used to generate unprin­ cipled heuristic solutions whose generality is ill-defined. But more principled approaches to domain constraint exploitation also exist. For example, Mackworth et al [1985] show how hierarchic domains can be exploited in the solution of constraint satisfaction problems.

In this paper we show how to exploit domain informa­ tion about arbitrary domains to generate improved arc consistency algorithms for constraint satisfaction prob­ lems (CSP's). A typical CSP is described by a set of nodes, a set of labels for the nodes, and unary and bi­ nary constraint predicates P and Q. Solving the con­ straint satisfaction problem involves finding a set of labels for the nodes that is consistent with the con­ straints. Arc consistency is a technique for eliminating solutions that are locally inconsistent [Mackworth, 1977, Mackworth and Freuder, 1985, Mohr and Henderson, 1986]. We have previously developed a massively parallel algorithm for arc consistency that can be implemented directly in VLSI. This algorithm is called the AC Chip, and is closely related to the uniprocessor algorithm AC4 [Mohr and Henderson, 1986]. The AC Chip finds arc consistent solutions to constraint satisfaction problems almost instantaneously, at the cost of a quadratic space complexity [Swain and Cooper, 1988].

This space complexity can be reduced by specializing the algorithm to accept problems from a restricted do­ main of all possible CSP's. To accomplish this, domain knowledge is expressed as meta-constraints on the con­ straint predicates P and Q. We describe a circuit mini­ mization algorithm, CircJ{in, that takes such a domain description and produces an optimized constraint satis­ faction circuit for that domain. The algorithm performs a set of optimizations that may reduce the numbers of gates needed by orders of magnitude. We illustrate the process with results from an example domain we are studying, the recognition of Tinkertoy objects from their compositional structure [Cooper and Hollbach, 1987, Cooper, 1988, Swain and Cooper, 1988]. Space complex­ ity improvements for the AC Chip algorithm can also be translated to time complexity improvements in AC-4.

2 Problem Formulation

A particular problem or class of problems is formulated as a constraint satisfaction problem by defining the el­ ements of the general constraint satisfaction problem in terms of the specific application being investigated. That is, a set of nodes and a set of labels must be defined in terms of the problem at hand. Likewise, the unary and binary predicates P and Q must be defined in terms rel­ evant to the application problem.

For illustrative purposes, considet as an example prob­ lem the recognition of Tinkertoy stick figures such as the "horse" in Figure 1. Tinkertoy objects consist of disks attached by connecting rods of differing lengths. The rods are plugged into slots on the junction disks (Fig­ ure 2). In the Tinkertoy recognition problem, structural descriptions derived from an image must be matched to stored descriptions in a model base. This matching prob­ lem is posed as a CSP by using the nodes in the CSP to represent the parts of the image description, and the labels in· the CSP to represent the parts of the corre­ sponding model description. A unique solution to the CSP then indicates a unique correspondence between the parts ofthe object and model. In the following examples, we define the rods and slots of the Tinkertoy descriptions to be the primitive parts.

To complete the formulation of Tinkertoy matching as a CSP, the unary and binary constraints are de­ fined in terms of properties of the nodes and labels as follows[Swain and Cooper, 1988]:

where some of the predicates can be expanded as follows:

and the terms are defined:

connected( i, j) True iff rod i is plugged into slot j or rod j is plugged into slot i.

filled( i) True iff a rod is plugged into slot i.

length( i) The length of the rod i .

position( i) The position of slot i on the disk, a number between 0 and s - 1, where s is the number of slots per disk.

same_disk( i, j) True iff i and j are slots on the same disk.

A solution to the CSP framed in this way constitutes a correspondence between a Tinkertoy object and model. But these definitions provide no restrictions on the prob­ lem instances that can arise, so the resulting CSP still requires a solution algorithm of complete generality.

3 Domain Description

If the space of input problem instances is in some way restricted, the potential for specialized and more effi­ cient solution algorithms exists. A problem domain is just such a restricted set of problem instances. Domains can be thought of as classes of problem instances with invariant properties. Consider for example the Tinker­ toy matching problem as framed above. For all problem instances, it is never the case that a rod can match a slot. To exploit such characteristics in general requires a domain description language.

The purpose of the domain description is to represent invariant properties that hold over different problem in­ stances. In constraint satisfaction problems, the nodes and labels are the entities that can have properties. In a Tinkertoy problem instance, the node i might represent a rod part, and thus have the property rod( i). If the node i is used to represent a rod part for all problem instances, rod( i) is a property invariant for all problem instances. Note that the mapping between Tinkertoy parts and the nodes of the CSP must maintain the invariant property across problem instances. It is straightforward to ar­ range that a certain subset of nodes represent rods and a different subset of nodes represent slots for all problem instances.

Once an invariant is established in this way, it can be conveniently described with a three-valued meta-term. A meta-term C' is defined in terms of an object prop­ erty C as follows. By defining a domain as a (possibly infinite) set 8 and designating problem instances as a,

Invariants in a domain are, of course, represented by those meta-properties that evaluate to t or f. For exam­ ple, rod'(i) would bet if rod(i) was true for all problem instances in the domain. Many properties will not be invariant, and their meta-description will evaluate to u.

Once the meta-terms describing the invariants are de­ fined, it is a simple matter to define meta-predicates P' and Q'. These are exactly the same as the unary and binary constraint predicates P and Q, with meta-terms used in place of the object terms of P and Q. The meta­ predicates are evaluated with Kleene's three-valued logic lTluner, 1984]. Consider for example:

Domain invariants can exploited when the meta­ predicates P' or Q' evaluate as invariant on some argu­ ments. As a concrete example, consider the meta unary predicate P'(i, x) for some i where rod(i) is always true

(rod'(i) = t), and for some x where slot(x) is always true. Because a rod does not correctly correspond to a slot, the predicate P(i, x) will evaluate to f for all problem instances (P'(i, x) = f). This fact is known in advance of runtime, and can be exploited in develop­ ing the algorithms to solve the CSP in this domain. We demonstrate this optimization with a particular parallel algorithm for arc consistency, the AC Chip.

4 The AC Chip

The AC Chip is a massively parallel digital circuit that computes arc consistency in worst case time O(na). The design is based upon the unit/value principle [Barlow, 1972, Ballard, 1986], and is limited to computing prob­ lems of maximum size n nodes and a labels. In short, the important parts of the design are an explicit representa­ tion of every value of the P and Q predicates in flip-flops, and combinational circuitry that eliminates inconsistent label candidates by implementing the equation:

There are two arrays of flip-flops, u(i, x) and v(i,j, x, y) corresponding to the predicates P and Q respectively. The circuit for one candidate labeling (one element of P(i, x)) is given in Figure 3.

The gates that implement the above expression are designated, from the inside of the expression to the out­ side, and gates A(i,j, x, y), or gates B(i,j, x), and gates C( i, x) and not gates D( i, x ). They are labeled in Fig­ ure 3. Identical circuitry exists for all na flip flops in the

procedure Circ..Min inputs: domain meta-predicates P' and Q' node tree node..hier label tree label..hier modifies: circuit, as in Figure 3 begin (* P elimination *) for all ( i, x) in P' do if P'(i, x) = f then Recursive_Delete(flip-flop u( i, x )) (* Q elimination *) forall (i,j,x,y) in Q' do if P' (j, y) = f or Q' ( i, j, x, y) = f then Recursive_Delete(and gate A( i, j, x, y)) else ifQ'(i,j,x,y) = t then begin wire output of flip-flop u(j, y) to or gate B(j) Recursive_Delete( and gate A( i , j, x, y)) end Replace_By JiierarchicaLGates( eire, labeLhier, node..hier) ; Merge_ With..SameJnputs( eire); FlattenJiierarchies( eire); end

array representing P. More details concerning the AC Chip may be found in Swain and Cooper [1988].

For the matching problem we investigate below, a = n = 29. To solve such a problem the general purpose AC Chip would require 1.4 million gates, already a very large chip! The domain optimizations described in the next section reduce this value to 66,000.

5 Optimizing the Algorithm for the Domain

If the meta-predicates P' or Q' are t or ffor some ar­ guments, this translates to flip-flops which are always on or off in the AC Chip arc consistency algorithm. System­ atically modifying the circuit to exploit the ramifications of these constants constitutes the domain dependent op­ timization of the algorithm. For example, if for some i and x P'(i, x) is f, the entire circuit of Figure 3 is not required for the u(i, x) element. The algorithm that per­ forms these simplifications in general is given in Figure 4, and is called Circ_Min.

Circ..Min consists of five phases: P elimination, Q elimination, Replace_ByJiierarchicaLGates, Merge_ With...SameJnputs, and FlattenJiierarchies.

P _elimination deletes any flip-flops u( i, x) that repre­ sent impossible candidate labels along with the trees of gates that feed into them. Q elimination removes type A and gates that are not necessary and replaces each one by a wire when Q' = true. These two optimizations are often the most important.

The purpose of the remaining three procedures is to factor out common sub-terms in the circuit and elimi­ nate the redundant circuitry that computes them. The procedure ReplaceJJy_HierarchicaLGates replaces a sin­ gle gate .by a hierarchy of gates in the pattern set by Figure 5: Procedure Replace_By _HierarchicaLGates the template or _hier (for or gates) or and_hier (for and gates) (Figure 5). These hierarchies are supplied by the user, and represent additional description of the domain. The hierarchy must correspond to natural groupings of the labels for hierarchical gate replacement to enable more wires to be eliminated in the merge phase. The procedure Merge_With..SameJnputs replaces redundant gates by one gate (thus also eliminating redundant in­ put wires), and wires the output appropriately to the multiple places it is used (Figure 6). Finally, the pro­ cedure Flatten_Hierarchy replaces hierarchies of gates of the same type with functionally equivalent multiple­ input gates. Flatten.Jiierarchy thus inverts the function of Replace_by .JiierarchicaLGates where it is still possible after common subterms have been eliminated (Figure 7). It is reasonable to apply this function only to minimize the number of gates and wires. If other complexity mea­ sures (wire length or wire crossings) are important, the functionality of Flatten.Jiierarchy might be undesirable.

The procedure RecursiveJJelete deletes the gate that is its argument, and recursively deletes any gates which become redundant by its deletion because they have no inputs or no outputs.

Analysis and Performance

The correctness of the algorithm can be determined by noting that each transformation converts one or more gates into an equivalent set of gates. Therefore, the function of the AC circuit is preserved throughout the algorithm.

A straight-forward analysis shows that the algorithm takes O(a 2 n 2 ) time and space. Since the circuit re­ duction algorithm is run offline, the exact value of its complexity is not important . However, it should be noted that the algorithm does not need combinatorial resources; in fact it needs time and space linear in the original size of the AC circuit.

Circ..Min may reduce the complexity of an AC circuit by orders of magnitude. For instance, for Tinkertoy do-

• 1: P flip-flop elimination
• 2: Q flip-flop elimination
• 3: gate merging
• 4: hierarchical gate substitution

main pro!:>lems with a number of disks d, number of rods r, and number of slots per disk s, the number of gates is reduced from almost 2( r + ds ) 4 to about 2r 2 d 2 s 2 . For the Tinkertoy domain with a maximum of 5 rods and 3 disks, each with 8 slots, this is a twenty-fold decrease (see Figure 8).

Figure 9 gives part of the reduced circuit for a Tinker­ toy matching problem with at most 3 rods and 3 disks, with 2 slots per disk. The Figure gives the input circuit to a single target candidate labeling - the match of slot 1 on disk 1 of the object, to slot 2 of disk 3 of the model. This candidate labeling is shaded in Figure 9.

In the figure, the square and rectangular boxes repre­ sent the array of flip-flops u( i, x) (holding P( i, x)) and the array of flip-flops v(i,j,x,y) (holding Q(i,j,x,y)) respectively. With no optimizations, the circuit would look everywhere as it does in the lower left corner of the Figure. But all four types of optimizations have been performed. P-elimination has eliminated u( i, x) flip flops (and their associated circuitry) from the upper left-hand corner and lower right-hand corners of the u( i, x) array. Q elimination has eliminated the v(i , j, x, y) flip flops associated with all of the slot-slot matches. Slot-slot matches have been be divided into two groups - those compatible with the target candidate labeling ( Q' = t), and those incompatible with the target candidate label­ ing (Q' = f) . Only those that are compatible have an output wire and can affect the consistency of the candi­ date labeling. Because of gate merging the same or gates shown in the diagram that are receiving input from the slot-slot matches feed to many other slot-slot matches. Hierarchical gate substitution has broken these or gates into a two-level hierarchy, with slots from the same disk grouped together at the lower level.

We do not claim to be able to generate the opti­ mal (most reduced) circuit for any problem. Domain knowledge not expressed in the meta-predicates might be exploitable [Cooper and Swain, 1988], or subtle opti­ mizations not discovered by Circ..Min might be feasible. Since, in general, circuit optimization is a difficult prob­ lem and must be approached heuristically [Brayton et al., 1984], we do not expect there to be a tractable algo­ rithm that finds the optimal circuit.

Because of the close relationship between the sequen­ tial arc consistency algorithm AC-4 [Mohr and Hender­ son, 1986] and the AC-Chip, the domain specific opti­ mizations which reduce the space complexity of the AC Chip algorithm can be used to reduce the time complex­ ity of AC-4, by modifying AC-4 so that it simulates the optimized chip [Cooper and Swain, 1988].

6 Conclusions

We have shown how to exploit information about arbi­ trary problem domains in order to generate more effi­ cient arc consistency algorithms for constraint satisfac­ tion problems in the domain. The domain description is formalized as meta-predicates whose purpose is to rep­ resent invariant properties of domain problem instances. The meta-predicates are the input to an algorithm that produces an optimized Arc Consistency (AC) Chip that may have space complexity many orders of magnitude lower than the general-purpose AC Chip. Because of the close relationship between the AC Chip and sequen­ tial arc consistency algorithm AC-4, the time complexity of AC-4 can be reduced by the same technique.

Acknowledgements

This work was supported by a Canadian NSERC post­ graduate scholarship, by the Air Force Systems Com­ mand, Rome Air Development Center, Griffis Air Force Base, New York 13441-15700 and the Air Force Office of Scientific Research, Bolling AFB, DC 20332 under Contract No. F30602-85-C-0008. The latter contract support the Northeast Artificial Intelligence Consortium (NAIC).