Olivier Simonin

François Charpillet

Eric Thierry

Olivier Simonin -Franc

Charpillet -Eric Thierry

Collective construction of numerical

Keywords:

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

Swarm intelligence is now recognized as a robust and flexible approach to deal with distributed problem in complex environments. Synthetic phromones is one of the most popular swarm techniques that provides adaptive solutions to problems such as path-planning [START_REF] Van Dyke | Digital pheromones for autonomous coordination of swarming UAV's[END_REF] [START_REF] Sauter | Evolving adaptive pheromone path planning mechanisms[END_REF], patrolling [START_REF] Sempe | Adaptive patrol for a group of robots[END_REF] [START_REF] Sauter | Performance of digital pheromones for swarming vehicle control[END_REF] and foraging [START_REF] Panait | A pheromone-based utility model for collaborative foraging[END_REF].

In these days of ubiquitous and cheap computing, the implementation of swarm and collective systems in real world has become more realistic and imaginable. Workplaces, for example, are already equipped with pervasive sensors and ad hoc, self-organized wireless networks (see [START_REF] Mamei | Field-Based Coordination for Pervasive Multiagent Systems[END_REF] for details). The RFID technology makes possible to deploy of hundreds of sensors in indoor environments or, to spread them out in the thousands outdoors (as dust sensors, [START_REF] Kahn | Next century challenges: Mobile networking for "smart dust[END_REF]).

In this paper we re-examine such an environment-based approach to study optimal path planning and exploration for the foraging problem in complex environments. The foraging problem is defined as a group of autonomous agents (such as robots) exploring an environment for resources to bring back to a base (see [START_REF] Steels | Cooperation between distributed agents through self-organization[END_REF]). Distributing a foraging activity among a group of agents is particularly challenging when the environment is unknown (no map, no information about obstacles) and contains "awkwardly" shaped obstacles. The lack of environmental knowledge is typical of most realistic situations, such as military campaigns (e.g., the transport of supplies in a hazardous terrain), rescue tasks (e.g., surveillance of catastrophe-hit areas) [START_REF] Asada | The robocup physical agent challenge: Phase I[END_REF] and planet exploration (e.g., robotic rovers that search for interesting rock samples on a planet [START_REF] Steels | Cooperation between distributed agents through self-organization[END_REF] [START_REF] Brooks | Lunar base construction robots[END_REF]).

Ants inspired a standard pheromone-based technique to forage with agents/robots [START_REF] Deneubourg | Random behaviour, amplification processes and number of participants : How they contribute to the foraging properties of ants[END_REF] [11] [START_REF] Resnick | Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds[END_REF]. In this model agents drop pheromones in the environment in order to build gradients from resources to their base [START_REF] Bonabeau | Swarm Intelligence: From Natural to Artificial Systems[END_REF]. This approach, though each agent itself is very simple, requires a large mass of agents and a considerable amount of time for best paths to emerge. Moreover, the pheromone-based technique requires the computation of propagation and evaporation dynamics. Another drawback of this approach is that each agent needs an ad-hoc mechanism for getting back home (for example, compass information). [START_REF] Resnick | Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds[END_REF] and [START_REF] Panait | A pheromone-based utility model for collaborative foraging[END_REF] proposed to use a second pheromone diffusing from the base in order to avoid this problem, but without guaranteeing to build no local minimal in complex environments.

In this paper we explore an original approach that allows to build optimal paths for foraging using only reactive (simple) agents, who do not have a map of the environment, and in which the environment is used as a shared memory but not requires any particular dynamics. We define agents that do not use pheromones, but instead directly write a gradient as they explore and discover the environment. Such an approach is inspired from centralized planning in which the environment is known. We refer to popular techniques based on Artificial Potential Fields (APFs) approaches [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF][15] [START_REF] Arkin | Behavior Based Robotics[END_REF].

The APF contruction algorithm proposed in [START_REF] Barraquand | Numerical potential field techniques for robot path planning[END_REF] is promising in this regard since it prevents the formation of local minima while computing the shortest paths to the agent destination. In this paper, we define a distributed and asynchronous version of the [START_REF] Barraquand | Numerical potential field techniques for robot path planning[END_REF] algorithm. We prove that our algorithm converges to the optimal APF, i.e., shortest paths are indeed found. Then we show that the model can be efficiently applied to foraging tasks. Performances are analysed and compared to the standard ant-model.

The rest of paper is organized as follows. In section 2, we describe [START_REF] Barraquand | Numerical potential field techniques for robot path planning[END_REF] algorithm; specifically, the construction of a numerical potential field and optimal path execution. In section 3, we describe a reactive multiagent system that builds the numerical potential field and prove its convergence to the optimal APF. In section 4, this system is extended to tackle the foraging problem (the corresponding algorithms are given in detail). Then, in section 5, we report statistical measures on performance and comparisons with the ant model. In Section 6, we discuss related work and some clues for a real-world implementation of our approach. Finally, in section 7, we summarize our conclusions.

Barraquand's numerical potential field

In order to define agents that can compute optimal paths in a complex environment, we first examine the pre-computed map proposed by Barraquand and colleagues [3] [4]. In the next section, we show how this global pre-computation can be distibuted in a reactive multi-agent system and later, in section 4, applied to the foraging task. In Barraquand's approach, the environment is represented as a grid. This facilitates the building of potential fields numerically, rather than analytically. Local minima are avoided by computing a "wavefront expansion" from the agent destination, which involves building an ascending APF incrementally. The environment is represented as a 2D-array of cells and it is denoted by E (see e.g. Figure 1.a). E empty denotes the subset of E containing all positions free of obstacles. Each point x = (i, j) ∈ E has a maximum of 4 neighbours: {(i -1, j), (i + 1, j), (i, j -1), (i, j + 1)}. A potential field is a function V : x ∈ E empty -→ V (x) ∈ R Let x goal be the goal position of the robot in E empty . The Wave-potential V is computed as shown in Algorithm 1 (L i denotes a list of points in E). The algorithm terminates when E empty has been totally explored. For every cell x ∈ E empty , set V (x) to infinity (e.g., a large number M) Set V (x goal ) to 0 and the list L 0 to (x goal ), i = 0 While L i is not empty Do initialize L i+1 to the empty list, For every point x in L i , For every neighbour y of x in E empty , if V (y) = M then set V (y) to i + 1 and insert y at the end of

L i+1 i = i + 1
result of the algorithm execution on a test environment where the goal position is located at the letter G (each point has a potential value representing the minimum distance to the goal).

We remark that this algorithm is essentially the classic BFS (Breadth First Search) algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF], which computes the path with the least cost between two vertices in a graph, applied to the task of robotic path planning by discretizing the environment. Using this computation, an agent can now reach the goal by just following the flow of the negative gradient vector field --→ ▽V . In a numerical potential field, such a behavior is called a "descent" and is defined as: at every iteration, the agent examines the potential values of the four neighbouring cells and moves to the cell with the smallest value (ties are broken arbitrarily).

In Figure 1.b the agent is represented by a circle and the black cells represent a descent path. The following two properties hold for Algorithm 1 (see details in [START_REF] Barraquand | Numerical potential field techniques for robot path planning[END_REF]): Property 1: In the Wave f ront numerical potential field produced by Algorithm 1, an agent that always moves to the neighbouring cell with the smallest potential value arrives at the goal location succeeding to avoid all obstacles. Property 2 : From any location in the Wave f ront numerical potential field, the path induced by Property 1 is the shortest.

Our objective is to conceive a multiagent approach to build a numerical potential field such as the one produced by Algorithm 1. We therefore define a distributed and asynchronous version of Algorithm 1 (i.e., the Barraquand Algorithm).

WaveFront computation with reactive agents

As stated before, we are interested to deploy agents that do not have information about their environment. Then the algorithm 1 we just described cannot be directly computed before launching agents for a task such as foraging. We therefore propose to transform the algorithm in a group of reactive agents able to build a comparable numerical potential field while exploring the environment. Reactive agents have no individual memory abilities but can cooperate and build patterns through indirect communication. This form of communication is embedded in the environment. It takes its inspiration from ants that drop pheromones as markings to be read at a later time by others (including possibly themselves) [START_REF] Holldobler | The Ants[END_REF]. The environment allows to aggregate the local interactions of numerous agents in order to build collective patterns. Such a process is called swarm intelligence ( [START_REF] Bonabeau | Swarm Intelligence: From Natural to Artificial Systems[END_REF]). The environment is then treated as a shared memory in which information can be stored and erased. Thus we have the central idea of our model: we treat the numerical values of the APF to build as markings that can be laid down and updated by agents.

Simple "marking agents"

We now describe the environment and the agents used for the APF construction. The environment is discretized in regular cells. At any time, agents do not know their global location, they just occupy a cell and perceive the 4 neighbour ones. Without loss of generality, in the interest of simplicity, we allow multiple agents to occupy a cell at the same time. Each agent is capable of,

• reading and writing integers values on the cell at which he currently is,

• perceiving the 4 neighbouring cells: detecting if any of the cells is an obstacle and reading their values • moving to a neighbouring cell that is not an obstacle We call such agents marking agents. Initially, the value of the goal cell is 0 and all the agents are placed on it (agents can start from any position but the construction is then slower).

The wavefront potential is collectively and incrementaly built around the initial value through the actions of the agents. Each agent repeatedly follows the steps as represented by Algorithm 2 (EXPLORATION & APF CONSTRUCTION). After choosing a cell and moving, the agent computes the UPDATE-VALUE operation which corresponds to a local wavefront expansion (when moving from a wavefront cell to a cell not yet visited). Then the shortest path from this new cell to the goal cell, in the current wavefront, is equal to the shortest path to a neighbouring cell + 1 (one move). The update operation is performed if the new value is lower than the current one.

Algorithm 2 EXPLORATION & APF CONSTRUCTION (Agent behavior) EXPLORATION

IF there exist neighbouring cells without a value THEN move randomly to one of them and UPDATE-VALUE ELSE move randomly to a cell which is not an obstacle and UPDATE-VALUE

UPDATE-VALUE Operation

Compute val = min(val, 1 + min(4-neighbour values)) Write (update) val in current cell As the movements of the agents are based on a random walk, they explore the environment while they mark it. However, it is not just a random exploration because the values of the cells (the markings) influence the choice of each agent in selecting a cell to move to: each agent favors unmarked cells over marked ones (see the first line of algorithm 2). As a consequence, their exploration progresses as a partial circular front around the starting cell. Figure 2.a shows such a progression with 3 agents. The number of agents will not be generally sufficient to sustain an entire circular front progression. So one exploration step, when all the agents move, is not equivalent to one loop of algorithm 1. Figure 2.b shows a situation where the cell with value 13 has clearly not reached the value of the shortest distance to G (which is 11, see Figure 2.c). Then agents may need to visit several times the same cell in order it reachs its optimal value. As the environment is bounded, the time necessary to obtain the complete optimal potential field is also bounded, i.e. the algorithm converges (Figure 2.c), see proof below.

Convergence

Theorem 3.1 In a bounded discrete environment containing a destination cell c 0 with potential 0 and some obstacles, a set of agents that follow algorithm 2 build in a finite time the entire wavefront from c 0 , i.e. the optimal APF. Proof: we define the following subset: let L i denote the set of cells which attain the value i such that the distance to c 0 is i (i.e. a path with optimal length i). It follows that when all L i sets are built, the system has converged to its final state (the optimal APF). In order to proove covergence to the optimal APF, we need to show that each L i is built in finite time. For this purpose, we consider the succesive constructions, L 0 , L 1 , L 2 , . . . Note that L 0 is equal to the single cell c 0 , which is assigned its optimal value 0 before agents begin exploring. The proof then involves showing inductively that if L n has been built, the system will compute L n+1 in a finite time. Assume L n is already built. Each cell c j in L n+1 is necessarily a neighbouring cell of some cell in L n cell. Indeed, the maximum gradient difference between two cells in the optimal APF is one. So, when any c j cell is visited, its value changes to the final value n + 1. This value cannot be lower, otherwise the cell would belongs to some set L k with k ≤ n, but each such set has been already built, so that c j is not an element of any such set. Moreover, this value cannot be higher due to the definition of the Update operation (algo. 2). So, to build L n+1 from L n , each cell in L n+1 must be visited at least once. Visiting each cell in L n+1 takes a finite time because agents do a random walk. Indeed Alg. 2 guarantees that each cell of the environment will be visited once with probability 1, in a finite time. As each L i is built in a finite time, the sum of times required to build L 1 , L 2 ,.. and L max is also finite. The assumption that the environment is bounded implies that L max exists. Thus convergence is proved.

Note that while the participation of multiple agents speeds up convergence (see section 5), this result is true even when only one agent is deployed. The next section shows how this multi-agent construction can be efficiently applied to the problem of collaborative foraging.

INRIA 4 Application to collaborative foraging 4.1 The multi-source foraging problem

In collaborative foraging, also known as the exploring robots problem [START_REF] Steels | Cooperation between distributed agents through self-organization[END_REF], mobile agents such as robots search for resources in a designated area, and transport found resources back to a base. Additionally, they may be required to return to the places where they found resources if they could not collect all the resources at those places in earlier trips. The robots are assumed to have no knowledge of the environment. The environment may and usually does contain obstacles. The difficulty of foraging depends on the number and shape of obstacles present. In practice, this last assumption -that the robots forage in an environment unknown to them -is somewhat relaxed by making some other assumption, such as the robots being endowed with a compass or the base being able to communicate with the robots. However, even such facilities cannot help the robots in navigating through obstacles, especially if they are "awkwardly" shaped. In our work, we do not require the robots or agents to have any such extra external facility.

Foraging using marking agents

We consider now environments that have resources in multiple locations. These locations are of course unknown to the agents. Each location has a given quantity of resource. As illustrated Fig 3 .a, a cell in the environment can,

• be an obstacle (grey colour),

• contain a resource (dark grey colour) whose quantity of resource q i is bounded,

• be the base ('B' letter in black cell), from where all agents start ,

• contain an agent (whose ID number is shown in a circle in the cell).

The agents begin all from the base. Note that a cell may contain more than one agent, but sharing a cell has no effect on the actions taken by each agent in it. In addition to the abilities mentioned in the previous section, an agent is able to • detect the presence of resources in the 4 neighbouring cells,

• load a quantity q max of resource onto itself for transporting back to the base.

Building a wavefront from the base is usefull for any task that requires the agents to traverse the environment many times (e.g. to manage their energy). This is just the case in the foraging problem, where agents may have to make multiple trips from the resource locations to the base to transport back all the resources. Using the wavefront, they just have to descend the numerical gradient to come back without being blocked by obstacles. Thus, the agent we have just described is essentially a marking agent (cf. section 3.1) with the ability to come back the base as often as it is required to. We define this re-entrant behaviour of the agent as descent motion (presented in section 2). Algorithm 3 represents the complete behaviour of an agent. It is also shown schematically in Figure 4. This is a sort of a rudimentary definition of marking agents who forage. One can note that three tasks can be simultaneously performed by such a multiagent system: (i) exploration to discover resources, (ii) construction of an optimal APF and (iii) transportation of resources to the base. Note that while the third task can be done by one or more agents, the two first tasks are carried out thanks to cooperation between all the agents. Figure 3

An interesting property of the APF contruction

The parallelization of the three tasks is time-efficient (we elaborate in the next section) but has the drawback stated in Section 3.1. As agents explore the environment, they do not immediately build an optimal APF. The value written in a cell the first time it is visited is not necessarily the optimal (i.e., limiting) value. It is a consequence of the random nature of the agents' exploration which implies that the agents do not discover the shortest path to a resource when that resource is detected. However, our algorithm has one interesting property: when an agent detects a resource at least one valid obstacle-free path exists to return back to the base. In fact, one of these paths is a path marked by the discovering agent itself. As stated above, this path is valid but not neccessarily the shortest (only Property 1, section 2 is valid). However, continuous exploration by the agents improves the APF values until there is convergence. If the environment is finite, the values converge (as was proved in the previous section). Thus, Property 2, of optimal path planning, is attainable in a finite time (as is the case in Figure 3.b). One may wonder if the agents can get stuck in local minima since this construction is asynchonous. The answer to this query is NO. The following lemma ensures this property. Lemma 4.1 During the APF construction, for each cell c different from c 0 , there exists at least a neighbouring cell with a value lower than cell c.

Proof: Recall that if an agent moves to a cell, the following update is made: val = min(val, 1 + min(4-neighbouring values)). Consider any cell c i different from c 0 . Every time an agent visits c i , its value can change to 1 + min(4neighbouring values), which results in at least one neighbouring cell having a value lower than c i . Now, even if the neighbouring cells of c i are themselves visited, their values can only change for lower ones (update operation can only decrease the current value val). So these visits cannot change the property that c i has at least a lower neighbouring.

Lemma 4.1 permits to any agent that evolves in the APF under construction to perform a descent to the base, since from each cell it always exists a lower neighbouring to move. As a consequence, at any point of the exploration, from any cell, our algorithm provides a valid path to any agent to return to the base, irrespective of the number and shapes of the obstacles present. However, our algorithm in the version presented above does not guide the agent in returning to a location that has been discovered to contain resources. In the next section, we show how previously followed paths can be reused and communicated to other agents, in order to improve the foraging.

Colour-marking (c-marking) agents: cooperation through numeric trails

We now describe how the previous foraging algorithm may be extended so that agents can retrace previously discovered resource locations from the base. Since the locations are not known to the agents per se and since agents cannot communicate with one another, the environment itself is turned into a communication tool. In the previous section, we saw that The idea is to make the agent marks this path as a trail while returning to the base. Then returning to discovered resource locations will be as simple as following these trails.

In order to allow agents to mark trails in the numerical potential field, we give the agents the ability to write values in a specific colour. So when an agent starts its return to the base from a resource location, it rewrites the values in the cells it followed using a distinctive trail colour (this task shall be called RETURN & COLOUR TRAIL). Trails marked by an agent can then be used by other agents. Thus the coloured values serve as a form of indirect communication. It is important to note that coloured trails do not change the potential field construction. Besides, as we show now, coloured trails can be easily detected and erased by the agents. When a location becomes exhausted of its resources, the trail leading upto it must be erased as quickly as possible, since now it is of no use to any agent. In the ant-model, the pheromone evaporation mechanism automatically erases useless trails. In our pheromone-less approach, this task is done by the module RETURN & REMOVE TRAIL, in which the agent does a simple descent of the coloured trail rewriting the values using the default colour (signifying absence of a trail). The behaviour of c-marking agents is shown in Figure 5, and the enhanced algorithm corresponding to c-marking agents is as follows:

The RETURN task defined in previous section has now two new versions: The LOADING task is now available with a choice of the type of RETURN task (see Algo. 4) which depends on the state of the discovered resource (exhausted or not), The default RETURN to BASE task is the same as in the previous section (i.e., it is a descent of the gradient). Finally, the SEARCH task is extended to allow agents to climb trails when they discover one: see SEARCH & CLIMB TRAIL.

Simulation

We used the TurtleKit toolkit [START_REF] Michel | The turtlekit simulation platform: application to complex systems[END_REF] (part of the MadKit Platform [START_REF] Ferber | A meta-model for the analysis and design of organizations in multi-agent systems[END_REF] [19]) for testing our algorithms. We tested with rectangular environments (grids of a variable size). Obstacles in the environment were defined in two ways: (i) given a desired density, cells were randomly designated as obstacles (ii) obstacles were specifically designed by hand (for example, a maze as in Figure 3). We illustrate the whole behavior of the system by describing an experiment with the following Setup (1):

• A 40 cells x 40 cells environment, 30 % of the cells are obstacles and they are randomly distributed. 20 cells are resource locations, whch are also randomly distributed. Each resource location contains 1000 units of resources.

