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:

• déterminer s'il existe k chemins noeuds-disjoints, c'est à dire k chemins qui passent par des noeuds différents (hormis la source et la destination elles-mêmes).
• version dans laquelle l'algo trouve lui-même le plus grand k
• afficher les noeuds les plus critiques ? (Ceux dont la suppression diminuerait k)
• afficher les k chemins eux-mêmes
• faire une version interactive, dans laquelle on peut marquer / démarquer des sommets à la souris pour indiquer qu'ils sont interdits, et où le calcul de k (ou des chemins) se met à jour

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 :

• Permettre à l'utilisateur de placer les villages
• Faire une version simple avec un seul robot (tester au moins deux algos ?)
• Afficher le temps max de communication entre villages
• Faire une version multi-robots (au moins 2 algos différents)
• Observer comment l'augmentation du nombre de robots améliore le temps.
• Ajouter des composants graphiques pour choisir les différents paramètres

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 :

• Créer une visualisation adaptée à ce scénario
• Concevoir une stratégie collective (distribuée) pour permettre au maximum d'agents d'atteindre le trésor vivants
• Faire un version où les agents ne peuvent rien écrire sur les sommets
• Faire varier les hypothèses (ensemble / pas ensemble; écrire sur les sommets / ne pas écrire; etc.) en faisant plusieurs versions.
• Ne pas faire trop de versions, mieux vaut entre 2 et 4 version bien comprises et analysées plutôt que beaucoup.
• Permettre à l'utilisateur de spécifier lui-même le graphe, les pièges, etc.

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

Evaluation

• Le code source de votre projet
• Un rapport de 2 à 4 pages en LaTeX
• Une soutenance de 10 minutes (+ questions)
• Une vidéo pédagogique (présentée également pendant la soutenance)