Aymé Spor
email: spor@moulon.inra.fr

Thibault Nidelet
email: nidelet@moulon.inra.fr

Jonattan Simon
email: jonattan.simon@gmail.com

Aurélie Bourgais
email: bourgais@moulon.inra.fr

Dominique De Vienne
email: devienne@moulon.inra.fr

Delphine Sicard
email: sicard@moulon.inra.fr

Niche-driven evolution of metabolic and life-history strategies in natural and domesticated populations of Saccharomyces cerevisiae

Background: Variation of resource supply is one of the key factors that drive the evolution of lifehistory strategies, and hence the interactions between individuals. In the yeast Saccharomyces cerevisiae, two life-history strategies related to different resource utilization have been previously described in strains from different industrial origins. In this work, we analyzed metabolic traits and life-history strategies in a broader collection of yeast strains sampled in various ecological niches (forest, human body, fruits, laboratory and industrial environments).

Results: By analysing the genetic and plastic variation of six life-history and three metabolic traits, we showed that S. cerevisiae populations harbour different strategies depending on their ecological niches. On one hand, the forest and laboratory strains, referred to as extreme "ants", reproduce quickly, reach a large carrying capacity and a small cell size in fermentation, but have a low reproduction rate in respiration. On the other hand, the industrial strains, referred to as extreme "grasshoppers", reproduce slowly, reach a small carrying capacity but have a big cell size in fermentation and a high reproduction rate in respiration. "Grasshoppers" have usually higher glucose consumption rate than "ants", while they produce lower quantities of ethanol, suggesting that they store cell resources rather than secreting secondary products to cross-feed or poison competitors. The clinical and fruit strains are intermediate between these two groups.

Conclusions: Altogether, these results are consistent with a niche-driven evolution of S. cerevisiae, with phenotypic convergence of populations living in similar habitat. They also revealed that competition between strains having contrasted life-history strategies ("ants" and "grasshoppers") seems to occur at low frequency or be unstable since opposite life-history strategies appeared to be maintained in distinct ecological niches.

Background

Resource supply is one of the most important ecological factors that drive the evolution of organisms. Therefore the metabolic pathways implicated in external resource consumption are expected to have an essential role in the evolution of life-history traits. Two different strategies for exploiting resources are commonly described. In the "selfish" strategy the individuals are consuming quickly resources and increase their own reproduction rate. In the "cooperative" strategy the individuals save resources for the whole group at the expense of their own reproduction rate. In the latter case, individuals are supposed to exploit resource slowly but efficiently. When individuals share common resources, there is a dilemma in which individuals that act selfishly consume rapidly the common resources, reducing the fitness of the whole group, which leads to what has been called the "tragedy of the commons" [START_REF] Hardin | The Tragedy of the Commons[END_REF]. The central principle of such a "social conflict" is that there must be a trade-off between individual shortterm and population long-term interests. This metaphor reflecting a dilemma between individual and population interests has been used in a vaste diversity of fields in science, from the evolution of competition and cooperation in insect societies [START_REF] Wenseleers | Tragedy of the commons in Melipona bees[END_REF] to intra-genomic conflict [START_REF] Leigh | How does selection reconcile individual advantage with the good of the group?[END_REF], and even to propose a solution to alleviate and improve the work of reviewers [START_REF] Hochberg | The tragedy of the reviewer commons[END_REF].

In the case of heterotrophic microorganisms, the existence of a dilemma between selfish and cooperative strategies has been proposed to result from a metabolic trade-off between the rate and efficiency of resource use [START_REF] Heinrich | Theoretical approaches to the evolutionary optimization of glycolysis: thermodynamic and kinetic constraints[END_REF][START_REF] Waddell | Optimization of glycolysis: a new look at the efficiency of energy coupling[END_REF]. A high rate of ATP production per unit of time is associated with a high reproduction rate and is considered as a selfish strategy, whereas a high yield of ATP production, i.e. the number of units of ATP per unit of resource consumed, is associated with a low reproduction rate but with a high biomass production, and is considered a cooperative strategy. The evolutionary significance of such a trade-off has been studied using both experimental and theoretical approaches in the context of evolutionary game theory [START_REF] Pfeiffer | Game-theoretical approaches to studying the evolution of biochemical systems[END_REF]. The outcome of competition between selfish and cooperative strains for a common resource is that a selfish strain with a high rate of ATP production always wins over the prudent strain with a high yield of ATP production [START_REF] Gudelj | Constraints on microbial metabolism drive evolutionary diversification in homogeneous environments[END_REF][START_REF] Kreft | Biofilms promote altruism[END_REF][START_REF] Pfeiffer | Cooperation and competition in the evolution of ATP-producing pathways[END_REF]. The maintenance of highly efficient cooperative strains is only possible in case of spatially structured environment or in case of density-dependent cost of selfish metabolism (toxins productions for instance) [START_REF] Kreft | Biofilms promote altruism[END_REF][START_REF] Pfeiffer | Cooperation and competition in the evolution of ATP-producing pathways[END_REF][START_REF] Maclean | Resource competition and social conflict in experimental populations of yeast[END_REF].

The yeast Saccharomyces cerevisiae is able to use two main metabolic strategies. The respiration allows a high efficiency of resource conversion into energy but at low rate. The fermentation is associated with a low efficiency of resource conversion into energy but a high metabolic rate. Mathematical modelling as well as construction of engineered strains of S. cerevisiae, either respirer or respiro-fermenter, have shown that coexistence or competitive exclusion between these two strategies could occur [START_REF] Maclean | Resource competition and social conflict in experimental populations of yeast[END_REF]. The analysis of these two metabolic strategies in natural populations had not yet been carried out. Although the genomic structure of S. cerevisiae populations begins to be studied [START_REF] Aa | Population structure and gene evolution in Saccharomyces cerevisiae[END_REF][START_REF] Fay | Evidence for domesticated and wild populations of Saccharomyces cerevisiae[END_REF][START_REF] Legras | Bread, beer and wine: Saccharomyces cerevisiae diversity reflects human history[END_REF][START_REF] Liti | Sequence diversity, reproductive isolation and species concepts in Saccharomyces[END_REF][START_REF] Liti | Population genomics of domestic and wild yeasts[END_REF][START_REF] Schacherer | Comprehensive polymorphism survey elucidates population structure of Saccharomyces cerevisiae[END_REF], very few studies are dedicated to the phenotypic characterisation of yeast populations coming from different ecological niches. We showed in a previous paper that the genetic variability of metabolic and life-history traits distributes the industrial strains between two extreme life-history strategies [START_REF] Spor | Ant" and "grasshopper" life-history strategies in Saccharomyces cerevisiae[END_REF]. The "grasshopper" strains have a high specific glucose consumption rate in fermentation, a large cell size but a low carrying capacity, while the "ant" strains have a low specific glucose consumption rate, a small cell size and a high carrying capacity. In other words, the "grasshoppers" behave as selfish strains allocating resource to their own cell size, while the "ants" behave as cooperative strains saving resource allowing a high population size to be reached.

The presence of these strategies in other habitats than industrial ones has not yet been addressed. Moreover, because of lack of genetic variation on reproduction rate in the studied collection of industrial strains, the previous data did not allow to ask question about the relationship between metabolic strategies and reproduction rate. Finally, life-history traits were studied in fermentation and correlated variation for performances during respiration was not studied.

In this paper, we asked whether different metabolic and life-history strategies could be found in the broad range of habitats of S. cerevisiae. We analyzed the plastic and genetic components of six life-history traits (intrinsic reproduction rate, carrying capacity, cell size, reproduction rate in fermentation, time of the shift between fermentation and respiration, and reproduction rate in respiration) and three metabolic traits (glucose consumption rate, ethanol production, fermentation yield) in 19 strains coming from forest, human body, laboratory, fruits and various industrial origins [START_REF] Spor | Ant" and "grasshopper" life-history strategies in Saccharomyces cerevisiae[END_REF]. Strains were grown in two culture media differing in their amount of resource (1% and 15% glucose) allowing both fermentation and respiro-fermentation processes to be investigated.

Methods

Biological Material

Nineteen diploid strains of S. cerevisiae were chosen from the CIRM-Levures (Centre International de Ressources Microbiennes, Thiverval-Grignon, France), the Saccharomyces Genome Resequencing Project collection (Sanger Institute, Cambridge, UK) and Justin Fay's Collection (Washington University in St. Louis -School of Medicine, St. Louis, USA). The collection included strains isolated from forest, coconut and cactus fruits, human body, laboratory, brewery and winery, and has been formed in order to group together at least 3 strains from each type of habitat (Table 1). For each strain, a reference stock was conserved at -80°C in our lab.

Culture Conditions and Measurements

For measuring accurately various life-history and metabolic traits, the strains were grown in the same artificial laboratory conditions. Growth kinetics were realized in two liquid media containing 3% Yeast Nitrogen Base with amino acids and differing by their glucose content, 1% and 15%. One percent glucose corresponds to a low concentration, commonly used in laboratory conditions, while 15% glucose is close to the concentration found in sap or fruits. We chose this nitrogen concentration to make sure that the glucose is the sole limiting nutrient. At 1% glucose concentration, yeast populations are supposed to grow first in fermentation then to switch to respiration. At 15% glucose concentration, yeast populations are supposed to grow only in fermentation, and are submitted to osmotic stress. The cultures were incubated at 30°C under 200 rpm agitation. In these conditions, yeast is exclusively reproducing by mitosis. After an overnight culture, around 10 6 cells were put into 40 mL fresh medium (30°C, 200 rpm). During growth kinetics, two samples (1 mL and 200 μL) were taken at seven time points (t = 4, 9, 13, 24, 48, 72 and 96 h) to estimate: (i) the glucose and ethanol concentrations, (ii) the population density and mean cell size measured with a counter Beckman Coulter ® Z2. Each growth kinetics was repeated independently from two to four times. Each replication was performed with a new colony from the reference stock.

Life-history traits

Life-history traits were measured by analyzing the population dynamics. In batch culture, the changes over time of the cell number are classically analysed using a logistic model (exponential growth followed by a stationary phase) in order to estimate population dynamics parameters. However, a diauxic shift occurs in the 1% glucose medium dividing the dynamics into two parts: after a first period of growth in fermentation with production of ethanol, yeast shifts its metabolism and the respiration process takes place using ethanol as a carbon source. Therefore, the population dynamics was analyzed using two adjustment models (Figure 1). First, the cell number over time was log-transformed, and a segmented regression model [START_REF] Muggeo | Estimating regression models with unknown break-points[END_REF] was used to estimate the parameters of the transition between fermentation and respiration (T shift ). The slope in fermentation gave the population reproduction rate in fermentation (R ferm ), the population size at T shift gave the carrying capacity in fermentation and the slope after the T shift gave the population reproduction rate in respiration after the diauxic shift (R resp ) (Figure 1A). This adjustment procedure was applied using the "segmented" package under R software. Although a diauxic shift is not supposed to occur in 15% glucose medium, some strains appear to have a small respiration phase in this condition (R resp different from zero) and we therefore used the method in the two media.

Second, a logistic model of population dynamics was fitted to experimental datapoints in fermentation (the points before T shift ): where N t is the population size at time t, K is the carrying capacity (maximum population size, reached when glucose is exhausted), N 0 is the initial population size and r is the intrinsic reproduction rate (maximum rate of increase of the population, i.e. at the beginning of the kinetics when there is no competition). Fitting the growth kinetics with this model allowed estimating K and r (Fig 1B ).

N KN e rt K N e rt t = + - 0 0 1 ( ) , (1)
As expected, a significant positive correlation was observed between the intrinsic growth rate r estimated by the second procedure and R ferm obtained from the first procedure (ρ 15% = 0.74 and ρ 1% = 0.77). Therefore we chose to focus only on R ferm .

As ethanol was not completely consumed after 96 hours, when the experiments were stopped, we did not have access to the population size (carrying capacity), cell size and yield (population size × cell size) at the end of the respiration process. We thus focused on the cell size, carrying capacity and yield at the end of the fermentation process. Mean cell size (S cell ) was therefore analyzed at the end of the fermentation process, i.e. at the time point the closest to T shift .

Metabolic traits

Glucose consumption rate and ethanol production Glucose and ethanol extracellular concentrations were measured using enzymatic kits (rBiopharm, Darmstadt, Germany). We estimated the glucose consumption rate as described in [START_REF] Spor | Ant" and "grasshopper" life-history strategies in Saccharomyces cerevisiae[END_REF]. The glucose consumption rate at T 50 (when 50% of the glucose was consumed) was divided by the population size at the same time point in order to infer a specific glucose consumption rate denoted J spec (g × min -1 × cell -1 ). Note that the T 50 falls during the exponential phase of the fermentation process in the two media (approximately after 8 hours and 20 hours respectively in the 1% and in the 15% glucose medium). We also measured the maximal quantity of ethanol produced and released in the medium (Eth max ), which occurred at the end of the fermentation or at the beginning of the respiration process, i. e. close to T shift .

Fermentation yield

In microbiology, the yield is classically estimated through the measurement of the OD per unit of glucose consumed [START_REF] Maclean | The tragedy of the commons in microbial populations: insights from theoretical, comparative and experimental studies[END_REF]. However, the correlation between OD value and biomass (product of the mean cell size by the population size [START_REF] Spor | Ant" and "grasshopper" life-history strategies in Saccharomyces cerevisiae[END_REF]) is only ρ = 0.77. So we estimated directly the fer- mentation yield, Y ferm , using the ratio of the biomass over the quantity of glucose consumed. We did not consider the yield of respiration because we did not reach the plateau of this process.

Variation of population sizes overtime during the growth kinetics

Microsatellite analysis

Yeast DNA extraction and microsatellite PCR amplifications were carried out as described in [START_REF] Albertin | Evidence for autotetraploidy associated with reproductive isolation in Saccharomyces cerevisiae: towards a new domesticated species[END_REF]. Eight microsatellites (three dinucleotide and five trinucleotide repeats) were analysed. They are located on 7 different chromosomes, mostly in non coding region.

Statistical Analysis

A Principal Component Analysis was first conducted on all traits (both life-history and metabolic traits) averaged over replications to visualize the distribution of the strains on the plane defined by the two axes explaining the largest part of variation.

Then the factors accounting for the variation of each variable among media and strains were analyzed with a mixed analysis of variance model:

where Z is the quantitative variable (K, S cell , R ferm , T shift , J spec , Eth max or Y ferm ), Block is the random block effect (experimental repetition) (i = 1, 2, 3, 4), medium is the medium effect (j = 1, 2), ori is the origin effect (k = 1, 2, 3, 4, 5), Strain is the random strain effect within habitat of origin (l = 1, 2, 3, 4, 5), Block*medium (random), medium*ori (fixed) and medium*Strain(ori) (random) are interaction effects and ε is the residual error.

For each trait, the normality and homogeneity of the residual distributions were studied. For all traits except R resp and J spec , a logarithmic transformation proved to be necessary to have normally and homogeneously distributed residues. The variables R resp and J spec displayed particular distributions. We chose to realize the ANOVA on the average values over the experimental repetitions for R resp , and on the log-transformed average values over the experimental repetitions for J spec . This resulted in homogeneity and normality of the residual distributions, but the ANOVA model used was less powerful:

where Z is the variable (R resp or J spec ), medium is the medium effect (i = 1, 2), ori is the origin effect (j = 1, 2, 3, 4, 5), Strain is the random strain effect within industrial origin (l = 1, 2, 3, 4, 5), medium*ori is a fixed interaction effect and ε is the residual error.

The average performances of strains of different origins were compared using the least square estimation of Y k obtained by averaging the phenotypic value over strains from the same origin. Least square mean and variance estimates were obtained from JMP Procedure (SAS Institute Inc.). Significance of differences between means was assessed using Tukey HSD method.

Genetic Correlations between life-history traits

The 19 strains were not phylogenetically independent.

Based on microsatellite length differences, we computed a matrix of genetic Euclidian distances between all pairs of strains. This matrix was used to specify the variance structure in a multivariate generalized linear model. Correlations between traits were calculated based on variance/ covariance component estimates by MCMC method.

Prior distribution for variance and covariance components of the G-matrix (the genetic variance/covariance matrix) and of the R-matrix (the residual variance/covariance matrix) were chosen according to the package documentation (inverse Wishart distributions). These analyses were performed under R software using 'ape' [START_REF] Paradis | APE: Analyses of Phylogenetics and Evolution in R language[END_REF] and 'MCMCglmm' (Hadfield, J: MCMC methods for Multiresponse Generalised Linear Mixed Models: The MCM-Cglmm R package, submitted) packages.

As we tested for 20 correlations, we corrected p-values using a local FDR (False Discovery Rate) procedure [START_REF] Aubert | Determination of the differentially expressed genes in microarray experiments using local FDR[END_REF].

Relationships between life-history and metabolic traits

In each glucose condition, the variability of life-history traits was compared to the variability of metabolic traits, according to the regression model:

where Y il is the mean value over repetitions of a life-history trait of the strain i in the medium l and X il is the mean value over repetitions of a metabolic trait (J spec , Eth max or Y ferm ) of the strain i in the medium l. D represents the phylogenetic distance matrix and ε il is the residual error term. We corrected p-values for multiple tests as previously.

Results

We measured five life-history traits (the carrying capacity K, the mean cell size in fermentation S cell , the reproduction rate in fermentation R fermv , the reproduction rate in respiration R resp and the time to reach the carrying capacity in fermentation T shift ) and three metabolic traits (the glucose consumption rate J spec , the maximal quantity of ethanol released in the medium Eth max and Y ferm ) in a collection of 19 strains coming from various habitats

= + + + + + m e ( ) * (3)
Y aX b D il il il = + + +e . (4)
(industry, forest, fruit, clinical, laboratory) and grown in two contrasted culture media (1% and 15% glucose).

Effect of the glucose content of the medium

We performed a Principal Component Analysis (PCA) to decompose the contribution of each quantitative trait on the variation between strains (Figure 2). The major part of the variation was explained by the first two axes (72%) of the PCA. A clear separation was observed between the strains grown in different glucose conditions. This separation was mainly explained by variation of metabolic traits (J spec , Eth max and Y ferm ) and of two life-history traits: K, which should be the direct reflect of the resource availability in the medium, and R resp , because respiration is present only in the 1% glucose medium. The ANOVA confirmed that the medium effect is very large for these traits (Tables 2,3). The variables Eth max , K and T shift increased with glucose content in the medium, while Y ferm , J spec and R resp had opposite behaviors. R resp was nearly equal to 0 in the 15% glucose medium. Surprisingly, in average, S cell and R ferm were not significantly affected by the glucose content of the medium.

Genetic variation of life-history and metabolic traits

Within each glucose condition, the strains appeared to be clustered according to their habitat of origin, and the variables that contributed mainly to this structure were lifehistory traits (r, S cell , R ferm and T shift ). The "habitat of origin" had a significant effect on K, S cell , R ferm and Y ferm (Table 2 &3). Globally, industrial strains had a large cell size, reproduced slowly, reached a low carrying capacity and produced a weak biomass per unit of resource consumed (Table 4). On the opposite, laboratory and forest strains had a small cell size, reproduced quickly, reached a high carrying capacity and were very efficient in converting glucose into biomass (Table 4). Clinical and fruit strains were intermediate between these two contrasted groups, fruit strains being closer to industrial strains and clinical ones to forest and laboratory ones. Significant genetic variation between strains coming from a same habitat of origin was also found (Strain(ori) effect) for all traits but for S cell (Table 2 &3). Note that genetic main effects (ori and Strain(ori)) were significant neither for Ethmax nor for J spec .

Principal Component Analysis realized on the six life-history traits (K, r, S cell , R ferm , R resp , T shift ) and on the three metabolic traits (Y ferm , Eth max , J spec ) Figure 2 Principal Component Analysis realized on the six life-history traits (K, r, S cell , R ferm , R resp , T shift ) and on the three metabolic traits (Y ferm , Eth max , J spec ). Filled circles correspond to laboratory strains, filled boxes to industrial ones, diamond to forest ones, crosses to clinical ones and stars to fruit ones. Red and blue symbols correspond to the two glucose conditions, respectively 15% and 1%.

Genotype-by-environment interactions

The medium*Strain(ori) interaction effect was significant for all traits. The medium*origin interaction effect was only significant R ferm and T shift . Industrial populations displayed a significantly higher R ferm value in 15% glucose than in 1% glucose (p < 0.05), while the other types of population harbour similar R ferm values in the two media. Industrial populations displayed a lower T shift value in 15% glucose than in 1% glucose, while it was the opposite for the other types of populations.

Genetic correlations between life-history traits

Correlations between life-history traits were studied using the average trait value for each strain in each glucose condition and taking into account the genetic relationships between strains (Table 5).

We detected a significant negative correlation between the carrying capacity K and the S cell in each glucose condition (ρ 15% = -0.79 and ρ 1% = -0.73) (Figure 3A). A significant positive correlation was observed between the carrying capacity and the R ferm in each glucose condition (ρ 15% = 0.87 and ρ 1% = 0.87) (Figure 3B). Finally, a significant negative correlation between S cell and R ferm in each glucose condition (ρ 15% = -0.63 and ρ 1% = -0.79) was found in agreement with the two previous relationships (Figure 3C).

The time to reach the carrying capacity (T shift ) was negatively correlated with R ferm in the 1% glucose medium (ρ 1% = -0.81), indicating that, the faster cells reproduced, the earlier they reached the carrying capacity in fermentation. More interestingly, a significant positive correlation between S cell and R resp (ρ 15% = 0.82 and ρ 1% = 0.73) was detected.

Consequently, whatever the quantity of resource, life-history trait variation in S. cerevisiae populations distributes between two extreme life-history strategies: populations of small cells reproduce quickly in fermentation and reach rapidly a high carrying capacity at the expense of a small reproduction rate in respiration, and populations of large cells reproduce slowly in fermentation, reach a lower carrying capacity but reproduce faster in respiration.

Strategies of resource utilization

Relationships between each life-history and metabolic traits were studied by linear regression using, as we did for correlations, the average trait value for each strain in each glucose condition and taking into account the genetics relationships between strains. The R ferm was positively correlated with Y ferm in the two glucose conditions (R 2 15% = 80%, p < 10 -4 and R 2 1% = 84%, p < 10 -4 ) (Figure 4A), while R resp was negatively correlated to Y ferm in 1% glucose (R 2 1% = 68%, p = 0.003) (Figure 4B). These opposite behaviours gave more weight to the marginally significant trade-offs observed in both environments between the two different reproduction rates (Table 5). Strains that were very efficient for the fermentation process (high reproduction rate and high yield in biomass) seemed to be less efficient in respiration.

In both media, S cell correlated negatively with Eth max (R 2 15% = 68%, p < 0.001 and R 2 1% = 67%, p < 0.024) (not shown). In the 15% glucose medium, where fermentation is the main process, an increase of the R ferm and of K were significantly correlated with Eth max (R 2 15% = 47%, p < 0.013 and R 2 15% = 61%, p = 0.001), while in 1% glucose, where respiro-fermentation occurs, the R resp was significantly negatively correlated to Eth max (R 2 1% = 26%, p < 0.0265). In other words, strains with small cell size that were efficient in the fermentation process released high amount of ethanol, while strains of large cell size, less efficient in fermentation, produced less ethanol and/or were more able to re-consume it as a carbon source during the respiration process.

Finally, in the 1% glucose medium, J spec was negatively correlated to the carrying capacity K and to the Y ferm (R 2 1% = 61%, p < 0.04 and R 2 1% = 58%, p = 0.032, Figure 4D) and positively to the S cell (R 2 1% = 49%, p = 0.05) (Figure 4C), while in the 15% glucose medium no correlation between J spec and any life-history trait was observed.

Discussion and Conclusions

Life-history strategies in wild and domesticated populations of S. cerevisiae

In a previous study, two opposite genetically-based lifehistory strategies have been described from the study of a collection of twelve industrial strains of S. cerevisiae. Some strains (the ''grasshoppers'') consumed quickly glucose, reached a big cell size at the expense of their carrying capacity, whereas other strains (the ''ants'') consumed slowly glucose, reached a smaller cell size, but had a higher carrying capacity [START_REF] Spor | Ant" and "grasshopper" life-history strategies in Saccharomyces cerevisiae[END_REF]. We extended the panel of S. cerevisiae strains to non-industrial populations to determine whether these two life-history strategies had arisen as a consequence of domestication for food processing The average value of the reproduction rate in fermentation (R ferm ), the carrying capacity (K in number of cells per mL), the cell size (S cell in μm), and the yield (Y ferm = K × S cell ) at the end of the fermentation process is reported for each habitat of origin. Significance of differences was assessed by HSD Tukey tests. Levels that are not connected by the same letter are significantly different. utilization or could be found in natural habitats. We showed that these two life-history strategies can be found in other habitats and that the range of trait variation between the two opposite strategies is larger when adding populations from non-industrial sources. In addition, the definition of the two opposite life-history strategies have been refined by analysing not only fermentation but also the respiration process: the "ants" reproduce quickly in fermentation, reach a large carrying capacity but have a small cell size and have a low reproduction rate in the respiration process, whereas the "grasshoppers" reproduce slowly in fermentation, reach a small carrying capacity but cells are big and their reproduction rate in respiration is high. Moreover, the "grasshoppers" have higher or equal glucose consumption rate than "ants" while the maximum quantity of ethanol released in fermentation is lower. This suggests that "grasshoppers" store resources inside the cell rather than secrete secondary products to cross-feed or poison competitors during fermentation. Their performance during the respiration process on the other hand might be related to a better ethanol consumption rate as well as reallocation of intra-cellular stock. The distribution of glycolysis carbons into the different intra and extra cellular metabolites need to be studied for getting more insight into the physiological basis of "ant" and "grasshopper" life-history strategies.

Niche-driven evolution of S. cerevisiae phenotypes

A significant "habitat of origin" effect for most of the lifehistory traits (K, S cell and R ferm ) and for Y ferm was found. Despite a broad geographical origin, strains of the same habitat had similar life-history strategy. Compared to the other strains, the industrial strains can all be considered as "grasshoppers", even though the distinction between "ant" and "grasshopper" life-history strategies has been initially defined within this group. The laboratory and for-est strains can be considered as extreme "ants" and the clinical and fruit strains as intermediate between these two groups (Table 4). Phenotypic homogeneity of strains coming from a same ecological niche supports the idea of genetic exchange among strains coming from similar habitats, as highlighted by phylogenomics studies for wine, laboratory and clinical-fruit strains [START_REF] Aa | Population structure and gene evolution in Saccharomyces cerevisiae[END_REF][START_REF] Fay | Evidence for domesticated and wild populations of Saccharomyces cerevisiae[END_REF][START_REF] Legras | Bread, beer and wine: Saccharomyces cerevisiae diversity reflects human history[END_REF][START_REF] Liti | Population genomics of domestic and wild yeasts[END_REF][START_REF] Schacherer | Comprehensive polymorphism survey elucidates population structure of Saccharomyces cerevisiae[END_REF][START_REF] Diezmann | Saccharomyces cerevisiae: population divergence and resistance to oxidative stress in clinical, domesticated and wild isolates[END_REF]. In addition, homogenizing selection may lead to phenotypic convergence in geographical distant but similar habitats. This hypothesis seems to explain why the three sequenced laboratory strains (S288C, SK1 and Y55), which are the most genetically distant strains [START_REF] Liti | Population genomics of domestic and wild yeasts[END_REF], have close life-history traits. In the case of forest strains our data also confirm a recent study on the variation of stress responses showing that oak strains are phenotypically more similar than expected from their genetic relationships [START_REF] Kvitek | Variations in stress sensitivity and genomic expression in diverse S. cerevisiae isolates[END_REF]. Altogether, these results support the idea of a niche-driven evolution of S. cerevisiae with phenotypic convergence of populations living in similar habitat.

The harshness of the winter season may be one of the key factors of the differentiation between "ants" and "grasshoppers"

The close phenotypic proximity between laboratory strains and forest strains, both having "ant" life-history strategies, is striking. Thinking about the environmental conditions common to these two groups of strains may help understanding what drives the evolution towards "ant" or "grasshopper" strategies. Both oak and laboratory strains appeared to live in low resource media. Oak strains have been isolated from bark or soil and laboratory strains are often grown in 1 or 2% glucose media. A lack of resource may lead to an "ant" strategy. Another explanation can be that both oak and laboratory strains have undergone freeze-thaw cycles related to environmental seasonality in forest or experimental utilization in Genetic correlations between life-history traits Figure 3 Genetic correlations between life-history traits. Each point corresponds to the mean value of traits for a strain in a glucose condition. Pearson correlation coefficients were calculated in each glucose condition between (A) K and S cell , (B) K and R ferm , (C) S cell and R ferm . Same symbols as in Figure 2.

research. Oak related strains have been demonstrated to be freeze-thaw resistant which have been hypothesized as an important advantage to survive to winter niche [START_REF] Kvitek | Variations in stress sensitivity and genomic expression in diverse S. cerevisiae isolates[END_REF].

On the opposite, "grasshopper" strains would not have had the opportunity to adapt to multiple freeze-thaw cycles because of their habitat of origin. The fruit strains used are coming from Philippines, Hawaii and Bahamas, and have probably never experienced freezing before their isolation. Similarly, clinical isolates are expected to live at human body temperature even though their exact mode of transmission and life cycle are unknown. Finally, industrial strains are probably living in quite controlled environments with no drastic temperature changes as expected in wine cellars [START_REF] Sablayrolles | Control of alcoolic fermentation in winemaking: Current situation and prospect[END_REF].

This hypothesis is supported by our knowledge on freeze tolerance which is expected to be higher in smaller cells.

Freezing tolerance has been related to cell size in S. cerevisiae [START_REF] Kaul | Cryoprotection provided by heat shock treatment in Saccharomyces cerevisiae[END_REF][START_REF] Teunissen | Isolation and characterization of a freeze-tolerant diploid derivative of an industrial baker's yeast strain and its use in frozen doughs[END_REF], Torulaspora delbrueckii [START_REF] Hernandez-Lopez | Characterization of a Torulaspora delbrueckii diploid strain with optimized performance in sweet and frozen sweet dough[END_REF], Candida utilis, Escherichia coli, Lactobacillus plantarum, and the human Relationships between life-history traits and metabolic traits Figure 4 Relationships between life-history traits and metabolic traits. Each point corresponds to the mean value of traits for a strain in a glucose condition. Regressions were calculated in each glucose condition between (A) R ferm and Y ferm , (B) R resp and Y ferm , (C) S cell and J spec and (D) Y ferm and J spec . Same symbols as in Figure 2.

leukemia K562 cells [START_REF] Dumont | Cell size and water permeability as determining factors for cell viability after freezing at different cooling rates[END_REF] and may have driven the evolution towards "ant" life-history strategy. A physical explanation could be that the larger surface-to-volume ratio of the small cells makes easier the release of water out of the cell and the decrease of intracellular pressure. Moreover, the formation of ice crystals leading to the mechanical disruption of cell components may be higher in large cells [START_REF] Dumont | Cell size and water permeability as determining factors for cell viability after freezing at different cooling rates[END_REF]. Selection experiments under variable "winter-season" length and temperature should be conducted to test these hypotheses.

Tragedy of the commons in S. cerevisiae populations -Where are we?

Competition for resources can lead to a "tragedy of the commons", i. e. a dilemma between using resource selfishly to the detriment of the long-term survival of the population, or saving resource for the whole community at the expense of its own reproduction. These two opposite types of resource utilization have already been described in yeast and are often illustrated by the trade-off between the rate of glucose uptake (supposed to be high in selfish strains) and yield (supposed to be improved in cooperative strains) [START_REF] Maclean | The tragedy of the commons in microbial populations: insights from theoretical, comparative and experimental studies[END_REF]. However, the trade-off between the yield and the resource uptake rate is commonly found in low glucose media but does not seem to be detected in richer media. In 15% glucose medium, where fermentation is the main physiological process, the trade-off between the yield and the resource uptake rate was not detected among industrial strains [START_REF] Spor | Ant" and "grasshopper" life-history strategies in Saccharomyces cerevisiae[END_REF] and was not detected here in a panel of strains representing a larger genetic diversity. This gives evidence for an environment-dependent rate/yield tradeoff, which reflects the biochemical trade-off between fermentation and respiration, but it does not seem to occur in fermentation.

Competition for resources and social conflict between "ants" and "grasshoppers" does not seem to commonly occur since the two opposite life-history strategies appear to be maintained in distinct ecological niches. Intermediary phenotypes, such as clinical and fruit strains, which have been previously described as resulting from exchanges between isolated genetic groups because of the mosaic composition of their genomes [START_REF] Liti | Population genomics of domestic and wild yeasts[END_REF][START_REF] Schacherer | Comprehensive polymorphism survey elucidates population structure of Saccharomyces cerevisiae[END_REF], could be the evolutionary outcomes of the competition and/or hybridization between "ants" and "grasshoppers". Human body and fruit have indeed been proposed to be environments that are regularly colonized by yeast coming from various geographical and ecological origins [START_REF] Liti | Population genomics of domestic and wild yeasts[END_REF][START_REF] Schacherer | Comprehensive polymorphism survey elucidates population structure of Saccharomyces cerevisiae[END_REF] and thus could be locations where strains of the two opposite life-history strategies meet and compete. However, the outcome of their competition remains difficult to predict. In a one-season time-scale in fermentation, "ants" may win the competition: they save resources, reproduce fast and invest preferentially resources in the carrying capacity at the expense of their own cell size. In a context of long-term competition through multiple seasons with fermentation/respiration cycles, "grasshoppers" should be the "winners". Although they reproduce slowly and reach a lower carrying capacity, they use resources quickly and store them inside the cell which may allow a better survival to starving conditions. In fermentation, they produce a small amount of "toxic" ethanol. In respiration, they may re-consume efficiently ethanol as a carbon source since they reproduce quickly. "Ants" and "grasshoppers" could both be considered as "selfish competitors" depending on the moment of the season.

Therefore, determining the cooperative or selfish nature of each of the two life-history strategies raised no consensus and depends both on the environment and on the time scale. Mathematical modelling and experimental validations of short and long-term competition between "ants" and "grasshoppers" in various habitats should be developed to study the evolutionary outcome of competitions between them.

Figure 1

 1 Variation of population sizes overtime during the growth kinetics. Examples of experimental data points (strain YPS1009) are presented with red (15% glucose) and blue dots (1% glucose). Two methods were used for fitting experimental data points and estimating life-history trait values. A) a segmented regression (red and blue broken lines) of log-transformed data points allowed us to estimate the reproduction rate in fermentation (R ferm ), the time point of the diauxic shift (T shift ), the population size at the end of the fermentation process (carrying capacity K), and the reproduction rate in respiration (R resp ). B) an adjustment to a logistic model allowed us to estimate the intrinsic growth rate (r) and the carrying capacity (K).