• Each agent can load a maximum of 100 units onto itself.

We ran 10 c-marking agents who were initially located at the base, which is in the center of the environment. We observe in Figure 6.a that the construction of the numerical potential field starts out as a pseudo-circular front computation (step 11). We can also observe that agent 0 has discovered a resource and started to create a trail as it returns to the base. Figure 6.b shows that at step 21 two other agents have discovered resource locations and started to create trails, while agent 9 performs multiple trips from the base to the resource location he discovered. Later, step 53, Figure 6.c shows that six resource locations were discovered, many agents are involved in transport of resource along trails marked by others (note that an agent may follow a trail even if it does not connect to the base at that point in time, e.g. agent 4). This communcation through trails permits the recovery of all the resources in the environment while the APF contruction proceeds parallely. Figure 6.d shows step 76, where agents 2, 4 and 5 work simultaneously along the same trail (connecting to a resource location at the bottom of the snapshot). On the other hand, the trail connecting the first dicovered resource location is now removed (by agent 9) as it was exhausted.

Note that when agents leave the base, if there is several possible trails they can be selected with equal probability. So the distribution of the agents between several resources is "well-balanced".

At around the 1200 th iteration, all resource locations in the envrionment have been discovered and all the resources thereby exhausted, and what is more, the potential field has converged to its optimal value (Figure 6.e).

Evaluation of our algorithm and comparison with the ant-model 5.1 Methodology

Criteria We now study the performance of our algorithm (c-marking agents) and compare foraging time with the ant algorithm. We define time to be the number of iterations required by the agents to discover and exhaust all the resources of the environment. One iteration consists for each agent to read or write a value on its current cell and to move to a neighbouring cell. We evaluated the performance of the two algorithms (see 5.5 for evaluation of the ant algorithm) in different configurations (number of agents, size of the environment). To evaluate average performance, we repeated each Table 1: Influence of increase in the number of agents on the performance of the algoritihm in a 40 x 40 environment with 30% for obstacle density and 20 resource locations each holding a 1000 units of resources (Setup 1).

foraging many times in each configuration (up to 5000).

Basic environment In all experiments, environments are defined as rectangles. The base is always located in the center and all agents start from it. Obstacles and resource locations are spread out randomly in the environment.

Influence of the number of agents on performance

Experiments of our algorithm show that increasing the number of agents have always the same influence on performances (for every configuration). So, we first describe performances on a representative scenario which is Setup 1 defined in the previous section.

Table 1 shows the performance of the algorithm in Setup 1 while the number of agents grows. It is represented graphically in Fig. 7. The algorithm was first evaluated for 5 agents and then this number was progressively doubled till 160. As Table 1 and Figure 7 show, foraging becomes dramatically faster with an increase in the number of agents. With every doubling of agents, the number of iterations required for foraging is halved or reduced even further, which shows the effect of cooperation between agents (we study the super-linearity of their performance in the next subsection). The standard deviation of the number of iterations indicates the impact of the pseudo-random walk in the exploration. We also evaluated the algorithm by varying other parameters such as obstacle density, resource location density, the quantity of resource at each location, besides the environment size and the number of agents. However, for any profile of parameters, we always obtained the same degree of change in the speed of foraging with a change in the number of agents. At the start of the curve (i.e., for small number of agents), there is a linear or super-linear decrease in the number of iterations. The curve is asymptotic as the number of agents becomes large, representing the fact that for any number of agents, a minimum amount of time is required to (i) reach the resource locations (ii) transport all the resources to the base. The performance of the algorithm raises a few questions. What are the conditions under which a super-linear performance is achieved? What is the effect of the environment's size on performance? How does our algorithm compare to the pheromone-based ant algorithm ? We now attempt to answer these questions.

Super-linear performances

A multi-agent system is said to be super-linear if increasing the number of agents increases further than linearly the efficiency with which it performs a task. Such an increase in efficiency is given to represent a measure of cooperation between agents. We measured the performance of c-marking agents in different setups (varying environment size, number of resource locations etc) in order to study super-linearity. We observed that super-linearity does not appear systematicaly but does so for a certain range of the number of agents and for certain problem configurations. We saw in the previous section that increasing the number of agents decreases asymptotically the speed of convergence. So it is meaningful to study super-linearity for a small number of agents. In order to improve accuracy, we reduced the environment size to 20 x 20 and the obstacle density in it to 5% (Setup (2)). Setup (2): A 20 x 20 cell environment, 5% of the cells are obstacles, 2 randomly located resource locations each containing 1000 units of resources.

We conducted 5000 simulations to obtain the average performance of the algorithm for a given configuration. The number of iterations required by different number of agents (1 to 8) to finish forgaging is shown in Table (2) (top row).

The average number of iterations required by a single agent was found to be 1790.4. We denote this value as V re f . We then computed the projected value of the average number of iterations required for different number of agents as a linear function of V re f . For n agents, the projected value was V re f /n. The difference between the projected and actual values measures super-linearity (time saving). Super-linearity is maximum in passing from one agent to two. Then it decreases. It becomes linear at about 6 agents. For more than 5 agents, the difference converges to a value, which is due to the Table 3: Influence of the size of the environment on the performance of the algorithm, using Setup (3) asymptotic behaviour mentioned before. In our simulations, we could observe that the boundary of super-linear to linear performance can be as high as more than 160 agents (as seen in Table 1).

We conjecture that a super-linear performance is related the ratio (number of agents)/("complexity" of the configuration). By complexity, we mean the size of the environment and the number of resource locations. We intend to study this relationship in our future work. It is motivited by the idea that if the number of agents is small compared to the size of the environment, in one iteration, there is few chance that two agents do identical actions on the environement (due to distances between agents) and each action is useful directly or later to all agents.

Influence of the size of the environment

We now see how the size of the environment affects the performance of the algorithm when the number of agents is kept fixed. Obviously, a large environment will require more time for exploration and transportation of resources to the base. However, we present some interesting results using Setup (3) and by progressively quadrupling the size of the environment.

Setup (3):

• Environments are defined with a 5% obstacle density and 20 resource locations randomly distributed, each with 2000 units of resources.

• The number of agents is 50. Each agent can transport a maximum of 100 units of resources at a time.

The performance of the algorithm on progressively constantly quadrupling the size of the environment, from 12x12 to 100x100 is shown in Table 3 and graphically in Figure 9. Let the ratio #Iterations size k /#Iterations size k-1 be denoted by INRIA R. Below 100x100, R is close to 2. Over 100x100, R quickly exceeds 4. In other words, the time to explore becomes exponential. It is because the pseudo-random walk the agents perform becomes more and more inefficent as the size of the environment increases. In the next section, we compare our results with the ant model in different environments.

Comparison with the ant model

We now evaluate quantitatively the performance of our algorithm with the classic ant model. In nature, ants deposit a chemical substance called pheromone in the area in which they explore. These deposits are gradually laid in the form of a gradient. This gradient creates paths from food sources to the ant nest [START_REF] Holldobler | The Ants[END_REF]. We have implemented a standard algorithm based on the ant model ( [24] [23]), shown in Figure 10. We computed several simulations to tune diffusion and evaporation rates in order to obtain the best possible performances. In presented results the diffusion rate is set to 95% and the evaporation rate to 0.5%. Simulations (e.g. figure 11.b) show that ants climb these gradients to retrieve discovered resources. This form of cooperation is similar to the one used by marking agents. Figure 10.b details the search and climb behavior.

Such a model requires that each ant be able to:

• drop an amount of pheromone on the current cell and read the amount currently in the cell,

• perceive if any of the 4 neighbouring cells is an obstacle and read pheromone amount in each of those cells

• move to a neighbouring cell if it is not an obstacle,

• know the direction of the base from its current cell Additionally, to follow the ant model, the following phenomena must also be simulated:

• pheromone evaporation

• pheromone propagation

• addition of an amount of pheromone to the pheromone already present in a cell One can see that simulating the ant model requires more environment management mechanisms than the marking agents model. Note that the propagation of pheromones may represent a high computational burden. Another drawback is that each 'ant' must have specific additional information about the location of the nest to be able to return to it. Such information is inadequate when complex obstacles are present in the environment. For example, it can be shown experimentally that ants can get stuck in cavities formed by just a few obstacle-cells (Figure 11.a). Even for a density exceeding just 5 %, such obstacles may form in a random generation. By contrast, the main advantage of marking agents is their ability to find paths in environments containing obstacles of a. any shape. As discussed in the next section, the ant model has been extended to address the problem of awkwardly shaped obstacles. The gist of these attempts is that a secondary pheromone is spread from the base in order to build a new gradient that culminates at the base (e.g. [START_REF] Panait | A pheromone-based utility model for collaborative foraging[END_REF]). However this pheromone evaporates while this gradient should be maintained in the entire explored environment. The gradient is usually artifically sustained by placing a huge amount of pheromone at the base.

INIT

We have compared our algorithm with the ant model in environments containing less than 5% obstacles. In all different configurations, we observed that c-marking agents take less time to finish foraging. Figure 9 shows such a comparison, in which the environment size is varied with Setup 3 (see snapshot Figure 11.b).

Figure 9 shows that as the environment grows the difference in the time required to forage by marking agents and by ants decreases (from 73% to 52% to 37%). It is due to the time needed to explore the environment and to discover the 20 resources.

As shown previously marking agents and ants engage in a pseudo-random walk, implying that they spend a majority of their time in exploration. However, the superior performance of the marking agents as compared to ants on the same foraging task clearly indicates that computing a wave-front while exploring is more efficient: it saves time by providing immediately paths from discovered resources to the base and reduces the amount of time spent in exploration by favouring

the not yet explored cells (see section 3.1).

6 Related work

Pheromone-based techniques for foraging and its variants

As previously outlined, ants inspired pheromone-based models for foraging (see section 5.5). However, it is interesting to consider the impact of the required environmental dynamics to perform the foraging task. The emergence of tidy paths in the environement can be slow as it depends on ierative deposits on the same areas. The persistance of a pheromone-path requires the replenishing of evaporated pheromone at a certain rate, and this in turn requires the participation of a large number of agents (on the other hand, even a single marking agent alone can build a gradient and therefore a path). By the same token, pheromone evaporation is a slow process and therefore it takes a long time for sub-optimal paths to be erased.

For the dynamic version of the foraging problem, i.e. with mobile resources (see e.g. [START_REF] Panait | A pheromone-based utility model for collaborative foraging[END_REF]), the pheromone technique has an advantage in that paths are automatically updated. A marking agent, on the other hand, immediately erases paths from which a resource has moved, and if there is no other agent close to it, its new location will be lost. However, we INRIA plan to study a simple extension of c-marking agents to deal with moving resources. It consists to keep the agent at the resource location until another one arrives, in order to extend the trail when the resource moves.

Pheromone-based learning algorithms have also been proposed in recent years. They try to take advantage of reinforcement learning or evolutionary algorithms. Agents use pheromone-amount to update the so-called Q-values (stateaction utility estimates) in order to improve exploration or the gradient ascent ( [START_REF] Monekosso | An improved q-learning algorithm using synthetic pheromones[END_REF]). Genetic algorithms are then used to fine tune different parameters and to optimize agent policies (exploration versus exploitation ratio) (e.g. [START_REF] Sauter | Evolving adaptive pheromone path planning mechanisms[END_REF]). It is worth pointing out that, besides the time required to compute the propagation and evaporation dynamics, these learning algorithms require additional time to actually converge to the optimal policies.

Pheromone-dependent methods need some ad-hoc mechanisms to be applied when the environment holds obstacles and that it is required for agents to find a path to the base. This could be compass information or some external information (e.g. [START_REF] Vaughan | Whistling in the dark: cooperative trail following in uncertain localization space[END_REF]). This problem can be overcome, as recently proposed by [START_REF] Panait | A pheromone-based utility model for collaborative foraging[END_REF], by combining pheromones with reinforcement learning to build numerical gradients. This approach is meant for collaborative forgaging and optionnaly for mobile food resources. In this work 'ants' have abilities quite similar to those of marking agents. They can move, perceive neighbouring cells, and read/write real values in them. Each agent updates the amount of pheromone in a cell on visiting it using a reinforcement learning update rule (such as TD(λ) learning). Repeating this update operation leads to the diffusion of values (rewards) set at home and at discovered resources. Even if this principle requires numerous agents, it is close to the wavefront expansion exploited in our model. However, the model of [START_REF] Panait | A pheromone-based utility model for collaborative foraging[END_REF] does not guarantee to avoid building local minima. For that matter, their paper reports experiments in environments containing only convex obstacles and only one resource.

It is interesting to note while marking agents require only one gradient, reinforcement learning agents are required to construct two gradients to create a path between a resource and the base. Reinforcement learning needs to manage several pheromone-related dynamics in the environment. Therefore the time required for convergence using RL is several-fold than our algorithm which constructs only one gradient.

Towards a real-world application

We now discuss ways to implement markings and pheromones models in real environments. [START_REF] Drogoul | From tom thumb to the dockers: Some experiments with foraging robots[END_REF] proposed that the markings/pheromones be actual physical objects; agents drop landmarks from discovered resources to the base. Even though this approach does not require an evaporation and propagation mechanism, it does demand complex abilities of the robots, to transport and to manipulate the landmarks. Futhermore, the approach does not incorporate the computation of a gradient. This prevents the tackling of complex obstacles such as cavities or mazes. For comparison, our digital markings concept can be considered as an intermediate between physical markings and synthetic pheromones. The cooperative transport model presented in [START_REF] Vaughan | Whistling in the dark: cooperative trail following in uncertain localization space[END_REF] is an interesting example of a real-world implementation, Each robot is asssumed to know its own location and it can communicate with a centre. The communication facility allows it to leave landmarks in an area that is shared by all the robots. The landmarks are directional pheromones (i.e., pheromones that indicate direction). Complex obstacles are not considered because the navigation is based on local (random) information and a compass (external information). These 'ant-robots' record their movements as a sequence of landmark droppings in the target localization space. Each robot makes use of the landmarks left by other robots. In this sense, landmarks that lead to the discovery of a valid path from a resource to the base, are said to be "shared" by the robots. In this way, a valid path, not necessarily the shortest path, is discovered. This principle, of using a common workspace to share simple information, may be the way to implement our algorithm without the requirement of writing values in the environment, for a real-world application. As emphazised in the introduction, the implementation of swarm and collective systems has become more realistic with pervasive and ubiquitous computing. Clearly, we can imagine to deploy or to use a wireless network while the robots explore the environment following our algorithm (see for instance [START_REF] Mamei | Spreading pheromones in everyday environments through rfid technology[END_REF] for an application of synthetic pheromones spreading). Eventually, simple mobile robots such as required in our model may be produce in quantity as their making becomes cheap (see for instance robots used in [START_REF] Labella | Division of labor in a group of robots inspired by ant's foraging behavior[END_REF]).

Conclusions and future work

We have defined a distributed and asynchronous version of an algorithm due to [START_REF] Barraquand | Numerical potential field techniques for robot path planning[END_REF] that builds an optimal APF for pathplanning. Our model relies on a group of reactive agents that build a gradient purely by exploring the environment and that do not require a map to do so. The agents are only required to be able to read and write integer values in the discretized environment. We have proved that this multi-agent algorithm builds a potential field that converges to an optimal one (in other words, the shortest path from any point in the environment to the base of the agents is determined) (Theorem 3.1). Furthermore, this gradient, even during its construction, allows agents to deal with the multi-source foraging problem.

Figure 1 .Figure 1 :

 11 Figure 1: WaveFront algorithm: initial environment state and result of the construction Algorithm 1 WaveFront expansion Algorithm[START_REF] Barraquand | Numerical potential field techniques for robot path planning[END_REF]

Figure 2 :

 2 Figure 2: Collective construction of the potential field with 3 agents (steps 2, 17 and 65)

Figure 3 :

 3 Figure 3: Foraging with eight marking agents in a little maze (a) after 18 iterations (b) final state

Algorithm 3

 3 SEARCH & RETURN TO BASE SEARCH IF a resource is detected in a neighbouring cell THEN move into this cell, load a quantity q max of resource and execute RETURN to BASE ELSE execute EXPLORATION & APF CONSTRUCTION (i.e. Algo. 2) RETURN TO BASE IF the agent is located at base THEN unload resource and execute SEARCH ELSE move to a neighbouring cell that has the least value and UPDATE-VALUE

  illustrates the progression of foraging in a little maze containing 5 location resources (3.a) and the final state attained after 500 iterations (3.b) showing the optimal APF.

Figure 4 :

 4 Figure 4: Behaviour of a marking agent in foraging

Figure 5 :

 5 Figure 5: c-marking agents that colour paths between sources and the base

Figure 6 :

 6 Figure 6: Resolution of the foraging problem with 10 c-marking agents (with Setup 1). Trails are represented in dark grey colour. Snapshots at step 11, 21, 53, 76, 1200.

Figure 7 :

 7 Figure 7: Performance of c-marking agents in Setup (1) (Table 1) #Agents 5 10 20 40 80 160 # Iterations 19200 8697 4114 2263 1070 574 Std. deviation 10071 4282 1890 1134 448 420

Figure 8 :

 8 Figure 8: Difference in projected and actual number of iterations required, on average, to achieve foraging in Setup (2)when varying number of agents -(Table (2))

Figure 9 :

 9 Figure 9: Comparision of the performance of the markings model with the ant-model as the size of environment is varied (Setup (3): 50 agents, 5% of obstacles, 20 resources of 2000 units). #Env Size k 12x12 25x25 50x50 100x100 200x200 # iterations 155,5 345 805 2290 7844 R 2,22 2,3 2,8 3,43

Figure 10 :

 10 Figure 10: The ant model: (a) global ant behavior (b) details into task Search & Climb pheromone

Figure 11 :

 11 Figure 11: Foraging with ants that drop pheromones and use "compass"-like information to return to their nest situated in the center. a) obstacle density of 30% generates cavities where agents freeze. b) obstacle density of 5% does not interfere with foraging (50 x 50 env., 50 ants, 20 sources)

  RETURN & COLOUR TRAIL (see Algorithm 4) and RETURN & REMOVE TRAIL. The latter task is identical to RETURN & COLOUR TRAIL except in the selection of the next cell and the colour used to write values. In RETURN & REMOVE TRAIL, the ELSE block of RETURN & COLOUR TRAIL is replaced by, Move to a new neighbouring cell that has the same colour as the trail Change the cell's colour to the default colour

  Trails are represented in dark grey colour. Snapshots at step 11, 21, 53, 76, 1200.

	Algorithm 4 colour Marking Agent
	SEARCH & CLIMB TRAIL
	IF a resource is detected in a neighbouring cell THEN
	move into that cell and run LOADING
	ELSE
	IF neighbouring cells are coloured and different from the previous position
	THEN move to highest-valued such cell
	ELSE execute EXPLORATION & APF CONSTRUCTION (i.e. Algo. 2)
	Pick up a quantity q max of resource
	IF the cell is now not exhausted of resources THEN
	IF the cell is coloured (it is part of a trail)
	THEN execute an algorithm equivalent to RETURN TO BASE
	ELSE execute RETURN & COLOUR TRAIL (create a trail in a specific colour)
	ELSE execute RETURN & REMOVE TRAIL (remove a trail)
	RETURN & COLOUR TRAIL
	IF the agent is located at the base THEN
	unload resource and execute SEARCH & CLIMB
	ELSE
	Move to a new neighbouring cell with the least value.
	Colour the cell in a trail colour
	first setup:
	INRIA

Table ( 2

 ( ))

	#Agents	1	2	3	4	5	6	7	8
	Difference: Proj-Expe		23,7	13,9	8,9	2	-3,6	-10,7	-12,4

