PhD Matthieu Champagne
email: matthieu.champagne@insa-lyon.fr

Mathieu Renouf
email: mathieu.renouf@univ-montp2.fr

Yves Berthier
email: yves.berthier@insa-lyon.fr

Modeling wear for heterogeneous bi-phasic materials using discrete elements approach

A proper understanding of the processes of friction and wear can only be reached through a detailed study of the contact interface. Empirical laws, such as Archard's, are often used in numerical models. They give good results over a limited range of conditions when their coefficients are correctly set, but they cannot be predicted: any significant change of conditions requires a new set of experimental coefficients. In this paper, a new method, the use of Discrete Element Models (DEM), is proposed in order to tend to predictable models. As an example, a generic biphasic friction material is modelled, of the type used in aeronautical or automotive brake systems. Micro-scale models are built in order to study material damage and wear under tribological stress. The models show what could be achieved by these numerical methods in tribological studies, and how they can reproduce the behavior and mechanisms seen with real-life friction materials without any empirical law or parameter.

Tribological context

Understanding the wear process is an essential part of the study of dry friction problems. Even if friction and wear are common and every-day phenomena, they are nonetheless complex multi-scale and multi-physical mechanisms [START_REF] Berthier | Handbook of Materials Behavior models[END_REF]. Friction and wear depend on parameters such as material properties, surface characteristics, stress cycles, mechanisms, etc. All these parameters are strongly connected and cannot easily be studied separately. Moreover, no single model can be used to describe a friction and wear process at all scales, whilst taking account of all these parameters. Being of industrial and economic importance, wear has led to many studies to try to understand the wear process and to predict its effects. For this reason, both experimental and numerical studies are mandatory: experimental studies are limited by cost, inner contact visibility, complex instrumentation, etc. and require the support of a numerical model to be useful; but the model needs to be fed with experimental results, measurements and observations. Numerical studies of friction and wear found in the literature often use theoretical laws based on simple and general hypotheses represented through different parameters. Their goal is to offer a quantitative prediction of wear "magnitude" which depends on these parameters. These laws are supposed to be adaptable to any system under study, accounting for normal contact force or sliding distance. For example, Archard's well known law [START_REF] Archard | Contact and rubbing of flat surfaces[END_REF] is widely used in numerical models to predict the worn volume obtained under given conditions (normal force and sliding distance). This law has been cleverly written but uses a constant coefficient, which must be chosen to adapt the law to the phenomenon being studied. Other laws such as Rhee's [START_REF] Rhee | Wear equation for polymers sliding against metal surfaces[END_REF] and Barwell's [4] are made to fit experimental results so as to predict the long term wear effect. Most of the time, the final result is given as the worn volume. Industrial interests encourage the use of such laws, emphasising the needs of long-term fatigue studies, and taking the "wear magnitude" obtained under given conditions and during a given time as the key output of the models.

From a numerical point of view, different methods can be found in the literature applied to these studies, based on two main approaches. The first is applied at the macro scale and uses a wear law or criterion as an input to the model, not always related to the problem being studied, to compute a worn volume or a worn surface. The second is applied at the micro scale and studies the wear mechanism itself, trying to reproduce experimental phenomena explicitly and giving wear parameters as an output.

In the first approach, the Finite Element Method (FEM) is probably the most widely used and popular method, particularly at macro scale. For example, Chongyi et al [START_REF] Chongyi | Study on numerical method to predict wheel/rail profile evolution due to wear[END_REF] use such a method to model the wheel / rail contact, using local results (such as normal pressure and sliding velocity) in an Archard-like law as wear model, to predict worn material volume after each time iteration. This volume is then eliminated from the existing material and both geometry and meshing are corrected. In other work, FEM models are used to predict wear using an empirical law [START_REF] Lee | Experimental and numerical analysis of friction and wear behaviour of polycarbonate[END_REF] where an abrasive wear coefficient, obtained from experiments, can be found. This approach can also be found in [START_REF] Agelet De Saracibar | On the numerical meodeling of frictional wear phenomena[END_REF][START_REF] Torrance | A method for calculating boundary friction and wear[END_REF][START_REF] Abubakar | Wear prediction of friction material and brake squeal using the finite element method[END_REF]. In the work of Gallego et al [START_REF] Gallego | Multiscale computation of fretting wear at the blade/disk interface[END_REF][START_REF] Gallego | A fast and efficient contact algorithm for fretting problems applied to fretting modes i, ii and iii[END_REF], the local results of a higher scale FEM model are used in a semi-analytical contact solver. Archard's law is then used to compute wear distribution and the new worn surface is updated in the FEM model. The advantage of such a model is that it is fast enough to perform cyclic wear computation and fatigue life studies.

Although useful to some extent, these models are not comprehensive: they simply create a fit to an existing process under precise conditions (for example temperature). The wear coefficient used in Archard's law reveals the empirical aspect of this law, and using it in inappropriate conditions can lead to incoherent results. As regards wear modeling, the main drawback of such models is that wear is only considered as a material removal process. The third body and wear particles are not taken into account, leading some authors to puzzle over the decrease in wear volume seen in experiments but not in their models [START_REF] Jourdan | A numerical model for multidirectional wear[END_REF], while this in fact could be explained by a third body layer accommodation mechanism [START_REF] Berthier | Velocity accomodation in friction[END_REF]. Others point out that third body studies are needed as a perspective for their models [START_REF] Torrance | A method for calculating boundary friction and wear[END_REF]. Sometimes, due to this lack of comprehensivity, predictive models using Archard's laws need a limit condition in worn volume computation, and this parameter is often arbitrary (for example a maximum allowable wear depth in [START_REF] Chongyi | Study on numerical method to predict wheel/rail profile evolution due to wear[END_REF]).

In contrast to previous models, micro scale numerical models can provide specific laws or parameters directly deduced from modelled wear mechanisms, and thus can be an alternative way to feed higher scale models. The continuum mechanics (FEM model and Linear Fracture Mechanics [START_REF] Sun | Etude mcanique des couches minces en tribologie: une approche numrique[END_REF], the continuous Granular Kinetic Lubrication model [START_REF] Higgs | Granular flow lubrication : continuum modeling of shear behaviour[END_REF]) have been used in models with such objectives, but continuum methods quickly show their limits when modeling a discontinuous environment such as the third body layer. Discrete mechanics methods can then be considered: the goal is no longer to use a global or local wear law, but explicitly to study material degradation, wear particle creation, and particle life within the contact interface (i.e. the role of the third body layer). For example, some authors [START_REF] Muller | A cellular automaton model to describe the three-diemnsional friction and wear mechanism of brake systems[END_REF][START_REF] Dimitriev | Numerical simulation of typical contact situations of brake friction materials[END_REF][START_REF] Dmitriev | A multilevel simulation of friction and wear by numerical methods of discrete mechanics and a phenomenological theory[END_REF] use the movable Cellular Automata method, a very simplified way of modeling a granular flow (as the third body can be); but it lacks some important aspects for studying wear process (such as thermochemical aspects). However, the Discrete Element Method (DEM) appears to be very promising for studying material degradation and third body flows in a contact. Under simple shear [START_REF] Fillot | A granular dynamic model for the degradation of material[END_REF], where a wear law is obtained, the authors find that Archard's law is applicable in a limiting case where all wear particles are expelled from the contact (which is not always the case!), and under fretting-like conditions [START_REF] Renouf | Third body flow during a wheel/rail interaction[END_REF], where these models proved to be a useful and powerful tool for investigating the wear process. These models use the conceptual approach of the tribological triplet [START_REF] Berthier | Handbook of Materials Behavior models[END_REF][START_REF] Godet | The third-body approach: a mechanical view of wear[END_REF] and the tribological circuit model [START_REF] Berthier | Velocity accomodation in friction[END_REF], which are tools for understanding and interpreting wear processes. They provide descriptive schemes which can lead to comprehensive models. As a consequence, comprehensive micro scale models which take third body into account so as to understand local wear phenomena with wear laws and parameters as outputs, are being steadily developed. Yet at the micro scale, no study has yet really considered the material heterogeneity of the third body layer. When frictional materials are considered, such as brake pads [START_REF] Osterle | A comprehensive microscopic study of third body formation at the interface between a brake pad and brake disc during the final stage of a pin-on-disc test[END_REF] or Carbon/Carbon composites [START_REF] Kasem | Interdependence between wear process, size of detached particles and co2 production during carbon/carbon composite friction[END_REF], shearing a homogeneous material is no longer representative, and local improvements are needed.

In the present paper, it is proposed to use the DEM method in order to investigate the friction and wear process of a biphasic composite under tribological conditions (pressure and shear velocity). As a first step, a simplified material composed of a matrix and vertical inclusions is considered. The goal of these studies is to model first body degradation (cracks and damage) at the micro scale, wear particle creation and flow, and the influence of inclusions on the process. To do so, Cohesive Zone Models (CZM) are implemented in a DEM model. The influence of different parameters is studied (pressure, CZM parameters), and finally a method to obtain parameters representative of wear phenomena and friction is given. Section 2 presents the numerical model used to describe the bi-phasic composite. Section 3 presents the numerical results and section 4 proposes a synthesis and comparison with experimental results from the literature.

Numerical framework 2.1 NSCD overview

