Algorithmique de la mobilité

↑ Accueil du cours

Projets 2021-22

Important: Pour chaque sujet, nous ne donnons ci-dessous qu'une description sommaire vous permettant de choisir ce qui vous intéresse le plus. Les objectifs de chaque projet seront ensuite affinés (probablement pendant la première séance) pour harmoniser la difficulté et la quantité de travail que cela représente pour chaque groupe et l'adapter au nombre de personnes dans le groupe.

Sujets

1) Maintenance de forêt couvrante

Nous avons vu en TP un algorithme de maintien de forêt couvrante dans un réseau dynamique. Cet algorithme utilisait un modèle à très forte atomicité : les réétiquetages de graphes (aussi appelés protocoles de population). L'objectif de ce projet est d'implémenter une version utilisant des messages classiques (en environnement synchrone). L'algorithme existe et sa description est donné dans cet article et dans cette présentation. Cet algorithme étant assez sophistiqué, le fait de le comprendre et de l'implémenter représente déjà un projet à part entière.

2) Routage et mensonge

Etant donné un réseau et un noeud destination $x$, on veut calculer, pour chaque noeud du réseau, la route locale qu'il faut emprunter pour rejoindre $x$ avec le moins de sauts possibles. L'objectif de ce projet est d'implémenter les fonctionnalités suivantes de manière distribuée :

  1. Etant donné $x$, calculer la meilleure route pour chaque autre noeud (et permettre de visualiser ces informations)
  2. Lorsque la topologie est modifiée, l'information de routage de certains noeuds deviendra automatiquement mauvaise, on dit alors que le noeud devient un "menteur". Il s'agit alors de détecter les menteurs et de les afficher
  3. Réparer les erreurs pour qu'après de tels changement, l'algorithme se restabilise sur un état dans lequel il n'y a plus de menteur.

Lien vers un article qui parle de choses similaires (mais qui ne donne pas de solution).

3) Construction d'un spanneur d'étirement 3 avec peu d'arêtes

Un spanneur est un sous-graphe qui connecte tous les noeuds d'un réseau. Par exemple, un arbre couvrant est un spanneur utilisant $n-1$ arêtes. Comme on peut s'en douter, il y a un compromis entre le nombre d'arêtes utilisées et la dégradation des distances entre sommets. On parle alors de facteur d'étirement. L'objectif de ce projet est d'implémenter un algorithme existant de construction distribuée (et locale) d'un spanneur n'utilisant que deux rondes et qui garantit un étirement de $3$ avec "seulement" $O(n\sqrt{n})$ arêtes.

L'algorithme est présenté dans ce document (issu d'un polycopié de C. Gavoille).

4) Problème du réveil de robots ("Freeze-tag")

Plusieurs robots (disons $n$) sont placés à des coordonnées aléatoires dans le plan. Ces robots sont en sommeil, pour les réveiller, il faut procéder comme suit:

  1. Choisir un robot que l'on réveille nous-même
  2. Ce robot se déplace ensuite vers un autre robot pour aller le réveiller
  3. Puis chacun de ces robots choisit un robot à aller réveiller
  4. Ainsi de suite, jusqu'à ce que tous les robots soient réveillés

L'objectif de ce projet est de minimiser le temps utilisé jusqu'au réveil du dernier robot. Il existe des travaux sur le sujet (vous pouvez chercher "freeze-tag"), cependant nous ne savons pas si les algorithmes existants sont pertinents dans le contexte d'un placement aléatoire des robots. Selon ce qui existe, vous pourrez implémenter un ou plusieurs algorithmes existants, ou en concevoir de nouveaux. Notez que l'on considère ici une version centralisée du problème (donc non distribuée).

5) Chemins disjoints et k-connexité

Etant donné une source et une destination, calculer k chemins noeuds-disjoints (c'est à dire k chemins qui passent tous par des noeuds différents, hormis la source et la destination elles-mêmes). On pourra commencer par traiter le cas k=2, puis trouver le k maximum, et enfin voir si on peut mettre à jour ces routes à moindre frais lorsque la topologie change ?

Travail à produire (date à discuter ensemble)