Experim. #iterations 1790,4 871,5 582,9 438,7 356,1 302,0 266,5 236,2 Projected #iterations 1790,4 895,2 596,8 447,6 358,1 298,4 255,8 223,8

Table 2 :

 2 Time saving on projected performances (in Setup 2)

RR n°0123456789

The computational experience of our algorithm shows that increasing the number of agents decreases dramatically the time required for foraging. In particular, cooperation can provide superlinear performances for small number of agents. We have discussed the differences between our algorithm and the standard ant-model algorithm. Computational experiments show that marking agents are more time efficient than pheromone dependant agents. Moreover, our model, which relies on the construction of only one gradient, whereas several are required by the other approaches, defines a solution for foraging in complex environments (i.e. with obstacles such as cavities or mazes).

The efficiency of our algorithm is on account of two factors:

• When marking agents discover a resource, a valid path from the resource location to the base is immediately available to them (since the APF construction starts as soon as agents leave the base).

• In contrast to pheromone based techniques, paths construction and removing do not rely on costly iterative processes such as accumulation and evaporation of pheromones.

Generally, we could observe that to achieve a given computational performance, the marking agents approach requires fewer agents than the ant-model. In complete constrast to the ants-pheronome approach is that, even a very small number of c-marking agents (it can even be a single one) can identify paths for forgaging by building the complete gradient. Such efficiency in the number of agents is afforded because the computation associated with pheromones accumulation is completely avoided.

We intend to elaborate this work in different ways. We plan to study paramaters that induce super-linear performances, to evaluate robustness to noise in navigation, and to adapt the model to deal with moving resources and energy limitation. We also think that the exploration process can be improved by adapting some existing strategies used for covering tasks (e.g. [START_REF] Wagner | Mac vs. pc: Determinism and randomness as complementary approaches to robotic exploration of continuous unknown domains[END_REF]). As we started to study, we intend to show that the proposed multi-agent algorithm can be generalized to the construction of other potential fields and harmonic functions. Eventually we plan to implement the proposed model with small mobile robots.

The author wishes to thank Bruno Scherrer for fertile discussions and reviewing of this work.


Alain Meunier
email: alain.meunier@hydrasa.univ-poitiers.fr

Bruno Lanson

Bruce Velde

COMPOSITION VARIATION OF ILLITE-VERMICULITE-SMECTITE MIXED-LAYER MINERALS IN A BENTONITE BED FROM CHARENTE (FRANCE)

Keywords: bentonite, Charentes, decomposition, high-charge smectite, hydration properties, mixed layer minerals

