Probabilistic agent traversing a 4x4 grid world with joint probability distribution

Question

I’m trying to solve a probabilistic agent for a simple board game from the book A Modern Approach to AI, but am having some trouble with the basic math and mostly the full joint distribution, so I’m asking for some pointers.

The board is 4x4 squares There is 1 monster and 2 pits somewhere on the board The monster and pits give out a stench/breeze in its adjacent squares giving the agent clues if there are pits/monsters nearby

Rooms written as tuples of their coordinate on the grid: (x,y) from 1-4

For example:

Rooms (1, 1), (1, 2), (2, 1) is visited and we found breezes in rooms (1, 2) and (2, 1)

This tells me that there could be pits in either room adjacent to (1, 2) and (2, 1)

P is Probability of a pit This variable is uniformly distributed over the 4x4 grid (16 rooms) in the beginning so we get a probability of 0.2 that there is a Pit or a Monster per square

B is whether there is a breeze or stench in the visited rooms (which means the probability of it being a pit next to them is higher

The full joint distribution should then be P(P11, …, P44, B11, B12, B21)

The product rule gives us that

P(P11, …, P44, B11, B12, B21) =

P(B11, B12, B21 | P11, …, P44) P(P11, …, P44)

Product Rule on Full Joint Distribution

So far so good, but it is here that I can’t seem to take the next step.

The second term I have since its evenly distributed probability of 0.2 over the rooms. But for the first term there should be 1 if the rooms with breeze (B21 and B12) is adjacent to a pit/monster. But what are the numbers for B? And how do I get that?

The AIMA book states: “The first term is the conditional probability distribution of a breeze configuration, given a pit configuration; its values are 1 if the breezes are adjacent to the pits and 0 otherwise”

I’m been struggling with this for days and making no headway. Any help would be appreciated.

Answer 1

The Bxy values are indicators of whether or not a breeze was observed in a cell xy. They're formally defined as:

Bxy = 1 if and only if a breeze was observed in (x, y),
Bxy = 0 otherwise

So, in your example situation, we already know that
B11 = 0, B12 = 1, B21 = 1

Similarly, the variables P11, P12, ..., P44 are also binary variables, where Pxy = 1 if and only if there is a pit in the cell (x, y).

Now to have a look at that first term, which I believe is what your question is about, the thing that you didn't understand:

P(B11, B12, B21 | P11, ..., P44)

This is the conditional probability distribution of making the observations (B11, B12, B21) given that there are pits located in the cells (x, y) where Pxy = 1.

In the example situation, you are able to fill in the values for B11, B12, and B21. You know that B11 = 0, and B12 = B21 = 1 (because that's what was observed). You don't know in which locations the pits are, so you cannot directly fill in the Pxy values specifically for your situation. However, you can fill in those values for any arbitrary situation you can think of.

You can say "ok, let's assume there is only a pit in location (1, 3)". Then we have P13 = 1, and all other Pxy = 0. For such a specific situation, it is also possible to compute the probability of that specific situation happening (which would be 0, because you can't observe a breeze in (2, 1) if there's only a pit in (1, 3)).

If you repeat this for all possible situations you can imagine, you can combine the results to get more interesting answers, such as the probability of there being a pit in a certain location, given the observations you made. That's what the text further down is about though, and I believe that's no longer what your question was about.