Nils Caillerie
email: nc691@georgetown.edu

Geodesic trail formation in a two-dimensional model of foraging ants with directed pheromones

Keywords: velocity-jump process, foraging ants, individual-based model, pheromone deposition, pattern formation, chemotaxis model. AMS Class. No: 92D50, 92B05, 60G50, 60J75, 60J25

We introduce an individual-based model of interacting particles imitating a colony of ants looking for a food source in a continuous plane. The mechanism describing communication between ants via pheromone deposition is inspired by a model of directed interacting particles previously introduced in [Boissard Degond Motsch, Trail formation based on directed pheromone deposition]. Here, we add a food source and introduce two types of pheromones: one left by ants leaving the food source and one left by ants leaving the nest. The particularity of our model is that we let the ants disperse in a two-dimensional space without a pre-existing lattice and we do not assume that the ants know their way back to the nest. We present simulations of our model and we investigate the ability of the colony to select the shortest path from the nest to the food source in various situations: with one or several food sources, with a food source whose location changes, with a food source behind an obstacle. Finally, we discuss the biological relevancy of our assumptions.

Introduction

Social interaction is a key element for the survival of a colony of ants. Ants are known to have low cognitive capacities but are able to survive as a group using work division, invasive and defensive strategies, communication, food stocks and sometimes harvests. One experimental study suggests that a minimal number of individuals is needed for the colony to have a functional organization [START_REF] Beekman | Phase transition between disordered and ordered foraging in Pharaoh's ants[END_REF]. Very simple interactions between individuals with low cognitive capacities can achieve very complex tasks, such as building a nest for the colony [START_REF] Khuong | Stigmergic construction and topochemical information shape ant nest architecture[END_REF], developing war strategies to protect the nest [START_REF] Mary | Ant wars: combat strategies, territory and nest defence in the leaf-cutting antAtta laevigata[END_REF], following routes and regulate the traffic to reduce congestion [START_REF] I D Couzin | Self-organized lane formation and optimized traffic flow in army ants[END_REF][START_REF] Dussutour | Optimal traffic organization in ants under crowded conditions[END_REF] or find food and bring it back to the nest using an optimal route in the process [START_REF] Beckers | Trails and U-turns in the selection of a path by the ant Lasius niger[END_REF][START_REF] Garnier | Path selection and foraging efficiency in Argentine ant transport networks[END_REF][START_REF] Goss | Self-organized shortcuts in the Argentine ant[END_REF]. It has also been observed that some ants, e.g. the Argentine ants Iridomyrmex humilis, can walk their way into a maze, find a food source and bring it back to their nest using a short path [START_REF] Goss | Self-organized shortcuts in the Argentine ant[END_REF]. In this paper, we are interested in the issue of food localization and optimization of the transport by a colony of ants.

The formation of trails has been observed in many experiments, [START_REF] Beckers | Trail laying behaviour during food recruitment in the ant Lasius niger (L.)[END_REF][START_REF] Beckers | Trails and U-turns in the selection of a path by the ant Lasius niger[END_REF][START_REF] I D Couzin | Self-organized lane formation and optimized traffic flow in army ants[END_REF][START_REF] Detrain | The influence of the physical environment on the self-organised foraging patterns of ants[END_REF] among many others. It is the result of simple local interactions, such as brief antennas contacts [START_REF] Gordon | What is the function of encounter patterns in ant colonies?[END_REF] or distant communication, via deposition of chemical markers called pheromones. We will focus only on pheromones deposition in this paper.

The principle of pheromone communication is simple. An ant can leave a pheromone drop using the stinger on its abdomen [START_REF] Hangartner | Trail laying in the subterranean ant, Acanthomyops interjectus[END_REF][START_REF] Jackson | Modulation of pheromone trail strength with food quality in Pharaoh's ant, Monomorium pharaonis[END_REF][START_REF] Wilson | Chemical communication among workers of the fire ant Solenopsis saevissima (Fr. Smith) 1. The Organization of Mass-Foraging[END_REF]. The ant then keeps walking but the pheromone drop remains where the ant left it. When a new ant arrives on site, it obtains the information that an ant was formerly here, but not only. Biologists argue that the pheromone drop carries more information. Depending on the studied species, pheromones drops can give different types of information. An ant can for instance obtain information on the orientation of the ants which laid the pheromone through a mechanism called osmotropotaxis (see [START_REF] Calenbuhr | A model for osmotropotactic orientation (II)[END_REF][START_REF] Calenbuhr | A model for osmotropotactic orientation (I)[END_REF] for a literature review on the subject). Furthermore, some ants are able to lay pheromones with different chemical compositions [START_REF] Tristram | Pheromones and animal behaviour: communication by smell and taste[END_REF]. For example Myrmica sabuleti specimens and Pheidole megacephala (big headed ant) specimens can leave two different pheromones depending if they have located a food source or not [START_REF] Cammaerts | Food recruitment strategies of the ants Myrmica sabuleti and Myrmica ruginodis[END_REF][START_REF] Dussutour | The role of multiple pheromones in food recruitment by ants[END_REF], the Pharaoh's ant Monomorium pharaonis is also able to depose attractive or repellent pheromones [START_REF] Elva | An agent-based model to investigate the roles of attractive and repellent pheromones in ant decision making during foraging[END_REF]. The ponerine army ant Leptogenys distinguenda can lay two pheromones marking either raid or emigration trails [START_REF] Witte | Coordination of Raiding and Emigration in the Ponerine Army Ant Leptogenys distinguenda (Hymenoptera: Formicidae: Ponerinae): A Signal Analysis[END_REF]. An ant which lays a pheromone signal can also modulate the importance of the information by leaving long or short-lasting pheromones. This was observed, among other species, for the Pharaoh's ant [START_REF] Jackson | Modulation of pheromone trail strength with food quality in Pharaoh's ant, Monomorium pharaonis[END_REF] or for the big headed ant [START_REF] Dussutour | The role of multiple pheromones in food recruitment by ants[END_REF]. These signals carry simple informations (location and orientation of the ant, chemical concentration, chemical composition...) but through multiplication of a large number of signals, the colony as a whole is able to develop complex social structures, in particular, to form patterns such as trails.

When a colony of ant carries food from a location to the nest, one can observe the formation of a trail (that is, a path with a high concentration of ants and pheromones) between the food source and the nest. One remarkable observation about those pheromone trails is that they optimize the time of food transport. Simply put, the ant colony is able to find the shortest path from the nest to the food source. When facing an environment with multiple possible routes to a food source, an ant colony will most of the times choose the shortest one [START_REF] Garnier | Path selection and foraging efficiency in Argentine ant transport networks[END_REF][START_REF] Goss | Self-organized shortcuts in the Argentine ant[END_REF]. Finding the shortest path between two points can be viewed as an optimization problem. Experiments have shown that ants are actually able to deal with more complex situations, like a dynamical environment with open/closed bridges, and solve optimization problems like the well-known "tower of Hanoi" [START_REF] Reid | Optimisation in a natural system: Argentine ants solve the Towers of Hanoi[END_REF]. This is rather spectacular since, once again, ants have low cognitive capacities. In particular, there is no central power leading the foraging ants and only local interactions between them.

Actually, the phenomenon that causes this is rather simple to understand. Assume that there exists two paths connecting a food source to the ants' nest. The shortest path of the two allows ants to bring the food faster so ants walking back and forth on this track will make more travels per unit of time than their counter specifics on the longest path. Therefore, they will make the travel more often and hence leave more pheromones so more ants will be recruited on the shortest track.

This principle has been understood a while ago and has nourished a field of probability theory called "reinforced random walks". One goal of this field is to find geodesics on graphs using random walkers (whose behavior is inspired by ants) on the graph, that use the vertices (with lengths) to go from one node to the other. When walking on a vertex the random walkers (robot ants so to speak) leave a signal (pheromone) giving more weight to this particular vertex, thus, raising the probability that the next ant will choose the same path. So-called "ants algorithms" have proven themselves very efficient to solve optimization problems such as the well-known "salesman problem" [START_REF] Dorigo | Ant colony system: a cooperative learning approach to the traveling salesman problem[END_REF][START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF][START_REF] Stützle | The Max-Min ANT System and Local Search for Combinatorial Optimization Problems[END_REF] among many others. Moreover, rigorous proofs exist to mathematically establish their efficiency [START_REF] Jayadeva | Ants find the shortest path: a mathematical proof[END_REF]. Ants algorithms also prove themselves capable of finding geodesic paths in mazes [START_REF] Bodnar | Mathematical model for path selection by ants between nest and food source[END_REF][START_REF] Vela-Pérez | Ant foraging and geodesic paths in labyrinths: Analytical and computational results[END_REF]. In [START_REF] Panait | Ant foraging revisited[END_REF][START_REF] Panait | Learning ant foraging behaviors[END_REF][START_REF] Panait | A Pheromone-Based Utility Model for Collaborative Foraging[END_REF], the authors considered a individual-based model on a two-dimensional grid. Ants were modeled by agents that can walk on either one of the nine adjacent cells but choose the one where the pheromone concentration is higher. The agents leave pheromones where they are and they leave different pheromones depending if they are walking away from the food source of if they are walking away from the nest. Their algorithm proves itself capable of finding optimal paths in dynamical environments (where the food source's location changes) or environments with obstacles.

More biologically relevant mathematical models have been introduced to understand the formation of trail following patterns. We refer to [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF] for a wide literature review on the subject. Their reading of the literature showed that there are few truly two-dimensional continuous models of foraging ants. Most models either consider a one-dimensional space or a two-dimensional space with pre-existing pheromone trails or they consider a two-dimensional space with a grid or a fixed lattice.

We refer to [START_REF] John | Collective effects in traffic on bi-directional ant trails[END_REF] and [START_REF] Nishinari | Modelling of self-driven particles: Foraging ants and pedestrians[END_REF] for some examples of one-dimensional cellular automata. In [START_REF] Johnson | A mathematical and experimental study of ant foraging trail dynamics[END_REF], the authors analyzed a system of one-dimensional partial differential equations to study the emergence of traveling waves on a trail between a food source and a nest.

There exists two-dimensional models which consider a pre-existing trail and focus on the way ants sense the trail or the way they regulate traffic [START_REF] Calenbuhr | A model for osmotropotactic orientation (II)[END_REF][START_REF] Calenbuhr | A model for osmotropotactic orientation (I)[END_REF][START_REF] I D Couzin | Self-organized lane formation and optimized traffic flow in army ants[END_REF]. Other models focus on the decision process which leads ants to follow one trail or the other. In [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF][START_REF] Goss | Self-organized shortcuts in the Argentine ant[END_REF], the authors considered two Monte-Carlo simulations to explain the formation of trails in a chemically unmarked area and the decision process to select one branch or an other in a diamond-shaped bridge. In the first simulation, the space is modeled by a two-dimensional mesh. In the second, the ants are constrained to use one branch or the other. Ordinary differential equations (ODEs) models have also been introduced to quantify the branch selection process in diamond-shaped bridges [START_REF] Peters | Analytical and numerical investigation of ant behavior under crowded conditions[END_REF] or to analyze the reinforcement or the evaporation of pre-existing pheromone trails [START_REF] Edelstein-Keshet | Simple models for trail-following behaviour; Trunk trails versus individual foragers[END_REF][START_REF] Watmough | A one-dimensional model of trail propagation by army ants[END_REF]. More two-dimensional models exist [START_REF] Schweitzer | Active random walkers simulate trunk trail formation by ants[END_REF][START_REF] Tao | Flexible Foraging of Ants under Unsteadily Varying Environment[END_REF] but those consider also a fixed lattice. In all these models, either the ants walk on a discrete lattice or the pheromone trails that the ants are constrained to follow is prescribed (in particular, the system does not produce the pheromone trails itself).

A two-dimensional model that does not consider a pre-existing lattice is the Boissard-Degond-Motsch model [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF]. In this model, ants are able to explore a two-dimensional space. Ants leave one type of pheromones behind them that tell other ants in what direction they were walking when they deposed the pheromone. Their model allows two different interactions: non-polar ones, where ants can distinguish the orientation of a pheromone but not its direction, or polar ones. In the present paper, we will only focus on the second kind of interactions. When considering polar interactions, Boissard, Degond and Motsch observed that the system was able to produce pheromone trails (that is, a large number of aligned pheromones that are oriented in the same direction) that ants would follow preferably. It is, to our knowledge, the first model in which the system was able to create pheromone trails without assuming a pre-existing lattice. Their model however, did not imply a food source.

More recently, Ryan [START_REF] Ryan | A model for collective dynamics in ant raids[END_REF] proposed a two-dimensional model of foraging ants, without a preexisting lattice. His model considered an ant colony coming out of a nest and looking for a food source within the environment. In his model, once an ant found the food source, it goes directly to the nest using the shortest path, leaving pheromones behind itself to recruit other ants on the trail. The model also includes collective strategies to self-regulate the traffic flow on the path. In Ryan's model, the ants already know the shortest way back to the nest. Therefore, in his model, the colony's collective strategy is important only to locate the food source and regulate the traffic flow. The hypothesis that ants (as individuals) know the shortest way back to the nest was also assumed in reaction-diffusion models of foraging ants. Those were mathematically analyzed in [START_REF] Alonso | Analysis of a chemotaxis system modeling ant foraging[END_REF][START_REF] Amorim | A continuous model of ant foraging with pheromones and trail formation[END_REF][START_REF] Amorim | Modeling ant foraging: A chemotaxis approach with pheromones and trail formation[END_REF]. We will adopt a very different point of view in the present paper. Namely, we will assume that individuals do not know their way back to the nest and the colony must adopt a collective strategy both to locate the food source and to bring the food back to the nest.

Let us summarize. To our knowledge, most models of foraging ants consider colonies on a discrete space, like a graph, a cellular automaton or a fixed lattice. These models prove themselves efficient to find geodesic paths on the discrete set but are less biologically relevant than continuous models. Most continuous models assume that the pheromone trails are prescribed and focus on the way ants are recruited on those trails rather than on their formation. To our knowledge, two-dimensional models without a pre-existing lattice, in which the system self produces the pheromones trails are rather rare. Individual-based models either focus solely on the formation of trails [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF] or consider that individuals are able to find the shortest way to bring food back to the nest without any help from others [START_REF] Ryan | A model for collective dynamics in ant raids[END_REF].

In this paper, we build an individual-based two-dimensional continuous model in which the colony self produces the pheromones trails. The crucial assumption of our model is that the ants do not have knowledge of where the food source and the nest are until they reach them. In particular, the route back to the nest is not prescribed. Our model is very similar to the Boissard-Degond-Motsch model. We will consider the same mechanism of pheromone deposition, the same mechanism of ant recruitment on trails and we will take the same parameter values.

Since our ants do not individually keep track of where the food source and the nest are, intelligent collective strategy is needed. Biological evidence [START_REF] Cammaerts | Food recruitment strategies of the ants Myrmica sabuleti and Myrmica ruginodis[END_REF][START_REF] Dussutour | The role of multiple pheromones in food recruitment by ants[END_REF] suggest that a possible strategy is to use two different pheromones, one for ants which have found the food source and one for ants which are still looking for it. This is why, unlike Boissard Degond and Motsch, we will consider two populations: a population of foraging ants and a population of ants coming back to the nest with food. The foraging ants will leave pheromones that indicate their direction to the ants with food. The ants with food will do the same with a second kind of pheromone. As in [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF], we will consider only interactions between the ants and the pheromones. In particular, we will not assume that ants can collide with each other or that they directly communicate when bumping into each other. We will also consider polar-interactions between ants and pheromones, which means that ants are able to know in what orientation and in what direction the pheromone is pointing to.

The outcome of our model is that the colony is able to find the food source and to bring it back to the nest, using a short path. The geodesic path (in most situations, the geodesic path will be the straight line between the food source and the nest) is never followed by an ant all the way since it requires that the ant keeps a ballistic trajectory for a very long time (in particular, the geodesic path has a zero-probability to be walked all the way).

Our paper is organized as follows. In Section 2, we precisely describe the model, we explain some assumptions made for the simulations and give our choice of parameter values. In Section 3, we present the outcome of various simulations of the model: with only one food location, with two food locations, with a food source whose location changes, with an obstacle between the food and the nest and finally, with an obstacle that appears during the simulation. In Section 4, we discuss our model and results and give ideas to improve the model from a biological perspective. Finally, we draw a conclusion and give perspectives for future work.

The model

We consider a model of interacting random walkers on a continuous plane, leaving particles carrying information behind them. In view of our motivation, we will call the random walkers "ants" and the particles "pheromones".

Our model is very similar to the one of [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF]. Namely, the way ants move and choose their directions are the same. Unlike [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF] though, we consider a food source, two types of pheromones and two types of ants:

• ants that are looking for food,

• ants which have found food and are trying to bring it back to the nest. Moreover, unlike [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF], we consider that pheromones keep the direction of their "parent" ant as an angle in [0, 2π) and not as a unit vector. We emphasize that this last modification is purely superficial and does not change the dynamics of trail formation.

The nest is modeled by a disc centered at the origin of radius R nest > 0 and the food source by a compact set Ω ⊂ R 2 such that Ω ∩ D(0, R nest ) = ∅, which means that the food source and the nest are at two different places.

We consider N ants moving in a 2-dimensional space. Every ant is either a "foraging" ant or an ant "with food" but this status can change. We denote by N f (t) and by N w (t) the number of foraging ants and ants with food respectively at time t ≥ 0. Each foraging ant i is described by its position x i ∈ R 2 and the direction of its motion θ i ∈ [0, 2π). Each ant with food j is described by its position y j ∈ R 2 and the direction of its motion ω j ∈ [0, 2π).

We assume that ants are able to depose two types of pheromones: foraging ants depose the first type of pheromones. From now on, we will call those the "green pheromones" out of simplicity. The ants with food on the other hand lay the second kind of pheromones. We will call those the "blue pheromones". We denote by P g (t) the number of green pheromones and by P b (t) the number of blue pheromones. Each green pheromone k is described by its position z k and by its direction α k ∈ [0, 2π). Each blue pheromone m is described by its position ζ m and by its direction β m ∈ [0, 2π). The foraging ants are only sensitive to the blue pheromones. Since those pheromones are laid by ants with food, which are going away from the food source, following the direction of this pheromone will make it easier for foraging ants to find the food source. The same mechanism with green pheromones will enable the ants with food to find their way back to the nest.

Once a pheromone is laid, it remains active (in other words, detectable by an ant) for an exponential time with parameter 1 Tp , where T p > 0 is the mean activity time of pheromones. We assume that the pheromones have no spatial dynamics: until it is no longer active, a pheromone stays where it is.

Unlike the pheromones, the ants do move. Every ant follows a so-called "Run & Tumble" motion (or velocity-jump process). During the running phase, we assume that an ant goes in a straight line with velocity c > 0 in the direction given by its angle θ or ω such that the motion dynamics of foraging ants and ants with food is given by

• x i (t) = c • cos θ i (t) sin θ i (t) , (2.1)
•

y j (t) = c • cos ω j (t) sin ω j (t) . (2.2)
The "Tumble" is an instantaneous phase of velocity redistribution process which is different depending on the status of the ant and on the pheromones' concentration. We explain this process in details in the next two subsections. We assume that the radius of detection of an ant is R > 0 regardless of the pheromone type or the ant's status. This means that the ant is sensitive to a pheromone if and only if the Euclidean distance between the pheromone and the ant is less or equal to R.

Foraging ants

After the end of its running phase, a foraging ant chooses a new direction in [0, 2π) depending on the pheromones' concentration.

Random velocity jumps

If there is no blue pheromone within the radius of detection of the ant, we assume that the new direction θ i of the ant is chosen randomly such that

θ i (t) ≡ θ i (t) + ε i (t) mod(2π), (2.3)
where θ i (t) is the current direction of the ant and (ε i (t)) i,t is an independent family of Gaussian random variables with zero mean and variance σ 2 > 0.

Once a foraging ant has chosen this direction, it keeps it for an exponential time of parameter λ f > 0 and then, a new tumble occurs.

Trail recruitment jumps

If there are blue pheromones within the radius of detection of the foraging ant, the ant chooses one of these pheromones uniformly and aligns its direction with the chosen pheromone such that its new direction θ i is

θ i (t) = β M i , (2.4)
where

M i is uniformly distributed in {m ∈ N, x i (t) -ζ m ≤ R}, where • is the standard Euclid- ian norm on R 2 .
After the ant has made a trail recruitment jump, the next velocity jump occurs after a random exponentially distributed time with parameter λ b • |{m ∈ N, x i (t) -ζ m ≤ R}|, where t is the time of the trail recruitment jump and |•| is the cardinal of the set. This means that the higher the number of blue pheromones within the detection zone, the shorter the time until the next tumble.

Laying pheromones

We assume that, with a rate ν g > 0, the foraging ants lay green pheromones, which means that each foraging ant lays a green pheromone at every ticking of an exponentially distributed clock with parameter ν g . When a foraging ant i lays a green pheromone at time t, a green pheromone k is created with the same position as the ant but in the opposite direction

z k = x i (t), α k ≡ π + θ i (t) mod(2π).
(2.5)

Finding the food source

When a foraging ant finds the food source, i.e. x i (t) ∈ Ω, a tumble instantaneously occurs: the ant's location does not change but the ant turns in the opposite direction and becomes an ant with food, which means that its new orientation ω j (t) is given by

ω j (t) ≡ π + θ i (t) mod(2π), (2.6)
where θ i (t) is its current direction. The next tumble will occur as was previously planned by the ant.

Ants with food

The random motion of the ants with food is pretty similar to the one of the foraging ants but ants with food only lay blue pheromones and are sensitive only to green pheromones. After its running phase, an ant with food chooses a new direction in [0, 2π) depending on the pheromones' concentration.

Random velocity jumps

If there is no green pheromone within the radius of detection of the ant, we assume that the new direction ω j of the ant is chosen randomly such that

ω j (t) ≡ ω j (t) + ε j (t) mod(2π), (2.7)
where ω j (t) is the current direction of the ant and (ε j (t)) j,t is an independent family of Gaussian random variables with zero mean and same variance σ 2 > 0 as the foraging ants.

Once an ant with food has chosen this direction, it keeps it for an exponential time of parameter λ w > 0 and then, a new tumble occurs.

Trail recruitment jumps

If there are green pheromones within the radius of detection of the ant with food, the ant chooses one of the pheromones uniformly and aligns its direction with the chosen pheromone such that its new direction ω j is

ω j (t) = α K j , (2.8)
where

K j is uniformly distributed in {k ∈ N, y j (t) -z k ≤ R}.
When the ant makes a trail recruitment jump, it chooses a random exponentially distributed time with parameter λ g • |{m ∈ N, x i (t) -ζ m ≤ R}| and will not make a velocity jump until this time. As for the foraging ants, this means that the tumbles occur more often when there are many green pheromones.

Laying pheromone

We assume that with a rate ν b > 0, the ants lay blue pheromones. When an ant with food j lays a blue pheromone at time t, a blue pheromone m is created with the same position as the ant but in the opposite direction

ζ m = y j (t), β j ≡ π + α j (t) mod(2π).
(2.9)

Finding the nest

When an ant with food finds the nest, i.e. y j (t) ∈ D(0, R nest ), a tumble instantaneously occurs: the ant chooses a new direction uniformly on [0, 2π) and becomes a foraging ant. Its new direction θ i (t) is therefore distributed as

θ i (t) ∼ Unif ([0, 2π)) .
(2.10)

The next tumble will occur as was previously planned by the ant.

Dealing with an obstacle

In some simulations, we will consider the existence of an insuperable obstacle. We model this obstacle by a rectangle

[O l , O r ]×[O d , O u ] in the plane such that ([O l , O r ] × [O d , O u ])∩D(0, R nest ) = ∅ and ([O l , O r ] × [O d , O u ]) ∩ Ω = ∅,
which means that the obstacle is not located at the same place as the nest or the food source. We describe here the dynamics of an ant, regardless of its status, when it encounters an obstacle. The ant tries to walk around the obstacle. This means that the spatial dynamics of the ant is not described by the running phase ((2.1) or (2.2)) anymore but rather by this "walking around" phase:

• x i (t) = c • (0, sign(sin θ i (t))), if x i (t) ∈ {O l , O r } × [Od, Ou], (sign(cos θ i (t)), 0), if x i (t) ∈ [O l , O r ] × {O d , O u } , (2.11) • y j (t) = c • (0, sign(sin ω j (t))), if y j (t) ∈ {O l , O r } × [Od, Ou], (sign(cos ω j (t)), 0), if y j (t) ∈ [O l , O r ] × {O d , O u } .
(2.12)

Figure 1: Illustration of the behavior of an ant facing an obstacle (one example). When arriving at the foot of the obstacle from the left, the ant starts to walk around the obstacle. In this example, the ant was going to the East-North-East direction so the ant walks around the obstacle going north.

When the ant no longer faces the obstacle, it keeps the direction that it had before it encountered the obstacle (unless a tumble occurred in between).

This means that an ant will systematically translate to its left or right when located at the foot of the obstacle. It will choose left or right according to its current orientation. It then gets back to a normal run phase when the obstacle is away. The fig. 1 gives a simple illustration of the behavior of an ant at the foot of the obstacle.

We emphasize that a tumble can still occur during this phase but that the dynamics will be determined by (2.11)-(2.12) until the ant is away from the obstacle.

Simulations parameters

For the sake of simulations, we add more parameters to our model.

Discrete time Model

We use time steps of size ∆t > 0 and we make any time related random variables T discrete by considering ∆t • T ∆t instead, where • is the upper integer part. We stop the simulation at a final time T f .

"Initial" conditions

At t = 0, we assume that a single foraging ant leaves the nest at position (0, 0) with a direction chosen uniformly on [0, 2π). Then, every second, a new foraging ant leaves the nest at position (0, 0) with the same direction probability distribution until the maximal number of ants N is reached.

Boundary conditions

We restrict our study to the square box

[-l 2 , l 2 ] × [-l 2 , l 2 ]
. When an ant reaches the boundary of the box, we suppose that it dies, regardless of its status. It is then instantaneously replaced by a new foraging ant, which comes out of the nest with direction chosen uniformly on [0, 2π).

Maximal number of pheromones

To keep the computations affordable, we impose a maximal number of pheromones that the system can support. When the maximal number P max b of blue pheromones or the maximal number P Maximal number of green pheromones 1000 of green pheromones is reached, the corresponding ants stop deposing those pheromones until the disappearance of other pheromones allow them to produce some more.

Choice of parameters

We recap here all the parameters of our model and specify what values we choose for them. The Table 1 shows the values of the model parameters and the Table 2 shows the values of the simulations parameters. When specified in the tables, this parameter value is chosen in all simulations shown in Sect. 3. When not specified, the parameter value depends on the simulation and will be specified in the corresponding subsection.

We emphasize that, when such correspondence can be made, we systematically choose the same parameter values as in [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF]. We discuss the biological relevancy of such choices in Sect. 4.

Results

Typical dynamics of the system

We show in fig. 2 the outcome of one simulation with T f = 200 seconds and where Ω is a disc of radius 2 centimeters centered at point (0, 40). The so-called green pheromones are represented by green sticks showing in which direction the pheromone is oriented and the blue pheromones by blue sticks. Black squares represent foraging ants and red squares represent ants with food. The nest is represented by a black circle and the food source by a red circle. After 30 seconds, there were 31 foraging ants in the environment, which were all making random velocity jumps and deposing green pheromones. No ant found food yet. After 56.20 seconds, one foraging ant found food and became an ant with food. The ant then proceeded to come back to the nest following the green pheromones that it left when it was still foraging. When it didn't find any pheromones ahead, it started to make random velocity jumps again, and made a detour but the green pheromones in the square [-10, 0] × [0, 10] put it back on track (see the middle-left part of the figure and more specifically, the blue pheromones). It took the ant 22.2 seconds to walk from the food source back to the nest, whereas the geodesic (i.e. the straight line which is 37 centimeters long) would have taken 37/c=18.5s. After 100 seconds, there were two ants with food, taking a different (presumably shorter) path to get back to the nest. After 200 seconds, there were 24 ants with food and the overall pattern was that ants with food walked on the straight line from the food source to the nest.

Geodesic path from the food source to the path

From now on, for a better understanding of the simulations, we only represent the pheromone trails and do not represent the ants in our figures.

We study the long time behavior of the system and we investigate the ability of the ants to optimize their food transport, that is, to find the geodesic that links the food source to the nest. In order to measure the length of a path, we adopt the following perspective: given that all ants constantly walk with speed c=2cm/s, we let the ants with food keep a memory of the time spent since they encountered the food source. When they finally find their way back to the nest and start foraging again, we call "path followed by the ant" the trajectory of this ant. In other word, a "path followed by an ant" is a set of the form

{y j (t) | T 0 ≤ t ≤ T 1 , y j (T 0 ) ∈ Ω, y j (T 1 ) ∈ D(0, R nest )} (3.13)
and the length of this path is defined as

L := c (T 1 -T 0 ) . (3.14)
We show in fig. 3 and fig. 4 the typical outcome of a simulation after T f = 1000 seconds when Ω is a disc of radius 2 centimeters centered at (0, 40). We first notice that there exists a "pheromone highway", that is, a high concentration of pheromones next to the geodesic. The shortest recorded path followed by an ant is 38 centimeters long, which is close to the 37 centimeters of the geodesic (there is 40cm between the two centers of the food source and the nest and the radii are 1cm and 2cm long). We represent in the bottom-right corner of fig. 4 the evolution of the shortest recorded path's length. The upper-left corner of fig. 4 shows evidence of a phase transition. It represents the mean-value of (sin α k ) k , where (α k ) k is the orientation of all green pheromones. Since the food source is located North to the nest, we expect many green pheromones to be oriented to the South and therefore, we expect the sine of this orientation to be close to -1. We can see that, between 0 and 200 seconds, the mean sine of the green pheromones orientation first gathers around the mean value 0 of the sine of the uniform law on [0, 2π), as predicted by the strong law of large numbers (let us recall that the direction of the foraging ants is initially uniformly distributed). But after 200 seconds, due to the presence of ants with food (see the bottom-left corner for comparison), the green line stabilizes around the middle of 0 and -1. We emphasize that it does not stabilize around -1 due to our boundary conditions. Indeed, when foraging ants reach the boundary, they die and are replaced with an ant whose orientation is uniformly distributed in [0, 2π). The blue line, as we can see in the upper-right corner of Figure 3, stays close to 1, which means that most of the blue pheromones are oriented in the North direction.

Disconnected food source

From now on, we will show the outcome of our simulations by representing the green and blue pheromones but we will show the blue pheromones in priority, in the same fashion as in the right-hand side of fig. 3. We emphasize that, where there is a high concentration of blue pheromones, there is also a high concentration of green pheromones, even though they may not appear in the figures.

In these simulations, we assume that the food source is disconnected, namely that it is the reunion of a disc of center (30, 30) with radius 2 centimeters and an other disc of center (-a, a) and same radius. From now on, we will call the first disc "the North-East food location" and the second disc "the North-West food location". We take different values for a > 3 (let us notice that the food source and the nest have a non-empty intersection when a ≤ 3). Given what happened in the previous simulations, we would expect the ant colony to select the shortest path, i.e. to have more pheromones oriented in the North-West direction when a < 30 and and more pheromones oriented to the North-East when a > 30. This is indeed the case for the simulations shown in fig. 5, when a = 5, 10, 15, 20, 35, 40, 50 but as, we can in the case a = 25, the probability that the colony does not privilege the shortest path is non-zero. In some situation, like the simulation with a = 45, the colony goes to both food locations.

We show in fig. 6, the probability that the North-West food location (i.e. the disc centered at (-a, a)) is chosen over the North-East one (i.e. the disc centered at [START_REF] Jayadeva | Ants find the shortest path: a mathematical proof[END_REF][START_REF] Jayadeva | Ants find the shortest path: a mathematical proof[END_REF]) as a function of a. For this, we develop the following statistical approach.

For each a ∈ {5, [START_REF] Calenbuhr | A model for osmotropotactic orientation (II)[END_REF][START_REF] Detrain | The influence of the physical environment on the self-organised foraging patterns of ants[END_REF][START_REF] Edelstein-Keshet | Simple models for trail-following behaviour; Trunk trails versus individual foragers[END_REF][START_REF] Haefner | Spatial Model of Movement and Foraging in Harvester Ants (Pogonomyrmex) (I): The Roles of Memory and Communication[END_REF][START_REF] Jayadeva | Ants find the shortest path: a mathematical proof[END_REF][START_REF] Müller | Path integration in desert ants, Cataglyphis fortis[END_REF][START_REF] Panait | A Pheromone-Based Utility Model for Collaborative Foraging[END_REF][START_REF] Schweitzer | Active random walkers simulate trunk trail formation by ants[END_REF], 50}, we simulate our model 500 times. Since this is a rather large number of simulations, we need to reduce the computational cost of all simulations. Hence, for the purpose of drawing fig. 6 and for this purpose only, we fix P max b = 200 and P max g = 600 and we stop the simulation once the maximal number of blue pheromones is attained. We call this stopping time τ . We then count the number of blue pheromones whose orientation lies in 0, π 2 and consider them as pheromones pointing to the North-West quadrant. We also count the number of blue pheromones whose orientation lies in π 2 , π and consider them as pheromones pointing to the North-East quadrant:

P N E b (τ ) := {β m | 1 ≤ m ≤ P b (τ )} ∩ 0, π 2 , (3.15)
P N W b (τ ) := {β m | 1 ≤ m ≤ P b (τ )} ∩ π 2 , π . (3.16)
We estimate that the colony chose the food location in the North-West quadrant over the North-East one if and only if

P N W b (τ ) > P N E b (τ ).
We estimate the probability that the colony privileges the Nort-West quadrant food by counting how many times this event occurred among the 500 simulations. The results are shown in fig. 6. The simulations show that when a increases, the probability that the colony will choose the food located next to (-a, a) decreases linearly.

Dynamical food source

In these simulations, the food source's location varies. There are two steps. Between 0 and T f /2 = 500 seconds, the food source is located at one place and between T f /2 = 500 seconds and T f = 1000 seconds, it is located at a different place. We simulate this model in a situation where the two locations and the nest are nearly aligned (fig. 7), one where the two locations and the nest form a right-angle (fig. 8) and finally, one where the two locations and the nest form an acute angle (fig. 9). We systematically represent the pheromone trail every 100 seconds after the 500th one. What these simulations show is that, after a small transition, the ants are able to find the second food source, even though they were first misled. The pheromone trail keeps memory of the first part of the simulation, as we clearly see in fig. 9. Indeed, even though the geodesic to the second food location is a straight path, the ant colony follows an S-shaped trail because of the history of the simulation.

Dealing with an obstacle

In these simulations, we set T f = 1000 seconds and consider that the food source is a disc of center (0, 40) and of radius 2 centimeters. We assume that there is a an obstacle of constant width (O l =20, O r =22) but with various lengths. The fig. 10 shows that if the obstacle is short enough, the colony is able to find the food source and to bring food back to the nest. As in the first simulations, we compute the length of the shortest trail by collecting the times spent by the ants with food. What this study shows is that the colony is able to find a path that is close to the shortest path. Let us emphasize that the shortest path is very unlikely to be followed by an ant since it requires to have a nearly ballistic trajectory from the food to the obstacle and from the obstacle to the nest but to make two sharp turns: one when arriving at the obstacle, one when leaving it. For a = 25, the colony did not choose the shortest path and for a = 45, the colony brings food from the two locations, with a preference for the closest one. Green sticks: "green" pheromones. Blue sticks: "blue" pheromones. Red circle: food source. Black circle: nest. Figure 6: Estimated probability that the colony chooses the food location located at a disc of radius 2cm and center (-a, a) over one located at a disc of radius 2cm and center [START_REF] Jayadeva | Ants find the shortest path: a mathematical proof[END_REF][START_REF] Jayadeva | Ants find the shortest path: a mathematical proof[END_REF] as a function of a. Red line: linear regression (y = -0.0181(x -3) + 0.9874).

We emphasize that, when the obstacle is too long, the colony may not find the food source. Our choice of boundary conditions is to blame. Indeed, suppose that ants do not die when reaching the edge of the box, but that they choose a new direction, we presume that the colony will most probably locate the food source.

Dynamical obstacle

In this simulation, the food source is a disc of radius 2cm centered at point [START_REF] Panait | A Pheromone-Based Utility Model for Collaborative Foraging[END_REF]0). For the 500 first seconds, this is the only setting of the simulation. Then, we place an insuperable obstacle as a rectangle [START_REF] Edelstein-Keshet | Simple models for trail-following behaviour; Trunk trails versus individual foragers[END_REF][START_REF] Garnier | Path selection and foraging efficiency in Argentine ant transport networks[END_REF] × [-20, 20] between the food source and the nest for the last 1500 seconds of the simulation. Thus, the shortest path from the food source to the nest turns from 37cm to approximatively 56.19cm. It is worth mentioning that the length of the obstacle is such that in the previous simulations where the obstacle was here all the time, the ant colony rarely found the food source. The simulation shown in the bottom-right corner of fig. 10 is one example but this outcome was very frequent in our (not shown here) simulations. In the present simulation, the situation is very different since we leave the ants enough time to find the initial geodesic straight path from the food source to the nest before making the geodesic path more complex. Our simulation shows that there is a time of adaptation, where many ants collide into the obstacle (see the concentration of pheromones onto the obstacle in the upper-right corner of fig. 11), the colony is able to find a path from the food source to the nest, that is quite optimal (60.2 cm). This is a rather interesting outcome since the ants would not have been able to find the food source had it been hidden from the beginning.

