X J Chen

J S Hwang

G Perillat-Merceroz

S Landis

B Martin

D Le

Si Dang

J Eymery

C Durand

Wafer-scale selective area growth of GaN hexagonal prismatic nanostructures on c-sapphire substrate

Keywords: Nanostructures A2, Selective epitaxy A3, Metalorganic vapor phase epitaxy B1, Nitrides

Selective area growth of GaN nanostructures has been performed on full 2" c-sapphire substrates using Si 3 N 4 mask patterned by nanoimprint lithography (array of 400 nm diameter circular holes). A new process has been developed to improve the homogeneity of the nucleation selectivity of c-oriented hexagonal prismatic nanostructures at high temperature (1040 °C). It consists of an initial GaN nucleation step at 950 °C followed by ammonia annealing before high temperature growth. Structural analyses show that GaN nanostructures are grown in epitaxy with c-sapphire with lateral overgrowths on the mask. Strain and dislocations are observed at the interface due to the large GaN/sapphire lattice mismatch in contrast with the high quality of the relaxed crystals in the lateral overgrowth area. A cathodoluminescence study as a function of the GaN nanostructure size confirms these observations: the lateral overgrowth of GaN nanostructures has a low defect density and exhibits a stronger near band edge (NBE) emission than the crystal in direct epitaxy with sapphire. The shift of the NBE positions versus nanostructure size can be mainly attributed to a combination of compressive strain and silicon doping coming from surface mask diffusion.

Introduction

The group-III nitride semiconductor nanostructures, such as quantum wells (QWs), quantum dots (QDs) and more recently nanowires (NWs) have attracted considerable interests, especially for photonic applications as light emitting diodes and lasers [1,2,3,4]. Significant efforts have been made to control the growth of GaN compound nanostructures in terms of size and density to get homogeneous structural and optical properties. Selective area growth (SAG) using patterned masks have been especially demonstrated to be an effective way to localize the growth of nitride nanostructures. This method is essentially used in metal organic vapor phase epitaxy (MOVPE) with patterned dielectric mask (SiO 2 or Si 3 N 4 ) to control the position and the size of GaN nanostructures as stripes [5], pyramids [5] and rods [6], and more recently in molecular beam epitaxy (MBE) using Ti patterned masks [7]. In MOVPE, SAG experiments are mostly reported on GaN layer template grown on c-sapphire substrate and usually result in pyramid-shaped nanostructures [8][9][10][11][12]. However, prismatic-shaped GaN structures have been observed for stripes and hexagonal nanostructures in SAG on c-sapphire [13,14]. Indeed, nitridated sapphire surface favours the growth of N-polar GaN crystal [15].

Such polarity is particularly interesting to promote the growth of hexagonal GaN wires [16,17]. This motivates the SAG of GaN nanostructures directly on c-sapphire that gives the opportunity to grow well organized c-oriented hexagonal GaN wires [18]. Nevertheless, the control of homogeneity of the nucleation selectivity of SAG GaN nanostructures on csapphire substrate remains an issue to be addressed. In addition, some more fundamental issues like the structural and optical properties of SAG nanostructures grown on sapphire have to be carefully studied especially due to the large lattice mismatch between sapphire and GaN.

In this work, we present a new method based on a temperature dependent two-step growth process to achieve the homogeneity of the nucleation selectivity growth of c-oriented GaN hexagonal prismatic-shaped nanostructures directly on patterned c-sapphire substrates.

The patterning is obtained by nanoimprint lithography (NIL), which exhibits relevant advantages to other nanoscale patterning methods (for example electron beam lithography) with no charge effect coming from insulating materials and full wafer surface patterning at low cost and time-consumption. The first part of the paper will detail how the GaN nanostructure shape and the SAG nucleation homogeneity are related to the growth temperature, then it will be shown that hexagonal prismatic-shaped GaN SAG nanostructures can be managed with a high homogeneity by a two-step temperature growth process combined with an annealing procedure. Finally, thanks to the use of sapphire substrate without any intermediate GaN template layer, the optical properties of single GaN hexagonal nanostructures will be studied with respect to the structural properties to understand the influence of the nanostructure size.

Experimental methods

The patterning of 2" c-sapphire substrates was carried out by NIL using a Si mold with a uniform square array of circular pillars. Fig. 1 shows the three main steps to prepare the patterned substrates. Firstly (see Fig. 1(a)), a 5 nm-thick Si 3 N 4 dielectric mask was deposited by plasma enhanced chemical vapour deposition at 300 °C. Hexamethyldisilazane (HMDS) was then spin coated to promote adhesion of the imprint resist. Secondly, a 225 nm-thick resist (NEB22 from Sumitomo) was spread and soft-baked at 110 °C for 2 minutes. The imprint process was done at 110 °C using a contact-force of 10 kN in a EVG  520HE nanoimprint equipment [19]. The residual resist layer at the bottom of the holes was removed by a short oxygen plasma treatment to reach the Si 3 N 4 surface (see Fig. 1(b)). Thirdly, the Si 3 N 4 mask was etched by using SF6 plasma followed by resist stripping to obtain a uniform patterning on the whole 2" wafers with a regular array of circular holes of 400 nm in diameter spaced by 1.1 µm (see the Fig. 1(c) and the AFM image in Fig. 1(d)). The choice of the circular shape of the openings is motivated by simplicity arguments in order to avoid taking into account the anisotropy of the pattern shape and its influence on the growth in terms of facet evolution.

The patterned substrates were then transferred into a MOVPE 3 x 2" close-coupled showerhead reactor (Aixtron CCS  ) to carry out the growth at high pressure (800 mbar) using a flow of 8000 sccm of N 2 as carrier gas. Before growth, an in-situ pre-treatment of the patterned sapphires was done at high temperature (~ 1200 °C) using two steps: first a bake under H2 atmosphere during 20 min to clean the surface followed by a surface nitridation using ammonia flow (200 sccm) for 400 s. It has been shown that this preparation leads to the formation of a spontaneous thin AlN layer [16] driving the growth of N-polar GaN crystals [15,17]. For GaN deposition, trimethylgallium (TMGa) and ammonia (NH 3 ) were used as precursors for the III and V materials. The V/III molar ratio was set to 16 corresponding to an injection flux of 135 µmol/min and 2.230 mmol/min for TMGa and NH 3 and the growth temperature has been set between 900 and 1040 °C. The choice of these growth conditions allows avoiding the lateral growth as explained in Ref. 16.

The morphology of the as-grown samples was characterized by field emission scanning electron microscopy (FE-SEM). The structural properties were analyzed by X-ray diffraction (XRD) using the Co Kα (λ ~ 0.17902 nm) radiation and by 400 keV transmission electron microscopy (TEM) equipped with selected area electron diffraction (SAED). The optical properties of single GaN nanostructures were measured by cathodoluminescence spectroscopy (CL) at 5 K using 30 keV electron beam high voltage with about 1 nA current.

Results and Discussion

Growth study: effect of temperature

Single-step temperature growth

Selective growths on patterned sapphires were performed at 900, 950, 1000 and 1040 °C and Fig. 2(a)-(d) shows the corresponding 45°-tilted SEM images. At 900 °C (see Fig. 2(a)), GaN crystals are not regularly faceted and are strongly disoriented with respect to the c-sapphire substrate. By increasing the temperature to 950 °C (see Fig. 2(b)), the orientation along the c-axis is improved, but the shape is still irregular. From 1000 to 1040 °C (see Fig. 2(c)-(d)), we observe more regular hexagonal shapes composed of flat <0 0 0 1> horizontal planes on top (i.e. prisms) and six 0 0 1 1 vertical side facets. Despite the significant improvement of the crystalline quality and orientation with increasing growth temperature, the homogeneity of the nucleation in the mask openings is strongly degraded since only a few openings are filled for 1040 °C growth. Actually, the percentage of opening fillings noticeably decreases from nearly 85 % at 900 -950 °C, to 60 % at 1000 °C and to about 20 % at 1040 °C. The SAG of GaN nanostructures on patterned sapphire substrates is therefore highly sensitive to the growth temperature in terms of crystal shape and homogeneity of nucleation selectivity: the formation of regular hexagonal nanostructures is obtained at high temperature with poor selectivity efficiency, while the opposite trends are observed for lower temperatures.

Two-step temperature growth

To combine high homogeneity of nucleation selectivity and high crystal quality of GaN nanostructures grown on sapphire, a two-step temperature process has been developed. The initial nucleation step is first made at 950 °C for 200 s with TMGa and ammonia sources to get a high homogeneity of the GaN nucleation seeds. The TMGa source is then stopped and the temperature is ramped from 950 °C to 1040 °C in 200 s under ammonia flow. Finally, the TMGa supply is restarted for 350 s at higher temperature (1040 °C) to grow high quality GaN crystals. The other growth parameters (pressure, flows of carrier gas and precursors) remain the same as written in Sect. 2. Fig. 3(a)-(c) shows the 45°-tilted SEM measurements after each step of the growth. The evolution of GaN crystal shape is schematically illustrated in Fig. 3(d).

As observed in Fig. 3(a), GaN growths at 950 °C result in c-oriented crystals with mostly an irregular truncated pyramidal shape (see the inset) with a filling percentage of mask openings around 85 %. The average diameter of the GaN nanostructures is about 500 nm that means there is already a lateral overgrowth outside the 400 nm openings. The temperature ramping under ammonia changes the crystal shape from irregular truncated pyramids to wellshaped hexagons as shown in the inset of Fig. 3(b) while keeping the homogeneity of nucleation selectivity. This anisotropic shape evolution of GaN nanostructures may be explained first by a mass transport driven by Ga diffusion to reach the energetically stable facets, i.e. the (1 1 0 0) planes at high temperature for growth on pre-nitridated sapphire substrates, which gives rise to the facets of the hexagons [20,21]. In addition, the isotropic size reduction of the hexagonal nanostructures compared to the initial truncated pyramids in both lateral and vertical directions is also observed and could be explained by a decomposition of GaN at high temperature induced by H 2 etching coming from the NH 3 decomposition. The duration of the step is thus critical to avoid the complete vanishing of GaN seeds. Notice, the exact value of this duration should be optimized as a function of MOCVD setup. In the third step, the restart of the GaN growth maintains the previous hexagonal shape (see Fig. 3(c) and the inset). The typical diameter of hexagonal nanostructures after a supplementary growth duration of 350 s is about 500-700 nm in the lateral dimension with a 0.6-1 aspect ratio. The increase in size distribution of the GaN nanostructures with the growth time is probably due to the uncontrolled lateral overgrowth on the mask and to the initial size distribution of the nucleation seeds.

