Description
Date depot: 1 janvier 1900
Titre: Réseaux de Robots Réalistes
Directeur de thèse:
Sébastien TIXEUIL (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Le sujet principal de la thèse est de modéliser mathématiquement les contraintes opérationnelles (en particulier, électroniques et physiques) liées aux activités des réseaux de robots organisés en essaim, et de développer des algorithmes distribués réalistes dans ce contexte.
Les travaux de la communauté “Robotique” se concentrent principalement sur la conception et la programmation de robots économiquement réalisables mais ces travaux utilisent des solutions algorithmiques simplifiées (centralisation des décisions avant leur diffusion à l’ensemble des robots). Ces aspects rendent improbable leur passage à l’échelle et leur capacité à résister à des pannes inopinées [1].
Les travaux de la communauté “Algorithmique distribuée” [2], à l’inverse, définissent des solutions distribuées et élégantes, mais prennent en compte des modèles comportant des simplifications parfois abusives. Les modèles considérés présentent, par exemple, les caractéristiques suivantes, qui ne peuvent exister en pratique :
les robots disposent d’une mémoire volatile infinie, mais ne disposent pas de mémoire persistante ;
les robots n’ont pas d’existence physique et sont assimilés à des points ;
les robots disposent de capteurs de précision infinie ;
les robots disposent d’actionneurs de précision, stabilité et rapidité infinies ;
aucun obstacle capable de perturber la vision ou le déplacement n’est présent sur la zone de fonctionnement.
En l’état actuel, les efforts afin d’améliorer le réalisme des modèles du point de vue “Algorithmique distribuée” ont principalement traité les aspects suivants :
- Robots volumiques. Des robots non-ponctuels ont été envisagés [3], mais le modèle de vision reste inenvisageable en pratique (deux robots sont capables de se voir si il existe un point du premier robot et un point du deuxième robot que l’on peut relier par une droite qui ne coupe aucun autre robot). Par ailleurs, dans ce contexte, seul le problème du rassemblement a été étudié.
- Robots déboussolés. Des robots dont la boussole (la direction du nord indiquée par les capteurs embarqués) est imprécise ont été étudiés à plusieurs reprises [4]. Dans ces travaux, on s’intéresse cependant à des problèmes théoriques seulement (rassemblement en un même point de robots en un nombre fini d’étapes).
- Robots défaillants. L’impact de robots défaillants a été relativement peu étudié. Les pannes crash (le robot s'arrête simplement de fonctionner) rendent les solutions algorithmiques plus difficiles à obtenir [5]. Le cas des défaillances possiblement malveillantes (aussi appelées défaillances Byzantines) génère beaucoup de résultats d’impossibilités [6].
[1] http://www.independent.co.uk/news/world/robots-fukushima-nuclear-disaster-dying-probe-clean-up-tepco-toshiba-reactor-nuclear-radiation-a7612396.html
[2] Distributed computing by oblivious mobile robots
P Flocchini, G Prencipe, N Santoro
Synthesis lectures on distributed computing theory 3 (2), 1-185
[3] Jurek Czyzowicz, Leszek Gasieniec, Andrzej Pelc:
Gathering few fat mobile robots in the plane. Theor. Comput. Sci. 410(6-7): 481-499 (2009)
[4] Taisuke Izumi, Samia Souissi, Yoshiaki Katayama, Nobuhiro Inuzuka, Xavier Défago, Koichi Wada, Masafumi Yamashita:
The Gathering Problem for Two Oblivious Robots with Unreliable Compasses. SIAM J. Comput. 41(1): 26-46 (2012)
[5] Quentin Bramas, Sébastien Tixeuil:
Wait-Free Gathering Without Chirality. SIROCCO 2015: 313-327
[6] Zohir Bouzid, Maria Gradinariu Potop-Butucaru, Sébastien Tixeuil:
Optimal Byzantine-resilient convergence in uni-dimensional robot networks. Theor. Comput. Sci. 411(34-36): 3154-3168 (2010)
Doctorant.e: Heriban Adam