A Ferreira

C Lopes

N Martin

S Lanceros-Méndez

F Vaz
email: fvaz@fisica.uminho.pt

Nanostructured functional Ti-Ag electrodes for large deformation sensor applications

Keywords: Stretchable electrodes, piezoresisitve sensors, GLAD, Ti-Ag thin films, polymer composites, PVDF, CNT

This paper reports on the development of thin film-based stretchable electrodes, suitable for different types of sensors. Columnar Ti-Ag thin films with a Ag content of 8 at.% were prepared by D.C. magnetron sputtering on carbon nanotube/poly(vinylidene fluoride) CNT/PVDF piezoresistive composites. GLancing Angle Deposition, GLAD, technique was used to change the typical normal columnar growth microstructure obtained by conventional sputtering, into different growing architectures, such as inclined columns and zigzag profiles, in order to tune mechanical and electrical responses of the materials. Three different incident angles of the particle flux, α = 40º, 60º and 80º, were used to deposit Ti-Ag thin films with the different architectures. Upon uniaxial stretching of the prepared zigzag thin films, the resistance of the thin film starts increasing smoothly for strains up to 3%. Above 10% strain, a sharp increase of the electrical resistance is observed due to film mechanical failure and therefore interruption of the electrical conductivity pathways. Furthermore, the influence of the thin film architecture was also studied with respect to the performance of piezoresistive sensors based on carbon nanotube/poly(vinylidene fluoride), CNT/PVDF, composites in which Ti-Ag coated films served as electrodes for signal acquisition. Electromechanical tests were thus performed in composites with CNT contents close to the percolation threshold, where the electromechanical response, characterized by the Gauge Factor, is the largest. The stability of the piezoresistive response was analyzed for the various architectures of the GLAD sputtered Ti-Ag electrodes, including incident angle and number of zigzag periods. It is shown that thin film architecture has a pronounced influence in the overall sensor response, where the best results are obtained for piezoresistive polymer composites coated with Ti-Ag films, produced with intermediate (α = 60º) incident angles.

A c c e p t e d M a n u s c r i p t

Introduction

In the fields of sensing and actuating devices [START_REF] Pham | Processing and modeling of conductive thermoplastic/carbon nanotube films for strain sensing[END_REF][START_REF] Li | Sensors and actuators based on carbon nanotubes and their composites: A review[END_REF] the use of polymer based materials allows to develop smart materials and functional composites by the production of conductive polymer composites, using small amounts of carbon nanotubes -CNT -dispersed in an insulating polymer matrix. In particular, composite materials can be developed with the ability to change significantly the electrical response when subjected to strains, which is suitable for the development of high sensitive polymer-based strain sensors [START_REF] Pham | Processing and modeling of conductive thermoplastic/carbon nanotube films for strain sensing[END_REF][START_REF] Li | Sensors and actuators based on carbon nanotubes and their composites: A review[END_REF][START_REF] Ferreira | Relationship between electromechanical response and percolation threshold in carbon nanotube/poly(vinylidene fluoride) composites[END_REF]. However, one of the critical issues of these sensors is the reliability of the electrodes, which link the responsive polymer composite to the signal acquisition circuit. This is particularly challenging given the relatively high and complex mechanical solicitation expected for these applications, i.e. bending, elongation and torsion. In fact, these sensors must be reliable and retain reproducibility and structural integrity over their lifetime. Furthermore, corrosive and mechanical failures must not occur. Thus, these materials, though not selected exclusively at the base of their mechanical and chemical properties, must provide adequate mechanical and chemical resistance that arise in any given application. Several technologies have been proposed to develop suitable electrodes for large strain sensors, including the use of intrinsic conductive polymers [START_REF] Deshpande | Studies on conducting polymer electroactive paper actuators: effect of humidity and electrode thickness[END_REF][START_REF] Richardson-Burns | Polymerization of the conducting polymer poly(3,4-ethylenedioxythiophene) (PEDOT) around living neural cells[END_REF], pre-stressed metal conductors [START_REF] Wagner | Electronic skin: architecture and components[END_REF]7] or in plane patterned metal conductors [START_REF] Gray | High-Conductivity Elastomeric Electronics[END_REF][START_REF] Pelrine | High-field deformation of elastomeric dielectrics for actuators[END_REF]. Metals can be deposited in thin layers on a broad range of substrates by electron beam evaporation, cathodic sputtering or electroplating and patterned down to the nm scale using photolithographic processes [START_REF] Gonzalez | Design of metal interconnects for stretchable electronic circuits[END_REF]. These processes are the best options to realize these electrodes die to their large electrical conductivity and relatively low cost, the main challenge remaining to maintain the integrity of the signal acquisition electrodes for larger deformations and repeated loading cycles. Further, reproducible results at a large production throughput must be obtained with the potential of moving the technology from the lab to the industry. The ability to pattern the electrodes on a small scale allows the fabrication of many electrically independent sensors and/or actuators on the same coating process, which paves the way for a broad range of novel applications.

In order to produce such electrodes, there are two major obstacles to the direct use of metallic 1. the Young modulus of metals is some orders of magnitude higher than that of polymers (50-100 GPa compared to 0.2-1 MPa) [START_REF] Rosset | Flexible and stretchable electrodes for dielectric elastomer actuators[END_REF];

2. the limit of elasticity for metals is around 2% and if a metal electrode is strained above this limit it will crack and strongly reduce the electrical conductivity [START_REF] Rosset | Flexible and stretchable electrodes for dielectric elastomer actuators[END_REF].

Beyond the specific nature and characteristics of the chosen smart polymer based sensing material, the approach reported in this work consists in using a sputtered conductive thin layer to detect the strain-induced electric signal produced by the reversible mechanical deformation in the polymer composite. The selected layer system should reveal high corrosion and wear resistance, high conductivity and high elasticity (deformation resistance) and, additionally, good chemical, thermal and mechanical stability. Therefore, the metallic film to coat the polymeric sensor, as well as the production method, should be carefully selected. Based on previous works [START_REF] Lopes | TiAgx thin films for lower limb prosthesis pressure sensors: Effect of composition and structural changes on the electrical and thermal response of the films[END_REF][START_REF] Gonçalves | Structural and morphological evolution in TiAgx thin films as a function of in-vacuum thermal annealing[END_REF] and given the large potential of these materials in the biomedical field, the Ti-Ag system was chosen to coat the polymers. Ti-Ag thin films combine the excellent Ti biocompatibility with the Ag antimicrobial properties, offering good thermal, electrical, chemical and mechanical properties, together with good wear and corrosion resistance [START_REF] Ewald | Antimicrobial titanium/silver PVD coatings on titanium[END_REF][START_REF] Takahashi | Grindability and mechanical properties of experimental Ti-Au, Ti-Ag and Ti-Cu alloys[END_REF][START_REF] Kikuchi | Machinability of Experimental Ti-Ag Alloys[END_REF].

Concerning the thin film preparation, it is known that the microstructure of the films strongly depends on the experimental parameters used during film deposition [START_REF] Thornton | The microstructure of sputter-deposited coatings[END_REF][START_REF] Messier | Revised structure zone model for thin film physical structure[END_REF][START_REF] Petrov | Microstructural evolution during film growth[END_REF][START_REF] Mahieu | Biaxial alignment in sputter deposited thin films[END_REF]. In conventional Physical Vapor Deposition (PVD) techniques, the normal incidence of the particle flux leads to a typically columnar growth normal to the substrate. Offering strong benefits comparatively to the conventional sputtering techniques, the GLancing Angle Deposition technique (GLAD), first reported in 1959 [START_REF] Knorr | Dependence of Geometric Magnetic Anisotropy in Thin Iron films[END_REF], is a suitable way to modify the microstructural aspects of the thin film and, indirectly the physico-chemical properties. Indeed a wide range of morphologies can be tailored by combining oblique incidence of the depositing species and substrate motion. This work reports on how the evolution of the morphological features of the GLAD sputtered Ti-Ag thin films can affect its electrical, mechanical and electromechanical responses, as they will influence sensor response and reliability. The CNT/PVDF piezoresisitve composites were prepared following the procedure described in [START_REF] Ferrreira | Electromechanical performance of poly(vinylidene fluoride)/carbon nanotube composites for strain sensor applications[END_REF]. In short, the appropriate amount of CNT, (Single Walled CNT, SWCNT, AP-SWNT grade) were purchased from Carbon Solutions Inc., Riverside, California, was mixed with 15 to 20 mL of acetone and immersed in an ultrasound bath. Separately, PVDF was manually dispersed in acetone and then added to the SWCNT/acetone dispersion, in an ultrasound bath [START_REF] Bottino | Solubility parameters of poly(vinylidene fluoride)[END_REF]. The total mass of PVDF and CNT sample was approximately 11 g. A mechanical stirrer was inserted into the acetone dispersion and sonication and mechanical stirring were applied until the acetone was completely evaporated. The resulting material was cut into small pellets and pressed at 2 Tons and 200 ºC for 1 h. The material was let to cool down inside a mould.

The nonpolar α-phase was obtained by crystallization from the melt. Homogeneous discs, with diameters of 130 mm, thicknesses of 1 mm and CNT filler contents between 0 (blank samples -just PVDF -to serve as a reference in the thin film conductivity measurements) and 10 wt.% were obtained.

Ti-Ag thin films

Ti-Ag thin films were deposited by D.C. reactive magnetron sputtering inside a stainless-steel custom-made vacuum reactor with a volume of 40 L. The reactor, equipped with a circular planar and water cooled magnetron sputtering source, was evacuated with a turbomolecular pump, backed by a mechanical pump, in order to obtain an ultimate pressure of 10 -5 Pa. A titanium target (purity 99.6 at.%, 51 mm diameter) was used and 11 inserts of silver (purity 99.9 at.%, 2 mm diameter) were placed equidistant from each other, within the preferential erosion zone of the target. This amount of pellets was used to obtain a Ag amount between 5 and 10 at.%, which was found to be in a good composition range for the present large deformation sensor applications [START_REF] Lopes | TiAgx thin films for lower limb prosthesis pressure sensors: Effect of composition and structural changes on the electrical and thermal response of the films[END_REF][START_REF] Gonçalves | Structural and morphological evolution in TiAgx thin films as a function of in-vacuum thermal annealing[END_REF]. The composite target was sputtered under a pure argon atmosphere, with a constant flow rate of 2.4 sccm, corresponding to a total pressure of 0.3 Pa. The pumping speed was set constant at S = 10 Ls -1 . Before each deposition, the CNT/PVDF samples were cleaned with ethanol and introduced through a 1 L airlock. In order to remove the target surface contamination layer, a pre-sputtering of the composite target was performed for 5 min. Finally the samples were positioned at 50 mm from the target and grounded. The depositions were carried out at room temperature and the Ti-Ag composite target powered with a constant current density of 24.5 A.m -2

. The deposition time was adjusted in order to obtain a thickness range between 400 nm and 900 nm. There is a linear dependence between film thickness and deposition time, which was previously studied by the determination of the deposition rate for each one of the individual film architecture, described below. All the sputtering parameters were optimized taking into account the strong changes in the mechanical behaviour of the polymer that occurs at ~ 90ºC [START_REF] Mano | Dynamic mechanical analysis and creep behaviour of β-PVDF films[END_REF].

The composition of the prepared films was measured by Rutherford Backscattering Spectrometry (RBS). The measurements were carried out using a 4 He with 2 MeV and a 1 H with 2.3 MeV beams, at an angle of incidence 0º. Three detectors were used, one standard located at 140º, and two pin-diode detectors located symmetrical each other, both at 165º.

Composition profiles for the as-deposited samples were determined using the software NDF [START_REF] Barradas | Simulated annealing analysis of Rutherford backscattering data[END_REF][START_REF] Barradas | RBS/simulated annealing analysis of ironcobalt silicides[END_REF]. The error associated to the Ag concentration was about 0.5 at.%, according to the resolution of this technique. Four different types of films were grown in order to correlate the growth conditions (conventional and zigzag approaches) and the specific features of the GLAD-like prepared films with the response of the thin films and piezoresisitive composites. Figure 1 shows a schematic illustration of the different prepared films and their main microstructural features.

PVD techniques use normal incidence to obtain the typical columnar growth normal to the deposition substrate, Fig. 1a). With adequate operating conditions, GLAD technique allows obtaining columnar microstructures with specific architectures by controlling the orientation of the substrate relative to the impinging vapor flux, as illustrated in Fig. 1b), 1c) and 1d). In the observed columns, when the incident angles of the particles flux α increase with respect to the sample surface, the angle β of the column with respect to the sample surface, increases the same way.

Electrical resistance measurements

Two different electrical conductivity measurements were performed in the samples. Electrical resistance of the CNT/PVDF composites was calculated from the slope of I-V curves, measured at room temperature with an automated Keithley 487 picoammeter/voltage source.

I-V data points were collected between Au contacts, deposited on both sides of the samples with a Polaron SC502 sputter coater. Volume resistivity was measured with circular contacts of 5 mm diameter with an applied voltage ranging between ±10 V and measuring the current.

The resistivity ρ (Ωm) was calculated by [START_REF] Costa | Mechanical, electrical and electro-mechanical properties of thermoplastic elastomer styrenebutadiene-styrene/multiwall carbon nanotubes composites[END_REF]:

d A R. = ρ (1)
where R is the resistance of the composite (Ω), d the thickness (m) and A the area of the electrodes (m 2 ).

Second, the electrical conductivity of Ti-Ag thin films was measured at room temperature, using the four-probe van der Pauw method [START_REF] Pauw | A method of measuring specific resistivity and hall effect of discs of arbitrary shape[END_REF][START_REF] Pauw | A method of measuring the resistivity and hall coefficient on lamellae of arbitrary shape[END_REF]. The measurements were carried out in a custom-made dark chamber. The error associated to the electrical measurements is below 1%.

Electromechanical characterization

Electromechanical tests were performed considering the whole system: CNT/PVDF polymer coated with the Ti-Ag thin films. The electrical resistance of the samples (approximate Two different mechanical solicitations were applied to the samples. During the so-called method 1, mechanical experiments were performed in the tensile mode (Fig. 2a); in the method 2, 4-point-bending deformation was applied to the samples (Fig. 2b). The evaluation of the electrical resistance response during the uniaxial stress tests (Fig. 1) was performed at speed rate of 0.5 mm/min and at a maximum strain level of 10%.

For the 4-point-bending measurements (Fig. 2b), the Ti-Ag electrodes with an area of 10×1 mm 2 , were placed at the bottom of the sample. For all experiments, 4 loading-unloading cycles were performed and the average electromechanical response was evaluated. All these experiments were carried out at room temperature.

A c c e p t e d M a n u s c r i p t 8

Morphological analysis

The morphological features of the Ti-Ag thin films was probed by scanning electron microscopy (SEM). Cross-section micrographs were obtained at room temperature in a FEI Quanta 400FEG ESEM apparatus operating at 15 keV. Additional information about surface properties (roughness and surface morphology) was obtained by atomic force microscopy (AFM), using a MultiMode STM microscope controlled by the Nanoscope III (tapping mode) system. The measurements were performed over surface scan areas of 5×5 μm 2 .

Results and discussion

Electrical properties of Ti-Ag electrodes

All prepared films were found to have a Ag content of about 8 at.%, measured by RBS. In order to study the electrical properties of the Ti-Ag electrodes sputtered by GLAD, electrical resistivity measurements at room temperature were carried out. The electrical behavior of the Ti-Ag thin films is presented in Fig. 3, where the influence of the different processing parameters -number of zigzag periods and sputter angles-was analyzed. The results plotted in Fig. 3 show that the films are characterized by suitable electrical conductivity for sensor electrode applications, with varying properties depending on the ) and thus adequate to be used as electrodes. Further, a slight enhancement of the electrical conductivity is observed for the lowest incident angles (α = 40º) and for the highest number of periods (Fig. 3), which is correlated with changes in the grain boundaries, in particular with the voids between the columnar structures. These voids are promoted as the incident angle increases and therefore the column angle β increases [START_REF] Lintymer | Glancing angle deposition to modify microstructure and properties of sputter deposited chromium thin films[END_REF][START_REF] Lintymer | Glancing angle deposition to control microstructure and roughness of chromium thin films[END_REF].

The effects of Ag additions to a stoichiometric TiN matrix has been studied [START_REF] Pedrosa | Electrical characterization of Ag:TiN thin films produced by glancing angle deposition[END_REF] and it is reported that for intermediate Ag contents (between ~6 and ~20 at.%), highly conductive Ag particles are placed among the TiN columns, providing an increased number of conduction paths. Further, in the case of the inclined features, the increase of both and angles give rise to increased porosity [START_REF] Rauch | Metal-to-dielectric transition induced by annealing of oriented titanium thin films[END_REF]. Thus, scattering at the column's interface is favoured, which reduces the electronic transport properties of the coatings [START_REF] Rauch | Metal-to-dielectric transition induced by annealing of oriented titanium thin films[END_REF]. Additional parameters such as temperature (T), film thickness (d), grain size (D) and the mean free path of the electrons in the film (λ e ) also affect the electrical conductivity ( ) of the metallic thin films [START_REF] Lintymer | Glancing angle deposition to modify microstructure and properties of sputter deposited chromium thin films[END_REF]. These parameters are also correlated with changes in the grain boundaries, mainly in the column frontiers, which behave as a potential barrier, which decreases the probability of the electron transmission [START_REF] Lintymer | Glancing angle deposition to modify microstructure and properties of sputter deposited chromium thin films[END_REF]. Thus, the variations in the electrical conductivity are mainly due to the modifications on the film's architecture and growing conditions. As demonstrated in [START_REF] Mayadas | Electrical-Resistivity Model for Polycrystalline Films: the Case of Arbitrary Reflection at External Surfaces[END_REF], the major contribution to the total resistivity comes from electron scattering at grain boundaries and therefore to the significant modifications of the film's morphology.

Electrical behaviour of Ti-Ag films under uniaxial stretching

To minimize the overall stiffness of the sensors, materials for both the matrix and the electrically active components should have low Young modulus and an ability to accommodate large strain deformations with a linear, elastic response. Thus, mechanical response and electrical transport properties are important.

Regarding the thin films prepared within the frame of this work, the electrical resistance for deformations up to 10% along the axial direction of the incident angle are shown in Fig. 4.

a) b)

A c c e p t e d M a n u s c r i p t The results plotted in Fig. 4 reveal two very distinct behaviors. On the one hand, the thin films deposited in the conventional way (α = 0º) show a very poor resistance to stretching, with the electrical resistance increases sharply after the application of the deformation. As shown in Fig. 4, upon uniaxial stretching, the samples deposited in conventional approach (α = 0º) reveal that the resistance starts increasing immediately after the stretching started, which demonstrates its inadequacy for the targeted sensor applications. This undesirable behaviour is actually expected as demonstrated in [START_REF] Pelrine | High-field deformation of elastomeric dielectrics for actuators[END_REF][START_REF] Rosset | Flexible and stretchable electrodes for dielectric elastomer actuators[END_REF], where electrodes produced with conventional sputtering deposition resulted in the smallest strain range before loss of conductivity, which was limited to ε = 3%. At 1% strain, cracks started to appear perpendicularly to the stretch direction, and the cracks became wide enough to completely interrupt the conducting path for strains of 3%. On the other hand, to solve this limitation, patterning metal traces can be used [START_REF] Pelrine | High-field deformation of elastomeric dielectrics for actuators[END_REF][START_REF] Gonzalez | Design of metal interconnects for stretchable electronic circuits[END_REF][START_REF] Sluis | Stretching-induced interconnect delamination in stretchable electronic circuits[END_REF]. When carefully designed, the patterned electrode still allows for the polymer to move and expand in the desired direction without damaging the metallic thin-film.

For the prepared zigzag structures, the resistance starts increasing only for strain ranging from 2 to 3% (Fig. 4). Furthermore, and even for the higher strain, the surface resistance increases smoothly, mainly due to a geometrical effect, demonstrating the large difference with respect to the conventional deposited films. A sharp increase of the electrical resistance occurs only above 10% strain, indicating electrical conductivity failure due to film damage (Fig. 4).

The structures with 2 periods (4 zigzags) presented in Fig. 4b) show no relevant variations of the electrical resistance for strains of ~ 4% for an incident angle of 40º. On the other hand,

A c c e p t e d M a n u s c r i p t the resistance of the samples prepared with α = 60º show variations of the electrical resistance for stretching around 3%. However, it is worth to note that these samples also showed a better strain distribution, with just a small increase of resistance up to 10% strain, allowing their use for high strain sensor applications. Failure is expected in regions where the highest plastic strain concentration is located [START_REF] Pelrine | High-field deformation of elastomeric dielectrics for actuators[END_REF][START_REF] Rosset | Flexible and stretchable electrodes for dielectric elastomer actuators[END_REF]. In a general way, an increase of the incident angle and the number of zigzags promotes a reduction in the accumulated strain (Fig. 3).

Morphological analyses of Ti-Ag films

In order to reduce even more the strain in the metal conductor, without sacrificing the electrical performance and/or changing the amplitude or period of the design, the obtained results show that the number of zigzags can be further optimized (increased), increasing their number with several periods of smaller thickness or even with periods of varying thicknesses. This ''multi trace" films may improve the stretchability and reduce the induced stresses [START_REF] Rauch | Metal-to-dielectric transition induced by annealing of oriented titanium thin films[END_REF].

Figure 5 shows the cross-section images of the sputtered GLAD samples, where all the films seem to exhibit a typical columnar microstructure. The tilting of columns increases with the incident angle α. Nonetheless, the incident angle α and the column angle β are not equal due to shadowing effects [START_REF] Lintymer | Glancing angle deposition to modify microstructure and properties of sputter deposited chromium thin films[END_REF][START_REF] Lintymer | Glancing angle deposition to control microstructure and roughness of chromium thin films[END_REF]. As the total film thickness was kept approximately constant, with increasing number of zigzag periods, the single period thickness decreases. For an incident angle α = 40°, the obtained inclined (1/2 period zigzag) and zigzag architectures (1 and 2 periods) exhibit a weakly distinguishable columnar structure. The column angle β cannot be accurately determined for any zigzag period. It is in agreement with the quite dense structure typically observed in GLAD thin films prepared with incident angles lower than 60°. The shadowing effect is not relevant enough for incident angles lower than 60°. The oriented growth is favoured but insufficiently to produce a clear defined cross section morphology [START_REF] Lintymer | Glancing angle deposition to modify microstructure and properties of sputter deposited chromium thin films[END_REF][START_REF] Lintymer | Glancing angle deposition to control microstructure and roughness of chromium thin films[END_REF][START_REF] Pedrosa | Electrical characterization of Ag:TiN thin films produced by glancing angle deposition[END_REF]. For incident angles α higher than 60°, inclined as well as zigzag columns are better viewed. The column angle is β = 40° and 45° (for any zigzag period) for a corresponding incident angle α = 60° and 80°, respectively. These close β values are expected within the GLAD sputtering process due to the dispersion of sputtered particles (the latter do not have a ballistic trajectory because of the sputtering pressure required to maintain the plasma). As a result, the β angle tends to saturate in spite of an increase of the incident angle and the films do not exhibit significant changes of their cross section morphology. In addition, with increasing the incident angle from 0º to a maximum of 80º, the structures become less dense and compact and an enhancement of the inter-columnar spacing is These results show the variations in the grain boundaries, mainly in the column frontiers which decreases the probability of the electron conduction [START_REF] Lintymer | Glancing angle deposition to modify microstructure and properties of sputter deposited chromium thin films[END_REF] and consequently decreases the electrical conductivity.

AFM was used to characterize the morphology and surface roughness of the Ti-Ag samples with a scan area 5×5 μm. The influence of this α angle on the surface roughness is represented in Table 1. Figure 6 and table 1 show that the surface of the samples prepared with an angle of deposition α = 60º are the smoother ones with a rms roughness of 5.8 nm. The statistical mean roughness of the surface is about 3.5 nm, while the maximum height is about 73.1 nm.

The results show maximum roughness for the samples prepared with α = 40º and α = 80º and therefore there is no relation between surface roughness and electromechanical response (Fig. 4b) but the latter is fully determined by the column angle.

Electromechanical response of the films

The electrical and piezoresistive response of carbon nanotube/poly(vinylidene fluoride) composites has been reported in [START_REF] Ferrreira | Electromechanical performance of poly(vinylidene fluoride)/carbon nanotube composites for strain sensor applications[END_REF]. The observed electrical and electromechanical responses are in accordance with the framework of the percolation theory. The piezoresisitive response, quantitatively analysed by the gauge factor, is maximized at concentrations around the percolation threshold. In this region, the deformation of the composites induces strong and reversible variations in the CNT network and therefore in the electrical response. The maximum value of the gauge factor is 6.2 and the linearity of the response over a wide strain range shows the viability of these materials to be used as piezoresistive sensors. In the same A c c e p t e d M a n u s c r i p t 14 way, the piezoresisitive response is stable with the number of cycles and reversible up to temperatures below 100 ºC [START_REF] Ferrreira | Electromechanical performance of poly(vinylidene fluoride)/carbon nanotube composites for strain sensor applications[END_REF].

In this study, electromechanical tests on the Ti-Ag coated carbon nanotube/poly(vinylidene fluoride) composites were performed on composites with the same percentage of CNT (3 wt.%.), i.e. around the percolation threshold, where the GF is the largest [START_REF] Ferrreira | Electromechanical performance of poly(vinylidene fluoride)/carbon nanotube composites for strain sensor applications[END_REF]. In this way, it was analysed whether the structure of the electrodes influences the signal response of the transducers. For this purpose, two parallel rectangular Ti-Ag electrodes of 6 mm width and 1 mm distance between them were coated onto one of the samples sides. From Fig. 7d) one can observe that loading and unloading curves do not coincide during two successive cycles, given evidence of a mechanical hysteresis in these composites. The mechanical hysteresis in the composite decreases with increasing number of cycles, in particular for the first few cycles.

The increasing of the incident and column angles (α and β, respectively), from α = 0º to α = 60º, as well as the number of zigzag periods enhances the electromechanical response.Above an incident angle of 60 ºC there is a divergence between the loading and unloading cycles, due to strong changes in the mechanical behaviour of the Ti-Ag films, leading to a very poor resistance to stretching as shown in Fig. 3. These results show that the electrode structure has a pronounced influence on the electrical conductivity response of the polymer composite (e.g.

variations on the resistivity) and therefore in the performance of the sensor.

As shown in Fig. 7d) the electrical resistance changes fairly linearly with the applied strain and that the linearity is maintained for the different cycles and for the different samples. The curves were thus fitted by linear regression. The GF is defined as the ratio of fractional change in electrical resistance to the fractional change in length (strain) [START_REF] Beeby | MEMS mechanical sensors[END_REF]:

GF = ΔR / R Δl / l (2)
In equation 2, R is the steady-state material electrical resistance before deformation and ΔR is the resistance change caused by the variation in length Δl [START_REF] Beeby | MEMS mechanical sensors[END_REF]. The quantity l represents the length of the sample. The resistance change under strain results from the contribution of the dimensional change -geometrical effect ΔR D -and from the intrinsic piezoresistive effect ΔR l . For the surface mode measurements (Fig. 2b) the GF can be written as [START_REF] Beeby | MEMS mechanical sensors[END_REF]:

GF = ΔR / R ε = ΔR D + ΔR l = (1+υ) + dρ / ρ ε (3)
where, ε=Δl/l, υ is the Poisson ratio and is the electrical resistivity.

The slope of the linear fit with equation is presented in table 2.

A c c e p t e d M a n u s c r i p t 16 2), show a strong intrinsic contribution of the CNT/polymer composite to the GF for the films prepared with α = 60º and roughly negligible for α = 80º, as observed by comparison with the value of GF ~ 1.35 calculated from just geometrical factors. Further, the α = 40º films show a strong intrinsic contribution from the electrodes themselves, as can be observed by maximum values of the GF obtained for these polymer composites with non-piezoresistive gold film, Table 3, data from [START_REF] Ferrreira | Electromechanical performance of poly(vinylidene fluoride)/carbon nanotube composites for strain sensor applications[END_REF]. For the samples prepared with gold films and concentrations above 3 wt.% CNT, the geometric factor is the dominant one, but just below 2 wt.% CNT loading, the intrinsic contribution to the GF is dominant. In the case of the Ti-Ag films, the change in conductivity induces strong variation of the response of the sensors due to their varying electrical response, which superimposes the variation of the piezoresistive composite [START_REF] Knorr | Dependence of Geometric Magnetic Anisotropy in Thin Iron films[END_REF][START_REF] Shokuhfar | Low-cost polymeric microcantilever sensor with titanium as piezoresistive material[END_REF]. It can be further stated that whereas the electromechanical signal is mainly due to the polymer sensing A c c e p t e d M a n u s c r i p t element for electrodes prepared with α = 60º and 80º, the strong variations in resistivity under mechanical solicitation for the sample prepared with α = 40º is ascribed to variation in the electrode itself. Upon stable response over varying cycles, the results shows a promising way to use the films as piezoresistive sensors themselves because the piezoresistive effects of the polymer material with non-piezoresistive gold had been studied [START_REF] Ferrreira | Electromechanical performance of poly(vinylidene fluoride)/carbon nanotube composites for strain sensor applications[END_REF], and the response of the piezoresistive films can be extrapolated by comparison. This is correlated with changes in the grain boundaries, mainly in the column frontiers which promote the tunneling resistance change [START_REF] Lintymer | Glancing angle deposition to modify microstructure and properties of sputter deposited chromium thin films[END_REF]. The variation of the conductivity with angle α is mainly due to significant modifications of the film's morphology. The obtained values are reasonable for these types of composites; however, denser and compact structures with smoother surfaces showed a good strain distribution coupled with appropriate electrical conductivity, favoring the electromechanical response of the coated polymer. The best results were obtained when the polymer was coated with Ti-Ag films produced with intermediate incident angles.

Conclusions

Ti-Ag thin films were prepared with a systematic variation of the incident angle α = 40º, 60º and 80º and number of zigzag periods in order to be applied as electrodes in high strain piezoresistive polymer based composites based on CNT and PVDF. Upon uniaxial stretching, for the zigzag structures, the resistance starts increasing for strains up to 3 %, rising sharply for strains above 10 %, due to thin film mechanical and electrical failure. By increasing the number of zigzags, the change in conductivity of the Ti-Ag films induces strong variation of the response of the sensors due to their varying electrical response, which superimposes the variation of the response of the piezoresistive composite and the best results were obtained when the polymer was coated with intermediate incident angles (α = 60º). The results show that the electrodes structure has a pronounced influence on the overall sensor response leading to values of the GF up to 85 mainly due to the electromechanical contribution of the thin film, which stability has to be studied for potential use for sensor applications itself. NORTE-07-0124-FEDER-000037", co-funded by the "Programa Operacional Regional do

Acknowledgements

1 .

 1 Carbon nanotube/poly(vinylidene fluoride) piezoresisitive composites

A c c e p t e d M a n u s c r i p t 5

 5

Figure 1 -

 1 Figure 1 -Schematic representation of the thin film microstructural features.In order to study the change in the electromechanical response of the thin films, a set of different architectures were tailored by varying the direction of the incident particles flux.

A c c e p t e d M a n u s c r i p t 6

 6

  mm 2 and ~1 mm of thickness) was measured through the Ti-Ag electrodes with an Agilent 34401A multimeter during the mechanical deformation of the sample, applied with an universal testing machine from Shimadzu (model AG-IS, with a load cell of 1 kN).

Figure 2 -

 2 Figure 2 -Schematic representation of the experimental configuration of the a) clamps for the stress-strain uniaxial stress experiments (method 1) with simultaneous electrical measurements for electrical response evaluation of the samples and b) representation of the 4-point bending tests (method 2) apparatus where z is the vertical displacement, d is the thickness of the sample and a is the distance between the first and the second bending points (15 mm). The electrodes are in the center of the sample.

Figure 3 -

 3 Figure 3 -Electrical conductivity of Ti-Ag films as a function of the incident angle (α) and the number of periods, and electrical conductivity of polymer composite as a function of CNT (wt.%).

  A c c e p t e d M a n u s c r i p t 9 number of periods and, mainly, deposition angle. The Ti-Ag thin films exhibit conductivity values in the order of 10 5 S.m -1 , smaller than the bulk Ti around 10 6 S.m -1 [30], and several orders of magnitude higher than the polymer composite (10 -4 S.m -1

Figure 4 -

 4 Figure 4 -Electrical resistance as a function of the tensile strain ε of the sputtered Ti-Ag samples for the different incident angles α = 0, 40, 60 and 80° and geometries: a) 1 zigzag period; b) 2 zigzags periods.

A c c e p t e d M a n u s c r i p t 12 perceivableFigure 5 -

 125 Figure 5 -SEM cross-section micrographs of the sputtered Ti-Ag samples for incident angles α = 0, 40, 60 and 80° and ½, 1 and 2 zigzags periods.

A c c e p t e d M a n u s c r i p t 13

 13

Figure 6 -

 6 Figure 6 -AFM topographic images of sputtered Ti-Ag samples with 2 zigzag periods and for different incident angles: a) α = 40°; b) α = 60°; c) α = 80°.

Figure 7 -

 7 Figure 7 -Electromechanical response of samples prepared with 2 zigzag period Ti-Ag films deposited on PVDF substrates with 3 wt.% CNT. The z-deformation is 1 mm and the deformation velocity is 0.5 mm/min at room temperature. The incident angle is a) α = 40°; b) α = 60°, c) α = 80° and d) representative resistance variation vs. strain curves and the corresponding fit for the determination of the Gauge Factor for the sample with α = 60º.

  This work was supported by FEDER through the COMPETE Program and by the Portuguese Foundation for Science and Technology (FCT) in the framework of the Strategic Project PEST-C/FIS/UI607/2014 and the project Matepro -Optimizing Materials and Processes", ref.

Figure 1 -

 1 Figure captions

Figure 2 -

 2 Figure 2 -Schematic representation of the experimental configuration of the a) clamps for the stress-strain uniaxial stress experiments (method 1) with simultaneous electrical measurements for electrical response evaluation of the samples and b) representation of the 4point bending tests (method 2) apparatus where z is the vertical displacement, d is the thickness of the sample and a is the distance between the first and the second bending points (15 mm). The electrodes are in the center of the sample.

Figure 3 -

 3 Figure 3 -Electrical conductivity of Ti-Ag films as a function of the incident angle (α) and the number of periods, and electrical conductivity of polymer composite as a function of CNT (wt.%).

Figure 4 -

 4 Figure 4 -Electrical resistance as a function of the tensile strain ε of the sputtered Ti-Ag samples for the different incident angles α = 0, 40, 60 and 80° and geometries: a) 1 zigzag period; b) 2 zigzags periods.

Figure 5 -

 5 Figure5-SEM cross-section micrographs of the sputtered Ti-Ag samples for incident angles α = 0, 40, 60 and 80° and ½, 1 and 2 zigzags periods.

Figure 6 -

 6 Figure 6 -AFM topographic images of sputtered Ti-Ag samples with 2 zigzag periods and for different incident angles: a) α = 40°; b) α = 60°; c) α = 80°.

Figure 7 -

 7 Figure 7 -Electromechanical response of samples prepared with 2 zigzag period Ti-Ag films deposited on PVDF substrates with 3 wt.% CNT. The z-deformation is 1 mm and the deformation velocity is 0.5 mm/min at room temperature. The incident angle is a) α = 40°; b) α = 60°, c) α = 80° and d) representative resistance variation vs. strain curves and the corresponding fit for the determination of the Gauge Factor for the sample with α=60º.

A c c e p t e d M a n u s c r i p t 23 Hilights-

 23 Thin films prepred with specific architectures (columns and zigzag profiles), carried out by Glancing Angle Deposition, GLAD -The influence of thin film architectures were correlated with respect to the performance of piezoresistive sensors, based on carbon nanotube/poly(vinylidene fluoride), CNT/PVDF, composites -Electromechanical tests showed a behaviour that not corresponds to required response in pressure sensors but also a very different result when compared to conventional-like deposited thin films -Thin film architectures have pronounced influence in the overall sensor response.

Table 1 :

 1 Surface roughness of the Ti-Ag films prepared with different incident angles of deposition and 2 zigzag periods.

	Sample	Mean square roughness (R q ) Nm	Mean roughness (R a ) nm	Max height (R max ) nm
	α = 40º	8.4	6.7	61.7
	α = 60º	5.8	3.5	73.1
	α = 80º	6.8	5.1	86.6

