Projet MOGPL — La balade du robot

👥 Équipe

• Guetteville Nathan
• Traore Ali

---

🎯 Description du projet

Ce projet vise à déterminer le temps minimal nécessaire pour qu’un robot se déplace dans un dépôt modélisé sous forme de grille contenant des obstacles.
Le robot se déplace à l’aide de deux types de commandes :

• a1, a2, a3 : avancer de 1, 2 ou 3 cases ;
• G, D : tourner à gauche ou à droite.

Chaque commande coûte 1 seconde, ce qui permet de modéliser le problème comme un plus court chemin dans un graphe orienté.
Un état est défini par :

• une position (i, j),
• une orientation (nord, sud, est, ouest).

Le projet inclut :

1. la modélisation du problème sous forme de graphe,
2. l'implémentation d’un BFS optimisé,
3. la génération aléatoire d’instances,
4. des expériences numériques (taille de grille, nombre d’obstacles),
5. une génération optimisée d’obstacles via Gurobi (programmation linéaire).

---

📁 Structure du projet

/.
│── src/
│ ├── main.py # Programme principal
│ ├── algo.py # BFS + reconstruction du chemin
│ ├── Node.py # Classe représentant un état du robot
│ ├── utils.py # Fonctions utilitaires
│ ├── instance_generator.py # Génération d'instances aléatoires
│ ├── obstacles_placement.py # Génération d'obstacles via PL + Gurobi
│
│── data/
│ ├── instancesC/ # Instances produites
│ ├── instancesD/ # Instances produites
│ ├── outputC/ # Résultats des expériences
│ ├── outputD/ # Résultats des expériences

│
│── benchmarks/
│ ├── Benchmarks_D.csv # Temps (P variable)
│ ├── Benchmarks_N.csv # Temps (N variable)
│ ├── plot_benchmarks.py # Scripts d'affichage
│
│── requirements.txt
│── .gitignore
│── README.md
│── GR2_Traore_Guetteville.pdf (Rapport)

---

🛠️ Installation

1. Créer un environnement virtuel

python3 -m venv venv
source venv/bin/activate          # macOS / Linux
# ou venv\Scripts\activate.bat    # Windows

2. Installer les dépendances

pip install -r requirements.txt

⚠️ Gurobi doit être installé séparément (nous avons utilisé les machines de l'établissement)

▶️ Exécution

Lancer le programme principal :

python -m src.main

Une invite de commande vous est alors demandée :

• "B" pour éxécuter les benchmarks et consulter les temps de calcul
• "G" pour générer une instance aléatoire à partir des paramètres de votre choix, afin de visualiser la grille ainsi que le chemin trouvé : le point bleu représente le point de départ, tandis que le triangle jaune représente l'objectif. Pensez à fermer la fenêtre matplotlib avant de saisir des paramètres.

Vous pouvez quitter le logiciel en saisissant "Q" lors d'une invite de commande