Skip to content

Latest commit

 

History

History
88 lines (64 loc) · 3.96 KB

README.md

File metadata and controls

88 lines (64 loc) · 3.96 KB
Raw

Graph Exploration with Deep Reinforcement Learning

This project addresses the problem of efficiently exploring unseen environments. The aim is to build a framework where an agent can learn to explore a graph, visiting the maximum number of states in a limited number of steps. This has been done (at least tried) with the combination of Deep Reinforcement Learning and Geometric Deep Learning. The environments considered in this project are small 5x5 grid graphs with a few obstacles like this one:

Training

An agent has been equipped with two Graph Neural Networks[1] in order to implement the DQN (and DDQN) algorithm. The training has been done on 1 graph and the results below have been drawn from the test-set of 9 unseen graphs. The two (identically structure) GNNs are coded (here) as sequential models built on top of the Gated Graph Sequence Neural Network [2], as implemented here [3]. You can find a more detailed analyis in my report.

My training went throug 10000 episodes of 25 steps each, where an exponentially-decaying epsilon-greedy strategy selected the actions for the agent. You can load my training notebook, beware that the code is quite messy.

In the plots above a few metrics are shown:

  1. Top left = Loss
  2. Top right = Epsilon decay
  3. Bottom left = Reward
  4. Bottom right = Nodes visited

Testing

The 10 environments used for this project are

where (a), (b), ..., (j) are maze_5x5_i.npy with i going from 0 to 9. You can plot these by running the plot_graph.py script.

Every environment was tested for 30 episodes of 25 steps each, where the agent could only use the action proposed by the previously trained network. At the end of every episode the percentage of valid nodes visited by the agent has been registered and the table below shows the results in term of mean, std and best episode coverage. The agent was trained on maze_5x5_0.

Map Mean Std Best Run
maze_5x5_0 89.8 8.3 100.0
maze_5x5_1 61.9 25.6 88.9
maze_5x5_2 78.5 10.7 94.4
maze_5x5_3 55.2 20.7 88.9
maze_5x5_4 74.0 9.5 89.5
maze_5x5_5 62.6 18.0 83.3
maze_5x5_6 71.4 19.1 88.2
maze_5x5_7 63.5 11.1 81.0
maze_5x5_8 56.0 23.9 85.0
maze_5x5_9 82.1 9.2 95.5

The results above have been obtained with models/model_16_03_2020-122921.pt.

The next table shows the results for a random policy, where the agent selects the next action by (uniformly) randomly samplig the action space (which is {left, up, right, down}).

Map Mean Std Best Run
maze_5x5_0 34.5 11.8 57.9
maze_5x5_1 32.2 11.2 55.6
maze_5x5_2 33.1 11.6 72.2
maze_5x5_3 31.1 10.0 50.0
maze_5x5_4 30.8 12.1 57.9
maze_5x5_5 32.2 8.7 55.6
maze_5x5_6 28.2 8.0 41.2
maze_5x5_7 36.9 12.8 57.1
maze_5x5_8 37.0 9.5 55.0
maze_5x5_9 36.1 10.8 54.5

The testing code can be found in the testing notebook. Beware that the code is quite messy! You may want to test locally with test.py.

Requirements

I've written the code directly into Google Colab, if you import the notebooks into Colab (Python3 + GPU) they should work out of the box. The libraries used are

numpy
gym
networkx
torch >= 1.4.0
torch_geometric
tensorboard >= 2.0
matplotlib