3
$\begingroup$

I am trying to build an RL agent to solve the NP-hard problem graph coloring. The problem is quite challenging.

This how I addressed it.

The environment

To preserve the scalability of the algorithm, providing the agent with the whole graph wouldn't be a good idea. Therefore, the input for the agent would be a window of embeddings.

More precisely, first, I would apply an embedding to the graph to generate fixed-size vectors to every vertex in the graph (thus, every vertex in the graph is represented as a vector that contains some information about its neighborhood and position in the graph).

Second, the agent will get a window of the embedding. For example, when coloring vertex number $17$, the input would be the $2n$ vectors from vertex $17-n$ to $17+n$, to give the agent more local information.

Third, I think the agent would require more information about the number of colors already used and the number of the already colores vertices.

The agent

My biggest problem is how the agent should be. Technically, the problem is the action space dimension. For a given graph, the maximal number of colors is the number of vertices which varies from graph to graph (losing the scalability). Plus, the possible actions at each state varies with the history of the coloring. The possible colors for a given state (or node) are all the used colors eliminating the connected colors and adding the possibility of a new color, that is, for vertex $56$, the agent has already used the first $40$ colors $\{0, 1, 2, 3, \dots,40 \}$, and node $56$ is connected to some neighbors already colored with $\{14, 22, 40 \}$, the possible colors are $\{0,1, \dots, 40 \}- \{14, 22, 40 \} + \{41\}$.

How do I overcome the high dimensional inconsistent action space?

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm fairly sure most problems with a large option for inputs simply inputs it as an image through a convnet, so I think that would certainly be step in the right direction. That being said, no one has ever actually "solved" any NP hard problem, so i wouldn't expect much no matter what network you use. You might be able to achieve something that gives some solution, just perhaps not the optimum. $\endgroup$
    – Recessive
    Jul 26, 2019 at 12:52
  • $\begingroup$ Sure. I'm trying to find an approximation for the solution. Plus, the possible set of actions depend on the whole history of coloring not only the state. So, there are actually two big problems: the high dimensional action space comparing to the low dimension of possible actions, and the set of possible action depends an all previous state not only the current. $\endgroup$
    – Ahmed Rebei
    Jul 26, 2019 at 13:18
  • $\begingroup$ I would think a recursive net, probably an LSTM, with modified hidden states that are computed through a convnet. This architecture should be capable of remembering previous states and analysing the high dimensional nature of the input (each dimension can be used as a channel into the convnet) while also providing a low dimensional output. $\endgroup$
    – Recessive
    Jul 27, 2019 at 0:27

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .