I am trying to solve the problem of an agent dynamically discovering(start with no information about the environment) the environment and to explore as much of the environment as possible without crashing into obstacles I have the following environment:

enter image description here

where the environment is a matrix. In this the obstacles are represented by 0's and the free spaces are represented with 1s. The position of the agent is given by a label such as 0.8 in the matrix.

The initial internal representation of the environment of the agent will look something like this with the agent position in it . enter image description here

Every time it explores the environment it keeps updating its own map:

enter image description here

The single state representation is just the matrix containing-

  • 0 for obstacles
  • 1 for unexplored regions
  • 0.8 for position of the agent
  • 0.5 for the places it has visited once
  • 0.2 for the places it has visited more than once

I want the agent to not hit the obstacles and to go around them.

The agent should also not be stuck in one position and try to finish the exploration as quickly as possible.

This is what I plan to do:

In order to prevent the agent from getting stuck in a single place, I want to punish the agent if it visits a single place multiple times. I want to mark the place the agent has visited once as 0.5 and if it has visited it more than once that place will be labelled 0.2

The reason I am marking a place it has visited only once as 0.5 is because if there is a scenario where in the environment there is only one way to go into a region and one way to come out of that region, I don't want to punish this harshly.

Given this problem, I am thinking of using the following reward system-

  • +1 for every time it takes an action that leads to an unexplored region
  • -1 for when it takes an action that crashes into an obstacle
  • 0 if it visits the place twice(i.e 0.5 scenario)
  • -0.75 is it visits a place more than twice

The action space is just-

  • up
  • down
  • left
  • right

Am i right in approaching the problem this way? Is Reinforcement Learning the solution for this problem?

Is my representation of the state , action, reward system correct?

I am thinking that DQN is not the right way to go because the definition of a terminal state is hard in this problem, what method should I use to solve this problem?


1 Answer 1


I would suggest you to use Deep Q or A2C (I personally use A2C). As a terminal state you can consider the state in which every tile has been visited once, except if you want to your agent wonder forever. I create OpenAI gym gridworlds so I can use some of their very useful wrappers (example TimeLimit wrapper in which an episode terminates when a certain number of steps has been reached).

For your state representation I would suggest you to follow well established practices. I assume that you want to use CNNs as a perceptual module and not MLP. You could either use an image of your gridworld with different colors for every entity or use what we call feature-image layers as inputs. These are simply a volume of images and each image has the same dimensions as your grid map and is everywhere 0 except the location of an entity which will have a value of 1. This is in other words a one-hot encoding but in the spatial dimensions of your map.

Actions seem fine to me and your reward function is worth giving a try but I wouldn't penalize that heavily (maybe -0.1 instead of -0.75). The issue will rise initially when your agent explores. If it is heavily penalized it will try to maintain its reward and deliberately crash.

Do not get frustrated if initially it doesn't learn. Designing a proper reward function is quite a task besides the proper feature representation (I suggest images).

  • $\begingroup$ Can u link me to article about the feature -image layers with implementation example, that would be really helpful. $\endgroup$ Commented Mar 24, 2020 at 8:44
  • $\begingroup$ Here it is: arxiv.org/pdf/1708.04782.pdf, section 3.2. $\endgroup$ Commented Mar 24, 2020 at 16:25
  • $\begingroup$ If my answer was helpful could you consider voting up or checking it as the correct answer so others can benefit from it as well? $\endgroup$ Commented Mar 26, 2020 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.