Christian Bessiere
email: bessiere@lirmm.fr

Rémi Coletta
email: coletta@lirmm.fr

Thierry Petit
email: thierry.petit@emn.fr

Acquiring Parameters of Implied Global Constraints

This paper presents a technique for learning parameterized implied constraints. They can be added to a model to improve the solving process. Experiments on implied Gcc constraints show the interest of our approach.

Introduction

Automatic model reformulation is a key issue for researchers [START_REF] Puget | Constraint programming next challenge: Simplicity of use[END_REF][START_REF] Frisch | The rules of constraint modelling[END_REF][START_REF] Colton | Constraint generation via automated theory formation[END_REF]. The objective is to decrease the expertise required to use constraint programming. One way to improve a model consists of adding implied constraints. An implied constraint is not mandatory to express the problem but it helps to solve it [START_REF] Smith | Modelling the golomb ruler problem[END_REF]. In this paper, we assume that we have a model which expresses the problem, but the solving time is not satisfactory. We wish to improve it by automatically adding new implied constraints. Our idea is to use a learning algorithm that deduces new parameterized constraints from assignments of values to sets of variables. The set of tuples allowed by a parameterized constraint not only depends on its variables and their domains, but also on some extra information provided by parameters, which are not necessarily part of the problem variables. For instance, the NValue(p, [X 1 , . . . , X n ]) constraint holds iff p is equal to the number of different values taken by X 1 , . . . , X n . p can be a CSP variable (in its more general definition) or a parameter which leads to different sets of allowed tuples on the X i 's, depending of the values it can take. In our context, a learning algorithm would try, for example, to learn the smallest range of possible values for p s.t. no solution exists outside this range. If the algorithm returns a lower bound min(p) > 0, or an upper bound max(p) < n, then the learned constraint can be of interest. 1

Learning Parameterized Constraints

The set of tuples allowed by a classical constraint is known once the variables it involves and their domains are set. A parameterized constraint may allow different sets of tuples depending on the possible values for its parameters. Let us first define parameterized constraints in the most general way to let our work be as general as possible. Our goal is to learn implied constraints on any type of constraint problem: we focus on those parameterized constraints where for any tuple e on var(C), S e = ∅. The basic idea is to learn the parameters of an implied constraint C by exploiting information provided by solutions and non-solutions of a subproblem (stem from the initial problem by removing variables and constraints). Indeed, if the current model is not good, obviously it should not easily provide instances2 for the whole problem. By definition, if a learned constraint is valid in a subproblem then it is still valid in the main problem. Variables of the subproblem are then the decision variables involved in the learned implied constraint. W.r.t. optimization problems, in the context of a Branch and Bound algorithm, a way to proceed is to learn new implied constraints at each step of the optimization. 3We assume now that the subproblem and the constraint C to learn have been chosen. We consider only constraints for which C( |∆| ) is the universal constraint (i.e., for any tuple e, S e = ∅). Thus, following Definition 3, C( |∆| ) is an implied constraint for the problem P. The objective of a learning algorithm will be to learn a 'target' set T ⊆ |∆| , as small as possible, s.t. C(T ) is still an implied constraint. Any s ∈ |∆| which is not necessary to accept some solutions of P can be removed from T .

Notation 2 Given a problem P = (X , D, C) and a parameterized constraint C, we denote by required(T ) the set of elements r of |∆| such that r ∈ required(T ) iff C( |∆| \ {r}) is not an implied constraint, namely r is compulsory in T if we want C(T ) to be an implied constraint in P. poss(T ) denotes those r in |∆| for which we do not know if they must belong to required(T ).

In other words, required(T ) represents those combinations of values for the parameters that are necessary to preserve the set of solutions of P, and poss(T ) those for which we have not proved yet that we would not lose solutions without them. The fact that an implied constraint should not remove solutions when we add it to the problem leads to the following property w.r.t. positive instances.

Property 1. Let e + be a positive instance and T ⊆ |∆| . If C(T ) is an implied constraint for P then T ∩ S e + = ∅.

Proof. e + is a solution of P. At least one s ∈ T should accept that instance to preserve the set of solutions of P. So, s ∈ S e + by Definition 2.

Corollary 1. Let e + be a positive instance of P and C a parameterized constraint. If there is a unique s ∈ |∆| such that e + [var(C)] ∈ C(s) then s ∈ required(T ).

Negative instances will help to remove from poss(T ) the combinations of parameters that can be removed without losing solutions. When receiving a negative instance e -, we want to know if it is possible to reduce the target set T in order to reject e - while preserving Sol(P).

Property 2. Let P be a problem, C a parameterized constraint, and S ⊂ |∆| . If P augmented with the constraint C(S) has no solution then C( |∆| \ S) is an implied constraint for P.

Proof. By previous assumption, we know that C( |∆| ) is an implied constraint for P. Since P ∪{C(S)} is inconsistent, we know that ∀e ∈ Sol(P), Se ∩S = ∅. Thus Sol(P +C( |∆| )) = Sol(P + C( |∆| \ S)). Checking if P augmented with the constraint C(S) is inconsistent (line 2) is obviously NP-hard. Even if P in this learning phase is not supposed to be the whole problem we want to reformulate, it is necessary to follow some heuristics to avoid huge numbers of NP-hard calls to a solver. For a parameterized constraint C, different representations of parameters may exist. The more general case studied until now (Algorithm 1) consists of considering that allowed tuples of parameters for C are given in extension as a set T . Corollary 1 may then seem weak. However, in practice, most of parameterized constraints are s.t. any two different combinations of parameters in |∆| correspond to disjoint sets of allowed tuples on var(C). We call them parameter-partitioned constraints. For instance, NValue(p, [X 1 , . . . , X n ]) is parameter-partitioned since a single value of p corresponds to an assignment of the X i .

Corollary 3. Let e + be a positive instance. If C is a parameter-partitioned constraint, s e + ∈ required(T ), where s e + is the only element in S e + .

This corollary allows a faster construction of required(T ) compared with Algorithm 1. Moreover, existing parameterized constraints are usually defined by sets of possible values for their parameters taken separately, which is less expressive than considering directly any subset of |∆| . It is possible to exploit this fact. We will note T [p i ] for the values of a parameter we wish to learn. Then, required(T

[p i ]) = {k i ∈ s.t. ∃s ∈ required(T ), s[p i ] = k i }, namely the set of values for p i that are re- quired in T [p i ]. Similarly, poss(T [p i ]) = {k i ∈ s.t. ∃s ∈ poss(T ), s[p i ] = k i }.

Experiments

We implemented with Choco [START_REF] Choco | A Java library for constraint satisfaction problems, constraint programming and explanation-based constraint solving[END_REF] a learning algorithm for implied Gcc (global cardinality constraints [START_REF] Régin | Generalized arc consistency for global cardinality constraint[END_REF]) where parameters are ranges. On the two intentionally naive models we implemented to evaluate the interest of our algorithm, tables compare the solving time of an initial model with the same model augmented with a learned Gcc.

Definition 1 .Definition 2 .

 12 Given a set of parameters ∆ = {p 1 , ..., p |∆| } taking their values in the set of integers , a parameterized constraint C is a constraint which expresses a property on the variables it involves (denoted by var(C)) depending on the possible values for its set of parameters ∆. Given s ∈ |∆| , an assignment of values to the parameters, C(s) refers to the set of allowed tuples of the constraint C when each p i in ∆ takes the i th value in s, noted s[p i ]. Given S ⊆ |∆| , C(S) = s∈S C(s). Given a constraint C with parameters ∆ and a tuple e on var(C) (or a superset of var(C)), S e contains the combinations s in |∆| s.t. C(s) accepts e.

Notation 1 PDefinition 3 .

 13 = (X , D, C) is the problem used to learn an implied constraint. An implied constraint C for P is a constraint s.t. var(C) ⊆ X and the set Sol(P) of solutions of P is equal to Sol((X , D, C ∪{C})); Namely, for any instance e ∈ Sol(P), e[var(C)] is allowed by C.

