Extending Consistent Domains of Numeric CSP

1 Introduction

This paper introduces a new framework for extending the domain of one variable in a consistent CSP 1 which is defined by a set of non-linear constraints over the re­ als. The aim is to offer the greatest freedom of choice of possible values for a variable to the designer of a CAD application. For example, one starts from the knowledge of a solution and tries to widen the varia­ tions of a variable. This problem occurs in a large class of electro-mechanical engineering and civil engineering applications, where extending the domain of a variable permits the tolerance of any associated component to be enlarged, and therefore to lower the cost of this compo­ nent. These problems are often under-constrained. So, what the user wants to know is a subset of the solu­ tions. For these applications, classical methods (e.g.,[7; 10]) , based on local consistencies and domain splitting, cannot ensure that a solution exists inside the arbitrarily small intervals they compute. Moreover, domain split­ ting is ineffective if the solution set is not a finite set of isolated solutions but a collection of intervals.

1 An introduction to CSP and numeric CSP can be found in [4; 7].

The framework we introduce here allows one to enlarge the domain of a variable while preserving the consistency of the CSP. Sam-Haroud and Faltings [9] have proposed an approach for computing safe solutions of non-linear constraint systems. Roughly speaking, they fill up the solution space with a set of consistent boxes 2 . Their approach could be used to extend the domain of one variable. However, the underlying costs in computation time and space are exponential.

The framework we introduce here is less general but it can be implemented efficiently. Before going into the de­ tails, let us outline our framework in very general terms. The main steps of the right extension 3 of the domain of a variable are:

1. Searching for a subset of the solution space; this solution space may be reduced to a single point;
2. Selecting of the variable the domain of which has to be extended;
3. Defining for each inequality of an extrema function that computes the left most solution of the selected variable in a space delimited by the domains of the other variables;
4. Finding the smallest solution of all extrema func­ tions.

The following example illustrates this process.

2 Their approach is based upon a classical method used in graphical computing for image synthesis (composition of shapes, of scenes) known as the 2k trees. The key idea is to classify portions of space in three categories: the black shapes contain no solution at all, the gray shapes contain solutions, but also contain points which are not solutions, and finally, the white shapes contain only points which are solution. The gray shapes are split into smaller one that are again classified into black, white and gray shapes; the decomposition process stops when the size of the shapes becomes smaller than a given value.

3 Throughout this paper, we will only consider the right extension since the left one can be computed in a symmetrical way.

Example 1 Let us consider the behavior of an electri­ cal shunt motor, the speed of which may be changed. The maximum speed can be up to 3 times the value of the min­ imum speed. We only consider two parameters of the mo­ tor: the torque Cu, and the rotation speed N. The motor cannot use more than a given power : N * Cu :S: P max. Moreover, the motor cannot operate above a given speed and torque: N E [1, 3], Cu E [0, 4].

We know that the motor is working efficiently for every tuple of values Dcu x DN in [0, 1] x [1 , 2] when Pmax = 5. What we want to compute is the maximum range of val­ ues of the torque which is safe with this motor. In other words, we are looking for the maximum domain Dcu such that every tuple in Dcu x D N is a solution of the constraint system.

Now, consider equation N * Cu = 5 in the space delim­ ited by N E [1, 3], Cu E [0, 4] . Its left most solution is the point defined by Cu = 2.5 and N = 2; this point is obviously an upper bound of the domain Dcu .

An initial subset of the solution space can often be found by experimentation. Note that the solution space may be reduced to a single point and the domains of the different variables may successively be extended.

The definition of the univariate extrema functions is a key point of our approach. Optimal univariate extrema functions can trivially be computed for the so-called primitive constraints. For non-primitive constraints, the methods used for computing Box- consistency [1] provide an efficient way to compute a safe approximation of uni­ variate extrema functions.

To define formally the extension of the domain of a vari­ able, we introduce an "internal" consistency, named i­ consistency, which ensures that every tuple in the Carte­ sian product of the variable domains is a solution of the constraint system. i-consistency should not be mistaken with arc consistency or approximations of arc consis­ tency [3] (e.g. 2B- consistency[7], Box-consistency[!]). Those consistencies define regions containing all the so­ lutions (and possibly tuples which are not solution) whereas i-consistency defines a region which is a subset of the set of solutions. Figure 2 shows the relations between these different families of consistencies. Roughly speaking, the smallest external box is the best approxi­ mation which can be computed by approximations of arc consistency over continuous domains.

