Modèles et algorithmes pour les systèmes émergents
Institution:
Paris 6Disciplines:
Directors:
Abstract EN:
Les réseaux de robots autonomes sont des entités mobiles qucommuniquent uniquement ˆ travers leurs mouvements et l'observation deleurs positions respectives. Ils sont anonymes, sans mémoire et sanssystème de coordonnées global, ni une notion commune de ladistance. Nous nous concentrons sur l'étude algorithmique des problèmes derassemblement et de convergence des robots quand ils sont sujets ˆ despannes. Notre première contribution est de nature géométrique. Nousfournissons un protocole pour calculer le point Weber d'une grandeclasse de configurations qui ont une symétrie rotationnelle. Se basant sur cette primitive, nous présentons un algorithme quirésout le problème du rassemblement en présence de n'importe quelnombre de pannes franches. Ensuite, nous abordons le problème de convergence quand les robotspeuvent subir des pannes byzantines qui sont plus difficiles àmanipuler que les pannes franches. Nous fournissons plusieurs bornesoptimales qui relient le degré de synchronie du système àsa résilience. Enfin, nous Étudions les robots qui sont dotées de mémoire et nousmontrons que ce modèle est plus fort que le modèle de passage demessages.
Abstract FR:
Networks of autonomous robots are mobile entities that communicate only through their movements and the observation of their respective positions. They are anonymous, without memory and without a global coordinate system nor a common notion of distance. We focus on the algorithmic study of the problems of gathering and convergence of robots when some of them may be subject to failures. Our first contribution is of geometric nature. We provide a protocol to compute the Weber point of a large class of rotational symmetric configurations. Based on this primitive, we present an algorithm that solves thegathering problem in presence of any number of crash failures. Then, we address the convergence problem when robots may incur byzantine failures which are harder to handle than crash failures. We provide several tight bounds relating the degree of synchronicity of the system to its resiliency. Finally, we study robots that are endowed with memory and we show that this model is stronger than the message passing model. The different node types in an uniformized manner. Our experimental results show that this model is able to take in account the correlations between labels of different node types.