Bouger et Calculer: Agents, Robots et Réseaux – MACARON

On assiste actuellement à l'émergence d'une nouvelle tendance dans le domaine de la robotique. A la place de quelques robots massifs, on utilise des robots minuscules, chacun ayant des capacités extrêmement limitées. Une tendance similaire concerne le déploiement de réseaux de capteurs, capteurs eux aussi limités mais nombreux. Ces systèmes émergents ont la particularité d'avoir des briques élémentaires simples et bon marché mais dont les comportements collectifs sont relativement complexes.

D'un point de vue algorithmique, ces évolutions nécessitent de considérer un nouveau champs de recherche dont le paradigme est «Bouger et Calculer»: l'étude et la conception de systèmes dont les entités de calcul sont elles-même capables de se déplacer au sein de l'espace où elles résident. Ce domaine possède des applications dans des domaines aussi divers que les robots autonomes se déplaçant sur un terrain, les agents logiciels se déplaçant dans un réseau, les véhicules autonomes intelligents, les réseaux ad hoc sans-fil mobiles et les réseaux de capteurs mobiles; les comportements recherchés étant l'exploration, la coordination ou la coopération.

Lorsque l'on s'intéresse à la conception d'un algorithme pour des robots mobiles évoluant dans un environnement donné, la modélisation de cet environnement, c'est-à-dire la manière dont les entités mobiles accèdent aux informations relatives à cet environnement est primordiale. Ces entités peuvent ainsi n'avoir accès qu'aux informations concernant les mouvements possibles. En effet, dans ce contexte, la principale responsabilité du robot est de déterminer son prochain déplacement. Une telle modélisation amène à considérer le graphe des localisations possibles, reliées par les déplacements élémentaires. Un tel graphe n'a pas une structure arbitraire mais possède des propriétés combinatoires héritant du contexte géométrique dont il provient.

Dans ce cadre, l'utilisation du modèle des agents mobiles, issu de l'algorithme distribuée classique, est tout-à-fait pertinente. Les graphes de déplacements spécifiques à notre étude sont de type géométriques. En outre, il est bien connu qu'ajouter des capteurs supplémentaires permet d'obtenir de meilleurs algorithmes. Une question naturelle est donc de déterminer quels sont les types de capteurs minimaux permettant de résoudre le plus efficacement des tâches telles que exploration, cartographie et rendez-vous.

Contrairement à la situation précédente, dans le cas de capteurs mobiles, l'objectif du calcul est davantage de réagir à des mouvements non contrôlés. L'utilisation des propriétés géométriques permet là aussi d'améliorer les performances des algorithmes. Cela nécessite une bonne compréhension des relations de voisinage engendrées par la topologie actuelle du réseau et plus particulièrement de ses évolutions possibles. Le modèle «agent mobile» est là aussi pertinent, car celui-ci propose une structure de calcul simple évoluant dans une structure de données complexe.

Il s'agit d'améliorer fondamentalement les modèles et algorithmes pour l'algorithmique distribuée robotique. Une telle étude implique de mieux comprendre les relations entre les propriétés globales, locales et géométriques partagées par ces problèmes et environnements. Cela nécessite également d'utiliser des résultats et des outils provenant de domaines tels que la théorie des graphes géométriques, la topologie algébrique discrète, la géométrie algorithmique ainsi que les systèmes temporisés. Il est important de noter qu'une partie de la validation des résultats proposés se fera sur et au bénéfice de «LED's CHAT» (http://leds-chat.net/): un système modulaire de lumières et de capteurs développé au LIF, et actuellement en cours de transfert technologique dans le but de commercialiser la technologie pour des applications lumineuses réelles.