Corollary 2 .

 2 Let P be a problem, C a parameterized constraint, S ⊆ |∆| , and poss(T ) a set s.t. C(poss(T )) is implied on P. If P augmented with the constraint C(S) has no solution then C(poss(T ) \ S) is an implied constraint for P.

Algorithm 1 : 2 else

 12 Learning Algorithm for Parameterized Constraints. Input: C, ∆, E = {e1, . . . , e k } a set of instances for P. Output: poss(T ), s.t. C(poss(T )) is an implied constraint for P. required(T ) ← ∅; poss(T ) ← |∆| ; while (E = ∅) and (required(T ) = poss(T )) do Pick e ∈ E; if e is positive then if |Se| = 1 then required(T ) ← required(T ) ∪ Se; /* Corol. 1*/ 1 else for some S ⊆ (poss(T ) \ required(T )) do if Sol(X , D, C ∪ C(S)) = ∅ then poss(T ) ← poss(T ) \ S; /* Corol. 2*/ put an element of Sol(X , D, C ∪ C(S)) as positive instance in E

Property 3 .

 3 If the possible values for a parameter p i are a set of integers, the learning algorithm uses sets of integers to represent required(T [p i ]) and poss(T [p i ]). The parameterized constraint will be called with poss(T [p 1 ]) × . . . × poss(T [p |∆| ]). If the possible values for p i are a range of integers, the learning algorithm uses ranges of the form [min(poss(T [p i ]))..max(poss(T [p i ]))] to represent poss(T [p i ]) (resp. required(T [p i ])). Properties 1 and 2 can be rewritten to fit these two cases. Let e + be a positive instance of P and C a parameterized constraint s.t. parameters are sets of integers. If there is a unique s ∈ |∆| such that e + [var(C)] ∈ C(s) then for any p i ∈ ∆, s[p i ] ∈ required(T [p i ]).

Property 4 .

 4 Let P be a problem, C a parameterized constraint where parameters are a set of integers, and poss(T ) a set s.t. C(poss(T )) is implied on P. Let p be a parameter of C, v a value in poss(T [p]), and S = {s ∈ poss(T ) s.t. s[p] = v}. If P augmented with C(S) has no solution then v can be removed from poss(T [p]). Note that for each negative instance e -, if the constraint is parameter-partitioned, a heuristic can be used to apply property 4 with v = s e -[p]. Property 5. Let e + be a positive instance of P and C a parameterized constraint s.t. parameters are ranges. If there is a unique s ∈ |∆| such that e + [var(C)] ∈ C(s) then for any p i ∈ ∆, min(required(T [p i ])) ≤ s[p i ] ≤ max(required(T [p i ])). Property 6. Let P be a problem, C a parameterized constraint where parameters are ranges, and poss(T ) a set s.t. C(poss(T )) is implied on P. Let p be a parameter of C, v a value in poss(T [p]), and S = {s ∈ poss(T ) s.t. s[p] ≤ v} (respectively: S = {s ∈ poss(T ) s.t. s[p] ≥ v}). If P augmented with C(S) has no solution then min(poss(T [p])) > v (respectively: max(poss(T [p i ])) < v).

Table 1 .

 1 Scheduling satisfaction problem with a fixed makespan, precedence constraints, and m = m1+m2 tasks (requiring one or two resources). maxi is the maximum allowed resource. 15 assignments where used to learn an implied Gcc on a problem relaxed from resource constraints.

	4

Table 2 .

 2 Optimization problem (allocation). n is the problem size (number of variables), |E| is the number of assignments used to learn implied Gcc's.

A lot of existing constraints[START_REF] Beldiceanu | Global constraints as graph properties on a structured network of elementary constraints of the same type[END_REF] may be used as implied parameterized constraints: AtLeast, AtMost, Change, Common, Count, Gcc, Max, Min, NValue, etc.

Given a problem P = (X , D, C), an instance e is an assignment of values to variables in X . It is positive if e belongs to Sol(P), otherwise it is negative.

We may observe a nice cooperation between the learning and the solving phases: new learned constraints help at each step to solve the problem, and thus to learn the next ones.

In the tables located at the left the last column indicates the solving time, whereas in the tables located at the right the last column indicates the sum of the learning time and the solving time.


Guillaume Verger
email: verger@lirmm.fr

Christian Bessiere
email: bessiere@lirmm.fr

Guiding Search in QCSP + with Back-Propagation

The Quantified Constraint Satisfaction Problem (QCSP) has been introduced to express situations in which we are not able to control the value of some of the variables (the universal ones). Despite the expressiveness of QCSP, many problems, such as two-players games or motion planning of robots, remain difficult to express. Two more modeler-friendly frameworks have been proposed to handle this difficulty, the Strategic CSP and the QCSP + . We define what we name back-propagation on QCSP + . We show how back-propagation can be used to define a goal-driven value ordering heuristic and we present experimental results on board games.

Introduction

The Constraint Satisfaction Problem (CSP) consists in finding values for variables such that a set of constraints involving these variables is satisfied. It is a decision problem, in which all variables are existentially quantified (i.e., Is there a value for each variable such that all constraints are satisfied?). This framework is useful to express and solve many real applications.

Problems in which there is a part of uncertainty are hard to model in the CSP formalism, and/or require an exponential number of variables. The uncertainty part may come from weather or any external event, which is out of our control. The Quantified Constraint Satisfaction Problem (QCSP [START_REF] Bordeaux | Beyond NP: Arc-consistency for quantified constraints[END_REF]) is a generalisation of the CSP in which variables can be either existentially (as in CSP) or universally quantified. We control the existential variables (we choose their value), but we have no control on universal variables (they can take any value in their domain). Solving such problems is finding values for existential variables according to the values taken by the preceding universal variables in the sequence of variables in order to respect constraints.

The structure of QCSP is such that the domains of universal variables do not depend on values of previous variables. But in many problems, values taken by variables depend on what has been done before. For example, if we want to express a board game like chess, some moves are forbidden, like stacking two pieces on the same cell.

In [START_REF] Benedetti | QCSP made practical by virtue of restricted quantification[END_REF][START_REF] Bessiere | Strategic constraint satisfaction problems[END_REF] this issue has been identified and new formalisms, SCSP and QCSP + , have been proposed to have symmetrical quantifier behaviors. Both in SCSP and QCSP + , the meaning of the universal quantifier has been modified, and the domains of universal variables depend on the values of previous variables. In the field of Quantified Boolean Formulas, this problem has also been identified. Ansótegui et al. introduced new QBF formulations and solving strategies for adversarial scenarios [START_REF] Ansótegui | The Achille's heel of QBF[END_REF].

In this paper, we propose a value ordering heuristic for the QCSP + . After preliminary definitions (Section 2) and clues for solving QCSP + (Section 3), we analyse constraint propagation in QCSP + in Section 4. Based on this analysis, we derive a value ordering heuristic for QCSP + in Section 5. Finally, in Section 6, we present experimental results on board-games.

Definitions

In this section we focus on the two frameworks that have been proposed to tackle the QCSP modeling issue, Strategic CSPs [START_REF] Bessiere | Strategic constraint satisfaction problems[END_REF] and QCSP + [START_REF] Benedetti | QCSP made practical by virtue of restricted quantification[END_REF]. But first of all, we give some background on CSP and QCSP.

CSP and QCSP

The constraint satisfaction problem. A constraint network N = (X, D, C) consists of a finite set of variables X = {x 1 , . . . , x n }, a set of domains D = {D(x 1 ), . . . , D(x n )}, where the domain D(x i ) is the finite set of values that variable x i can take, and a set of constraints C = {c 1 , . . . , c e }. Each constraint c k is defined by the ordered set var(c k ) of the variables it involves, and by the set sol(c k ) of combinations of values on var(c k ) satisfying it. A solution to a constraint network is an assignment of a value from its domain to each variable such that every constraint in the network is satisfied. A value v i for a variable x i is consistent with a constraint c j involving x i iff there exists an assignment I of all the variables in var(c j ) with values from their domain such that x i is assigned v i and I satisfies c j .

Given a constraint network N = (X, D, C), the constraint satisfaction problem (CSP) is the problem of deciding whether there exists an assignment in D for the variables in X such that all constraints in C are satisfied. In a logical formulation, we write, "∃x 1 . . . ∃x n , C?"