Table 2 :

 2 GF values resulting of the linear fit of ΔR/R as function of stress ε for samples with 2 zigzags and PVDF substrates with 3 wt.% CNT.From Solef®PVDF datasheet, the Poisson ratio of PVDF is 0.35 at room temperature, which means that the geometric effect contribution to GF is around 1.35. Therefore, the obtained values of the GF, that are above this value (Table

	Angle	GF	Standard Error
	α = 40º	85	2
	α = 60º	2.88	0.01
	α = 80º	1.44	0.05

Table 3 :

 3 GF values resulting of the linear fit of ΔR/R as function of stress ε for samples with non-piezoresistive

	gold and PVDF substrates with CNT [22].
	CNT (wt.%)	GF	Standard Error
	1	2.63	0.19
	1.3	3.75	0.09
	1.7	6.18	0.30
	2	4.84	0.07
	3	1.54	0.18
	7	1.13	0.01
	10	1.70	0.18

Norte" (ON.2 -O Novo Norte), under the "Quadro de Referência Estratégico Nacional" (QREN), through the "Fundo Europeu de Desenvolvimento Regional" (FEDER). The authors also thank FCT for financial support under project PTDC/CTM-NAN/112574/2009. AF thanks the FCT for grant SFRH/BD/69796/2010.


Andre Naz
email: andre.naz@femto-st.fr

Benoit Piranda
email: benoit.piranda@femto-st.fr

Seth Copen Goldstein

Julien Bourgeois
email: julien.bourgeois@femto-st.fr

André Naz

Benoît Piranda

A distributed self-reconfiguration algorithm for cylindrical lattice-based modular robots

Keywords: Distributed algorithm, Selfreconfiguration algorithm, Modular robotic, Programmable Matter, Ensembles

come   L'archive ouverte pluridisciplinaire

Introduction

Modular Self-reconfigurable Robots (MSR) [START_REF] Yim | Modular self-reconfigurable robot systems [grand challenges of robotics[END_REF] are distributed robotic systems composed of independent connected modules which are able to collaborate and coordinate their activities in order to achieve common goals. Every module has its own computation and communication capabilities, sensors and actuators. MSR have a wide range of potential applications. This work is part of the Claytronics project [START_REF] Goldstein | Claytronics: An instance of programmable matter[END_REF][START_REF] Bourgeois | Programmable matter as a cyber-physical conjugation[END_REF] in which we envision massivescale MSR, composed of up to millions of modules, to build programmable matter, i.e., matter that can change its physical properties under program control.

The most used algorithm in MSRs is the selfreconfiguration algorithm which causes the modules to move from one configuration (the initial shape) to another one (the goal shape) (see Figure 1). Self-reconfiguration has several applications. In the context of programmable matter, it enables an MSR to assume different shapes. Self-reconfiguration can also be used to adapt MSR to changes in the environment or to specific tasks. For instance, in [START_REF] Lakhlef | Distributed and dynamic map-less selfreconfiguration for microrobot networks[END_REF], the authors use the self-reconfiguration to rearrange modules connectivity in order to reach an optimal network topology.

Figure 1: Example of initial and goal shapes. Selfreconfiguration is the process during which the initial clump of modules on the left self-reconfigures into the car shape on the right.

Self-reconfiguration algorithms pose several challenges. Firstly, planning is challenging as the number of possible unique configurations is huge: (c • w) n where n is the number of modules, c the number of possible connections per module and w the ways of connecting the modules together [START_REF] Park | Automatic configuration methods in modular robots[END_REF]. Depending on the physical constraints, modules can often move concurrently which makes the configuration space grow at the rate of O(m n ) with m the number of possible movements and n the number of modules free to move [START_REF] Barraquand | Robot motion planning: A distributed representation approach[END_REF]. The exploration space for reconfiguration between two random configurations is therefore exponential in the number of modules which prevents finding a complete optimal planning for all but the simplest configurations. The optimal self-reconfiguration planning for chain-type MSRs is then an NP-complete problem [START_REF] Hou | Graph-based optimal reconfiguration planning for self-reconfigurable robots[END_REF], and, to the best of our knowledge, nothing has been proved so far for lattice-based MSR. Secondly, in addition to the path planning problem, the self-reconfiguration process is also challenging as it is a distributed process that requires distributed coordination of mobile autonomous modules connected in time-varying ways. In particular, modules have to coordinate their motions in order to not collide with each other.

Self-reconfiguration algorithms are tailored for a specific class of modular robots, with specific motion constraints [START_REF] Stoy | Current topics in classic self-reconfigurable robot research[END_REF], for example using cubes sliding on the floor, some motions need a cooperation process that complicates motion algorithms [START_REF] Piranda | A distributed algorithm for reconfiguration of lattice-based modular self-reconfigurable robots[END_REF]. In this paper, we base our model on the millimeter-scale cylindrical robots [START_REF] Mustafa Emre Karagozler | Stress-driven mems assembly + electrostatic forces = 1mm diameter robot[END_REF][START_REF] Emre | Design, Fabrication and Characterization of an Autonomous, Sub-millimeter Scale Modular Robot[END_REF] (see Figure 2), called 2D Catoms, developed in our project. Catoms are the basic unit for Claytronics. 2D Catoms have been partially validated with the realization of a hardware prototype. In this paper, we assume 2D Catoms can communicate together using neighbor-toneighbor communications and move by rolling around each other as long as they respect some motion constraints (see section 2).

Figure 2: The 2D Catom. A fabricated prototype (on the left) and the actuation scheme (on the right) [START_REF] Mustafa Emre Karagozler | Stress-driven mems assembly + electrostatic forces = 1mm diameter robot[END_REF].

The contribution of this paper is to propose the Cylindrical-Catoms Self-Reconfiguration (C2SR) algorithm which is asynchronous, deterministic, fully decentralized and able to manage almost any kind of initial and goal compact shapes (see section 4). Although our work is focused on the algorithm, we carry out our analysis with respect to hardware constraints based on the 2D Catoms prototype developed in [START_REF] Mustafa Emre Karagozler | Stress-driven mems assembly + electrostatic forces = 1mm diameter robot[END_REF][START_REF] Emre | Design, Fabrication and Characterization of an Autonomous, Sub-millimeter Scale Modular Robot[END_REF]. C2SR is a step toward realizing programmable matter.

We implemented our algorithm in C++ and evaluated it through simulations with our simulator, Visi-bleSim [START_REF] Dhoutaut | Efficient simulation of distributed sensing and control environments[END_REF][START_REF] Piranda | Visiblesim: Your simulator for programmable matter[END_REF]. We show the effectiveness of C2SR on large-scale ensembles composed of up to ten thousands of modules. We also show the effectiveness of our algorithm and study its performance in terms of communications, movements, and execution time. Our observations indicate that the number of communications, the number of movements and the execution time of our algorithm is predictable. Furthermore, its execution time appears to be linear in the size of the goal shape.

The rest of this paper is organized as follows. In section 2, we define the system model and assumptions. Afterwards, we discuss the related work in section 3. In section 4, we present the general idea of C2SR and in section 5, we describe its implementation. In section 6, experimental results are presented and analyzed. Section 7, concludes this paper and section 8 proposes some directions for future work.

System Model and Assumptions

In this paper, we consider the millimeter-scale cylindrical robots [START_REF] Mustafa Emre Karagozler | Stress-driven mems assembly + electrostatic forces = 1mm diameter robot[END_REF][START_REF] Emre | Design, Fabrication and Characterization of an Autonomous, Sub-millimeter Scale Modular Robot[END_REF] (see Figure 2), called 2D Catoms, developed in the Claytronics project. Some of the 2D Catoms functionalities have been validated using this prototype.

A 2D Catom consists of a 6-mm long and 1-mm diameter cylindrical shell. A high voltage CMOS die is attached inside the tube. The chip includes a storage capacitor and a simple logic unit. The tube has electrodes used for power transfer, communications and actuation. The power is spread from a powered floor through the ensemble using neighbor-to-neighbor power transfer.

We assume that 2D Catoms are organized into a horizontal pointy-topped hexagonal lattice where modules have up to six neighbors. Modules can communicate together using neighbor-to-neighbor communications. We assume that modules automatically discover their neighbors using communications after becoming attached. We assume that moving modules cannot communicate with any other module. p Ci = (x Ci , y Ci ) denotes the coordinates of the 2D Catom C i in the horizontal hexagonal lattice. p Ci .x denotes C i 's column in the lattice, while p Ci .y denotes C i 's height. For instance, in Figure 3, p C2 .y = 0 and p C9 .y = 2. We assume that, at any time, modules know both their coordinates in the lattice and the coordinates of their neighbor through an external algorithm, e.g., [START_REF] Funiak | Distributed localization of modular robot ensembles[END_REF] or a distributed and incremental version of [START_REF] Dermas | First evaluation of a system of positioning of microrobot with ultra-dense distribution[END_REF].

Moreover, a 2D Catom can roll CW or CCW around a stationary module. During an atomic move, a module rotates 60 • going from one cell of the lattice to its adjacent cell. We assume that a 2D Catom has only the capability to lift itself, it cannot carry or push other modules. A module can move if it satisfies the freedom of movement rule (see Rule 1).

Rule 1 (the freedom of movement rule) Because of possible mismatching issues due to physical constraints, a 2D Catom can only move from/into a cell if this cell is currently unoccupied and no two symetrically opposing cells adjacent to that cell are occupied (see Figure 3). Furthermore, we consider the floor as if it were filled with 2D Catoms. If a 2D Catom, C i , satisfies the freedom of movement rule, f ree(C i ) is true, otherwise it is false.

In the current design, a 2D Catom is able to perform a revolution in 1.67 seconds or 3.35 seconds [START_REF] Emre | Design, Fabrication and Characterization of an Autonomous, Sub-millimeter Scale Modular Robot[END_REF], which corresponds to an average speed of 1.88 mm • s -1 or 0.94 mm • s -1 . We assume that 2D Catoms are not provided with any hardware mechanism to handle collision. Thus, collisions have to be prevented by the selfreconfiguration algorithm, using communications. On the right, a labeled system: gray cells are occupied by a module whereas white cells are empty. Some of the empty cells are labeled with their position (e.g., p a , p b , etc.).

We use N K p to denote the set of modules geographically adjacent to position p. A module C i , moving from p Ci to p ′ Ci , is somewhere between these two positions, and thus, C i belongs to the set of geographically adjacent modules of all the cells adjacent to p Ci or p ′ Ci . For instance, in the labeled system depicted in Figure 3, module C 12 is moving and, thus it belongs to

N K pa , N K p b , N K p d , N K p C 12 , N K pe , N K p C 11 , N K p ′ C 12
, N K p f , N K pg and N K p h . Note that in the presence of moving modules, N K p C i may be different from N N Ci . Also notice that the construction of the N K sets is not automatic. 2D Catoms are not equipped with any presence sensor. Maintaining on Catoms the N K set of some specific nearby positions, using only communications, is one of the key operations in the implementation of our algorithm.

I and G respectively denote the initial and the goal shapes. We assume that every module stores a representation of the shape geometry of G. Our algorithm also assumes some admissibility conditions for I and G (see section 4).

In this paper, colors are used for illustration purposes only. The current prototype is not equipped with any mechanism to glow with color. It is possible to do so, but the weight of that color mechanism will probably change the 2D Catom motion speed.

Furthermore, we assume a failure-free environment, i.e., we assume there is no module, communication, move or lattice failure during the algorithm execution.

Related Work

Self-reconfiguration and self-assembly have attracted a lot of attention in the last two decades. Algorithms have been proposed for modules of different shapes, with different physical motion constraints and arranged in various ways. In this paper, we consider self-reconfiguration of 2D Catom systems, rolling elements organized in a vertical and two-dimensional hexagonal lattice. Algorithms also differ by their restriction on the initial and goal shapes. Our algorithm can manage almost any kind of initial and goal compact shapes (see section 4). Algorithms also vary in their control properties. In particular, they can be cen-tralized or distributed and synchronous or asynchronous. In this paper, we propose a distributed and asynchronous algorithm.

In [START_REF] Walter | Distributed reconfiguration of metamorphic robot chains[END_REF], the authors propose a distributed algorithm to perform chain-to-chain self-reconfiguration in a hexagonal lattice. Modules move in synchronous rounds. This work was latter extended to allow self-reconfiguration from a chain configuration to an arbitrary shape with some admissibility conditions [START_REF] Walter | Algorithms for fast concurrent reconfiguration of hexagonal metamorphic robots[END_REF][START_REF] Bateau | Increasing the efficiency of distributed goal-filling algorithms for self-reconfigurable hexagonal metamorphic robots[END_REF]. These algorithms assume less restrictive motion constraints than the motion constraints we assume for the 2D Catoms. For instance, these algorithms allow the two first motions described as infeasible in Figure 3, starting from the left.

Self-reconfiguration presented in [START_REF] Lakhlef | Energy-aware parallel self-reconfiguration for chains microrobot networks[END_REF][START_REF] Lakhlef | Fast and robust self-organization for micro-electro-mechanical robotic systems[END_REF] consists in using map-less representation for describing shapes. The benefit lies in a reduced memory footprint, but the number of supported goal shapes is limited. Proposed distributed algorithms manage to construct square shapes with spherical modules arranged in a two-dimensional hexagonal lattice. Due to the fact that initial and goal shapes are fixed, the number of movements can be predicted.

Algorithms to reconfigure an initial clump of modules arranged in a hexagonal lattice to a chain configuration were proposed in [START_REF] Wong | Deterministic distributed algorithm for self-reconfiguration of modular robots from arbitrary to straight chain configurations[END_REF][START_REF] Wong | Unpacking a cluster of modular robots[END_REF]. These algorithms do not require message passing and do not use any pre-processing. In these algorithms, modules can both rotate and slide over other modules. Thus, these algorithms assume less restrictive motion constraints than ours.

In [START_REF] De | Scalable shape sculpting via hole motion: Motion planning in lattice-constrained modular robots[END_REF], the authors propose a distributed shape formation algorithm based on hole motions, for ensembles arranged in a hexagonal lattice. This algorithms can construct various shapes by randomly moving empty spaces within the ensemble. Although a wide variety of shapes can be built, this algorithm requires less restrictive motion constraints than ours, e.g., it allows the two first infeasible motions in Figure 3.

In [START_REF] Michael Rubenstein | Programmable self-assembly in a thousandrobot swarm[END_REF], the authors propose a parallel, decentralized and asynchronous algorithm for the Kilobot swarm system [START_REF] Michael Rubenstein | Kilobot: A low cost scalable robot system for collective behaviors[END_REF] to self-assemble almost any kind of compact twodimensional shapes. This algorithm has been applied on hardware systems with more than a thousand individual robots per swarm entities. However, these swarm robots have different physical motion constraints. During the self-assembly process, Kilobots may collide with one another. While this is possible with Kilobots, this is not acceptable in our system.

Existing protocols contain interesting ideas but consider different physical motion constraints, different restrictions on the initial and the goal shapes and different control properties. The contribution of this paper is to propose a distributed, fully decentralized, asynchronous and parallel self-reconfiguration algorithm for 2D Catoms that can manage almost any kind of initial and final compact shapes.

In this section, we present the general idea of the Cylindrical-Catoms Self-Reconfiguration (C2SR) algorithm 1 that reconfigures a robot composed of modules from an initial shape I to a goal one G.

Both shapes have to satisfy some admissibility conditions. We provide some intuitions about them in this paragraph and in Figure 4. A more formal description of the conditions and their demonstration are left for future work. Both shapes are compact, i.e., they do not contain holes, they are homeomorphic to a sphere. Moreover, both shapes are next to each other and intersect in one or more bottom cells. Let the peripheral path be the path formed from the empty cells on the periphery of both shapes, starting from and ending at the second horizontal layer (see Figure 4). This path has to be large enough to allow some modules, which progress along that path in the same direction with an empty space of at least one cell between successive modules, to move without violating our motion constraints and without risking colliding/getting attached with one another (see Figure 4 and Rule 1). Note that this condition implies that, at the upper layers, the horizontal space between the initial and the goal shapes has to be sufficiently large to enable these modules to move between the two shapes. Furthermore, the number of 2D Catoms in I has to be greater or at least equal to the number of target positions in G (i.e., |I| ≥ |G|). are not part of the initial or the goal shapes, progress along the peripheral path in the same direction with an empty space of at least one cell between successive modules. The configurations on the top are not valid for several reasons. First, they do not intersect in at least one cell. Second, they both contain a hole. Third, the peripheral path is not large enough in locations in red. Indeed, modules in yellow could not move without violating our motion constraints and without getting attached with each other.

During the execution of C2SR with shapes individually composed of only continuous horizontal layers, the goal 1 Some examples of self-reconfiguration with C2SR are available online in video at https://youtu.be/XGnY-oS4Nw0 shape is progressively constructed from the bottom layer to the top one by stripping the initial shape, module by module in the reverse order (see Figure 5). Because of physical constraints, at a given instant, only modules on the periphery can move. In order to avoid module collisions and deadlocks, peripheral modules form a stream: modules roll in the same direction d (CW in Figures 1 and5), and maintain an empty cell between each other using message exchanges. Modules in the stream do not overtake each other. Ci denotes the position that C i would occupy after its rotation around C j . C i decides to take part in the stream if the following logical condition is satisfied:

stream(C i ) : -f ree(C i ) ∧ ( (p Ci / ∈ G ∧ p Cj .y = 0) ∨ (p Ci / ∈ G ∧ p ′ Ci .y ≤ p Ci .y) ∨ (p Ci / ∈ G ∧ p Cj ∈ G) ∨ (p Ci ∈ G ∧ p ′ Ci ∈ G ∧ p ′ Ci .y ≤ p Ci .y) )
A module in the stream decides to move if it satisfies the stream progression rule (see Rule 3). More precisely, a module in the stream can move if the set of modules geographically adjacent to its destination cell contains no more than three modules and none of them, except the module itself, belongs to the stream (see Figure 6). This rule requires local interactions with neighbors adjacent to its source and destination positions. These modules are at most two cells away. The admissibility conditions on I combined with the two rules above, guarantee that these modules are at most five network hops away.

Rule 3 (the stream progression rule) A module C i can move from its position p Ci to the position p ′ Ci if the following condition is satisfied: Rule 3 prevents collisions. The admissibility conditions on I and G, combined with Rules 2 and 3 prevent deadlock. Note that, because of the stripping order and the construction order, our algorithm also guarantees that at all time the system remains connected.

progression(C i ) : -stream(C i ) ∧ |N K p ′ C i | ≤ 3 ∧ ∄C j ∈ N K p ′ C i | C j = C i ∧ stream(C j )
Each module checks for convergence using Rule 4 at the initialization and after every move. A module has converged if it is initially in a goal position, or if it has reached G and moving in direction d will cause it to leave G or to go up.

Rule 4 (the local convergence rule) Let us consider two modules C i and C j such that both C i and C j are on the periphery and C j is the next peripheral neighbor of C i in the direction of rotation. p ′ Ci denotes the position that C i would occupy after its rotation around C j . C i has converged if it satisfies the following condition:

converged(C i ) : -(p Ci ∈ I ∧ p Ci ∈ G) ∨ (p Ci ∈ G ∧ p ′ Ci / ∈ G) ∨ (p Ci ∈ G ∧ p ′ Ci ∈ G ∧ p ′ Ci .y > p Ci .y)
Applying these rules in a distributed asynchronous system with parallel communications and motions is challenging. It is especially complex to maintain N K sets using only communications. A complete implementation that overcomes this challenge is presented in the next section.

C2SR Implementation

In this section, we provide a detailed implementation of C2SR2 . Algorithm 1 shows the input and local variables of C2SR along with its initialization pseudo-code. Every module knows its position in the lattice, the goal shape, G, and the rotation direction, d. Algorithm 2 describes some helper functions used in the description of our implementation of C2SR. Algorithm 3 provides the message handler pseudo-code of C2SR. Algorithm 4 gives the pseudo-code executed by a module after it finishes an atomic move. We assume that interrupts are disabled during message and event handler execution. In our implementation, modules can have different states: BLOCKED, GOAL, WAITING or MOVING. WAITING and MOVING modules belong to the stream. At the initialization and during the execution, modules locally decide their state using Rules 1, 2 and 4. Modules in the stream move in rotation direction d around their peripheral neighbor in the d direction. Before moving, modules have to ensure that the stream progression rule (Rule 3) is satisfied. WAITING modules send CLEAR-ANCE REQUEST messages to get the authorization to move. Clearance requests are composed of the module source position and of its destination. These requests travel around the module destination cell. At each hop, modules check if the requested move satisfies the stream progression rule (see Algorithm 3, lines 1-24). If the stream progression rule is not satisfied the clearance request either has to be stored locally (see Algorithm 3, lines 6-9) or to be stored at the previous module using a DE To prevent collision, modules maintain a list of neighbor cells from/into which a module is moving. After having moved to a new position, modules send an END OF MOVE (EOM for short) message that is progressively forwarded around the cell of their previous position (see Algorithm 4, line 3 and Algorithm 3, lines 42-57). Upon reception, of an EOM message, delayed clearances are potentially re-activated (see Algorithm 3, lines 48-57).

Input: p C i // position of C i d ∈ {CW, CCW } // direction
START TO MOVE and START TO MOVE ACK messages guarantee that no message is lost when a module decides to actually move (see Algorithm 3, lines 36-41).

Modules never need to communicate with modules farther than two cells away in the lattice, which means that, due to our requirements, modules never need to send messages that have to more than five hops. Thus, our algorithm uses only local interactions between modules.

Experimental Evaluation

We implemented C2SR in C++ and evaluated it using VisibleSim [START_REF] Dhoutaut | Efficient simulation of distributed sensing and control environments[END_REF], a simulator for modular robots. This section presents our experimental results. Through our experiments, we show the effectiveness of C2SR and its efficiency in terms of communications, movements and execution time.

VisibleSim enables one to perform simulations with different and variable motion and communication delays. In our evaluation, we assume that neighboring modules communicate together using 8-N-1 serial communications. Hence, we assume the effective bit-rate is equal to 80% of the link bit-rate. We assume the effective average communication bit-rate between two neighboring modules follows a Gaussian distribution. Moreover, we assume the average motion speed during atomic moves of a 2D Catom also follows a Gaussian distribution. We do not simulate delays due to processing and interruptions because we assume them to be negligible in comparison to communication and motion delays.

Unless explicitly mentioned, we assume the following simulation parameters. We consider the effective aver-age communication bit-rate during message exchanges between two neighboring modules has a distribution centered on 38.9 kbps with a standard-deviation of 389 bps (1% of the mean). Moreover, we assume the average motion speed during atomic moves of a module has a distribution centered on 1.88 mm • s -1 with a standard-deviation of 0.0188 mm • s -1 (1% of the mean).

We evaluate C2SR on the self-reconfiguration of random clumps of 2D Catoms into four kinds of shapes, namely a car, a flag, a magnet and a pyramid shape (see Figures 1 and7). For each target shape, we generated different versions of the goal configurations using different scales ranging from a dozens to ten thousands of modules.

Effectiveness Evaluation

As shown in Figure 7, C2SR is able to self-reconfigure ensembles composed of more than 10,000 2D Catoms.

Communication Evaluation

Figure 8 shows the total number of messages sent during the execution of C2SR according to the size of the goal shape. For the shapes we considered, the number of messages seems to depend on the size of the goal configuration and not on the actual shape of the arrangement. Moreover, the standard-deviation is very small, so small, that it is not visible on the figure. Thus, for a goal shape of a given size, C2SR always sends approximately the same number of messages. Furthermore, as shown in Figure 8 by the curve of best fit y(x) = 20.29x 1.53 , this number of messages is highly predictable and increases polynomially with the size of the goal shape. Figure 9 indicates that a few modules tend to send a lot more messages than the other modules. Intuitively, modules that stay at the boundary between I and G are communication hotspots because many modules have to communicate with them before rolling over them in order to reach G (see Figure 13). Figure 10 shows the maximum message queue size reached by the modules during the execution of C2SR, taking into account both the incoming and the outgoing messages. The maximum message queue size is constant and equal to two regardless of the shape of the goal configuration and regardless of its size. We recall that messages generated by C2SR have a small and constant size. As a consequence, the traffic generated by C2SR is well controlled and modules do not require a lot of memory space to store incoming and outgoing messages.

Figure 11 shows the average number of hops traveled by the packets during the execution of C2SR. The average and the maximum number of hops traveled by the packets is small and relatively constant regardless of the shape of the goal configuration and regardless of its size. This confirms that C2SR only involves local interactions, as announced in the previous section.

Motion Efficiency

Figure 12 shows the total number of atomic moves performed during the execution of C2SR according to the size of the system for different goal shapes. Note that this figure is really similar to Figure 8. Here again, the number of atomic moves seems to only depend on the size of the goal configuration and not to the actual shape of the arrangement. As shown in Figure 12 by the curve of best fit y(x) = 2.09x 1.53 , the number of atomic moves is highly predictable and increases polynomially with the size of the goal shape. Notice that the number of messages is approximately equal to ten times the number of moves (see Figures 8 and12). Thus, an atomic move requires in average 10 messages.

As shown in Figure 13, many modules can move concurrently during the execution of C2SR. Thus, although the self-reconfiguration process may require many atomic moves, it remains reasonably time efficient as shown in the next subsection.

Execution Time Efficiency

Figure 14 shows the average simulated time of C2SR execution according to the size of the system. For the different goal shapes we considered, this time seems to only depend on the size of the configuration and not to the actual shape of the arrangement. Moreover, the standard-deviation is very small and not visible on the figure. Thus, for goal shape of a given size, C2SR always approximately lasts the same duration. As shown in Figure 14 by the curve of best fit y(x) = 0.017x + 0.149, the simulated time is highly predictable and increases linearly with the size of the goal shape. The slope of the line gives the reconfiguration speed: C2SR fills on average 1 0.017 ≈ 59 goal cells per minute.

Figure 15 shows the average simulated time of C2SR execution according to the average communication bit-rate for the two different motion speeds supported by the 2D Catoms. We consider the usual bit-rates of serial communications. We conducted this experiment for the car goal shape composed of 1,073 modules. Until 38.9 kbps, the self-reconfiguration process becomes much more faster as the average communication bit-rate increases. Beyond 38.9 kbps, the self-reconfiguration speed increases less quickly and tends to stabilize.

Conclusion

We have proposed Cylindrical-Catoms Self-Reconfiguration (C2SR), a parallel, asynchronous and fully decentralized distributed algorithm to selfreconfigure lattice-based MSR from an initial shape to a goal one.

The evaluation of C2SR has been conducted with real executions under a simulated physical environment (Vis-ibleSim). These simulations show our algorithm to have nice properties.

The time for reconfiguration is linear in the number of modules and this time is predictable and seems to only depends on the number of modules. The number of messages sent is also predictable such that added with the number of movements, it can give an estimate of the power consumption of the algorithm. Communications are local such that no routing protocol is needed and the message queue of each module is always bounded by two on our simulation. The needed bandwidth is reasonable, as it uses less than 40 kbps on one example without slowing down the reconfiguration process.

Future Work

In future works, we will demonstrate the correctness of C2SR, i.e., we will prove that the goal configuration can be built if the shape admissibility conditions are satisfied. Moreover, we will study the performance of C2SR on other types of shapes and compare it to existing algorithms. We will also study the distribution of both the number of messages sent per module and the number of atomic moves performed per module. Our observations seem to indicate that our algorithm is highly predictable and that its execution time is linear to the size of the goal shape. A further step would be to prove it. Furthermore, we would like to reduce the memory usage of our algorithm induced by the storage of the goal shape representation. Indeed, hardware modules have limited memory capacity and cannot afford to store the complete representation of large goal shapes [START_REF] Bourgeois | Programmable matter as a cyber-physical conjugation[END_REF][START_REF] Lakhlef | Fast and robust self-organization for micro-electro-mechanical robotic systems[END_REF][START_REF] Lakhlef | Energy-aware parallel self-reconfiguration for chains microrobot networks[END_REF]. We envision two approaches to address this storage limitation, namely to use a compressed representation of the goal shape and/or to disseminate and share the representation of the goal shape between all modules [START_REF] Bourgeois | Programmable matter as a cyber-physical conjugation[END_REF].

Figure 3 :

 3 Figure 3: On the left, motion constraints: examples of feasible (on the top) and infeasible moves (on the bottom).On the right, a labeled system: gray cells are occupied by a module whereas white cells are empty. Some of the empty cells are labeled with their position (e.g., p a , p b , etc.).

Figure 4 :

 4 Figure4: Invalid (on the top) and valid (on the bottom) initial and goal configurations. Modules in yellow, which are not part of the initial or the goal shapes, progress along the peripheral path in the same direction with an empty space of at least one cell between successive modules. The configurations on the top are not valid for several reasons. First, they do not intersect in at least one cell. Second, they both contain a hole. Third, the peripheral path is not large enough in locations in red. Indeed, modules in yellow could not move without violating our motion constraints and without getting attached with each other.

Figure 5 :

 5 Figure 5: Screenshot during the self-reconfiguration process with the initial and goal shapes of Figure 1. Modules in the stream progress by rotating CW.

Figure 6 :

 6 Figure 6: Stream progression rule: a simple example. Modules should rotate CW. White cells are empty and some of them are labeled with their position in the lattice (e.g., p a , p b , etc.). Modules C 1 , C 2 , C 3 and C 4 are in the stream. C 3 is moving. C 1 cannot move because C 2 is in the stream and C 2 ∈ N K pa . C 2 cannot move because C 3 is in the stream and C 3 ∈ N K p b . C 3 can move to p ′ C3 because N K p ′ C 3 contains only three modules and none of them is in the stream, except C 3 . C 4 cannot move because |N K pe | = 5.

Algorithm 4 :

 4 C2SR algorithm event handler detailed for any module C i . 20-24). The clearance is then progressively forwarded back to the module that initiated the request (see Algorithm 3, lines 25-31).

  (a) Car (9,644 Catoms). (b) Flag (12,047 Catoms). (c) Magnet (10,220 Catoms). (d) Pyramid (8,033 Catoms).

Figure 7 :

 7 Figure 7: Screenshots of VisibleSim at the end of the simulation of C2SR with different kinds of goal shapes composed of about 10,000 2D Catoms.

Figure 8 :

 8 Figure8: Average total number of messages (± standarddeviation) versus the size of the system for different goal shapes. For each point, 10 executions were performed.

Figure 9 :

 9 Figure 9: Average number of messages sent per 2D Catom (± min/max) versus the size of the system for different goal shapes. For each point, 10 executions were performed.

Figure 10 :Figure 11 :

 1011 Figure 10: Maximum reached message queue size (incoming and outgoing messages) versus the size of the system. For each point, 10 executions were performed.

Figure 12 :

 12 Figure 12: Average total number of atomic moves (± standard-deviation) versus the size of the system for different goal shapes. For each point, 10 executions were performed.

Figure 13 :

 13 Figure 13: Screenshot of VisibleSim during a selfreconfiguration process. Modules in the stream progress by rotating CW. Blocked modules are in gray, waiting ones in yellow, moving ones in red and modules that have converged are in green.

Figure 14 :

 14 Figure 14: Average simulated time (± standard-deviation) versus the size of the system for different goal shape. For each point, 10 executions were performed.

Figure 15 :

 15 Figure 15: Average simulated time (± standard-deviation) versus the communication bit-rate (random initial configuration to the car of 1, 073 2D Catoms). For each point, 10 executions were performed.

  N N Ci denotes the network neighbors of the module C i . Catoms on the periphery have clockwise (CW) and counter-clockwise (CCW) neighboring Catoms that also belong to the periphery. For instance, in Figure 3, C 9 is C 6 's CW peripheral neighbor and C 10 's CCW one. C 11 is both C 12 's CW and CCW peripheral neighbor.

  of rotation G // goal shape Local Variables: state // state of C i M ovings // cells from/into which a neighbor module is moving P endings // pending clearance requests clearance // clearance for the current move (if any)

	8 else
	9	state ← BLOCKED;
	10 end
	Algorithm 1: C2SR algorithm input, local variables
	and initialization detailed for any module C i .

1 Initialization of C i : 2 M ovings ← ∅; P endings ← ∅; clearance ←⊥; 3 if p C i ∈ G then 4 state ← GOAL; 5 else if isInStream() then 6 state ← WAITING; 7 requestClearance();

25

  -LAYED CLEARANCE message (see Algorithm 3, lines 2-5, 11-14 and 32-35). If the stream progression rule is satisfied, the clearance is granted (see Algorithm 3, lines cells at positions p 1 and p 2 are adjacent in the hexagonal lattice, false otherwise; N C i such that C i is connected to C k on the connected interface that immediately follows the interface pointing to position pos in direction dir; When CLEARANCE REQUEST(r(src, dest, cnt)) is received by C i from C j do: 2 if state = WAITING then 3 send DELAYED CLEARANCE(r) to C j ; end 17 Cn ← getN eighbor(d, r.dest); 18 if Cn = C j ∧ areAdjacentCells(p Cn , r.dest) then When CLEARANCE(c(src, dest)) is received by C i from C j do: 26 if c.src = p C i then When START TO MOVE is received by C i from C j do: 37 send START TO MOVE ACK to C j ; 38 When START TO MOVE ACK is received by C i from C j do: 39 state ← MOVING; 40 C k ← getN eighbor(d); 41 move around C k in direction d; 42 When END OF MOVE(c(src, dest)) is received by C i from C j do: 43 M ovings ← M ovings -{c.src, c.dest}; 44 f orwardEndOf M ove(c, C j ); 45 if isInStream() then else if ∃r ∈ P endings | r ∈ areAdjacentCells(r.dest, c.src) then When C i has finished to move do: 2 p C i ← clearance.dest; 3 send END OF MOVE(clearance) to getN eighbor(d);

	1 Function hasConverged():
		// The local convergence rule (Rule 4)
			4	return;
			5 end
			6 if r.dest ∈ M ovings then
			7	P endings ← P endings ∪ {r};
	6 end	8	return;
	7 Function opppositeDirection(d): // d ∈ {CW, CCW } 8 return the opposite direction of d; 9 end	9 end 10 if state = BLOCKED ∨ state = GOAL then 11 if r.cnt = 3 then 12 send DELAYED REQUEST(r) to C j ; 13 return;
	10 Function isFree(): // The freedom of movement rule (Rule 1)	14 15	end r.cnt ← r.cnt + 1;
	11	return free(C i ) considering both N N C i and M ovings;
	12 end
	13 Function isInStream():	19	send CLEARANCE REQUEST(r) to Cn;
	// The stream entrance rule (Rule 2) return stream(C i ) considering both N N C i and M ovings; 15 end 14	20 else 21 c ← (r.src, r.dest); 22 M ovings ← M ovings ∪ {r.dest}; 23 f orwardClearance(c, ⊥);
	16 Function getNeighbor(dir):	24 end
	17	return the peripheral neighbor in direction dir (see Section
		2);
			29 else
			30	f orwardClearance(c, C j );
	21 end	31 end
	24 C 40 p ′ end	46 47	state ← WAITING; requestClearance();
	41 end
	42 Function forwardEndOfMove(c(src, dest), C j ): 43 if areAdjacentCells(c.src, p C i ) then 44 C k ← getN eighbor(oppositeDirection(d), c.src);	49 50 51	Cn ← getN eighbor(d, r.dest); if areAdjacentCells(r.dest, p Cn ) then send CLEARANCE REQUEST(r) to Cn;
			52	else
			53	cl ← (r.src, r.dest);
			54	M ovings ← M ovings ∪ {cl.dest};

2 return converged(C i ); 3 end 4 Function areAdjacentCells(p 1 , p 2 ): 5 return true if 18 end 19 Function getNeighbor(dir, pos): 20 return C k ∈ N 22 Function requestClearance(): 23 C k ← getN eighbor(d); i ← position after rotation in direction d around C k ; 25 r ← (src ← p C i , dest ← p ′ C i , cnt ← 0); 26 send CLEARANCE REQUEST(r) to C k ; 27 end 28 Function forwardClearance(c(src, dest), C j ): 29 if areAdjacentCells(c.src, p C i ) then 30 C k ← getN eighbor(oppositeDirection(d), c.src); 31 if C k = C j ∧ areAdjacentCells(c.src, p C k ) then 32 send CLEARANCE(c) to C k ; 33 else 34 M ovings ← M ovings ∪ {c.src}; 35 send CLEARANCE(c) to C l | p C l = c.src; 36 end 37 else if areAdjacentCells(c.dest, p C i ) then 38 C k ← getN eighbor(oppositeDirection(d), c.dest); 39 send CLEARANCE(c) to C k ; 45 if C k = C j ∧ areAdjacentCells(c.src, p C k ) then 46 send END OF MOVE(c) to C k ; 47 end 48 else if areAdjacentCells(c.dest, p C i ) then 49 C k ← getN eighbor(oppositeDirection(d), c.dest); 50 send END OF MOVE(c) to C k ; 51 end 52 end Algorithm 2: C2SR helper functions detailed for any module C i . 1 16 27 clearance ← c; 28 send START TO MOVE to C j ; 32 When DELAYED CLEARANCE(r(src, dest, cnt)) is received by C i from C j do: 33 if r.src = p C i then 34 P endings ← P endings ∪ {r}; 35 end 36 48 55 f orwardClearance(cl, ⊥); 56 end 57 end Algorithm 3: C2SR algorithm message handler detailed for any module C i . 1 4 clearance ← perp; 5 if hasConverged() then 6 state ← GOAL; 7 else if isInstream() then 8 state ← WAITING;

The complete source code is available online at https://github. com/claytronics/visiblesim

Acknowledgments

This work has been funded by the Labex ACTION program (contract ANR-11-LABX-01-01) and ANR/RGC (contracts ANR-12-IS02-0004-01 and 3-ZG1F) and ANR (contract ANR-2011-BS03-005).