Thierry Petit
email: tpetitg@ilog.fr

Jean-Charles R Egin

Christian Bessi Ere

Range-Based Algorithm for Max-CSP

A Max-CSP consists of searching for a solution which minimizes the number of violated constraints. The best existing solving algorithm is PFC-MRDAC. It is based on the computation of a lower bound of the number of violations. This lower bound is obtained by evaluating the violations involved by each value of each domain. Unfortunately, some applications imply thousands of variables with huge domains. In scheduling, it arises that numerous activities have to be scheduled over several month with a unit of time of a few minutes. In this situation using PFC-MRDAC requires a large amount of memory which can prevent from using it. In this paper, we propose an algorithm called the Range-based Max-CSP Algorithm (RMA), based on the exploitation of bound-based ltering algorithms of constraints. This technique does not require to study each value of each domain: its complexity depends only on the number of variables and the number of constraints. No hypothesis is made on the constraints except that their ltering algorithms are related to the bounds of the involved variables, the general case of scheduling constraints. Then, when the only information available for a variable x w.r.t. a constraint C are the new bounds of D(x) obtained by applying the ltering algorithm of C, the lower bounds of violations provided by PFC-MRDAC and RMA are identical.

Introduction

A problem is over-constrained when no assignment of values to variables satis es all constraints. The simplest theoretical framework for over-constrained problems is the Maximal Constraint Satisfaction Problem (Max-CSP). A solution of a Max-CSP is a total assignment of values to variables that minimizes the number of constraint violations.

The best solving algorithm for Max-CSP, PFC-MRDAC 1], has been extended to the non binary case 4,5, 3]. Moreover, in 4, 5] it has been shown that a Max-CSP can be encoded through a global constraint. When we de ne a Max-CSP as a global constraint, then we use the PFC-MRDAC algorithm as the ltering algorithm of the constraint. This formulation is suited to real-life problems, because generally some parts correspond to Max-CSPs although the whole problem cannot be expressed as a Max-CSP. Moreover any search algorithm can be used. Therefore we selected it to describe the algorithms presented in this paper.

For sake of clarity, we consider rst that a Max-CSP is solved by a Branch and Bound based search algorithm : successive assignments of values to variables are performed through a depth-rst traversal of the search tree, where internal nodes represent incomplete assignments and leaf nodes stand for complete ones. The number of violations to minimize is expressed by an objective variable obj. For any given node, UB = max(D(obj)) + 1 corresponds to the number of violations of the best solution found so far. That is, the solution we would like to improve. min(D(obj)) is the number of violated constraints in C detected by the solver at the current step of the search. In fact, min(D(obj)) can be simply de ned as the number of constraints C such that values have been assigned to all variables in the set var(C) of the variables involved in C, and C is violated. This number is generally called the distance. If distance > max(D(obj)) then the current best solution cannot be improved below the current node. Thus it is not necessary to traverse the sub-tree rooted by the current node.

PFC-MRDAC improves that condition by computing a lower bound LB of the number of violations, equal to distance plus an under-estimation of the number of violations entailed by constraints involving some variables which have not yet been instantiated. The new condition of pursuit of the search is LB max(D(obj)). When ltering, PFC-MRDAC combines generally LB with a lower bound local to each value, in order to remove this value if it cannot belong to a solution.

All these lower bounds are based on direct violations of constraints by values: they require to maintain for each value a of the domain of a variable x the number of constraints C such that a is not consistent with C. This principle is applicable to a wide number of problems, providing that domain sizes are not too big.

Unfortunately, some applications involve a big number of variables with huge domain sizes.

For instance, consider the problem of scheduling the construction of o ces. Some activities, as painting or installing windows, have a short duration and require essentially human resources. They can be performed over a large period. They concern each o ce of each oor in each building, and they are linked to other activities by precedence rules. Given that the manager has to deal with a large number of workers which express preference constraints with respect to their week schedule, it is mandatory to have a time unit of at most one quarter of hour. If the total duration of the project is one year then for each activity we have 35040 possible start dates. If there exists thousands of activities then it is not realistic to maintain for each possible date of each activity a counter of inconsistencies. Moreover, since scheduling constraints generally propagate on bounds, redundant computations will be made when testing the consistency of each value of a domain with a constraint. Therefore, PFC-MRDAC is not really suited to this case.

In this paper, we propose a new algorithm called the Range-based Max-CSP Algorithm (RMA), which computes a lower bound by exploiting ltering algorithms of constraints1 . The principle is similar to PFC-MRDAC except concerning the computation of inconsistencies involved by each variable. Instead of evaluating each value of a domain D(x), the RMA stores two entities per constraint C in which x is involved: the new minimum and maximum of D(x) obtained when applying the ltering algorithm of C. For instance, for 100 variables with domains of 35040 values and 100 constraints, the RMA requires to maintain 200 minima and maxima per variable instead of 35040 in PFC-MRDAC. That is, instead of having a total of 3:5 millions of counters with PFC-MRDAC we have 20000 datas with the RMA.

We show that in the case of constraints which propagate only bounds of domains, the same LB is obtained by using PFC-MRDAC and the RMA.

We compare the complexity of a non incremental implementation with PFC-RDAC2 : when domain sizes are big the amortized complexity of the RMA is better because it does not depends on the number of values of domains.

We provide a ltering algorithm based on the same principle, which propagate on bounds. We discuss about the incremental version of the RMA and about a ltering algorithm which performs holes in domains. We point out a promising generalization of our algorithm: for general problems, it is possible to take into account ranges of succesive values involving the same number of violations to compute the lower bounds.

Preliminaries

CSP A constraint network N is de ned as a set of n variables X = fx 1 ; : : :; x n g, a set of domains D = fD(x 1 ); : : :; D(x n )g where D(x i ) is the nite set of possible values for variable x i , and a set C of constraints between variables. A constraint C on the ordered set of variables var(C) = (x i1 ; : : :; x ir ) (also denoted by C(x i1 ; : : :; x ir )) is a subset rel(C) of the Cartesian product D(x i1 ) D(x ir ) that speci es the allowed combinations of values for the variables x i1 ; : : :; x ir . D(var(C)) = x2var(C) D(x). An element of D(x i1 The variables S C] are used in order to express which constraints of C must be violated or satis ed: value 0 assigned to s 2 S C] expresses that its corresponding constraint C is satis ed, whereas 1 expresses that C is violated. Throughout this formulation, a solution of a Max-CSP is an assignment that satis es the ssc with the minimal possible value of obj. Comparing a lower bound of the objective to max(D(obj)) of a Max-CSP leads to a necessary consistency condition of the ssc. Domain reduction algorithms for the Max-CSP correspond to speci c ltering algorithms of the ssc.

3 Generalized version of PFC-MRDAC PFC-MRDAC 1] is considered as the best algorithm for solving binary Max-CSPs. This section is a summary of the generalization of this algorithm to non-binary constraints 4,5,3]. Basically, PFC-MRDAC is based on counters of violations involved by each value of each domain :

De nition 2 Let x be a variable, a be a value of D(x), C be a set of constraints, #inc((x; a); C) = jfC 2 C s.t. (x; a) is not consistent with Cgj.

In a solver, this information can be obtained by applying independently the speci c ltering algorithms of the constraints in which x is involved while the domain of x is reduced to the value a we study.

Necessary condition of consistency

From the de nition of minObj(C; S C]) we have:

Property 1 If minObj(C; S C]) > max(D(obj)) then ssc(C; S C]; obj) is not consistent.
A lower bound of minObj(C; S C]) provides a necessary condition of consistency of a ssc. A possible way for computing it is to perform a sum of independent lower bounds of violations, one per variable. For each variable a lower bound can be de ned by:

De nition 3 Given a variable x and a constraint set K, #inc(x; K) = min a2D(x) (#inc((x; a); K)).

The sum of these minima with K = C cannot lead to a lower bound of the total number of violations, because some constraints can be taken into account more than once. In this case, the lower bound can be overestimated, and an inconsistency could be detected while the ssc is consistent.

In the binary case, the constraint graph 3 is used in order to guarantee this independence 1]. Each edge is oriented and for each variable x only the constraints out-going x are taken into account.

This idea can be generalized to the non binary case, by associating with each constraint C one and only one variable x involved in the constraint 4,5]: C is then taken into account only for computing the #inc counter of x. Therefore, the constraints are partitioned according to the variables that are associated with:

De nition 4 Given a set of constraints C, a var-partition of C is a partition P(C) = fP(x 1 ); :::; P (x k )g of C in jX(C)j sets such that 8P(x i ) 2 P(C) : 8C 2 P(x i ); x i 2 X(C). Given a var-partition P(C), the sum of all #inc(x i ; P (x i )) is a lower bound of the total number of violations, because all sets belonging to P(C) are disjoint; thus we obtain the following lower bound:

LB P(C) = X xi2X(C) #inc(x i ; P(x i ))
Property 2 8P(C) = fP(x 1 ); :::; P (x k )g, LB P(C) minObj(C; S C]). 3 the graph where vertices are variables and edges are binary constraints between pairs of variables.

The necessary condition of consistency of a ssc is deduced from this Property:

Corollary 1 8P(C) = fP(x 1 ); :::; P (x k )g, If LB P(C) > max(D(obj)) then ssc(C; S C]; obj) is not consistent. It can be applied in the general case 4,5, 3]. In order to do so, we suggest to split C into two disjoint sets P (x) and C P (x), where P (x) is the subset of constraints associated with x in a var-partition P(X) of C. Consider the following corollary of Theorem 1:

Corollary 2 Let P(X) be a var-partition of C, x a variable and a 2 D(x), if minObj((x; a); P (x); S P (x)]) +minObj((x; a); C P (x); S C P (x)]) > max (D(obj)) then (x; a) is not consistent with ssc(C; S C]; obj). Proof: e.g., 5].

Note that minObj(C P (x); S P (x)]) minObj((x; a); C P (x); S P (x)]).

From this remark and Properties 2 and 3 the following theorem can be deduced:

Theorem 2 8P(C) a var-partition of C; 8x 2 X(C); 8a 2 D(x), if #inc((x; a); P(x)) + LB P(C P(x)) > max(D(obj)) then a can be removed from D(x). [START_REF] R Egin | An original constraint based approach for solving over constrained prolems[END_REF] The Range-based Max-CSP Algorithm

Principle

PFC-MRDAC algorithm requires to maintain one counter #inc ((x; a); P (x)) for each value a of each domain D(x). The computation of these counters is su cient to e ciently compute the consistency of a satis ability sum constraint (see Corollary 1) and to apply the ltering algorithm associated with it (see Theorem 2). Therefore, the main issue of the PFC-MRDAC algorithm is the computation of these counters, and if this coumputation is speed-up then the algorithm is improved.

We propose a new algorithm called the Range-based Max-CSP Algorithm (RMA) that does not require one counter per value although the principle is very similar to the non binary PFC-MRDAC: for each variable x we consider a set P(x) of a var-partition of constraints P(C), in order to compute a lower bound #inc(x; P(x)) of the violations involved by x.

The di erence is the way we compute #inc(x; P (x)). In the RMA, there is no need to maintain one counter of violation #inc((x; a); P (x)) for each value a in D(x) as it is the case in PFC-MRDAC.

The idea exploited in our algorithm is based on the following de nition:

De The proof of this property is obvious (from de nition 5).

It is possible to take into account only a set of homogeneously inconsistent ranges to compute #inc(x; P (x)), provided that each value of D(x) belongs to one range. More formally, we have: De nition 6 A set I(P(x)) = fI 1 ; :::; I m g of homogeneously inconsistent ranges such that 8a 2 D(x); 9I 2 I(P(x)) and a 2 I is called a set of homogeneously inconsistent ranges which covers D(x).

Property 5 Let I(P(x)) be a set of homogeneously inconsistent ranges which covers D(x). Then we have: #inc(x; P (x)) = min I2I(P(x)) #inc(I; P (x)).

proof: from Property 4 Thus, if we are able to identify such a set I(P(x)) with jI(P(x))j < jD(x)j then it is possible to improve PFC-MRDAC in two ways:

1. the number of counters required to compute #inc(x; P (x)) is smaller, 2. #inc(x; P (x)) can be computed faster. The rst point is quite important in practice. Indeed, in some problems the number of variables and the size of the domains make methods requiring for each value of each variable some additional data, as #inc((x; a); P (x)), unusable in pratice. For instance, this is the case of almost all real world scheduling applications. Moreover, in such problems, the ltering algorithms associated with constraints are range-based ltering algorithms: they reduce only the bounds of the domain. They do not create any \holes" in domains. Such a range-based approach is interesting if some issues can be e ciently solved: { the number of ranges is small, { for each range I, #inc(I; P(x)) can be e ciently computed.

In the remaining of this section, we will consider that only range-based ltering algorithms are used. Under this condition, we will prove that: { the size of I(P(x)) is at most 2 jP(x)j + 1, { all #inc(I; P (x)) can be computed in O(jP (x)j) provided that we have computed I(P(x)).

Computation of #inc counters

The principle is to consider the bounds obtained by applying independently each ltering algorithm of constraints in P (x) on D(x):

Notation 2 Let P(C) be a var-partition, x a variable, P(x) 2 P(C) and C 2 P(x): D(x) C is the domain obtained by applying the ltering algorithm of C on D(x).

For each constraint C we consider the minimum min(D(x) C ) and the maximum max(D(x) C ) of D(x) C . By ordering all these minima and maxima from the lower to the greater, it is possible to divide D(x) in di erent ranges. Each of them corresponds to a certain number of violations. The following gure illustrates an example where P (x) is the set of constraints fC 1 ; C 2 ; C 3 g, which involve four variables x, y, z, t such that D(x) = D(y) = D(z) = D(t) = 0; 10]: { C 1 = x y > 5] that leads to min(D(x) C1 ) = 6, max(D(x) C1 ) = 10, { C 2 = x z > 7] that leads to min(D(x) C2 ) = 8, max(D(x) C2 ) = 10, { C 3 = t x > 7] that leads to min(D(x) C3 ) = 0, max(D(x) C3 ) = 2. For this example the homogeneously inconsistent ranges are 0; 3); 3; 6); 6;8); 8; 11) and #inc(x; P (x)) = #inc(x; P (x)) = min I2I(P(x)) #inc(I; P (x)) = min(#inc( 0; 3); P (x)) = 2; #inc( 3; 6); P(x)) = 3; #inc( 6; 8); P(x)) = 2; #inc( 8; 11); P(x)) = 1) = 1. Now, we present more formally, this idea: De nition 7 Let B(P(x)) be the set of bounds sorted in ascending order, dened by the bounds of D(x) and the bounds of domains D(x) C for all constraints C in P (x). We will denote by I(B(P(x))) the set of ranges such that each range is de ned by a pair of two consecutive elements of B. The k th range of I(B(P(x))) is denoted by I k = p; q), where p is the minimum of I k and q 1 is the maximum. Property 6 The following properties hold: 1. the maximal possible number of ranges in I(B(P(x))) is 2 jP(x)j + 1 2. 8a 2 D(x) 9I 2 I(B(P(x))) such that a 2 I 3. 8I 2 I(B(P(x)))8C 2 P (x) : I D C (x) or I \ D C (x) = ; 4. 8I 2 I(B(P(x))), I is homogeneously inconsistent. 5. I(B(P(x))) is a set of homogeneously inconsistent ranges which covers D(x). proof:

1. B(P(x)) contains at most 2 jP(x)j + 2 values, thus the maximum number of ranges is 2 jP(x)j + 1. 2. By construction of I(B(P(x))) 3. Suppose that I \D C (x) = J with J 6 = ; and J I. Then, one bound of J is equal to a bound of D C (x) and is not equal to a bound of I. So, I contains a bound of D C (x) which is not one of its bounds. This is not possible by construction of I(B(P(x))). The problem is then to compute the value #inc(I; P (x)) for each I 2 P (x)).

It is not possible to compute independently each #inc(I; P (x)) in O( 1), but we will show that all #inc(I; P (x)) can be computed in O(jP (x)j). Therefore, since jI(B(P(x)))j 2 jP(x)j+ 1, the amortized complexity for an #inc(I; P (x)) is O [START_REF] Larrosa | Maintaining reversible DAC for Max-CSP[END_REF].

The following property helps us to compute all #inc(I; P (x)) in O(jP (x)j). This idea has to be re ned, given that a value in D(x) may correspond to minima or maxima of several D(x) Ci . Therefore we count the number of minima of domains equal to a, and maxima of domains equal to a 1. From this proposition and Property 7 the following property holds:

Property 8 Given I = p; q). Then, #inc(I; P (x)) = jP(x)j #sat(I; P(x)). Consider again the previous example in order to illustrate this principle:

Interval Ik #sat(Ik; P(x)) #inc(Ik; P(x))

I1 = 0; 3) 0 + 1 -0 = 1 2 I2 = 3; 6) 1 + 0 -1 = 0 3 I3 = 6; 8) 0 + 1 -0 = 1 2 I4 = 8; 11) 1 + 1 -0 = 2 1
We deduce #inc(x; P (x)) = min I2P(x) (#inc(I k ; P (x)) = 1.

Algorithm 1 is a possible implementation of the computation of #inc counters.

Algorithm 1: ComputeMinInc Data : x; P(x);B(P(x)); I(B(P(x))) Result : #inc(x; P(x)) #sat 0; #inc(x;P(x)) jP(x)j; k 1; while k 6 = jI(B(P(x)))j do let Ik = p; q) be the k th range of I(B(P(x)));

#sat #sat + nMin(p; B(P(x))) nMax(p 1; B(P(x)));

if jP(x) #satj < #inc(x;P(x)) then #inc(x;P(x)) jP(x) #satj;

k k + 1 end end return #inc(x; P(x));

Consistency of a ssc

The LB P(C) is computed by performing a sum of all #inc(x; P (x)), following a schema similar to PFC-MRDAC. Note that the LB provided by PFC-RDAC and RMA are the same when ltering algorithms reduce only the bounds of the domains.

Compared with PFC-MRDAC, the computation of the lower bound LB P(C) of Property 2 remains the same. Thus, we have: LB P(C) = P xi2X(C) #inc(x i ; P(x i )). The di erence is the computation of all #inc(x i ; P (x i )). Complexity In order to compare the complexity of checking the consistency of a ssc with RMA and with PFC-RDAC (the non incremental version of PFC-MRDAC 2]), we insist on the fact that the principle is the same except for computing the #inc(x; P (x)). Consequently, we compare the procedure Com-puteMinInc with the method used in PFC-RDAC for computing #inc(x; P (x)): Notation 4 We denote by : { d the maximal domain size: max x2X (jD(x)j), { p the maximal size of a set in the var-partition: max P(x)2P(C) (jP (x)j), { f the maximal complexity of a ltering algorithm of a constraint C applied on a domain D(x) (useful either to know if a value a 2 D(x) is consistent with a constraint C, in this case we call the algorithm D(x) = fag, or to compute D(x) C ).

In PFC-RDAC, a counter #inc((x; P (x); a)) of violations involved by each value a of D(x) is computed. Thus, for each a 2 D(x) the complexity is O(f jP(x)j); and then we iterate over all such counters to determine the minimal one, #inc(x; P (x)). Finally the complexity is O(jD(x)j f jP(x)j).

In RMA, the ltering algorithm of each constraint is called only once. That is, jP(x)j f. We sort the jP(x)j 2 + 2 bounds to compute I(B(P(x))): O(jP (x)j log(jP(x)j)); and we iterate on them to determine #inc(x; P (x)). Finally the complexity is O(jP (x)j log(jP (x)j) + f jP(x)j).

To obtain LB, these computations will be performed at most n times (n is the number of variables). Since P xi2X(C) (jP (x i )j) = jCj we have:

PFC-RDAC RMA #inc(x;P(x)) O(jD(x)j f jP(x)j) O(jP(x)j log(jP(x)j) + f jP(x)j)

Filtering Algorithm

In this section we propose to apply the principle described in previous sections to lter domains.

It is important to note that if only range based ltering algorithms are associated with the constraints then it is useless to introduce a ltering algorithms which is able to create \holes" in the domains, because this \holes" will not be used by the other algorithms. However, this can have an interest to the search heuristic which can be based on the number of remaining values in the domains of the variables. Therefore, we rst propose an algorithm which reduce only the bounds.

Following the schema of PFC-MRDAC (see Theorem 2), we will take into account the lower bound corresponding to all sets in the var-partition P(C) except P(x): LB P(C P(x)) . As in PFC-MRDAC, viability of values will be evaluated according to max(D(obj)):

Theorem 3 Let I 2 I(B(P(x))). If #inc(I; P (x)) + LB P(C P(x)) > max(D(obj))

then all values in I can be removed from D(x).

proof: I is homogeneously independent thus any value in I violated the same number of constraints. From theorem 2 the theorem holds.

The algorithm is based on this theorem: starting from I = min(D(x)); q), we remove successive ranges while the condition of Theorem 3 is satis ed; and similarly, from the maximum of D(x): starting from I = p; max(D(x)) + 1), we remove successive ranges while the condition of Theorem 3 is satis ed.

This algorithm can be slightly modi ed in order to obtain further domain reductions, that is, to create \holes" in the domain: for each range, Theorem 3 is applied and values are accordingly modi ed.

These algorithms have the same worst case complexity, and the gain in regards to PFC-MRDAC is similar as for the consistency checking.

Once again, if the ltering algorithms associated with soft constraints are range based algorithms, the second algorithm and PFC-MRDAC will lead to the same domain reduction.

Incrementality

Until now, we considered that all the computations are done from scratch. In this section, we propose to study the incremental behavior of RMA.

After some modi cations of domains of variables, the ltering algorithm associated with one constraint C 2 P (x) may reduce the domain of x in a di erent way than the previous one. In this case, some operations have to be done in order to accordingly update #inc(x; P (x)). Let us study in detail what append when a constraint leads to a new domain reduction of D(x). Suppose that the previous was p; q] and the new is p 0 ; q 0 ]. Necessarily we have p 0 p and q 0 q. Consider the current set I(B(P(x))).

This set has to be updated.

We will consider the modi cation due to p 0 . If p 0 = p then there is no modication thus we will study only p 0 > p.

Let I k = p; r) 2 I(B(P(x))) and I l = s; q + 1) 2 I(B(P(x))) Two cases must be studied: p 0 r and p 0 > r. p 0 r: If nMin(p; B(P (x))) > 1 then I k is splitted into two sets: I k1 = p; p 0 ) and I k2 = p 0 ; r) with #sat(I k1 ) = #sat(I k ) 1 and #sat(I k2 ) = #sat(I k ). Thus #inc(x; P (x)) can be immediatly updated. If nMin(p; B(P (x))) = 1 then the ranges I k 1 = o; p) and I k are modi ed as follows: I k 1 = o; p 0 ) with #sat(I k 1 ) #sat(I k 1 ) 1 and I k = p 0 ; r) with #sat(I k ) #sat(I k ). Thus #inc(x; P (x)) can be immediatly updated. p 0 > r: Consider the range I l which contains p 0 . If nMin(p; B(P (x))) > 1 then I k is not changed but #sat(I k ) #sat(I k ) 1 and the set I l is modi ed as in the previous case. Thus, #inc(x; P (x)) can be immediatly updated. If nMin(p; B(P (x))) = 1 then the ranges I k 1 = o; p) and I k are merged into one range o; r) with #sat( o; r)) = #sat(I k ) 1 and the set I l is modi ed as in the previous case. Thus, #inc(x; P (x)) can be immediatly updated.

The same kind of reasoning can be applied for q 0 and q.

The complexity of this method depends on the time needed to nd the range containing a speci c value. If each constraint C of P (x) contains the range starting by D(x) C and the range ending by D(x) C , then at most jD(x)j operations are required to nd the searched range. However, the maximal number of ranges is in O(jP(x)j). In the worst case, and for only one constraint: O(min(jP (x)j; jD(x)j)) tests are needed, but for k constraints a more sophisticated algorithm should be designed in order to reduce the global complexity.

Therefore, #inc(x; P (x)) can be e ciently updated in O(min(jP (x)j; jD(x)j))

when the ltering algorithm associated with one constraint of P(x) lead to a new domain. This complexity is certainly not optimal and could be improved.

Discussion

The method we propose can be used when:

1. domains are not range 2. ltering algorithm associated with constraints are not range based algorithm

Domains are not range

We can either consider that domains are ranges even if they are not, or directly deal with such domains.

In the rst case, this means that we consider a relaxation of the domains and, then, RMA is still valid but it is no longer equivalent to PFC-MRDAC.

In the second case, we consider that a domain is a union of ranges. RMA can be applied, but the complexity of this algorithm will change because each range of a domain has to be taken into account. Thus, the number of ranges in I(B(P(x))) is accordingly changed and also the complexity of the algorithm.

If a domain contains r ranges then the new complexity when only range based ltering algorithms are used becomes:O(jP (x)+ rj log(jP(x)+ rj)+ f jP(x)+ rj). Therefore, this method is better than PFC-MRDAC if log(jP(x)j + r) O(jD(x)j).

General ltering algorithms

The application of a ltering algorithm for a constraint may lead to domains which are not ranges. That is, a domain will no longer correspond to one range, but to several ranges. Then, two possibilities can be studied: the \holes" in the domain are ignored or the algorithm will deal with the set of ranges corresponding to each domain. In the rst case, RMA is still valid but it is no longer equivalent to PFC-MRDAC. In the second case, RMA is equivalent to PFC-MRDAC, but the complexity is changed. In fact, the number of ranges corresponding to a domain have to be taken into account. The complexity becomes: O((jP (x)j + P r i ) log(jP (x)j + P r i ) + f (jP (x)j + P r i )) where r i is equal to the number of ranges required to represent the domain of x when the ltering algorithm associated with C i 2 P (x) is applied. Roughtly, this method is better than PFC-MRDAC if log(jP (x)j + P r i ) O(jD(x)j).

Conclusion

In this paper, we propose an alternative to PFC-MRDAC called the Range-based Max-CSP Algorithm (RMA), based on the exploitation of bound-based ltering algorithms of constraints. This technique does not require to study each value of each domain: its complexity depends only on the number of variables and the number of constraints. When the only informations available for a variable x w.r.t. a constraint C are the values of bounds of D(x) when the ltering algorithm of C is applied, the lower bounds provided by PFC-MRDAC and RMA are identical and RMA outperforms PFC-MRDAC algorithm.

Some variations of RMA are also studied in order to deal with general cases: domains which are not ranges, ltering algorithms associated with constraints which are not range based algorithms and so on... For each case we show the advantages and the drawbacks of our new method.

  (si = 0)) _ (:Ci ^(si = 1))] Notation 1 Given a ssc(C; S C]; obj), a variable x, a 2 D(x) and K C: max(D(obj)) is the highest value of current domain of obj; min(D(obj)) is the lowest value of current domain of obj; minObj(C; S C]) is the minimum value of obj consistent with ssc(C; S C]; obj); minObj((x; a); C; S C]) is equal to minObj(C; S C]) when x = a; S K] is the subset of S C] equals to the projection of variables S C] on K; X(C) is the union of X(C i ); C i 2 C.

3. 2

 2 Filtering algorithm PFC-MRDAC 1] and its extension to the non binary case 4,5, 3] include a look-ahead procedure used to reduce domains of variables that have not yet an assigned value. From de nition of minObj((x; a); C; S C]) we have the following theorem: Theorem 1 8x 2 X(C); 8a 2 D(x): if minObj((x; a); C; S C]) > max(D(obj)) then (x; a) is not consistent with ssc (C; S C]; obj). Any lower bound of minObj((x; a); C; S C]) can be used to check the consistency of (x; a). An obvious lower bound is #inc((x; a); C): Property 3 #inc((x; a); C) minObj((x; a); C; S C]) From this Property and theorem 1, we obtain a rst ltering algorithm. It can be improved by including the lower bound of Property 2. This idea was introduced by Larrosa et al. 1], for binary constraints networks.

  nition 5 Let I D(x) be a range of consecutive values. If 8a 2 I, 8b 2 I, #inc((x; a); P (x)) = #inc((x; b); P (x)) then I is homogeneously inconsistent. If any value in a range I violates the same number of constraints of P(x) then we can consider globally the range to evaluate the number of violations, instead of studying the values one by one: Property 4 Let I be an homogeneously inconsistent range. The number of constraints in P (x) violated if D(x) = I is #inc(I; P (x)) = #inc((x; a); P (x)); a 2 I.

4 .

 4 By 3 8C 2 P (x) and 8a; b 2 I : a \ D C (x) = b \ D C (x). Therefore, 8a 2 I #inc((x; a); P (x)) = #inc(I; P (x)). 5. Immediate from 2 and 4.

Property 7 #

 7 inc(I; B(P (x))) = jP(x)j jfC=D C (x) \ I = Igj proof: #inc(I; B(P (x))) = jfC=D C (x)\I = ;gj and by Property 6.3 jfC=D C (x)\ I = ;gj + jfC=D C (x) \ I = Igj = jP(x)j The ranges I(B(P(x)) are traversed w.r.t. the ascending order, applying for each I K = a; b) the following rules to determine how many constraints are satis ed: { if a is a minimum of a domain D(x) C then we enter in a new D(x) C and the range I k satis es one constraint more than the previous one, I k 1 .{ if a 1 is a maximum of a domain D(x) C : we close a domain D(x) C and I k satis es one constraint less than I k 1 .

Notation 3

 3 Given a 2 D(x). { nMin(a; B(P (x))) denotes the number of domains D(x) C 2 B(P (x)) such that min(D(x) C ) = a, { nMax(a; B(P (x))) denotes the number of domains D(x) C 2 B(P (x)) such that max(D(x) C ) = a. Proposition 1 Given I k = p; q). The number of satis ed constraint #sat(I k ; P (x)) of a range I k 2 I(B(P(x))) is de ned recursively by : #sat(I k ; P(x)) = #sat(I k 1 ; P (x))+nMin(p; B(P (x))) nMax(p 1; B(P (x))) with #sat(I 1 ; P (x)) = 0. proof: By induction. I 0 is equal to min(D(x)); o), because all D(x) C D(x).Thus, #sat(I 0 ; P(x)) = #sat(I 1 ; P (x))+nMin(min(D(x)); B(P (x))) nMax(min(D(x)) 1; B(P (x))) = nMin(min(D(x)); B(P (x))). Therefore the property holds for I 0 . Suppose that it is true for I k 1 , and I k = p; q). By de nition of nMin and nMax and from Property 6.3 we have #sat(I k ; P (x)) = #sat(I k 1 ; P (x)) + nMin(p; B(P (x))) nMax(p 1; B(P(x)))

  Algorithm Given I(B(P(x))), we propose an implementation of the algorithm used to compute LB P(C) : Algorithm 2: ComputeLB Data : P(C), X, D Result : LB LB 0; foreach x 2 X do LB LB + ComputeMinInc(x; D(x);P(x)); end return LB;

An implementation of PFC-MRDAC based on ltering algorithms of constraints were proposed in 6], but this one requires also to maintain one counter by value.

 is the non incremental version of PFC-MRDAC.


Marc Ricordeau
email: mricorde@wanadoo.fr

Michel Liquière
email: liquiere@lirmm.fr

Policies Generalization in Reinforcement Learning using Galois Partitions Lattices

The generalization of policies in reinforcement learning is a main issue, both from the theoretical model point of view and for their applicability. However, generalizing from a set of examples or searching for regularities is a problem which has already been intensively studied in machine learning. Our work uses techniques in which generalizations are constrained by a language bias, in order to regroup similar states. Such generalizations are principally based on the properties of concept lattices. To guide the possible groupings of similar environment's states, we propose a general algebraic framework, considering the generalization of policies through a set partition of the states and using a language bias as an a priori knowledge. We give an application as an example of our approach by proposing and experimenting a bottom-up algorithm.

Introduction

The reinforcement learning domain gives the promising theoretical framework of an agent learning a behavior by interactions with an environment with the following properties: [START_REF] Watkins | Q-learning[END_REF] The agent doesn't have any a priori knowledge, on the environment. [START_REF] Sutton | Between mdps and semi-mdps : A framework for temporal abstraction in reinforcement learning[END_REF] There is no separation between a learning phase and a phase of use of the learning. [START_REF] James | Learning and discovery of predictive state representations in dynamical systems with reset[END_REF] The agent has to manage the temporal difference learning problem, that is to say considering that the effect of an action can be delayed or that an effect can be the consequence of several successive actions. With the formalism used to realize and demonstrate the properties of most of the algorithms as well as in practice, the approach is severely more restrictive: environments are designed with a Markovian Decision Process (MDP), the succession of interactions and perceptions are discretized and the agent is supposed to perceive its environment completely. The constant progress of reinforcement learning since the emergence of its most famous algorithm, Q-Learning [START_REF] Watkins | Q-learning[END_REF], aims at adapting the algorithms to a wider class of problems than those that can be formalized with a MDP: extension of the formalism [START_REF] Sutton | Between mdps and semi-mdps : A framework for temporal abstraction in reinforcement learning[END_REF] or more recently [START_REF] James | Learning and discovery of predictive state representations in dynamical systems with reset[END_REF], environment's states or continuous actions [START_REF] Munos | Error bounds for approximate policy iteration[END_REF], non markovian environments, partially observable environments [START_REF] Mccallum | Reinforcement Learning with Selective Perception and Hidden State[END_REF]. Presently, the question of generalization of policies for reinforcement learning and their corollaries: the use of a priori knowledge and the search for important description features to learn the task, has become an important research fields.

