How to represent grid environment as a graph?

user_17659557 0
Viewed 90

I would like to try to proceed some experiment, where I give two inputs for reinforcement learning agents. As first input, I would like to provide him grid-like environment that would represent room-maze with some walls and reward in one of the maze rooms. And the second one would be a graph representation of this maze.

I'm still stuck at planning the experiment, because I'm not sure about creating sufficient way to create a proper graph structure of 2D-grid environment. For example, I was thinking about looking for some algorithms that is able to find modularities (e.g. modules could correspond to rooms).

Do you have any idea what would be worth recommending when it comes to building a graph? And maybe what RL algorithm would work fine on both?

agent reinforcement-learning graph python
1 Answers

A maze grid is often represented in a text file as "ASCII ART"

enter image description here

The * mark the cells that are in the path from the start to the end.

It is fairly straightforward to write code to read this text file and create a graph with links between adjacent cells. If there is a wall the link has "infinite" cost, if there is a door then the link cost can be small or zero. From this graph a standard path finding code will find the path through the maze.

Here is the result as visualized by graphviz

enter image description here

"cnrm" is the node representing the call at row m, column n and the path is highlighted in red.

You can look at C++ code for doing this at https://github.com/JamesBremner/PathFinder specifically the code to read the ascii art and generate the graph is in https://github.com/JamesBremner/PathFinder/blob/main/src/cMaze.cpp

user_165820
Related