whereas for intermediate-and high charge layers this montmorillonitic charge is complemented by additional tetrahedral substitutions (0.30 and 0.35-0.

ABSTRACT

Mineralogical and chemical variations were studied in the upper half of a 1 m thick discontinuous bentonite bed interlaminated in the Lower Cenomanian sedimentary formations of the northern Aquitaine basin (France). X-ray diffraction patterns obtained from the <2 µm fraction in the Ca and K-saturated states were decomposed and compared to those calculated from decomposition parameters. They revealed the presence of two highly expandable illiteexpandable (I-Exp) mixed-layer minerals (MLMs). Relative proportions of the two MLMs steadily evolve with depth leading to the decrease of the cation exchange capacity and of the (Na + Ca) content towards the center of the bentonite bed. However, the system is essentially isochemical and Mg, Al, Si, K and Fe are roughly constant in the bulk samples. It is thought that the mineralogical zonation results from the initial stages of the smectite formation in an ash layer.

In the Ca-saturated state, the expandable component of these MLMs was for the most part homogeneous with the presence of 2 sheets of ethylene glycol molecules in the interlayer. However, the heterogeneous hydration behaviour of these expandable layers was enhanced by the potassium saturation test. From this test, the presence of three layer types with contrasting layer charge was evidenced from their contrasting swelling abilities. The C 12 -alkylammonium saturation test applied to samples in which the octahedral charge had previously been neutralized (Hofmann-Klemen treatment) showed that the tetrahedral charge is located on specific layers. These layers are responsible for the heterogeneous hydration behaviour. Low-charge smectite layers are mostly octahedrally substituted,

INTRODUCTION

It has been established in numerous studies that smectitic bentonite beds tend to alter to illite by diffusion processes at their contacts with encompassing rocks and sediments [START_REF] Foscolos | Diagenesis of clay minerals from lower Cretaceous shales of north eastern British Columbia[END_REF]Velde & Brusewitz, 1978;[START_REF] Hoffman | Clay mineral assemblages as low grade metamorphic geothermometers: application to the thrust faulted disturbed belt of Montana[END_REF][START_REF] Huff | Chemical characteristics of Ordovician Kbentonites along the Cincinnati Arch[END_REF][START_REF] Altaner | Model for K-bentonite formation: Evidence from zoned K-bentonites in the disturbed belt[END_REF].

These sedimentary units form K-bentonites. The rate at which this diffusioncontrolled reaction occurs has been estimated by [START_REF] Altaner | Potassium metasomatism and diffusion in Cretaceous K-bentonites from the Disturbed Belt, north-western Montana and in the Middle Devonian Tioga K-bentonite[END_REF]. The most remarkable observation is the increase of the potassium content in the essentially monomineralic bed towards its outer edge. In most cases, illite-smectite (I-S) mixed-layer minerals (MLMs) are smectite-rich in the interior of the bentonite bed and have a higher illite content at the edge. Such occurrences have been assumed to represent simple smectite-to-illite reaction series which appear to differ in their kinetics of transformation when compared to detrital shales [START_REF] Sucha | Smectite to illite conversion in bentonites and shales of the East Slovak basin[END_REF].

Implicit in such a mineralogical sequence is the initial conversion of the acidic volcanic ash into a monomineralic material of essentially pure smectite composition. In this preliminary process, a chemical exchange with the exterior of the ash bed is necessary to transform the original volcanic rock into smectite through a non-isochemical process. It is always assumed that the initial ash bed transformation gives a homogeneous smectite layer [START_REF] Altaner | Potassium metasomatism and diffusion in Cretaceous K-bentonites from the Disturbed Belt, north-western Montana and in the Middle Devonian Tioga K-bentonite[END_REF]. However, since the initial phases of the ash-to-clay transformation imply an exchange of several elements, there is little reason to exclude an initial composition gradient during the smectite formation process.

The object of the present investigation is to assess the mineralogical homogeneity of a Cretaceous bentonite bed which has experienced little burial diagenesis leading to clay mineral transformation. The unit has experienced only shallow burial and no tectonic effect during its 120 Ma existence [START_REF] Meunier | Geological significance of two smectiterich beds from Lower Cenomanian sediments, northern Aquitaine basin, France[END_REF]. Here, we expect to see the initial stages of diffusion and smectite formation before illitization [START_REF] Meunier | Vermiculitization of smectite interfaces and illite layer growth as a possible dual model for illite-smectite illitization in diagenetic environments: a synthesis[END_REF].

MATERIALS AND METHODS

Sample location and existing data

The investigated bentonite bed is discontinuously interlaminated in the Lower Cenomanian sedimentary formations from the northern Aquitaine basin (Fig. 1). It belongs to the A unit in the Lower Cretaceous stratigraphic sequence [START_REF] Meunier | Geological significance of two smectiterich beds from Lower Cenomanian sediments, northern Aquitaine basin, France[END_REF]. This bed is 1 m thick in the sampling area: a quarry near Archingeay (Charentes, France). There, it is interlaminated between two unconsolidated sand deposits (Fig. 1). For this study, 5 samples were taken out at regular 10 cm intervals and indexed A, B, C, D and E from top to bottom in a vertical profile.

Analytical procedures

All samples were gently crushed in an agate mortar. The powders were then ultrasonically dispersed in distilled water and the <2 µm fraction was separated from the suspension using standard sedimentation procedures. Oriented preparations of a Ca-saturated <2 µm fraction were analyzed by means of X-ray diffraction (XRD) in the air-dried state (AD), and after ethylene-glycol solvation (EG). Additional analyses were carried out from EG solvated samples after Ksaturation, and after Li-exchange and heating to 300°C (Li-300;[START_REF] Hofmann | Lost of exchangeability of lithium ions in bentonite on heating[END_REF]. The contribution of tetrahedral substitutions to the total layer charge was estimated by comparing XRD patterns obtained for each sample after saturation with C 12 -alkylammonium [START_REF] Olis | The rapid estimation of the layer charges of 2:1 expanding clays from a single alkylammonium ion expansion[END_REF]

Methods for the interpretation of XRD patterns

Most identification methods routinely used to determine the composition of I-S MLMs rely on the position of diffraction maxima, on relative positions of maxima, on intensity ratios between these bands, or on peak/background intensity ratios [START_REF] Srodon | X-ray identification of randomly interstratified illite-smectite in mixtures with discrete illite[END_REF][START_REF] Velde | Pressure-temperature-composition of illite/smectite mixed-layer minerals: Niger delta mudstones and other examples[END_REF][START_REF] Watanabe | The structural model of illite/smectite interstratified minerals and the diagram for their identification[END_REF][START_REF] Inoue | A convenient technique to estimate smectite layer percentage in randomly interstratified illite / smectite minerals[END_REF]Esposito & Whitney, 1995 among many others). These parameters are first measured on experimental XRD patterns and then compared with values determined from calculated patterns. However, one may note that all these methods rely on two main hypotheses: (i) the expandable (inter)layers are assumed to be homogeneous as all calculations are performed for 2 components:

illite and expandable layers (I-Exp). As a consequence, none of these identification methods allows the description of 3 component systems such as the illite-smectite-vermiculite (I-S-V) MLMs reported (e.g.) by [START_REF] Drits | Sequence structure transformation of illite-smectite-vermiculite during diagenesis of Upper Jurassic shales, North sea[END_REF] The errors introduced by these methods when applied to 3-component systems may be illustrated by applying some of them to XRD patterns calculated for 20:80 I-Exp MLMs in which the swelling behavior of the expandable layers is heterogeneous (Fig. 2). Initially, one may note in Table 1 that the identification results obtained for a simple two-component system (0%V in I-S) strongly depend on the identification method used as estimates range from 90 to 72% smectite. In addition, the identification results also depend on the swelling behavior of the expandable layers. Some of the identification methods used are not applicable if

V-type layers are present in I-Exp MLMs, whereas others may still be applied but provide different results as a function of the relative proportions of S-and V-type layers in the stacking sequences, increasing the range for the estimated smectite content to 95-54% (Table 1).

Because the presence of expandable layers with contrasting swelling behaviors may also be encountered in bentonites [START_REF] Calarge | The smectitic minerals in a bentonite deposit from Melo (Uruguay)[END_REF] a three step process was adopted to identify the MLMs present in our bentonite samples: first, decomposition of the diffraction peaks into Gaussian and Lorentzian elementary contributions was performed using the DECOMPXR program [START_REF] Lanson | Decomposition of experimental X-ray diffraction patterns (profile fitting): a convenient way to study clay minerals[END_REF].

This decomposition procedure was carried out on 00l peaks from XRD patterns recorded after different sample treatments (Ca-AD, Ca-EG, K-EG of peaks at 15-20, 8-12 and 2-12 °2θ Cu-Kα angular ranges respectively). Special attention was paid to the first steps of the procedure, and specifically to background stripping.

As recommended by [START_REF] Lanson | Decomposition of experimental X-ray diffraction patterns (profile fitting): a convenient way to study clay minerals[END_REF] background was assumed to be linear whenever possible (2θ ≥ ~8°), and interpolated assuming a Lorentz-factor like shape in low angle regions. The decomposition was performed by obtaining a satisfactory fit to the experimental data using a minimum number of elementary contributions. However, these elementary contributions are related to specific (sub-)populations of crystals which contribute to the scattered intensity over the whole angular range whatever the physical and chemical pre-treatment. As a consequence, the preliminary identification allowed us to introduce additional constraints on the number of elementary contributions that can be used in the analysis of smectite patterns following the different treatments. In the present case, constraints were not only derived from the processing of peaks from the same XRD pattern but also from the analysis of peaks from patterns of the same sample recorded in different conditions (cation exchange, EG solvation, etc…) as recommended by [START_REF] Drits | Sequence structure transformation of illite-smectite-vermiculite during diagenesis of Upper Jurassic shales, North sea[END_REF] and [START_REF] Sakharov | Determination of illitesmectite structures using multispecimen X-ray diffraction profile fitting[END_REF] for their multispecimen approach.

The decomposition allowed an objective description of peak profile modification with "depth" in the bentonite bed. Second, the position, intensity and

RESULTS

Chemical composition

The chemical compositions of the <2 µm size fraction from the five samples (Table 2) are relatively homogeneous in spite of some erratic variations related to impurities. The SiO 2 content varies because of the presence of microcrystalline quartz (e.g. sample D). The amounts of CaO and Na 2 O as well as the CEC decrease regularly with increasing depth (Fig. 3) while the K 2 O content remains roughly constant throughout the bed.

XRD analyses

Air-dried and glycol solvated states (Ca-saturated). According to [START_REF] Inoue | A convenient technique to estimate smectite layer percentage in randomly interstratified illite / smectite minerals[END_REF], the low background intensity on the low angle side of the smectite 001 reflection suggests a high smectite content in the investigated clays (Figs 4,5).

However, on the same experimental pattern the significant asymmetry of the smectite 002 reflection (~8.55 Å) towards lower angles (Fig. 4) suggests the presence of several expandable phases. If this asymmetry was due to contrasting swelling ability of expandable layers, a significant shift of the ~17.0 Å reflection would also be observed as illustrated on Figure 2. The presence of these highly expandable MLMs is also evidenced by the asymmetry of the smectite 003 reflection at about 5.00Å in the Ca-saturated AD pattern (Fig. 5), whereas a sharp symmetrical peak is usually observed when essentially expandable phases are contributing to the diffracted intensity even if the hydration state of the expandable layers is not homogeneous. The above peak asymmetries seem to evolve with depth in the sampled sequence (Figs. 4,5) to indicate a change in the composition of MLMs, which could be related to the CEC evolution with depth in the sampled sequence.

To assess the possible presence of such different MLMs, and to obtain an objective description of their diffraction behaviour, we have decomposed the peaks mentioned above. It was first assumed that all mixed-layered components, and illite, have a unique contribution in each of these angular ranges. The validity of this assumption was checked in the identification step by the calculation of the whole experimental XRD profile. All experimental XRD patterns were successfully fitted with three contributions. The sharper contribution (FWHM = 0.2-0.5°2θ) likely corresponds to illite and/or detrital mica whereas the other two phases exhibit broader reflections of variable intensities and positions (Tables 3,4; Figs. 6,7). For the Ca-EG diffraction pattern, the positions of these two contributions range from 8.45-8.52 Å (major contribution) and from 8.72-9.22 Å, respectively (Table 3; Fig. 6). These two mixed-layered structures contribute to the Ca-AD XRD pattern at 4.99-5.03 Å, and 5.03-5.07 Å, respectively (Table 4; Fig. 7). These contributions were both attributed to I-Exp MLMs.

To check the validity of the assumed nature of phases contributing to the diffracted intensity, experimental XRD patterns were compared to profiles calculated with the programs developed by [START_REF] Plançon | Phase analysis of clays using an expert system and calculation programs for X-ray diffraction by two-and three-component mixedlayer minerals[END_REF]. It was possible to obtain a satisfactory fit to the experimental data by assuming, in agreement with the decomposition results, the presence of two MLMs, in addition to an illite-rich phase (Fig. 8). The first mixed-layered structure (I-Exp 1 ) corresponds to a highly expandable, disordered (R=0) I-Exp MLM (peak at ~8.5 Å on the Ca-EG pattern) whereas the second MLM (I-Exp 2 ) is less expandable (peak at ~8.9 Å on the Ca-EG pattern). In these two MLMs, the swelling behaviour of the expandable component is heterogeneous as the compositions of I-Exp 1 and I-Exp 2 are respectively 70:20:10 and 40:30:30 (S:V:I ratios). Because these two MLMs were systematically identified after different sample treatments (see below), no attempt was made to try to describe these two MLMs as a unique MLM.

One may note that the decomposition of Ca-AD XRD patterns leads to intensity ratios between the different contributions that are similar for all samples.

On the contrary, the contribution of illite and/or detrital mica is much enhanced on the Ca-EG XRD patterns of samples D and E, as compared to samples A-C, whereas the contribution of I-Exp 1 is decreased for the former samples. This is likely due to the increased contribution of illite crystallites with small coherent scattering domain sizes (CSDS) for samples D and E as shown by the increased breadth of the ~10.0 Å diffraction maximum in the Ca-EG XRD pattern (Fig. 6).

On the Ca-AD XRD patterns, the breadth of the diffraction maximum attributed to the illite and/or detrital mica is systematically low (Fig. 7). It is thus likely that this peak represents the whole contribution for illite and/or detrital mica in samples A-C, whereas it accounts only for the larger crystallites in samples D and E. In the Ca-EG state (Fig. 7) illite crystallites with a smaller CSDS present in samples D and E are included in the I-Exp1 contribution which is thus enhanced as compared to the Ca-AD state (Fig. 6).

Identification of smectite layer components

Hofmann-Klemen treatment. Following the Hofmann-Klemen treatment, all samples show two broad bands at about 17 Å and 9.6 Å (Fig. 9) corresponding to domains containing mostly expanded beidellitic layers and collapsed montmorillonitic layers, respectively. However, the high saddle/peak ratio observed for the 17 Å peak is reminiscent of the interstratification effects described by [START_REF] Inoue | A convenient technique to estimate smectite layer percentage in randomly interstratified illite / smectite minerals[END_REF] The decomposition of the diffraction profile over 2-12 ° 2θ gives a satisfying fit with three diffraction bands (Fig. 11). The overwhelming broad

(2.28>FWHM>1.86) 16.22-17.03 Å band represents the sole contribution of the I-Exp 1 phase identified in Ca-saturated samples. The sharp (0.21>FWHM>0.18) contribution at 9.95-10.07 Å is related to the illite/mica phase, whereas the broad (2.32>FWHM>1.87) 10.17-9.82 Å contribution is likely related to the I-Exp 2 mixed-layer structure. The intensity of the latter contribution is extremely low as compared to that attributed to I-Exp 1 . This contrast arises most likely from their contrasting structure factors over this angular range rather than from their relative proportions. In spite of this low intensity the I-Exp 2 contribution likely integrates the second order of the I-Exp 1 contribution. This is supported by the variability of the I-Exp 2 peak position, and more especially by its shift on the high angle side of the illite contribution which can hardly be accounted for otherwise.

13

C 12 -alkylammonium saturation state. This study was performed after neutralizing the octahedral charge with the Hofmann-Klemen treatment, which produced collapsed and expandable layers, possibly interstratified (see Hofmann-Klemen paragraph). Then, the remaining tetrahedral charge has been investigated using the C 12 -alkylammonium saturation procedure to identify high-and low-charge layers

(2 or 1 alkylammonium layers respectively). Resulting XRD patterns show an intense peak at about 13.6 Å which is typical of low-charge layers, which intercalate only one sheet of alkylammonium cations [START_REF] Lagaly | Determination of the layer charge in mica-type layer silicates[END_REF]. On the low angle side of this broad maximum, a shoulder is visible at ∼ 17.2 Å indicating the presence of high-charge layers with 2 sheets of alkylammonium cations. A weak 10 Å peak is also visible on these patterns (Fig. 12). After decomposition, the broad 13.6 Å peak is shown to include the contributions from three different populations of crystals which scatter X-rays coherently (Fig. 13).

The main 13.5-13.6 Å peak is typical of low-charge layers having one sheet of alkylammonium cations whereas the 17.1-16.5 Å and the 11.9-11. Decomposition of these XRD patterns shows that the 13.6 Å band (1 sheet of alkylammonium cations) is the most intense, indicating that, in most of the layers with tetrahedral substitutions, these represent only about 0.30 charge per O 10 (OH) 2 [START_REF] Olis | The rapid estimation of the layer charges of 2:1 expanding clays from a single alkylammonium ion expansion[END_REF]. The presence of the 16.5-17.1 Å shoulder (2 sheets of alkylammonium cations) shows that some expandable layers present a higher tetrahedral charge (0.35 to 0.40 per O 10 (OH) 2 ). The amounts of Al 2 O 3 and MgO in the <2 µm fraction should vary together with the proportion of less expandable layers. This is not clearly the case (see Table 1) probably because the expected composition variations are too small to be detected by such averaging bulk chemical analyses. The distribution of tetrahedral charge may be responsible for the heterogeneous expansion behaviour observed in intermediate and high-charge layers after K-saturation. According to this hypothesis, the location of the layer charge may be assessed for the three layer types defined above. Low-charge smectite layers are mostly octahedrally substituted, whereas for intermediate-and high charge layers this montmorillonitic charge is complemented by additional tetrahedral substitutions (0.30 and 0.35-0.40 charge per O 10 (OH) 2 , respectively).

MLM variation throughout the profile

In the upper part, the composition of the dominant MLM (I-Exp 1 ) changes progressively with depth as shown by the K saturation test and the migration of its main peak from 17.03 Å (sample E) to 16.22 Å (sample A). This indicates that the amount of high-charge layers increases towards the top of the bentonite bed.

However the increased charge is not related to a significant change in the K-or Al-content in the bulk composition of the clay-size fraction, suggesting that the studied bentonite bed from Charentes is not a K-bentonite type, where K and Al are changed by a post-deposit diffusion process [START_REF] Cetin | Layer charge of the expandable component of illite/smectite in K-bentonite as determined by alkylammonium ion exchange[END_REF].

On the other hand, the observed change in expandability is correlated with the limited but steady CEC increase from the center of the bentonite bed (~74 cmol.kg -1 ) towards its edges (~80 cmol.kg -1 -Table 2). This increase correlates with both Ca-and Na-contents (Fig. 3), indicating that the amount of these cations is ruled by the CEC of the expandable layers in the bentonite, and hence by the layer charge heterogeneities. If this reasoning is correct, the mineral changes observed in the layer are due to re-adjustments in an essentially isochemical system, at least concerning the elements Mg, Al, Si, K and Fe (no visible changes in chemical compositions presented in Table 1). In this isochemical system, the evolution of hydration ability, expandability and CEC with depth in the bentonite bed must be due to different interlayer charge distributions in expandable layers.

For example, for the same layer charge, octahedral and tetrahedral substituted sites may be or not superimposed inside the volume delimited by the upper and lower hexagonal cavities. As a result, the number of highly charged sites may vary: if low, the total charge is spread over the layer surface increasing the CEC and reducing the swelling ability.

CONCLUSION

The studied Charentes bentonite bed, although largely smectitic and containing I/S minerals, does not correspond to a K-bentonite occurrence where K and Al are exchanged for other elements during a diffusion process which gradually replaces smectite by illite layers in a sequence of I-S minerals. It is possible that the Charentes bentonite corresponds to the initial stage of smectite formation from an ash layer, and that it has not been affected by the processes generating K-bentonites usually described. According to this hypothesis, it is clear that the initial clay mineralogy of the bentonite (smectite) is not homogeneous nor monophase at any one given point. In fact the Charentes bentonite shows mineralogical zoning from the edge toward the center even though its chemistry is not zoned.

  of the original sample and of the Li-300 sample in which the octahedral charge has been neutralized. XRD patterns were recorded using a Philips® PW 1730 diffractometer (Ni-filtered Cu-Kα radiation generated at 40 kV and 40 mA), equipped with a stepping motor drive in the goniometer (SOCABIM DACO system). A Co-Kα radiation generated at 40 kV and 40 mA has been used to analyse the samples saturated with C 12 -alkylammonium ions. The usual analytical conditions were 2-35°2θ as a data collection range, 0.025°2θ as scanning step size and 6 s per step as counting time. The smectite samples were chemically analyzed for major elements using ICP-AES (experimental errors are <1% for SiO 2 , Al 2 O 3 , Fe 2 O 3 , MgO;<2% for TiO 2 , MnO, CaO, K 2 O, Na 2 O). Cation exchange capacity (CEC) was obtained by saturation with Mg 2+ , the excess of Mg salt being carefully washed out with ethanol. The Mg 2+ was then displaced by NH 4 + and analyzed by atomic absorption spectroscopy (AAS) in the exchange solution (experimental error <1% for CEC > 60 cmol kg -1 ).

FWHM

  parameters of these elementary contributions were used for a preliminary individual identification of each "clay phase" (type of MLM; %smectite) by comparison with calculated patterns. XRD patterns were calculated using /www.univorleans.fr/ESEM/plancon) which allow the calculation of three-component MLMs without restrictions on the nature of the different layer types or on the junction probabilities. All parameters necessary for such calculations (atomic positions, dspacings) were set as recommended by[START_REF] Moore | X-ray diffraction and the identification and analysis of clay minerals[END_REF] except for the basal spacing of smectite layers with only one sheet of EG molecules which was set to 13.5 Å. Finally, the validity of this preliminary identification was checked by the calculation of the complete XRD profile corresponding to the various elementary contributions identified.

  for I-S MLMs and possibly indicates the coexistence (interstratification) of collapsed and expanded layers in the same "crystals". From their similar respective intensities, and considering the greater contribution of the structure and Lorentz-polarization factors to intensity at low angles, the relative abundance of the 17 Å component appears to be lower than that of the 9.60 Å one.K-saturated ethylene glycol solvated state. XRD patterns obtained from Ksaturated samples in the EG state all exhibit a broad maximum in the 17 Å region (Fig.10). If compared to the 17 Å band in the Ca-EG sample (Fig.4), the width of this 17 Å band is considerably increased and its position for A and B samples is shifted towards lower d-values. This may indicate that the average CSDS is lower in the K-EG state, but a significant decrease of the CSDS would induce a strong shift of the position towards higher d-values. Rather this increased peak width is likely related to the presence of layers that are fully expandable after Casaturation (S-type) and only partly expandable (V-type) or even collapsed to 10Å when K-saturated. As a result, the peak position shifts towards lower d-values (from 17.06 to 16.12 Å for sample A in the in the Ca-EG and K-EG states, respectively). Since the position shift decreases A to E, the relative proportion of such partly expandable layers likely decreases with depth. The K-saturation outlines the charge heterogeneity of expandable layers in the main smectite-rich I-Exp 1 MLM.

  5 Å peaks likely represent the contributions of domains in which layers with contrasting alkylammonium contents are interstratified. The first of these contributions (MLM1) include layers having 2 and 1 sheets of alkylammonium cations (high and low tetrahedral charge respectively) whereas the other contribution (MLM2) include layers with 1 and 0 alkylammonium sheet (low and no tetrahedral charge respectively). DISCUSSION Decomposition of the XRD patterns obtained from our samples after different treatments indicates the systematic presence of two (I-Exp) MLMs whose structural variability contributes to a general change in XRD profiles. The following discussion will first focus on the characterization of layer charge heterogeneity (amount and location), and then try to relate the observed evolution of this heterogeneity to the main trends derived from bulk chemical analysis of the clay fraction.Layer charge heterogeneityFrom the comparison of XRD patterns obtained from Ca-EG and K-EG samples, it is possible to hypothesize the coexistence of expandable layers having contrasting charges and hydration properties. The K + -for-Ca 2+ exchange increases the number of partly or completely collapsed layers (13 and 10 Å, respectively) in the I-Exp MLMs after EG solvation. For the most expandable I-Exp 1 MLM, this induces a shift of the 17 Å peak towards lower d-spacing values. In our series of samples, the peak position shifts from 16.22 (sample A) to 17.02 Å (sample E) with depth (Fig.14) indicating that the proportion of partly or completely collapsed layers in I-Exp 1 increases from E to A, i.e., towards the outside of the bentonite bed.From the variation of layer expandability as a function of the interlayer cation, one can define at least three types of expandable layers in the studied samples: i) low-charge smectite layers that accept 2 sheets of EG molecules (d 001 ~17 Å) in both Ca-and K-saturated states; ii) intermediate-charge smectite layers accepting 2 sheets of EG molecules if Ca-saturated but only one (d 001 ~13 Å) when K-saturated; iii) high-charge layers (vermiculite) that accept 1 sheet of EG molecules when Ca-saturated and are collapsed (d 001 ~10 Å) when Ksaturated.From the presence of domains containing mostly expanded beidellitic layers and collapsed montmorillonitic layers after the Hofmann-Klemen treatment, it is possible to evaluate the relative contributions of octahedral and tetrahedral substitutions to the total layer charge evidenced by[START_REF] Cuadros | Compositional and structural features of the octahedral sheet in mixed-layer illite/smectite from bentonites[END_REF] in smectitic minerals from bentonite deposits. First of all, one may note the much greater contribution of octahedral substitutions as demonstrated by the similar intensities of the 9.6 and 17 Å peaks observed on XRD patterns recorded after the Hofmann-Klemen treatment (Fig.9). As a consequence, expandability possibly depends on the amount of beidellitic substitutions. The C 12 -alkylammonium saturation of samples previously submitted to the Hofmann-Klemen treatment to neutralize their octahedral charge allows one to analyze further this beidellitic charge.

