Solving Geometric Constraint Satisfaction Problems for Spatial Planning

1 Introduction

In the face of growing importance of industrial applica­ tions in electronics, mechanics, architecture, town plan­ ning, etc. layout automation has spurred considerable interest. A spatial planning problem consists of finding a layout of a set of objects that satisfies a set of con­ straints among these objects.

Like many important problems in artificial intelligence and operations research, spatial planning can be viewed as a Constraint Satisfaction Problem (CSP). A CSP is defined by a finite set of variables taking on values from finite domains, and a set of constraints among these vari­ ables. In spatial planning problems, the variables are the objects, the domains are the configuration sets ( <;>rienta­ tions + positions) of the objects, and the constramts are the geometric relations among the objects. We call such a problem a Geometric Constraint Satisfaction Problem (GCSP). .

·This work was supported in part by the National Agency of Research and Technology (ANRT), and in part by Al­ catel Alsthom Recherche, in collaboration with the Claude­ Bernard University of Lyon.

A solution to a CSP is an assignment of values to van­ abies satisfying all constraints, and the problem is to find one or all solutions. Many improvements of the back­ tracking search algorithm [Haralick and Elliott, 1980], preprocessing techniques [Dechter and Pearl, 1989] and consistency algorithms [Montanari, 1974; Mackworth, 1977; Mohr and Henderson, 1986] have been designed to solve CSPs. In particular, consistency algorithms re­ duce the search space by removing, from the domains and constraints, values that cannot be part of a solution. Arc-consistency algorithms work on binary CSPs, and make sure that constraints are individually consistent [Mackworth, 1977]. AC-4 is an optimal arc-consistency algorithm [Mohr and Henderson, 1986] for general con­ straints over finite domains. Other arc-consistency algo­ rithms have been designed to exploit internal structure of domains such as interval domains [Davis, 1987], hi­ erarchical structured domains [Mackworth et al., 1985] or specific constraints such as functional and monotonic constraints [Deville and Van Hentenryck, 1991].

In this paper, we propose a new approach to solve ge­ ometric constraint satisfaction problems. First, we rep­ resent the position set of an object in a given orientation as one multi-dimensional domain (2D or 9D). Second, we propose a uniform symbolic representation of differ­ ent geometric constraints in order to make conjunctions of constraints bearing on the same objects. Third, to achieve arc-consistency, we take advantage of the ordered structure of the domains, in the same way as specific con­ sistency algorithms do over intervals. All these principles have been implemented in the ATLAS spatial planning system, and tested in the field of microwave electronic equipment design.

Section 2 presents the representations chosen for vari­ ables and constraints. Section 3 describes the solution of the GCSP: conjunction and consistency of constraints. Section 4 reports the implementation of the proposed approach in ATLAS. Section 5 proposes a comparison with other works, and a discussion of the interest and the application of otir approach. Conclusions are given in section 6.

2 Representations

In this paragraph, we present the representations chosen for variables and constraints.

2.1 Representation of Variables

The representation of variables is based on the follow­ ing hypothesis: the possible orientations of the objects are discrete and in a limited number. For example, the objects may have orientation 0, ?I" /2, ?I" or 3?1" /2. This hypothesis is not restrictive for a large variety of spatial planning applications.

The configuration set of an object (its domain) is rep­ resented by the cartesian product of 1c position sets, where 1c is the number of possible orientations. For ex­ ample, in a ~D spatial planning problem with 4 possible orientations (0, ?r/2, ?I" or 3?r/2), figure 1 shows the de­ composition of the domain D, of an object i in several position sets D,(a), for each orientation a of i. Each position set is represented by a multi-dimensional space (2D or 3D according to the application). Note that the domain representation introduces two levels: the orien­ tation level and the position level. The position set and the object form have therefore the same topological di­ mension, used the same representation resulting in easier geometric operations between them.

We represent the position set of an object for a given orientation by the positions of its reference point. This representation is based on the configuration space ap­ proach used in particular in robotics for motion plan­ ning [Lozano-Perez, 1983]. Indeed, the configuration set of an object is a non injective view of the configuration set of its reference point. Note that the configuration set of an object is given by the geometric sum (Minkowski sum 1 ) of the configuration set of its reference point and its form. To illustrate the non injective nature of this transformation, figure 2 shows, for a given orientation of an object 0, two different domains of its reference point Dom(o(O)) and Dom'(o(O)), corresponding to the same domain Dom(O) of 0.

Geometric constraints, such as "no-overlap", are at the origin of the removal of values situated at the cen­ ter of the domain rather than those on the boundaries. Therefore, we don't restrict the removal of inconsistent configurations on domain boundaries, but make possible the removal of any inconsistent configuration. Note that a position set of an object may be non connected (i.e. may consist of several disjoint parts).

1 A EB B = {a + b I a E A, b E B}

2.2 Representation of Constraints

Constraints express relationships among objects. They come either from the problem specifications or from the problem solving know-how. The constraints considered here are restricted to being unary or binary. Two types are distinguished: orientation constraints and position constraints.

2.2.1 Representation of Orientation Constraints

Orientation constraints are restrictions on the orien­ tations of one or two objects. They are represented ex­ plicitly by their relation graph. For example, a "same­ orient" constraint between two objects is represented by the following set: {0, ?I" /2, ?I" or 3?1" /2}.

2.2.2 Representation of Position Constraints

Position constraints are restrictions on the positions of one or two objects. They are represented implicitly by symbolic relations between two regions ("no-overlap", "contains", "min-distance" ... ). A region is a geometric entity (point, line, surface, volume) which position is de­ fined relatively to the layout space or to the reference point of an object. For example, the form of an object is a particular region of it, like its special points. Symbolic relations considered here are the same for unary and bi­ nary constraints; a unary position constraint is a relation between a region of an object and a region of the layout space; a binary position constraint is a relation between two regions of two objects.

We take advantage of the configuration space ap­ proach [Lozano-Perez, 1983] in order to express different symbolic relations between two regions, with a uniform "belong" relation between a reference point and a region. Let C1,; be a position constraint between two regions Rt and R; of the objects i and j. For example, C,,; may be a "no-overlap" constraint between the forms Rt and R; of the objects i and j. We express C,,i with a "belong" relation between the reference point o( i) of the object i and a region which is given by the deformation of the region R; in accordance with the region R.t. Table 1 presents the uniform "belong" relation of different sym­ bolic relation of position constraints. R; ffillt denotes the geometric sum between R; and Rt, - Rt denotes the sym­ metric of Rt, Rt denotes the complementary of Rt and Dulc( d) denotes the disk of radius d. The proof of this result is given in appendix A. In [du Verdier, 1992], we give the expressions of other position constraints, such as "alignment".

Note that the form of the region which is introduced in the "belong" relation depends on the object orienta­ tions. Therefore, the "belong" relation of a unary po­ sition constraint introduces as many regions as possible orientations; for binary position constraint, it introduces as many regions as possible pairs of orientations.

3 Solution

Before presenting the consistency algorithms, we de­ scribe the conjunctions of constraints bearing on the same objects, in order to improve the performance and to guarantee that there is at most one binary constraint between two variables.

3.1 Conjunction of Constraints

A significant improvement of the propagation process in a CSP consists of substituting constraints bearing on the same variables for a single constraint, conjunction of the initial constraints [Montanari, 1974]. First, because of a reduction of the back-and-forth propagation process between the same variables, inconsistent values will be detected earlier. Second, local consistency over the con­ junction constraint may detect more inconsistent values than the same local consistency over the initial ones; for example, in figure 3, the detection that the value b of the variable i is inconsistent requires a path-consistency for the initial CSP (a), and only an arc-consistency for the CSP after conjunction (b) .

Figure 3: Example of the conjunction of two constraints bearing on the same variables.

Sections 3.1.1 and 3.1.2 describe the conjunction of

orientation and position constraints according to their proposed representation in the GCSP.

3.1.1 Conjunction of Orientation Constraints

The conjunction of orientation constraints bearing on the same variables is given by an intersection of the re­ lations, since their representation is ex,plicit.

3.1.2 Conjunction of Position Constraints

The conjunction of position constraints bearing on the same variables is given by a geometric intersection of the concerned regions, since they are expressed uniformly with a "belong" relation. Figure 4 gives an example of conjunction of a "no-overlap" constraint C between two regions Ro and R; of two objects i and j and a "max­ distance" constraint between the points Pi of i and P; of

j:

C'=no-overlap(R., R;) ¢> o(i) E R; EB -Ri C"=max-di.tt(R,,R;,d) ¢> o(i) E R;EB Di.tk(d)EB -R, C = C" 1\C' ¢> o(i) E R; EB -R, n R;EB Di.tk(d) EB -R,

p. G

Figure 4: Example of conjunction of a "no-overlap" con­ straint and a "max-distance" constraint.

3.2 Consistency

For complexity reasons (time and space), we limit the degree of consistency to 2 with an arc-consistency pro­ cedure. Note that arc-consistency doesn't achieve the complete consistency of a CSP, and that some inconsis­ tent values may still remain in an arc- consistent CSP.

An arc-consistency algorithm is a symbolic relaxation algorithm to achieve node-consistency~ over each vari­ able and arc-consistency 3 over each binary constraint. Then, the propagation process consists of only reconsid­ ering a binary constraint between two variables i and j after a deletion from the domain D; of j.

The arc-consistency procedure of the GCSP applies this principle, except that it operates on two kinds of constraints (orientation constraints and position con­ straints), and that it takes advantage of the domain rep­ resentation introduced in 2.1. First, consistency of an orientation constraint operates at the orientation level of the domain representation of the objects. Second, prop­ agation on an orientation constraint occurs only when all configurations of the position set of an orientation are re­ moved. Therefore, propagation on a constraint concerns a given orientation.

2 A variable i is node-consistent iff each value of Di satisfies the unary constraints on i.

3 A binary constraint Ci,j is arc-consistent iff for each value :z: of D, there is at least one value 11 in D; such that c,,;(:z:,y) is satisfied.

For orientation constraints, local consistency of one node or one arc is achieved by usual algorithms ("NC" and "REVISE" procedures [Mackworth, 1977]), since the representation of these constraints is explicit. Concern­ ing local consistency of position constraints, we propose a new specific method which is the essence of our con­ tribution. Our approach is based on the configuration space approach [Lozano-Perez, 1983], and uses the pro­ posed uniform symbolic representation of position con­ straints. The idea is to take advantage of the ordered structure of the domains, in the same way as consistency algorithms do over intervals. We present this original ap­ proach of consistency of position constraints and gives some remarks about complexity. We give the complete arc-consistency algorithm of the GCSP and analyse its complexity in [du Verdier, 1992].

3.2.1 Node-Consistency of Position Constraints

A unary position constraint limits possible configu­ rations of an object. These configurations are directly given by the region of the layout space which is intro­ duced by the uniform "belong" relation of the constraint. Indeed, this region defines the positions of the reference point of the object satisfying the constraint. Therefore, for a given orientation ai, the consistency of a unary position constraint Ci on a region ~ of an object i, con­ sists of a geometric intersection between the correspond­ ing position set Di(ai) and the region Region(~(ai)) of the uniform "belong" relation of ci.

3.2.2 Arc-Consistency of Position Constraints

Concerning a binary position constraint, its uniform "belong" relation introduces, for each pair of orienta­ tions, an imposed placement region for the reference point of the first object of the relation. As this region is defined wrt. to the reference point of the second object of the relation, it may "move" around the layout space in accordance with the positions of this second object. Therefore, concerning the consistency of a binary posi­ tion constraint Ci,; between the regions ~ and R; of the objects i and j, for each pair of orientations of i and j, the position set Di of o(i) satisfying Ci,; is given by the geometric sum between the position set D; of o(j) and the region Region(~, R;) which is introduced by the uniform "belong" relation of ci,j .

Figure 5 shows·an example of the consistency of a "no­ overlap" constraint between the regions~ and R; of two objects i and j with domains Di and D;. The "belong"

relation of this "no-overlap" constraint introduces the region R; EB -~. The positions of o(i) satisfying the constraint are given by the geometric sum between the possible positions D; of o(j) and the region R; EB -~. Then, the positions Di of o( i) which are not in the region D; EB R; EB -~ are removed from Di by a geometric intersection.

This result is valid only for a given pair of orientations. In the general case, the consistency of a binary position constraint, for a given orientation of the first object of the relation, leads to a disjunction on the orientations of the second object. Instead of testing all pairs of possi­ ble orientations, it is better to test only those satisfying binary orientation constraints among the considered ob­ jects, in order to improve the efficiency of the consistency achievement in terms of both time and quality. Note that the motivation is the same for the conjunction of con­ straints bearing on the same variables (See section 3.1). We introduce the predicate R-Orient ( i, j, ai, a;), which is true for the pairs of orientations (ai, a;) of the objects i and j satisfying the binary orientation constraints be­ tween i and j.

3.2.3 Consistency Complexity of Position Constraints

Concerning position constraints, node-consistency of an object in a given orientation consists of only one ge­ ometric intersection, and arc-consistency of a position constraint between two objects in given orientations con­ sists of only one geometric sum and one geometric inter­ section. The complexity of such geometric operations de­ pends on the geometric representation of the regions, and on their geometric properties. For example, the geomet­ ric sum or the intersection of two convex polygons with p and q edges respectively can be computed in O(p + q) time [Preparata and Shamos, 1985].

With usual consistency techniques over finite domains, the consistency of a position constraint C would consist of checking C for every possible position of the concerned objects. In opposition to our approach, such usual con­ sistency techniques can't exploit the compactness of intensional geometric representations for the position set of the object.

4 Implementation

The proposed GCSP has been implemented in the AT­ LAS spatial planning system. Figure 6 shows the general architecture of ATLAS. The GCSP which has been pre­ sented in this paper constitutes the kernel of ATLAS. It updates the domain of objects by consistency. To exe­ cute geometric operations, it calls a geometric represen­ tation module. For considerations about the application in particular, a geometric representation by quadtrees has been implemented [Samet, 1989]. At the beginning of the solution, objects and constraints come from the problem specifications. Then, a rule-based system pro­ poses to add constraints in order to reduce the solutions space. When a conflict arises (i.e. when the problem is over-constrained), a failure handling method applies constraint substitutions in order to solve it. More infor­ mation about ATLAS may be found in [du Verdier and Tsang, 1991; du Verdier, 1992].

Although ATLAS has been tested in the field of microwave electronic equipment design, it is able to solve many spatial planning problems in £D applications where each object may have 4 possible orientations (0, 1r /2, 1r or 3?r /2) and 2 possible forms.

To compare ATLAS with other spatial planning sys­ tems, it has been experimented on common theoretical problems. In terms of search efficiency, results substan­ tiate the consistency approach for spatial planning prob­ lems, and show that the more the problem is constrained, the more filtering before backtracking is relevant. More­ over, in comparison with other spatial planning sys­ tems which use constraint satisfaction techniques, such as WRIGHT [Baykan and Fox, 1987], ATLAS requires less intermediate states to solve the same problems be­ cause the pruning is more effective (See section 5.1).

5 Discussion

5.1 Comparison with Other Works

Several spatial planning systems have used constraint satisfaction techniques in different application domains: WRIGHT for kitchen design [Baykan and Fox, 1987], PROTEAN to identify the 3D conformations of proteins [Hayes-Roth et al., 1986] and SIGHT-PLAN for layout of construction sites [Tommelein, 1989]. These systems represent the configuration set of an object as the carte­ sian product of one-dimensional domains (orientations

+ coordinates) in order to use basic consistency algo­ rithms over intervals. This type of representation is lim­ ited to parallelepipedic forms (rectangles in 2D), which thereby restricts the removal of inconsistent configura­ tions. Moreover, a geometric constraint is defined by a disjunction of one-dimensional constraints. For example, a "no-overlap" constraint is expressed with a disjunction of "above", "under", "left-of" and "right-of" constraints.

The proposed GCSP avoids these limitations. The geometric focus of our approach allows a rich expressiv­ ity. First, we are able to solve spatial planning problems with non rectangular forms. Second, since we represent non rectangular domains, more inconsistent values may be removed; therefore, pruning is more effective and the solution requires less intermediate states.

5.2 The Geometric Representation of Regions

Although in ATLAS a geometric representation by quadtrees has been implemented, the proposed approach imposes no particular geometric representations, and it can be applied for any D applications ( 1D, 2D, 3D . . . ). Discrete representations as well as continuous ones are available. However, to guarantee the convergence of the consistency algorithms, note that a continuous geomet­ ric representation leads us to introduce a threshold for domain reductions, under which reductions become in­ significant, and the propagation process stops. A par­ ticular geometric representation has to be chosen in ac­ cordance with geometric specifications of the problem and as well as with the efficiency of the following geo­ metric algorithms: union, intersection, complementary, geometric sum and symmetric.

6 Conclusions

A new representation for GCSP and its solution have been described. A uniform symbolic representation of position constraints, based on the configuration space approach [Lozano-Perez, 1983], is proposed to achieve conjunctions of constraints bearing on the same objects, and arc-consistency. The geometric focus of our ap­ proach allows a rich expressivity. In terms of complexity, it takes advantage of the compactness of intentional geo­ metric representations, with the same idea as consistency do over intervals.

Specific consistency algorithms, in opposition to gen­ eral ones over finite domains [Mackworth, 1977; Mohr and Henderson, 1986], exploit the internal structure of the domains of the variables (interval domains [Davis, 1987], hierarchical structured domains [Mackworth et al., 1985]) or the specificity of the constraints (functional and monotonic constraints [Deville and Van Hentenryck, 1991]). Our work contributes to this field of research in the case of geometric constraints.

Future research on this topic includes the solution of GCSPs with regions of variable forms. For example, in kitchen design, a furniture may have several possible forms. The idea is to consider region forms as additional variables of the GCSP with domains of possible values. The first difficulty consists of representing domains of possible forms, and the second one consists of taking into account such additional variables in the solution of the GCSP.

Acknowledgments

I would like to thank particularly Jean-Patrick Tsang and Simone Pimont who helped me shape these ideas, and for their useful comments on this paper.

A Expression of position constraints with a uniform "belong" relation

Intersection Constraints: A region ~ overlaps a re­ gion R; if the reference point o( i) of i belongs to the configuration space obstacles of Rj due to ~. denoted COR,(R;) [Lozano-Perez, 1983]:

Include Constraints: A region ~ is contained in a region R; if the reference point o( i) of i belongs to the configuration space interior of R; due to ~. denoted CIR.(R;) [Lozano-Perez, 1983]:

contain.t( R,, R;)

{:}

{:}

{:} o i E R; EB -R,

Distance Constraints A region ~ is at a minimal dis­ tance d to a region R; if ~ doesn't overlap a region given by an expansion of R;. For an euclidean dis­ tance, this expansion is the geometric sum of R; and a disc which radius is d, denoted Di.tk(d):

min-di.t

{:}

{:}

{:}

max-di.tt( R,, R;, d) {:}