Discussion

Our model is rather simple but it has proven itself very effective to localize a food source and to bring it back to the nest in a quite optimal way. When no obstacle is involved, the colony tends to concentrate on a "highway" located on the straight line linking the food source to the nest. When two food locations are involved the colony tends to favor the closest one. Sometimes, the colony does not choose the closest food location (fig. 5, a = 25) but the probability to choose the "wrong" food location decays almost linearly as its distance to the nest increases (cf fig. 6). Hence, the colony makes "big mistakes" (choosing a food location far away when one is much closer) with a rather small probability. Even when the location of the food changes, the colony is able to find the new location quite rapidly. In this scenario, the pattern keeps a memory of the history of the experiment and the colony can follow non-straight paths (cf fig. 9). The colony is also able to find an optimal trail when an obstacle is involved. Let us now discuss the biological relevancy of our model.

Regarding the modeling of directed pheromones of Boissard, Degond and Motsch, a discussion about the biological relevancy was already conducted in [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF]. We summarize it here but we would suggest to read it in details (see [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF], Section 3.6) since it contains many arguments supporting the hypothesis of directed pheromones. A mechanism called "osmotropotaxis" described in [START_REF] Calenbuhr | A model for osmotropotactic orientation (II)[END_REF][START_REF] Calenbuhr | A model for osmotropotactic orientation (I)[END_REF][START_REF] I D Couzin | Self-organized lane formation and optimized traffic flow in army ants[END_REF] could explain how ants can sense the orientation of a pheromone drop. There are two possible hypothesis to explain the sensitivity of ants to the direction of a pheromones drop: either ants leave long continuous pheromone drops or they leave several small drops one after an other. In the case of continuous pheromones drop modeled in [START_REF] William | The analysis of olfactory communication among animals[END_REF], the pheromone drop has an oval shape with higher chemical concentration in the middle. In this scenario, the ants are able to sense the orientation of the crest line of higher concentration. In the case of discontinuous drops modeled by [START_REF] Haefner | Spatial Model of Movement and Foraging in Harvester Ants (Pogonomyrmex) (I): The Roles of Memory and Communication[END_REF], a diffusion process must be taken into account to homogenize the pheromone drop. A quantitative study of this homogenization process with realistic parameter values was conducted in the appendix of [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF].

A second issue regarding the pheromone modeling is our choice of polar interactions. More precisely, our modeled pheromones keep information of the orientation and the direction of the "parent" ant. Non-polar interactions seem more biologically accurate since no evidence of polar oriented pheromone exist to our knowledge. Here is how we could model these interactions: when an ant walks with orientation θ and encounters a pheromone of orientation θ , the ant can either pick the orientation θ or θ +π but chooses the closest angle to its current orientation. This way, the trajectory of the ant does not make acute angles. We emphasize that such a choice might interfere in the process of selection of the shortest path since much information is lost compared to the polar interaction scenario.

Our choice of parameters was made to match the ones from [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF] when a connection could be made. We refer to this reference and to the references therein for a motivation of this choice of parameter values for Lasius niger.

Our model considers two types of pheromones. There is evidence showing that some ants, such as the Pharaoh's ant [START_REF] Beekman | Phase transition between disordered and ordered foraging in Pharaoh's ants[END_REF][START_REF] Fourcassié | The dynamics of collective exploration and trail-formation in Monomorium pharaonis: experiments and model[END_REF][START_REF] Jackson | Modulation of pheromone trail strength with food quality in Pharaoh's ant, Monomorium pharaonis[END_REF][START_REF] Jackson | Spatial and temporal variation in pheromone composition of ant foraging trails[END_REF][START_REF] Jeanson | Pheromone trail decay rates on different substrates in the Pharaoh's ant, Monomorium pharaonis[END_REF][START_REF] David | From nonlinearity to optimality: pheromone trail foraging by ants[END_REF], the Argentine ant Iridomyrmex humilis [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF][START_REF] Garnier | Path selection and foraging efficiency in Argentine ant transport networks[END_REF][START_REF] Vittori | Path efficiency of ant foraging trails in an artificial network[END_REF], and the fire ant [START_REF] Vander Meer | Hydrocarbon components of the trail pheromone of the red imported fire ant, Solenopsis Invicta[END_REF][START_REF] Robert | The orientation inducer pheromone of the fire ant Solenopsis invicta[END_REF] can lay different type of chemicals using different glandes to produce them. However, it is in [START_REF] Dussutour | The role of multiple pheromones in food recruitment by ants[END_REF] that was first shown that the use of two pheromones enabled foraging Pheidole megacephala to locate the food source. Although they have not chemically identified the two types of pheromones, Dussutour, Nicolis, Shepard, Beekman and Sumpter exhibited through three experiments strong evidence that foraging ants and ants returning to the nest with food lay different kinds of pheromones. It is worth mentioning that they also found strong evidence that pheromones left by foraging ants lasted much longer than the ones left by ants with food but that they were much lesser attractive. Dussutour and her co-authors suggested that this behavior allows the colony to adapt quickly to a change of the food location. We would like to emphasize that our choice of parameters values is not consistent with these observations but that it only takes a change of those values to adapt our model. Indeed, we considered both pheromones to have the same mean life-time and foraging ants and ants with food to have the same trail recruitment jump frequency. Furthermore, since our model is adapted from the Boissard-Degond-Motsch model, our choice of parameter values is adapted to the black garden ant Lasius niger, even though the two pheromones strategy was observed on a different species. These are notable critics that can be made to our choice of parameter values.

Throughout this paper, we constantly assumed that the ants did not know their way back to the nest and we made very clear that this assumption differentiates our work from previous related works, such as [START_REF] Alonso | Analysis of a chemotaxis system modeling ant foraging[END_REF][START_REF] Amorim | A continuous model of ant foraging with pheromones and trail formation[END_REF][START_REF] Amorim | Modeling ant foraging: A chemotaxis approach with pheromones and trail formation[END_REF][START_REF] Ryan | A model for collective dynamics in ant raids[END_REF]. In [START_REF] Amorim | Modeling ant foraging: A chemotaxis approach with pheromones and trail formation[END_REF], Amorim suggests that there are biological evidence that some ants are able to come back to the nest without help from others: the desert ants Cataglyphis fortis and the harvester ants, for example, can use individual orientation using visual or odorous clues [START_REF] Hölldobler | Recruitment behavior, home range orientation and territoriality in harvester ants, Pogonomyrmex[END_REF][START_REF] Steck | Smells like home: Desert ants, Cataglyphis fortis, use olfactory landmarks to pinpoint the nest[END_REF]. Other studies [START_REF] Müller | Path integration in desert ants, Cataglyphis fortis[END_REF][START_REF] Müller | Path Integration Provides a Scaffold for Landmark Learning in Desert Ants[END_REF][START_REF] Wehner | Desert ant navigation: how miniature brains solve complex tasks[END_REF] quoted by Amorim suggest that desert ants are able to know the shortest way to the nest by path integration. In this scenario, ants keep track of all their direction changes in order to know the compass direction to the nest. Let us remark that such navigation can be problematic when there are obstacles between the nest and the food source. We emphasize that neither [START_REF] Ryan | A model for collective dynamics in ant raids[END_REF] nor [START_REF] Amorim | Modeling ant foraging: A chemotaxis approach with pheromones and trail formation[END_REF] raised this issue (Ryan, however, did mention this issue as a perspective for future work). The hypothesis that some species of ants find the shortest path by individual rather than collective strategy is hence supported by biological evidence. The experimental results of [START_REF] Dussutour | The role of multiple pheromones in food recruitment by ants[END_REF] however showed that some other species still needed the combination of two pheromones to make their way back to the nest. In particular, their experiments ex situ indicates that the species they studied (Pheidole megacephala) can find their way to their nest in a sterile non-odorous environment.

One assumption of our model, which is physically irrelevant, is the absence of collisions between ants. As was previously observed in experiments and models [START_REF] I D Couzin | Self-organized lane formation and optimized traffic flow in army ants[END_REF][START_REF] Dussutour | Optimal traffic organization in ants under crowded conditions[END_REF][START_REF] Ryan | A model for collective dynamics in ant raids[END_REF], this issue is crucial since a large number of ants can be at the same time on a narrow track. Reduction of traffic congestion is very important to optimize the food transport by ants. Physical interactions between ants can be modeled using a Lennard-Jones repulsive operator in the same spirit as Ryan's work [START_REF] Ryan | A model for collective dynamics in ant raids[END_REF]. We could also consider communication between ants when a collision occurs. As was observed in many biological experiments (see [START_REF] Gordon | What is the function of encounter patterns in ant colonies?[END_REF] among many others), antennas contacts between individuals is a key element to understand how complex tasks are achieved by ants societies. Taking these into account is likely to improve the capacity of the model to optimize food transport since exchange of informations is the key to the ants' complex social structures. On the other hand, taking physical interactions, like Ryan did, does not slow the foraging process as was observed in [START_REF] Ryan | A model for collective dynamics in ant raids[END_REF] but we expect that it will raise the computational cost of the simulation since interactions between a large number of ants would have to be taken into account.

