Abstraction via Approximate Symmetry

1. Introduction

Abs~ractio~ tec~niques are important for solving con­ stra~nt satlsfact10n ~roblems (CSPs) with global con­ stram.ts and low solutl~n.density. Examples of such prob­ lems mclude the Partlt10n problem and the Multipro­ cessor Scheduling problem, both of which are NP-hard [Garey .and Johnson, .1979]. In the presence of global c~nstram~s, backtrackmg search is unable to prune par­ hal solut10ns [Nadel, 1988]. It therefore operates like pure ge.nerate-and-t.est. When <;>verall solution density is low, th1s approach 1s not effect1ve, except when applied to small problems. Abstraction can improve the perfor­ man~e of backtracking by enabling entire subsets of the solut10n space to be pruned early in the search process.

. T~e value of a~straction can be illustrated by con­ s1?ermg the Mult1processor. Schedulin~ problem. (See F1gure. 2. ~ A ~olut10n ~o th1s problem 1s an assignment of begmmng tlmes to Jobs that meets deadlines obeys prec~dence constraints .and has a limited number' of jobs runnmg at <?nee. In th1s problem, the constraint on the number of s1multaneously running jobs is global, i.e., in general, one cannot verify the constraint without know­ ing t~e beginning times of all .the jobs .. Backtracking algonthms therefore cannot eas1ly use thts constraint to prune. partial solu~ions. In contrast, the following ab­ stractlOn strateg~ mtrod~ces a new level of description t~at enables partial solut10ns to be pruned: First parti­ tion the set of possible beginning times into contiguous,

2. Symmetry and Abstraction

An "abstraction space" A may be defined formally as a partition of the states in the underlying "concrete space" S. Thus each abstract state alA is a set of concrete states slS. Abstract search spaces may also be characterized in terms of permutation groups whose elements operate on states in the concrete search space. In particular, given a group I: of permutations that operate on states slS, one may define an abstraction space A as follows: For all pairs of states s1 and s2 drawn from S, s1 and s2 lie in a common abstract state a if and only if there exists a O"l:E, such that o-(s1 ) = s2 · (The group axioms guar­ antee that this definit10n yields a partition of S .) On the other hand, given an abstraction space A, one can construct a group I: of permutations that will induce A according to the definition given above. For example, one may take I: to be the direct product of the symmet­ ric subgroups A(a) for all alA. (The symmetric groul? A(X) is just the set of all permutations of the set X.) Notice that this last construction is not unique, since several permutation groups may induce the same parti­ tion. As a result of the connection between permutation groups and abstraction spaces, one can characterize var­ ious abstraction strategies in terms of the structure of permutation groups, as described below.

Exact Symmetry: Consider an arbitrary group I: of permutations of the states in the concrete space S. A goal function G : S -+ {True, False} is said to be ex­ actly symmetric with respect to I: if for each slS, and each o-EI:, G(o-(s)) = G(s). If the group I: is used to induce a partition of S into an abstraction space A, the space A will have the following useful property. For each abstract state a, all concrete states sw have the same value of the goal function. Thus if any single element of a fails to satisfy the goal function, then all elements of a will fail. The abstract state a may then be safely pruned without risk of losing completeness of the prob­ lem solver. Furthermore if any single element of a suc­ ceeds in satisfying the goal function, then all elements of a will succeed. All members of the abstract state a may then be immediately identified as solutions.

Approximate Symmetry: Consider once again an arbitrary group I: of permutations of the states in the concrete space S. A goal function G : S -+ {True, False} is said to be approximately symmetric with respect to I: if there exists a good approximation G of G such that G is exactly symmetric with respect to I:. Once again, if the group I: is used to induce a partition of S into an abstraction space A, the space A

will have useful properties. Two interestin~ cases result from considering the ways in which G and G are related:

• Necessary Approximations: G => G, i.e., G entails G: In this case, given an abstract state a, if any single element of a fails to satisfy the approximate goal G, all elements of a will fail to satisfy G, and therefore all elements of a will fail to satisfy the original goal G. The abstract state a may then be safely pruned.
• Sufficient Approximations: G => G, i.e., G entails G: In this case, given an abstract state a, if any single element of a succeeds in satisfying the approximate goal G, all elements of a will satisfy G, and therefore all elements of a will satisfy the original goal G. All elements of the abstract state a will then be valid so­ lutions.

Necessary approximations are generally more important in practice. In particular, necessary approximations are useful for finding solutions when solution density is low (the usual case), while sufficient approximations are use­ ful for finding non-solutions when solution density is high (not the usual case). The distinction between necessary and sufficient approximations is quite similar to the dif­ ference between "TI abstraction" an "TO abstraction" defined in [Giunchiglia and Walsh, 1992], and the distinc­ tion between the "Upward Solution Property" and the "Downward Solution Property" described in [Knoblock et al., 1991].

Types of Approximate Symmetry: Interesting special types of approximate symmetry result from con­ sidering CSPs whose solution requires finding a function f : D -+ R to meet specified constraints. Example prob­ lems of this type include the Multiprocessor Scheduling problem, which requires finding a function mapping jobs to beginning times, and the Partition problem, which requires finding a boolean valued function of a set of el­ ements. For problems of this type, the concrete search space S is the set of all functions from D into R. Ab­ stractions of this space can be defined in the following three steps: (1) Select some group~ of permutations of the domain b or the range R; (2) Use the group ~ to construct a group I: of permutat10ns of the search space S such that~ is a homomorphic image of I:; (3) Use I: to induce a partition A of S. Various types of abstractions result depending on the structure of the original group ~. on whether members of~ operate on the domain D or the range R and on the details of constructing I: from ~-

Range Symmetry: Suppose that ~ is a/roup of per­ mutations of the range R of the function . Define the group I: in the following steps: (1) For each permuta­ tion if! of ~, and each element d of D define o-<f>d such that O"<f>d(/)(d) =if!(!( d)) and for all d'ED, if d # d' then O"<f>d(!)(d') = f(d'). (2) For each dlD, let :Ed be the set of all o-q,d such that ifil~. (3) Let I: be the direct product of all :Ed fordED. Using this construction, two functions /1 and h are equivalent with respect to I: whenever It and h differ only by returning values that are equivalent with respect to~. In this case, I: induces an abstraction A of the original space S that can be represented in the following way: Each element aEA is a function j that accepts an element d in D and returns a set f appearing in the partition R induced by ~-

Consider an application of range symmetry to the Multiprocessor Scheduling problem. (See Figure 2.) In this example, the role of f is played by an integer val­ ued function b that defines the beginning times of jobs. The role of D is taken by the set J of jobs. The role of R is taken by the set T of possible beginning times. The group C) could be selected to induce a partition T ofT such that the sets teT are disjoint sequences [1 ... u] of beginning times. Each element a in the abstraction space A will represent a function b that assigns to each job j a range i of possible beginning times. The range i constrains the beginning time of job d to lie in a time window, but does not specify the precise beginning time of any job. Range symmetry thus captures the abstrac­ tion strategy of the Multiprocessor Scheduling example described above.