Table 1 : Collection of strains of Saccharomyces cerevisiae Strains ID Geographical Origin Habitat Description Collection

 1

	227	Netherlands	Industrial	Brewery, Top	CIRM-Levures 1
	157	Spain	Industrial	Vinery (Grapes)	CIRM-Levures 1
	NCYC110	West Africa	Industrial	Ginger Beer from Z officinale	SGRP 2
	YJM320	USA	Clinical Isolate	unknown	Fay Collection 3
	YJM421	USA	Clinical Isolate	Ascitic Fluids	Fay Collection 3
	322134S	Newcastle, UK	Clinical Isolate	Thorat-Sputum	SGRP 2
	YJM981	Bergamo, Italy	Clinical Isolate	Vaginale	SGRP 2
	IL-01	Illinois, USA	Forest	Soil	Fay Collection 3
	YPS128	Pennsylvania, USA	Forest	Oak Exudate	SGRP 2
	YPS606	Pennsylvania, USA	Forest	Oak Exudate	SGRP 2
	NC-02	North Carolina, USA	Forest	Oak Exudate	Fay Collection 3
	T7	Missouri, USA	Forest	Oak Exudate	Fay Collection 3
	YPS1009	New Jersey, USA	Forest	Oak Exudate	Fay Collection 3
	Y10	Philippines	Fruit	Coconuts	Fay Collection 3
	UWOPS83-2421	Hawaii	Fruit	Opuntia megacantha	SGRP 2
	UWOPS83-787.3	Bahamas	Fruit	Opuntia stricta	SGRP 2
	S288C	California, USA	Laboratory	Rotting fig	SGRP 2
	Y55	France	Laboratory	Wine	SGRP 2
	SK1	USA	Laboratory	Soil	SGRP 2

1

Centre International de Ressources Microbiennes, Thiverval-Grignon, France 2 Saccharomyces Genome Resequencing Project, Sanger Institute, Cambridge, UK

3

Washington University in St. Louis -School of Medicine, St. Louis, USA

Table 2 : Analysis of variance for five life-history traits: the carrying capacity of fermentation (K), the mean cell size (S cell ), the reproduction rate in fermentation (R ferm ), the reproduction rate in respiration (R resp ) and the time to reach the carrying capacity in fermentation (T shift ).

 2

				K	S cell			R ferm		T shift		R resp
	Sources of Variation	df	MS	F	MS	F	MS	F	MS	F	df	MS	F
	Block	3	0.17	0.85	7 × 10 -3	91	0.07	25	0.03	2.50
	medium	1	22.05	42.85**	3.42 × 10 -3	0.29	0.13	2.77	0.35	8.74*	1	3 × 10 -4	79.19**
	ori	4	8.72	8.11**	0.27	12.79**	1.71 5.35** 0.19	2.11	4	1.28 × 10 -5	0.99
	Strain(ori)	14	1.16	2.81*	0.02	1.76	0.33 8.01** 0.10	2.55*	14	1.33 × 10 -5	3.46*
	Block*medium	3	0.20	8.43**	5.8 × 10 -4	0.75	0.02	1.86	0.01	1.83
	medium*ori	4	0.46	1.19	5.15 × 10 -3	0.43	0.21 5.34** 0.12	3.35*	4	6.63 × 10 -6	1.72
	medium*Strain(ori)	14	0.41	17.45**	0.01	15.96**	0.04 4.87** 0.04 6.73**

df : degrees of freedom, MS : Mean Square, F : Fisher's F * p < 0.05, ** p < 0.01 Block and Strain are main random effects while medium (1 and 15% glucose) and habitat of origin (ori: forest, industrial, clinical, fruit and laboratory) are main fixed effects.

Table 3 : Analysis of variance for three metabolic traits: the yield of the fermentation process (Y ferm ), the maximal quantity of ethanol produced in the medium (Eth max ), and the specific glucose consumption rate when 50% of the glucose was consumed (J spec ). Y ferm Eth max J spec

 3

	Sources of Variation	df	MS	F	MS	F	df	MS	F
	Block	3	0.23	0,89	0.93	19.86*
	medium	1	75.41	148,68**	179.63	2436.56**	1	4.59	12.21**
	ori	4	5.11	5,20**	0.10	2.27	4	0.15	0.25
	Strain(ori)	14	1.06	3,02*	0.05	0.91	14	0.59	1.57
	Block*medium	3	0.26	9,86**	0.05	3.13*
	medium*ori	4	0.84	2,57	0.09	1.87	4	0.37	0.98
	medium*Strain(ori)	14	0.35	13,28**	0.05	3.45**

df : degree of freedom, MS : Mean Square, F : Fisher's F *p < 0.05 **p < 0.01 Block and Strain are main random effects while medium (1 and 15% glucose) and habitat of origin (ori: forest, industrial, clinical, fruit and laboratory) are main fixed effects.

Table 4 : Main effect of the habitat of origin on life-history and metabolic traits variation

 4

		Industry	Fruit	Clinical	Laboratory	Forest
	K	2.12 10 7 B	4.36 10 7 AB	4.96 10 7 AB	9.99 10 7 A	9.80 10 7 A
	S cell	6.36 A	5.21 BC	5.36 B	4.81 BC	4.80 C
	R ferm	0.18 B	0.23 AB	0.26 AB	0.31 AB	0.35 A
	Y ferm	3.80 10 6 B	6.26 10 6 AB	7.57 10 6 AB	1.26 10 7 A	1.22 10 7 A

Table 5 : Pearson correlation coefficients between life history traits

 5

	Life-History Traits	K	S cell	R ferm	R resp	T shift
	K	\	-0 . 7 9 b [-0.94, -0.51]	0.87 b [0.54, 0.94]	-0.63 b [-0.85, -0.18]	-0.04 NS [-0.49, 0.46]
	S cell	-0.73 b [-0.88, -0.38]	\	-0.72 b [-0.91, -0.37]	0.82 b [0.49, 0.93]	-0.23 NS [-0.65, 0.27]
	R ferm	0.87 b [0.65, 0.95]	-0.71 b [-0.89, -0.37]	\	-0.54 a [-0.82, -0.01]	-0.37 NS [-0.72, 0.15]
	R resp	-0.79 b [-0.94, -0.23]	0.73 a [0.17, 0.92]	-0.73 a [-0.93, -0.11]	\	-0.46 NS [-0.78, 0.03]
	T shift	-0.74 b [-0.91, -0.40]	0.39 NS [-0.09, 0.72]	-0.81 b [-0.93, -0.52]	0.46 NS [-0.17, 0.86]	\
	Over the diagonal: 15% glucose medium; below the diagonal: 1% glucose medium.

a Pearson correlation coefficients becoming non-significant after the correction for multiple tests (see Material & Methods) b Pearson correlation coefficients still significant after the local FDR procedure NS: Non Significant 95% confidence interval of the estimation of the correlation coefficients are given between brackets

(page number not for citation purposes)

Acknowledgements

The authors would like to thank Pierre Delobel, Sylvie Dequin, Justin Fay, Gianni Liti, and the CIRM-Levures for kindly providing strains. We are grateful to Christine Dillmann for her statistical expertise. We are also grateful to the GQF team for fruitful discussions and critical reading of the manuscript. This work was supported by the french Agence Nationale de la Recherche (ANR Project ADAPTALEVURE n° NT05-4_45721) and a PhD fellowship of the Ministère de l'Enseignement Supérieur et de la Recherche to AS.

Authors' contributions


Esteban Restrepo
email: esteban.restrepo@onera.fr.

Antonio Loria
email: antonio.loria@centralesupelec.fr

Ioannis Sarras
email: ioannis.sarras@onera.fr.

Julien Marzat
email: julien.marzat@onera.fr.

Antonio Loría

Leader-follower Consensus of Unicycles with Communication Range Constraints via Smooth Time-invariant Feedback

Keywords: Formation control, persistency of excitation, Lyapunov design, nonholonomic systems I

come

Therefore, much effort has been spent recently on the design of connectivity maintenance strategies for nonholonomic systems. However, most works in the literature address only the problem of position consensus. Moreover, the consensus protocols used are, for the most part, either non-smooth or time-varying. Besides increasing the complexity of the analysis (use of non-smooth Lyapunov analysis, non-autonomous systems theory, persistency of excitation, etc.), they may give way to undesirable behavior, such as oscillations. In [START_REF] Kan | Ensuring network connectivity for nonholonomic robots during decentralized rendezvous[END_REF] and [START_REF] Kan | Decentralized Rendezvous of Nonholonomic Robots With Sensing and Connectivity Constraints[END_REF] a navigation-function-based time-varying controller with connectivity maintenance is proposed, respectively, for undirected and directed graphs; nevertheless, it presents some problems inherent to the navigation-function framework such as local minima and the need to have a bounded workspace. In [START_REF] Ajorlou | Connectivity preservation in nonholonomic multi-agent systems: A bounded distributed control strategy[END_REF] and [START_REF] Lian | Formation Control and Obstacle Avoidance for Multi-Agent Systems Using Barrier Lyapunov Functions[END_REF] connectivity-preserving controllers are proposed, respectively, for undirected and leader-follower topologies based on barrier functions. However, only position consensus is addressed. In [START_REF] Panagou | Distributed coordination control for multi-robot networks using Lyapunov-like barrier functions[END_REF], position consensus-based formation with connectivity maintenance is achieved using barrier functions but assuming a complete undirected graph, that is, assuming that each agent has access to the information of every other agent in the system at all times, which can prove limiting in realistic practical scenarios. In [START_REF] Williams | Global connectivity control for spatially interacting multi-robot systems with unicycle kinematics[END_REF], a discontinuous controller is presented to guarantee connectivity, but consensus is not considered and global parameters must be estimated, thereby increasing the complexity of the controller. Estimation of global parameters is also used in [START_REF] Poonawala | Collisionfree formation control with decentralized connectivity preservation for nonholonomic-wheeled mobile robots[END_REF] to achieve practical stability of a desired formation, but only position consensus is addressed.

In this paper we present a distributed controller for full consensus (in position and orientation) of nonholonomic vehicles in a leader-follower configuration, under relative distance constraints. More precisely, the full-consensus algorithm proposed in [START_REF] Restrepo | Leader-follower consensus of unicycle-type vehicles via smooth time-invariant feedback[END_REF] is extended herein to address, also, the problem of connectivity maintenance. Remarkably, the proposed control law is smooth (in the domain of definition) time-invariant. Moreover, it has the advantage of relying only on relative measurements of distance-to-follower and line-of-sight angles, which makes our controller more suitable for implementation and practical use. The latter is made possible by employing a polar-coordinates model based on the one proposed in [START_REF] Aicardi | Closed loop steering of unicycle like vehicles via Lyapunov techniques[END_REF]. We also remark that the leader-follower configuration of the robots means that the graph topology corresponds to that of a (minimal) directed spanning tree.

In Section II are presented the model and the problem statement. The main results are presented in Section III and are illustrated via experimental results in Section IV. Some concluding remarks are given in Section V.

II. MODEL AND PROBLEM STATEMENT

Notation. The real n-coordinate space, with n ∈ N, is denoted as R n ; R n ≥0 and R n >0 are the sets of real n-vectors with all elements non-negative and positive, respectively. The notation x is used for the Euclidean norm of a vector x ∈ R n . A function γ : R ≥0 → R ≥0 is said to be of class K (γ ∈ K), if it is continuous, strictly increasing and zero at zero. If moreover γ(s) → ∞ as s → ∞, we say that γ ∈ K ∞ . A digraph, denoted G = (V, E), is defined by a set of nodes, V := {1, 2, . . . , n} whose elements correspond to the labels of the agents' states and a set of edges, E ⊆ V 2 of cardinality m, that represents the communication between a pair of nodes. A directed edge e k , with k ≤ m, is an ordered pair (i, j) ∈ E if and only if a connection exists from node i to node j. The distance d(i, j) between nodes i, j ∈ V is the number of edges in the shortest path from i to j. A directed tree is a subgraph consisting in a root node, with no parent, and a set of nodes reachable from the root. A directed spanning tree G T ⊂ G is a directed tree containing all the nodes in G.

Unicycle systems are typically modelled by the equations

ẋj = v j cos θ j (1a) ẏj = v j sin θ j (1b) θj = ω j , j ≤ n (1c)
where q j = [x j , y j ] ∈ R 2 is the vector of Cartesian coordinates, θ j ∈ (-π, π] denotes the vehicle's orientation with respect to the axis of the abscissae, and the control inputs are the linear speed, v j ∈ R, and the angular velocity, ω j ∈ R. One of the best known characteristics of nonholonomic systems (1) is that, in general, equilibria in the space of (x, y, θ) are not reachable via smooth time-invariant feedback.

In [START_REF] Lin | Necessary and sufficient graphical conditions for formation control of unicycles[END_REF] necessary conditions for stabilisability of the positionconsensus manifold (i.e., disregarding orientations) via smooth invariant feedback are given.

In [START_REF] Aicardi | Closed loop steering of unicycle like vehicles via Lyapunov techniques[END_REF] an alternative, polar-coordinates-based, model for unicycles is proposed. Such model is not defined at the origin (zero distance to the target point), but equilibria are reachable via smooth time-invariant feedback. Furthermore, used in a leader-follower configuration, this model has the additional advantage of naturally leading to the design of controllers that rely only on local relative measurements. After [START_REF] Aicardi | Closed loop steering of unicycle like vehicles via Lyapunov techniques[END_REF], for every pair of leader and follower vehicles, labelled i and j respectively, let ρ k denote the distance separating them, let β k denote the angle between the line of sight and the leader's direction of motion, and let α k denote the angle between the line of sight and the follower's direction of motion -see Figure 1. That is, ρ k := q i -q j (2a)

β k := arctan y i -y j x i -x j -θ i , ∀ρ k > 0 (2b) α k := arctan y i -y j x i -x j -θ j , ∀ρ k > 0 (2c)
Note that the three-dimensional space of (x j , y j , θ j ) is mapped into another space of dimension 3, corresponding to the relative coordinates

(ρ k , β k , α k ) ∈ R ≥0 × (-π, π] 2 .
Indeed, ρ k = 0 and β k = α k is equivalent to q i = q j and θ i = θ j . Therefore, the solutions to Eqs. (3) correspond to the leader-follower relative error trajectories for the pair of index k and the full consensus control goal is reached if (ρ k , β k , α k ) → (0, 0, 0) asymptotically for all k ≤ m, where m corresponds to the number of pairs of leaders-followers. Then, from a control viewpoint, a network of agents interacting with each other in a leader-follower configuration, corresponds to m interconnected dynamical systems,

ρk = v i cos β k -v j cos α k (3a) βk = 1 ρ k [-v i sin β k + v j sin α k ] -ω i (3b) αk = 1 ρ k [-v i sin β k + v j sin α k ] -ω j , (3c)
which result from differentiating on both sides of (2) with respect to time and using (1). In the latter equations v j and ω j are the control inputs, and v i and ω i , which are respectively the leader's velocity and angular rate, are considered as external signals.

For the purpose of analysis, the interconnections are represented using a generic spanning-tree graph in which a triple (ρ k , β k , α k ) corresponds to the state of an edge e k in the tree -see Figure 2. A sequence of one-leader-one-follower pairs forms a directed path and the overall dynamical system has a convenient cascaded structure [START_REF] Maghenem | Lyapunov functions for persistentlyexcited cascaded time-varying systems: application in consensus analysis[END_REF], in which the dynamics of each subsystem corresponds to (3). As we show farther below, the cascaded structure is conserved for general spanning-tree topologies; this is fundamental to our control approach.

:

: :

i j : : : Now, while the existence of a directed spanning tree is necessary for consensus, taking this for granted may be conservative in certain applications. In this paper, we develop upon the preliminary results obtained in [START_REF] Restrepo | Leader-follower consensus of unicycle-type vehicles via smooth time-invariant feedback[END_REF] to design controllers that ensure the following property.

• • • • • •
Definition 1 (Connectivity maintenance): For each k ≤ m, let ∆ k > 0 denote the maximal distance between the leaderfollower pair i and j such that the communication between them, through the arc e k = (i, j), is reliable. We say that the graphs connectivity is maintained if the set

J := ρ k ∈ R ≥0 : ρ k < ∆ k , ∀ k ≤ m , (4)
where

ρ k is defined in (2a), is forward invariant. That is, if ρ k (0) < ∆ k implies that ρ k (t) ∈ J for all t ≥ 0.
The design of controllers that guarantee connectivity maintenance relies on so-called barrier Lyapunov functions. In turn, the latter are defined as the anti-derivative of so-called connectivity potential functions.

Definition 2 (Connectivity potential):

Let p 0 ∈ R and, for each k ≤ m, let B ∆ k := {ρ k ∈ R ≥0 : ρ k < ∆ k }. Let φ k : 0, ∆ 2 k → R ≥0 , s → φ k (s), be C 1 and non-decreasing on 0, ∆ 2 k , such that φ k (s) → ∞ as s → ∆ 2
k , and the connectivity potential

p k : B ∆ k → R >0 , defined as p k (ρ k ) := ∂φ k ∂s (ρ 2 k ), (5)
is also non-decreasing, p k (ρ k ) ≥ p 0 > 0 for all ρ k < ∆ k , and

p k (ρ k ) → ∞ as ρ k → ∆ k .
Then, we define a barrier function 1 U k :

B ∆ k → R ≥0 as U k (ρ k ) := φ k (ρ 2 k ) (6)
and it satisfies

∂U k ∂ρ k = 2p k (ρ k )ρ k . (7)
Thus, the control problem is to define, for each j ≤ n, control laws v j and ω j such that, for the system (3), (ρ k , β k , α k ) → (0, 0, 0) asymptotically for all k ≤ m and that connectivity, according to Definition 1, is maintained for all initial conditions such that ρ k (0) ∈ J and for all t ≥ 0.

III. MAIN RESULTS

A. Control approach

