1
$\begingroup$

I'm trying to use Q-learning in order to solve Wumpus world environment.

Wumpus world is a toy problem on 4x4 gridworld. The agent starts in entry position of the cave, looks for gold (agent can sense that he is on the gold field), then he has to pick it up and leave cave in the entry position. Some fields are safe, other contain pit or wumpus (monster). If agent move to the pit or wumpus field he dies. The fields next to wumpus or pit (not diagonally!) have properties that agent can sense - stench (wumpus), breeze (pit). Agent achieve positive reward if he leaves cave with gold and negative if he dies. Action space: turn right/left, move forward, shoot arrow (if shot in good direction it can kill wumpus, only 1 available), pick up gold, leave cave. There: https://www.javatpoint.com/the-wumpus-world-in-artificial-intelligence you can find more detailed description of environment.

It is easy to solve this problem if the gridworld is constant. I have a huge problem to even start thinking about it if gridworld is random in every learning episode (random fields and random size) and also random in testing. How should I define it (especially state space)? How should I create q table? I'm using Python.

Thank you in advance for any help.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

From your linked description of the game, we can see it has a key property when used normally in AI teaching:

  • Partially observable: The Wumpus world is partially observable because the agent can only perceive the close environment such as an adjacent room.

This makes sense, the problem of avoiding hazards would be trivial if the full map was revealed to the agent. The problem is also not about learning a specific map.

You could use the agent's perception to construct a simple state table based on current observations:

  • Current location
  • Current facing
  • Boolean flags for stench, breeze, glitter, bump, scream

This would be relatively easy to build into a Q table, and might have some success. However, it would likely perform a lot worse than the propositional logic and planning suggested suggested at https://www.javatpoint.com/the-wumpus-world-in-artificial-intelligence for two reasons:

  • Agent will not take account of knowledge specific to the current map that it has gathered. This is critical, because the stench and breeze sensors only tell you that at least one of the adjacent rooms has a hazard. In theory you know that this will not be any of the rooms that the agent has already visited, but a simple state representation based on current observations will not capture this.

  • Agent will not plan using the deterministic rules of the game that you know and could code for.

There are a few different approaches you could take to improve on these issues. Sticking with Q learning and trying to solve this by improving the state representation, you could look at the suggested knowledge-building structure from the java T point site, and replicate something like it as input features:

  • Current facing
  • Whether or not the last move forward resulted in a bump
  • Whether or not there has been a scream
  • For each allowed room, a binary flag set to true if the room has been visited by the agent
  • For each allowed room, a set of binary variables covering the three observations that are about the room: stench, breeze, glitter
  • Either the current location separately, or another binary variable added to each grid square set to true for the one room that the agent is in

When multiplied by 16 to cover each room, you will end up with ~84 binary flags. Although many combinations will not be possible, this is still going to be far too large a state space to use with a Q table. You would probably use a simple neural network and DQN agent to solve this problem using Q learning.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 1) "For each allowed room" - do you mean for each room of the gridworld - 16 in 4x4 grid ? 2) So in the 4x4 grid world there will be: 16 (4x4 - x * y) * 4 (agent's direction) * 2 (if last move forward was bump) * 2 (if scream) * 2 (if visited by agent) * (2 * 2 * 2) (stench, breeze, glitter) * 16 (agent's location) = 65536 ? 3) For each allowed room, a binary flag set to true if the room has been visited by the agent - why do we use this information ? $\endgroup$
    – Geperd
    Mar 14, 2021 at 16:33
  • 1
    $\begingroup$ @Geperd Your state space caclulation is way off, because it is not tracking separate flgas for each room. The state space is around $2^{84}$. We need to use this information because figuring out logical positions of the pits and wumpus is part of the problem, and cannot be done using current observation (this is why I critique the simple observation "Agent will not take account of knowledge specific to the current map that it has gathered."). You need a structure within the agent that summarises information discovered so far - my suggestion at the end of the answer is one way to do this. $\endgroup$
    – Neil Slater
    Mar 14, 2021 at 17:34
  • $\begingroup$ Sorry to ask you again and again but i can't see it yet. So the state space is: $2^4$ (direction) * $2^2$ (bump) * $2^2$ (scream) * $2^{16} * 2^2$ (each room if visited) * $2^{16} * 2^2 * 2^{16} * 2^2 * 2^{16} * 2^2$ (for each room stench, breeze, glitter) * $2^{16} * 2^2$ (if agent is in room) = $2^{98}$ ??? If my calculations are wrong can you please write it in comment in similar fashion as above? $\endgroup$
    – Geperd
    Mar 14, 2021 at 18:32
  • 1
    $\begingroup$ @Geperd You have some extra $2^2$ in there for most of the factors. For instance, a binary flag on each room for "stench" is $2^{16}$, not $2^{16} \times 2^2$. There is some flexibility about how you represent current location and direction, so you may not get exactly $2^{84}$. That is not too important, but you should expect to have something closer to it than $2^{98}$ $\endgroup$
    – Neil Slater
    Mar 14, 2021 at 18:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .