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:

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]

Organisation des soutenances [mis à jour le 22.12.2020]

JourHoraireModalité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.