Domain Symmetry: Now suppose that C) is a group of permutations of the domain D of the function f. Sup­ pose further that C) is a direct product of symmetric subgroups A(J) for all J in some partition b of D. Define the group E by taking each element ~ of C) and forming a corresponding element <T,p of E such that for each feS and each deD, <T,p(f)(d) = /(~(d)). Thus two functions It and h are equivalent with respect to E whenever It and h differ by permuting their values at points in D that are equivalent with respect to «<». In this case, E induces an abstraction A of original space S that can be represented in the following way: Each element aeA is a function j that accepts a subset J in the partition b and returns a multiset of cardinality ldl of values drawn from the range k.

Consider an application of domain symmetry to the Partition problem. (See Figure 3.) In this example, the role off is played by a boolean function m, which spec­ ifies the elements included in the set M. The role of D is taken by the set E of elements to be partitioned. The role of R is taken by the set {True, False} of boolean values. The group c) could be selected to induce a partition E of E such that each set eeE contains elements of nearly equal weight. Each element a in the abstraction space A will represent a function m that assigns to each set e a multiset of boolean values. The number of True values in the multiset will represent the number of ele­ ments of e that are included in M. Likewise, the number of False values in the multiset will represent the number of elements of e that are not included in M. An abstract solution a therefore implicitly assigns a quota to each set e, but does not precisely specify the inclusion status of any particular element. Domain symmetry thus cap­ tures the abstraction strategy of the Partition example described above.

