DS161 Introduction to Data Science & Artificial Intelligence
Self-Study 5
Knowledge Representation in the Real World
Krishnendu Ghosh
Wumpus World
The wumpus world is a cave consisting of rooms connected by passageways. Lurking somewhere in the cave is the terrible wumpus, a beast that eats anyone who enters its room. The wumpus can be shot by an agent, but the agent has only one arrow. Some rooms contain bottomless pits that will trap anyone who wanders into these rooms (except for the wumpus, which is too big to fall in). The only mitigating feature of this bleak environment is the possibility of finding a heap of gold.
Wumpus World
Performance measure: +1000 for climbing out of the cave with the gold, –1000 for falling into a pit or being eaten by the wumpus, –1 for each action taken and –10 for using up the arrow. The game ends either when the agent dies or when the agent climbs out of the cave.
Environment: A 4×4 grid of rooms. The agent always starts in the square labeled [1,1], facing to the right. The locations of the gold and the wumpus are chosen randomly, with a uniform distribution, from the squares other than the start square. In addition, each square other than the start can be a pit, with probability 0.2.
Wumpus World
Actuators: The agent can move Forward, TurnLeft by 90◦, or TurnRight by 90◦. The agent dies a miserable death if it enters a square containing a pit or a live wumpus. (It is safe, albeit smelly, to enter a square with a dead wumpus.) If an agent tries to move forward and bumps into a wall, then the agent does not move. The action Grab can be used to pick up the gold if it is in the same square as the agent. The action Shoot can be used to fire an arrow in a straight line in the direction the agent is facing. The arrow continues until it either hits (and hence kills) the wumpus or hits a wall. The agent has only one arrow, so only the first Shoot action has any effect. Finally, the action Climb can be used to climb out of the cave, but only from square [1,1].
Wumpus World
Sensors: The agent has five sensors, each of which gives a single bit of information:
Wumpus World
We can characterize the wumpus environment along the various dimensions. Clearly, it is discrete, static, and single-agent. It is sequential, because rewards may come only after many actions are taken. It is partially observable, because some aspects of the state are not directly perceivable.
The percepts will be given to the agent program in the form of a list of five symbols; for example, if there is a stench and a breeze, but no glitter, bump, or scream, the agent program will get [Stench, Breeze, None, None, None].
Wumpus World
The agent’s initial knowledge base contains the rules of the environment, as described previously; in particular, it knows that it is in [1,1] and that [1,1] is a safe square
The first percept is [None, None, None, None, None], from which the agent can conclude that its neighboring squares, [1,2] and [2,1], are free of dangers—they are OK.
Wumpus World
Wumpus World
A Simple Knowledge Base: Wumpus World
For now, we need the following symbols for each [x, y] location:
Px,y is true if there is a pit in [x, y].
Wx,y is true if there is a wumpus in [x, y], dead or alive.
Bx,y is true if the agent perceives a breeze in [x, y].
Sx,y is true if the agent perceives a stench in [x, y].
A Simple Knowledge Base: Wumpus World
The sentences we write will suffice to derive ¬P1,2 (there is no pit in [1,2]). We label each sentence Ri so that we can refer to them:
• There is no pit in [1,1]:
R1 : ¬P1,1
A square is breezy if and only if there is a pit in a neighboring square. This has to be stated for each square; for now, we include just the relevant squares:
R2 : B1,1 ⇔ (P1,2 ∨ P2,1)
R3 : B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1)
A Simple Knowledge Base: Wumpus World
The preceding sentences are true in all wumpus worlds. Now we include the breeze percepts for the first two squares visited in the specific world the agent is in, leading up to the situation in Figure 7.3(b).
R4 : ¬B1,1
R5 : B2,1
A Simple Inference Procedure: Wumpus World
Our goal now is to decide whether KB |= α for some sentence α.
For example, is ¬P1,2 entailed by our KB?
Our first algorithm for inference is a model-checking approach that is a direct implementation of the definition of entailment: enumerate the models, and check that α is true in every model in which KB is true.
A Simple Inference Procedure: Wumpus World