Outline of the paper: Section 2 introduces the no­ tation and recalls the basics on CSP over continuous domains which are needed in the rest of the paper. Sec­ tion 3 is devoted to the description of the i- consistent extension process. Extrema functions are formally de­ fined and an efficient algorithm is introduced. Section 4 outlines the capabilities of our approach on a ballistic example.

2 Preliminaries

2.1 Notation

We use the following notations, possibly subscripted:

• x, y, z denote variables over the reals;
• u, v denote real constants;
• f, g denote functions over the reals;
• c denotes a constraint over the reals;

The next subsection recalls a few notions of numeric CSP; Details can be found in [2; 10; 3].

2.2 Interval constraint system

A k-ary constraint c is a relation over the reals.

Definition 1 (Interval) Let IF denote a finite sub­ set of R augmented with the two infinity symbols { -oo, +oo}. An interval [a, b] with a, bE IF is the set of real numbers { r E R I a :S: r :S: b}.

Definition 2 (CSP)

A CSP [8} is a triple (X, V,C) where X= {x1 , ... ,xn} denotes a set of variables, V = { Dx, , . .. , Dxn} denotes a set of domains, Dx, being the interval containing all acceptable values for x;, and C = { CI, ... , Cm} denotes a set of constraints 4 .

i5 denotes the Cartesian product Dx1 x ... , x Dxn. v denotes the tuple (vxu ... , vxJ such that v E i5. 1fx(v) denotes the projection over x of v. D; (resp. D;) denotes the lower bound (resp. upper bound) of the interval D;.

Definition 3 (k-box) A k-box h x ... x h is the part of a k-dimension space defined by the Cartesian product of intervals (h, ... , h)

By construction, all the k-boxes are convex.

2.3 Local consistencies

Local consistencies over continuous domains are based on arc consistency[8] which was originally defined for finite domains. This section introduces two local consistencies that will be used in the rest of the paper.

Definition 4 (arc consistency) A CSP P (X, V,C) is arc- consistent iff: '<IDx E V, 'ivx E Dx, 'r:/c E C : 3 v E i5 I 7f X ( v) = Vx (\ c( v)

Davis ([4]) has studied the application of the Waltz algorithm ([12]) over contin'llous domains and has shown important theoretical limitations. The Waltz algorithm was then extended by Faltings ([5; 6]) in order to deal with ternary constraints defined by continuous and dif­ ferentiable curves.

Definition 5 (Set Extension) LetS be a subset ofR. The approximation of S -denoted hull- is the small­ est interval I such that S ~ I.

2.4 Box-consistency

Roughly speaking, Box- consistency [1; 10] is a local con­ sistency over continuous domains which computes a safe approximation of the solution of each variable involved in a given constraint.

Definition 6 (Box-consistency) Let (X, V, C) be a CSP and c E C a k-ary constraint over the vari­ ables (xi, ... , Xk). c is Box- consistent if, for all x; in {XI, ... , xk} such that Dx; = [a, b], the following rela­ tions hold :

1. C(Dx1' ... 'DXi-1' [a, a+), Dxi+1' ... 'Dxk),

2. C(Dx1, . . . , Dx;_1, (b-, b], Dxi+1, ... , Dxk).

where a+ (resp. a-) corresponds to the smallest (resp. largest) number of IF strictly greater (resp. smaller) than a, and C stands for interval extension of c [3}.

The essential point is that the variable x is Box­ consistent for constraint f(x, XI, ... , Xn) = 0 if the bounds of the domain of x correspond to the leftmost and the rightmost 0 of the optimal interval extension of j(x, XI, ... , Xn)·

4 It is worthwhile to notice that the set of constraints C represents a conjunction of constraints that have to be sat­ isfied. Disjunctions may only occur inside a single constraint, e.g. the single constraint x 2 = y is equivalent to the disjunc­ tion (x = ,JY) V ( -x = ,fY).

3 Extension of the domain of a variable of a CSP

This section introduces the way a domain of a single vari­ able can be extended while preserving consistency of the whole CSP. We start by defining two local consistencies which are needed to characterize the extended domains.

Next, we formally define the univariate extrema func­ tions that actually compute the bounds of the i­ consistent extensions of the domain of a variable.

3.1 e-consistency

Various approximations of arc consistency (e.g. 2B­ consistency[7], Box-consistency[1]) have been intro­ duced for continuous domains. e- consistency is the best approximation of the solution space which can be com­ puted by these partial consistencies. For instance, e­ consistency corresponds to the "smallest external box" on Fig. 2. More formally, e- consistency is defined as follows:

Definition 7 ( e-consistency) Let P = (X, V, C) be an arc consistent CSP. A CSP P' = (X, V', C) is e­ consistent iff'r:/D~ E V': D~ =hull(Di)

In other words, a CSP P = (X, V, C) is e-consistent iff P' = (X, V', C) is arc consistent and D corresponds to the smallest box containing all values of V'. So, for inequality c, e- consistency on the corresponding equa­ tion Cequ (see section 3.4) yields a box which bounds the maximal extension that can be performed for any vari­ able occurring in c.

3.2 i-consistency

Definition 8 (i-consistency)

Let P = (X, V, C) be a CSP. P is i- consistent iff 'r:/c E C, 'r:/v E i5 : c( v)

In other words, a CSP P = (X, V, C) is i- consistent iff V only contains tuples which are solutions.

Example 2 Let P be the CSP defined by X = { x, y}, Dx = [-2, 2], Dy = [6, 12], C = {x 2 - y :S 0, -x 2 + 20 :S y}. This system is i-consistent :

'r:/(vx, Vy) E (Dx, Dy) : v; - Vy :S 01\ -v; + 20 :S Vy Now, we want to find the largest D~ ;:2 Dx such that the CSP defined by replacing Dx by D~ in P is i-consistent.

Figure 3 shows the original box and the extension of Dx. Both boxes are i-consistenf'. The domain of y re­ mains unchanged. B is the e- consistent box for equation x 2 = y and gives the upper bound of the extension of Dx.

Ward et al. [13] have proposed four kinds of interval propagation. One of them is related to i-consistency. Each interval Dx is labeled with one of these kinds:

5 Note that we could also perform a fruitful i- consistent extension of Dy to [6, 14] with the new box. But this ex­ tension of Dy is much smaller than the one we would have obtained if we had extended the initial box (Dy would have been extended to [4, 16]). In general, the result of successive extensions by i- consistency of several variables depends on the processing order of the variables.

"only", "every", "some" and "none" . If Dx is labeled "only" then solution tuples only take their values for x in Dx. If Dx is "every" then every value of x in Dx gives a tuple solution. If Dx is "some" then there exists at least one solution tuple such that x takes its value in Dx. If Dx is "none" then there is no solution tuple such that the value of x is in Dx.

Labelling every variable with "every" is what we call i- consistency. However, Ward et al. 's inference rules that allow computing labelled interval propagation do not consider the case where two variables are labelled "every" . Moreover, these inference rules assume strong monotony and continuity properties of the constraint system.

Now, we formally define what we mean by right i­ consistent extension.

3.3 Right i-consistent Extension of Dx Definition 9 (Right i-consistent extension of Dx)

Let P =(X, V,C) be a i-consistent CSP. P' =(X, V',C) is a right i- consistent extension of Dx for P iff:

• 'VDi E V \ {Dx}, Di = D~
• Dx c D~, D~ = Dx
• P' is i-consistent

Definition 10 (Maximal right extension)

Let P =(X, V,C) be a i-consistent CSP. P' =(X, V',C) is a maximal right i- consistent extension of Dx for P iff:

• P' is a right i- consistent extension of Dx for P;
• V P", such that P" is a right i- consistent extension of Dx for P, P" C P' 6

3.4 Extrema functions

Let c be an inequality, Cequ denotes the equation corre­ sponding to c. More precisely, if c is defined by an expres­ sion of the form f(xl , ... , Xn) :::; 0 or f(xl, ... , Xn) 2': 0, then Cequ denotes the equation f(xl , ... , Xn) = 0.