ACKNOWLEDGEMENTS:

  FIGURE CAPTIONS

TABLE CAPTIONS TABLE 1 .

 CAPTIONS1 Comparison of the results given by different identification methods from saddle/peak ratio or peak positions of calculated XRD patterns of three component mixed layers minerals. NA: not analyzed. (See text for details).

TABLE 2 .

 2 Chemical composition and Cation Exchange Capacity (CEC) of the <2 µm fraction of smectite collected at several points in the bentonite layer.

TABLE 3 .

 3 Decomposition values of XRD patterns (8 to 12 °2θ Cu-Kα angular range) of bentonite samples in the Ca-saturated EG state.

TABLE 4 .

 4 Decomposition values of XRD patterns (15 to 20 °2θ Cu-Kα angular range) of bentonite samples in the Ca-saturated AD state.

TABLE 1

 1

	2 I 20% -Exp 80%		Peak position (°2θ Cu-Kα)	Identification
	3 S%	4 V%	1 001	1 002	1 003	1 005	1 006	Srodon (1981)
	80	0	5.11 17.3 Å	9.96 8.88 Å	15.73 5.63 Å	26.40 3.376 Å	31.75 2.818 Å	90%S
	70	10	5.18 17.0 Å	9.89 8.94 Å	15.69 5.65 Å	26.48 3.366 Å	31.74 2.819 Å	95%S
	60	20	5.28 16.7 Å	9.77 9.05 Å	15.62 5.67 Å	26.59 3.352 Å	31.73 2.820 Å	NA
	50	30	5.40 16.4 Å	9.33 9.48 Å	15.54 5.70 Å	26.73 3.335 Å	31.69 2.823 Å	NA
	1 Peaks are labeled as smectite; 2 randomly ordered illite/smectite mixed layer mineral; 3 S:
	smectite (2 EG sheets), 4 V: vermiculite (1 EG sheet).
	I 20% -Exp 80%			Identification
	S%	V%	Peak position	Saddle/pea k ratio	Inoue et al. (1989)	Weir et al. (1975)
	80	0	5.11 17.3 Å	0.38	72%	82%
	70	10	5.18 17.0 Å	0.45	67%	78%
	60	20	5.28 16.7 Å	0.53	62%	74%
	50	30	5.40 16.4 Å	0.60	57%	72%

