Algorithmique appliquée
Description
Ce projet a comme contexte la compétition mondiale de robotique RoboCup et plus particulièrement la ligue SSL. Dans cettes compétition, plusieurs robots à roues se déplacent rapidement et disputent un match de football robotique.
Dans le cadre de ce projet, l'objectif sera de traiter le problème de la défense. Soit: comment placer les défenseurs pour éviter que les attaquants aient un angle de tir? Le problème sera abordé avec différents niveaux de simplifications et sera modélisé comme un problème de graphe.
Problème initial
Dans la version initiale du problème à résoudre, la position des adversaires est donnée et l'objectif est de savoir combien de robots sont nécessaires pour défendre de manière satisfaisante. On considère que chaque robot adverse peut tirer immédiatement et il faut donc couvrir tous les angles de tir possible, avec un pas de discrétisation donné.
Les variables du problèmes sont les suivantes:
- Positions des adversaires
- Taille du terrain
- Rayon du robot
- Pas de discrétisation angulaire
- Pas de discrétisation pour les positions des défenseurs
La définition des problèmes et des solutions se fera à l'aide de simples fichiers JSON, des exemples étant fournis dans le Visualiseur
Calendrier prévisionnel [mis à jour le 11.12.2020]
- Séances 1 à 3: Modélisation du problème
- Deadline: vendredi 2 octobre, 18h00
- Contenu attendu:
- Définition formelle du problème
- Modélisation du problème
- Pistes de résolution du problème
- Compatibilité de la modélisation choisie avec les extensions
- Séances 4 et 5: Méthodes exactes
- Séances 6 et 7: Méthodes gloutonnes
- Séances 8 et 9: Redéfinition du problème
- Deadline: vendredi 27 novembre, 18h00 [Mis à jour le 18.11.2020]
- Contenu attendu:
- Définition formelle du problème
- Modélisation du problème
- Algorithmes implémentés
- Extensions: fonctionnalités développés et envisagées
- Critique des performances
- Proposition de modification de la formalisation du problème
- Séances 10 à 12: Programmation dynamique, approfondissement des extensions et travail libre
- Séance 10: Groupe entier: 3 décembre
- Séance 11: Réunion par groupes de projet: 10 décembre
- Séance 12: Groupe entier: 17 décembre
- 18 janvier 20h00: Rendu des rapports et du code [mis à jour le 11 décembre]
- Pour celles et ceux qui le souhaitent, vous pouvez rendre vos rapports et votre code avant le 18 décembre à 18h. Le fait que vous n'ayez pas les vacances pour avancer votre travail sera pris en compte lors de l'évaluation.
- 20-21 janvier: Soutenances
Organisation des soutenances [mis à jour le 22.12.2020]
- Les soutenances auront lieu en présentiel ou en distanciel selon les préférences de chaque groupe.
- La soutenance commencera par une présentation de 15 minutes
- Pas besoin d'introduire le sujet
- Choix de modélisation
- Choix d'implémentation
- Traitement des extensions
- Plutôt que de survoler tous les éléments rapidement, présentez le contenu global et annoncer les éléments sur lesquels vous vous focalisez.
- La soutenance se concluera par 15 minutes de discussion
Jour | Horaire | Modalité | Groupe |
---|---|---|---|
Mercredi 20 janvier 2021 | 14h00-14h30 | Distanciel | Maurin |
Jeudi 21 janvier 2021 | 13h30-14h00 | ??? | PaarDeKooper, De Castro Pinto |
Jeudi 21 janvier 2021 | 14h00-14h30 | ??? | Pichon |
Jeudi 21 janvier 2021 | 14h30-15h00 | ??? | Simba |
Jeudi 21 janvier 2021 | 15h00-15h30 | ??? | Abderrahmane, Alan, Cataldi |
Jeudi 21 janvier 2021 | 15h30-16h00 | ??? | Carn, Capdordy |
Jeudi 21 janvier 2021 | 16h00-16h30 | ??? | Arnault, Dauriac |
Jeudi 21 janvier 2021 | 16h30-17h00 | ??? | Loison |
Jeudi 21 janvier 2021 | 17h00-17h30 | ??? | Gharout |
Jeudi 21 janvier 2021 | 17h30-18h00 | ??? | Clauzel |
Liens utiles
Extensions [Mis à jour le 17 décembre]
Plusieurs buts
Dans cette variante, les attaquants ont le droit de marquer dans plusieurs buts, ce qui ne change pas les objectifs, mais augmente le nombre de possibilités des attaquants.
Position initiale des joueurs
En pratique, les robots ne peuvent pas se téléporter, il faut donc que les cibles données aux défenseurs soient proches de leurs positions actuelles. Dans cette version du problème, la position initiale et le nombre de défenseurs sont connus et l'objectif est de minimiser le temps nécessaire pour atteindre une position de défense satisfaisante. Autrement dit, minimiser la distance maximale entre la position initiale et la position cible pour les défenseurs.
Distance minimale entre les robots
La précision du placement et de la localisation des robots étant limitée. Il peut être souhaitable d'espacer les défenseurs pour éviter des risques de collisions. L'un des paramètres optionnel est donc la distance minimale autorisée entre le centre de deux robots, celle-ci pouvant être supérieure au diamètre des robots.
Gardien
Dans cette version, une partie du terrain est réservée au gardien, les zones disponibles pour le gardien sont donc différentes des zones disponibles pour les autres défenseurs.
Vitesse maximale
Cette extension introduit des vitesses limites pour la balle et les robots défenseurs. Cela permet de modéliser le fait qu'un robot défenseur peut se déplacer alors que la balle roule pour intercepter le tir.
Trajectoires courbées
Certaines équipes sont capables d'effectuer des tirs courbés. Il est donc intéressant d'étendre le modèle de graphe pour prendre en compte le fait que les tirs peuvent être courbés. La paramétrisation des courbes et son implémentation dans le visualiseur ne sont pas encore disponibles.
Version libre
L'un des aspects les plus importants de la résolution de problèmes est le choix de la modélisation à utiliser. Pour le problème initial ainsi que pour les extensions, la problématique a déjà été traduite en problèmes simplifiés. Une des pistes de travail proposée pour vos rapports est donc de repenser la manière dont est modélisé le problème pour sélectionner les variables qui vous semblent les plus importantes. Cette version ne nécessite pas forcément d'être implémentée et peut être simplement une discussion dans votre rapport. Un regard critique sur la complexité du modèle engendré par votre proposition sera nécessaire.