To sum up the multi-step temperature growth approach, the first step allows to get high homogeneity of nucleation selectivity of the seeds, the annealing step at ramped temperature induces the formation of hexagonal islands with uniform size (400 ± 20 nm) and the third step leads to hexagonal prismatic nanostructure growth.

Discussion of growth mechanism 3.2.1. Shape evolution versus growth temperature

In the last decade, the relationship between the crystal shape of GaN nanostructures and the growth parameters, especially the temperature has been mainly investigated by using the Wulff"s plot (γ-plot) which deals with the anisotropy of the surface energy. It has been found in molecular beam epitaxy SAG that the equilibrium geometry of GaN nanostructures may change from pyramid to hexagon by decreasing the growth temperature due to the facet energy anisotropy [22]. In the case of MOVPE SAG process, Tanaka et al. [13] have reported the modification of SAG stripe morphologies from trapezoidal to rectangular cross-section with an increase of growth temperature from 850 to 1040 °C on pre-nitridated sapphire substrates. The kinetic influence in terms of kinetic Wulff"s plot (ν-plot) must also be taken into account in a real MOVPE growth condition [23,24]. For instance, it has been found that the GaN crystal polarity strongly influences the growth rate of different crystal facets at high temperature leading to hexagonal N-polar wires [17]. In conclusion, the observed shape evolution of the GaN nanostructures from pyramidal shape at low temperature to hexagonal prismatic shape at high temperature can be understood by a combination of the influences of temperature-related facet energy anisotropy and kinetics. Further experiments to quantify this behaviour in details are under way.

Selectivity versus growth temperature

The MOVPE growth rate is in general determined by the competition between deposition from the vapour phase transport and desorption phenomena (evaporation, H 2 etching...). In our growth temperature range (above 950 °C), the transport of species in the vapour phase can be considered as constant (transport regime), whereas the desorption rate increases with the growth temperature (desorption regime). Additionally, the desorption of N atoms should be higher than in the standard two-dimensional GaN growths because of the low V/III ratio used to avoid the lateral growth, when a high ammonia partial pressure is generally required above 1040 °C to limit N-desorption [25]. In the case of SAG, the effective diffusion length of the reactive species on the mask (called the migration length) is a third effect that contributes significantly to the growth rate [26,27,28]. The migration length is usually strongly dependent on the growth temperature [29,30]. At high temperature, ammonia molecules are immediately decomposed to adducts in the gas phase [25], and therefore, mainly Ga species are involved in the mask migration process. By increasing temperature, the migration length of the Ga species is decreased due to the significant reduction of the residence time of Ga species on the mask, which reduces the amount of supplied materials for incorporation [30].

Thus, the combination of deposition, desorption and migration contributions leads to a reduction of the nanostructure growth rate when the growth temperature is increased in the 900-1040 °C range. Furthermore, we can suspect that the nucleation of GaN crystals does not occur exactly at the same time in all openings due to the different surface states in terms of chemistry and structure: residues of resist, different diffusion barriers, surface defects, efficiency of nitridation (with respect to polarity control [17]). The seeds, which appear first, will serve as "sink" to collect the contiguous growth species. It then creates an adatom concentration gradient on the nearby surface that may lead to a diffusion network [31]. For 1040 °C growth, less material is provided compared to the growths at lower temperature.

Therefore, the quantity of provided material is not large enough to compensate the desorption effect in the mask openings, except for some sites benefiting from the "sink" effect that may locally increase the growth rate. It finally gives a poor homogeneity of nucleation selectivity of SAG growth at high temperature. In the case of growths at lower temperature (900 and 950 °C), although the "sink" effect still exists, the growth rate is high enough to fill most of the mask openings, which leads to a higher homogeneity of nucleation selectivity.

For two-step temperature growth, the GaN seeds nucleate in most of mask holes due to low temperature process (950 °C) giving a high homogeneity of nucleation selectivity. After the annealing step under ammonia, the homogeneity of nucleation selectivity is maintained with a reduction of size distribution of nanostructure growth. Thanks to the high homogeneity of nucleation selectivity and size uniformity after the ammonia annealing, the "sink" effect corresponding to a local gradient of incoming species is strongly reduced at high temperature (1040 °C), and a SAG of GaN hexagonal prisms with high homogeneity of nucleation selectivity can be obtained.

Structural and optical characterizations of GaN nanostructures

Crystalline quality of nanostructures