Cu Ka) Position (°2q Cu Ka) Position (°2q Cu Ka) Position (°2q Cu Ka) Position (°2q Cu Ka) Meunier et al. Fig. 07

				9.98 Å		8.55 Å 5.00 Å
	A A	17.0 Å 15.2 Å	4•0.524 x R 2 = 0.97	B B
	9.99 Å
	9.26 Å	8 15 4.99 Å 8.52 Å 5.03 Å 4.95 Å	16	9	17	10	11 19 9.23 Å 9.99 Å 18	12 20 8.52 Å 5.00 Å 5.04 Å 4.96 Å
			9.98 Å	8.55 Å 7.14 Å	5.60 Å 5.00 Å
									A A
	2 2 Position (°2q 15 4 6 4 6 8 9 10 C 10.02 Å 8.49 Å 8.97 Å 8 9 10 E 8.72 Å 10.02 Å 8 9 10 16 17 18 15 16 17 18 C 5.07 Å 5.03 Å 8 Position (°2q Cu Ka) 10 12 8 10 12 9.98 Å 7.14 Å 14 14 Position (°2q Cu Ka) 8 D 10.02 Å 9 11 12 11 12 8.47 Å 8 9 11 12 19 20 15 16 19 20 4.99 Å 15 16 D 15 16 17 18 19 20 E 5.06 Å 5.00 Å 4.97 Å Position (°2q Cu Ka) Position (°2q 16 18 16 18 5.00 Å 10 11 8.75 Å 8.43 Å 10 11 17 18 17 18 5.07 Å 5.00 Å 20 B C D E 20 B C D E 19 19 4.97 Å	12 12 20 20

Cu Ka) Position (°2q Cu Ka) Position (°2q Cu Ka) Position (°2q Cu Ka)

				17.2 Å	17.2 Å 10.02 Å 9.60 Å 16.1 Å 13.6 Å		7.14 Å				5.00 Å
	A								9.98 Å 9.98 Å		7.14 Å 7.14 Å B				5.00 Å 5.00 Å
												B
							13.54 Å										13.62 Å	A A
																	B A
		17.1 Å 16.22 Å 16.55 Å		10.17 Å 10.10 Å 9.95 Å 11.86 Å			16.42 Å 17.08 Å	10.03 Å	C C D B C 10.08 Å 9.75 Å B 11.67 Å
	3	4	5	6	7	8	9	10 11 12	3	4	5	6	7	8	9	D 10 11 12
	C C	4 2 2 2		6 4 4 Position (°2q Cu Ka) 8 9.98 Å 6 8 6 8 4 6 8 10 13.58 Å	10	8.55 Å 10 10 12	12 14	14 7.14 Å 12 12 16 D D 2 3 4 5 6 7 8 9 10 11 12 16 18 20 5.60 Å 5.00 Å 14 16 18 20 14 16 18 20 18 20 22 24 13.52 Å E E Position (°2q Cu Ka) E D Position (°2q
								Position (°2q Cu Ka) Position (°2q Cu Ka) Position (°2q Cu Ka) Position (°2q Co Ka)
		16.94 Å 16.80 Å		10.10 Å 10.07 Å 10.06 Å 11.78 Å			16.78 Å 16.48 Å	10.04 Å 9.99 Å 10.07 Å 11.79 Å
	3	4	5	6	7	8	9	10 11 12	3	4	5	6	7	8	9	10 11 12
	2 3 4 5 6 7 8 9 10 11 12	2 3 4 5 6 7 8 9 10 11 12
	E			Position (°2q Cu Ka)							Position (°2q Cu Ka)
	E
							13.52 Å
			17.03 Å 16.62 Å			9.82 Å 10.06 Å 11.50 Å
								10.08 Å
	3	4	5	6	7	8	9	10 11 12
	2 3 4 5 6 7 8 9 10 11 12
				Position (°2q Cu Ka)

Co Ka) Position (°2q Co Ka) Position (°2q Co Ka) Position (°2q Co Ka) Position (°2q Co Ka)

I/S MLMs ;

peak position ;

Full Width at Half Maximum intensity


Guillaume Beslon

Vincent F Liard

David P Parsons

Jonathan Rouzaud-Cornabas

In silico experimental evolution shows that complexity can rise even in simple environments

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Methods

Experimental design and complexity measures

Experimental design • To unravel the origin of molecular complexity, we evolved populations in an environment where the simplest possible organism can strive. • We evolved 300 populations of 1024 individuals for 250,000 generations under 3 mutation rates and monitored the evolution complexity.

In silico experimental evolution shows that complexity can rise even in simple environments Systems biology, often viewed as reverse engineering of biological systems, deals however with objects that have not been designed. Neither do they have a prefdefined purpose nor do they follow engineering rules. Indeed, we don't know what are the "design rules" that evolution imposes to biological systems while this knowledge would be a valuable interpretative framework for systems biology.

One of the recurrent questions on that matter is the origin of the striking molecular complexity of biological systems. Answering this question requires deciphering the complex interactions between all the forces that drive evolution, including selective and non-selective ones. In this context, simulation is a valuable tool as it enables to observe how organisms grow in complexity (or do not) when they evolve in environments which complexity is perfectly controlled.

Aevol (www.aevol.fr) is an In Silico Experimental Evolution (ISEEaka digital genetics) platform developed by the Beagle team to study the evolution of genome structure. Aevol is based on three principles that makes it perfectly suited to study the evolution of complexity:

Complexity measures

  Guillaume Beslon, Vincent Liard, David Parsons, Jonathan Rouzaud-Cornabas INRIA-Beagle team (INSA-Lyon), Lyon, France

  Qualitative measure: "simple" organisms are those encoding only proteins with the same m and w values. Genomic complexity: quantity of information encoded on the genome (total amount of coding sequences). Functional complexity: quantity of information encoded on the proteome (number of different parameters). scale : 38 bp scale : 55 bp

Discussion

Results

(1) Organisms evolved complex functional structures in 66% of the simulations Whatever the mutation rate, ≈1/3 of the simulations led to "simple" organisms with few genes and a low functional complexity (A). ≈2/3 of the simulations led to "complex" organisms despite the simplicity of the target function (B).

(2) Complex organisms accumulate more information at the genomic and functional levels Genomic complexity is strongly bounded by mutation rates (A) due to robustness constraints on the genome (Knibbe et al., 2007;Fischer et al., 2014). Mutation rates also constrain the functional complexity (B) but this effect is less stringent at the functional level.

(3) Simple organisms are fitter than complex ones Whatever the complexity measure, we observe a clear trend for simple organisms to be fitter than complex ones after 250,000 generations. This demonstrates that in our simulations complexity is not driven by selection.

On the opposite, complex functional structures have evolved in spite of selection. (4) Despite the advantage of being simple, complex organisms evolve greater complexity on the long term The simple/complex identities are determined early on in the simulation and generally conserved thereafter (A). Complex organisms evolve greater complexity (B); their fitness grows but remains far below simple organisms.

A. Genome and proteome of a simple organism B. Genome and proteome of a complex organism A. Distribution of genomic complexity for complex (top) and simple (bottom) organisms. The higher the mutation rate, the lower the genomic complexity. Genomic complexity is strongly limited by mutational robustness.

B. Distribution of functional complexity for complex (top) and simple (bottom) organisms. The higher the mutation rate, the lower the functional complexity.

A. Fitness at generation 250,000 vs genomic complexity. The higher the genomic complexity, the lower the fitness. Simple organisms approach the optimum fitness ( f opt = 1 ). Mean fitness of complex organisms: f = 0.38.

A. Starting from simple organisms at generation 0, organisms' identity (simple vs complex) is determined before generation 10,000 and generally maintained for the rest of the simulation.

B. Long-term evolution of functional complexity in a complex organism. Functional complexity and fitness continuously grow during the 250,000 generations but the fitness remains far below that of simple organisms. Our results show that, in such a simple constant environment, there is a decoupling between the molecular complexity of the organisms and the complexity of the environment. This shows that selection for complexity is not mandatory for complexity to evolve and that complex biological structures could flourish in conditions where complexity is not needed. Reciprocally, the global function of complex biological structures could very well be simple. We think this result is greatly significant for both evolutionary biology and systems biology.