Introduction

On va travailler sur ce TP sur la simulation d’agents mobiles avec le simulateur davis. Le but sera de travailler sur les algorithmes vus en cours. davis est un environnement de visualisation d’algorithmes distribués pour le simulateur JBotSim développé au LIS.

Prérequis

Pour que cette séance se passe bien, nous vous conseillons d’installer les logiciels suivant :

• installer openjdk (avec la ligne de commande sudo apt install openjdk-8-jdk ou sudo apt install openjdk-11-jdk sous linux suivant la version voulue). Vous pouvez aussi installer le JDK 8 d’oracle.
• installer git (avec la ligne de commande sudo apt install git sous linux)
• installer IntelliJ IDEA.

Installation davis

Afin de vous faciliter le travail, nous avons créer un projet déjà configuré.

Adresse du projet : https://gitlab.lis-lab.fr/davis/basic-example.git

Lancer IntelliJ, puis commencez un nouveau projet depuis un dépot git en

• cliquant sur Check from version control depuis la fenêtre de lancement d’IntelliJ
• ou bien en passant par les menus d’IntelliJ : menu File, New, Project from version control, Git.

Dans les deux cas, renseignez l’adresse du dépôt git donnée au dessus.

Compilation et exécution

Avec gradle en ligne de commande

Vous pouvez sauvegarder toutes les configurations dans le fichier scénario.

1. Écrivez vos algorithmes dans le répertoire src : MyAlgo.java
2. Ouvrez le fichier scr/scenario et ajoutez une ligne ayant les 5 paramètres suivants : <ScenarioName> <networkGeneratorFile> <scheme> <size> <algoFile : MyAlgo.java>
3. Utilisez la ligne de commande ./gradlew runScenarioName

Avec Intellij et gradle

1. Écrivez vos algorithmes dans le répertoire src : MyAlgo.java
2. Ouvrez le fichier scr/scenario et ajoutez une ligne ayant les 5 paramètres suivants : <scenarioName> <networkGeneratorFile> <scheme> <size> <algoFile : MyAlgo.java>
3. Rafraichissez le panneau gradle (onglet à droite d’IntelliJ).
4. Dans Tasks/application du panneau gradle, votre test devrait apparaître.
5. Cliquez dessus pour l’exécuter.

Interface graphique

• Bouton NEW : Réinitialise le réseau.
• Bouton START : Démarre la simulation ou la relance.
• Bouton PAUSE : Met en pause la simulation
• Bouton STEP : Réalise un pas de calcul (dans le modèle actuellement considéré).
• Vitesse de simulation : Cette vitesse est contrôlée par le widget

Fonctionnement des agents mobiles dans davis

Les agents mobiles disposent des primitives suivantes :

• void become(String state) : met l’agent dans l’état state à la ronde suivante. Il doit y avoir au moins une méthode void state(MyClass object). La méthode void state(MyClass object) correspondant à l’état state de l’agent est appelée à chaque début d’étape. Il est important qu’un appel à cette méthode n’engendre qu’un seul déplacement de l’agent.
  
• void log(String info) : affiche un message info (automatiquement précédé du toString() de l’agent).
• des primitives de déplacement :
  • méthode void stay() : permettant de rester sur place. Si l’agent ne doit pas se déplacer à cette étape il faut appeler cette méthode.
  • Anneau : void goRight() et void goLeft() qui permettent à l’agent de se déplacer à droite ou à gauche.
  • Grille : boolean goRight(), boolean goLeft(), boolean goTop() et boolean goBottom() qui permettent à l’agent de se déplacer à droite, à gauche, en haut ou en bas. Si le mouvement dans cette direction n’est pas possible, la méthode retourne false et l’agent n’est pas déplacé. La méthode retourne true si le déplacement est effectué.
• void init() : méthode que vous devez implémenter pour initialiser l’agent : lui donner un état de départ et des valeurs initiales pour ses attributs.
• ìnt getID() : permet de récupérer l’identifiant de l’agent.
• int getTopologySize() : permet de récupérer la taille du réseau.

Rendez-vous dans l’anneau

Pour cet exercice, nous allons considérer des agents avec identifiants dans un anneau anonyme. On va considérer un anneau de taille 18 avec 2 agents disposés de manière symétrique et comme premier algorithme une marche aléatoire (une chance sur deux à chaque étape d’aller dans une direction).

