Algorithmique de la mobilité

↑ Accueil du cours


Projets 2022-23

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) Chemins disjoints et k-connexité

Domaine d'application : cyber-sécurité + tolérance au pannes.

Etant donné une source et une destination:

Adaptations possibles en fonction des souhaits du binôme (à discuter avec l'enseignant).

2) Entités mobiles pour rétablir la connexité

Domaine d'application : déploiement réseau dans des zones sans infrastructure

Entrée : Nous avons des noeuds isolés dans un réseau (trop éloignés pour communiquer). On souhaite déployer des robots mobiles qui vont se déplacer pour rétablir une forme de connexité entre ces noeuds.

Objectifs :

On peut supposer que les robots sont initialement placés là où l'algo le souhaite.

Adaptations possibles en fonction des souhaits du binôme (à discuter avec l'enseignant). Une amélioration utile serait de pouvoir connaître la valeur optimale (qui à utiliser un algo de brute force) pour comparer les solutions de vos algorithmes.

3) Chasse au trésor piégée

Domaine d'application : intelligence collective / robotique (?)

L'environnement est représenté par un graphe. Nous avons des agents placés sur les noeuds du graphe. Ils peuvent se déplacer sur les noeuds voisins. Ils peuvent communiquer entre eux lorsqu'ils sont sur un même sommet. Ils démarrent sur un noeud x et doivent trouver un noeud y (le trésor), mais il y a des noeuds piégés qui suppriment tout agent qui se rend dessus.

Objectif :

Adaptations possibles en fonction des souhaits du binôme (à discuter avec l'enseignant).

Evaluation