Logical Agents

In this chapter we see how agents equipped with the ability to represent internally the state of the environment and reason about the effectiveness of possible actions using propositional logic, can construct plans that are guaranteed to achieve their goals. We start with the KB we developed in wumpus world and enhance it by introducing representations that avoid looking back at the whole percept history to make an inference about the state of the environment currently.

Enhancing the KB

We add a couple of sentences in the KB we had developed,focusing on axioms (facts or rules that evaluate to TRUE). When these axioms involve variables that they never change we call such variables atemporal. This is shown in the next table.

Sentence Description KB
R1 There is no pit in cel [1,1] ¬P1,1
R2 The cell [1,1] is breezy if and only if there is a pit in the neighboring cell. B1,1(P1,2P2,1)
R3 The cell [2,1] is breezy if and only if there is a pit in the neighboring cell. B2,1(P1,1P2,2P3,1)
R4 The cell [1,1] is stenchy if and only if there is a wumpus in the neighboring cell. S1,1(W1,2W2,1)
R5 There is only one wumpus in this world.
R51 There is at least one wumpus W1,1W1,2...W4,4
R52 There is at most one wumpus
R521 ¬W1,1¬W1,2
R522 ¬W1,1¬W1,3
R52N ¬W4,3¬W4,4

With respect to percepts and and in fact with everything in the world that is dynamic, we introduce the notion of time (t) and index all such variables accordingly. We do so to avoid the situation where we have conflicts in the KB where while in cell [1,2] we store in the KB Stench and in another instance e.g. in cell [2,2] we store ¬Stench. These type of variables are called some times called fluent but effectively these are the usual mutable state variables. Location as we have seen is a primary variable that is carried by the environment state. We can then define an associated fluent Lx,yt and store the following sentences in the KB.

Sentence Description KB
R6 if an agent is in cell [x,y] at t and perceives [Stench, Breeze, Glitter, Bump, Scream]=[None, Breeze, None, None, None] then the cell is a Breeze cell Lx,yt(BreezetBx,y)
R7 if an agent is in cell [x,y] at t and perceives [Stench, Breeze, Glitter, Bump, Scream]=[Stench, None, None, None, None] then the cell is a Stench cell Lx,yt(StenchtSx,y)

Similar to percepts, actions also are taken at specific times t. By convention, we first receive a percept at t, then take an action during the same time step t and then the environment transitions to another state at t+1. To specify the transition model that describes how the world changes we use effect axioms as follows:

Sentence Description KB
R8 if an agent is in cell [1,1] at t=0 and is FacingEast and decides to move Forward it will transition to L2,1 in the next time step L1,10FacingEast0Forward0(L2,11¬L1,11)

There lies a serious issue. There is a combinatorial explosion problem as we have to repeat sentences like the R8 for each of the possible T time steps into the future that include actions. For a single Forward action we need to consider 4xTxn2 possibilities, where 4 are the possible agent orientations and n2 is the number cells in the wumpus world! But there are more bad news. We need to also include in the KB was remains unchanged - this is a well known issue called the representation frame problem. It took its name from the video frame where most of the pixels stay unchanged (background) and only a few change (foreground). Imagine the bandwidth that we need to consume to transmit all video frame pixels. This is analogous to the KB - imagine the combinatorial explosion if we have to specify sentences for everything that stays the same at every time instant. As an example we will have to specify that the wumpus is alive at t+1 as it was at t, that the agent continues to have one arrow when it didn’t use it and a myriad other intuitively obvious axioms.