On va utiliser pour cette partie le générateur de topologie RingAnon2AgentsSym.java et l’algorithme RandomWalkRing.java. On utilisera donc le scénario suivant (déjà présent dans le projet) :

RandomWalkRing RingAnon2AgentsSym.java Anonymous 18 RandomWalkRing.java

Questions

• Pourquoi l’algorithme de la marche aléatoire ne fonctionne pas dans l’exemple choisi (anneau de taille 18 avec 2 agents disposés de manière symétrique) ?
• Comment corriger l’algorithme de marche aléatoire pour qu’il fonctionne pour ce cas ?
• Implémentez les autres algorithmes de rendez-vous naïfs évoqués dans le cours :
  • Algorithme AlgorithmSizeRing.java dans lequel chaque agent effectue \(id\) tours de l’anneau dans le sens des aiguilles d’une montre dans l’anneau (se déplace \(id.n\) étapes vers la droite). Vous pouvez rajouter une classe dans Intellij avec un clic droit sur le dossier suivi de New -> Java class. On utilisera le scénario suivant : AlgorithmSizeRing RingAnon2AgentsSym.java Anonymous 16 AlgorithmSizeRing.java.
  • Algorithme AlgorithmSpeedRing.java dans lequel chaque agent tourne à vitesse \(\frac{1}{id}\) (se déplace puis attend \(id-1\) étapes) dans le sens des aiguilles d’une montre dans l’anneau. On utilisera le scénario suivant : AlgorithmSpeedRing RingAnon2AgentsSym.java Anonymous 16 AlgorithmSpeedRing.java.

Rendez-vous dans le chemin

Pour cet exercice, nous allons considérer des agents avec identifiants dans un chemin anonyme. On va considérer un chemin de taille 18 avec 2 agents et comme premier algorithme une marche aléatoire (choix aléatoire uniforme parmi la ou les directions possibles).

On va utiliser pour cette partie le générateur de topologie RectangularTwoAgents.java et l’algorithme RandomWalkPath.java. Le générateur de topologie est écrit pour une grille mais il suffit de fixer la hauteur à un pour obtenir un chemin.

On utilisera donc le scénario suivant (déjà présent dans le projet) :

RandomWalkPath RectangularTwoAgents.java Anonymous 18*1 RandomWalkPath.java

Questions

• Pourquoi l’algorithme de la marche aléatoire ne fonctionne pas dans l’exemple choisi ?
• Comment corriger l’algorithme de marche aléatoire pour qu’il fonctionne pour ce cas ?
• Peut-on écrire un algorithme plus simple de rendez-vous en utilisant le fait que les deux agents sont d’accord sur les directions gauche et droite ? Si oui, implémentez cet algorithme.

Rendez-vous dans la grille

Pour cet exercice, on va garder le générateur de topologie RectangularTwoAgents.java mais cette fois on va considérer une grille de taille \(18\times 10\). Vous utiliserez au départ l’algorithme RandomWalkRectangular.java que vous allez devoir écrire.

On utilisera donc le scénario suivant (à ajouter dans le dossier src/scenario) :

RandomWalkRectangular RectangularTwoAgents.java Anonymous 18*10 RandomWalkRectangular.java

Questions

• En partant du fichier RandomWalkPath.java, écrivez une classe RandomWalkRectangular.java effectuant une marche aléatoire dans la grille et donc prenant en compte les quatre directions possibles dans la grille.
• Peut-on écrire un algorithme plus simple de rendez-vous en utilisant le fait que les deux agents sont d’accord sur les directions haut, bas, gauche et droite ? Si oui, implémentez cet algorithme.

Questions supplémentaires

• Implémentez les algorithmes suivant de rendez-vous dans le chemin :
  • l’algorithme de rendez-vous dans le chemin avec une mémoire \(O(\log\log n)\) qui est décrit à la fin du cours.
  • une adaptation l’algorithme dans l’arbre mais ne fonctionnant que dans le chemin
• Implémentez l’algorithme de rendez-vous optimal dans l’anneau décrit dans le cours. Vous pouvez commencer par implémenter un des deux algorithmes qui ne fonctionne que pour l’un de deux cas.