Several ways are intensively studied in this frame: generalization by function approximation, algebraical model generalization [START_REF] Ravindran | Smdp homomorphisms: An algebraic approach to abstraction in semi markov decision processes[END_REF], [START_REF] Givan | Equivalence notions and model minimization in markov decision processes[END_REF], temporal abstraction generalization [START_REF] Dietterich | State abstraction in maxq hierachical reinforcement learning[END_REF], link with planning and ILP methods [START_REF] Dzeroski | Relational reinforcement learning[END_REF] or search for relevant descriptions of the environment [START_REF] James | Learning and discovery of predictive state representations in dynamical systems with reset[END_REF]. In our work, we consider the generalization of policies and task description problem from a double point of view: the learning of a behavior by reinforcement and the problem of grouping elements which are considered similar agreeing with a description language. We propose to apply to reinforcement learning, learning methods, based on the Galois lattice algebraical structure, used in classification and more recently in data mining. In [START_REF] Ricordeau | Q-concept-learning: Generalization with concept lattice representation in reinforcement learning[END_REF], methods in the same framework have been presented but in a different way. Notably, we present here an original search space: the descriptions partitions Galois lattice instead of the classical powerset Galois lattices. Moreover, we characterize algebraically the space search, instead of building the whole lattices structures in our algorithms. Section 2 recapitulates briefly the basis of reinforcement learning, essentially to present formalisms used in this paper. In particular, we remind the reader how to formalize the generalization of policies as a partitioning of the environment's states. Then, section 3 shows how to use Galois lattices as a generalization space for a set constrained with a description language (possibly structural). Moreover, we present the descriptions partitions Galois lattice, which is an extension of this method to partitioning a set of objects. In section 4, we see how to use this algebraical structure for policies generalization in reinforcement learning. We study the existence of solutions for the learning problem as a function of the description language. Then, in section 5, we present an algorithm based on these methods and we apply it to an academic problem. We show notably the possibility to extract relevant description elements for the task to be learned by the agent.

2 Basis of Reinforcement Learning, policies generalization

Reinforcement Learning Problem

We only give here the basis and main formalisms of reinforcement learning. A complete introduction can be found in [START_REF] Sutton | Reinforcement Learning : An Introduction[END_REF]. The reinforcement learning proposes a framework where an agent learns a task in a given environment, only by receiving rewards when the task is accomplished. A reinforcement learning is classically formalized as a succession of interactions. The agent receives at the step t a state s t from the environment and a numerical value of reinforcement r t ∈ R, called reward, indicating the quality of the state in which the agent is. Then, the agent acts on its environment, selecting one of the eligible actions a t for the state s t , which modifies the environment's state s t+1 . This process continues indefinitely or until a terminal state is reached. The goal of the agent is to learn to select the actions which maximize the flow of the rewards r i , i ≥ t to come and not only the following reward r t+1 . However, the closest rewards (in term of number of interactions) are considered as more important then the far ones. Thus, the goal of the agent is to maximize the following value called cumulated delayed reward:

R t = ∞ k=0 γ k r t+k , 0 < γ ≤ 1.
The environment is formalized with a MDP. That is to say that the state s t+1 depends only on the state s t , on the selected action a t and on a probability transition P (s t , a t , s t+1 ). In particular, the probability doesn't depend on the previous states-actions sequence s 0 , a 0 , . . . , s t-1 , a t-1 . Formally, an environment is defined with a tuple S, A, ψ, P, R ; S = {s 1 , s 2 , . . . , s n } is a set of states; A = {a 1 , a 2 , . . . , a n } is a set of actions; ψ ⊆ S × A is a set of eligible couples (state, action). We note A(s) the set of eligible actions for the state s ((s, a i ) ∈ ψ); P : ψ × S → [0, 1] is the set of transition probabilities from the state s to the state s selecting the action a; R : ψ → R is the reward function giving a numerical value for each eligible couple (s, a). The function π : ψ → [0, 1] gives the probability for the agent to select the action a being in the state s. The function π is called the policy of the agent. The function Q π : ψ → R, called quality function, defines the expected cumulated delayed reward (expected because the process is stochastic and not deterministic) the agent would obtain following the policy π from the state s and taking the action a.

The set of all policies can have a partial order relation, based the cumulated delayed reward. A policy π 1 is greater than a π 2 if ∀(s, a) ∈ ψ, Q π1 (s, a) ≥ Q π2 (s, a). The policies allowing the agent to collect the maximum possible rewards (R t ) are called optimal policies. All the optimal policies share the same values for the function Q(s, a) which is noted Q * (s, a). Thus, we note π * to refer to an optimal policy. The knowledge of Q * (s, a) allows to find greedily an optimal policy π * by selecting in each state s, one of the actions a with a maximal expected cumulated delayed reward. We note A * (s) the set of the optimal actions for the state s. The reinforcement learning algorithms are based on the approximation of the Q * (s, a) function, during the interactions of the agent with the environment. The hypothesis on the Q(s, a) function is modified with an update rule. For example, this is the update rule for the Q-learning algorithm [START_REF] Watkins | Q-learning[END_REF]:

Q(s, a) ← (1 -α)Q(s, a)+ α r t +γ M ax a∈A(s t+1 ) Q(s t+1 , a) , 0 < α ≤, 0 ≤ γ ≤ 1 (1)
Some main issues characterize the reinforcement learning. Firstly, the temporal difference learning problem, that is to say the repartition of an acquired experience (a value r t ) over the previously selected actions. Secondly, the explorationexploitation problem, that is to say the balance between using the actual knowledge of Q(s, a) function to maximize the flow of rewards (exploitation) and increasing its precision by selecting assumed non-optimal actions (exploration). One of the corollaries is the balance between keeping the actual theory and incorporating the newly acquired knowledge (managed with the γ parameter). Finally, the question we propose to give elements on: the question of the generalizing of policies. It can be viewed as: "How a behavior learned in an environment can be used in a similar environment", or "How a learned knowledge on a set of states can be generalized on a greater set of states". This problem is related to a main question of machine learning: "How to find a relevant description for a given task ?"

Generalization by partitioning the environment's states

In [START_REF] Givan | Equivalence notions and model minimization in markov decision processes[END_REF], [START_REF] Ravindran | Smdp homomorphisms: An algebraic approach to abstraction in semi markov decision processes[END_REF], the generalization for MDPs and consequently for reinforcement learning is presented as the search for an equivalence relation between the environment's states. Two similar states can be merged if they are equivalent, i.e. if the merging doesn't change the dynamic of the environment. It's actually a generalization, because a learning on a state s is applied to the set of the states equivalent with s. However, in these articles, the equivalence relation between the states is computed directly from the MDP, that is to say from the model of the environment. In our work, we want to apply generalization methods without this information, preserving the agent point of view. The equivalence relation on S, the set of the environment's states, we propose is not based on the compliance with the environment's dynamic, but on the equivalence of their optimal actions. Definition 1. Let s 1 , s 2 ∈ S, be two environment's states. s 1 and s 2 are equivalent, which is noted This means that all the optimal actions of s 1 are the sames (considering their label) as the optimal actions of s 2 . It's important to note that we have introduced a first a priori knowledge since this definition implies that two actions can be equivalent according to their description. The partition P * allows to express rules such as "in the set of states S 1 , we must select an action among A * (S 1 ) in order to act optimally". The knowledge of this set of rules, gives the optimal policies and enables us to present them in a more intelligible and general way than an classical probabilities function. Thus, the search for P * becomes in our framework, the goal of the learning. The space search becomes the set partitions of S. However, grouping the states according to their optimal actions doesn't give a direct generalization method. To do it, we need to be able to compare the states. In the next section, we show how the Galois Lattice algebraical structure can be used to generalize a set of objects with a generalization language.

s 1 ≡ * s 2 if and only if A * (s 1 ) = A * (s 2 ).

Galois lattice as generalization space

