logo EDITE Sujets de doctorat

Communiquer sans moyen direct de communication au sein d'une équipe de robots sujets à des pannes et des attaques

Sujet proposé par
Directeur de thèse:
Doctorant: Marjorie Audrey Elodie BOURNAT
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Domaine: Sciences et technologies de l'information et de la communication

Projet

La décennie qui vient de s'écouler a vu naître un regain d'attention de l'approche multi-agent en robotique. Comme dans de nombreux autres domaines, cet engouement n'est pas le fruit du hasard mais plutôt celui d'une simple constatation : dans bien des cas, il vaut mieux disposer de plusieurs entités plutôt qu'une seule pour mener à bien une tâche donnée. Et la robotique ne déroge pas à la règle. Cependant qui dit approche multi-agents/robots, dit également collaboration et coordination entre ces mêmes robots pour l'accomplissement d'une tâche commune. Or, la réussite de la plupart des tâches collaboratives est intimement liée aux aptitudes dont disposent les robots, comme leur capacité à se déplacer et leur capacité à percevoir leur environnement, en d'autres termes leurs facultés à interagir avec leur environnement dont l'exemple le plus emblématique se retrouve dans les moyens de communications qui passent le plus souvent par le biais de technologies sans fil. Cette faculté à communiquer semble très souvent incontournable pour la réalisation d'une tâche commune et s'avère d'ailleurs même être un pré-requis nécessaire pour des missions qui consisteraient à relayer des informations ou faire du renseignement. Une question qui vient alors à l'esprit est celle de savoir s'il existe des tâches pouvant être résolues par des robots dépourvus de moyens de communications directs ?

Ils existent plusieurs études sur le sujet dans la littérature, en particulier dans les domaines de l'intelligence artificielle [8] et de l'automatique [1]. La plupart de ces travaux tentent de faire émerger des comportements collectifs fondés sur des heuristiques. Beaucoup ont en commun de s'inspirer de travaux issues de recherches en biologie concernant le comportement de certains animaux, principalement les insectes sociaux tels que les fourmis, les termites ou encore les abeilles. En effet, ces derniers présentent ce que certains appellent une intelligence collective, c'est à dire un ensemble de capacités et de comportements complexes résultant d'interactions multiples entre les membres d'une même communauté, dont ces derniers ne pourraient faire preuve si chacun d'entre eux était isolé ou mis à part.

Aussi, la résolution de certaines tâches émergent naturellement des interactions et communications indirectes entre les individus. Cette inclination à communiquer via des communications indirectes ou implicites est évoquée sous le terme de "stigmergie" par les biologistes [6]. La nature recèle de nombreux exemples de communications indirectes, que ce soient les fourmis ou les termites qui échangent des informations en déposant des phéromones ou encore les abeilles qui exécutent une danse sui generis afin d'indiquer le lieu de provenance de la nourriture. Dans le règne animal, la stigmergie se réfère la plupart du temps à des manifestations de coopération non conscientes ayant pour but l'accomplissement d'une tâche spécifique, notamment se nourrir ou se défendre.

Le phénomène de stigmergie se révèle donc être toujours en relation très étroite avec l'exécution d'une tâche donnée, c'est-à-dire communiquer n'est jamais considéré comme une tâche ou une fin en soi. Même si la stigmergie permet à certains insectes de modifier leur environnement, elle ne permet pas a priori de bavarder ou d'échanger des informations qui ne seraient pas en rapport avec une mission spécifique. Ainsi, bien qu'elle soit une source d'inspiration dans de nombreux domaines reliés aux systèmes distribués, par exemple l'intelligence en essaim [6] ou les technologies de la communication [9, 10], avant les travaux de [2], la stigmergie n'a jamais été envisagée comme média en tant que tel, c'est-à-dire comme moyen de transmettre des informations explicitement et intentionnellement.

Dans [2], les auteurs introduisent l'utilisation de signaux par le mouvement (par analogie aux danses des abeilles ou aux signaux utilisés dans l'aéronautique) comme moyen de communication explicite entre robots dépourvus de tout moyen direct de communication : on parle alors de stigmergie intentionnelle. Ces signaux permettent d'échanger des informations même dans un environnement où les communications ne sont pas possibles. Les scenarii où des robots peuvent être dépourvus de moyen de communications ne manquent pas. On peut par exemple citer le cas où la faculté à communiquer des robots a été désactivée (pour des raisons de sécurité/confidentialité) ou le cas où les communications sont brouillées (dans des conditions hostiles). On peut également citer le cas où les transmetteurs/récepteurs sont défaillants ou lorsque des contraintes physiques (taille des équipements et/ou des robots, capacité énergétiques, etc.) ne permettent tout simplement pas aux robots d'embarquer un émetteur/récepteur.

Plusieurs algorithmes déterministes sont proposés dans [2]. Ils sont adaptés aux aptitudes (ou équipements) des robots comme la présence ou l'absence du sens d'orientation (boussole), d'identification visible (par exemple, la couleur) ou encore des limites de leur capacité de vision (limitée ou non à une certaine distance).

Le but de la thèse consiste à proposer des solutions au problème de la stigmergie intentionnelle c'est-à-dire communiquer via les déplacements, dans un contexte où les robots sont sujets à des défaillances (ou fautes). Nous envisageons d'étudier deux natures de fautes : les fautes transitoires (ou occasionnelles) et les fautes Byzantines.

L'auto-stabilisation [3, 4, 5] est un paradigme bien connu dans le domaine des systèmes distribués pour développer des solutions tolérantes aux fautes transitoires, quelque soit la sévérité des fautes. En effet, un algorithme distribué est dit auto-stabilisant, si, quelles que soient ses conditions de départ, il finit par fonctionner correctement vis-à-vis des spécifications du problème qu'il est sensé résoudre. Cette approche consiste à ne pas se soucier du fonctionnement du système pendant les défaillances et de garantir qu'une fois les défaillances terminées, le réseau recouvre un fonctionnement (ou comportement) correct en un temps fini.

Un robot est dit byzantin lorsque son comportement peut être complètement erratique et aléatoire. Il peut par exemple s'agir d'une erreur ou d'une intrusion hostile dans le programme du robot. Ce cas se révèle particulièrement intéressant car il s'avère être le pire des cas que l'on puisse rencontrer dans le domaine de la tolérance aux fautes en ce sens que, si on possède un algorithme capable de supporter la présence de k robots byzantins dans une cohorte, on possède alors un algorithme capable de résister à n'importe quel types de pannes touchant k robots ou moins.

Dans le cadre de cette thèse, nous espérons apporter des solutions auto-stabilisantes et/ou tolérant les fautes byzantines dont l'efficacité dépende du niveau de synchronisation des robots entre-eux.

REFERENCES

[1] C.R. Kube. Task modelling in collective robotics. Auton. Robots, 4(1) :53–72, 1997.

[2] Yoann Dieudonné, Shlomi Dolev, Franck Petit, and Michael Segal. Deaf, dumb, and chatting robots: Enabling distributed computation and fault-tolerance among stigmergic robots. In Thirteenth International Conference On Principle Of DIstributed Systems (OPODIS 2009), volume 5923 of Lecture Notes in Computer Science, pages 71–85, Nîmes, France, 2009. Brief Announcement in the Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing (PODC 2009), pages 308-309.

[3] Stéphane Devismes, Franck Petit, and Vincent Villain. Autour de l’auto- stabilisation : Partie I : Techniques généralisant l’approche. Technique et Science Informatiques, 30 :1–22, 2011.

[4] Stéphane Devismes, Franck Petit, and Vincent Villain. Autour de l’auto- stabilisation : Partie II : Techniques spécialisant l’approche. Technique et Science Informatiques, 30 :23–50, 2011.

[5] Shlomi Dolev. Self-stabilization. MIT Press, 2000.

[6] Andries P. Engelbrecht. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, 2006.

[7] P-P Grassé. La reconstruction du nid et les coordinations inter-individuelles chez bellicosi-termes natalensis et cubitermes sp. la theorie de la stigmergie : Essai d’interpretation des termites constructeurs. Insectes Sociaux, 6 :41–83, 1959.

[8] MajaJ. Mataric. The Robotics Primer (Intelligent Robotics and Autonomous Agents). The MIT Press, 2007.

[9] C Tovey. The honey bee algorithm : A biological inspired approach to internet server optimization. Engineering Enterprise, the Alumni Magazine for ISyE at Georgia Institute of Technology, Spring 2004 :13–15, 2004.

[10] H.F Wedde and M Farooq. A comprehensive review of nature inspired routing algorithms for fixed telecommunication networks. J. Syst. Archit., 52(8) :461–484, 2006.

Enjeux

Permettre à des essaims de robots de communiquer entre eux dans des environnements hostiles où les moyens de communications conventionnels ne sont pas possible.

Remarques additionnelles

Projet financé en partie par la Direction Générale de l'Armement (DGA, Ministère de la Défense).

Thèse co-encadrée avec Yoann Dieudonné.