Several discrete element methods have been used for tribological purposes [START_REF] Fillot | A granular dynamic model for the degradation of material[END_REF][START_REF] Elrod | Numerical experiments with flows of elongated granules[END_REF][START_REF] Jerier | Normal contact between rough surfaces by the discrete element method[END_REF] each based on a different formalism. The one used in the present work is the Non-Smooth Contact Dynamics approach (NSCD), initially developed by Moreau and Jean [START_REF] Moreau | Unilateral contact and dry friction in finite freedom dynamics[END_REF][START_REF] Jean | The non smooth contact dynamics method[END_REF]. Often used in the context of granular material investigation [START_REF] Radjai | Force distributions in dense two-dimensional granular systems[END_REF], it has also been used several times in tribological applications [START_REF] Cao | Coupling continuous and discontinuous descriptions to model first body deformation in third body flows[END_REF][START_REF] Renouf | Discrete numerical modeling of granular materials[END_REF][START_REF] Renouf | Multiphysical modeling of third-body rheology[END_REF].

The NSCD approach uses an implicit time discretized formulation of the equation of motion written for a collection of particles. Since the number of contacts is higher than the number of particles (dense particle assemblies), the interaction between particles is not considered at the scale of each individual particle but at each contact scale.

To describe the evolution of a collection of particles, the equation of dynamics can be written as:

M q + F int (t, q, q) = F ext (t, q, q) + R, (1)
where M represents the mass matrix, F int (t, q, q) are the internal force and the nonlinear inertia terms, F ext (t, q, q) the external forces, and R the contact forces. Vector q represents the vector of generalized degrees of freedom while q and q denote the generalized velocity and acceleration vectors respectively. To transfer information from the contact frame (local level) to the body frame (global level) (cf. Fig. 1), two linear mappings, H and its transpose H * , are used. So it is possible to relate the local contact force vector r and the local relative velocity vector u to the global body contact force vector R and the body velocity vector q thus: R = Hr u = H * q (2)

Both mappings depend on local information such as the local frame defined at each contact point and the network connectivity of each contact (cf. Fig. 1). By using a system (2) and a θ time integrator scheme [START_REF] Jean | The non smooth contact dynamics method[END_REF], it is possible to reformulate equation (1) in the contact frame. This allows to us write, at each time step, the system (3) containing the equations of motion:

Wr -u = b law α [u α , r α ] = true, α = 1, n c (3)
Where the matrix W is the Delassus operator, containing local information (such as local frames and contact points) allowing it to be used at the particle scale. The vectors u and r are respectively the vectors containing the relative velocity and the mean contact impulse for all the contact points of all particles. b represents the free relative velocity calculated by taking into account the external forces only. The θ-method is used for time discretization and a classical non-linear Gauss-Seidel algorithm is used to solve the system (3) [START_REF] Jean | The non smooth contact dynamics method[END_REF]. The approach benefits from a parallel version to ensure reasonable CPU times [START_REF] Renouf | A parallel version of the Non Smooth Contact Dynamics algorithm applied to the simulation of granular media[END_REF].

Interaction law for tribological purposes

A key point of the system (3) is the definition of the law connecting the unknown u and r. Indeed, though unilateral contact with Coulomb friction may be used to model a granular material, it is not sufficient for tribological purposes, especially when the discretely packed particles initially represent a continuum, from which particles may be detached by tribological stress then subsequently evolve through interaction between themselves and with the continuum. Consequently, two interaction laws are used: firstly, a cohesive zone model (CZM) [START_REF] Elices | The cohesive zone model : advantages, limitations and challenges[END_REF][START_REF] De Borst | Numerical aspects of cohesive-zone models[END_REF] is used to model the continuum with discrete packing, from which particles may be detached according to a damage criterion (first body law); and secondly, a unilateral cohesive contact law which models the interactions between detached particles as well as interactions between detached particles and the continuum (third-body law).

First body law

In the literature, CZM [START_REF] Elices | The cohesive zone model : advantages, limitations and challenges[END_REF][START_REF] De Borst | Numerical aspects of cohesive-zone models[END_REF] are usually combined with finite elements to model crack evolution in materials such as concrete [START_REF] Elices | Cohesive cracks modelling of a simple concrete : experimental and numerical results[END_REF], zircaloy [START_REF] Pérales | Two field multibody method for periodic homogenization in fracture mechanics of nonlinear heterogeneous materials[END_REF], etc. Such a model allows multi-cracking studies where no pre-crack is needed, nor crack path predicted. Here the method is implemented in a DEM model, which leads to an innovative way of studying the wear mechanism. The tribological history of the first body (damage accumulation) and its degradation allow the creation of third body and its life in the contact to be modelled. The present model, used to describe the interaction between 1st body particles, was first proposed by Raous et al [START_REF] Raous | A consistent model coupling adhesion, friction, and unilateral contact[END_REF] and is based on five parameters: C n and C t , the normal and tangential stiffness respectively; w, the de-cohesion energy; b, the viscosity associated with the evolution of inter-particle adhesion and µ the local friction coefficient. The intensity of the adhesion of the interaction is characterized in this model by the internal variable β, introduced by Frémond [START_REF] Frémond | Adhérence des solides[END_REF]. It takes values between 0 and 1 (0 is no adhesion and 1 is perfect adhesion). A damageable stiffness is used for the interface, depending on β, to ensure good continuity between contact conditions throughout the process.

∂β ∂t = - 1 b (w -β(C n u 2 n +C t u 2 t )) -, (4)
where (.) -denotes the negative part. For the purposes of the present work, inter-particle friction is zero (µ=0), as is viscosity (b = 0). The initial interactions are perfectly intact (β=1) and normal and tangential stiffness are considered equal. This means that the local model is defined by two parameters, i.e. C n and w. √ wC n while the corresponding distance defining the elastic range (without damage), g c , is equal to w/C n . Note that when such a law is used in discrete element assemblies, care is needed during the contact detection process. Indeed, to avoid overlap between particles, an alert distance is used to anticipate a potential contact. Usually, this distance should not be too large so as to minimize the number of contacts (active or not). With the presence of CZM, the alert distance should not be so small as to truncate the CZM graph, which would lead to numerical overestimation of the dissipation of energy.

Third body law

For the purposes of this work, a non-smooth cohesive contact law is used. It may be seen as the non-smooth extension of a force which derives from a Lennard-Jones potential. Two parameters are considered: a cohesive force γ that represents a constant force in opposition to body detachment and a distance d w that defines the attraction area of each body. If body attraction areas do not overlap, then the contact status is non contact (r n = 0 and g > d w ).Otherwise, the following linear complementarity problem is solved:

g ≥ 0, r n + γ ≥ 0, g • (r n + γ) = 0. (5)
Therefore the contact status is cohesive when γ < r n < 0 and g ≤ d w . Finally the contact status is stick when the gap vanishes (g = 0) and r n ≥ 0. When γ = 0 then d w = 0 and cohesion vanishes. In this case the description of the contact is the classical Signorini condition used to simulate dry systems [START_REF] Jean | The non smooth contact dynamics method[END_REF].

Model

Figure 3 represents a typical sample of the biphasic material used in this work: a uniform matrix and several vertical inclusions. The inclusions represent 10% of the whole surface. CZM parameters are chosen according to the properties of the particles in interaction (matrix-matrix; matrix-inclusion; inclusion-inclusion). The cohesion forces used in Equation ( 5) have been chosen with regard to the dimensionless parameter η [39] defined as,

η = γ Pd ( 6
)
where P is the normal pressure and d the particle diameter. Consequently, if P and d are constant, the evolution of eta is directly related to the evolution of γ. In shear simulations of cohesive granular flows [START_REF] Rognon | Dense flows of cohesive granular materials[END_REF], the measured global friction coefficients exhibit a plateau for values of η less than 1 and a large increase above this value. The different values of γ have been chosen here to describe the plateau, except for the higher value of γ (i.e. γ = 10 -2 N) which corresponds to a value of η equal to 1.33.

The value of CZM stiffness has been chosen to ensure that the global stiffness of the material corresponds to a range of values close to those of friction materials. The matrix stiffness is less than that of the inclusions (with sufficient contrast), and the order of magnitude of these parameters is adjusted according to model size, particle size and the external forces applied. The upper boundary, where normal force is applied, is connected to the matrix/inclusions via CZM interactions (and so it is part of the upper 1st body) while the lower boundary, where shear velocity is applied, is connected to the sample through the unilateral cohesive law (so that it represents the lower 1st body -see Fig. 3). The degrees of freedom of upper and lower boundaries (other than those where normal force and shear velocity are applied) are blocked. The model is 100 micrometers long and 50 micrometers high. Particles have an average radius of 0.375 micrometers; this parameter is chosen as a compromise so that inclusions are detailed enough, yet are of the same order of magnitude as the wear particle that can be observed in friction and wear studies. The numerical parameters are summarized in table 1. Pressure and shear velocity (i.e. tribological inputs) are applied to the model and periodic conditions are used to simulate an infinite flow. The shear velocity is constant in the simulation and equal to 1 m/s, typical of tribological processes. In the simulation, there was no velocity decay. As velocity is constant, the value of the force applied to the domain can influence on the degradation process. As the aim of this work is to understand the degradation process, the applied force (and consequently the pressure) should be high enough to produce transition phenomena. To calibrate the value of F, three values were tested: 0.1, 1 and 10 N (see Fig. 4). As mentioned above, the range of pressure should be chosen so that the analysis of material behavior is not biased by a disproportionate pressure effect. This range is around 10 MPa for our studies (i.e. F = 1 N). Above this value, the material is crushed (see Fig. 4 c), and below, the pressure applied is not sufficient to produce any degradation in a reasonable computational time (see Fig. 4 a).

Numerical measures

To analyze the simulation results, different macroscopic quantities are used: the global damage, the macroscopic friction and the stress tensor. Each definition is given hereinafter.

Global damage

The CZM law used to model the first body is associated with a local parameter β α (α ∈ [1, n c ]). Using such parameter, it is possible to define two new variables.

The first, denoted

β i (i ∈ [1, n b ]
) is the equivalent damage of a single particle and is defined as:

β i = 1 n 0 i ∑ α∈L i β α , (7)
where n 0 i and L i are the initial number of contacts and the list of contact of particles i, respectively. As for the parameter associated with each contact, β i ranges from 0 to 1. If β i is equal to 1 all the contacts of the particle i are preserved. If β i is equal to 0, all its contacts are broken and the particle becomes a third-body particle.

In a similar way, the second variable defined, β, corresponds to the global damage of the sample and is defined as:

β = 1 n 0 ∑ α∈L β α , (8)
where n 0 and L are the initial number and the list of contacts in the whole sample, respectively. When plotted for a given geometry, a value of 1 (red color on the simulation snapshots) means that the sample is intact: the more the curve tends to lower values, the more the sample is damaged. To sum up, the graph represents the integrity of the sample.

Global friction

Experimentally, the friction coefficient is measured as the ratio between the force in the sliding direction and the force applied to the system. To reproduce these measurements in the simulations, the global friction coefficient µ(t) is defined as:

µ(t) = ∑ n LB i=1 r i x (t) F (9)
where r x is the component of the force in the sliding direction, exerted on one of the n LB particles composing the lower boundary, while F denotes the normal force applied to the upper body.

Equivalent stress tensors

In a discrete element assembly, an equivalent strain tensor may be computed [START_REF] Radjai | Force distributions in dense two-dimensional granular systems[END_REF] to reveal macroscopic quantities such as the hydrostatic pressure p or the deviatoric stress q. The stress tensor of a particle P, σ(P), is defined as typical for granular material as [START_REF] Radjai | Force distributions in dense two-dimensional granular systems[END_REF] :

σ i j (P) = 1 vol(P) ∑ α∈L p r α i l α j , (10)
where, for two particles i and j, r α is the force exerted on the contact, α, l the distance between the contact point and the centre of mass of the particle P, and L p the contact list of the particle P.

In a biphasic material, such a tensor may be computed within each phase (matrix and inclusion) and also at the matrixinclusion interface. Moreover, when dealing with first body degradation, it is also possible to perform such a computation for the first body, the third-body and for the interface between them; then, computing the value of the q/p ratio can give an idea of where the relative motion is accommodated. 3.1 Wear of homogeneous material First, a simulation using homogeneous models was performed in order to obtain reference results for the analysis of the degradation of biphasic materials. Two homogeneous models were created with equal CZM parameters: a value of C N of 10 7 for homogeneous model 1 and a value of 10 5 for homogeneous model 2. A heterogeneous model combining the two values of C N was also created: the larger value for the interactions between inclusion particles and the lower value for the interactions between matrix particles as well as between inclusion and matrix particles. In this case, when debris particles were created, they evolved with cohesion-less interactions. The resulting damage evolution is presented in Fig. 5. Different observations may be made. First, the lower damage value was obtained for homogeneous model 1 i.e. the material with the highest CZM stiffness parameter. The highest value was not obtained for homogeneous model 2 but for the heterogeneous model. Consequently, the damage evolution of a biphasic material could not be limited to the damage evolution of a homogenous model composed of a single phase. Even if damage values are different, a stabilization of the global damage curve can be observed for all models. Damage stabilization, which occurs for each model, can easily be explained by the creation of a third-body layer which plays a protective role, accommodating the relative velocity by shearing within itself (see Fig. 6). This phenomenon is possible because of the presence of periodic conditions, representing an infinite contact where all debris particles stay in the contact, whereas in a "real" mechanism the contact can retain more or less particles depending on the evolution of the whole system (first body vibrations, separation, acceleration,...). The role and influence of this third-body layer will be discussed more precisely later on.

Wear of heterogeneous material

In order to study the influence of inclusion location and length, different microstructures were created (see Fig. 7), all with the same ratio between inclusion surface and matrix surface. Three heterogeneous models were used, characterized by different inclusion lengths, denoted by l, reaching the frictional surface: mixed inclusions, short inclusions (l < H/2), long inclusions l < H/2, where H is the height of the sample. In each case, the stiffness of the matrix is always smaller than the stiffness of the inclusions. The same inputs were applied to each model: a pressure of 10 MPa and a sliding velocity of 1 m/s. The normal stiffness C N has a value of 10 7 for the interactions between inclusion particles and a value of 10 5 for the interactions between matrix particles as well as between inclusion particles and matrix particles. To activate damage faster, cohesion was allowed between the moving first body (lower body) and all the particles which constitute the upper degradable first body. With these tribological inputs, the damage in each model evolved in the same way (a transitory stage and a steady stage) but to a different final value of damage for each case (see Fig. 8). To learn more about the damage mechanisms in each model, the mechanism of third-body layer creation and composition was investigated, just as in real life contact. Fig. 9 shows the global damage of each phase in each model: matrix/matrix, inclusion/matrix and inclusion/inclusion.

The results clearly show that the percentage of broken contacts is larger for the matrix/matrix interactions than for the matrix/inclusion or inclusion/inclusion interactions. Indeed the overall magnitude of broken matrix/inclusion contacts is also relevant (around 25% of contacts are broken). The inclusion/inclusion contacts are much less affected (the maximum damage observed is close to 2.5%). The damage of each phase occurs mainly during the first quarter of the simulation time. Then, once all contacts are broken, debris particles evolve with cohesion-less interactions (just as in the homogeneous models), creating a "fluid-like" layer which easily accommodates the relative motion between first bodies. This film prevents upper first body degradation and is responsible for the steady state observed in the global damage graphs. The action of the layer is reinforced by the periodic boundaries which allow all the particles to be retained in the contact, maintaining a continuous internal flow of particles once the layer is established. shows that the third-body layer, once established, has a "protective" role which explains the steady state observed in Fig. 9 : the process which damages the material is stopped.

Keeping this phenomenon in mind, it can easily be seen that to reduce the amount of global damage, the microstructure should allow the creation of a third-body layer, easily and quickly. In heterogeneous microstructures, stiff inclusions have a large influence: if they are too long or not mobile enough to allow the circulation of debris particles, the creation of the third-body layer is disturbed. Thus, accommodation still occurs in the first body volume which continues to be deformed. Microstructures with longer inclusions reaching the friction surface (microstructure 3), show the greatest final damage value (see Fig. 8). In Fig. 9, it can be seen that each microstructure contains the same relative amount of broken inclusion/matrix links. Yet whilst this amount is sufficient, with microstructure 2, to allow the creation of a third-body layer and to stabilize its damage (stabilization of the number of intact matrix/matrix links ), this is not the case for the others. When the circulation of debris particles is disturbed, there occurs a so-called "corner effect" between the remaining matrix and the inclusions: the matrix degrades until the inclusions become more mobile. Damage continues to accumulate (transient state) until the inclusions gain sufficient mobility to allow particles to circulate freely enough for the third body layer to be established; both damage and friction then stabilize (steady state).

Similar observations may be made of the macroscopic friction. Figure 11 presents the evolution of the q/p ratio for the first and the third-body, compared to the global friction coefficient (see Eq. 9). During the transient phase, the friction coefficient value is closer to the q/p ratio of the first body, underlining the fact that accommodation takes place mostly within the first body. The ratio then gradually falls to reach a value close to the q/p ratio of the third-body, showing that accommodation takes place within the third-body layer during the steady state. 0 0,1 0,2 0,3 0,4 time (ms) 0 0,1 0,2 0,3 0,4 0,5 first body q/p third-body q/p friction coefficient Fig. 11. q/p values of the equivalent strain tensors of 1st and 3rd body, compared to global friction coefficient.

To understand the impact of interaction forces on the distribution of inclusion geometries, simulations were performed for the three microstructures with constant C N values for interactions between inclusion particles (equal to 10 7 ) and for interactions between matrix particles (equal to 10 5 ). The value of the interaction between inclusion particles and matrix particles takes the value of 10 3 , 10 5 and 10 7 . The results of the evolution of β are presented respectively in Fig. 12a, Fig. 12b and Fig. 12c. If there is some variation in the evolution of β in the first part of the simulations, the microstructures are always ranked the same (β G2 < β G1 < β G3 ) at the end of the simulated process (c.f. Fig. 12). This shows that the inclusion shape and distribution is more important than the inclusion/matrix interface strength. The greater this strength, the greater the damage. The inclusion/matrix interactions limit the damage in the structure like the fuse in an electrical circuit. If the threshold value is too large, the high rigidity of inclusions directly affects the matrix, favoring its degradation (stress and deformation being transmitted from inclusions to matrix). When the threshold value is small, the interface quickly breaks down, and the inclusions are detached from the matrix allowing more accommodation at lower degradation. The impact of this "fuse effect" is also observed in the evolution of the global friction µ (c.f. Fig. 13).

When interaction between inclusion particles and matrix particles is high, the global friction remains high for longer, except for microstructure 2 whose global friction and damage are not so much affected by the different threshold values.

However, Fig. 13 shows that the friction coefficient always has the same final value during its steady regime, whatever the model. This is easily explained by the fact that during the steady state, friction is controlled by the shearing of the third-body layer alone (where, as shown above, all relative velocity is accommodated). The media and interaction laws for this layer are the same in all models which therefore show the same global friction coefficient; a possible improvement of the models is then to introduce adhesive forces within this medium, and this is considered in the next section.

Wear of heterogeneous material with adhesive third-body

Physico-chemical aspects are known to be very important in tribological phenomena [START_REF] Kasem | Interdependence between wear process, size of detached particles and co2 production during carbon/carbon composite friction[END_REF][START_REF] Renouf | Multiphysical modeling of third-body rheology[END_REF]. Particles are always reactive, and this should be represented in a numerical model. To understand the influence of such reactivity on the damage process, three levels of cohesive forces were tested. The cohesive force intervenes in the media once CZM links are broken (i.e. β α = 0). The values of cohesive force chosen were 10 -4 , 10 -3 , 10 -2 (common values for this particle size and external forces) and will be called "weak", "medium" and "strong" forces, respectively. The cohesion for the contact between the two first bodies is the same as between the debris particles.

Figure 14 presents the evolution of the global damage β with the different cohesion values (i.e. 10 -4 , 10 -3 and 10 -2 ) for model 2. The results are compared to a full cohesion-less simulation (no cohesion within third-body particles and between particles and the lower first body) and the previous case (no cohesion within third-body particles and a cohesion of 10 -2 between particles and the lower first body). The evolution of the global damage is strongly dependent on the cohesion between the detached particles. For a given simulated time, a larger cohesion value leads to greater global damage. However, with strong cohesion, the global damage reaches a quasi steady state; yet that is not the case with lower cohesion. In this case the damage process seems to start and continue for a time longer than the run time of 0.4 ms. Consequently, it is difficult to give a direct correlation between global damage and the cohesion value. It can also be noted that the example discussed in the previous section with no cohesion between third-body particles and a cohesion of 10 -2 between particles and the lower first body was more damaged than the full cohesion-less example. This underlines the influence of the initial cohesion between the first bodies. If the cohesive properties of the debris particles are important, the initial surface reactivity has also much influence on the damage process. Figure 15 shows the appearance of microstructure 2 with the weak (a), medium (b) and strong (c) cohesion value for debris particles after 0.1 ms and at the end of the simulation. Such visualizations corroborate the comments concerning Fig. 15. For the strong cohesion (case (c)), snapshots at the chosen times are quasi identical, in terms of degradation and deformation. This is not the case for the weak and medium cohesion values where there are numerous differences between the snapshots at different times. It is interesting to note that Fig. 15a at t = 0.4 resembles Fig. 15b at time t = 0.1. This shows the need for longer simulations to determine whether the cohesion is simply an accelerator of the damage process (same damage level for different times). However, the global damage level is higher with strong adhesion forces, due to adhesive wear; thus 3rd body layer thickness is greater with high cohesion (debris particles being always in contact) than without cohesion.

Figure 16 proposes an interpretation of the influence of the debris particle cohesion in terms of global friction evolution, for the case of microstructure 2. For strong cohesion, the global friction is nearly constant during the simulation process (the transitory stage being very short), while for the weak and medium cohesion values, it increases during the process, showing that no steady state has been reached. It can also be noted that the sample used in the previous section presents an initial friction value close to the value for strong cohesion and then decreases quickly to the value of the full cohesion-less simulation. If the initial surface reactivity leads to a large friction value (as well as a large damage gradient), the third-body layer flow could subsequently become dominant in the frictional process.

The results for other microstructures (see Fig. 17) show that when the adhesion parameter is high enough to allow the microstructure to reach a steady state, inclusion distribution and length have the same effects as without adhesion (β G2 < β G1 < β G3 ). The mechanism of accommodation in the 3rd body layer still occurs, and microstructures that allow the easy creation of the layer still show the least damage. The effects of other parameters, as mentioned above, require longer simulations to confirm that the trends are the same. To conclude, it can be said that with adhesion, different levels of damage and friction coefficient arise, giving an "environmental parameter" which affects the wear of a microstructure without modifying the general behavior that depends on its geometrical characteristics.

Discussion

Some of the phenomena predicted here can be found in experimental studies, particularly those studying heterogeneous friction materials. In [START_REF] Osterle | A comprehensive microscopic study of third body formation at the interface between a brake pad and brake disc during the final stage of a pin-on-disc test[END_REF], the authors study the friction of brake pad material; Fig. 18 shows a SEM-micrograph and a sketch of the friction interface of such materials, with heterogeneities reaching that surface. The authors show that the 3rd body layer is "mainly responsible for the friction response", and that the nature and quantity of particles retained in the contact influence the formation of this film. The same observation is made for homogeneous materials, but in heterogeneous materials the friction surface is obviously particular. Wear troughs that appear at the surface, influenced by the presence of micro-structure and inclusions reaching the surface, play an important role in facilitating or hampering the circulation of particles in the contact, influencing the behavior of the 3rd body layer and thus influencing the friction and wear behavior of the whole contact. The nature of the particles is also significant: they may come from the matrix or from inclusions which do not have the same (mechanical, chemical...) properties. The same kind of observations are made for other heterogeneous friction materials, such as Carbon/Carbon friction composites (see Fig. 19). In such materials, micro-structure and porosity influence the life of the 3rd body in the contact. For example they may allow "particle pools" to form which remove the "dangerous" character of the "corner effect" discussed above, by helping to feed the third-body layer [START_REF] Kasem | Interdependence between wear process, size of detached particles and co2 production during carbon/carbon composite friction[END_REF]. The numerical results given above, use internal cohesions of 0 and 10 -2 which are not representative of such a material: The first leads to a powdery third-body and the second to an abrasive third-body. One could imagine that, according to the physical properties of the interface, the cohesion value may evolve during the sliding process, but this idea needs experimental verification. To conclude, numerical models like those presented in this study may be useful for understanding heterogeneous material behavior in terms of friction and wear, depending on micro-structure geometrical characteristics, material mechanical properties and interactions occurring in the 3rd body layer. The use of the Discrete Element Method to model the wear of a material is not an innovation in itself. However, the use of the NSCD method with CZM and adhesive laws gives very interesting advantages, of which the most important is to model the evolution of damage throughout the life of the contact. Every aspect of a tribological problem at the local scale can be taken into account, even if temperature and thermo-mechanical aspects are still to be studied. More important, the predicted local friction coefficient and wear are key parameters which could be used in higher scale finite element models, replacing the arbitrary, and sometimes meaningless, parameters currently used. All in all, the model is a numerical tool of experimental investigation. Apart from the consideration of temperature, other improvements could be made to overcome the limitations highlighted earlier in this paper. First of all, an upscaling of the models will be made, with bigger models and comparatively smaller inclusions. This should lead to a reduction in the bias due to the "scale effect", and should allow other material parameters, such as the volume ratio of inclusions, to be studied more precisely. 3D models will also be built, with cylindrical inclusions, in order to avoid the so called "scraping effect" and to introduce a better description of mechanical systems. The introduction of a "wear flow" with evacuation of debris particles outside the contact is also planned.

Fig. 1 .

 1 Fig. 1. Representation of the linear mappings of the contact frame (local level) onto body frame (global level). The black dot represents a contact point connected to the local frame while the white dots represent the centre of the mass of particles connected to the contact point by linear mapping H

Fig. 2 .

 2 Fig. 2. Cohesive Zone Model force profile ; (a) elastic range definition and (b) beta value.

Figure 2

 2 Figure 2 gives an example of a typical CZM graph. The maximum traction force r c is equal to √ wC n while the corresponding distance defining the elastic range (without damage), g c , is equal to w/C n . Note that when such a law is used in discrete element assemblies, care is needed during the contact detection process. Indeed, to avoid overlap between particles, an alert distance is used to anticipate a potential contact. Usually, this distance should not be too large so as to minimize the number of contacts (active or not). With the presence of CZM, the alert distance should not be so small as to truncate the CZM graph, which would lead to numerical overestimation of the dissipation of energy.

Fig. 3 .

 3 Fig. 3. (a) Granular model principle and micro-structure description: dark-gray particles represent inclusions while light-gray particles represents the matrix and (b) sketch of the model with 1st bodies (upper and lower) and 3rd bodies shown; the granular model shown in (b) is the abradable part of the upper 1st body shown in (a)

Fig. 4 .

 4 Fig. 4. Comparison between heterogeneous materials under growing normal pressure, under the same shear velocity, at the same simulation time : (a) pressure of 1 MPa (0.1 N as normal force), (b) pressure of 10 MPa (1 N), (c) pressure of 100 MPa (10 N).

Fig. 5 .

 5 Fig. 5. Evolution of global damage for two homogeneous materials and a heterogeneous material under normal pressure and shear velocity.