The definitions and theorems used here about Galois lattices can be found in [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. First, we show how this structure is used in machine learning to allow a generalization over a set of elements biased with a language. Secondly, we give an extend of Galois lattice by presenting the partitions Galois lattice.

Galois lattice and generalization languages

The Galois lattice, or more generally the lattice structure is commonly used in machine learning, directly or in an underlying way. The first well known use of such mathematical objects is certainly the Version Space [START_REF] Mitchell | Machine Learning[END_REF]. More recently, the formal concept analysis theory [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] uses directly Galois lattices as structure used for generalization over a set of objects. We give here a general algebraical approach that can be found in [START_REF] Liquière | Structural machine learning with galois lattice and graphs[END_REF]. A Galois lattice can be classically summed up as a structure defined by a double closure relation between two join semi-lattices. We note it GL(A, ≤ A , ⊗ A , B, ≤ B , ⊗ B , f, g), (A, ≤ A , ⊗ A ) and (B, ≤ B , ⊗ B ) being the two join semi-lattices defined respectively by a set, a partial order relation and a product operator producing the supremum of two elements and f and g being the two closure operators. In the frame of machine learning, the Galois Lattice produced from the powerset of objects and a generalization langage (L, ≤ L , ⊗ L ) defines the set of all the subsets authorized by a given description language and their associated description. More formally, to use a Galois lattice as a generalization space for a set of objects E constrained with a generalization language L, we need to identify the elements of the Galois lattice definition: (1) The set A with P(E), the powerset of the elements to classify. ( 2 The instantiation of an element of the language l ∈ L is the set of all the elements e ∈ E which description is more specific than l. Finally, the set C of the couples (c a , c b )

∈ C i•d (P(E)) × C d•i (L) is called the set of concepts of GL(P, ⊆, ∩, L, ≤ L , ⊗ L , d, i). Let a concept c = (P, l), P ∈ C i•d (P(E)), l ∈ C d•i (L)
, P is the extension of c and l the intention of c. We have three main properties about this structure. First, the set C i•d (P(E)) is the powerset of E that can be expressed with the language L. Thus, L implies a selection between all the possible generalizations of the elements of E. Roughly speaking, we can also say that the language L implies rules like "if we decide to put together the elements e 1 and e 2 , then we must also regroup them with e 3 ". Secondly, the set C d•i (L) is the set of the descriptions of the elements of C i•d (P(E)). If a new, unknown element e n occurs, we can use its description d(e n ) to compare and eventually classify it in a previously found group. Finally, the set C of concepts has a lattice structure, which can be used to compare and merge generalizations of elements of E. This framework is very large, every generalization language L provided with ≤ L and ⊗ L is usable. For example, the formal concept analysis theory studies particularly the attributes-values description case with: L is the powerset P(A) of a set of attributes A, ≤ L is the set inclusion ⊆, ⊗ L is the set intersection ∩. Notably, we can also use structural languages (see [START_REF] Liquière | Structural machine learning with galois lattice and graphs[END_REF] for examples). Thus, the descriptions of the generalizations keep their structural properties.

Descriptions Partitions Galois lattice

We present a special case of Galois lattice: the descriptions partitions Galois lattice as generalization space for the set partitions. It is built in a similar way than the powerset Galois lattice. It will be used to constrain the possible set partitions with a generalization language describing the elements of E, with the same properties. Figure 1 presents the general scheme. The main principle of the Galois lattices for partitions is to use the partitions lattice of E instead of powerset lattice and to use the powerset lattice of the generalization language L instead of L. We also have to redefine the description and instantiation functions to fit the definition. Finally, we show that the extents of the generated concepts are the partitions of E for which each element is a concept of the classical Galois lattice. Let's define the partial order relation ⊆ P for partitions, the product ⊗ P and the sum ⊕ P of two partitions.

Definition 2 (⊆ P , ⊗ P , ⊕ P ). Let E be a set and P(E) be set partitions of E. Let P 1 , P 2 ∈ P(E) be two partitions of E. P 1 ⊆ P P 2 ⇔ ∀P 1 ∈ P 1 , ∃P 2 ∈ P 2 such that P 1 ⊆ P 2 . Let R ⊗ and R ⊕ be two binary relations such that ∀e i , e j ∈ E, e i R ⊗ e j ⇔ e i and e j are in the same part in P 1 or in P 2 ; e i R ⊕ e j ⇔ e i and e j are in the same part in P 1 and in P 2 . The transitive closure of R ⊗ defines a partition which is P 1 ⊗ P P 2 and R ⊕ defines a partition which is P 1 ⊕ P P 2 .

For example, E = {a, b, c, d, e, f, g}, P 1 = {a, b}, {c}, {d, e}, {f, g} and P 2 = {a}, {b}, {c}, {d, }{e, f }, {g}. P 1 ⊗ P P 2 = {a, b}, {c}, {d, e, f, g}. Remind that a partition defines an equivalence relation. Thus ⊗ P can be viewed as the merging of the equivalence classes defined by P 1 and P 2 . Let's identify the generalization language (L, ≤ L , ⊗ L ) to describe the partitions of E, which is based on the generalization language (L, ≤ L , ⊗ L ) for E. A partition of E is composed of subsets of E. Each of these subsets can be described with an element l ∈ L with the description function d. Consequently, the description of a partition of E is described with a set L of elements of L. Thus, the description language for the partitions set is the powerset of L. Nevertheless, we only consider a subset of P(L). Indeed, we only need the set, noted P(L) P(E) of the subsets of L such that their instantiations are partitions of E. In the general case, the instantiation is only a coverset of E.

Definition 3 (≤ L , ⊗ L ). Let (L, ≤ L , ⊗ L ) be a generalization language. Let L 1 , L 2 ∈ P(L) P(E) . L 1 ≤ L L 2 ⇔ ∀l 1 ∈ L 1 , ∃l 2 ∈ L 2 such that l 1 ≤ l 2 . L 1 ⊗ L L 2 is the set L ⊗ such that: L ⊗ = l ∈ L |l = d(P 1 ), P 1 ∈ merge({i(l 1 ) ∪ i(l 2 ), l 1 ∈ L 1 , l 2 ∈ L 2 })
The definitions of ≤ L and ⊗ L are presented to keep mathematical formalism and are not used in practice. The description function d P and the instantiation function i P illustrate the method in a better way. To find the description of a partition P ∈ P(E), we first close the subsets P of E composing the partition with the closure i • d. This gives a coverset of E. Then, we merge transitively the subsets of this coverset which have at least one element e in common with the operator ⊗ P . This gives a partition of E for which all subsets are closed elements of i • d, i.e. extents of the classical Galois lattice. Finally, we redescribe those elements with d.

Definition 5 (instantiation of a subset of L i P ). We define the instantiation function

i P (E) L → P(E) with:∀P L ∈ P(L) P(E) , i P (P L ) = i(l), l ∈ P L .
The instantiation of a subset P L ∈ P(L) P(E) , is simply the set composed with the instantiations of each element l ∈ P L . We can finally produce the partitions Galois lattice.

Theorem 1 (descriptions partitions Galois lattice). GL P (P(E),⊆ P ,⊗ P ,P(E) L , ⊆ P ,⊗ L ,d P ,i P ) is a lattice called descriptions partitions Galois lattice. Let C be the set of concepts of GL P . Let C = (ext, int) ∈ C. The extension ext is a partition of E and the intention int is its description. With all the elements described above, the proof constits in showing that (d P • i P , i P • d P ) defines a Galois connexion. Note that the same elements are needed to define the partitions Galois lattice compared to the classical Galois lattice: a set E and a generalization language (L, ≤ L , ⊗ L ). The classical properties of classical Galois lattices as a generalization space constrained with a language can be applied to the partitions Galois lattice: rules concerning regrouping objects, the possibility to deal with unknown objects, and a comparison between generalizations. The difference is that instead of considering the set of the regroupings of elements of E which can be expressed with the language L, we consider the set partitions of E which can be expressed with L.

Proposition 1 (partition agreeing with a language). Let E be a set and (L, ≤ L , ⊗ L ) be a generalization language for E. A partition P(E) of E agreeing with the language L is a partition whose all the subsets can be expressed with an element l ∈ L. That is to say whose all the subsets are closed elements of P(E) with the closure i • d. The set of the extensions of the concepts of the description partitions Galois Lattice GL P is the set partitions of E agreeing with the language L. Size of GL P The size of the GL P is equal to the number of partitions agreeing with L. Consequently, the size of the GL P is lower than the |E| th Bell number. The exact number of partitions agreeing with L is an open question. However, we can say that it's a function of the size of the classical GL size. In the worst case, the size of the GL is 2 |E| . Then, the size of GL P is the |E| th Bell number, but in this case, L doesn't give any bias concerning the possible ways of regrouping the elements of E. This case is useless in our context. We can note that for each subset of E which can't be described with an element of L, the size of GL P is falling as a function of the number of elements of this subset.

Using the partitions Galois lattice for reinforcement learning

The set partition P * of the environment's states induced by the quality function of optimal policies Q * (s, a) can be considered as observed section 2.2, as the goal of a reinforcement learning. We have just defined the descriptions partitions Galois lattice as space search for partitioning a set of objects, here S, the set of the environment's states. The space search being constrained with a language L S , we have first to study the relationship between P * and the possibility to express it with L S . Then, we propose an algorithm to build P * .

4.1 Relationship between P * and a generalization language L S Let an agent evolving in an environment formalized with a MDP M S,A,ψ,P ,R . The set S is described with the generalization language (L S , ≤ L S , ⊗ L S ). Let's consider three different cases concerning the agreement of P * with L S . (1)

The partition P * agrees with L S . In this case, each of the sets regrouping the states according to their optimal actions can be expressed with an element of the language l ∈ L S . ( 2) It exists at least one partition P agreeing with L S such that P ⊆ P * . In this case, if we add the condition which is that each state s ∈ S has a different description (the agent has a complete vision of its environment), it always occurs. Indeed, in the worst case, it's the partition of size |S|. Moreover, if the description language doesn't have any generalization properties that is to say the product of l 1 , l 2 ∈ L S always gives the same element l , then we have the classical case of reinforcement learning. Note that there can be more than one such partitions. (3) There is no partition P agreeing with L S such that P ⊆ P * . The agent is unable to distinguish states which should be considered different from the task point of view. We are in the case of Partially Observable MDP. We need for example, to use a memory based system [START_REF] Mccallum | Reinforcement Learning with Selective Perception and Hidden State[END_REF] to separate the states.

A bottom-up Algorithm

The general framework we proposed: search for the partition P * , using the set partitions of S, can be implemented in several ways, depending on the chosen space exploration (bottom-up, top-down, breadth-first,...) and on the heuristics managing the imprecision of the current Q(s, a) function.

We propose the bottom-up algorithm 1 which partitions the set of the states at a given step of the learning. The built partition is the most general, agreeing with L S . The equivalence relation ≡ * doesn't always give a unique partition. Thus, the algorithm regroups in priority the states with the same value for their optimal actions.

Proof elements for the algorithm All the states are considered successively using a FIFO structure (variable States line 1). In the worst case, each state is added as a singleton to the resulting partition (line 7). This ensures that the final result is a cover of S. The lines 2 and 5 ensure that the elements are added to only one subset, ensuring that the result is a partition of S. Line 3, the algorithm constructs a subset of S from a state and according to the equivalence relation ≡ * , using te closure operator i • d. This ensures that the produced subset agrees with the language L. Then, we verify line 4 that the closure has only added equivalent elements, ensuring that the resulting partition is lower (using ⊆ P ) than P * .

Experiment

We present an experiment of our algorithm on an academic problem to illustrate our method and to validate our theoretical approach with an implementation. to describe the task instead of 504 initially. There are expected elements such as being at one tile at the south of the reward implies move north (example 1), the other tiles don't matter. We also find non intuitive rules (example 4). Note that there are descriptions with the same optimal actions which are not grouped (example 1 and 2). This is because there are no language elements allowing the grouping of these descriptions without regrouping others, with different optimal actions. We could add, for example, the notion of relative position with the reward, either directly or using a knowledge data base.

Conclusion

First, we reminded the reader of the general principles in the use of a Galois lattice as a generalization space for a set of objects described with a generalization language. Then, we extended these results to define an original generalization space for the partitions instead of powerset, in particular by introducing the notion of partition agreeing with a language. We showed that, considering generalization as a partitioning, this structure can be used to generalize learning in reinforcement learning. Finally, we proposed a bottom-up algorithm which through a reinforcement learning and a generalization language made it possible to produce general rules linking description elements of the environment and optimal actions. This work considered principally the algebraical aspects. Consequently, we didn't treat two remaining important issues: "How to use the rules on unknown examples" and "How to deal with knowledge uncertainty".

Our future work will focus on three directions. First, a more formal link between our work and the relational reinforcement learning [START_REF] Dzeroski | Relational reinforcement learning[END_REF]. Secondly, an algorithmic improvement, studying the different ways of exploring the space search and the classical balancing between spatial and temporal complexity. Thirdly, we will consider the exploration-exploitation problem, i.e. using previously acquired knowledge or acquiring new knowledge and as a corollary, managing knowledge uncertainty. It remains a difficult problem in machine learning and in reinforcement learning in particular. In our case, it's transposed in a particular way as the concept reliability, already presented in [START_REF] Ricordeau | Q-concept-learning: Generalization with concept lattice representation in reinforcement learning[END_REF]. We think that a relevant approach can consists in the explicit management of second order elements (states distribution, maximal reward,. . . ) directly through the algorithms.

  The equivalence relation ≡ * implies a partitioning of the set S, noted P * .

  ) The partial order relation ≤ A with the set inclusion ⊆. (3) The product operator ⊗ A with the set intersection ∩. (4) The set B, ≤ B and ⊗ B can be identified with any description language L with a partial order relation ≤ L and a product operator ⊗ L such that exists a description function d and an instantiation function i described below and agreeing with the Galois connection conditions. Such languages are called generalization languages. The relation ≤ L defines the relation more general than or more specific than and ⊗ L is called generalization operator. (5) The function f with the following description function d : P(E) → L, d(P ) = L {d(e), e ∈ E}. The description d(P ) of a subset P ⊆ E is the least general generalization of the descriptions of the elements e ∈ P . Note that only the description d(e), e ∈ E must be known in order to compute the description of all subset P ⊆ E. (6) The function g with the following instantiation function i : L → P(E): ∀l ∈ L, i(l) = {e ∈ E | d(e) ≤ L l}.

Fig. 1 .

 1 Fig. 1. Scheme of partitions Galois lattice constrained with a generalization language

Definition 4 (

 4 description of a partition d P ). We define description function d P : P(E) → P(L) with: ∀P ∈ P(E), d P (P) = l ∈ L | l = d(P 1 ), P 1 ∈ merge({i • d(P ), P ∈ P})

Fig. 2 .Fig. 3 .

 23 Fig. 2. A graphical example of two states, their descriptions and their product

Data

• A generalization language (L S , ≤ L S , ⊗ L S ) for the states S the current estimation of Q(s, a) Result • A partition P, based on ≡ * , agreeing with the language L S , such that P is the most general possible, with grouping uppermost the states of S with the same optimal actions values. Algorithme 1 : Partitioning the set S according to ≡ * and agreeing with a generalization language (L S ,

P artition ← ∅;

The example consists in a grid-world of size (3 × 3) containing an agent, a reward and a wall. All the other tiles are empty. The walls can be moved, if there is no other behind, with the action push. The task to be learned is to move as fast as possible to the reward tile. Each episode lasts until the agent reaches the reward tile or until it destroys it with a wall. The agent receives an reward of +1.0 if it reaches the reward tile. All other actions receive -0.1. There are 504 different states with 4 actions in each. push and move are different actions, |ψ| = 2016. The consequences of actions are deterministic and the environment is stationary. The actions are described with: {move west, move east, move north, move south, push west, push east, push north, push south}. The language (L S , ≤ L S , ⊗ L S ) used to describe the states is an attribute-values language. The description of a state is composed with one attribute for each tile that the agent can see (see Figure 2). The partial order relation ≤ L S is defined by: d(s 1 ) ≤ L S d(s 2 ) ⇔ all the attributes of d(s 1 ) are less than or equal to the corresponding one in d(s 2 ) according to the join semi-lattice given Figure 2. The product ⊗ L S of two descriptions is the generalization of each attribute. The selection of actions and learning has been made with a classical Q-Learning algorithm.

Our algorithm allows the extraction of relevant description elements according to the task. Figure 3, shows an extract of the partition obtained after the convergence of the learning. Quantitatively, we need only 92 description elements


V Tuninetti
email: victor.tuninetti@ufrontera.cl

P Flores
email: pfloresv@udec.cl.

C Medina
email: cmedinam@udec.cl.

L Duchêne
email: l.duchene@uliege.be

A M Habraken
email: anne.habraken@uliege.be

Presqu'île de Giens (Var) Effect of small strain rate variations on the identification of the compressive behaviour of Ti6Al4V

Keywords: yield stress, material indentification, constant strain rate, strain sensitive material, Ti64

Ti6Al4V is an hcp material that exhibits a strain rate sensitive behaviour and the tension compression asymmetry yielding known as the Strength Differential (SD). To quantify the SD effect of this alloys, initial yield compressive stress at different temperatures are computed by performing two type of tests, the conventional constant die speed and the constant strain rate compression tests. The results show the effect of the small strain rate variations on the initial yield stress and the strain hardening of the alloy at moderated temperatures.

Introduction

The plastic characterization of the Ti6Al4V alloy involves the identification of an initial yield locus, and its evolution with the plastic work, the temperature and the strain rate. Several models representing the strain rate sensitive behaviour of this hcp alloy are available in the literature, for instance, Zerilli-Armstrong [START_REF] Zerilli | Dislocation-mechanics-based constitutive relations for material dynamics calculations[END_REF], Norton-Hoff [START_REF] Hoff | Approximate analysis of structures in the presence of moderately large creep deformations[END_REF] and the most widely used Johnson-Cook [START_REF] Johnson | A constitutive model and data for metals subjected to large strains, high strain rates and high temperatures[END_REF][START_REF] Dorogoy | Determination of the Johnson-Cook Material Parameters Using the SCS Specimen[END_REF][START_REF] Peirs | Novel Technique for Static and Dynamic Shear Testing of Ti6Al4V Sheet[END_REF] material model. Other advanced models as the one developed by Cazacu et al. [START_REF] Cazacu | Orthotropic yield criterion for hexagonal close packed metals[END_REF] with a distortional hardening allows the description of material anisotropy and Strength Differential (SD) effect. The mechanical tests required to accurately identify or validate these material models of the material should be performed at constant strain rates and constant temperature.

Galán López et al. [START_REF] Galán López | Effect of small temperature variations on the tensile behaviour of Ti-6Al-4V[END_REF] demonstrated that tests performed at constant sample temperature are required for the accuracy of the stress modelling. The temperature increase due to heat generation of the sheet Ti6Al4V tensile samples tested in air, influences the strain hardening response due to the thermal softening.

For tensile and compressive constant strain rate tests, universal testing machines are equipped with a closed-loop control system [START_REF] Hartley | Tensile Testing at Constant True Plastic Strain Rate[END_REF]. Nevertheless, in many laboratories, this feature is not always available in the machines. The capability of machines to be configured with a proper user-defined displacements of the cross-head is used in this research to perform constant strain rate compression test at several temperatures. To quantify the effect of the small variations of strain rate on the Initial yield stress and the initial strain hardening of the Ti6Al4V alloy at moderated temperatures, constant cross-head speed tests are also performed. This contribution is organized as follows. Section 2 presents the properties of the alloy and experimental procedures. The experimental results and the assessment of the compressive strain rate sensitivity of Ti6Al4V is presented in Section 3. Finally, main conclusions obtained in this study are summarized in Section 4.

Material and experimental procedure

The bulk forged Ti6Al4V alloy shown in Figure 1 is tested under compression at the LD material direction. Its chemical composition is given in Table 1. A servo-hydraulic testing machine controlled for both constant strain rate and constant cross-head speed tests is used to perform compression tests on elliptical samples as the ones proposed in Tuninetti et al. [START_REF] Tuninetti | Compression test for plastic anisotropy characterization using optical full-field displacement measurement technique[END_REF]. The machine is equipped with an infrared furnace (Quad Ellipse Chamber, Model E4, Radiant Energy Research Inc.) to apply compression test on samples at 400°C and 600°C. Prior to the tests, the samples were held for 10 min at the testing temperature in order to ensure a homogeneous temperature distribution through the specimens.

Equation 1 allows computing the height increase or reduction   t X ep of the specimen (note that negative value is associated with compression) as a function of time necessary to impose on the sample for a test at a constant strain rate  . 0 H is the initial height of the specimen. This   t X ep value could be used as the user-defined displacement of the actuator only if the displacement is imposed according to an extensometer directly applied on the specimen. This case is usual for the tests performed at room temperature (RT) with the tensile testing machines. Imposing the user-defined displacement computed with Equation 1, one can reach a constant strain rate test. However, high temperature extensometers for tensile tests are not currently available in many laboratories. Besides, in the testing machine used for compression tests, the sensor associated to the user-defined displacement is connected in the actuator (cross-die). The rigidity of the machine should be first identified and considered in order to impose the proper displacement or deformation of the specimen for the constant strain rate tests.

      1 exp 0   t H t X ep  (1)
Imposing a cross-head global displacement   t X gl with the purpose of reaching a specific specimen displacement   t X ep needs a previous knowledge of the machine deflection   t X ma (Figure 1b). This deflection could be measured during the test of a sample with a specific material, however   t X ma depends on the load applied by the machine, which also depends on the strain rate sensitivity of the material. To reach a constant strain rate test, a closed-loop control feature could be used [START_REF] Hartley | Tensile Testing at Constant True Plastic Strain Rate[END_REF]. A second option, which is used in this research, is to perform a consecutive series of tests with the proper user-defined displacement of the actuator until a constant strain rate test is reached.

Assessment of the compressive strain rate sensitivity of Ti6Al4V

The compressive stress-strain responses of the two types of tests performed on Ti6Al4V at 400 °C and 600 °C are compared (Figure 2):

1. The first type of test is performed at constant die (cross-head) speed knowing the targeted strain rate equal to 10 -3 s -1 . Two merely constant strain rates for the plastic range (around to 1.2x10 -3 s -1 ) and the elastic range (around to 10 -4 s -1 ) can be observed for the two studied temperatures (Figure 2).

2. The second type of test is performed at a constant strain rate equal to 10 -3 s -1 by applying the proper user-defined displacement of the actuator of the machine. The difference between the yield stress level for a test at a constant strain rate and at a constant cross-head speed is higher at 600°C degres. As observed in Figure 2 and Figure 3, the variation in the strain rate can lead to a large inaccuracy in the estimation of the proper initial yield stress of the alloy and the initial strain hardening rate for a targeted strain rate at moderated temperatures. For room temperature tests, negligible differences in the stress-strain response for the two different test conditions has been observed. These findings on the material response are qualitatively similar to the response reported on other metals [START_REF] Li | The Effect of Strain Rate, Specimen Geometry and Lubrication on Responses of Aluminium AA2024 in Uniaxial Compression Experiments[END_REF].

Conclusion

The effect of small strain rate variations on the strain hardening rate and the initial yield stress of Ti6Al4V was presented for temperatures equal to 400°C and 600°C. The compressive behaviour was selected in this study, and the capability of machines to be configured with proper user-defined displacements of the cross-head was used to perform constant strain rate and constant cross-head speed compression tests. The importance of using accurate method for the characterization of the strain rate sensitivity of the Ti6Al4V alloy was also highlighted. The experimental results showed that significant variations of the mechanical features of the alloy can be found at moderated temperatures if constant strain rate is not reached for the full range of strain. These findings should be considered in order to accurately identify the constitutive laws modelling the mechanical behaviour of the studied alloy.

Figure 1 .

 1 Figure 1. (a) Bulk Ti6Al4V alloy and (b) deflection of the machine (SCHENCK Hydropuls 400 kN press) and Ti6Al4V specimen deformation in a constant cross-head speed test (test 1) at 021 . 0  v mm/s.

Figure 2 -

 2 Figure 2 -Comparison between stress-strain curves of compression tests at constant die speed and constant strain rate at (a) 400 °C and (b) 600 °C.

Figure 3 -

 3 Figure 3 -Comparison between the evolution of the strain hardening rate   p y y      

Table 1 -

 1 Chemical composition of the bulk forged Ti6Al4V alloy investigated.

Acknowledgements

The authors thank the Chilean Scientific Research Fund CONICYT FONDECYT 11170002, the Universidad de La Frontera internal Research Found DIUFRO (Project DI17-0070), cooperation WBI/AGCID SUB2019/419031 and the Belgian Scientific Research Fund FNRS for financial support. The authors would also like to thank O. Milis for its technical support.