3. Synthesis of Problem Solvers

A general strategy for synthesizing hierarchic problem solvers can be formulated in terms of approximate sym­ metry: ( 1) Select a group E of permutations of the search space S. (2) Transform the original goal G into an approximate goal G such that G =? G and G is exactly sym­ metric with respect to E. (3) Use E and G to construct components of the hierarchic problem solver shown in Figure 1. Algorithms that instantiate this generic ab­ straction strategy for the special cases of domain sym­ metry and range symmetry are described below.

Parameterized CSPs: Classes of constraint sat­ isfaction problems are represented using a notation called "parameterized constraint satisfaction problems"

• Given: A set J of jobs; a set T of beginning times; a workin~ time w(j) for each job j; a deadline d(j) for each JOb j; a precedence relation p(j, k) on the jobs; a number n of processors. Find: An assignment of beginning times to jobs that meets the deadlines, obeys the precedence relation and has at most n jobs running at once.
• Signature:
• Sets: Jobs J (Symbol); Times T (Integer).
• Known:

Working-Time w: J-+ T Deadline d : J -+ T Precedence p : J x J -+ {True, False} Number of Processors n of type Integer.

• Unknown: Beginning-Time b : J -+ T
• Goal Function:

G(p, s)

= g1(p, s) I\ g2(p, s) I\ g3(p, s)

gl(p, s) (VjeJ(p)) e(j,p,s):::; d(j,p)