In CSPs, the backtrack algorithm is inefficient when problems are big, and the most common way to solve CSPs is to combine depth-first search and constraint propagation. The aim is to use constraint propagation to reduce the size of the search tree by removing some inconsistent values in domains of variables. An inconsistent value is a value such that if it is assigned to its variable, the CSP is unsatisfiable. That is, removing inconsistent values does not change the set of solutions.

Most CSP solvers use Arc Consistency (AC) as the best compromise between tree pruning and time consumption. A constraint c j is arc consistent iff for any x i ∈ var(c j ), for any v i ∈ D(x i ), v i is consistent with c j . To propagate AC during the backtrack, after each instantiation, we remove inconsistent values in domains of not yet instantiated variables x j until all constraints are arc consistent.

The quantified constraint satisfaction problem. The quantified extension of the CSP [START_REF] Bordeaux | Beyond NP: Arc-consistency for quantified constraints[END_REF] allows some of the variables to be universally quantified. A quantified constraint network consists of variables X = {x 1 , . . . , x n }, a set of domains D = {D(x 1 ), . . . , D(x n )}, a quantifier sequence Φ = (φ 1 x 1 , . . . , φ n x n ), where φ i ∈ {∃, ∀}, ∀i ∈ 1..n, and a set of constraints C. Given a quantified constraint network, the Quantified CSP (QCSP) is the question "φ 1 x 1 . . . φ n x n , C?".

Example 1. ∃x 1 ∀y 1 ∃x 2 , (x 1 = y 1 )∧(x 2 < y 1 ) with x 1 , y 1 , x 2 ∈ {1, 2, 3}. This can be read as: is there a value for x 1 such that whatever the value chosen for y 1 , there will be a value for x 2 consistent with the constraints?

As in CSP, the backtrack search in QCSP is combined with constraint filtering. Propagation techniques are heavily depending on the quantifiers of variables. In Example 1 the QCSP is unsatisfiable because for each value of x 1 , there is a value of y 1 violating x 1 = y 1 . As y 1 is a universal variable and x 1 is an existential variable earlier in the sequence, any value in the domain of x 1 that is not compatible with a value in the domain of y 1 is not part of a solution. Constraint propagation in QCSP has been studied in [START_REF] Bordeaux | Beyond NP: Arc-consistency for quantified constraints[END_REF][START_REF] Mamoulis | Algorithms for quantified constraint satisfaction problems[END_REF][START_REF] Gent | Solving quantified constraint satisfaction problems[END_REF].

Restricted quantification

One of the advantages that CSPs have on SAT problems (satisfaction of Boolean clauses) is that a CSP model is often close to the intuitive model of a problem, whereas a SAT instance is most of the time an automatic translation of a model to a clausal form, and is not human-readable. QCSP and QBF can be compared as CSP and SAT. To model a problem with a QBF, one needs to translate a model into a formula, and the QBF is not human-readable. QCSP, like CSP, should have the advantage of readability. But modeling a problem, even a simple one, with a QCSP, is a complex task. The prenex form of formulas is counterintuitive. It would be more natural to have symmetrical behaviors for existential and universal variables. We describe here two frameworks that are more modelerfriendly: Strategic Constraint Satisfaction Problem (SCSP), and QCSP + .

The strategic CSP. In SCSP [START_REF] Bessiere | Strategic constraint satisfaction problems[END_REF], the meaning of the universal quantifier is different from the universal quantifier in QCSP. It is noted ∀. Allowed values for universal variables are values consistent with previous assignments.

Let us change the universal quantifier of Example 1 into the universal quantifier of SCSPs. The problem is now ∃x 1 ∀y 1 ∃x 2 , (x 1 = y 1 ) ∧ (x 2 < y 1 ) with x 1 , y 1 , x 2 ∈ {1, 2, 3}. If x 1 takes the value 1, the domain of y 1 is reduced to {2, 3} because of the constraint (x 1 = y 1 ) that prevents y 1 from taking the same value as x 1 . This SCSP has a solution. If x 1 takes the value 1, y 1 can take either 2 or 3, and x 2 can always take the value 1 that satisfies the constraint (x 2 < y 1 ). Solving a SCSP is quite similar to solving a standard QCSP. The difference is that domains of universal variables are not static, they depend on variables already assigned in the left part of the sequence (before the universal variable we are ready to instantiate).

The quantified CSP + . QCSP + [START_REF] Benedetti | QCSP made practical by virtue of restricted quantification[END_REF] is based on the same idea as SCSP, which is to modify the meaning of the universal quantifier in order to make it more intuitive than in QCSP. It uses the notion of restricted quantification, which is more natural for the human mind than unrestricted quantification used in QCSP. Restricted quantification adds a "such that" right after the quantified variable. A QCSP + can be written as follows:

P = ∃X 1 [R X1 ], ∀Y 1 [R Y1 ]∃X 2 [R X2 ] . . . ∃X n [R Xn ], G
All constraints noted R X are called rules. They are the restrictions of the quantifiers. Each existential (resp. universal) scope X i (resp Y i ) is a set of variables having the same quantifier. The order of variables inside a scope is not important, but two scopes cannot be swapped without changing the problem. The constraint G is called goal, it has to be satisfied when all variables are instantiated. The whole problem can be read as "Is there an instantiation of variables in X 1 such that the assignment respects the rule R X1 and that for all tuples of values taken by the set of variables Y 1 respecting R Y1 , there will be an assignment for variables in X 2 . . . such that the goal G is reached?"

A QCSP + can be expressed as a QCSP. The difference between QCSP and QCSP + is the prenex form of QCSP. The QCSP + P is defined by the formula

∃X 1 (R X1 ∧ (∀Y 1 (R Y1 → ∃X 2 (R X2 ∧ (. . . ∃X n (R Xn ∧ G)))))). The prenex form of P is ∃X 1 ∀Y 1 ∃X 2 . . . ∃X n , (R X1 ∧(¬R Y1 ∨(R X2 ∧(. . . (R Xn ∧G))))
). We see that, in this formula, we lose all the structure of the problem because all information is merged in a big constraint. Furthermore, disjunctions of constraints do not propagate well in CSP solvers. Finally the poor readability of this formula makes it hard to deal with for a human user.

The example of SCSP derived from Example 1 (see above) is modelled as a QCSP + as follows:

∃x 1 ∀y 1 [y 1 = x 1 ]∃x 2 [x 2 < y 1 ], with x 1 , y 1 , x 2 ∈ {1, 2, 3}
, where is the universal constraint.

The difference between SCSP and QCSP + is mainly the place where constraints are put. A constraint of a SCSP containing a set X of variables should be placed in the rules of the rightmost variable of X in a QCSP + modeling the same problem.

In the rest of the paper, we will only consider the QCSP + , but minor modifications of our contributions should be enough to adapt them to SCSPs.

Solving a QCSP +

In this section, we focus on solving QCSP + . First, we show how we use a backtracking algorithm with universal and existential variables. Then we focus on constraint propagation in QCSP + .

As with classical CSPs or QCSPs, one can solve a QCSP + by backtracking. For each variable, we choose a value consistent with the rules attached to the variable, and we go deeper in the search tree. At the very bottom of the tree, we need to check that the assignments are consistent with the goal.

For existential variables, we do as for classical CSPs. If it is possible to assign the current existential variable according to the rules, then we can go deeper in the tree. But if there is no value consistent with the rules, it means that the current branch failed. Then we jump back to the last existential variable we instantiated and make another choice. If there is no previous existential variable, the QCSP + has no solution. Another case for which the branch can fail is when we instantiated all variables, but the assignments are not consistent with the goal.

On the other hand, if we instantiated all variables such that it is consistent with the goal, we just found a winning branch of the QCSP + . In this case we jump back to the last universal variable instantiated, we assign another value of its domain consistent with its rules and we try to find another winning branch. When all values of the universal variable have been checked and lead to winning branches, we can go back to the previous universal variable. When there is no previous universal variable, the QCSP + has a solution. If at any moment, the current universal variable we want to instantiate has an empty domain, it is a winning branch. For example if it is a game, it means that the adversary cannot play because we blocked him, or because we just won before his move.