Fig. 6 .

 6 Fig. 6. Steady state of a homogeneous material submitted to tribological solicitations with the establishment of a protective third-body layer (seen at the bottom of the model).

Fig. 7 .

 7 Fig. 7. Geometry of the three heterogeneous models used, characterized by different properties of inclusions reaching the frictional surface: (a) mixed inclusions, (b) short inclusions, (c) long inclusions.

Fig. 8 .

 8 Fig. 8. Evolution of global damage of the three heterogeneous models.

Fig. 9 .

 9 Fig. 9. Evolution of global damage of the three heterogeneous models in each phase of the material : (a) matrix 1, (b) inclusion/matrix and (c) inclusions.

Fig. 10 .

 10 Fig. 10. Visualisation of the evolution of β i during the tribological process for the geometry 2 at time: (a) t=0.025, (b) t=0.075, (c) t=0.10 and (d) t=0.3.

Figure 10

 10 Figure 10 presents the aspect of material (microstructure 2) during the tribological process. During the transient phase (t < 0.1, see Fig. 9 and Figs. 10a,b,c) the matrix damage mainly appears where inclusions reach the friction surface, where matrix particles contribute, step by step, to the formation of the third-body layer. A comparison of Figs. 10c and Figs. 10dshows that the third-body layer, once established, has a "protective" role which explains the steady state observed in Fig.9: the process which damages the material is stopped.Keeping this phenomenon in mind, it can easily be seen that to reduce the amount of global damage, the microstructure should allow the creation of a third-body layer, easily and quickly. In heterogeneous microstructures, stiff inclusions have a large influence: if they are too long or not mobile enough to allow the circulation of debris particles, the creation of the third-body layer is disturbed. Thus, accommodation still occurs in the first body volume which continues to be deformed. Microstructures with longer inclusions reaching the friction surface (microstructure 3), show the greatest final damage value (see Fig.8). In Fig.9, it can be seen that each microstructure contains the same relative amount of broken inclusion/matrix links. Yet whilst this amount is sufficient, with microstructure 2, to allow the creation of a third-body layer and to stabilize its damage (stabilization of the number of intact matrix/matrix links ), this is not the case for the others. When the circulation of debris particles is disturbed, there occurs a so-called "corner effect" between the remaining matrix and the inclusions: the matrix degrades until the inclusions become more mobile. Damage continues to accumulate (transient state) until the inclusions gain sufficient mobility to allow particles to circulate freely enough for the third body layer to be established; both damage and friction then stabilize (steady state).Similar observations may be made of the macroscopic friction. Figure11presents the evolution of the q/p ratio for the first and the third-body, compared to the global friction coefficient (see Eq. 9). During the transient phase, the friction

Fig. 12 .

 12 Fig. 12. Evolution of the global damage β for value of the interaction between inclusion particles and matrix particles of (a) 10 3 , (b) 10 5 and (c) 10 7

Fig. 13 .

 13 Fig.[START_REF] Berthier | Velocity accomodation in friction[END_REF]. Evolution of the global friction µ for the value of the interaction between inclusion particle and matrix particles of (a) 10 3 , (b) 10 5 and (c)10 7

Fig. 14 .

 14 Fig. 14. Global damage with different level of adhesion force in the third-body layer. The plain line correspond to the result of the previous section.

Fig. 15 .

 15 Fig. 15. Aspect at time t = 0.1 ms and t = 0.4 ms of damaged material (geometry 2) for a weak (a), medium (b) and strong (c) cohesion value for debris particles.

Fig. 16 .Fig. 17 .

 1617 Fig.[START_REF] Muller | A cellular automaton model to describe the three-diemnsional friction and wear mechanism of brake systems[END_REF]. Friction coefficient of the geometry 2 with different level of adhesion force in the 3rd body layer.

Fig. 18 .

 18 Fig. 18. Interface between brake pad friction materials, (a) SEM-micrograph and (b) sketch (courtesy of W. Oesterle [22])

Fig. 19 .

 19 Fig. 19. (a) Interface between Carbon/Carbon friction materials, SEM-micrograph (courtesy of H. Kasem [23]) and (b) Optical microscopy cross section view of CC composite after friction showing heterogeneous aspect and 3rd body "corner effect"

Table 1 .

 1 Numerical parameters used in the model.

	Sample length	100 µm	Computation time	0.4 ms
	Sample height	50 µm	Time step	10 -7 ms
	Particle mean radius	0.5 µm	CZM stiffness	10 3 , 10 5 , 10 7 MPa
	Particle number	10 000	Decohesion energy	10 -2 J/m
	Cohesion force	0, 10 -4 , 10 -3 , 10 -2 N	Sliding velocity	1 m/s
			Normal pressure	10 MPa

Acknowledgements

Part of this work is funded by the Agence Nationale de la Recherche in the framework of the ANR-10-RMNP-0013 project.


Gérard Bailly
email: gerard.bailly@icp.inpg.fr

Frédéric Elisei
email: frederic.elisei@icp.inpg.fr

Stephan Raidt
email: stephan.raidt@icp.inpg.fr

Alix Casari
email: alix.casari@icp.inpg.fr

Antoine Picot
email: antoine.picot@icp.inpg.fr

Embodied conversational agents : computing and rendering realistic gaze patterns

Keywords: Embodied conversational agents, talking faces, audiovisual speech synthesis, face-to-face interaction

We describe here our efforts for modeling multimodal signals exchanged by interlocutors when interacting face-to-face. This data is then used to control embodied conversational agents able to engage into a realistic faceto-face interaction with human partners. This paper focuses on the generation and rendering of realistic gaze patterns. The problems encountered and solutions proposed claim for a stronger coupling between research fields such as audiovisual signal processing, linguistics and psychosocial sciences for the sake of efficient and realistic human-computer interaction.

Introduction

Building Embodied Conversational Agents (ECA) able to engage a convincing faceto-face conversation with a human partner is certainly one of the most challenging Turing test one can imagine [START_REF] Cassell | Embodied Conversational Agents[END_REF]. The challenge is far more complex than the experimental conditions of the Loebner Prize1 where dialog is conducted via textual information: the ECA should not only convince the human partner that the linguistic and paralinguistic contents of the generated answers to human inquiries have been built by a human intelligence, but also generate the proper multimodal signals that should fool human perception. We are however very close to being able to conduct such experiments. Automatic learning techniques that model perception/action loops at various levels of human-human interaction are surely key technologies for building convincing conversational agents. George, the talkative bot that won the Loebner Prize 2005, learned its conversation skills from the interactions it had with visitors to the Jabberwacky website, and through chats with its creator, Mr Carpenter. Similarly the first Turing test involving a non interactive virtual speaker [START_REF] Geiger | Perceptual evaluation of video-realistic speech[END_REF] has demonstrated that image-based facial animation techniques are able to generate and render convincing face and head movements.

Combining a pertinent dialog management with convincing videorealistic animation is still not sufficient to reach a real sense of presence [START_REF] Riva | Being there: concepts, effects and measurements of user presence in synthetic environments[END_REF]. The sense of "being there" requires the featuring of basic components of situated face-toface communication such as mixed initiative, back channeling, turn taking management, etc. The interaction requires a detailed scene analysis and a control loop that knows about the rules of social interaction: the analysis and comprehension of an embodied interaction is deeply grounded in our senses and actuators and we do have strong expectations on how dialogic information is encoded into multimodal signals.

Appropriate interaction loops have thus to be implemented. They have to synchronize at least two different perception/action loops. On the one hand there are lowfrequency dialogic loops. They require analysis, comprehension and synthesis of dialog acts with time scales of the order of a few utterances. On the other hand there are interaction loops of higher frequency. These include the prompt reactions to exogenous stimuli such as sudden events arising in the environments or eye saccades of the interlocutor. The YTTM model [START_REF] Thórisson | Natural turn-taking needs no manual: computational theory and model from perception to action[END_REF] of turn-taking possesses three layered feedback loops (reactive, process control and content). Content and reactive loops correspond to the two loops previously sketched. The intermediate process control loop is responsible for the willful control of the social interaction (starts and stops, breaks, back-channeling, etc). In all interaction models, information-and signal-driven interactions should then be coupled to guarantee efficiency, believability, trustfulness and user-friendliness of the information retrieval. We describe here part of our efforts for designing virtual ECAs that are sensitive to the environment (virtual and real) in which they interact with human partners. We focus here on the control of eye gaze. We describe the multiple scientific and technological challenges we face, the solutions that have been proposed in the literature and the ones we have implemented and tested. 2 Gaze and mutual gaze patterns.

The sampling process with which the eye explores the field of sight consists of fixations, smooth pursuits and saccades. Saccades are the rapid eye movements (approx. 25-40ms duration) with which the high-resolution central field (the fovea) is pointed to the area of interest. Fixations (and slow eye movements) of relatively long duration (300ms) enable the visual system to analyze that area (e.g. identify objects or humans). They are characterized by microsaccades that compensate for retinal adaptation. Functionally these two components correspond to two complementary visual streams, a 'where '-and a 'what'-stream (Grossberg 2003). The 'what'-stream is responsible for object recognition, the 'where'-stream localises where these objects and events are. The 'what'-stream is assumed to be allocentric, i.e. object centered, whereas the 'where'-stream is egocentric, i.e. observer centered. An additional mechanism, called smooth pursuit, locks slowly moving interest points in the fovea. Scrutinizing a scene (either a static picture or a video) is more complicated than just moving from one salient feature of the scene to the next. Perceptual salience is not the only determinant of interest. The cognitive demand of the scrutinizing task has a striking impact on the human audiovisual analysis of scenes and their interpretation. [START_REF] Yarbus | Eye movements during perception of complex objects. Eye Movements and Vision[END_REF] showed notably that eye gaze patterns are influenced by the instructions given to the observer during the examination of pictures. Similarly Vatikiotis-Bateson et al (1998) showed that eye gaze patterns of perceivers during audiovisual speech perception are influenced both by environmental conditions (audio signal-to-noise ratio) and by the recognition task (identification of phonetic segments vs. the sentence's modality). Attention is also essential: [START_REF] Simons | Gorillas in our midst: sustained inattentional blindness for dynamic events[END_REF] suggest that attention is essential to consciously perceive any aspect of a scene. Major changes to scenes may be ignored ('change blindness') and objects may even not be perceived ('attentional blindness') if they are not in our focus of attention. Finally, eye gaze is an essential component of face-to-face interaction. Eyes constitute a very special stimulus in a visual scene. Gaze and eye-contact are important cues for the development of social activity and speech acquisition [START_REF] Carpenter | Joint attention, cultural learning and language acquisition: Implications for children with autism. Communicative and language intervention series. Autism spectrum disorders: A transactional perspective[END_REF]: theories of mind2 [START_REF] Scassellati | Foundations for a theory of mind for a humanoid robot[END_REF] rely on the ability of computing eye direction of others. In conversation, gaze is involved in the regulation of turn taking, accentuation and organization of discourse [START_REF] Argyle | Gaze and mutual gaze[END_REF][START_REF] Kendon | Some functions of gaze-direction in social interaction[END_REF]. We are also very sensitive to the gaze of others when directed towards objects of interest within our field of view or even outside [START_REF] Pourtois | Dissociable roles of the human somatosensory and superior temporal cortices for processing social face signals[END_REF]). In the Posner cueing paradigm (1980), observers' performance in detecting a target is typically quicker in trials in which the target is present at the location indicated by a former visual cue than in trials in which the target appears at the uncued location. The outstanding prominence of the human face in this respect was shown by [START_REF] Langton | Reflexive visual orienting in response to the social attention of others[END_REF]2000). [START_REF] Driver | Shared attention and the social brain : gaze perception triggers automatic visuospatial orienting in adults[END_REF] have shown that a concomitant eye gaze also speeds reaction time. The data presented so far show that gaze control is a complex cognitive activity that not only depends on the environment -that of course includes other humans -but also on our own cognitive demands.

Most robots incorporate a computational model for observing their environment. Mobile robots use the results for planning displacements and avoid obstacles. Anthropoid robots embed cameras at eyes location and the movements that are necessary for controlling their field of view informs indirectly human partners on their focus of interest. Most sociable anthropoid robots control gaze for communication needs: robots constructed by the Humanoid Robotics Group at the MIT Artificial Intelligence Laboratory have been designed to mimic the sensory and motor capabilities of the human system. The robots should be able to detect stimuli that humans find relevant, should be able to respond to stimuli in a human-like manner. The first computational theory of mind built by Scassellati [START_REF] Scassellati | Foundations for a theory of mind for a humanoid robot[END_REF] was already incorporating a complex control of eye gaze et neck movements for pointing and signalling shared visual attention. Robita developed at Waseda University [START_REF] Matsusaka | Conversation Robot Participating in Group Conversation[END_REF] points to objects and regulates turn taking in group conversation by gaze direction. Most gaze control strategies for ECA are more elementary. When no contextual audiovisual stimuli are available (e.g. for web-based ECA), the basic strategy consists in globally reproducing blinks and gaze paths learnt by statistical models from human data [START_REF] Lee | Eyes alive[END_REF]. Attempts to regulate an ECA gaze from video input are quite recent: [START_REF] Itti | Realistic avatar eye and head animation using a neurobiological model of visual attention[END_REF] propose a visual attention system that drives the eye gaze of an ECA from natural visual scenes. This system consists in computing three maps: (a) a saliency map, a bottom-up path that computes a global saliency for each pixel of the current image that combines color, orientation and flow cues; (b) a pertinence map, a top-down path that modulates the saliency map according to cognitive demands (e.g. follow white objects… that may cause attention blindness to events connected to darker areas of the scene), and (c) an attention map that is responsible with the observation strategy that switches between the successive points of interest.

The attention map also handles temporary Inhibition Of Return (IOR) so that all points of interest in a scene have a chance to be in focus. Although mostly tested on still images, the object-based attention framework proposed by [START_REF] Sun | Hierarchical object-based visual attention for machine vision[END_REF] is based on a multi-scale segmentation of the image that computes a hierarchy of the points of interest as function of salience, granularity and size of the objects. We recently implemented a eye gaze control system that builds on Itti et al proposal but replaces the pertinence and attention maps with a detector/tracker of regions of interest as well as with a temporary inhibition of return that rules the content of an attention stack [START_REF] Xu | Dissociable neural mechanisms supporting visual short-term memory for objects[END_REF]) that memorizes position and appearance of previous regions of interest. The object detector is responsible for detecting known objects (such as faces) that triggers further predetermined scrutation (such as focus on mouth and eyes for speaking faces) and for building statistical models of the shape and appearance of unknown objects (based yet on color histogram). If necessary, the detector uses the built characteristics to perform a smooth pursuit using a Kalman filter (see Figure 3). Once the object of interest does not move and fixation has been long enough for recognizing/building a model of the object, the object is pushed in the attention stack and the system seeks for the next salient object. While none is found, the system pops back the objects stored in the attention stack. The stack is also used for storing temporally the characteristics of an object that has not been entirely processed when a more salient object bumps in the scene: the exogenous stimulus is urgently processed and the system goes back to its normal sequential exploration. Two natural videos have been used for testing (see Figure 3): the first scene features a subject waiving colored objects in front of him while the second one features several person passing behind a subject facing the camera. Gaze patterns computed by our system have been compared to human ones recorded using a non invasive Tobii® eyetracker: main differences occur when innate objects have a stronger intrinsic salience than faces in the scene (see Figure 4). Subjects are in fact more sensitive to faces than clothing since human faces are of most importance for understanding natural scenes. When interacting with people, events occurring in the immediate environment have also an impact on gaze and gaze interpretation. For instance, [START_REF] Pourtois | Dissociable roles of the human somatosensory and superior temporal cortices for processing social face signals[END_REF] have shown that facial expressions of your interlocutor is interpreted very differently depending on whether his gaze are directed to you or not.

Gaze patterns in face-to-face interaction

When interacting, people mostly gaze at the other's face and gesturing. While speech is clearly audiovisual [START_REF] Stork | Speechreading by Humans and Machines[END_REF], facial expressions and gaze also

Left

Right

Top

Bottom

inform us about the physical, emotional and mental state of the interlocutor. Together with gesturing, they participate in signaling discourse structure, ruling turn taking and maintaining mutual interest. Context-aware ECA should be reactive to gaze patterns of their interlocutors and implement these complex interaction rules [START_REF] Thórisson | Natural turn-taking needs no manual: computational theory and model from perception to action[END_REF]. Most data on eye movement of perceivers during audiovisual speech perception have been gathered using non interactive audiovisual recordings [START_REF] Vatikiotis-Bateson | Eye movement of perceivers during audiovisual speech perception[END_REF]. Several experiments have however shown that live gaze patterns are significantly different from screening [START_REF] Gullberg | Visual attention towards gestures in face-toface interaction vs. on screen[END_REF]: social rules have in fact a strong impact on communication when interacting face-to-face. We conducted preliminary experiments for determining the natural gaze interplays between interlocutors according to their social status, their roles in the conversation and the dialog task. We illustrate below the complex gaze patterns already observed in a simple task such as repeating the other's utterance. The experimental setting involves two cameras coupled with two eye trackers (see Figure 1b) that monitor the gaze patterns of the interlocutors when interacting through two screens. We checked that this setting enables an acceptable spatial cognition so that each interlocutor correctly perceives what part of his face the other is looking at. The task just consisted in a speech game where Semantically Unpredictable Sentences (see [START_REF] Benoît | The SUS test: A method for the assessment of text-to-speech synthesis intelligibility using Semantically Unpredictable Sentences[END_REF], for description of SUS) uttered by one speaker in noisy environment have to be repeated with no error by his interlocutor. The speaker has of course to correct the repeated utterance as long as the repetition is incorrect. Mutual attention is thus essential to the success of interaction. Preliminary results (see Table 1) confirm for example that prephonatory (preparing to speak) activity is characterized by a gaze away from the face of the interlocutor. Eyes and mouth are all scrutinized when first listening to SUS whereas gaze during verification is focused on the mouth: gaze patterns are of course highly depending on cognitive demands [START_REF] Yarbus | Eye movements during perception of complex objects. Eye Movements and Vision[END_REF].

Comments

