Cette thèse s’articule autour de deux séries de travaux motivés par des expériences sur des fourmis. Bien qu’inspirés par labiologie, les modèles que nous développons utilisent une terminologie et une approche typique de l’informatique théorique.Le premier modèle s’inspire du transport collaboratif de nourriture au sein de l’espèce P. Longicornis. Certains aspectsfondamentaux du processus peuvent être décrits par un problème de recherche sur un graphe en présence d’un certain typed’indications bruitées à chaque noeud. Ces indications représentent de courtes traces de phéromones déposées devant l’objettransporté afin de faciliter la navigation. Dans cette thèse, nous donnons une analyse complète du problème lorsque le graphesous-jacent est un arbre, une hypothèse pertinente dans un cadre informatique. En particulier, notre modèle peut être vucomme une généralisation de la recherche binaire aux arbres, en présence de bruit. De manière surprenante, lescomportements des algorithmes optimaux dans ce cadre diffèrent suivant le type de garantie que l’on étudie : convergence enmoyenne ou avec grande probabilité.Le deuxième modèle présenté dans cette thèse a été conçu pour décrire la dissémination d’informations au sein de fourmis dudésert. Dans notre modèle, les échanges ont lieu uniformément au hasard, et sont sujets à du bruit. Nous prouvons une borneinférieure sur le nombre d’interactions requis en fonction de la taille du groupe. La borne, de même que les hypothèses dumodèle, semblent compatible avec les données expérimentales.Une conséquence théorique de ce résultat est une séparation dans ce cadre des variantes PUSH et PULL pour le problème du broadcast avec bruit. Nous étudions aussi une version du problème avec des garanties de convergence plus fortes. Dans cecas, le problème peut-être résolu efficacement, même si les échanges d’information au cours de chaque interaction sont très limités / This thesis is built around two series of works, each motivated by experiments on ants. We derive and analyse new models,that use computer science concepts and methodology, despite their biological roots and motivation.The first model studied in this thesis takes its inspiration in collaborative transport of food in the P. Longicornis species. Wefind that some key aspects of the process are well described by a graph search problem with noisy advice. The advicecorresponds to characteristic short scent marks laid in front of the load in order to facilitate its navigation. In this thesis, weprovide detailed analysis of the model on trees, which are relevant graph structures from a computer science standpoint. Inparticular our model may be viewed as a noisy extension of binary search to trees. Tight results in expectation and highprobability are derived with matching upper and lower bounds. Interestingly, there is a sharp phase transition phenomenon forthe expected runtime, but not when the algorithms are only required to succeed with high probability.The second model we work with was initially designed to capture information broadcast amongst desert ants. The model usesa stochastic meeting pattern and noise in the interactions, in a way that matches experimental data. Within this theoreticalmodel, we present in this document a strong lower bound on the number of interactions required before information can bespread reliably. Experimentally, we see that the time required for the recruitment process of even few ants increases sharplywith the group size, in accordance with our result. A theoretical consequence of the lower bound is a separation between theuniform noisy PUSH and PULL models of interaction. We also study a close variant of broadcast, without noise this time butunder more strict convergence requirements and show that in this case, the problem can be solved efficiently, even with verylimited exchange of information on each interaction.
| Identifer | oai:union.ndltd.org:theses.fr/2018USPCC044 |
| Date | 30 November 2018 |
| Creators | Boczkowski, Lucas |
| Contributors | Sorbonne Paris Cité, Korman, Amos, Kerenidis, Iordanis |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation, Text, Collection, Image |
Page generated in 0.0026 seconds