Taïssir Marcé (LaBRI)
Title: How to wake-up robots in a graph? (in French)
Comment réveiller les robots dans un graphe ?
Abstract:
On se demande comment réveiller un ensemble de robots positionné dans l'espace : Initialement, seul un robot est réveillé. Pour réveiller un robot endormi, il faut qu'un robot éveillé s'y déplace physiquement.
Le problème d’optimisation émanant consiste alors à déterminer dans quel ordre réveiller les robots pour minimiser le temps total de réveil.
Dans cet exposé, on considère le problème de réveil de robot dans les espaces métriques définits par des graphes : les robots sont initialement positionnés sur des sommets du graphes et se déplacent uniquement le long des arêtes.
On présente un algorithme pour approcher le temps de réveil optimal (16.8-approximation).
Dans un second temps, on présente une version distribuée du problème de réveil de robot.