Sujet : Réveil de robots dans les graphes

Responsables : Cyril Gavoille, Nicolas Hanusse
Contacts : gavoille@labri.fr, hanusse@labri.fr
Département : Combinatoire et Algorithmique
Équipes : Graphes et Optimisation / Algorithmique Distribuée
Type : thèse de doctorat en Informatique
Lieu : LaBRI
Mot-clés : graphe, graphe planaire, réveil de robots ("freeze-tag problem")

Présentation du sujet :

On s'intéresse au problème de réveiller un ensemble de robots disséminés dans une certaine région du plan à l'aide d'un robot initialement actif (ou réveillé). Seul un robot actif peut réveiller (et donc rendre actif) un robot inactif (ou endormis). Pour ce faire, le robot actif doit se rendre à la position du robot inactif. Le réveil des robots peut se faire en parallèle dès qu'une équipe d'au moins deux robots réveillés est formée. L'objectif est alors de réveiller le plus rapidement possible l'ensemble des robots endormis, en supposant que la vitesse de déplacement des robots est unitaire.

De nombreux résultats sont connus pour ce problème nommé Freeze-Tag Problem et introduit en 2002 [ABFMS02], notamment lorsque les robots sont positionnés sur un plan muni de la distance euclidienne. En particulier, il a été montré que toute configuration de $n$ robots endormis à distance au plus $r$ du robot éveillé peut être réveilléé en temps $O(r)$ [ABFMS06][ABGHM03]. Plus précisément, c'est au plus $5\sqrt{2}\cdot r$ comme montré récemment dans [BCGH24]. Cependant le problème algorithmique sous-jascent, déterminer la solution optimale pour chaque configuration de robots, est réputé difficile [AAJ17].

Il s'agit ici d'investiguer la variante "graphe" du problème, c'est-à-dire où les robots sont initialement situées sur des sommets du graphe et où la distance entre deux robots est déterminée par la distance dans un certain graphe $G$. En quelque sorte tous les déplacements des robots sont assujettis à suivre les arêtes de $G$. Dans ce contexte, on pourra par exemple essayer de déterminer, pour une classe de graphes donnée, comme les graphes planaires-extérieurs ou les graphes planaires de diamètre $r$, quelle est la plus petite constante $k$ telle que tous les robots peuvent être réveillés en temps au plus $k\cdot r$.

Références :

[login: gavoille, pwd: bib0]

[ABFMS02]
Esther M. Arkin, Michael A. Bender, Sándor P.
Fekete, Joseph S.B. Mitchell, and Martin Skutella. The freeze-tag problem: How to wake up a swarm of robots. In 13th Symposium on Discrete Algorithms (SODA), pages 568–577. ACM-SIAM, 2002. See [ABFMS06].

[AAJ17]
Zachary Abel, Hugo A. Akitaya1, and Yu Jingjin.
Freeze tag awakening in 2D is NP-hard. In 27th Annual Fall Workshop on Computational Geometry (FWCG), November 2017.

[ABFMS06]
Esther M. Arkin, Michael A. Bender, Sándor P.
Fekete, Joseph S.B. Mitchell, and Martin Skutella. The freeze-tag problem: How to wake up a swarm of robots. Algorithmica, 46:193–221, 2006.

[ABGHM03]
Esther M. Arkin, Michael A. Bender, Dongdong Ge,
Simai He, and Joseph S.B. Mitchell. Improved approximation algorithms for the freeze-tag problem. In 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 295–303. ACM Press, June 2003.

[BCGH24]
Nicolas Bonichon, Arnaud Casteigts, Cyril Gavoille, and Nicolas Hanusse
. Freeze-tag in L1 has wake-up time five. Technical Report 2402.03258v1 [cs.DS], arXiv, February 2024.