Standard XRD measurements in the symmetric θ-2θ geometry have been performed to investigate the crystallographic phases of the as-grown nanostructures obtained by the twostep growth process. As shown in Fig. 4, three Bragg peaks can be indexed with the (0 0 6) α-Al 2 O 3 reflection (R 3 c, c =1.2991 nm), the (0 0 2) and the (0 0 4) wurtzite GaN reflections (P6 3 mc, c = 0.5188 nm). It indicates c-axis oriented growth of nanostructures on c-sapphire with no other secondary phases. To completely characterize the epitaxial relationships and the local structural properties, TEM measurements were performed on as-grown samples prepared by standard polishing and ion-milling processes. Fig. 5(a) and (b) depicts crosssection dark-field TEM images taken in a two-beam condition with g-vectors along <0 0 0 2> and <1 1 0 0> to image screw and edge dislocations having <0 0 0 2> and <1 1 2 0 > Burgers vectors. In the TEM images, a lateral overgrowth of the nanostructures outside the mask openings (see the limits indicated by the two black arrows in Fig. 5(a)) can be observed since the 550 nm nanostructure size is larger than the 400 nm mask opening. In the central part, we observe fringes in TEM images (Fig. 5(a)) coming from the large GaN/sapphire lattice mismatch and also misfit dislocations at the interface due to the strain relaxation. Threading dislocations (TD) are rarely observed: only two TDs with screw type are for instance visible in Fig. 5(a) (see white arrows) and no edge-type TD is observed in Fig. 5(b). On the contrary, in the lateral overgrowth part, a better crystal quality is observed with a low strain (absence of fringe) and no observed dislocations. Only a few stacking faults have been seen in Fig. 5(b) indicated by the white dashed triangular. It has been recently published that GaN nanorods grown on c-sapphire can present a high TD density [18]. These observations are attributed to the use of a thicker dioxide mask (100 nm) [18]. This evidences that a very thin mask (5 nm) significantly improve the crystalline quality of the SAG GaN nanostructure on sapphire. SAED pattern taken in the central interface area with the beam parallel to the <1 1 2 0> direction of the GaN crystal is given in Fig. 5(c). The pattern indexation (black and white arrows denoting GaN and sapphire respectively) confirms the usual in-plane epitaxial relationship between GaN and sapphire ([1 1 0 0] GaN // [1 1 2 0] Sapp. ) with a measured lattice mismatch of about 16.0 % along the [1 0 1 0] direction, in agreement with the 16.09 % bulk value.

Optical studies of single nanostructures

Cathodoluminescence measurements in area-scanning mode were carried out at 5 K on single nanostructures to study the optical properties. Fig. 6 shows the CL spectra taken in a top view of single nanostructures (grown with the two-step temperature method) having 250, 500 and 1300 nm diameters and heights. The spectra are normalized to the intensity maximum. Fig. 7 gives the SEM image and the corresponding CL mappings measured at 3.46 and 2.26 eV in the top and cross-section views. In these images, darker area corresponds to larger emission intensity.

CL spectra exhibit two main contributions: the near band edge (NBE) emission of GaN in the UV region (~3.4 eV) and the yellow band (YB) emission at ~2.2 eV in the visible wavelength range, which is generally assigned to crystal defects like Ga vacancies and O complexes [32]. The relative intensity ratio between YB and NBE contributions strongly depends on the diameter of single nanostructures: it increases with the decrease of the nanostructure size as clearly observed in Fig. 6(a). To understand this behaviour, CL mappings were performed to localize the spatial emission of the NBE and YB wavelengths in the nanostructures. Fig. 7(a) shows the top view SEM image of the nanostructure arrays. The corresponding CL mapping images of the NBE and YB emissions at 3.46 and 2.26 eV are shown in Fig. 7(b) and (c) respectively. We can deduce from these measurements that the NBE emission mostly comes from the border part of the nanostructures, especially for the ones with size larger than 400 nm. On the contrary, the luminescence of the YB emission is more or less uniformly distributed whatever the nanostructure size. This observation is confirmed in Fig. 7(e) and (f) by CL mappings at 3.46 and 2.26 eV on 550 nm ion-milled sample in cross-section (the dashed line indicates the contour of the single nanostructure). This is consistent with the fact that the NBE emission is more sensitive to carrier diffusion than the YB emission, and the side part of the nanostructures is of much higher structural quality than the central part (see TEM results above). The size dependence of the optical properties can be also attributed to the fact that crystals with larger size have larger volume ratio between the side and the central part of the nanostructures leading to much stronger NBE emission. This result is in favour of the use of small diameter openings for optoelectronic applications.

In addition, we observe a variation of the NBE peak position of the nanostructures with different diameters as shown in Fig. 6(b). The peak shift can be assigned to two opposite effects: a blueshift due to compressive strain induced by the lattice mismatch [33] and a redshift induced by silicon doping [34]. Such unintentional Si doping, which is mostly located at the bottom part of the nanostructures, may come from the Si 3 N 4 dielectric mask through a surface diffusion process as already reported in SAG pyramids [35]. Depending on the concentration, Si doping may induce a gradual redshift up to ~40 meV due to band gap renormalization [34,35]. For nanostructures with diameter equal to 1300 nm, the NBE emission is principally related to the strain-relaxed lateral overgrowth. Thus, the NBE peak position located at 3.46 eV corresponds to the value of the fully relaxed GaN 2D layers at 5 K [36]. For nanostructures with a diameter close to 500 nm, the NBE emission is mostly attributed to the strain relaxed lateral overgrowth on the mask and the NBE redshift of 35 meV can be mainly assigned to the Si incorporation from the mask surface diffusion. For nanostructures equal to 250 nm, the NBE emission comes from the crystals grown in direct epitaxy with the sapphire since the nanostructures size is smaller than the mask openings.

Thus, the compressive stain must be also taken into account in addition to the Si incorporation effect. The 28 meV blueshift of the NBE peak position compared to that of the nanostructure with 500 nm size can be assigned to this compressive strain. Moreover, the peak profiles of the NBE emission for nanostructures with a diameter of 500 and 250 nm are consistent with the Si doping assumption: The shape of the NBE emission is typical of Si-doped GaN, featuring a sharp cut-off at high energy and a low energy tail [34,37]. From the observed FWHM of 60 meV, the doping level can be estimated to 10 19 /cm 3 [38].

Conclusions

In summary, a wafer-scale and effective SAG of GaN nanostructures on patterned csapphire substrate using NIL has been demonstrated. The temperature influence on the nanostructure shape has been studied for a single-step temperature growth: for temperature smaller than 1000 °C, a pyramidal shape is observed whereas a prismatic one is favored at higher temperature. In parallel, the SAG homogeneity of nucleation selectivity is significantly degraded at high temperature (> 1000 °C) due to a combination of several temperaturedependent effects, such as the desorption, the precursors migration length on the mask and the "sink" effect due to the non-uniform GaN seed nucleation. Based on these results, SAG of hexagonal prismatic GaN nanostructures with high homogeneity of nucleation selectivity has been achieved using a two-step temperature process consisting of a low temperature nucleation at 950 °C followed by an ammonia annealing and a further growth at high temperature (1040 °C). Structural characterizations of GaN nanostructures show (i) a central zone in direct epitaxy with c-sapphire with a relatively poor crystal quality exhibiting misfit and threading dislocations and (ii) an overgrown area on the Si 3 N 4 mask showing good crystalline quality. The CL mappings depict a relatively larger intensity of NBE emission from the border part of the nanostructures (i.e. overgrown on Si 3 N 4 ) in agreement with a better crystalline. Consequently, it results in a decrease of the YB/NBE intensity ratio with an increase of the nanostructure size. Finally, the NBE peak shift of GaN prisms as a function of size is attributed both to the compressive strain and to the silicon incorporation through surface diffusion from the Si 3 N 4 mask.

Figures

  Figures

Fig. 1

 1 Fig. 1. (a)-(c) Schematic of the nanoimprint patterning process on c-sapphire substrate. (d)

  Fig. 1. (a)-(c) Schematic of the nanoimprint patterning process on c-sapphire substrate. (d)

Fig. 2 . 20 Fig. 3 . 21 Fig. 4 .

 2203214 Fig. 2. 45º-tilted SEM images of the self-assembled growth (SAG) for a single-step

Fig. 5 .

 5 Fig. 5. (a) and (b) Cross-section dark field TEM images of 500 nm GaN hexagonal

Fig. 6 .

 6 Fig. 6. (a) Normalized cathodoluminescence spectra at 5 K for single GaN nanostructures

Fig. 7 .

 7 Fig. 7. (a) Top view SEM image of an array of GaN nanostructures grown by the two-step

Acknowledgments

The authors thank J. Dussaud and M. Lafossas for technical support, F. Levy and P. Gilet from LETI/DOPT for patterned sapphire substrates. G.P.M acknowledges P.-H. Jouneau and G. Feuillet for scientific support and X.J.C. thanks for the financial support of the foundation « Nanosciences aux limites de la Nanoélectronique ». The work was partly funded by the French ANR Bonafo (ANR-08-Nano-031-01) and Sincrone (ANR-09-MAPR-0011-03).


Guillaume J Laurent

Anne Delettre

Nadine Le Fort-Piat

A New Aerodynamic Traction Principle for Handling Products on an Air Cushion

Keywords:

This paper introduces a new aerodynamic traction principle for handling delicate and clean products, such as silicon wafers, glass sheets or flat foodstuff. The product is carried on a thin air cushion and transported along the system by induced air flows. This induced air flow is the indirect effect of strong vertical air-jets that pull the surrounding fluid. The paper provides a qualitative explanation of the operating principles and a description of the experimental device. Very first experimental results with active control are presented. The maximum velocity and acceleration that can be obtained for the considered device geometry meet the requirements for industrial applications.

I. INTRODUCTION

Many industries require contactless transport and positioning of delicate or clean objects such as silicon wafers, glass sheets, solar cell or flat foodstuffs. The handling of delicate, freshly painted, hot, sensitive or micron-sized structured components is feasible because mechanical contact is avoided. Contamination from and of the endeffector can be totally avoided. This can be important in food handling or in semiconductor production processes. Furthermore, dry friction forces are canceled, which enables accurate positioning or high velocity motions.

In order to avoid contact between feeding devices and work pieces, many handling approaches have been proposed. These methods typically employ magnetic, electrostatic, near-field and aerodynamic levitation [START_REF] Vandaele | Non-contact handling in microassembly: Acoustical levitation[END_REF]. Both magnetic and electric levitation are restricted to conductive materials and the lifting force depends on material properties. Pneumatic levitation approaches use air flow to apply a force to a work piece. Because air flow is magnetic free and generates little heat, pneumatic approaches can be applied to any material: insulator or conductor, magnetic or non-magnetic, rigid or non-rigid.

Researchers have experimented with a variety of air-jet techniques to design contactless manipulators. Aerodynamic levitation uses a flow of gas to apply a lift force. Two different approaches can be considered: air cushion or Bernoulli levitation. In Bernoulli levitation, the sample is held below the end-effector of the manipulator which consists in a cup-shaped air nozzle [START_REF] Waltham | Bernoulli levitation[END_REF]. Bernoulli levitation has been use in practical applications to "pick-and-place" wafers [START_REF] Li | Analysis of vortex levitation[END_REF] and flat soft foodstuffs [START_REF] Davis | An end effector based on the bernoulli principle for handling sliced fruit and vegetables[END_REF].

In air cushion levitation, the sample is held on a plate which is drilled by many small holes. Pressurized air flows upwards through these holes and creates an air cushion that counterbalances the weight of the component. This is the principle of popular air-hockey tables. Two additional means have been proposed to move the object: suction and tilted air jets.

Luntz and Moon [START_REF] Luntz | Distributed manipulation with passive air flow[END_REF], [START_REF] Moon | Distributed manipulation of flat objects with two airflow sinks[END_REF], [START_REF] Varsos | Superposition methods for distributed manipulation using quadratic potential force fields[END_REF], [START_REF] Varsos | Generation of quadratic potential force fields from flow fields for distributed manipulation[END_REF] use an air-hockey table in addition to a few flow sinks (suction points) above the table. The sinks create a stable flow pattern towards them. This device is a sensorless positioning surface able to move any rectangular object to a predictable orientation and position. Ku et al. [START_REF] Ku | Distributed control system for an active surface device[END_REF] developed the same idea but they used closed-loop control to move the object from one sink to another. The device is a 4 mm × 4 mm array of 100 capillary glass tubes. Each tube is equipped with a pressure sensor and a two-position valve which provides positive or negative pressures. The typical velocity of the object is 8 mm•s -1 .

Many devices use arrays of tilted air-jets to produce a traction force in addition to the air cushion. The geometry of the device is designed to get stable transport system without closed-loop control, for example we can mention wafer and glass transportation systems [START_REF] Babinski | Transport system for semiconductor wafer multiprocessing station system[END_REF], [START_REF] Hoetzle | Glass transportation system[END_REF], [START_REF] Paivanas | Wafer air film transportation system[END_REF]. In contrast, the Xerox PARK paper handling system [START_REF] Berlin | Motion control of planar objects using large-area arrays of mems-like distributed manipulators[END_REF], [START_REF] Biegelsen | Air-jet paper mover: An example of meso-scale mems[END_REF] uses 1,152 directed air-jets in a 12 in. × 12 in. array to levitate paper sheets. Each jet is separately controlled by an independent MEMS-like valve. 32,000 optical sensors (photodiodes) are integrated between actuators to sense and control the paper position. The levitation-transport system uses two arrays of 578 valves arranged in opposition to one another across a small gap in which the paper is located. The system has demonstrated closed-loop positioning accuracies in the order of 0.05 mm and trajectory tracking with typical velocity about 30 mm•s -1 . Rij et al. [START_REF] Van Rij | Planar wafer transport and positioning on an air film using a viscous traction principle[END_REF] proposed a wafer transport system based on viscous traction principle. The device is designed to produce horizontal air flow under the wafer. The principle is then similar to the paper handling system. On a near microscopic scale, some active surfaces have been developed using MEMS actuator arrays. The surface of Fukuta et al. [START_REF] Fukuta | Design, fabrication and control of mems-based actuator arrays for air-flow distributed micromanipulation[END_REF] is able to produce tilted air-jets thanks to integrated electrostatic valves. In their experiments a flat plastic piece was successfully moved with velocity about 4.5 mm•s -1 . This paper introduces a new principle to move an object on an airhockey table. This system use neither tilted air jet nor suction nozzle. The object is moved indirectly by an air flow which is induced by some strong vertical air jets. These strong jets are coming from some specific orifices of the air-hockey table.

This paper is organized as follow. The first part presents a qualitative explanation of the operating principles and a description of the experimental device called induced air flow surface. The second part describes the active control of the device. The last parts present first experimental results, their analysis and future works.

II. INDUCED AIR FLOW SURFACE

The induced air flow surface is a 120 mm×120 mm square surface upon which an object is moving in aerodynamic levitation.

The device consists of two parts detailed in the exploded view of the Figure 1: • the upper-block is drilled of 15 × 15 holes (nozzles); each one is 0.4 mm in diameter; • the lower-block is drilled of 112 holes in staggered rows; these holes connect one nozzle out of two to independent air inlets; these nozzles are useful to create induced air flow; between the holes of the lower-block a network of diagonal channels connects the other nozzles to a common air inlet located on the side; the airflow spreads over this network and creates the air cushion under the object. The object is maintained in constant levitation thanks to the air cushion created by the airflow that comes through the common air inlet (cf. Figure 1b). The novelty is that the object can be moved on the table by generating strong vertical air-jets through the specific nozzles of the surface. Each nozzle is driven by an independent solenoid valve (3/2 normally closed valve). When a valve is open, air-flow comes through both blocks and generates a vertical air-jet on the front side of the upper-block. The air-jet creates an induced air flow in the surrounding fluid that pulls the object towards the nozzle (cf. Figure 1c). This traction phenomena is a counter-intuitive physics demonstration of fluid mechanics such as the popular Bernoulli levitation [START_REF] Waltham | Bernoulli levitation[END_REF]. It would be very interesting in future works to describe it in a more formal and quantitative way.

The experimental setup for the distributed-air-jet manipulator is composed of pressurized air supply, two pressure regulators, the set of solenoid valves and its control system, and a computer for vision processing. Figures 2 and3 describe the complete hardware configuration.

The induced air flow surface is put on a mechanical platform to adjust its equilibrium position. The air-flow source is provided by compressed air via two pressure control systems. One regulator controls the levitation and the other one supplies air pressure for the valves. Default settings for operating pressures are 10 kPa for levitation and 500 kPa for traction.

Each valve is independently actuated by an electric signal. The electrical voltage applied to the valves is 24 V DC. Control signals are sent by computer via a multi-channel digital output board (NI USB-6509) and a 5V/24V amplifier circuit. A camera is used to grab video frames of the surface of the manipulator. The image processing is done by a computer at the rate of 30 frames per second (the software is cvLink).

III. ACTIVE CONTROL

Contrary to the device of Luntz and Moon, the induced air flow principle does not create stable equilibrium positions and then can not operate without active control. Actually the induced air flow pulls the object towards the nozzle and when the object masks the orifice, the air jet is over. In this case the air radially flows outwards. While the nozzle is under the object, this one is free to move in any direction.

So to control the induced air flow surface, we need sensors. With the aim to conduct the proof-of-concept of a future surface integrating sensors under each nozzle, we emulate local sensors thanks to the image of the camera. The image processing calculates the state bi(k) of every emulated sensor i for each frame k. bi(k) is 1 if the object is above the nozzle i and 0 else. Figure 4 shows the working of the sensor emulation.

The state bi(k) of the sensors is sent to the valve controllers. Then, the controllers independently allocate a state ui(k) to each valve i so as to generate a specific motion of the object. ui(k) = 1 means that the valve i is open at time k, ui(k) = 0 means that the valve is closed. The long term objective with this system is to control three degrees of freedom of an object (two directions and one angle). In this paper, we focus on 1D-control for doing first experiments and establishing a model of the system. The task is to send the object towards the east edge of the surface. For this task, the control laws are quite simple. To carry the object to the east, the valve located east of the object must be opened.

We note xi the abscissa of the nozzle linked to the valve i. The control law ui(k) of an air-jet is defined by:

ui(k) = 1 if xi > xmax(k) 0 else (1)
where xmax(k) is abscissa of the eastern active sensor at time step k.

xmax(k) = max i, b i (k)=1 xi (2)
IV. EXPERIMENTS

A. Acceleration trial

In this section, we report very first experimental results obtained with the induced air flow surface. To begin with, we used a Hshaped object made of aluminum piece (mass: 32.38 g, dimension: 39 mm×33 mm×9 mm). A trial starts by placing the object against the west edge on the surface. Thanks to the virtual sensors, the controller opens the appropriate valves that induces an air flow towards the east and moves the object. Figure 4 shows an image sequence extracted from a video made during the experimental manipulation, which can be further appreciated in the video clip accompanying this paper 1 .

Figure 5 shows the trajectory of the H-shaped object for different values of traction pressure. The exit velocity increases with the pressure from 89 to 181 mm•s -1 whereas the time response decreases.

1 Also available at http://www.femto-st.fr/~guillaume.laurent/

B. Dynamic model

To a first approximation, we can assume that the object receives two forces, a viscous traction due to the induced air flow and a viscous drag force due to friction of the air cushion on its backside:

mẍ(t) = kt[vair(t) -ẋ(t)] -k d ẋ(t) (3)
where m is the mass of the object, vair is the velocity of the induced air flow, kt is the viscous traction coefficient corresponding to the front and lateral sides of the object and k d another viscous coefficient corresponding to the backside of the object.

In other words, the motion of the object is described by a first order model with integrator:

X(s) Vair(s) = k t k t +k d s(1 + m k t +k d s) = Ko s(1 + τos) (4)
The velocity of the induced air flow depends on time. To measure it, we use small expanded polystyrene balls of negligible mass. By opening the valves, the ball moves with the air jet and its velocity is approximately the same as the air flow thanks to its negligible mass.

By observing the position of the balls for a step response (see Figure 6) and deducing the air velocity we can model the induced air flow dynamic by a first order:

Vair(s) P (s) = Ka 1 + τas ( 5
)
where P (s) is the Laplace variable corresponding to the input pressure p, Ka is the gain, and τa the time constant corresponding

Ka 1 + τas p(t) Ko s(1 + τos) vair(t)
x(t) to the establishment of the induced air flow, including the dynamic of the valves.

Figure 7 shows the proposed model of the global system.

C. Parameters identification

The experimental identification of the gain Ka and the time constant τa is done using a mean square error minimization in the time domain. The gain and the time constant depend on the pressure value. Actually the system is not linear according to the input pressure. For a traction pressure of 500 kPa we obtain Ka = 0.742 mm•s -1 •kPa -1 and τa=0.085 s. The maximum velocity of the air is 371 mm•s -1 .

The characterization of the viscous friction coefficients can be established from the velocity measured during the acceleration phase for the conveyed object (cf. Figure 5). We obtain kt = 83.04 mN•m -1 .s and k d = 56.53 mN•m -1 •s. The comparison between the system response and the model output for a step reference signal of amplitude 500 kPa is shown on Figure 8.

D. Estimated performances

The model of the device can be used to do simulations and estimate its expected performances. For instance, we can estimate the maximum velocity that the object could reach with a long enough active surface. The maximum velocity is Ka * Ko * p. For the H-shaped object the maximum velocity the object could reach is 220 mm•s -1 with a traction pressure of 500 kPa.

The settling time of the steady state of the system is given by (for 5%):

Ts = 3 ω0(ξ -ξ 2 -1) (6)
with ω0 = 1/ √ τa * τo and ξ = (τa + τo)/2 √ τa * τo. The settling time for the H-shaped object is 0.70 s.

We can also estimate the maximum traction force that the induced air flow is able to produce. The traction force is given by:

Ft(t) = kt(vair(t) -ẋ(t)) (7)
Figure 9 shows the estimated traction force according to time. The traction force starts from zero because of the settling time of the induced air flow. When the air flow is established and when the object still moves slowly, the traction force reaches a maximum value. Then, the traction force reduces after that time since its value depends on the difference of velocities between the air flow and the object. The peak is reached 0.185 s after the opening of the valves and is about 20.81 mN in value.

We carried out some experiments with different kinds of objects. The results are reported in Table I. The device works better with large and thick objects: the velocity of the object and the traction force are larger, and the settling time is smaller. It is obvious because large and thick objects have a higher drag coefficient that makes the traction more efficient. Furthermore the backside of object must be flat. Indeed, a rough face leads to use higher levitation pressure that is only possible with heavy objects.

V. DISCUSSION

Compared to existing devices, the induced air flow surface produces traction forces in the range of other techniques using tilted air-jets. The tests show that this system is able to produce a force from 1 mN to 21 mN depending on the shape of the object. For instance, the Berlin's Xerox PARK paper handling system [START_REF] Berlin | Motion control of planar objects using large-area arrays of mems-like distributed manipulators[END_REF], [START_REF] Biegelsen | Air-jet paper mover: An example of meso-scale mems[END_REF] exerts a force about 10 mN on a 15 cm × 13 cm plastic sheet. The simulations of the viscous traction concept of Rij et al. [START_REF] Van Rij | Planar wafer transport and positioning on an air film using a viscous traction principle[END_REF] predict a force up to 18 mN on a 100 mm silicon wafer.

In terms of velocity, the induced air flow surface outperforms the existing devices even for thin products. But one negative point is the energetic efficiency. Since the actuation is indirect, only a small part of the mechanical potential energy of the pressured air is used to move the object. Nevertheless, this fact is balanced by the absence of dry friction.

Concerning the bandwidth, our device is in the middle range. It is faster than Luntz and Moon's system one but slower than the devices which use MEMS valves like Fukuta's [START_REF] Fukuta | Design, fabrication and control of mems-based actuator arrays for air-flow distributed micromanipulation[END_REF] and Berlin's ones. Contrary to these last systems, the induced air flow surface requires only conventional technologies and conventional machining that are cheaper and more robust. In addition, both Luntz's and Berlin's devices are limited to flat product since the object is moved between two opposite plates. In our case, the upper space is free. The induced air flow surface can manipulate thick objects and enables the access for a robot to pick or place objects on the surface.

About the controllability of the object motion, this paper presents experiments in a single direction. But, this traction principle is able to control the three degrees of freedom of the object on the plan (two translations and one rotation). Actually, the traction air jets acts like suction points in the surrounding air. By selecting the right air-jets, we can induce an air flow that exerts a force and also a torque on an elongated object. Figure 10 illustrates the rotation capability by opening two traction nozzles.

VI. CONCLUSION AND FUTURE WORK

The described new contactless transport system for delicate and clean products may be implemented in several industrial production processes, such as semiconductor manufacturing, flat panel display production equipment, solar cell production or food industry, etc. The results indicate that the traction force and the bandwidth of the considered device are sufficient when compared with requirements for possible industrial applications.

These experiments are a proof-of-concept that demonstrates the potentiality of the principle. In the future, more complex tasks could be achieved such as 3-dof positioning, trajectory following, part sorting, etc. These tasks require independent control of each traction nozzle. Finding coherent control laws for hundreds of independent air jets is a challenging problem [START_REF] Matignon | Designing decentralized controllers for distributed-air-jet mems-based micromanipulators by reinforcement learning[END_REF]. With this aim in view, a distributed model of the device behavior would be very useful to predict the motion in presence of multiple air jets.

Another great challenge is to integrate the sensors, the valves and the control circuits inside the surface. In this paper, we used a video camera to emulated local sensors and a PC to calculate the control laws. The long term objective is to integrate distributed control units to get a flexible, scalable and robust contactless transport device.

  Cross view that shows the generation of the air cushion (the path of the air flow is darkened). Traction air-jet Induced air flow Traction nozzle Traction inlet (c) Global view that shows the generation of the induced air flow (the path of the air flow is darkened).

Figure 1 .

 1 Figure 1. The induced air flow surface.

Figure 2 .Figure 3 .

 23 Figure 2. Complete hardware configuration.

Figure 4 .

 4 Figure 4. Image sequence of an experiment with a H-shaped object (dark crosses represent inactive sensors, light squares represent active sensors and dark circles represent active traction nozzles).

Figure 5 .Figure 6 .

 56 Figure 5. Abscissa of the center of the object according to time for different traction pressures. The valves are opened at time 0.

Figure 7 .Figure 8 .

 78 Figure 7. Dynamic model of the system.

Figure 9 .

 9 Figure 9. Estimated traction force of the H-shaped object according to time. The valves are opened at time 0.

Figure 10 .

 10 Figure 10. Two traction air jets form a useful induced air flow (top view).

ACKNOWLEDGMENTS

The authors gratefully acknowledge Joël Agnus and David Guibert from the FEMTO-ST Institute for their technical assistance.


G Perillat-Merceroz
email: guillaume.perillat-merceroz@cea.fr

P H Jouneau

G Feuillet

R Thierry

M Rosina

P Ferret

MOCVD growth mechanisms of ZnO nanorods

ZnO is a promising material for the fabrication of light emitting devices. One approach to achieve this goal is to use ZnO nanorods because of their expected high crystalline and optical quality. Catalyst free growth of nanorods by metalorganic chemical vapour deposition (MOCVD) was carried out on (0001) sapphire substrates. Arrays of well-aligned, vertical nanorods were obtained with uniform lengths and diameters. A thin wetting layer in epitaxy with the sapphire substrate is formed first, followed by pyramids and nanorods. The nucleation of nanorods occurs either directly at the interface, or later on top of some of the pyramids, suggesting various nucleation mechanisms. It is shown that crystal polarity plays a critical role in the growth mechanism with nanorods of Zn polarity and their surrounding pyramids with O polarity. A growth mechanism is proposed to explain that most threading dislocations lie in the wetting layer, with only a few in the pyramids and none in the nanorods.

Introduction

ZnO has been studied for decades, but recently generated renewed interest due to its potential applications for optoelectronic devices [1]. Its large band gap (around 3.4 eV, similar to GaN) makes ZnO a candidate for short wave length light emitting diodes (LEDs) and laser diodes. The large exciton binding energy (60 meV compared with 25 meV for GaN) is promising for light emission at room temperature, presuming that the difficult problem of p type doping is solved. Growth of ZnO nanowires or nanorods is widely reported because of possible uses as field emitters, solar cells, gas sensors or LEDs. Their high crystalline quality and purity, due to growth without a catalyst, are adequate for optoelectronic applications. MOCVD growth [2] enables fast, large area deposition at an industrial scale. Understanding of the growth mechanism of nanorods is needed for better control of their density and size and should give an indication as to why the nanorods are defect-free.

Experimental details

ZnO nanorods were grown using catalyst-free MOCVD in a horizontal hot-wall Epigress reactor. The c-plane sapphire substrates were annealed at 1200°C in oxygen. Diethylzinc (DEZn) was used as Zn precursor, N 2 O as the oxidiser, with a VI/II ratio between 100 and 1000. The ZnO nanorods were grown at 750-850°C, with different deposition times in order to follow the formation of the nanorods. The morphology of the samples was investigated by scanning electron microscopy (SEM) using a Zeiss Ultra 55 microscope. Structural studies were carried out by transmission electron microscopy (TEM) on two microscopes: a 300 kV FEI Titan and a 400 kV Jeol 4000 EX.

Results and discussion

Morphology

After a growth of 20 seconds to 1 minute, a thin 2 dimensional ZnO wetting layer is observed on the sapphire substrate (as shown by cross sectional TEM in Figure 5b), together with nanorods and pyramids (Figure 1a andb). The higher density seen in the 20 seconds growth sample is due to different growth conditions. After one hour of deposition, nanorods have grown in diameter and length. At this stage, the nanorods have a typical length of 4 µm, and a diameter of 200 nm (Figure 1c). Nanorods grow along the c direction as demonstrated by X-ray diffraction [3]. Some pyramids exhibit nanorods on their top and some do not.

Role of crystal polarity

We used convergent beam electron diffraction (CBED) to determine the crystal polarity of nanorods and pyramids. Nanorods were found to be of Zn polarity while pyramids have O polarity (Figure 2). This is in agreement with a recent result by Sun et al. [4] who reported that nanorods grown by pulsed laser deposition exhibit Zn polarity. Contrary to that the buffer layer shows O polarity. Facets of the hexagonal nanorods have been indexed basing on intensity profiles of nanorods viewed along the <1-100> or <11-20> zone axis. It was found that they are of {1-100} type (Figure 3). Laudise et al. have also reported the higher growth rate of the [0001] direction (Zn polarity) and the presence of {1-100} facets in hydrothermal growth [5]. Growth of nanorods requires Zn polarity nuclei which have a high growth rate in the [0001] direction, partly because of the low free energy of the {1-100} facets.

Nanorod nucleation

Nanorods originate either from the ZnO / sapphire interface (Figure 4a), or from the top of some pyramids (Figure 4b). Contrasts in the nanorod are bend contours resulting from the glue-induced strain. No defects are visible in nanorods dispersed on a carbon film (Figure 5d). For one sample, pyramids and nanorods were observed to be aligned in a <11-20> direction (Figure 4c). In this case, nucleation of the pyramids and of the nanorods would be linked to atomic steps at the substrate surface [6]. However, as the alignment along a particular direction is not always seen and as some nanorods nucleate on top of pyramids, atomic steps could not explain the nucleation of all nanorods. The exact nucleation mechanisms remain under investigation.

Growth mechanism and defects

As it is usually observed, the orientation relationship is (Figure 5a):

[0001] Al 2 O 3 // [0001] ZnO and [-1010] Al 2 O 3 // [11-20] ZnO leading to an in-plane mismatch of 18.4% between the sapphire substrate and ZnO. A regular network of misfit dislocations is formed at the interface in order to relax the heteroepitaxial stress (Figure 5b andc): with a thickness of 8 monoatomic layers, the wetting layer is almost totally relaxed. But no dislocations are observed in the nanorods (Figure 5d). This high crystalline quality of nanorods is confirmed by photoluminescence studies [7]. The nanorods nucleating at the ZnO / sapphire interface are very narrow (3 to 20 nm, Figure 6a) suggesting that few misfit dislocations are present at the base of the nanorod. Furthermore, the ratio between the nanorod length and the diameter is such that the probability for a dislocation to thread into the nanorods is low. When a nanorod has grown vertically, a pyramid nucleates around it. The pyramid grows both, laterally and vertically, and dislocations follow the growth front, threading from the nanorod base to the sides of the pyramid (Figure 6b, c andd). In the case of a pyramid with no nanorod inside, growth on the wetting layer is similar. Most dislocations in the wetting layer bend over, due to the lateral growth of the pyramid (Figure 7).

Conclusion

We have proposed a growth mechanism of ZnO nanorods. A 2 dimensional wetting layer covers the sapphire substrate, and nuclei appear locally to form pyramids and nanorods. Nanorods grow because some nuclei are of Zn polarity and because of the large growth rate anisotropy between [0001] and [000-1] direction. No dislocations are observed in the nanorods. Threading of dislocations from the substrate is not very probable because of the nanorod narrowness. The dislocations are not favoured energetically because of the nanorods length. Relatively few dislocations are observed inside the pyramids because of their lateral overgrowth on top of the wetting layer which bends dislocations under the pyramids.

Figure 1 .

 1 Figure 1. Tilted SEM images of ZnO nanorods: (a) after 20 s of growth, (b) after 1 min of growth, (c) after 1 hour of growth.

Figure 2 .

 2 Figure 2. Determination of the polarity of both the nanorod and the pyramid: (a) STEM image of the analyzed zone, (b) and (c) respective CBED patterns of the nanorod and the pyramid. Growth direction upwards. (d) Simulated CBED pattern with the JEMS software.

Figure 3 .

 3 Figure 3. Identification of the side facets of the nanorods by intensity profiling of TEM bright-field images: (a) <1-100> zone axis (b) <11-20> zone axis.

Figure 4 .

 4 Figure 4. Nucleation of ZnO nanorods. (a) Nucleation at the sapphire / ZnO interface. The nanorod pointing out of the pyramid was removed during TEM sample preparation (b) Nucleation on top of a pyramid. (c) Top view SEM image showing alignment of pyramids and nanorods along a <11-20> direction.

Figure 5 .

 5 Figure 5. Stress relaxation and defects formation: (a) Fourier transform at the ZnO / sapphire interface, (b) high resolution TEM image of the ZnO wetting layer on sapphire after one min of growth, (c) [01-10] filtered image showing the network of misfit dislocations at the sapphire / ZnO interface and (d) bright field TEM image of a nanorod with no dislocations.

Figure 6 .

 6 Figure 6. Nanorods surrounded by pyramids: (a) High resolution TEM image (1 min growth). (b) (c) (d) Twobeam bright field TEM images (30 min growth). The nanorods pointing out of the pyramids were removed during TEM sample preparation. Images (c) and (d) are taken on the same pyramid and with the same magnification.

Figure 7 .

 7 Figure 7. Defect structure of nanorods free ZnO pyramid: (0002) two beam dark field image of a pyramid on the wetting layer (left) and zoom on the interface region (right).


Guillaume J Laurent
email: guillaume.laurent@ens2m.fr

Laëtitia Matignon

N Le Fort-Piat

The World of Independent Learners is not Markovian

Keywords: Multi-Agent System, Machine Learning, Reinforcement Learning

In multi-agent systems, the presence of learning agents can cause the environment to be non-Markovian from an agent's perspective thus violating the property that traditional single-agent learning methods rely upon. This paper formalizes some known intuition about concurrently learning agents by providing formal conditions that make the environment non-Markovian from an independent (non-communicative) learner's perspective. New concepts are introduced like the divergent learning paths and the observability of the effects of others' actions. To illustrate the formal concepts, a case study is also presented. These findings are significant because they both help to understand failures and successes of existing learning algorithms as well as being suggestive for future work.

Introduction

The problem of an agent learning to act in an unknown world is both challenging and interesting. Besides challenges inherited from single-agent learning, including the curse of dimensionality, the exploration-exploitation trade-off and the issue of observability of state, several new challenges arise in multi-agent learning [START_REF] Tesauro | Reinforcement learning in autonomic computing: A manifesto and case studies[END_REF]. Foremost among these is the difficulty of defining good learning goals for the multiple learning agents [START_REF] Busoniu | A comprehensive survey of multiagent reinforcement learning[END_REF]. Furthermore, in the case of cooperative tasks, a learner must coordinate its behavior with other learners, such that a coherent joint behavior results [START_REF] Fulda | Predicting and preventing coordination problems in cooperative q-learning systems[END_REF]. Finally, the presence of multiple concurrent learners makes the environment non-stationary from a single agent's perspective. The loss of environmental stationarity is a commonly cited cause of difficulties in multi-agent learning systems [START_REF] Vlassis | A concise introduction to multiagent systems and distributed artificial intelligence[END_REF][START_REF] Panait | Cooperative multi-agent learning: The state of the art[END_REF][START_REF] Dowling | Decentralized reinforcement learning for the online optimization of distributed systems[END_REF][START_REF] Sandholm | Perspectives on multiagent learning[END_REF][START_REF] Bowling | An analysis of stochastic game theory for multiagent reinforcement learning[END_REF].

A process is said non-stationary if its transition probabilities change with the time. A non-stationary process can be Markovian if the evolution of its tran-sition probabilities depends only on time and not on the history of actions and states. Most single-agent learning algorithms rely on the Markov assumption but can deal with time-dependent non-stationarity [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF].

In multi-agent learning systems, the process evolution is led by the agents' actions. For a learning agent, the choice of its future actions is dependent upon its own history, in other words upon past observations of its environment. If a past action of one agent have influenced the past evolution of the process, it could also have changed the learned behavior of a second agent. Then, from the first agent's perspective the future evolution of the environment can be different depending of its past action. Therefore, from a single agent's perspective, the environment no longer appears Markovian. This violation of basic assumptions requires new techniques to be developed to learn effective policies in stochastic games.

This paper contributes to analyze the underlying conditions that lead the environment to be non-Markovian from a single agent's perspective. We focus our study on independent learners in stochastic games where this problem is acute. Independent learners are non-communicative (isolated) agents that are unable to observe the rewards and actions of the other agents [START_REF] Claus | The dynamics of reinforcement learning in cooperative multiagent systems[END_REF]. We formally show under which assumptions the local process is not Markovian. For this purpose, some new concepts are introduced like the divergent learning paths and the observability of the effects of others' actions.. These findings are significant because they offer a new perspective on related research in multi-agent learning and help to provide a better understanding of the difficulties faced by multiagent learning methods. It both helps to understand failures and successes of learning algorithms as well as being suggestive of areas for future work.

Beyond the formal analysis, we provide a case study example using independent Q-Learners. Q-Learning [START_REF] Christopher | Technical note: Q-learning[END_REF] is a well-known reinforcement learning algorithm that has been applied successfully in multi-agent cases despite the lack of guaranteed convergence. This example helps to thoroughly understand the impact of non-Markovian effects on this algorithm. Moreover, it shows that the exploratory actions can be detrimental for other learners in a cooperative game.

The remainder of this paper is organized as follows. Section II introduces the necessary background in multi-agent learning and related works. Section III defines formally the concept of learning agents. Section IV introduces some useful concepts and shows under which assumptions, the local process is not Markovian. Section V then gives a case study which enlightens the non-Markovian problem. Section VI concludes and explores some of the implications of the results described in the paper.

Background

In this section, we introduce some background material that will be used throughout the paper.

Stochastic Games

Stochastic games [START_REF] Shapley | Stochastic games[END_REF] (also called Markov games) are the foundation for much of the research in multi-agent learning. Stochastic games are a superset of Markov decision processes [START_REF] Bellman | A markov decision process[END_REF] and matrix games [START_REF] Neumann | Theory of Games and Economic Behavior[END_REF][START_REF] Osborne | A Course in Game Theory[END_REF], including both multiple agents and multiple states.

Definition 1. A (finite) stochastic game is a tuple m, S, A 1 , . . . , A m , T, R 1 , . . . , R m , where,
• m is the number of agents (or players),

• S is the finite set of states,

• A i is the finite set of actions available to agent i (and

A = A 1 × • • • × A m
is the joint action set),

• T : S × A × S → [0; 1] is the transition function, such that, ∀s ∈ S, ∀a ∈ A, s ∈S T (s, a, s ) = 1, (1)
• R i : S × A → R is the reward function for the ith agent.

The transition function T gives the probability that action a in state s at time step k will lead to state s at step k + 1,

P s k+1 = s | a k = a, s k = s = T (s, a, s ). (2)
Note that joint actions and sets of joint actions are typeset in bold throughout the paper, e.g. a and A.

By definition, a stochastic game satisfies the Markov assumption. Basically, this requires that the probability to reach a state and to get a reward be fully specified by the current state and the agent's action (and eventually by the time). We can state this property formally. Definition 2. A decision process is Markovian, iff, for all k ∈ N, (s 0 , . . . , s k+1 ) ∈ S k+2 , and (a 0 , . . . , a k ) ∈ A k+1 ,

P s k+1 = s k+1 | a k = a k , s k = s k , . . . , a 0 = a 0 , s 0 = s 0 = P s k+1 = s k+1 | a k = a k , s k = s k . (3)
If a process is not Markovian, it is typically termed history dependent. Another quality of decision process is whether its transition and reward functions depend explicitly on time. Definition 3. A decision process is stationary (or homogeneous), iff, for all k, l ∈ N, s , s ∈ S, a ∈ A

P s k+1 = s | a k = a, s k = s = P s l+1 = s | a l = a, s l = s . (4)
A non-stationary process can be Markovian if the evolution of its transition and reward functions depends only on time step and not on the history of actions and states.

Independent Learners

Claus and Boutilier [START_REF] Claus | The dynamics of reinforcement learning in cooperative multiagent systems[END_REF] distinguish two fundamental classes of learning agents: independent learners and joint-action learners. The former have no knowledge of the other agents, interacting with the environment as if no other decision-makers exist. In particular, they are unable to observe the rewards and actions of the other agents. Independent learners were also described as isolated concurrent learners. Joint action learners, on the contrary, are aware of the existence of other agents and are capable of perceiving (a posteriori) their actions and rewards.

Learning algorithms considering joint-action learners are easily implementable from standard single-agent reinforcement learning algorithms [START_REF] Michael | Value-function reinforcement learning in markov games[END_REF]. From a single agent's perspective the process stays Markovian as it observes the actions of others.

However, in many practical applications it is not reasonable to assume the observability of the actions of the others [START_REF] Melo | Convergence of independent adaptive learners[END_REF]. Most agents interact with their surroundings by relying on sensory information and action recognition is often far from trivial. With no knowledge of the actions of the other agents and payoffs, the problem becomes more difficult.

A Key Challenge

As an agent is not aware of actions of the other agents, it does not know if others are changing their policy or taking an exploratory action. Specifically, the transition probabilities associated with the action of a single agent from one state to another are not stationary and change over time as the other agents' action choices change. These choices are probably influenced by the past history of play, and so the history of play influences the future transition probabilities when revisiting a state. Therefore, from a single agent's perspective, the environment no longer appears Markovian. All the recent surveys and many works on multiagent learning mention this fact as a key challenge [START_REF] Bowling | An analysis of stochastic game theory for multiagent reinforcement learning[END_REF][START_REF] Vlassis | A concise introduction to multiagent systems and distributed artificial intelligence[END_REF][START_REF] Munoz | Learning to cooperate in multi-agent social dilemmas[END_REF][START_REF] Panait | Cooperative multi-agent learning: The state of the art[END_REF][START_REF] Weinberg | Best-response multiagent learning in non-stationary environments[END_REF][START_REF] Dowling | Decentralized reinforcement learning for the online optimization of distributed systems[END_REF][START_REF] Busoniu | A comprehensive survey of multiagent reinforcement learning[END_REF][START_REF] Tuyls | An evolutionary dynamical analysis of multi-agent learning in iterated games[END_REF][START_REF] Yang | Multiagent reinforcement learning for multirobot systems: A survey[END_REF][START_REF] Sandholm | Perspectives on multiagent learning[END_REF][START_REF] Jelle | Collaborative multiagent reinforcement learning by payoff propagation[END_REF][START_REF] Young | The possible and the impossible in multi-agent learning[END_REF].

Using single-agent algorithm in this context is inherently flawed: the convergence of such algorithm usually relies on an underlying transition model that is stationary [START_REF] Vlassis | A concise introduction to multiagent systems and distributed artificial intelligence[END_REF]. For example, straightforward extensions of Q-Learning to multiagent systems fail to reach the optimal policy in fairly simple domains [START_REF] Claus | The dynamics of reinforcement learning in cooperative multiagent systems[END_REF][START_REF] Kapetanakis | Improving on the reinforcement learning of coordination in cooperative multi-agent systems[END_REF]. However this approach has been successfully applied in simulation to domains such as prey-pursuing games [START_REF] Tan | Multiagent reinforcement learning: Independent vs. cooperative agents[END_REF], block-pushing problems [START_REF] Ip Sen | Learning to coordinate without sharing information[END_REF], the control of elevators [START_REF] Crites | Improving elevator performance using reinforcement learning[END_REF], the exploration of planets by mobile robot teams [START_REF] Zheng | Multiagent reinforcement learning for a planetary exploration multirobot system[END_REF], the control of a two-link rigid manipulator [START_REF] Busoniu | Decentralized reinforcement learning control of a robotic manipulator[END_REF], multi-robot cooperative transportation tasks [START_REF] Wang | A machine-learning approach to multi-robot coordination[END_REF], distributed manipulation [START_REF] Matignon | Designing decentralized controllers for distributed-air-jet mems-based micromanipulators by reinforcement learning[END_REF] to name but a few.

Understanding the underlying conditions which cause non-Markovian aspects will be useful to predict whether a given system is likely to experience convergence problems or not. Moreover, once these conditions are isolated and understood, the development and application of new (or significantly modified versions of) machine learning methods will be greatly facilitated. Before exam-ining these underlying conditions, we have to formalize the concept of a learner.

Definition of a Learner

In this section, we propose a formal definition of a learner. This definition is based on the concept of the individual policy used in most of the works.

Individual and Joint Policies

Independent learners observe the process state and receive a reward after executing an individual action. These agents choose their individual actions based on individual policies. A policy (or strategy) for an agent is a probability distribution over the set of its actions.

Definition 4. The policy of an agent

i at time step k is a function π i k : S ×A i → [0; 1] such that, ∀s ∈ S, a∈A i π i k (s, a) = 1. (5)
The policy of an agent gives the probability of selecting an action from a state,

∀a ∈ A i , P a i k = a|s k = s = π i k (s, a). (6)
The space of possible policies for agent i is noted Π i .

The concept of individual policy leads to the concept of joint policy when considering the actions of a group of agents.

Definition 5. The joint policy is a function π

k : S × A → [0; 1] such that, ∀s ∈ S, a∈A π k (s, a) = 1. (7)
The joint policy is the policy of the group of agents. The joint policy is a mapping that defines the probability of selecting a joint action from a particular state, formally,

∀a ∈ A, P [a k = a|s k = s] = π k (s, a). (8)
For independent learners which select actions independently, the joint policy is given by:

∀s ∈ S, ∀a ∈ A, π k (s, a) = m i=1 π i k (s, a i ). ( 9
)

Learners and Divergent Learning Paths

A learner uses its past experiences to improve its behavior. The policy of a learner may change over time depending on the history of states, of rewards and of its own actions. It is clear that an agent may learn different behaviors depending on the evolution of the process. In other words, a learner is not only non stationary but also history dependent.

We propose here to formalize the definition of a learner. First, we call the learning path of an agent i at step k the random variable h i k which summarizes all past states, rewards and agent's actions,

h i k = s 0 , r i 0 , a i 0 , s 1 , r i 1 , a i 1 , . . . , s k , r i k , a i k ( 10
)
h i k takes on its values in H i k which is the set of possible realizations of the agent's learning path. Definition 6. A learner i is defined by its learning function Ψ that associates a policy to a learning path, Ψ :

H i k → Π i h → Ψ(h) = π i k,h , (11)
where Π i is the space of possible policies for agent i. π i k,h is the policy of the agent i at step k after the learning path h.

This definition introduces only deterministic learning functions (∀h, g ∈ H i

k , h = g ⇒ Ψ(h) = Ψ(g)). Stochastic learning functions could have been considered as well (see discussion bellow).

The second characteristic of a learner is that the obtained policy could be different with regard to the past of the agent even if the agent reaches the same state at step k. To express this, we propose the concept of divergent learning paths.

Definition 7. A pair of two different learning paths h, g ∈ H i

k which lead to the same state s k at time k, and such that,

∃a ∈ A i , π i k,h (s k , a) = π i k,g (s k , a). ( 12
)
is called a pair of divergent learning paths.

Discussion

The learning function represents the algorithm implemented in the agent. We focus here on deterministic learning functions. For instance, Q-Learning [START_REF] Christopher | Technical note: Q-learning[END_REF] is a deterministic learning function because agent's Q-values are updated using an algebraic equation and the agent's policy is usually computed from Q-values using a Boltzmann distribution [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. Deterministic learning functions cover most of reinforcement learning algorithms for independent learners such as Wolf-PHC [START_REF] Bowling | Multiagent learning using a variable learning rate[END_REF], Distributed Q-Learning [START_REF] Lauer | An algorithm for distributed reinforcement learning in cooperative multi-agent systems[END_REF], Hysteretic Q-Learning [START_REF] Matignon | Hysteretic q-learning : an algorithm for decentralized reinforcement learning in cooperative multi-agent teams[END_REF], etc.

We could also imagine stochastic learning functions. This case could be studied as well. The proof would be less straightforward but would lead to the same results. If deterministic learning functions imply non-Markovian local processes, so do stochastic ones. Indeed, focusing on deterministic functions is better for the clarity of the paper and does not harm the generality of the results.

Local Decision Processes

The Agent's Perspective

Independent learners ignore the presence of the other agents in the system. That is to say, each agent can treat the other agents as part of its environment (cf. figure 1). We call local decision process the environment from a single agent's perspective.

Definition 8. The local decision process from the ith agent's perspective is defined by the tuple S, A i , T i k , R i k , where, • S is the finite set of states,

• A i is the finite set of actions, • T i k : S × A i × S → [0; 1] is the transition function at time step k, • R i k : S × A i → R
T i k (s, a, s ) = a -i ∈A -i π -i k (s, a -i )T (s, a, a -i , s ), (13)
and,

R i k (s, a) = a -i ∈A -i π -i k (s, a -i )R i (s, a, a -i ). ( 14
)
We use π -i k to refer to the current joint policy of all the agents except agent i. In the same way, we use a -i to refer to the joint actions of all the agents except agent i. a, a -i is then the joint actions of all the agents including agent i.

Proof. This result comes directly from the law of total probability. For all (s, a, s ) ∈ S × A i × S,

T i k (s, a, s ) = P s k+1 = s | a k = a, s k = s = a -i ∈A -i P s k+1 = s | a k = a, a -i k = a -i , s k = s P a -i k = a -i |a k = a, s k = s . ( 15
)
As agents choose their action independently from each other, a -i k and a are independent. So, we get,

T i k (s, a, s ) = a -i ∈A -i P s k+1 = s | a k = a, a -i k = a -i , s k = s P a -i k = a -i |s k = s = a -i ∈A -i T (s, a, a -i , s )π -i k (s, a -i ). ( 16
)
On the one hand, if the policies of other agents are stationary, the local process is simply reduced to a Markov decision process. On the second hand, it is obvious that the local process can be non-stationary as π -i k is not. We would like to show that, when one of the other agents is learning, the local process can no longer be Markovian.

Observability of the effects of the actions

In fact, everything depends on the observability of the effects of the actions of the learner. We say that the effects of the actions of an agent j are observable from the ith agent's perspective in a state s if the jth agent's choice has an influence on the transition probability of the process from the ith agent's perspective. Definition 9. The effects of the actions of an agent j are observable from the ith agent's perspective in state s at step k if the probability of reaching the state s from a state s depends on the jth agent's policy, formally if π j and πj are two policies of agent j, such that,

∃b ∈ A j , π j (s, b) = πj (s, b), (17)
Then, the effects of the actions of agent j are observable if,

∃a ∈ A i , ∃s ∈ S, T i π j (s, a, s ) = T i πj (s, a, s ). ( 18
)
This definition means that if the jth agent were to change its policy, the ith agent observe a change in the evolution of the process.

Non-Markovian Local Decision Processes

We are now able to state sufficient conditions of the local process to be non-Markovian.

Theorem 1. Let m, S, A 1 , . . . , A m , T, R 1 , . . . , R m be a Stochastic Game with m agents and π i : S × A i → [0; 1] the agent's policies. If,

• (h, g) are a pair of divergent learning paths for an agent j,

• h and g are both attainable,

• the effects of jth agent's actions are observable from an ith agent's perspective in the state s, where s is the common final state of h and g, then, the local decision process from the ith agent's perspective is not Markovian.

A learning path is attainable if the probability to follow it is not zero.

Proof. Let (h, g) ∈ H j k 2 be a pair of divergent learning paths for an agent j. Let s be the common final state of h and g. As h and g verify the equation 12, we have,

∃b ∈ A j , π j k,h (s, b) = π j k,g (s, b). ( 19
)
As the effects of the actions of agent j are supposed to be observable, this statement implies that,

∃a ∈ A i , ∃s ∈ S, T i π j k,h (s, a, s ) = T i π j k,g (s, a, s ), ( 20
)
where s is the realization of s k . T i π j k,h (s, a, s ) is the transition probability of the local process after the path h, then we can write that,

T j π j k,h (s k , a, s ) = P s k+1 = s | a i k = a, s k = s k , h j k = h . (21)
So rewriting 20, we get, ∃a ∈ A i , ∃s ∈ S,

P s k+1 = s | a i k = a, s k = s k , h j k = h = P s k+1 = s | a i k = a, s k = s k , h j k = g . (22)
Some transition probabilities depend on learning paths. As these learning paths are supposed to be attainable and different in the past, then the local process is history dependent and not Markovian.

Discussion

The proof is straightforward as the definitions have been well established. What is important is the statement of conditions that lead to non-Markovian local processes.

The first condition expresses the fact that agent j is a learner. A learner is history dependent. But the presence of a learner is not sufficient to make the local process non-Markovian: some divergent learning paths of the learner must be attainable.

It is a strong assumption which is not easy to check in practice. Nevertheless, to guarantee their convergence, most of the reinforcement learning algorithms suppose that every state can be visited an infinite number of time. For instance, this is the case of Q-Learning. This condition is generally guaranteed by the use of action-selection methods which are not fully greedy and which keep a small account of random exploration. This practice permits the algorithm to visit the state space in a satisfactory way. This approach may also ensure that the learning paths of the learner are attainable.

The last hypothesis is that the effects of the actions of the learner must be observable from another agent's perspective. This new concept of observability reports a coupling of the actions of both agents. On the one hand, if there is no coupling between the actions then both agents will evolve independently in Markovian worlds. On the other hand, when actions are coupled, if the learner changes its policy, then the other agent will have to adapt itself to this evolution.

Anyway, these three assumptions are sufficient conditions. We believe that they are also necessary but a formal proof remains to be carried out. In the next section, we propose to examine an example. We think that a good example is as important as formal results to thoroughly understand non-Markovian impacts on learners.

Case study

This example uses a two-state cooperative stochastic game with two Q-Learners. We chose Q-Learning [START_REF] Christopher | Technical note: Q-learning[END_REF] because many works use it with success despite the lack of guarantees (cf. section 2.3). We will show that the local process from the first agent's perspective is not Markovian that explains the possible failures of using this algorithm even in cooperative multi-agent system.

A Simple Stochastic Game

We considered a stochastic game defined by:

• 2 states, S = {0, 1},

• 2 actions for each agent, A = {0, 1} × {0, 1},

• a deterministic transition function T (s, a) and a team reward function R represented in figure 2.

Q-Learners

Q-Learning is a well-known reinforcement learning algorithm for single agent process. The objective is to compute an optimal action-value function in order to get an optimal policy. The action-value function for a given policy π is defined by,

Qπ(s, a) = E ∞ t=0 γ t r t+1 |s 0 = s, a 0 = a, π . ( 23
)
where γ is a discount factor 0 ≤ γ < 1.

We assume that both agents are independent learners and apply Q-Learning in the classic sense. Each agent i stores a local action-value function Q i (s, a) only depending on state s and on its own action a. Q i (s, a) is an estimation of the expected sum of future rewards when taking action a i from state s at time k. This approach results in big storage and computational savings in the actionspace. For example, with 7 agents and 6 actions per agent only 42 Q-values have to be stored per state rather than 6 7 Q-values for joint-action learners.

The action-value function of agent 2 is noted Q 2 k (s, a). We assume that Q 2 k is equal to the optimal1 action-value function at time k for the discounted criteria with γ = 0.9, i.e.,

Q 2 k (0, 0) = 4.26 Q 2 k (1, 0) = 4.26 Q 2 k (0, 1) = 4.74 Q 2 k (1, 1) = 5.26
We assume that agent 2 always follows a greedy policy based on Q 2 k (no exploratory actions)

π 2 k (s, a) =    1 if a = arg max b Q 2 k (s, b) 0 else (24)
We also assume that agent 2 is still learning. We use the learning rate α = 0.6 to quickly see non-Markovian effects. Agent 2 updates its Q-values using the one-step backup equation,

Q 2 k+1 = (1 -α)Q 2 k (s k , a 2 k ) + α(r k+1 + γ max b∈A 2 Q 2 k (s k+1 , b)). (25)

Two Different Scenarios

The local process from the first agent's perspective at step k is then defined by:

• 2 states, S = {0, 1}, • 2 actions, A 1 = {0, 1},
• a deterministic transition function, such that,

T 1 k (s, a, s ) = T (s, a, arg max b Q 2 k (s, b) , s ) (26)
• a reward function, such that,

R 1 k (s, a) = R(s, a, arg max b Q 2 k (s, b) ). ( 27
)
For example, the transition probability from the first agent's perspective starting in state 0, doing action 1 and reaching the state 1 is then,

T 1 k (0, 1, 1) = T (0, 1, arg max b Q 2 k (0, b) , 1) = 1 (28)
Now, we will study the effect of two different sequences of actions starting from state 0 at step k. In the first sequence, we assume that agent 1 follows the optimal policy 2 , that is a 1 k = 1, a 1 k+1 = 1. In the second one, agent 1 experiences other actions by playing a 1 k = 0, a 1 k+1 = 0. Let us study in detail the effects of each scenario.

Scenario 1 (agent 1 is playing the optimal policy) 1. step k: the process state is 0, agent 1 does action 1 and agent 2 selects a greedy action in arg max

The transition probability from the first agent's perspective for state 0 and action 1 is therefore:

T 1 k+2 (0, 1, 1) = T (0, 1, arg max b Q 2 k+2 (0, b) , 1) = 1. (31)
So, following scenario 1 we get,

P s k+3 = 1 | a 1 k+2 = 1, s k+2 = 0, a 1 k+1 = 1, s k+1 = 1, a 1 k = 1, s k = 0 = 1. ( 32
)
Scenario 2 (agent 1 is exploring)

1. step k: the process state is 0, agent 1 does action 0 and agent 2 selects a greedy action in arg max 2 The optimal policy is computed from a centralized point-of-view of the process.

The transition probability from the first agent's perspective for state 0 and action 1 is then:

T 1 k+2 (0, 1, 1) = T (0, 1, arg max b Q 2 k+2 (0, b) , 1) = 0. ( 35
)
So, following scenario 2 we get,

P s k+3 = 1 | a 1 k+2 = 1, s k+2 = 0, a 1 k+1 = 0, s k+1 = 0, a 1 k = 0, s k = 0 = 0. ( 36
)
The transition probabilities of the local process have changed! This fact is not only a non-stationarity. Indeed, if the first agent's actions are different, the transition probabilities can remain the same. The transition probabilities of the local process for state 0 and action 1 depend on the past actions of agent 1. So, the local process is history dependent and not Markovian.

We can check that the action-state sequences form a pair of divergent learning paths for agent 2. The action-state sequences are different and lead to two different policies while reaching the same state 0 at time k + 2. Both learning paths are attainable thanks to agent 1 exploratory actions.

We can also check that the effects of the actions of agent 2 are observable from the first agent's perspective in state 0. On the one hand, if π 2 (0, 1) = 1, then T 1 k+2 (0, 1, 1) = 1. On the other hand, if π 2 (0, 1) = 0, then T 1 k+2 (0, 1, 1) = 0. So, the equation ( 18) holds and the effects of the actions of agent 2 are observable.

Discussion

This example meets all the conditions for the local process to be non-Markovian: agent 2 is learning, the exploratory actions of agent 1 can induce divergent learning paths and the system is strongly coupled.

It is interesting to notice that if agent 1 acts in an optimal way (scenario 1), then agent 2 does not change. However, if agent 1 explores (scenario 2), then agent 2 destroys its initially-optimal policy. This highlights one of the dangers of the use of Q-Learning in the multi-agent context. Simple-but-coupled situations can put this algorithm in the wrong. This confirms and explains the failures of Q-Learning on matrix games presented by Claus and Boutillier [START_REF] Claus | The dynamics of reinforcement learning in cooperative multiagent systems[END_REF] and by Kapetanakis and Kudenko [START_REF] Kapetanakis | Improving on the reinforcement learning of coordination in cooperative multi-agent systems[END_REF].

Conclusion

In this paper, we contributed to identify conditions that lead the environment to be non-Markovian from an independent learner's perspective. The first assumption requires that there is in the system at least one agent which is learning. This means that different state-action sequences can lead to different policies for this agent. The second condition is the attainability of such learning paths. The third condition is that the effects of the learner's actions are observable from another agent's perspective. These three assumptions are sufficient conditions. We believe that they are also necessary but a formal proof remains to be carried out. In the meantime, this analysis shows the proposed algorithms for independent learners in an interesting light.

Numerous works use directly single-agent algorithms in the multi-agent context. As we saw in the previous section, the results of this approach are not always good. For instance, the presented example shows that an exploratory action of an agent can destroy the optimal policy of another one. In this example the agents' actions are highly coupled. In low coupled distributed systems, it is reasonable to think that these algorithms are more likely to converge because the effects of the non-stationarity of agents are less observable. In some degree, the observability of the effects of the actions may have a direct influence on the convergence of the algorithms. Nevertheless, this comment must be qualified. Indeed, in cooperative multi-agent systems, theoretical and experimental works showed that only few couplings, as action shadowing, raise convergence issues [START_REF] Fulda | Predicting and preventing coordination problems in cooperative q-learning systems[END_REF][START_REF] Matignon | Coordination of independent learners in cooperative markov games[END_REF]. Anyway, the convergence of these approaches requires to use decreasing exploration rates so as to avoid too much concurrent exploration [START_REF] Claus | The dynamics of reinforcement learning in cooperative multiagent systems[END_REF][START_REF] Kapetanakis | Improving on the reinforcement learning of coordination in cooperative multi-agent systems[END_REF]. The principle is to decrease the exploration frequency as the learning goes along so that each agent should find the best response to the behavior of the others. Another way is to use coordinated exploration techniques that exclude one or more actions from the agent's action space, so as to coordinate their exploration in a shrinking joint action space [START_REF] Verbeeck | Multi-agent reinforcement learning in stochastic single and multi-stage games[END_REF][START_REF] Verbeeck | Exploring selfish reinforcement learning in repeated games with stochastic rewards[END_REF]. Both approaches can be considered as a means of reducing the attainability of divergent learning paths. By reducing the exploration of new actions, the agents evolve slower and the non-Markovian effects are reduced.

To overcome the problems encountered by single-agent methods, many algorithms have been proposed in order to address the non-stationarity problem. A few approaches address this by restoring the Markovian property of the local environment by the memorizing of past events [START_REF] Melo | Convergence of independent adaptive learners[END_REF][START_REF] Lauer | Reinforcement learning for stochastic cooperative multi-agent systems[END_REF]. The algorithm proposed by Lauer and Riedmiller [START_REF] Lauer | Reinforcement learning for stochastic cooperative multi-agent systems[END_REF] builds an exhaustive list of past actions [START_REF] Lauer | Reinforcement learning for stochastic cooperative multi-agent systems[END_REF]. Thanks to the distinction between joint actions, the algorithm is proved to converge. An obvious limitation is its application in large stochastic games because of the combinatorial explosion of the number of joint actions and so of the size of lists.

The last class of methods is to develop algorithms that are robust to non-Markovian effects. For instance, the Distributed Q-Learning ignores the effect of an unfortunate action done by a fellow agent [START_REF] Lauer | An algorithm for distributed reinforcement learning in cooperative multi-agent systems[END_REF]. The idea that the agents have to be lenient with regard to exceptional sub-optimal behavior of other agents gave several algorithms. We can mention the WOLF-PHC algorithm [START_REF] Bowling | Multiagent learning using a variable learning rate[END_REF], the Hysteretic Q-Learning [START_REF] Matignon | Hysteretic q-learning : an algorithm for decentralized reinforcement learning in cooperative multi-agent teams[END_REF], and lenient learners [START_REF] Panait | Theoretical advantages of lenient learners: An evolutionary game theoretic perspective[END_REF]. The experimental results show that these approaches are especially robust and converge in most highly coupled systems with high observability of the effects of the actions. On the one hand, the leniency of agents tends to make the bad changes of policies of team-mates unobservable. On the other hand, an agent seldom changes its own policy, and then the number of divergent learning paths is lower than with single-agent methods.

In this paper, we limited ourselves to non-communicating learners because the non-Markovian effects are exacerbated in this case. The problem of nonstationarity agents also arises when communications are possible. Then, for cooperative systems, the communication between agents can be seen as a promising way to report policy changes and so to ensure convergence.

Figure 1 :

 1 Figure 1: Illustration of the first agent's perspective.

Property 1 .

 1 is the expected reward at time step k.The local transition function Ti k and the local reward function R i k can be easily computed from T , R i and from the current policies of the other agents[START_REF] Borkar | Reinforcement learning in markovian evolutionary games[END_REF][START_REF] Bowling | Multiagent Learning in the Presence of Agents with Limitations[END_REF]. Let m, S, A 1 , . . . , A m , T, R 1 , . . . , R m be a Stochastic Game with m agents and π i k : S ×A i → [0; 1] the agent's policies. The local decision process from the ith agent's perspective is defined by the tuple S, A i , T i k , R i k , where for all (s, a, s ) ∈ S × A i × S,

Figure 2 :

 2 Figure 2: Small stochastic game

b Q 2 k

 2 (0, b) that is action 1. 2. step k + 1: the process reaches state 1, agent 2 updates its Q-values, Q 2 k+1 (0, 1) = (1 -0.6) * 4.74 + 0.6 * (0 + 0.9 * 5.26) = 4.74 = Q 2 k (k + 2: the process returns to state 0, agent 2 updates its Q-values, Q 2 k+2 (1, 1) = (1 -0.6) * 5.26 + 0.6 * (1 + 0.9 * 4.74) = 5.26 = Q 2 k (1, 1),

b Q 2 k

 2 (0, b) that is action 1. 2. step k + 1: the process state is 0 again, agent 2 updates its Q-values, Q 2 k+1 (0, 1) = (1 -0.6) * 4.74 + 0.6 * (0 + 0.9 * 4.74) = 4.46, (33) then, agent 1 does action 0 again and agent 2 chooses arg max b Q 2 k+1 (0, b) = 1

13 3 .

 3 instant k + 2: the process is still in state 0, agent 2 updates its Q-values,Q 2 k+2 (0, 1) = (1 -0.6) * 4.46 + 0.6 * (0 + 0.9 * 4.46) = 4.19,

The optimal action-value function is computed from a centralized point-of-view of the process.