A control model for eyes direction should not only rely on a context-aware multimodal scene analysis and a basic comprehension of the user's intentions and social rules but also rely on a faithful scene synthesis. Gaze patterns should be rendered so that human partners perceive the intended multimodal deixis and mutual attention. In a preceding paper [START_REF] Raidt | Does a virtual talking face generate proper multimodal cues to draw user's attention towards interest points?[END_REF], we have shown that our ECA is able to efficiently attract users' attention towards its focus of interest. We currently investigate the impact of the eye gaze rendering on performance. Eyelids deformations as well as head movements participate to the elaboration of gaze direction: adequate prediction of these deformations according to gaze direction reinforces perception of spatial cognition.

Conclusions

This paper sketches a research framework for giving ECA the gift of situated human interaction. The landscape on eye gaze research is of course incomplete and gaze is one part of the facial actions that humans involve in face-to-face conversation. Gestural scores should be properly orchestrated so that complementary and redundant information is delivered at the right tempo to the interlocutor. Human behavior is so complex and subtle that computational models should be grounded on quantitative data (please refer for example to [START_REF] Bailly | Degrees of freedom of facial movements in face-to-face conversational speech[END_REF], for a study of facial movements involved in conversation). Interaction rules should be completed with interaction loops that take into account the necessary coupling between signals extracted by a detailed multimodal scene analysis and the comprehension of the discourse and speaker's desires and beliefs that the artificial intelligence is able to built. Part of the success and realism of the interaction is surely in the intelligent use the artificial intelligence can make of the symptoms of the comprehension of the interaction the human partners who are present in the scene offer for free.

  -to-face interaction: (a) gaming with an ECA; (b) studying human gaze patterns; (c) our ECA mounted on the Rackham mobile robot at the Space city in Toulouse -France (Clodic, Fleury et al. 2006). Copyright CNRS for (a) and (b).

Figure 2 :

 2 Figure 2: Models for observing natural scenes. Left: eye saccades of the ECA developed by Itty et al (Itti, Dhavale et al. 2003) are sequenced by points of interest computed from a video input. Right: Sun (Sun 2003) uses a multiscale segmentation to scrutinize an image by successive zoom-ins and -outs.

Figure 3 :

 3 Figure 3: An ECA exploring a visual scene. The ECA scrutinizes a real scene displayed on a transparent screen. Key frames are displayed. A black circle materializes the point of interest for each image. Top: a subject waves a blue book in front of the ECA and the module responsible for smooth pursuit controls the gaze. Bottom: a person passes behind the interlocutor and a saccade is performed to track this new object of interest.

Figure 4 :

 4 Figure 4: Comparing gaze trajectories (top: horizontal displacement; bottom vertical displacement) generated by our eye gaze control system with those recorded from subjects observing the same scene (the colored gauge is obtained by computing the variance between 5 subjects). Major differences (enlightened) are observed in vertical displacement where the control system is sometimes attracted by saturated colors of clothes of people passing in the background rather than their faces.

Figure 5 :

 5 Figure 5: Screenshot of the labeling framework for face-to-face interaction data (using the ELAN editor® www.mpi.nl/tools/elan.html). The female listener fixates either the mouth or the right eye of the male speaker when he is uttering a SUS utterance (see text).

Figure 6 :

 6 Figure 6: A 3D statistical shape model that reproduces geometric deformations of the eyelids of one subject depending on gaze direction.

Table 1 : Gaze data from speaker X when interacting with speaker Y. A turn consists in trying to repeat a SUS uttered by the partner with no error. Percentage of time spent on mouth and eyes regions is given for various actions and roles of the interlocutors.

 1

			Regions of the face of Y gazed by X
	SUS giver	Actions of X Mouth	Left eye	Right eye Other
	X	Prephonatory	48,1	0	6,9	45,0
		Speaking	91,6	0	5,1	3,3
		Listening	82,0	0	6,7	11,3
	Y	Listening	64,0	14,6	17,8	3,6
		Speaking	48,4	29,2	19,2	3,2
		Prephonatory	18,7	10,2	37,6	33,5

The Loebner Prize for artificial intelligence awards each year the computer program that delivers the most human-like responses to questions given by a panel of judges over a computer terminal.

The ability to understand that others have beliefs, desires and intentions that are different from one's own[START_REF] Baron-Cohen | Does the autistic child have a "theory of mind[END_REF][START_REF] Premack | Does the chimpanzee have a theory of mind?[END_REF]

Acknowledgments

The authors want to thank Jan Cornelis, Hichem Sahli and Werner Verhelst for their kind invitation. The technical support from Alain Arnal and Christophe Savariaux was essential. This work is financed by the GIS PEGASUS, the ELESA research federation and the Presence project of the Cluster Rhones-Alpes InfoLog.


Tristan Cazenave

Sequential Halving applied to Trees

Keywords: Monte Carlo Tree Search, Sequential Halving, SHOT, UCT, Nogo. ✦

Monte Carlo Tree Search (MCTS) is state of the art for multiple games and problems. The base algorithm currently used for Monte Carlo Tree Search is UCT. We propose an alternative Monte Carlo Tree Search algorithm: Sequential Halving applied to Trees (SHOT). It has multiple advantages over UCT: it spends less time in the tree, it uses less memory, it is parameter free, at equal time settings it beats UCT for a complex combinatorial game and it can be efficiently parallelized.

INTRODUCTION