Example 2. Let P = ∃x 1 ∀y 1 [y 1 = x 1 ]∃x 2 , x 2 = y 1 , D(x 1 ) = D(y 1 ) = {1, 2, 3}, D(x 2 ) = {1
, 2} be a QCSP + . In this QCSP + , x 1 can play any of the moves 1, 2, or 3. Then y 1 can play a move different from the move of x 1 , and x 2 can play 1 or 2. At the end, in order to win, x 2 and y 1 must have the same value.

⊥ ⊥ x 1 3 3 3 x 2 x 2 y 1 y 1 y 1 1 1 1 2 2 2
If x 1 plays 1 or 2, y 1 will be able to play 3 and will win because x 2 cannot play 3 (this value is not in its domain). The only way for the ∃-player to win is to play 3 at the first move to forbid y 1 to play 3. Then whatever the value taken by y 1 (1 or 2), x 2 will be able to play the same value. The QCSP + has a solution.

Note that in Example 2, the goal could have been a rule for x 2 . When the last variable is an existential one, its rules and the goal have the same meaning.

Propagating the constraints in QCSP +

We try to identify how it is possible to use constraint propagation to reduce the domains of variables.

Example 3.

Let P = ∃x 1 ∀y 1 [y 1 < x 1 ], ⊥. D(x 1 ) = D(y 1 ) = {1, 2, 3}.
x 1 has to choose a value, then y 1 has to take a lower value.

In Example 3, a standard CSP-like propagation of y 1 < x 1 would remove the value 1 for x 1 and the value 3 for y 1 . Like in CSPs, the value 3 in the domain of y 1 is inconsistent because whatever the value taken by x 1 , y 1 will never be able to take this value. 1 But contrary to the CSP-like propagation, the QCSP + propagation should not remove the value 1 for x 1 : if x 1 takes the value 1 he will win because y 1 will have no possible move. Let x i be a variable in a QCSP + , with a rule R xi . If we only propagate the constraint R xi on the domain of x i , we remove from its domain all values inconsistent with what is happening before. This propagation is allowed, because values removed this way cannot appear in the current search tree (when the solver will have to instantiate x i , the allowed values are values consistent with R xi ).

Let x j be another variable in a scope before the scope of x i . Now suppose that the rule R xi involves x j too (i.e., the values that x i can take depend on the values taken by x j ). If the CSP-like propagation of the constraint R xi removes some values in the domain of x j , it does not mean that x j cannot take the values removed, but that, if x j takes one of these values, then when it will be x i 's turn to play, he will not be able to take any value. Hence a QCSP + propagation should not remove these values.

Briefly speaking, it is allowed to propagate constraints from the left of the sequence to the right, but not to propagate from the right to the left. Benedetti et al. proposed the cascade propagation, a propagation following this principle.

Cascade propagation. In [START_REF] Benedetti | QCSP made practical by virtue of restricted quantification[END_REF], cascade propagation is proposed as a propagation mechanism. The idea is that propagating a rule can modify the domains of variables of its scope, but not the domains of variables of previous scopes.

In [START_REF] Benedetti | QCSP made practical by virtue of restricted quantification[END_REF], cascade propagation is implemented by creating a sequence of subproblems. Each sub-problem P i represents the restriction of problem P to its scopes from the first to the ith. That is, each P i contains all rules belonging to scopes 1 . . . i. If there are n scopes in P , P n will be the problem excluding the goal, and P n+1 = P . In a sub-problem, propagation is used as in a classical CSP. Each P i can be considered as representing the fact that we will be able to instantiate variables from the first one of the first scope to the last one of scope i according to the rules. Let P be the problem described in Example 2. Cascade propagation creates 4 sub-problems:

P 1 = ∃x 1 , P 2 = ∃x 1 ∀y 1 [y 1 = x 1 ], P 3 = ∃x 1 ∀y 1 [y 1 = x 1 ]∃x 2 , P 4 = ∃x 1 ∀y 1 [y 1 = x 1 ]∃x 2 , x 2 = y 1
For each sub-problem P 1 to P 3 , the goal is because we say a sub-problem has a solution if we can instantiate all its variables, without thinking of the goal of P . Propagation in each sub-problem can be done independently, but to speed up the process, if a value is removed from the domain of a variable, it can safely be removed from the deeper sub-problems. Furthermore if the domain of any variable in a sub-problem P k becomes empty with propagation, it means that it is impossible to do the k th move. So, from there it is no longer necessary to check the problems {P k+1 , . . . , P n+1 } since they are inconsistent too. If the scope k is universal and if P k-1 can be completely instantiated, then the current branch is a winning branch. If the scope k is an existential one and if P k-1 can be completely instantiated, the current branch is a losing branch.

Back-Propagation

In this section we present what we name back-propagation, a kind of constraint propagation which uses the information from the right part of the sequence. We also show that this propagation may not work properly in general.

Removing values in domains

The aim of constraint propagation in CSPs is to remove every value for which we know that, if we assign this value to the variable, it leads to a fail. In QCSP + , the aim of constraint propagation is to remove values in domains too. But values we can remove without loss of solution depend on the quantifiers. In the case of existential variables, the values we can remove are values that do not lead to a solution (as we do in CSPs). Intuitively, it means that the ∃-player will not play this value because he knows that he will lose with this move. If all values are removed, it is impossible to win at this point. In the case of universal variables, the values we can remove are values that lead to a solution. Intuitively, it means that the ∀-player will not play this value because he knows that it means a loss for him. If all values are removed, it means that the ∀-player cannot win, so it is considered as a win for the ∃-player.

An illustrative example

We will see how to propagate information from right to left. Back-propagation adds some redundant constraints inside the rules of variables. These constraints will help to prune domains.

Consider the Example 2 from Section 3. Let us propagate the goal (x 2 = y 1 ). It removes the value 3 in the domain of y 1 . It means that if y 1 = 3, we cannot win. So x 1 has to prevent y 1 from taking the value 3. If y 1 is able to take this value, the ∃-player will lose. The way to prevent this is to make sure that the rule belonging to y 1 , y 1 = x 1 , will force the ∀-player not to take the value 3. In other terms, the rule must be inconsistent for y 1 = 3. We can express it as (¬(y 1 = x 1 ) ∧ y 1 = 3), or ¬(3 = x 1 ), that is (x 1 = 3). This constraint can be posted as a rule for x 1 . The problem is now

P = ∃x 1 [x 1 = 3]∀y 1 [y 1 = x 1 ]∃x 2 , x 2 = y 1 , D(x 1 ) = D(y 1 ) = {1, 2, 3}, D(x 2 ) = {1, 2}.
The new rule we just added removes the inconsistent values 1 and 2 for x 1 .

General behavior

First we know that if v is inconsistent with the rules of the scope of x, we can remove it from the domain of x. Then, we can look ahead in the sequence of variables. Consider a QCSP + containing the sequence with φ = ∀ and φ = ∃ or φ = ∃ and φ = ∀:

φx i [R xi ], φy j [C j (x i , y j )], φx k [C k (x k , y j )].
Suppose that propagating C k (x k , y j ) removes the value v j in the domain of y j . As we said before, it means that if we assign v j to y j , x k will not be able to play. Then the φ-player will have to forbid the φ-player to play v j . If he is not able to forbid it, then he will lose. He can reduce the domain of y j with the rules belonging to y j and involving x i .

To ensure that y j will not forbid any move for x k , we have to make sure that the constraint C j (x i , y j ) will remove the value v j . It is equivalent to forcing ¬C j (x i , y j ) to let the value v j in the domain of y j , or equivalently forcing (¬C j (x i , y j ) ∧ y j = v j ). Hence, we can add to R xi the constraint ¬C j (x i , v j ),2 so that the φ-player is assured to have chosen a move that prevents the φ-player from doing a winning move.

Back-propagation does not work in general

In the case where there are variables between x i and x k , our previous treatment is not correct: imagine that the game always ends before x k 's turn and we are unable to detect it with constraint propagation, we should not take into account the constraints on x k . For example, consider the following problem:

