Détail du poste
Établissement : Université Paris-Saclay GS Informatique et sciences du numérique École doctorale : Sciences et Technologies de l'Information et de la Communication Laboratoire de recherche : Laboratoire Interdisciplinaire des Sciences du Numérique Direction de la thèse : Janna BURMAN Début de la thèse : 2026-10-01 Date limite de candidature : 2026-05-12T23:59:59 Les agents mobiles constituent un cadre pour l'étude des systèmes distribués dans lesquels des entités autonomes (agents) se déplacent, interagissent et accomplissent des tâches dans des environnements dynamiques ou inconnus. Introduits à l'origine dans les années 1990, les agents mobiles ont été appliqués à des tâches réseau telles que la tolérance aux défaillances, la gestion de réseau, la collecte de données, et servent également de modèles pour des phénomènes comme le code mobile ou les logiciels malveillants.
Un axe central de la thèse est la communication entre agents sous contraintes. Les modèles traditionnels permettent des méthodes de communication relativement puissantes, telles que l'interaction directe, les jetons ou la mémoire partagée (tableaux blancs). En revanche, cette thèse étudie un mécanisme beaucoup plus faible : les phéromones évaporantes. Dans ce modèle, les agents laissent des traces indiscernables sur les noeuds, perceptibles localement et influençant leur comportement, mais ces traces disparaissent après un temps fixé, sauf si elles sont renouvelées. Cela crée une forme de communication très limitée et indirecte, inspirée des traces de phéromones naturelles, mais utilisée ici comme modèle computationnel abstrait.
La thèse vise à explorer comment une communication aussi faible affecte la capacité des agents à se coordonner et à résoudre des problèmes distribués. Parmi les directions de recherche envisagées figurent : premièrement, l'étude de nouveaux problèmes au-delà de la chasse au trésor (Treasure Hunt), déjà abordée dans des travaux antérieurs, notamment la patrouille, la dispersion et le maintien de chemins, ainsi que la réévaluation de problèmes classiques comme le rendez-vous ou la formation de motifs. Deuxièmement, l'analyse de la tolérance aux défaillances, en prenant en compte diverses perturbations telles qu'une évaporation plus rapide des phéromones, des erreurs de perception ou des changements environnementaux comme l'apparition d'obstacles. Troisièmement, des extensions du modèle seront examinées, telles que l'utilisation de plusieurs types de phéromones, de signaux inhibiteurs ou d'une mémoire accrue des agents. Enfin, d'autres modèles de communication encore plus faibles seront étudiés, comme les messages éphémères ou des signaux minimaux (par exemple, des bips).
L'originalité de la thèse réside dans le fait de considérer les phéromones évaporantes comme un mécanisme principal de communication. Les recherches existantes se sont principalement concentrées sur des modèles plus puissants, comme les jetons permanents ou la communication directe, avec une seule étude antérieure examinant les phéromones évaporantes d'un point de vue algorithmique, dans le contexte du problème de la chasse au trésor. Contrairement aux modèles précédents, les phéromones évaporantes introduisent des défis fondamentalement nouveaux en raison de leur nature temporaire. Cela nécessite de nouvelles techniques algorithmiques, telles que la différenciation des rôles entre agents.
Au-delà de l'intérêt théorique, ce modèle est également motivé par des considérations pratiques. Étant donné que les traces de phéromones disparaissent par définition, aucune information persistante ne subsiste après l'exécution, ce qui évite les interférences entre exécutions répétées et élimine la nécessité explicite de nettoyage ou réinitialisation de protocoles. Cette approche est particulièrement pertinente pour des systèmes à mémoire limitée, soumis à des contraintes énergétiques ou disposant de moyens de stockage peu fiables.
The novelty of this thesis is the study of evaporating pheromone as a weak agent communication mechanism, directly inspired from nature.
The state of the art, with respect to this particular evaporating pheromone model, involves a single recent paper [3], which investigates the implications of such weak agent communication capabilities to the Treasure Hunt problem. In the Treasure Hunt problem, a team of mobile agents need to locate a single treasure that is hidden in their environment. The problem is considered in the discrete setting of an oriented infinite rectangular grid, where agents are modeled as synchronous identical deterministic time-limited finite-state automata, originating at a rate of one agent per round from the origin. Agents perish rounds after their creation, where 1 is a parameter of the model. An algorithm is said to solve the Treasure Hunt problem if every grid position at distance or less from the origin is visited by at least one agent. Pheromone traces evaporate over µ rounds from the moment they were placed on a node, where µ 1 is another parameter of the model. It is shown that, if pheromone persists for at least two rounds (µ 2), then there exists a fairly simple Treasure Hunt algorithm for all values of agent lifetime. A more sophisticated algorithm works for all values of µ, hence also for the fastest possible evaporation rate of µ = 1, but only if agent lifetime is at least 16.
In previous work, the ANTS (Ants Nearby Treasure Search) problem was introduced in [12, 13, 14] as a natural abstraction of foraging behavior of ants around their nest. They explore the tradeoff between searcher memory and the speedup obtained by using multiple probabilistic searchers vs using a single searcher. Searchers may not communicate once they leave the nest. Follow-up work [4, 5, 10, 11, 16, 17] modeled searchers as finite state machines that can communicate outside the nest, when they are sufficiently close to each other, by exchanging messages of constant size. Under these assumptions, it is shown in [11] that the optimal search time can still be achieved by probabilistic finite state machines, matching the lower bound of [13]. The minimum number of searchers that can solve the ANTS problem, when they are controlled by randomized/deterministic finite/push-down automata, is investigated in [4, 5, 10]. A probabilistic fault-tolerant constant-memory algorithm is presented in [17], for the synchronous case. An algorithm that tolerates obstacles is presented in [16].
A different communication mechanism is considered in [1, 2, 18], where it is assumed that agents may communicate by leaving permanent markers (tokens) on nodes, which can be sensed later by other agents. Note that, although these papers use the word pheromone to describe the traces that agents leave on nodes, these are assumed permanent and do not evaporate. The usual term in the mobile agent literature to describe this type of marker is token or pebble [8]. Tokens that may disappear instantly from the system have actually been considered before in the literature, but only in the context of faults [6, 7, 9, 15].
Evaporating pheromone has never been considered before as a communication mechanism, from an algorithmic point of view, except in [3]. We aim to study the impact of this weak communication model on agent coordination. The introduction of evaporation significantly distinguishes this model from pre-existing models, and requires new techniques. We cite, as an example, the agent role differentiation that was used as a key idea in one of the Treasure Hunt algorithms of [3]. The evaporating pheromone model, although directly inspired by the behavior of actual pheromone trails in nature, does not aim to capture or model natural ant foraging behavior patterns. On the contrary, the outcomes of this study will be more appropriate for artificial agent systems under energy limitations (agent lifetime).
Finally, the use of an evaporating communication mechanism, such as pheromones, can also be understood as a way to design distributed algorithms that do not leave persistent traces in the environment once the computation terminates. In contrast to classical models based on tokens or whiteboards, where information may remain or accumulate indefinitely, evaporating markers ensure that any information written by the agents is temporary by construction. This introduces a form of implicit cleanup, which may be particularly relevant in settings where agents repeatedly execute tasks in the same environment, as it avoids interference between successive executions and eliminates the need for explicit reinitialization of protocols, or in settings with limited memory or unreliable storage, where maintaining long-term state is costly or impossible.
The mobile agent paradigm has been proposed since the 90s as a concept that facilitates various fundamental networking tasks in the network layer or in the application layer, such as fault tolerance, network management, and data acquisition. Mobile agents serve as a natural model for the fundamental computing entities of systems with inherent mobility (mobile code, malware propagation, web crawlers, etc.) and, as such, they have found application as a software design paradigm for various networked systems. The agents may interact with their environment or with each other in order to accomplish the required task. Crucially, the network is potentially dynamic or of unknown topology to the agents at the beginning of the execution of a mobile agent protocol. The distributed algorithms community has taken a strong interest in mobile agents, ever since their introduction.
A second perspective on the mobile agent paradigm is as a model for computational entities that operate and move in continuous spaces, with typical applications emerging in the fields of artificial intelligence, robotics, and control. This is in contrast to the software agent view, where the agents operate in a discrete space, typically a graph representing the underlying network. The tasks that are considered in this case may be similar to those in the context of software agents (rendezvous, exploration, etc.) or fundamentally different (pattern formation, flocking, evacuation, collision avoidance, etc.). This perspective has also been picked up by the distributed algorithms community. Although the two settings are technically different, they share some similarities on a higher level, as regards the nature of the emerging questions and problems.
With regard to agent communication, several standard communication models have emerged in the literature of mobile agent algorithms, including face-to-face communication, wireless communication, tokens, enhanced tokens, or whiteboards [8]. In this thesis, we aim to explore how agents can coordinate, explore, and solve fundamental algorithmic problems when communication is indirect and limited, as captured by the model of evaporating pheromones. In this model, agents communicate by leaving indistinguishable traces (pheromone) on nodes, which can be sensed by agents in neighboring nodes and modify their behavior. These pheromones gradually evaporate and eventually disappear from the system in a fixed amount of time, which is a parameter of the model, unless refreshed by a new pheromone drop on the same node. This is in contrast to and significantly weaker than the standard token model, where tokens are permanent markers that may be dropped by the agents on a node. The evaporating pheromone model, directly inspired by the behavior of actual pheromone trails in nature, was introduced in a recent paper [3], which studied the Treasure Hunt problem in a synchronous, deterministic, and error-free setting.
We aim to pursue the following research directions in the thesis:
1) Definition and study of new problems: Other than Treasure Hunt, we will study different problems, such as patrolling an area, agent dispersion, or the construction and maintenance of a pheromone path between the nest and a food source. In addition, we will explore the limitations of the model when dealing with standard problems from the mobile agent literature, such as rendez-vous, black hole search, or pattern formation.
2) Fault tolerance: We will introduce and study different types of adversarial or random faults involving pheromone. For example: evaporation faults (pheromone evaporates faster than expected), pheromone addition faults (pheromone is added or refreshed), scenting errors (agents misread the pheromone marks around them), or stochastic pheromone evaporation. Additionally, we will study mechanisms for dealing with static or dynamic obstacles that may appear, modifying the underlying graph or even crushing a number of agents.
3) Model enhancements: We will study the impact of allowing for various enhancements to the basic model, such as access to multiple types of pheromone, the possibility to use inhibitory pheromone, or agents having more than constant memory at their disposal.
4) Other weak communication models: As a more general direction, we would like to explore strictly weaker communication mechanisms than the ones typically found in the literature. Such limited communication models may come in different flavors, for example: Ephemeral whiteboards (a message left by an agent disappears when the agent moves beyond a certain distance from the message), or beeping (agents are only capable of communicating by simple signals called beeps).
The approach to these problems will be formal, as we will focus on proving worst case guarantees on the performance of the proposed algorithms, as well as corresponding hardness or impossibility results.
Le profil recherché
Publiée le 27/04/2026 - Réf : d5d4b720224c596c78802f60af20d1ee