g2(p, s) = (Vj,j'eJ(p))-.p(j,j',p) V q(j,j',p, s)

g3(p, s) = ..., (3jeJ(p)) l(j,p, s) > n(p)

q(j,j',p,s)

= b(j', s) ~ e(j,p, s)

l(j,p,s) = EkeJ(p) if(r(k, b(j),p, s), 1, 0)

r(j, t,p, s) {b(j, s):::; t} I\ {e(j,p, s) > t}

e(j,p, s) = b(j,s)+w(j,p)

Figure 2: Multiprocessor Scheduling Problem Class

· (PCSPs). A PCSP includes a signature S and a goal­ function G. The signature is a declaration ofthe types of sets and functions that appear in problem instances, in­ cluding: A list of names and data types (symbol or inte­ ger) of finite sets; A list of names offunctions along with a declared domain and range for each; A list of names and data types of constants. Furthermore, the signature also declares each function to be either "known" or "un­ known". The known functions are supplied as part of a problem instance specification. The unknown functions must be found in order to solve the problem. We use the notation /(e,p) to indicate that the known function f depends on the problem instance p, as well as its ar­ gument e. We use the notation f(e, s) to indicate that the unknown function f depends on the solution s, as well as its argument e. The problem instance p or state s parameter will occasionally be omitted from f(e,p) or /( e, s ), when its role is clear from the context.

The goal function G serves to determine how the un­ known functions may be specified in order to solve the problem. G is conceptually a map from the known and unknown functions into the booleans. We use the nota­ tion G(p, s) to indicate that G depends on the problem instance p (i.e., the known functions) and the solutions, (i.e., the unknown functions). A particular goal function G is represented by a boolean formula that may reference the known and unknown functions; primitive arithmetic (+, -, *,/),relational(<,:::;,>,~) and boolean(-., V, II.) operations; as well as conditionafs If(c, x, y) and abso­ lute values Abs(x). G may also include universal V or existential 3 quantification and sums E or products II of functions over sets declared in the signature. Signatures and goal functions for the Partition and Multiprocessor Scheduling problems are found Figures 2 and 3.

• Given: A set E and a weight w( e) for each element e of E. Find: A subset M of E such that the total weight of M equals the total weight of E - M.
• Signature:
• Sets: Elements E (Symbol); Weights W (Integer).
• Known: Weight w : E -+ W
• Unknown: Membership m : E -+ {True, False}
• Goal Function:

Figure 3: Partition Problem Class

Synthesis Algorithms: Algorithms for synthesizing hierarchic problem solvers based on range and domain symmetry are shown in Figure 4. Each algorithm be­ gins by partitioning the range R or the domain D of the unknown function f into a set R or b of equivalence classes. The partitioning is carried out by clustering R or D based on similarity of values of some known func­ tion whose domain is R or D respectively, and which is referenced by the goal function G(p, s). (These clus­ tering techniques are described [Ellman, 1993).) Next, the original goal function G(p, s) is transformed into an abstract goal G(p, a) in order that it will operate on ab­ stract states a that represent abstractions j of the un­ known function f. In each algorithm this transformation is achieved, in part, by a process of replacing operations on objects with corresponding operations on sets, or cor­ responding symmetric operations. The revised goal is then surrounded with a test for the appearance of True in the returned set of boolean values. The resulting ab­ stract goal G(p, a) is, by construction, a necessary con­ dition on solvabihty of the abstract state a. Finally, a refinement function Rd is constructed for each element D of the domain d. The function Rd(p, a, s) takes the prob­ lem specification p, an abstract solution a, and a par­ tially specified concrete solution s, and returns the set of possible values for /(d) that are consistent with a and s.

The abstract goal is synthesized at compile time, i.e., when the problem class is specified, but no prob­ lem instances are at hand. Once the abstract goal is constructed, the system applies a series of equivalence­ preserving optimizing transformations, such as distribu­ tive laws and factorization of sums, products and quan­ tifications, to improve the computational efficiency of the abstract goal. (The same optimizations are applied to the original, concrete goal and to localized versions of both abstract and concrete goals). All set arithmetic op-

erations appearing in abstract goals (E.g.,+,.:,/,*) are implemented as operations on real intervals. Since these set operations take constant time, the abstract goal has the same asymptotic complexity as the original goal.

The domain D or range R is partitioned at run time, i.e., after a problem instance has been specified. Input taken from the user at compile time is used to determine which known function will guide partitioning of D or R. (In the Partition and Multiprocessor Scheduling exam­ ples, the user actually has only one choice.) Depending on the set U to be partitioned, and the known function f selected to guide the partitioning, one of two clustering algorithms is used: (1) Iff is the identity function, and

Definitions:

• Set Functions: Given an arbitrary function h : A -+ B, define the corresponding set function h : AU 2A -+ 2 8 , such that h(x) = {h(x)}, if xeA, and h(x) = {h(y)IYEX} if x ~A.
• Symmetric Functions: Given an arbitrary func­ tion h : A -+ B, and a partition A of A, define the corresponding symmetric function h : A U 2A -+ 2 8 such that h(x) = {h(y)ly£Clas8(x)}, if xeA, and h(x) = Uyez{h(z)luClass(y)}, if x ~A.

Algorithms: Given a search space S representin~ all functions f from D into R, and a goal function G(p, s) defined on all 8£5 and problem instances p.

1. Define an abstraction space A:
2. Range Symmetry: Define a partition R of R by clus­ tering R based on similarity of values of R itself or some known function defined on R that is referenced by the goal function G(p, s ). Let the abstraction space A represent all functions j : D -+ R.
3. Domain Symmetry: Define a partition b of D by clustering D based on similarity of values of D itself or some known function defined on D that is refer­ enced by the goal function G(p, s ). Let the abstraction space A represent all functions j with domain b such that for all dED, j(J.) returns a multiset over R of cardinality ldl.
4. Synthesize an abstract goal G(p, a) defined on all aEA and problem instances p:
5. (a) Construct an approximate goal function G(p, 8) that is exactly symmetric with respect to R or b:
6. Transform the original goal function G(p, s) into a boolean set valued function G(p, s ):
7. Range Symmetry: Replace each reference to the unknown function /(d) with the expression Cla88(/(d)). Replace each primitive or known function h with the corresponding set function h.
8. Domain Symmetry: Replace each reference to a known function h defined on domain D, with the corresponding symmetric function h. Replace each primitive or known function h defined on D' # D, with the corresponding set function h.
9. Let G(p, s) = True f G(p, s ).
10. (b) Define the abstract goal G(p, a) to select an arbi­ trary sEa and return G(p, s ).
11. Synthesize functions Rd(P, a, s) that incorporate con­ straints between the abstract space A and the concrete space S. For each dED, Rd(p, a, s) is the set of values of f(d) that are consistent with the lll)stract solution a and the partially specified concreL 'solution 8.
12. Range Symmetry: Rd(p, a, s) is the set j( d, a).
13. Domain Symmetry: Rd(P, a, s) is the set of elements in the multiset difference between j(J., a), and the multiset of all /( d, 8) (dE d) such that /(d) is assigned a value in state s.

Figure 4: Synthesis Algorithms and Definitions

Figure 5: Abstract Multiprocessor Scheduling Goal

G(p,a) 8t(P, a) 8t(P, a) = True E (8t(P, a)£:82(p, a)) = te·E(p)t(e,.,)·(e,m(e,a))if(v, w(e,p) , {0}) = te·E(p)t(e,.,)·(e,m(e,a))if(v, {0}, w(e,p))

Figure 6: Abstract Partition Goal

U is an unbroken sequence of integers (U = [1 ... u]), then U is partitioned into intervals of equal or nearly equal size; (2) Otherwise, U is partitioned in a bottom up fashion, starting with singleton sets, and repeatedly merging two sets x and y such that f has minimal varia­ tion over xUy. In either case, the final partition is chosen to yield an abstract space whose size is the square root of the size of the concrete space, based on a rough anal­ ogy with Korf's result on the optimal size of abstraction spaces [Korf, 1987].

When the range symmetry algorithm is applied to the Multiprocessor Scheduling problem description in Fig­ ure 2, it generates the abstract ~oal function shown in Figure 5. This goal function G(p, a) performs interval arithmetic, interval comparisons, and boolean-set alge­ bra on the time window assignments b(j, a) represented by an abstract state a: For example, G(p, a) checks dead­ lines by converting beginning time windows into ending time windows, and noticing whether any job's deadline occurs earlier than the start of its ending window. Like­ wise, G(p, a) checks for processor overload by computing lower bounds on the numbers of jobs running at each point in time, and noticing whether any lower bound ex­ ceeds the available number of processors. The abstract goal G(p, a) thereby computes a necessary condition on the original goal.

When the domain symmetry algorithm is applied to the Partition problem description in Figure 3, it gener­ ates the abstract goal function shown in Figure 6. This goal function G(p, a) selects an arbitrary concrete so­ lution 8 consistent with the quota assignments m( e' a) represented by an abstract state a. It then applies to s an approximation G(p, s) of the original goal function that is symmetric with respect to the partition E. This symmetric goal function G(p, s) treats each eEE as if it has an interval w( e) of we1ghts, rather than an actual weight w(e), i.e. , an interval spanning the weights of all elements in Class(e). It first computes an interval 8 1 bounding the total weight of elements included in M and an interval Sz bounding the total weight of elements excluded from M . It then checks whether these intervals overlap. The abstract goal G(p, a) thereby computes a necessary condition on the original goal.

4. Experimental Results

A series of experiments was run to evaluate the per­ formance of automatically synthesized problem solvers based on range and domain symmetry. Results of these experiments are shown in Figures 7 and 8. Each graph compares the performance of a hierarchic problem solver, which uses abstraction, to the performance of a flat prob­ lem solver, which uses no abstraction. The hierarchic and flat problem solvers use the same underlying back­ tracking code, but with different input specifications. Each graph plots problem size against performance mea­ sured in terms of CPU time. CPU time is a better mea­ sure than alternatives, like numbers of goal tests or num­ bers of states generated, for two reasons: First, the com­ putational cost of generating one state or testing one goal may not be the same in the flat and hierarchic problem solvers. Second, the relative importance ofstate gener­ ation and goal testing may not be the same in the flat and hierarchic problem solvers.

The Multiprocessor Scheduling problem graph com­ pares performance on problems with a fixed domain size (i.e., 6 jobs), and a varying range size (i.e., the number of time slots running from 5 to 35). Each data point represents an average over a set of 100 randomly gener­ ated problems. The multiprocessor problem search was guided by localized versions of the abstract and concrete goals in order to realize pruning from application of the local constraints that appear in this problem. The local­ ized goals were constructed automatically from the corre­ sponding unlocalized goals using standard dependency­ tracing techniques. The Partition problem graph com­ pares performance on problems with a varying domain size (i.e., the number of elements running from 4 to 16) and a fixed boolean range. Each data point represents an average over a set of 10 randomly generated problems. The Partition problem search was guided by unlocalized versions of the abstract and concrete goals, since no local constraints appear in the Partition problem. In each of the two test domains, the hierarchic solver outperforms the flat solver for sufficiently large problems. A series of paired, single-tailed T-Tests shows hierarchic scheduling to be faster than flat scheduling with significance greater than 99% on the five largest problem sizes. A series of paired, single-tailed T-Tests shows hierarchic partition­ ing to be faster than flat partitioning with significance greater than 99% on the two largest problem sizes.

5. Related Work

Abstraction techniques have been studied previously in the context of planning [Knoblock et al., 1991] and the­ orem proving [Giunchiglia and Walsh, 1992]. In con­ trast, the research presented here is focused on ab­ straction techniques for constraint satisfaction problems. A program called "HiT" for automatically construct­ ing abstraction spaces for CSPs is presented in [Mohan, 1991]. HiT uses the ranges offunctions appearing in the goal definition as the basis for constructing abstraction spaces. HiT may be seen as a special case of the range symmetry technique described here. Methods of attack­ ing hierarchical CSPs are discussed in [Mackworth et al., 1985]; however, these methods exploit existing hierar­ chies and do not construct new ones. Abstractions based on quotas have been studied in the context of resource allocation problems [Lowry and Linden, 1992]. Approxi­ mate symmetry provides a rational reconstruction of the quota concept. Furthermore, approximate symmetry is more general, because it depends only on the algebraic form of the problem and not on semantic notions such as "resources". Abstractions based on windows oper­ ate in a manner similar to interval constraint propaga­ tion [Davis, 1987]. Approximate symmetry provides a means of using such interval-based methods to attack problems with global constraints, to which constraint propagation techniques to not immediately apply. Tech­ niques for recognizing and exploiting exact symmetries have been investigated in the context of propositional satisfiability [Crawford, 1992]. In contrast, the methods presented here construct and exploit symmetries that are not present in the original problem. Approximations and abstractions have been used to construct heuristic eval­ uation functions in the context of constraint satisfaction [Dechter and Pearl, 1987] and state space search [Priedi­ tis, 1991]. A system that selects and combines multiple heuristics to synthesize CSP algorithms is described in [Minton, 1993a] and [Minton, 1993b].

6. Acknowledgments

This research is supported by the National Science Foun­ dation. (Grants IRI-9017121 and IRI-9021607). It has benefited from discussions with Haym Hirsh and Christo­ pher Tong and programming by Saibal Patra.