Finally, let us discuss the strategy we adopted when an obstacle was involved. We considered a very simple strategy that was very easy to implement (see fig. 1). This strategy is not efficient with more complex obstacles. In particular, it is not difficult to convince ourselves that many ants will can be trapped in the acute angle of an L-shaped obstacle if they only follow the rule we presented. From our reading of the biology literature, it does not seems that a lot of focus was made on this particular matter. It seems very obvious however that a much more complex behavior then the one we depicted is adopted by real ants otherwise they would not be able to find food in complex mazes [START_REF] Reid | Optimisation in a natural system: Argentine ants solve the Towers of Hanoi[END_REF].

Conclusion

We have presented a model of foraging and pheromones deposing ants with two types of pheromones. The model has two strengths:

1. It is rather simple. Indeed, the local interactions between ants and pheromones is very simply described and the pheromones' lifetime process as well.

2. It allows the modeled colony to find the food source and to bring it back to the nest in a quite optimal way.

We then showed the outcome of simulations of the model in various situations, namely: simulations with one or two food locations, simulations with one food source which location that changes during the experiment and simulations with an obstacle between the food source and the nest. We showed that even in these situations, the ants were capable of finding a way to bring the food back to the nest, using an optimal path. The actual geodesic path is never followed by ants since, in those cases, it requires the ant to have a nearly ballistic trajectory. Throughout our discussion of the model, we underlined that the model can be improved from the biological perspective by letting ants communicate with each other and by considering a model with physical interactions between ants. We can also take more realistic parameter values that are consistent with a single species. Considering that the big headed ant's specimens lay two types of pheromones depending if they are carrying food or if they are looking for food, this species is our suggestion.

