Skip to main content
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.
SentenceDescriptionKB
R1R_1There is no pit in cel [1,1]¬P1,1\neg P_{1,1}
R2R_2The cell [1,1] is breezy if and only if there is a pit in the neighboring cell.B1,1⇔(P1,2∨P2,1)B_{1,1} ⇔ (P_{1,2} \lor P_{2,1})
R3R_3The cell [2,1] is breezy if and only if there is a pit in the neighboring cell.B2,1⇔(P1,1∨P2,2∨P3,1)B_{2,1} ⇔ (P_{1,1} \lor P_{2,2} \lor P_{3,1})
R4R_4The cell [1,1] is stenchy if and only if there is a wumpus in the neighboring cell.S1,1⇔(W1,2∨W2,1)S_{1,1} ⇔ (W_{1,2} \lor W_{2,1})
R5R_5There is only one wumpus in this world.
R5−1R_{5-1}There is at least one wumpusW1,1∨W1,2∨...∨W4,4W_{1,1} \lor W_{1,2} \lor ... \lor W_{4,4}
R5−2R_{5-2}There is at most one wumpus
R5−2−1R_{5-2-1}¬W1,1∨¬W1,2\neg W_{1,1} \lor \neg W_{1,2}
R5−2−2R_{5-2-2}¬W1,1∨¬W1,3\neg W_{1,1} \lor \neg W_{1,3}
……
R5−2−NR_{5-2-N}¬W4,3∨¬W4,4\neg W_{4,3} \lor \neg W_{4,4}
With respect to percepts and and in fact with everything in the world that is dynamic, we introduce the notion of time (tt) 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\mathtt{Stench} and in another instance e.g. in cell [2,2] we store ¬Stench\neg \mathtt{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,ytL_{x,y}^t and store the following sentences in the KB.
SentenceDescriptionKB
R6R_6if an agent is in cell [x,y] at tt and perceives [Stench, Breeze, Glitter, Bump, Scream]=[None, Breeze, None, None, None] then the cell is a Breeze cellLx,yt  ⟹  (Breezet⇔Bx,y)L_{x,y}^t \implies (\mathtt{Breeze}^t ⇔ B_{x,y})
R7R_7if an agent is in cell [x,y] at tt and perceives [Stench, Breeze, Glitter, Bump, Scream]=[Stench, None, None, None, None] then the cell is a Stench cellLx,yt  ⟹  (Stencht⇔Sx,y)L_{x,y}^t \implies (\mathtt{Stench}^t ⇔ S_{x,y})
Similar to percepts, actions also are taken at specific times tt. By convention, we first receive a percept at tt, then take an action during the same time step tt and then the environment transitions to another state at t+1t+1. To specify the transition model that describes how the world changes we use effect axioms as follows:
SentenceDescriptionKB
R8R_8if an agent is in cell [1,1] at t=0t=0 and is FacingEast\mathtt{FacingEast} and decides to move Forward\mathtt{Forward} it will transition to L2,1L_{2,1} in the next time stepL1,10∧FacingEast0∧Forward0  ⟹  (L2,11∧¬L1,11)L_{1,1}^0 \land \mathtt{FacingEast}^0 \land \mathtt{Forward}^0 \implies (L_{2,1}^1 \land \neg L_{1,1}^1)
There lies a serious issue. There is a combinatorial explosion problem as we have to repeat sentences like the R8R_8 for each of the possible TT time steps into the future that include actions. For a single Forward\mathtt{Forward} action we need to consider 4xTxn24 x T x n^2 possibilities, where 4 are the possible agent orientations and n2n^2 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+1t+1 as it was at tt, that the agent continues to have one arrow when it didn’t use it and a myriad other intuitively obvious axioms.
Edit this page on GitHub or file an issue.
Connect these docs to Claude, VSCode, and more via MCP for real-time answers.