Before presenting the control laws that solve the problem of full consensus with connectivity maintenance, we first introduce the rationale used for their design. Exploiting the natural cascaded structure of the system, we follow a backstepping procedure. To see this more clearly, consider first the system (3) for a single edge e k with zero leader velocities, that is, v i = ω i = 0. It is clear from (3) that the angular rate ω j directly affects only the dynamics of α k , whereas the evolution of ρ k and β k are determined by α k . Hence, the first step is to design the actual control input v j and a virtual control input 1 Examples of functions satisfying the properties and Definition 2 are the logarithmic barrier Lyapunov functions proposed in [START_REF] Tee | Barrier Lyapunov functions for the control of output-constrained nonlinear systems[END_REF]. that α * k (0, 0) = 0, in order to make ρ k (t) → 0 and β k (t) → 0 asymptotically. Defining the virtual input

α * k : R ≥0 × R → (-π/2, π/2); (ρ k , β k ) → α * k (ρ k , β k ) such
α * k := arctan(-c 3 β k ), c 3 > 0, (8)
and using the identities

sin(arctan(s)) = s √ 1 + s 2 , cos(arctan(s)) = 1 √ 1 + s 2 ,
we obtain a dynamical subsystem of the form

ρk = - v j 1 + (c 3 β k ) 2 , βk = -c 3 v j ρ k 1 + (c 3 β k ) 2 β k .
Note that the latter can be rendered asymptotically stable by taking the input v j proportional to ρ k . Next, defining the error variable αk := α k -α * k , we obtain

ρk = - v j 1 + (c 3 β k ) 2 -v j [cos(α k ) -cos(α * k )] (9a) βk = -c 3 v j ρ k 1 + (c 3 β k ) 2 β k + v j [sin(α k ) -sin(α * k )] (9b) αk = v j ρ k sin α k -α * k -ω j , (9c)
so, following a backstepping procedure, the angular rate ω j is designed so that αk → 0, or equivalently, α k → α * k . The previous control design is effective in stabilizing one robot to a point without considering proximity constraints. For the purpose of leader-follower consensus of multi-agent systems (3) we follow the previous ideas and, to satisfy the connectivity-maintenance requirement, the input v j is not simply chosen proportional to ρ k , but as a function of the gradient of a barrier function W k : B ∆ k → R ≥0 which encodes the distance constraints. This function is defined as

W k (ρ k ) := 1 2 ρ 2 k + κ ρ 2 U k (ρ k ), (10)
where κ ρ > 0 is a design parameter and U k is as in (6). Then, denoting the gradient of

W k as ∂ ρ W k := ∂W k ∂ρ k
, we introduce the distributed control laws that solve the full consensus problem with connectivity maintenance as:

v j := c 1 k≤m a jk η k ∂ ρ W k (ρ k ), η k := 1 + (c 3 β k ) 2 (11a) ω j := k≤m a jk   c 2 αk + ψ k + 1 + c 3 η 2 k sin(α k ) ρ k i≤n a ik v i   (11b)
where c 1 , c 2 > 0 are design constants, α * k is defined in [START_REF] Kan | Decentralized Rendezvous of Nonholonomic Robots With Sensing and Connectivity Constraints[END_REF],

ψ k :=-∂ ρ W k [cos(α k ) -cos(α * k )] αk + β k ρ k [sin(α k ) -sin(α * k )] αk , (12)
a jk := 1 if edge e k is incident on node j 0 otherwise. ( 13
)
B. The multi-agent system in closed loop So far, we considered the leader-follower pair (3) as an individual system. Consider, now a multi-agent system composed of n unicycles communicating through an arbitrary directed spanning tree. Each robot has only one leader, but may have several followers, so the tree has h ≤ n -1 levels based on the distance to the root. Now, let E p ⊂ E denote the set of edges such that the distance from its terminal node to the root of the tree, labelled "1", is equal to p ≤ h, i.e., E p := {e k = (i, j) ∈ E : d(1, j) = p}. Without loss of generality, assume that each level p of the tree contains an l p number of edges, such that 1 ≤ l p ≤ m, h p=1 l p = m -see Figure 2. Then, we define a multi-variable model containing the three states of all the edges belonging to a level of the tree. To that end, for each level p having l p arcs labelled e k with k ∈ [l p-1 + 1, l p ] we define the closed-loop state variables

ξ p := ξ p,1 • • • ξ p,lp , ξ p,k := [ρ k β k αk ] . (14)
Note that the dimension of ξ p is 3l p , that is, it depends on the number of arcs in the tree level. Using this notation, the systems (3) in closed loop with [START_REF] Panagou | Distributed coordination control for multi-robot networks using Lyapunov-like barrier functions[END_REF], with k ≤ m and for the considered graph, can be written in the compact cascaded-system form,

                   ξh = f h (ξ h ) + g h (ξ h , ξ h-1 ), . . . ξp = f p (ξ p ) + g p (ξ p , ξ p-1 ) . . . ξ2 = f 2 (ξ 2 ) + g 2 (ξ 2 , ξ 1 ) ξ1 = f 1 (ξ 1 ) (15)
where, for each p ≤ h, f p (ξ p ) := f p,1 (ξ p,1 ) . . . f p,lp (ξ p,lp ) , g p (ξ p , ξ p-1 ) := g p,1 (ξ p,1 , ξ p-1 ) . . . g p,lp (ξ p,lp , ξ p-1 ) , and the nominal system, ξp,k = f p,k (ξ p,k ), corresponds to

ρk = -c 1 ∂ ρ W k 1 + [cos(α k ) -cos(α * k )]η k (16a) βk = - c 1 ρ k ∂ ρ W k c 3 β k -[ sin(α k ) -sin(α * k ) η k (16b) αk = -c 2 αk -c 1 ψ k η k ∂ ρ W k (16c)
where we recall that α k = αk + α * k . The interconnection term g p (ξ p , ξ p-1 ) depends on states relative to the p-th level in the tree and to the previous one in the following way. Fix k ∈ [l p-1 + 1, l p ] and r ∈ [l p-2 + 1, l p-1 ] in a manner that the edge e r ∈ E p-1 is incident on e k ∈ E p , that is, so that the terminal node of e r is the initial node of e k -see Figure 2. Let ξ p-1,r := [ρ r β r αr ] be the state associated to e r . Then,

g p,k (ξ p,k , ξ p-1 ) =   c 1 cos(β k )η r ∂ ρ W r gβ (ξ p,k , ξ p-1,r ) gα (ξ p,k , ξ p-1,r )   , (17)
where

η r := 1 + (c 3 β r ) 2 , gβ := -c 1 η r ∂ ρ W r sin(β k ) ρ k + 1 + c 3 η 2 r sin(α r ) ρ r + ψ r -c 2 αr and gα := - c 2 c 3 η 2 k αr -c 1 η r ∂ ρ W r c 3 η 2 k ψ r + 1 + c 3 η 2 r sin(α r ) ρ r + 1 + c 3 η 2 k sin(β k ) ρ k ( 18
)
where α r = αr + α * r . We stress that ∂ ρ W r is a function of ρ r only and [∂ ρ W r ](0) = 0. Therefore, from the definition of g p we have g p (ξ p , 0) ≡ 0. Hence, based on cascaded-systems theory [START_REF] Panteley | Growth rate conditions for uniform asymptotic stability of cascaded time-varying systems[END_REF], one can assert that if for every p ∈ [2, h + 1] the solution of ξp-1 = f p-1 (ξ p-1 ) converges to zero and if, for every p ∈ [2, h], the solutions of ξp = f p (ξ p )+g p (ξ p , ξ p-1 ), denoted ξ p (t), remain bounded, we also have ξ p (t) → 0. This is established in our main statement, which is presented below.

C. Main statement

Proposition 1 (Main result): Consider n unicycle agents described by ( 1) and communicating over a directed spanning tree G T (V, E). The smooth time-invariant controller ( 11)-( 13) achieves full consensus with connectivity maintenance, i.e., q i → q j , θ i → θ j and ρ k (t) ∈ J , for all e k = (i, j) ∈ E, k ≤ m, and for all initial conditions (ρ k (0),

β k (0), α k (0)) such that ρ k (0) ∈ J \{0} -see Definition 1.
Proof: The proof follows the rationale of [19, Lemma 1]. To that end we establish that for each nominal system, ξp = f p (ξ p ), we have ξ p (t) → 0 and that the solutions of (15) are bounded. Assume, for the time-being (this assumption will be proven later), that the solutions of [START_REF] Aicardi | Closed loop steering of unicycle like vehicles via Lyapunov techniques[END_REF] are such that ρ k (t) ∈ J for all k ≤ m and all t ≥ 0. Let k ≤ m and p ≤ h be arbitrarily fixed and for the edge e k ∈ E p , consider the Lyapunov function candidate

V p,k (ξ p,k ) = W k (ρ k ) + 1 2 α2 k + 1 2 β 2 k . (19)
Its total derivative along the trajectories of ( 16) -see also [START_REF] Williams | Global connectivity control for spatially interacting multi-robot systems with unicycle kinematics[END_REF], satisfies

Vp,k (ξ p,k ) = -c 1 ∂ ρ W k 2 -c 2 α2 k - c 1 c 3 [∂ ρ W k ] ρ k β 2 k . (20)
Now, from equations ( 7), [START_REF] Lian | Formation Control and Obstacle Avoidance for Multi-Agent Systems Using Barrier Lyapunov Functions[END_REF], and Definition 2, we have

Vp,k (ξ p,k ) ≤ -c 1 ρ 2 k -c 2 α2 k -c 3 β 2 k ≤ -c ξ p,k 2 < 0, (21)
where

c := min{c 1 , c 2 , c 1 c 3 (1 + κ ρ p 0 )}. Next, consider the function V p (ξ p ) = lp k=1 V p,k (ξ p,k ). (22)
In view of (21), we have

Vp (ξ p ) ≤ -c ξ p 2 < 0. (23)
Since V p is positive definite and Vp is negative definite on its domain of definition, we conclude that the origin for the nominal system ( 16) is asymptotically stable at the origin. Next, we establish boundedness of the solutions of [START_REF] Aicardi | Closed loop steering of unicycle like vehicles via Lyapunov techniques[END_REF]. For that purpose, fix p ≤ h arbitrarily and consider the (p -1)-th and the p-th equations of the cascaded system [START_REF] Aicardi | Closed loop steering of unicycle like vehicles via Lyapunov techniques[END_REF].

In view of ( 17)-( 18), for any r and k as chosen previously (such that the edge e k is incident on e r ), the interconnection terms g p,k (ξ p,k , ξ p-1 ) satisfy, component-wise,

g p,k (ξ p,k , ξ p-1 ) ≤     γ ρ ( ξ p-1,r ) max 1, 1 ρ k γ β ( ξ p-1,r ) max 1, 1 ρ k γ α ( ξ p-1,r )     , (24)
where γ ρ (s), γ β (s), γ α (s) ∈ K ∞ and we recall that ξ p-1,r = [ρ r β r αr ] is the r-th entry of ξ p-1 . Then, consider the Lyapunov function in [START_REF] Panteley | Growth rate conditions for uniform asymptotic stability of cascaded time-varying systems[END_REF] 20) and (24), we have

with p = 2, k ∈ [l 1 + 1, l 2 ], and r ∈ [1, l 1 ]. From (
V2,k (ξ 2,k ) ≤-c 1 ∂ ρ W k 2 -c 2 α2 k -c3 β 2 k + |∂ ρ W k | γ ρ ( ξ 1,r ) + max 1, 1 ρ k |β k |γ β ( ξ 1,r ) + |α k | γ α ( ξ 1,r ) . (25)
Assume, first, that max{1, 1/ρ k } = 1. Then, let λ 1 , λ 2 , λ 3 > 0 be sufficiently large so that c 1 := c 1 -1 2λ1 > 0, c 2 := c 2 -1 2λ3 > 0, and c 3 := c3 -1 2λ2 > 0. In view of Young's inequality, from (25) we have

V2,k (ξ 2,k ) ≤ -c 1 [∂ ρ W k ] 2 -c 2 α2 k -c 3 β 2 k + λ 1 2 γ ρ ( ξ 1,r ) 2 + λ 2 2 γ β ( ξ 1,r ) 2 + λ 3 2 γ α ( ξ 1,r ) 2 ≤ -c ξ 2,k 2 + γ( ξ 1,r ) (26)
where c

:= min {c 1 , c 2 , c 3 } and γ( ξ 1,r ) := λ1 2 γ ρ ( ξ 1,r ) 2 + λ2 2 γ β ( ξ 1,r ) 2 + λ3 2 γ α ( ξ 1,r ) 2
. Now, let max{1, 1/ρ k } = 1/ρ k . For any δ > 0 and for any ρ k ≥ δ, we have max{1, 1/ρ k } ≤ 1/δ. Then, define λ 4 , λ 5 , λ 6 > 0 such that c 1 := c 1 -1 2λ4δ > 0, c 2 := c 2 -1 2λ6δ > 0, and c 3 := c3 -1 2λ5δ > 0. Applying Young's inequality on (25), we obtain

V2,k (ξ 2,k ) ≤ -c ξ 2,k 2 + 1 δ γ( ξ 1,r ) (27)
where, c := min{c 1 , c 2 , c 3 }. Therefore, from (26) and ( 27), we see that the function V p in (22) with p = 2, satisfies

V2 (ξ 2 ) ≤ -c ξ 2 2 + γ( ξ 1 ) (28)
where γ( ξ 1 ) := max{1, 1 δ } l1 r=1 γ( ξ 1,r ) and c = min{c , c }. Assume now that the solutions t → ξ 2 (t) grow unboundedly. Since ξ 1 (t) is bounded, there exists t such that V2 (ξ 2 (t)) ≤ 0 for all t ≥ t , which leads to a contradiction. That is, ξ 2 (t) is bounded. Furthermore, since ξ 1 (t) → 0 it follows that, also, ξ 2 (t) → 0. The previous arguments hold for p = 3 and, by induction, for any p ≤ h.

So far we assumed that ρ k (t) ∈ J for all t ≥ 0. We show next that this holds under the Proposition's assumption that ρ k (0) ∈ J \{0}. We proceed by contradiction. Suppose that there exists T > 0 such that for all t ∈ [0, T ) and at least one k ≤ m, ρ k (t) ∈ J and ρ k (T ) / ∈ J . Then, from the definition of the barrier functions W k , we have that W k (ρ k (t)) → ∞. This, however, contradicts (23) and (28), which imply that W k (ρ k (t)) is bounded for all t ≥ 0 and all k ≤ m. Connectivity maintenance (equivalently, forward invariance of J ) follows.

IV. EXPERIMENTAL RESULTS

To illustrate our formal results, some experiments were performed with four Nexter Robotics' Wifibots and the Robot Operating System (ROS) interface were used for the implementation of the control law. An Optitrack motion capture system based on active IR cameras and markers was used which, coupled with odometry sensors, allowed us to obtain positions and velocities of the robots for analysis purposes.

For the tests we consider a leader-follower full-consensusbased formation scenario, rather than a generic consensus one, in order to prevent collisions between the agents when close to the consensus point. It is assumed that the four mobile robots interact through a directed spanning tree as illustrated in Figure 3. The leader is static due to space limitations in the test facility. The results are depicted in Figures 45678for initial conditions (x 1 (0), y 1 (0), θ 1 (0)) = (1.5, 2.2, 0), (x 2 (0), y 2 (0), θ 2 (0)) = (-1.3, 2.2, -1.9), (x 3 (0), y 3 (0), θ 3 (0)) = (-1.5, -0.5, 1.6), and (x 4 (0), y 4 (0), θ 4 (0)) = (1.2, 0.3, -2.8). In the testscenario each robot was subject to a limited communication range, hence imposing distance-based connectivity constraints. These constraints are encoded by the barrier function [START_REF] Lian | Formation Control and Obstacle Avoidance for Multi-Agent Systems Using Barrier Lyapunov Functions[END_REF] as

U k (ρ k ) := ln ∆ 2 k ∆ 2 k -ρ 2 k
, where the radii of the communication ranges were set to ∆ 1 = 2.7 m, ∆ 2 = 3.4 m, and ∆ 3 = 4.2 m.

In Figure 4 is presented the motion of the vehicles. The blue dot represents the position of the static leader and the red dots are the desired positions of each agent with respect to its respective leader as defined by the interaction graph showed in Figure 3. It is clear from Figures 5 and6 that the group of agents successfully achieve the desired formation with consensus on the orientation. Additionally, in Figure 6 it can be appreciated that all distance constraints (dashed lines) are respected, thus guaranteeing connectivity maintenance. In Figures 7 and8 are presented the control inputs for the four agents of the system. It is evident from the figures that the control inputs are smooth, as claimed. We clarify that the apparent "dripping" in the curves on Figures 7-8 is due to position-measurements noise coming from the motion capture system of our experimental benchmark. The effect of such noise can also be appreciated in Figures 4 and6.

V. CONCLUSIONS

In this paper we presented a smooth time-invariant distributed feedback control law that solves the full consensus problem for swarms of unicycles with communication range constraints and interconnected through a directed-spanningtree communication topology. The control methodology is based on barrier Lyapunov functions and a polar-coordinatesbased model. The latter allows the use of smooth timeinvariant control laws and transforms the consensus problem into a stabilization one so that it may be analysed through classical Lyapunov theory. Furthermore, the proposed con-troller uses only relative information, making it well suited for practical applications.

Current and future work focuses on more general digraph topologies, higher-order systems, obstacle avoidance, and 3D autonomous vehicles.

Fig. 1 .

 1 Fig. 1. Leader-follower scheme and polar-coordinates variables

Fig. 2 .

 2 Fig. 2. Directed spanning tree G T . Open directed chain illustrated in red

3 Fig. 3 .

 33 Fig. 3. Directed-tree topology used in experiments.

Fig. 4 .

 4 Fig. 4. Motion of the vehicles.

Fig. 5 . 3 Fig. 6 .Fig. 7 .Fig. 8 .

 53678 Fig. 5. Trajectories of the orientation of the vehicles.

The work of A. Loría was supported by the French ANR via project HANDY, contract number ANR-18-CE40-0010 and by CEFIPRA under the grant number 6001-A.