
In this project, we worked on the Natural Language Inference (NLI) task. 

We used [The Stanford Natural Language Inference (SNLI) Corpus](https://nlp.stanford.edu/projects/snli/) to train a transformer model to classify the relationship between two sentences as : 1. entailment, 2. contradiction, or 3. neutral.

Our approach was the contatenation of the two sentences with special tokens to feed the model. We used the [all-MiniLM-L6-v2](https://huggingface.co/voidful/all-MiniLM-L6-v2) model and achieved an accuracy of **0.9** on the validation set, which is on par with the state-of-the-art models. 



# Projet NLI

## *Architecture de notre projet*

* **Dossier project**: contient les logs des sbatch (logslurms), un notebook pour visualiser les données, les results (checkpoints), notre config, notre dataloader et le modèle.

* un notebook **play** qui propose à l'utilisateur de rentrer deu xphrases et d'appliquer à ces phrases notre modèle.

* un notebook **attention** qui illustre les méchanismes d'attention au sein de notre modèle.

* un fichier python **train** qui se lance via le fichier bash **submit_slurms** pour lancer des sbatch lorsque l'on veut réaliser un finetuning.

* un notebook **test**, pareil que le notebook **train** mais pour lancer en local et tester notre modèle.

## *Dataset*

Voici, à titre indicatif un **leaderboard des modèles avec leur performance respective pour la tâche de NLI sur le dataset** que l'on étudie. Même s'il n'est pas extrêment récent, il pourra nous donner une idée des caractéristique de notre dataset et de ce que sera une bonne performance sur ce dataset.

[Dataset Leaderboard](https://nlp.stanford.edu/projects/snli/)

Vous pourrez trouver dans le fichier **load_visualize** du dossier notebooks quelques commandes nous ayant permis de prendre en main le dataset.

Vous trouverez aussi dans le notebook **test** le code pour prendre en main le dataset, le charger et créer un dataloader.

## *Preprocessing*

Pour le preprocessing de nos données nous avons choisis d'extraire à chaque fois l'hypothesis et le premise, de les tokenizer puis de concatener les deux vecteurs afin de ne donner en entrée à notre modèle qu'un seul vecteur et son label. Les deux phrases étant délimitées par des séparateurs au sein du vecteur, on ne perd pas d'information en effectuant cette opération.
Par exemple les premières lignes preprocess de notre dataset sont les suivantes:

```
[CLS] a person on a horse jumps over a broken down airplane. [SEP] a person is training his horse for a competition. [SEP] [PAD] [PAD]
```
On remarque l'utilisation des token spéciaux [CLS] pour le début de la phrase et [SEP] pour la délimitation des deux phrases. On ajoute aussi des [PAD] pour compléter les phrases et avoir des inputs de même taille.

Vous pouvez trouver notre dataloader dans le fichier **data_utils** au sein du dossier **project**.


## *Nos modèles*

Pour le choix du modèle nous nous sommes inspiré de la documentation suivante, qui présente le leaderboard des modèles pour le Massive Text Embedding:

[Model Leaderboard](https://huggingface.co/spaces/mteb/leaderboard)

* Nous avons tester plusieurs modèle (Bert, Roberta et all-MiniLM-L6-v2) pour réaliser notre tâches et avons opté pour all-MiniLM-L6-v2 au vu des bonnes perfoamnces qu'il obtenait en comparaison des autres et de sa très petite taille. Il s'agit pour tous les trois de modèle transformers que nous avons adaptés pour réaliser la tâche de NLI.

* On a utilisé Wandb pour le suivi de nos expériences et pour le choix de nos hyperparamètres. Vous pouvez voir ci-dessous les courbes d'accuracy de Bert et all-MiniLM-L6-v2. Roberta n'a pas été retenu car il n'obtenait pas de bonnes performances.

![Accuracy Curces](wandb-acc.png)


* Comme vous pouvez le voir, on a atteint une accuracy d'evaluation de **0.9** avec all-MiniLM-L6-v2, le test nous donne un score de **0.89** (voir le notebook **test**).

* Nous avons choisi l'optimizer AdamW au vu des bonnes performances qu'il présentait en comparaison de SGD.

* Enfin pour la métrique, comme nous avons afaire à une  tâche de classification nous avons trouvé pertinent de prendre l'accuracy.

* Pour le scheduler, nous avons choisi d'appliquer un warmup pendant les 500 premières itérations puis de réduire le learning rate progessivement.

![Learning Rates](wandb-lr.png)

* Pour tout les autres hyperparamètres du modèle, nous avons choisi la taille des batch et réduit le max_length de chaque input pour respecter les limitations imposées par la mémoire des GPU.

## *Visualisation de l'attention*

* Avec notre meilleur modèle : all-MiniLM-L6-v2, nous avons étudié les couches d'attention du modèle entrainé. Comme vous pouvez le voir dans la figure ci-dessous, ce modèle possède 12 couches et 12 têtes d'attention. 12 couches signifie 6 couches d'attention et 6 couches de feedforward. Chaque couche d'attention possède 12 têtes d'attention.

* Chaque image représente la matrice d'attention d'une tête d'attention pour une couche donnée. Chaque pixel de l'image représente l'attention d'un token de la phrase source sur un token de la phrase cible.

* Les premières couches sont les plus interprétables car dans les suivantes les feedforward ont beaucoup mélangé les informations.

* On peut remarquer plusieurs spécificités montrant le bon apprentissage du modèle:
    * Layer 1 Head 3: Le modèle fait de l'attention sur le token précédent.
    * Layer 2 Head 9: Le modèle fait de l'attention sur le token suivant.
    * Layer 1 Head 1 et autres: Les tokens [CLS] et [SEP] ont une attention très forte sur les tokens de la phrase source et cible. Cela montre que le modèle a bien appris à les utiliser pour la classification.
    * Layer 1 Head 5: Le modèle fait de l'attention sur les tokens de la phrase source et cible qui sont les plus proches.


![Attention](attention.png)

## *Annexe: Prise en main du code*

Commandes pour lancer des sbatch sur le DCE pour le finetuning:

Se créer un environnement virutel et installer les requirements :
```
python3 -m pip install virtualenv --user
virtualenv -p python3 venv
source venv/bin/activate
python -m pip install -r requirements.txt
```

Lancer le sbatch avec `sbatch submit_slurms.sh` et cancel avec `scancel <job_id>`

Tout peut être lancé en local dont les notebooks **test**, **play** et **attention**.

Natural Language Inference


A project to solve the $1|r_j|\sum_j w_jT_j$ Scheduling problem.

A task squedulling problem on **one machine** whith :
- $r_j$ : release dates
- $p_j$ : processing times
- $d_j$ : due dates
- $w_j$ : weights



# Schedulling Problem

## Problem

The problem to solve is the following : $1|r_j|\sum w_jT_j$

The objective is to minimize the sum of the weighted delays on one machine according to minimal starting dates ($r_j$) and due dates ($d_j$)

$$
(P)=\left\{ 
    \begin{array}{ll}
        \min & \sum w_jT^\sigma_j \\
        & T^\sigma_j = \max(0,c_{\sigma(j)}-d_j) & \forall j\\
        & c_{\sigma(j)} \geq r_j + p_j & \forall j \\
        & \sigma \in S(n) \text{ : permutation}
    \end{array}
\right.
$$

We want to find a permutation of the tasks $\sigma (j)$

### Heuristics

We defined 7 heuristics to solve the problem. The heuristics are the following :

- EDD : Earliest Due Date, by sorting the jobs by due date in ascending order
- LPT : Longest Processing Time, by sorting the jobs by processing time in descending order
- SPT : Shortest Processing Time, by sorting the jobs by processing time in ascending order
- Minimum Slack : by sorting the jobs by slack in ascending order. A slack is the difference between the due date and the processing time
- Weighted SPT : by sorting the jobs by the ratio of weight and processing time in ascending order
- FIFO : First In First Out, by sorting the jobs by their arrival time in ascending order
- Weight First : by sorting the jobs by weight in descending order

### Linear Programming


We can express it as a linear programming problem by adapting the formulation that we saw during the class :

$$
(LP)=\left\{ 
    \begin{array}{ll}
        \min & \sum w_jT_j \\
        & T_j \geq 0 & \forall j\\
        & T_j \geq c_j - d_j & \forall j\\
        & c_j \geq r_j + p_j & \forall j\\
        & x_{ij} + x_{ji} = 1 & \forall i,j, i \neq j\\
        & c_j \geq c_i + p_j + M(x_{ij} - 1)& \forall i,j, i\neq j\\
        & x_{ij} \in \{0,1\}, c_j \in \mathbb{N}& \forall i,j, i\neq j\\
    \end{array}
\right.
$$

$x_{ij}$ set to 1 if job i is before job j, otherwise set to 0

$M$ is set to a high value, so that $M \geq \max (c_i+p_j)$

#### Simplified Linear Programming Problem

We can keep only the top triangle of the matrix as the relation $x_{ij} = 1-x_{ji}$ stands for the bottom triange

$$
(LP')=\left\{
    \begin{array}{ll}
        \min & \sum w_jT_j \\
        & T_j \geq 0 & \forall j\\
        & T_j \geq c_j - d_j & \forall j\\
        & c_j \geq r_j + p_j & \forall j\\
        & c_j \geq c_i + p_j + M(x_{ij} - 1)& \forall i,j, i\text{<}j\\
        & c_j \geq c_i + p_j - Mx_{ji}& \forall i,j, i\text{>}j\\
        & x_{ij} \in \{0,1\}, c_j \in \mathbb{N}& \forall i,j, i\text{<}j
    \end{array}
\right.
$$

This way we get 2x fewer variables and less constraints


### Evaluation 

For small instances (n<10), we can compare the results with the optimal solution found with the linear programming problem. For bigger instances, we can compare the results with the best heuristic (tabou multi-start).

### Aim of the Study

We build an algorithm/formula that decides wich algorithm/heuristic to use according to the parameter distributions : which one performs the best 


Scheduling Problem


A project to solve the Capacitated Vehicle Routing Problem. A problem where we have to find the best way to deliver goods to a set of clients using a set of vehicles.



# OPTIMISATION VRP

## Introduction

## Running the project
### Installation

For Windows : make sure you are using WSL2

Download CPlex from [IBM](https://www.ibm.com/products/ilog-cplex-optimization-studio/cplex-optimizer) and install it.

Modify the `CMakelists.txt` file to add the path to the CPLEX installation.

```cmake
# Path to CPLEX and CONCERT
set(CPLEX_DIR "/opt/ibm/ILOG/CPLEX_Studio2211/cplex")
set(CONCERT_DIR "/opt/ibm/ILOG/CPLEX_Studio2211/concert")
```

### Usage

```bash
bash run.sh <table_number[1:17]> (verbose{0,1,2})
```
The first argument is the number of the table to run. The second argument is the verbosity level. 0 is the default level, 1 is for more details and 2 is for debug.

## Structure of the project

### Importing the data from the tables

The data is stored in the `tables` folder. Each table is decomposed into 3 files: `distance.csv`, `demands.csv` and `vehicles.csv`.
All those files have been made from the original tables using the `cleaner.py` script.

The `config.cpp` file is responsible for importing the data from the tables and storing it in the `Config` class.

### The CPLEX model

The CPLEX model is implemented in the `CPLEX_implex.cpp` file. It is responsible for creating the model from the `Config` class, adding the constraints and the objective function and solving the model. 
The mathematical model is described in the `report.pdf` file.

### The Exact algorithm

The exact algorithm is implemented in the `exact_solver.cpp` file. It is responsible for solving the problem using an exact algorithm. It is a hierarchical approach, decomposing the problem into a partitioning problem and a TSP.
The TSP is solved using the Held-Karp algorithm (dynamic programming in O(n^2*2^n)) and the partitioning problem is solved by brute force (in O(3^n) for 3 vehicles).

### The Bottom-up Heuristic algorithm

The bottom-up heuristic algorithm is implemented in the `heuristic.cpp` file. It is an adaptation of the exact algorithm, to tackle problems with a large number of clients. In place of solving the TSP exactly, we find an upper bound using a MST and shortcutting the tour. The partitioning problem is solved using a greedy algorithm.

### The Local Search Heuristic algorithm

The tabu search algorithm is implemented in the `tabu_search.cpp` file. It is responsible for finding an approximate solution to the problem. We initialize the solution using the nearest neighbor algorithm and then we apply the tabu search algorithm to improve it.
`vrp.cpp` runs 100 different tabu search algorithms (with different initial solutions) and keeps the best one.

### The `run.sh` script

The `run.sh` script is a bash script that compiles the project and runs it with the given arguments. It calls the `vrp.cpp` file which is the main file of the project, responsible for calling every algorithm and printing the time and the results.


Vehicle Routing Problem


This project was a competition I organized for Automatants. It is inspired by Kore22 but only with a single agent. The aim was to create an environment that could be solved by metaheuristics and RL agents alike.

As the orginizer, I also created some agents to solve the environment. The best one was a DQN agent hybridized with a Monte Carlo Tree Search.



# Harvest - Optimization Competition - Agents
This repository gives a solution to the [Harvest Competition](https://github.com/Kreyparion/Harvest-Competition).

## Installation

For Installation and rules of the environment, you should read the [Readme](https://github.com/Kreyparion/Harvest-Competition#readme) of the competition

We do a small change in the environment, by putting the step_number in the State instead of putting it in the Env.

## Agents

Here we implemented some possible agents that were performing well on the environment.

### Branch&Bound

This algorithm is similar to a brute-force algorithm but we use an heuristic to make sure that we don't look into the bad solutions. We define the "bad" solution, those that are behind the best solution at any step.
We have 4 different agents, with only different heuristics. The `QuickBranchAndBound` converges quickly to around 41000 and we can use the `CVBranchAndBound` on the `best_at_depth.json` file generated by the `QuickBranchAndBound` to improve the score up to 44000.
To reuse the `best_at_depth.json` file, only switch the `use_json` argument from False to True

### DQN

The DQN is originally from the [Pytorch DQN Tutorial](https://pytorch.org/tutorials/intermediate/reinforcement_q_learning.html) on Cartpole. We adapt the existing structure of the code to the environment and improve some parts

#### The Network

The network has 2 convolutional layers and 4 fully connected layers. The convolutional layers are preceded by a layer that adds the last collomn in the front and the first one in the back and does the same for the rows. This allows to make conviolution and taking into account the looped environment.
These layers are the `Add sides` layers in the picture below

<img src="network.jpg" width="200" />



#### The Parameters

- We use a scheduler to decrease slowly the **learning rate**, it allows the agent to converge to a better solution
- We use **epsilon greedy** exploration with a decay and stop at a value were the agent can make 1 or 2 random actions per episode
- **Gamma** is set to 1 so that the agent make long term strategies 
- The **Reward** is centered to allow the qvalues to converge more easily. 

### MCTS

The Monte-Carlo Tree Search algorithm is the classic one with the usuall exploration function. Here it is used to improve the score of the DQN agent.
The point here is doing the rollout (when we calculate the value of a node), that is usually a random exploration to the leaves, with the agent and thus using really good actions. This gives a better approximation of the value of a node and, paired with the exploration of the MCTS, is able to improve the score by a lot.

The point here is that the inference of the DQN Agent is much faster and the exploration of the MCTS is better so we easily find better solutions.
This is the way I was able to achieve a total of 47223 on the Env (with the 42 seed)
You can play for yourself the 47223 execution by running the `evaluate.py` code.

### Other implemented Agents

I implemented other agents on this environment just to learn them and see how they are performing on this type of environment.
For now only reinforce was implemented and performed quite bad on this environment, maxing out at 38000.

Harvest Competition


I was in charge of the design and the development of the Automatants website. I added a lot of features to the website, including the AI Tree, a tool to organize the courses given by Automatants for the students.



AI Tree


Multi-agent pathfinding in a warehouse. The robots must retrieve the boxes and bring them to the drop-off points. The robots must avoid collisions and take into account the movements of the other robots. The algorithm used is A* multi-agent pathfinding.



# Multi-agent pathfinding in a warehouse

### Order allocation

- Clustering according to proximity of order items
- Gradual allocation of orders to robots as shelves are retrieved
    
    -> Potential improvement: Allocation of new orders through non-overloaded operators

### Collision-free pathfinding - version 5

- Check for robots stuck / waiting on a square to avoid them
- Pathfinding with dijkstra to nearest box/drop-off point, taking other robots' movements into account

### Strategies
#### Strategy 1 - Detach if operator too far away

Calculate the distance to the next available shelf and compare with the operator's distance to the shelf. Detach if operator too far away.

-> In steady state / t large enough, most robots are blocked because a shelf is at the level of the last package to be retrieved. Everything jams -> Need strategy 2

#### Strategy 2 - Detach if blocked

Detach from the shelf if the robot gets stuck and can't reach its target.

-> Problem of robots coming and going, detaching and coming back because they think the shelf they've just left needs to be processed. -> Strategy 3 needed

#### Strategy 3 - List waiting shelves without blocked shelves

List of waiting shelves: ready to be retrieved by a robot according to these criteria:
- Shelf is not already connected / the target of another robot
- Shelf has been / will soon be processed by an operator
- Shelf not blocked**

#### Strategy 4 - Stuck robots move as close as possible to their target
A jammed robot will stop and impede traffic.
It usually gets stuck when picking up its last item. It's in our interest to stop close to this item, and not in the main thoroughfare.

-> Takes precedence over strategy 2 but compatible

#### Strategy 5 - Better Pathfinding
Robots now take into account the movements of other robots and can therefore follow each other in a corridor.
This principle works with marking the next move on the floor, according to the notations in "tableau_entrepot.md". The shortest path algo takes these markings into account.

-> Optimizes even when shelves are fixed.

![Rendu](./robot_demo.gif)

Multiagent Pathfinding in a Warehouse


Short-term cloud density prediction using Satellite images and Computer Vision. The prediction was made using a U-net and a U-net mixed with LSTM.



# Short Term Weather Forcasting
Short-term cloud density prediction using Satellite images and Computer Vision

## Dataset
You can find the dataset online, made by the EUMETSAT datacenter. I personnaly used images in visible wave length from the geostationary satellite MSG.


<img src="VIS8_MSG4-SEVI-MSG15-0100-NA-20190502092744.jpg" width="150" align="left" style="margin-right: 10px;" />
<img src="VIS8_MSG4-SEVI-MSG15-0100-NA-20190502172744.jpg" width="150" />

I took pictures from 9h27 to 17h27 to have a good view of the atlantic ocean, the area I chose to work on


## Development of the project
All the steps are presented in the PowerPoint (in french)

## Adopted solution

The best performing algorithms were the U-net and the U-net mixed with LSTM

<img src="unet.png" width="600"/>

## Results

Working on 200x200 pictures gives us :

<img src="example-gif.gif" />