6 A CSP P (X, 'D,C) is smaller than a CSP P' = (X,'D',C) if 1) ~ V'. 1) ~ 1)' means Dx; ~ Dx: for all i E l..n.

F:;'in(x) (V) is an optimal extremum function of Cequ for variable x if Fcmin(x) (V) computes the smallest value of x which is a solution of Cequ 7 in the space delimited by v.

Definition 11 (Optimal extremum function)

Let P = (X, V,C) be a CSP, x a variable of X and c a constraint of C. The optimal extremum function of constraint Cequ for variable x is

By convention, Fcmin(x) (V) returns Dx when Cequ has no solution in the space delimited by V.

Definition 12 (Extremum function approximation)

Let P = (X, V, C) be a CSP, c a constraint of C and Fcmin(x) (V) an optimal extremum function of Cequ for variable x.

AF:;'in(x) (V) is a safe approximation of F:;'in(x) (V) iff: AFcmin(x) (V) < Fcmin(x) ('D)

3.5 Computing an i-consistent right extension of Dx for P

To define the right i-consistent extension of Dx for a CSP P =(X, V,C), we introduce two specific domains, named 'Dmax and 'Dext :

• 'Dmax is the set of initial domains where Dx has been set to [Dx, oo), i.e., 'Dmax = VD,+-(D.,oo)
• 'Dext is the set of initial domains where Dx has been extended to the value of the extremum function of constraint con x,

Next proposition defines the right i- consistent exten­ sion of Dx for a CSP P with only one single constraint.

Proposition 1 Let P = (X, V, { c}) be an i- consistent CSP with only one inequality constraint c and let x be a variable of X. Then, P = (X, V ext, { c}) is a maximal right i- consistent extension of Dx for P.

Proof:

We assume that c is not a tautology 8 which is true for any value of x. So it results from the definition of the extrema functions (definition 9) that we have either:

Since P is i-consistent, it results that 'Vv E 'Dext c(v).

Proposition 2 Let P = (X, V, C) be a i-consistent CSP. Let P' = (X, V', C) such that:

• 'VDi E V \ {Dx}: Di = D~

7 0f course, when Cequ is not defined in a subpart of 'D, Fcmin(x) (D) returns a value that is strictly smaller than the smallest value of Dx for which Cequ is not defined.

8 Tautologies can be removed in a pre-processing step.

• D~ = [Dx,mincEc(Fcmin(x)(Vmax)))

Then, P ' is a right i- consistent extension on x of P. Furthermore, P' is a maximal right i- consistent exten­ sion of P on x.

Proof: From proposition 1, it results that Vv E D', Vc E C : c(v). Since P is a conjunction of con­ straints, P' is i-consistent .

Let P" =(X, V" ,C) be ani- consistent extension of Dx for P =(X, V ,C). Assume that P' c P" and that:

• VD~' E V" \ {D"} · D' = D" 't X · 't 't
• D~ c D~
• D~ = D~ = Dx

Assume that ck is the constraint such that D~ Fcn;:in(x)(Vmax)· So, there exists v E Dmax such that ck is false, and that D~ < IIx ( v) ~ D~. Thus, P" is not i- consistent.

The algorithm in Figure 4 directly follows from prop­ erty 2. Note that this algorithm is much simpler than the framework introduced by Sam-Haroud and Faltings [9] to compute a local consistency. Both algorithms se­ lect relevant extrema from all extrema including intersec­ tions between several curves and intersections between curves and interval extremities. However, in our case, the relevant extrema is simply the left most one since we start from an initial i-consistent box (so we know which portion of the space is a solution) and we extend only one variable domain to the right. This algorithm only searches for the left most extrema, thus, it is linear if the extrema functions can be computed in constant time. The next section shows that the left most extrema can be computed very efficiently.

3.6 Computing extrema functions

Optimal extrema functions for variable x of constraint c can trivially be computed if c is either a monotonic on x, or if Dx can be decomposed in subdomains where c is monotonic on x. Such constraints are usually called primitive constraints[3]. The set of primitive constraints is infinite and includes the following constraints: { x = y,x ~ y ,x < y,x f. y,z = x + y,z = x * y,x = -y,y = sin(x) , y = cos(x) , y = e"', y = abs(x) , z = xY , .. . }.

Example 3 The constraint x 3 = y is primitive: the right extrema function for x is :

For a non-primitive constraint c, we will approximate the e- consistent box for Cequ in the space delimited by domains VDz+-Dmaz. The methods introduced to com­ pute Box-consistency provide an efficient way to compute such a safe approximation of Fcmin(x) CD max). The key observation is that extrema functions are univariate functions which can be tackled by the Newton method implemented in the Box-consistency.

So, consider the i-consistent extension of Dx for CSP P = (X, V, C) and an inequality c E C. To compute a safe approximation of the extrema functions for x of constraint c, we could just com­ pute a Box-consistent interval for x with regard to Cequ. Box- consistency would yield an interval D~ such that IIx(sol(Cequ, Vmax)) C D~. Thus, Dx = AF;'in(x)(Vmax).

As a matter of fact, a complete computation of Box­ consistency is not required. The LNAR procedure [11] used in Box- consistency finds the left most zero of the interval extension of the univariate function on x derived from Cequ by replacing all variables but x by their do­ mains. Of course, when the function i-extension (see. fig. 4) uses approximations of extrema functions, the i- extension of the domain of x may not be maximal.

4 A ballistic example

In this section, we give a small ballistic application which illustrates the capabilities of our system. The problem consists of finding the maximum mechanical tolerances when an object is launched in a uniform gravitational field §, with an initial speed ~ which has an incidence a with the ground (see fig. 5).

The strong requirement is that the object must fall inside a predefined interval.

4.1 Modeling of the problem

The initial speed and incidence of the bullet can be stated as follows:

These equations give the impact point (x1 ,y1) of the bullet when t = t1 and YJ = 0: t = Vy~

4.2 Computing i-consistency extension of Da

The target is defined by the interval [220, 250]. Now, as­ sume that the bullet falls on the target when a E [32, 35] and V E [49.2, 50.1]. So the initial i- consistent box is defined by :

Va E Da:

To extend Da to the right by i- consistency, we have to check whether the box at the right of the i- consistent box is i- consistent. Thus, we have to find the left most bound of Da for Cequ and c~qu with Dmax = [35, 90]. To find these bounds, we have used Numerica [10] to compute Box- consistent intervals for Cequ and c~qu. The left most bound of these intervals respectively are 58.4 and 38.4. So, Da can be extended by i- consistency to interval [32, 38.4] (see Fig. 6).

Now, consider the three dimensional version of this problem where the target is defined by a rectangular area of space Rx x Ry x Rz such that 220 :S Rx :S 250, Ry = 0 and -50 :S Rz :S 50. Let (3 be the angle between x and the projection of V on the plane defined by y = 0. We know that the box defined by Da = [34, 35J,Dv =

To extend (3 by i- consistency, we have computed with Numerica the Box- consistent intervals for the equations derived from the following inequalities :

The left most bound of these intervals is 1.4; thus, D13 can be extended by i- consistency to the interval [0, 1.4].

[49.2, 50.1] and D13 = [0, OJ is i- consistent. 220 :S 9 _~ 1 * V 2 *sin( a)* cos(a) * cos((J) 250 2: 9 _~ 1 * V 2 *sin( a)* cos( a)* cos((J) -50 :S 9 _~ 1 * V 2 *sin( a)* cos( a)* sin((J) 50 2: 9 ~ 1 * V 2 *sin( a)* cos( a)* sin((J)

5 Conclusion

This paper has introduced an effective framework for extending the domain of one variable in an already con­ sistent CSP. Extending the domain of one variable is a critical issue in applications where the tolerance of a component determines its cost.

Contrary to Ward et a! [13] we do not impose any re­ strictions on the form of the constraints. The approach suggested by Sam-Haroud and Faltings [9] is more gen­ eral since they do not know an initial solution but its computation cost is very high. The key point of our framework is the definition of univariate extrema func­ tions which can be computed efficiently.

An interesting way to explore concerns maximizing the size (or volume) of i-consistent boxes.

Acknowledgements

Thanks to Gilles Trombettoni for his careful reading and helpful comments on earlier drafts of this paper. Thanks also to Olivier Lhomme, Jean-Paul Stromboni and Alexander Semenov for interesting suggestions.