In a future work, it would also be interesting to allow our ants to have more complex behaviors when facing complex obstacles. We would like to investigate the capacity of our model to find a shortest path in a maze. Such attempts have failed with our simple model but we believe that it only requires a little more complexity to be able to see the colony find geodesic paths in a maze, as is observed with actual colonies of ants. Moreover, we would like to explore the behavior of our model in curved spaces. Indeed, unlike previous models on a fixed lattice, we believe that our model can simply be adapted on non-Cartesian spaces. We would like to explore the capacity of our model to select the shortest path on such spaces.

There are other perspectives for future work. A possible sequence of this work is to derive the kinetic equations that describe the dynamics of the system at the mesoscale. Such a (formal) derivation was conducted in Boissard Degond and Motsch's article [START_REF] Boissard | Trail formation based on directed pheromone deposition[END_REF] as well as a hydrodynamic limit of the equation. The purpose of such a derivation is to get a kinetic partial differential equation whose numerical resolution is faster than the simulation of our model. In a recent work [START_REF] Amorim | A continuous model of ant foraging with pheromones and trail formation[END_REF], Amorim established a description of a chemotactic model of foraging ants at the macroscopic scale. He further analyzed the corresponding system of diffusive equations along with Alonso and Goudon in [START_REF] Alonso | Analysis of a chemotaxis system modeling ant foraging[END_REF]. Amorim's numerical resolution shows the emergence of a trail from the food source to the nest [START_REF] Amorim | Modeling ant foraging: A chemotaxis approach with pheromones and trail formation[END_REF]. We emphasize that, in Amorim's description, the ants know the shortest way to get back to the nest. As a perspective for future work, we could do the same kind of analysis: we could derive (formally or rigorously) the kinetic Kolmogorov equation of our model and solve it numerically. This can be challenging since there will be 4 structure variables: the time variable, the two space variables and the orientation variable θ. From the reading of the present paper, we expect that this numerical simulation gives an algorithm that approaches the geodesic between the food source and the nest by spotting the high concentrations of pheromones.

In conclusion, the purpose of this work is to open perspectives in two different fields. From the biology perspective, we presented a model in which a colony of ants finds optimal paths to bring food back to the nest without assuming any pre-existing lattice, which seems more naturally accurate than the previous models. We hope that this work will get attention from the biology community and that it will help understanding the behavior of some insects. From the mathematics perspective, we hope to have set the first stone of a kinetic partial differential equation method to find geodesics on a plane or on more complex two-dimensional spaces.

Figure 2 :Figure 3 :

 23 Figure 2: One simulation of the model where the food source is a disc of radius 2cm centered at (0, 40). Top left: Outcome of the simulation after 30s. Top right: Outcome of the simulation after 56.20s (discovery of the food source by one ant). Middle-left: Outcome of the simulation after 78.4s (when the first ant with food found its way back to the nest). Middle-right: Outcome of the simulation after 100s. Bottom-left: Outcome of the simulation after 200s. Bottom-right: Outcome of the simulation after 200s (only the pheromones' locations are shown and blue pheromones are shown in priority over the green ones). Black circle at the origin: Nest. Red circle: Food source.Black squares: foraging ants. Red squares: ants with food. Green sticks: "green pheromones" (left by foraging ants). Blue sticks: "blue pheromones" (left by ants with food).

Figure 4 :

 4 Figure4: Evidence of a phase transition. Top-left: dark green line: mean orientation of the green pheromones, green zone: standard deviation around the mean-value, red line: orientation of the geodesic going from the food source to the nest, magenta line: Mean value of the uniform distribution on [0, 2π).Top-right: dark blue line: mean orientation of the blue pheromones, light-blue zone: standard deviation around the mean-value, red line: orientation of the geodesic going from the nest to the food source. Bottom-left: black line: number of foraging ants. Red line: number of ants with food. Bottom-right: deep blue line: mean paths length, dark blue line: minimal path length, red line: geodesic length.

Figure 5 :

 5 Figure5: Ten simulations of the model with disconnected food source. The food source is simultaneously located at the reunion of the disc of radius 2cm centered at[START_REF] Jayadeva | Ants find the shortest path: a mathematical proof[END_REF][START_REF] Jayadeva | Ants find the shortest path: a mathematical proof[END_REF] and the disc with same radius centered at (-a, a) for a = 5, 10,15, 20, 25, 30, 35, 40, 45, 50. In all above simulations but the ones obtained with a = 25 and a = 45, the colony clearly favored the shortest path to the food source. For a = 25, the colony did not choose the shortest path and for a = 45, the colony brings food from the two locations, with a preference for the closest one. Green sticks: "green" pheromones. Blue sticks: "blue" pheromones. Red circle: food source. Black circle: nest.

Figure 7 :Figure 8 :Figure 9 :Figure 10 :

 78910 Figure 7: One simulation of the model with a dynamical food source. The food source is a disc of radius 2cm centered first at (20, 10) and then at (40, 40) after 500s. Blue sticks: "blue" pheromones. Green sticks: "green" pheromones. Red circle: Food source. Black circle: nest.

Figure 11 :

 11 Figure 11: One simulation of the model with a dynamical obstacle. Between t = 0s and t = 500s, there is no obstacle (upper-left corner). After t = 500s, we put an obstacle and represent the outcome of the simulation at t = 600, 700, 1000, 1500 and 2000s. The food source is a disc of radius 2cm centered at (40, 0). Between 500s and 2000s, the obstacle is the rectangle[START_REF] Edelstein-Keshet | Simple models for trail-following behaviour; Trunk trails versus individual foragers[END_REF][START_REF] Garnier | Path selection and foraging efficiency in Argentine ant transport networks[END_REF] ×[-20, 20]. Blue sticks: "blue" pheromones. Green sticks: "green" pheromones. Red circle: Food source. Black circle: nest. Brown rectangle: obstacle.

max g Table 1 :

 g1 Model parameters and their values

	Parameter		Interpretation	Value
	c		Instantaneous speed of ants	2cm/s
	λ f		Random jump frequency of foraging ants	2s -1
	λ w		Random jump frequency of ants with food	10s -1
	σ		Standard deviation of orientation changes	0.1
	λ b	Trail recruitment jump frequency of foraging ants	2s -1
	λ g	Trail recruitment jump frequency of ants with food 2s -1
	ν g		Green pheromones deposition rate	0.2s -1
	ν b		Blue pheromones deposition rate	0.6s -1
	T p		Pheromones mean lifetime	100s
	R		Detection radius	1cm
	R nest		Radius of the nest	1cm
	Ω		Food source
	O l , O r , O d , O u		Dimensions of the obstacle
	Table 2: Simulations parameters and their values
	Parameter	Interpretation	Value
	T f		Duration of the simulation
	∆t		Time increments	0.1s
	l		Dimension of the box	100cm
	N		Maximal number of ants	200
	P max b P max g		Maximal number of blue pheromones	1000

Acknowledgment

The idea of this paper was born after a friendly conversation with Pierre Degond and thanks to Sébastien Motsch's patient answers to the author's emails. The author would like to thank them both for discussing about their model with him.

Research of the author was partially supported by the National Science Foundation grant 1615126 to Judith R. Miller.