Monte Carlo Tree Search [START_REF] Coulom | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF] has been very successful in a number of games and single agent problems [START_REF] Browne | A survey of Monte Carlo tree search methods[END_REF], [START_REF] Cazenave | Nested monte-carlo search[END_REF] such as Go [START_REF] Coulom | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF], General Game Playing [START_REF] Finnsson | Simulation-based approach to general game playing[END_REF], [START_REF] Méhat | Combining uct and nested monte carlo search for single-player general game playing[END_REF] and Morpion Solitaire [START_REF] Christopher | Nested rollout policy adaptation for monte carlo tree search[END_REF]. The standard Monte Carlo Tree Search algorithm is UCT [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF]. It uses the UCB bandit formula [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. Alternative algorithms have been designed for bandits. For example Sequential Halving [START_REF] Karnin | Almost optimal exploration in multi-armed bandits[END_REF] allocates multiple playouts to each move. It runs a few rounds and it is given in advance the number of playouts it will use. We propose to adapt Sequential Halving to Monte Carlo Tree Search and to name the resulting algorithm SHOT.

There is a number of reasons why SHOT is worth considering:

• SHOT spends less time in the tree than UCT.

• SHOT uses less memory than UCT.

• At equal time settings SHOT beats UCT for a typical combinatorial game.

• It can be parallelized efficiently.

• There is no need to tune a parameter. SHOT differs significantly from the traditional UCT-like model of MCTS, as it does not execute the usual selection-expansion-simulationbackpropagation loop. Instead it allocates a budget of playouts to each move, this is why it spends less time in the tree and can be parallelized efficiently.

• T. Cazenave is at LAMSADE, Université Paris-Dauphine, 75016

Paris, France. email: cazenave@lamsade.dauphine.fr SHOT does the opposite of usual pruning heuristics for MCTS. Progressive widening [START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF] and progressive unpruning [START_REF] Guillaume | Progressive strategies for monte-carlo tree search[END_REF] start with only the most promising moves and then extend the number of moves under consideration at a node when the number of playouts increase. On the contrary SHOT starts with all the possible moves and gradually decreases the number of moves under consideration. SHOT does not use domain dependent knowledge to prune the moves.

SHOT is parameter free as is Nested Monte Carlo Search (NMCS) [START_REF] Cazenave | Nested monte-carlo search[END_REF]. However SHOT develops a tree near the root and performs simple playouts outside of this tree whereas NMCS does search all along the game with nested playouts, also searching near the end of the game.

SHOT can be applied to single-player, two-player and multi-player games. In this paper it is applied to a two-player game.

The second section is about Sequential Halving, the third section deals with SHOT, the fourth section details experiments, the last section concludes.

SEQUENTIAL HALVING

Sequential Halving [START_REF] Karnin | Almost optimal exploration in multi-armed bandits[END_REF] is an algorithm that is based on sequential elimination of moves. The algorithm proceeds in rounds. In each round the remaining moves are sampled uniformly. The number of playouts is fixed at the start of the algorithm. Parts of the budget of playouts are allocated independently to moves during the few sequential rounds. A round consists of playing a fixed number of playouts for each remaining move. After each round the number of moves under consideration is divided by two. Only the best half of the moves with the largest empirical averages are kept for the next round. When there is only one move left, the algorithm stops and sends back the move.

The number of playouts allocated to a move in each round is given by the following formula: budget |S|×⌈log 2 (|possibleM oves|)⌉ where budget is the total number of playouts that the algorithm will use, S is the set of remaining moves and possibleM oves is the set of all possible moves. Figure 1 gives an example of Sequential Halving applied to a position with four moves and a budget of sixty-four playouts. At the beginning of the algorithm, all four moves have zero wins and zero playouts. Then the algorithm decides to try each move eight times since there are four possible moves and the budget is sixty-four ( 64 4×⌈log 2 (4)⌉ = 8). So after the first round the four possible moves have empirical averages of 2/8, 8/8, 6/8 and 7/8. The two best moves (i.e. the moves that have the 8/8 and 7/8 empirical averages) are selected for the next round. Then the algorithm allocates 64 2×⌈log 2 (4)⌉ = 16 playouts to each of these two remaining moves for the second round. After the second round, the resulting empirical averages are 18/24 and 20/24 so the best move that has the 20/24 empirical average is selected and as it is the only remaining move it is returned as the best move by the algorithm.

Sequential Halving has interesting theoretical properties. Instead of minimizing the regret as in UCB [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], Sequential Halving maximizes the probability of choosing the best arm having the maximal expected reward. In [START_REF] Karnin | Almost optimal exploration in multi-armed bandits[END_REF], they prove a bound on the probability to erroneously eliminate the best arm. If n is the number of arms, the multiplicative gap from the lower bound on the number of required arm pulls to reach a given probability is in log log n while in previous algorithms the gap was in log n. The exact theorem is: for succeeding with probability at least 1δ, the algorithm needs a total of at most

T = O(H 2 × log(n) × log( log(n) δ )) arm pulls. Where H 2 = max i =1 ( i ∆ 2 i
) and ∆ i = p 1p i and p 1 ≥ p 2 ≥ ... ≥ p n are the expected rewards of the arms.

These results were established using previous work on complexity measure [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF].

Sequential Halving scales better than other algorithms when the number of possible moves grows [START_REF] Karnin | Almost optimal exploration in multi-armed bandits[END_REF]. The paper on Sequential Halving also addresses the fixed confidence setting in which the number of arm pulls is not fixed but the error probability is fixed.

Sequential Halving is given in algorithm 1.

6

SEQUENTIAL HALVING APPLIED TO TREES

Sequential Halving is adapted when there is a fixed budget. When we use Sequential Halving in combination with tree search, we may come back to an already visited node with an increased budget. The policy that SHOT uses in this case is to consider the already allocated budget and the new budget as a whole. The overall budget is distributed as if it was given at first. The information on the node such as the number of playouts and the number of wins for each move are stored in the transposition table entry. This information is used to allocate the new budget so as not to give to a move more playouts than what it would have been given if the allocated budget and the new budget were considered as a whole. So the algorithm looks in the transposition table entry at the number of playouts that have already been given to the move and gives it the difference between the new budget for the move and the number of playouts already given.

An example of the behaviour of SHOT coming back to a previously explored node is given in figure 2. During the previous exploration of the node the four possible moves have been explored using Sequential Halving with a budget of sixtyfour playouts. It resulted in empirical averages of 2/8, 18/24, 6/8 and 20/24 for the four possible moves. Now, SHOT comes back to the node with a budget of one hundred and twenty-eight playouts. It considers the overall budget as the sum of the budget previously spent at the node and of the budget still to be spent. The overall budget is 64 + 128 = 192. It then calculates the budget to be allocated to each move in the first round using the formula t.budgetN ode+budget |S|×⌈log 2 (|possibleM oves|)⌉ where t.budgetNode is the budget already spent at the node during previous calls (64), budget is the budget to spend during the current call (128), and S is the set of remaining moves which is the set of all possible moves since it is the first round. So each possible move is allocated 64+128 4×⌈log 2 (4)⌉ = 24 playouts. However each move has already used some playouts the last times the node has been visited. So SHOT only gives each move the difference between the number of allocated playouts and the already used playouts. It gives sixteen playouts to the first move that has 2/8 and to the third move that has 6/8, and no playout to the other two moves that already have used twenty- four playouts. After this first round we have the four moves that each have 24 playouts and empirical averages of 16/24, 18/24, 21/24 and 20/24. The best two moves are selected for the second round. This time they are allocated 64+128 2×⌈log 2 (4)⌉ = 48 more playouts using the same formula as for the first round. After the playouts have been played it results in empirical averages of 58/72 and 60/72. The best move is selected and the algorithm sends it back.

Due to the multiple visits of a node it happens that the budget allocated to a node is not completely used. In this case it is saved and reallocated to the best move at the root during the last round. It helps verifying the best move really has a better empirical average than the second best move. However other reallocation strategies can be thought of.

In order to avoid waste of memory, a new node is inserted in the transposition table only if it contains two playouts or more. It means that SHOT will create much less nodes than the number of playouts it will play. A memory saving strategy that consists of creating a node only when it has a given number of playouts can also be used for UCT so as to save memory [START_REF] Chou | Revisiting Monte-Carlo tree search on a normal form game: Nogo[END_REF].

In order to avoid spending too much time sorting the moves, moves are sorted only if the overall budget is greater than the number of possible moves. When this is not the case only moves that have zero playouts are tried.

SHOT is given in algorithm 2. The variable budget is the maximum number of playouts allowed in the function, budgetU sed is set to zero at each call of the function and counts the number of playouts really played in the function. Similarly playouts and wins count the number of playouts and the number of wins. They are initialized to zero at each call of the function (the variables u, p and w are set to zero and passed by reference). t.budgetN ode is the number of playouts already used at the node during previous calls. b is the total budget that each move in S should use including the previous rounds and the current round. b1 is the number of playouts that are allocated to a move m in S for the current round given b, the playouts already allocated to the move in previous rounds and the budget left for the node.

SHOT allocates possibly large numbers of playouts in parallel to the possible moves. It can therefore be efficiently parallelized since it decomposes in independent parts that each take a significant amount of time.

21

EXPERIMENTAL RESULTS

SHOT and UCT have been implemented for Nogo [START_REF] Chou | Revisiting Monte-Carlo tree search on a normal form game: Nogo[END_REF]. The resulting program is named Noname. Nogo is a misere version of the game of Go. The first player to capture a string has lost. Suicide is forbidden. The playouts are completely random.

A transposition table keeps nodes in memory. For each index of the transposition table there is a list of entries.

For all of the experiments 500 games are played, 250 with white and 250 with black.

The machine used for the experiments has an Intel 2.83 Ghz CPU, 4 GB of RAM and runs on Linux.

Table 1 gives the results of UCT with various constants against SHOT with the same number of playouts as UCT. For each board size and for all the remaining experiments the constants that gave the best results are used: 0.4 for 9 × 9 and 0.032 for 19 × 19.

Table 2 gives the times used by UCT and SHOT to perform a given number of playouts starting from an empty board. We can see that even for very low numbers of playouts SHOT takes less time than UCT. When we reach 10,000 playouts SHOT takes half the time of UCT, and approximately three times less time for 500,000 playouts. There is no time for 19×19 UCT and 500,000 playouts because it took a large time due to the use of a lot of memory. UCT uses the same number of nodes as the number of playouts. SHOT uses less memory than UCT since it does not create a node for each playout. Table 3 gives the number of nodes used by SHOT for different number of playouts and different sizes.

Table 4 gives the percentage of wins for SHOT and UCT when they play against themselves with twice the number of playouts. Both SHOT and UCT scale well with more playouts.

Table 5 gives the percentage of wins for SHOT over UCT. The number of playouts of SHOT is fixed and UCT takes at each move the same amount of time as SHOT took at the previous move. We can see that SHOT outperforms UCT at equal time settings.

DISCUSSION

In [START_REF] Chou | Revisiting Monte-Carlo tree search on a normal form game: Nogo[END_REF] a modification of the UCT algorithm consisting of creating a node in memory if it has been simulated at least five times is shown to reduce memory consumption by a factor four while increasing the winning rate to 77 % for Nogo. In comparison, the SHOT algorithm reduces the memory consumption by a factor twenty-five for 9 × 9 Nogo (see table 3) while increasing the winning rate to 66.8 %. For 19 × 19 Nogo, the memory consumption is reduced by a factor forty while increasing the winning rate to 100.0 %. It is also possible to add slow node creation to SHOT reducing even more its memory consumption.

We have used a transposition table both in the UCT and in the SHOT algorithms. So both algorithms deal in fact with Directed Acyclic Graphs and they both have inconsistent child visit counts.

It is possible that SHOT will work better for games that are Monte Carlo perfect, i.e. increasing numbers of playouts give increasingly accurate results, than for games that are Monte Carlo resistant, i.e. increasing numbers of playouts can actually give worse results. UCT can handle such cases as the tree boundary grows to outweigh the inaccurate playout estimates and revise the estimated value of moves near the root. SHOT eliminates moves from the search so this revision of previous move estimates does not occur, hence it is possible that SHOT will fail to handle games that are Monte Carlo resistant where UCT can.

CONCLUSION

In conclusion, SHOT is a viable alternative to UCT. It is parameter free. It scales well since the results are better for 19 × 19 Nogo than for 9 × 9 Nogo and that increased number of playouts increase the level of play. It uses less memory than standard UCT and beats standard UCT at Nogo for equal time settings.

Future works include parallelization on a multicore machine and on a cluster, applying it to other games and problems and adapting the various improvements of Monte Carlo Tree Search to SHOT.

TABLE 2

 2 Times of SHOT versus time of UCT for Nogo.

TABLE 3

 3 Number of nodes used by SHOT.

TABLE 4

 4 Scalability of SHOT versus scalability of UCT for Nogo.

	Playouts SHOT SHOT vs UCT SHOT vs UCT
		9 × 9	19 × 19
	1,000	75.6 %	83.8 %
	10,000	75.8 %	90.0 %
	100,000	66.8 %	100.0 %

TABLE 5

 5 SHOT versus UCT with same thinking times.

ACKNOWLEDGMENT

I thank Abdallah Saffidine pointed me to the Sequential Halving paper and the anonymous reviewers for helping me improve this paper.