Example 4. P = ∃x 1 ∀z 1 z 2 [ = (x 1 , z 1 , z 2 )]∃t 2 ∀y 1 [y 1 = x 1 ]∃x 2 , x 2 = y 1 . D(x 1 ) = D(t 2 ) = D(y 1 ) = {1, 2, 3}, D(z 1 ) = D(z 2 ) = {0, 1, 2}, D(x 2 ) = {1, 2}. The constraint = (x 1 , z 1 , z 2
) is a clique of binary inequalities between the different variables. The variable t 2 is here only to separate the two scopes of universal variables. This problem is the same as the problem in Example 2 in which we added the variables z i and the variable t 2 .

From Example 4 we can add the same constraint x 1 = 3 as we did for Example 2 in Section 4.2. Doing this, we forbid x 1 to take either the value 1 or the value 2. But if x 1 would take any of these two values, we would win since it is not possible to assign values for the different z i .

In the general case the back-propagation may remove values that are consistent, so it cannot be used as a proper propagation for QCSP + . But from the back-propagation, we can make a value ordering heuristic that will guide search towards a win, or at least prevent the adversary to win.

Goal-Driven Heuristic

In this section we present our value ordering heuristic for QCSP + . The behavior of the heuristic is based on the same idea as back-propagation. The difference is that, as it is a heuristic, it does not remove values in domains, but it orders them from the best to the worst in order to explore as few nodes as possible.

In the first part of the section, we discuss value ordering heuristics on QCSP + , and the difference with standard CSP. Afterwards, we present our contribution, a goal-driven value ordering heuristic based on back-propagation.

Value heuristics

In CSPs, a value ordering heuristic is a function that helps the solver to go towards a solution. When the solver has to make a choice between the different values of a variable, the heuristic gives the value that seems the best for solving the problem. The best value is a value that leads to a solution. If we are able to find a perfect heuristic that always returns a value leading to a solution, it is possible to solve a CSP without backtracking. But, when there is no solution or when we want all the solutions of a CSP, the heuristic, even perfect, does not prevent from backtracking. In the case of QCSP + , value ordering heuristics can be defined too. But the search will not be backtrack-free, even with a good heuristic, because of the universal quantifiers.

In QCSP + , a good value for an existential variable (like for CSP) is a value that leads to a solution (i.e., the ∃-player wins). A good value for a universal variable is a value that leads to a fail (i.e., we quickly prove that the ∀-player wins). If the QCSP + is satisfiable, the heuristic helps to choose values for existential variables, and if it is unsatisfiable, the heuristic helps to choose values for universal variables.

In the rest of the section, we describe the value ordering heuristic we propose for QCSP + .

The aim of the goal-driven heuristic

Our aim, with the proposal of our heuristic, is to explore the search tree looking ahead to win as fast as possible, to avoid traps from the adversary, and of course not to trap ourselves. For example, in a chess game, if you are able to put your opponent into checkmate this turn, you do not ask yourself if another move would make you win in five moves. Or if your adversary is about to put you into checkmate next turn unless you move your king, you will not move your knight!

In terms of QCSP + checking that a move is considered as good or bad is a question of constraint satisfaction. We will use the same mechanisms as backpropagation, i.e., checking classical arc consistency of rules.

Let see how to choose good values on different examples. In each of these example, the aim is to detect what would be a good value to try first for the first variable. In these examples, φ and φ will we the quantifiers ∃ and ∀ or ∀ and ∃.

Self-preservation. In Example 5, a rule from a scope with the same quantifier removes some values in the domain of the current variable. The φ-player tries not to block himself.

Example 5. P = φx 1 . . . φx 2 [x 2 < x 1 ] . . . , D(x 1 ) = D(x 2 ) = {1, 2, 3}. AC on the rule of x 2 removes the value 1 in the domain of x 1 . As the φ-player wants to be able to play again, it could be a better choice to try the values x 1 = 2 and x 1 = 3 at first. If x 1 = 1 is played, the player knows that he will not be able to play for x 2 .

Blocking the adversary. In Example 6, a rule from a scope with the opposite quantifier removes some values in the domain of the current variable. The φplayer tries to block the φ-player. Example 6. P = φx 1 . . . φy 1 [y 1 < x 1 ] . . . , D(x 1 ) = D(y 1 ) = {1, 2, 3}. AC on the rule of y 1 removes the value 1 in the domain of x 1 . As the φ-player wants to prevent the φ-player from playing, it could be a better choice to try the value x 1 = 1 first. If x 1 = 2 or x 1 = 3 is played, the φ-player could be able to keep playing.

If two rules are in contradiction, the heuristic will take into account the leftmost rule, because it is the rule which is the more likely to happen. We will implement this in our algorithm by checking the rules from left to right.

Annoying the adversary. Now imagine the other player finds a good value for his next turn with the same heuristic. Your aim is to prevent him from playing well, so the above process can be iterated.

This point is illustrated with the problem from Example 2:

P = ∃x 1 ∀y 1 [y 1 = x 1 ]∃x 2 , x 2 = y 1 , D(x 1 ) = D(y 1 ) = {1, 2, 3}, D(x 2 ) = {1, 2}.
The heuristic for finding values for y 1 detects that the value 3 is a good value (x 2 will not be able to win). x 1 is aware of that, and will try to avoid this case. His new problem can be expressed as P = ∃x 1 ∀y 1 [y 1 = x 1 ], ⊥ with D(x 1 ) = {1, 2, 3}, D(y 1 ) = {3}. (If the ∃-player lets y 1 take the value 3, he thinks he will lose. There may be a value for x 1 such that the ∃-player will prevent the ∀-player from making him lose). The heuristic for finding values for x 1 in P detects that x 1 should choose to play 3 first to prevent y 1 from playing well.

In the next section, we will discuss on the algorithm for choosing the best values for variables.

The algorithm

In this section, we describe the algorithm GDHeuristic (Goal-Driven Heuristic) used to determine what values are good choices for the current variable. The algorithm takes as input, the current variable and the rightmost scope that we consider. Note that we consider the goal as a scope here. It returns a set of values which are considered better to try first as defined in the above part.

Note that the aim of an efficient heuristic is to make the exploration as short as possible. If we try to instantiate a variable of the ∃-player, this means finding a value that leads to a winning branch. If we try to instantiate a variable of the ∀-player, this means finding a value that proves the ∀-player can win, that is, a losing branch. We see that in both cases, the best value to choose is a value that leads the current player to a win. Thus, in spite of the apparent asymmetry of the process, we can use the same heuristic for both players.

Algorithm 1 implements the goal driven value ordering heuristic. It is called when the solver is about to assign a value to the current variable. The aim is to give the solver the best value to assign to the variable. In fact, it is not more time consuming to return a set of equivalent values than a single value, so we return a set of values for which we cannot decide the best between them.

In this algorithm, we use different functions we explain here:

saveContext() saves the current state (domains of variables) restoreContext() restores to the last state. AC(P i ) runs the arc consistency algorithm on the problem P i quant(var) returns the quantifier of var (∃ or ∀) scope(var) returns the scope containing var dom(var) returns the current domain of var initDom(var) returns the domain of var before the first call to GDHeuristic().

We now describe the algorithm's behavior. The first call to it is done with GDHeuristic(current variable, goal). We try to find the best value for the current variable, for the whole problem (the rightmost scope to consider is the goal). Note that we could bound the depth of analysis by specifying another scope as the last one.

First of all, we save the context (line 1) because we do not want our heuristic to change the domains. The context will be restored each time we return a set of values (lines 5, 14, 17 and 19).

For each future sub-problem (i.e., containing the variables at the right of the current variable), we will try to bring back information in order to select the best values for the current variable. This is the purpose of the loop (line 2). If no information can be used, it will return the whole domain of the current variable (line 20) since all its values seem equivalent.

For each sub-problem P #Scope containing all variables from scope 1 to scope # Scope , we enforce AC (line 3). If the domain of any variable in P #Scope-1 is reduced, we will decide the aim of our move: self-preservation (line 6), blocking the adversary (line 7) or annoying the adversary (line 13). The heuristic performs at most q 2 calls to AC, where q is the number of scopes. It appears when all recursive calls (line 13) are done with scope(V ar) = LastScope -1.

The rest of the main loop is made of two main parts. The first part, from line 4 to line 8, describes the case where the domain of the current variable is modified by the scope # Scope . (Note that we know it is not modified due to an earlier scope because we have not exited from the main loop -line 2-at a previous turn.) If the current variable has the same quantifier as the scope # Scope , the heuristic returns values consistent with the scope # Scope (self-preservation line 6). If the quantifiers are different, the heuristic returns values that block any move for the scope # Scope , i.e., values inconsistent with the rules of scope # Scope (blocking the adversary line 7). The second part of the main loop, from line 9 to line 18, represents the case where a variable (V ar), between the current variable and the scope # Scope has a domain reduced (line 9). If V ar and the scope # Scope have different quantifiers (annoying the adversary line 11), V ar will try to block any move for the scope # Scope by playing one of the values not in its reduced domain (line 12). We then try to find a good value for the current variable according to this new information that we have for V ar (line 13). If V ar and the scope # Scope have the same quantifier (self-preservation line 16), V ar will try to play values in its reduced domain, that is, those that do not block its future move at scope # Scope . But we know that arc consistency has not removed any value in the domain of the current variable. This means that whatever the value selected by the current variable, V ar will be able to play in its reduced domain (i.e., good values). As a result, the heuristic cannot discriminate in the initial domain of the current var (line 18).

If no domain is modified (except the domains in scope # Scope ), we will have to check the next sub-problem (returning to the beginning of the loop).

Note that at lines 6 and 16, we immediately return a set of values for the current variable. We could imagine continuing deeper to try to break ties among equally good values for the current variable. We tested that variant and we observed that there were not much difference between the two strategies, both in terms of nodes exploration and cpu time. So, we chose the simpler one.

Experiments

We implemented a QCSP + solver on top of the constraint library Choco [START_REF] Choco | Java constraint library[END_REF]. Our solver accepts all constraints provided by Choco, and uses the classical constraint propagators already present in the library. In this section, we show some experimental results on using either our goal-driven heuristic or a lexicographical value ordering heuristic. We compare the performance of this solver with QeCode [START_REF] Benedetti | QCSP made practical by virtue of restricted quantification[END_REF], the state-of-the-art QCSP + solver, built on top of GeCode, which uses a fail-first heuristic by default. This value ordering heuristic first tries the value inconsistent with the earliest future scope. We also tried our solver with the promise heuristic [START_REF] Geelen | Dual viewpoint heuristics for binary constraint satisfaction problems[END_REF], but it was worse than Lexico. The effect of a heuristic trying to ensure that constraints will still be consistent is that a player does not want to win as early as possible (by making the other player's rules inconsistent). In all cases, the variable ordering chosen is the same: we instantiate variables in order of the sequence.

We implemented the same model of the generalized Connect-4 game for our solver and for QeCode.

Connect-4 is a two-player game that is played on a vertical board with 6 rows and 7 columns. The players have 21 pieces each, distinguished by color. The players take turns in dropping pieces in one of the non-full columns. The piece then occupies the lowest empty cell on that column. A player wins by placing 4 of his own pieces consecutively in a line (row, column or diagonal), which ends the game. The game ends in a draw if the board is filled completely without any player winning. The generalized Connect-4 is the same game with a board of m columns and n rows, where the aim is to place k pieces in a line.

At first we tried our solver on 4×4 grids, with alignments of 3 pieces. We ran QeCode and our solver with Lexicographical heuristic (Lexico) or with Goal-Driven heuristic on problems with different number of allowed moves, from 5 to 15. We compare the time taken to solve instances.

The results are presented in Figure 1 (note the log scale). There is a solution for 9 allowed moves and more. As we can see, our solver with lexicographical value ordering solves these instances faster than QeCode. It can be explained by different ways. First, it is possible that Choco works faster in propagating constraints defined as we did. The second reason is that QeCode uses cascade propagation (propagation on the whole problem for each instantiation), whereas our solver propagates only the rules of the current scope. Thus, our solver spends less time in propagation. We can see that the Goal-Driven heuristic speed up the resolution. It is about twice as fast as with Lexico. In next experiments, we only compare our solver with Lexicographical value ordering and with Goal-Driven value ordering because QeCode was significantly slower and the aim is to test the accuracy of our heuristic.

In Figure 2, the real Connect-4 game is solved. We vary the number of moves from 1 to 13 and compare the performance in terms of running time. For a number of moves less than 9, Goal-Driven heuristic does not improve the performance, but from this point, the heuristic seems to be useful. In this problem, all instances we tested are unsatisfiable. In Figure 3, we solve the game of Noughts and Crosses. This is the same problem except the gravity constraint which does not exist in this game. It is possible to put a piece on any free cell in the board. Instead of having n choices for a move, we have n×m choices. In the problem we tested, the aim is to align 3 pieces. This problem has a solution for 5 moves. We see that the Goal-Driven heuristic is very efficient here for solvable problems. Adding allowed moves (increasing the depth of analysis) has not a big influence on the running time of our solver with the Goal-Driven heuristic. The heuristic seems to be efficient when there are more allowed moves than necessary to finish the game.

Discussion. More generally, when can we expect our Goal-Driven heuristic to work well? As it is based on information computed by AC, it is expected to work well on constraints that propagate a lot, i.e., tight constraints. Furthermore, as it actively uses quantifier alternation and tries to provoke wins/losses before the end of the sequence, it is expected to work well in problems where there exist winning/losing strategies that do not need to reach the end of the sequence.

Conclusion

In QCSP + , we cannot propagate constraints from the right of the sequence to the left. Thus, current QCSP + solvers propagate only from left to right. In this paper, we have analyzed the effect of propagation from right to left. We have derived a value ordering heuristic based on this analysis. We proposed an algorithm implementing this heuristic. Our experimental results on board games show the effectiveness of the approach.

Algorithm 1 : 2 AC(P # Scope ) 3 if 4 ReducedDomain 6 return ReducedDomain else 7 return 8 if

 1234678 GDHeuristic input: CurrentV ar, LastScope Result: set of values begin saveContext() 1 for #Scope ← scope(CurrentVar ) + 1 to LastScope do dom(CurrentVar ) = initDom(CurrentVar ) then ← dom(CurrentVar ) restoreContext() 5 if quant(CurrentVar ) = quant(#Scope) then initDom(CurrentVar ) \ ReducedDomain else any domain has been reduced before scope #Scope then 9 Var ← leftmost variable with reduced domain in P # Scope -1 10 if quant(Var ) = quant(#Scope) then 11 dom(Var ) ← initDom(Var ) \ dom(Var ) 12 values ← GDHeuristic(CurrentVar, scope(Var ))

Fig. 1 .Fig. 2 .

 12 Fig. 1. Connect-3, on 4x4 grid

Fig. 3 .

 3 Fig. 3. Noughts and Crosses, on 5x5 grid

Note the difference with the QCSP case for which a removal of value in a universal domain means a fail of the whole problem.

the constraint C in which we replaced the occurrences of yj with the value vj

Supported by the ANR project ANR-06-BLAN-0383-02.


domain: spi phys

text:
François Vuillot

Sâm Landier

Thomas Renaud

Christophe Benoît

Laurent Sanders

Intersected Octree Conformal Grid Strategies for Applications to Aeroacoustic Computations of the LAGOON, Landing Gear Model, using the CEDRE unstructured Flow Solver

come   L'archive ouverte pluridisciplinaire

Introduction and context

Aircraft noise is a societal concern and landing gears contribute significantly to the generated noise in approach and landing configurations. Landing gears are characterized by their complex geometry and numerous works have been carried out to develop and validate aeroacoustics simulations to predict the associated noise (e.g. [START_REF] Sanders | LAGOON: CFD/CAA coupling for Landing Gear Noise and Comparison with Experimental Database[END_REF], [START_REF] Manoha | Summary of the LAGOON solutions from the Benchmark problems for Airframe Noise Computations -III Workshop[END_REF]). Most of them associate a time resolved flow solution, to capture the acoustic sources, to an acoustic computation, to estimate the resulting far field noise. Due to the geometric complexity, unstructured grids are required and may necessitate meticulous work to optimize (e;g. [START_REF] Vuillot | Applications of the CEDRE unstructured flow solver to landing gear unsteady flow and noise predictions[END_REF], [START_REF] Vatsa | Aeroacoustic Simulation of a Nose Landing Gear in an Open Jet Facility using FUN3D[END_REF], [START_REF] De La Puente Cerezo | Zonal Detached Eddy Simulation of a simplified nose landing-gear for flow and noise predictions using an unstructured Navier-Stokes solver[END_REF]). In this context, Lattice Boltzmann Methods (LBM) have become popular as they propose to combine automatic grid generation and high CPU efficiency and produced remarked results (e.g. [START_REF] Casalino | Lattice-Boltzmann Aeroacoustic Analysis of the LAGOON Landing-Gear Configuration[END_REF], [START_REF] Murayama | Computational study of low-noise fairings around tire-axle region of a two-wheel main landing gear[END_REF]). The automatic grid generation is facilitated by the use of advanced wall models that do not require resolution of complex details of boundary layer flow, ranging from attached to detached regimes, that are produced by the complex geometries and flow environment of landing gears. Navier-Stokes (NS) solvers on the contrary rely on precise boundary layer solution that require complex grids, even in the unstructured approach, to handle the attached boundary layer regimes, that require strong grid anisotropy, as well as detached regimes and their trailing flow, that require grid isotropy. The grid construction work can therefore become a complex process. The simplification of this process is then an important challenge for industrial applications. The present work details a multi-year effort at ONERA in that direction.

Objective

The present effort aims at demonstrating the interest of some automatic grid generation strategies for NS solvers while preserving the detailed boundary layer flow solution. The present approach focuses on the details of the matching region where the automatically generated grid merge with the boundary layer grid generated around the landing gears geometry. In that sense the present work can be viewed as an alternative to the present efforts on immersed boundary conditions (IBC, [START_REF] Mincu | Immersed boundary conditions for high order CAA solvers -Aeroacoustics installation effects, assessment[END_REF]), described elsewhere, where the background grid directly intersect the landing gears body. In the present paper, the LAGOON (LAnding Gear nOise database for CAA validatiON) test case is retained. The LAGOON project, founded by AIRBUS, and involving ONERA, DLR and University of Southampton, aimed at providing an extensive database of flow and noise measurements for the development of new CFD/CAA strategies for landing gear noise predictions. The geometry used is based on a highly simplified 2:5 scaled AIRBUS single aisle aircraft nose landing gear. It was extensively tested for both aerodynamics and aeroacoustics measurements at ONERA's F2 and CEPRA19 wind tunnels [START_REF] Manoha | LAGOON : an Experimental Database for the Validation of CFD/CAA Methods for Landing Gear Noise Prediction[END_REF], [START_REF] Manoha | LAGOON : further analysis of aerodynamic experiments and early aeroacoustics results[END_REF]. The basic configuration was then proposed in the framework of the AIAA BANC international workshop and has been computed by several teams [START_REF] Manoha | Summary of the LAGOON solutions from the Benchmark problems for Airframe Noise Computations -III Workshop[END_REF]. The geometry of the LAGOON landing gear is presented in Figure 1.

Methods

This section presents the ONERA tools that were used in the present effort. They have been used in a number of past works, demonstrating their ability to produce high quality aerodynamic and acoustic results. First the aerodynamic flow is computed using the ONERA in house CEDRE code which is a multi-physics, fully unstructured solver, developed at ONERA with main applications in the energetics and propulsion fields [START_REF] Chevalier | CEDRE: development and validation of a multiphysic computational software[END_REF], [START_REF] Refloch | CEDRE software[END_REF]. It is based on a cell centered finite volume approach that deals with generalized polyhedral grids (cells can have any number of faces and faces can have any number of vertices). Its Navier-Stokes solver, CHARME, relies on spatial discretization based on second order MUSCL schemes and time integration schemes based on explicit or implicit GMRES schemes (up to third order). Several turbulence models are available, ranking from one-equation or twoequations RANS models, to LES Smagorinsky models and ZDES hybrid RANS-LES approach. The computations performed in the present paper were run with the ZDES approach [START_REF] Spalart | A new version of detached-eddy simulation, resistant to ambiguous grid densities[END_REF], [START_REF] Deck | Recent improvements in the zonal detached eddy simulation (ZDES) formulation[END_REF], based on a SA (Spalart-Allmaras) RANS model. This methodology has been applied to several landing gear configurations and proved to provide very satisfactory results [START_REF] De La Puente | On LAGOON nose landing gear CFD-CAA computation over unstructured mesh using a ZDES approach[END_REF], [START_REF] De La Puente | Nose landing gear flow and noise predictions on unstructured grid using a cell-centered Navier-Stokes code[END_REF], [START_REF] De La Puente | Aeroacoustic simulations of landing gears with unstructured grids and a ZDES turbulence model[END_REF], [START_REF] De La Puente Cerezo | Zonal Detached Eddy Simulation of a simplified nose landing-gear for flow and noise predictions using an unstructured Navier-Stokes solver[END_REF].

The ZDES wall pressure is stored on the landing gear surface and is subsequently used in an acoustic postprocessing step, to reconstruct the far field noise, relying on a Ffowcs-Williams and Hawkings approach (FW-H), available in the ONERA in house KIM code [START_REF] Prieur | Aeroacoustic integral methods, formulation and efficient numerical implementation[END_REF], [START_REF] Rahier | Investigation Of Integral Surface Formulations For Acoustic Post-processing Of Unsteady Aerodynamic Jet Simulations[END_REF].

In the present work, in continuation of the previous paper [START_REF] Vuillot | New Unstructured Grid Strategies for Applications to Aeroacoustic Computations of the LAGOON, Landing Gear Model, Using the CEDRE Unstructured Flow Solver[END_REF], the ONERA Cassiopée tool [START_REF] Benoît | Cassiopee: a CFD pre-and post-processing tool[END_REF] is used to automatically generate the computational grid. Starting from a surface grid that includes all the desired refinements to describe the flow around the landing gear geometry, the Cassiopée software is used to first generate the prisms layers around the landing gear surface, with a prescribed prism height distribution and then to generate an automatic octree grid, based on specified grid size in different regions of the computational domain. The particular options to handle the conformal matching between the two independently generated grids are discussed later on.

Past work

Two grid strategies are considered as detailed in the previous work presented in 2017 [START_REF] Vuillot | New Unstructured Grid Strategies for Applications to Aeroacoustic Computations of the LAGOON, Landing Gear Model, Using the CEDRE Unstructured Flow Solver[END_REF]. The first one is the simplest where the background grid is based on an octree grid that is interrupted before reaching the landing gear body and its attached boundary layer grid made of prismatic layers, the gap being filled by tetrahedra, much like the Dragon grid strategy [START_REF] Liou | Progress in Grid Generation: From Chimera to DRAGON Grids[END_REF], [START_REF] Kao | Direct replacement of arbitrary grid-overlapping by nonstructured grid[END_REF]. The second strategy, with great benefit in the total cell count by removing the tetrahedra of the dragon approach, is to simply let the octree grid intersect the prismatic layers. In both strategies, the resulting grid is handled by the generalized polyhedral approach available in the CHARME NS solver, that treats all particular cells generated in the grid generation process, either the octree refinement, where one cubic cell is matched to four smaller cubic cells, or the intersected cells, as polyhedral cells in a fully conservative way. It must be emphasized that the second, intersected approach, generates complex, potentially concave, cells that present a challenge for the NS solver. In the previous work [START_REF] Vuillot | New Unstructured Grid Strategies for Applications to Aeroacoustic Computations of the LAGOON, Landing Gear Model, Using the CEDRE Unstructured Flow Solver[END_REF] that challenge was not properly handled and the corresponding computation could not be carried out, due to solver instability at these particular cells, that led to strongly reduce the computation time step and hence increased the total CPU cost. As a consequence the previous work could only conclude on the fist, dragon like approach, the second one being left to further treatment of problematic concave cells, which is the subject of the present paper.

Present work

The present work will detail and comment recent progress made on the second approach. First the intersection module was enhanced by a regularization of concave cells and the NS solver was upgraded in its treatment of polyhedral cell definition, allowing a robust cell definition and face orientation. This permitted to carry out the second strategy to completion from aerodynamic flow solution to acoustic far field computations. In addition the previous dragon grid approach was revisited with a refined background grid (grid OM13). These new results are rapidly presented in the present abstract and will be detailed and discussed in the final paper. Table 1 below summarizes the different grids that were used in the present effort. [START_REF] Vuillot | New Unstructured Grid Strategies for Applications to Aeroacoustic Computations of the LAGOON, Landing Gear Model, Using the CEDRE Unstructured Flow Solver[END_REF].

It is worth to mention that the present OM22 grid is based on previous octree definition of OM12 and that the identical polyhedra count with the refined OM13 grid is simply coincidental as it includes both the octree (hexahedra) and the real polyhedra resulting from octree refinements and cut cells resulting from the intersection work for the OM2i grids. The fact that OM21 and OM22 grids show the same cell count is due to the relative small number of the regularized cells of the OM22 grid. Figure 2 illustrates the general grid topology generated by the Cassiopée octree grid generation module.

These cell counts can be compared to the previous G1 and G2 unstructured grids that were especially tailored to the flow physics of the LAGOON landing gear [START_REF] De La Puente | Aeroacoustic simulations of landing gears with unstructured grids and a ZDES turbulence model[END_REF], see Table 2. These overall octree grid requirements being specified, two strategies are being considered to complete the computational grid. The first strategy, grids termed OM1i, will proceed in filling the gap between the octree grid internal boundary and the prism layers external boundary with tetrahedra, much like the dragon grid strategy exposed in [START_REF] Liou | Progress in Grid Generation: From Chimera to DRAGON Grids[END_REF], [START_REF] Kao | Direct replacement of arbitrary grid-overlapping by nonstructured grid[END_REF]. The second strategy, grids termed OM2i, will directly intersect the octree grid with the prismatic boundary layer grid. Several grids were generated, for different maximum resolution in the inter-wheel cavity and landing gear close vicinity. OM12 and OM22 share the same octree grid definition while OM13 benefits from a refined definition in the inter-wheel cavity. Figure 3 presents general views of the OM13 and OM22 grids used in the present paper and Figure 4 show the details in the vicinity of the LAGOON wheels. This figure can be compared to Figure 5 which shows the previous grid G2 . These figures illustrate the differences of the considered grids in the inter-wheel and wake regions which may have some importance on the final results. Close-up views of the different matching approaches are illustrated by Figure 6 and Figure 7, respectively for the intersected and dragon approaches.

Table 2: Grids and cell counts of previous work [17]

OM13 OM22

New results

This paragraph will quickly illustrate the new results obtained. The computations were run until overall flow establishment was achieved. As proposed in [START_REF] De La Puente Cerezo | Zonal Detached Eddy Simulation of a simplified nose landing-gear for flow and noise predictions using an unstructured Navier-Stokes solver[END_REF] one convenient indicator of flow establishment is the main effort on the landing gear body, represented by the drag coefficient. A total of 300 ms were computed and the last 120 ms were used for flow statistics, PSD computations and acoustics computations.

A. Mean aerodynamic results

First the computed Cp distributions around the left wheel for the OM12 (OM13 still to be processed) and OM22 grids are compared to measurements on Figure 9. Then Figure 10 presents the mean velocity profile from the left wheel at the 90 deg. position, compared to measurements for OM12 and OM22 computations. These figures illustrate the good agreement obtained and that both grid definition produce a good description of the mean aerodynamic field. Power Spectral Density (PSD) computed (using 11 overlapping blocks and Hann windowing) from the 120 ms of available unsteady wall pressure with the different grids are illustrated on Figure 14 and Figure 15 for selected pressure transducers. Figure 14 presents the PSD of pressure signals recorded along the right wheel (see Figure 13) and shows an overall satisfactory agreement, from pressure sensors pk01, pk04, pk09 and pk19, in terms of observed levels and presence of frequency peaks at 1000 and 1500 Hz. Figure 15 presents the PSD of pressure signals recorded at other locations (pk15, pk17, pk20 and pk23). Again an overall satisfactory agreement is observed. Good comparison with the previous computation of grid G1 is also observed, except for a consistently smaller cut-off frequency which results from the coarser grid definition of the octree grids used in OM computations. The better results observed for the pk15 transducer is attributed to a finer surface grid size for the OM grids in this critical flow area, where the flow detaches.

C. Far field acoustic results

In this section, the far field results will detailed and commented. Figure 16 and Figure 17 present the far field arc measurement locations, along the Fly Over and Side Line arcs. These arcs are centered at the wheel center and have a 6m radius (20D, with D the wheel diameter). They comprise 12 microphones which are spaced by 10 deg. approximately.

During the computation, 120 ms of wall pressure data were stored on the skin of the landing gear. These data are input to the ONERA KIM code, to compute the far field at the fly-over (FO) and side-line (SL) microphones. The acoustic far field results are illustrated by Figure 18 and Figure 19 presenting the far field results along the Fly Over arc, for the different grids. Despite the consistently lower cut-off frequency observed for the OM grids computations, already mentioned above, the results are quite encouraging. This reduced cut-off frequency can be explained by the octree definition around the landing gear that was not as fine as previous G1 or G2 grids, especially in the inter-wheel cavity and near field of the landing gear. This choice of aggressive grid cell count reduction, was made from the beginning, in line with the proof of concept objective assigned to the present computations. This can be easily handled in future works, once the feasibility of the proposed approach is established.

Figure 1 :

 1 Figure 1: LAGOON baseline configuration.

Figure 2 :Figure 3 :

 23 Figure 2: overall grid topology from OM grids

Figure 4 :Figure 5 :Figure 6 :Figure 7 :

 4567 Figure 4: Detailed view around the landing gear wheels for OM13 and OM22 grids

Figure 8 :

 8 Figure 8: Convergence history of OM22 computation from computed drag on the Lagoon wall

Figure 9 :Figure 10 :Figure 11 :Figure 12 :

 9101112 Figure 9: Pressure distribution along the left wheel. Solid line computation OM12 (top), OM22 (bottom), symbols measurements. Cp (left); Cp_rms (right)

Figure 13 :

 13 Figure 13: experimental pressure transducer locations

Figure 14 :Figure 15 :

 1415 Figure 14: unsteady pressure PSD on the wheel. px , Kxd, Kxd3, Kxi: computations respectively on G1, OM12, OM13, OM22, pkx: measurements

Figure 16 :

 16 Figure 16: Far field microphones, Fly over arc.Figure 17: Far field microphones, Fly over and Side line arcs.

Figure 17 :

 17 Figure 16: Far field microphones, Fly over arc.Figure 17: Far field microphones, Fly over and Side line arcs.

Figure 18 :

 18 Figure 18: Fly over arc, comparison of computed and measured (black dots) OASPL

Figure 19 :

 19 Figure 19: comparison of computed and measured (black line) PSD of microphones on the Fly over arc

Flow

Table 1 : Grids and cell counts

 1

		OM11	OM12	OM13*	OM21**	OM22*
	prisms	16M	19M	20M	16M	16M
	polyhedra (octree and cut cells for OM2i)	2M	4M	6M	6M	6M
	tetrahedra	12M	12M	12M	-	-
	Total	30M	35M	38M	22M	22M
	* : new grids constructed for the present paper.
	** : OM21 did not produce valuable results

Scientific advisor, Multi-Physics for Energetics department: francois.vuillot@onera.fr

Research scientist, Aerodynamics, Aeroelasticity, Acoustics department

Acknowledgments

The present work has been supported by internal grants from the ONERA scientific direction. The authors would like to thank E. Manoha from ONERA for fruitful discussions and help in conducting the present work. They also thank Airbus, ONERA and NASA for providing the LAGOON test case inside the BANC international workshop framework. Supports from Ph. Grenard from ONERA in handling OM2i grid computations are kindly acknowledged by the first author.

American Institute of Aeronautics and Astronautics 15

The full paper will present and discuss the full acoustic results obtained in the course of the present effort.