CSEN2031: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
Module IV Lecture Notes – PART- I
[Knowledge And Reasoning]
Syllabus
Knowledge Representation: Logical Agents: Knowledge based agents, the wumpus world, and logic.
Propositional Logic: A very simple logic, reasoning patterns in propositional logic.
.
Concepts
Knowledge-based agents
Example: The wumpus world
Logic in general—models and entailment
Propositional (Boolean) logic
Equivalence, validity, satisfiability
Inference rules and theorem proving
– forwardchaining
– backward chaining
– resolution
First Order Logic
Knowledge Based Agents
A knowledge-based agent needs a KB and an inference mechanism. It operates by storing sentences
in its knowledge base, inferring new sentences with the inference mechanism, and using them to
deduce which actions to take The interpretation of a sentence is the fact to which it refers.
Knowledge Bases:
domain−independent
Inference engine algorithms
domain−specific content
Knowledge base
¾ B.Tech , Department of Computer Science and Engineering, GU Page 2 of 2
CSEN2031: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
Knowledge base = set of sentences in a formal language
Declarative approach to building an agent (or other system):
Tell it what it needs to know
Then it can Ask itself what to do—answers should follow from the KB Agents can be viewed at
the knowledge level i.e., what they know, regardless of how implemented or at the implementation
level i.e.,data structures in KB and algorithms that manipulate them.
The Wumpus World:
A variety of "worlds" are being used as examples for Knowledge Representation, Reasoning, and
Planning. Among them the Vacuum World, the Block World, and the Wumpus World.
The Wumpus World was introduced by Genesereth, and is discussed in Russell-Norvig. The Wumpus
World is a simple world (as is the Block World) for which to represent knowledge and to reason.
It is a cave with a number of rooms, represented as a 4x4 square.
Rules of the Wumpus World
The neighborhood of a node consists of the four squares north, south, east, west of the given square.
In a square the agent gets a vector of percepts, with components
Stench, Breeze, Glitter, Bump, Scream
For example [Stench, None, Glitter, None, None]
¾ B.Tech , Department of Computer Science and Engineering, GU Page 3 of 3
CSEN2031: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
Stench is perceived at a square iff the wumpus is at this square or in its neighborhood.
Breeze is perceived at a square iff a pit is in the neighborhood of this square.
Glitter is perceived at a square iff gold is in this square
Bump is perceived at a square iff the agent goes Forward into a wall
Scream is perceived at a square iff the wumpus is killed anywhere in the cave
An agent can do the following actions (one at a time):
Turn(Right), Turn(Left), Forward, Shoot, Grab, Release, Climb
The agent can go Forward in the direction it is currently facing, or Turn Right, or Turn Left.
Going Forward into a wall will generate a Bump percept.
The agent has a single arrow that it can Shoot. It will go straight in the direction faced by the
agent until it hits (and kills) the wumpus, or hits (and is absorbed by) a wall.
The agent can Grab a portable object at the current square or it can Release an object that it is
holding.
The agent can Climb out of the cave if at the Start square. The Start square is (1,1) and
initially the agent is facing east. The agent dies if it is in the same square as the wumpus.
The objective of the game is to kill the wumpus, to pick up the gold, and to climb out with it.
Representing our Knowledge about the Wumpus World
Percept(x,y)
where x must be a percept vector and y must be a situation. It means that at situation y the
agent perceives x. For convenience we introduce the following definitions:
Percept([Stench,y,z,w,v],t) = > Stench(t)
Percept([x,Breeze,z,w,v],t) = > Breeze(t)
Percept([x,y,Glitter,w,v],t) = > AtGold(t)
Holding(x,y)
where x is an object and y is a situation. It means that the agent is holding the object x in
situation y.
Action(x,y)
where x must be an action (i.e. Turn(Right), Turn(Left), Forward, ..) and y must be a situation.
It means that at situation y the agent takes action x.
¾ B.Tech , Department of Computer Science and Engineering, GU Page 4 of 4
CSEN2031: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
At(x,y,z)
where x is an object, y is a Location, i.e. a pair [u,v] with u and v in {1,2,3,4}, and z is a
situation. It means that the agent x in situation z is at location y.
Present(x,s)
means that object x is in the current room in the situation s.
Result(x,y)
It means that the result of applying action x to the situation y is the situation Result(x,y).
Notethat Result(x,y) is a term, not a statement.
For example we can say
Result(Forward, S0) = S1
Result(Turn(Right),S1) = S2
These definitions could be made more general. Since in the Wumpus World there is a single agent,
there is no reason for us to make predicates and functions relative to a specific agent. In other
"worlds" we should change things appropriately.
Wumpus World : PEAS Description
Performance measure
Gold +1000, death−1000
−1perstep,−10forusingthearrow
Environment
Squares adjacent to wumpus are smelly Squares adjacent to pit are breezy Glitter iff gold
is in the same square
Shooting kills wumpus if youarefacing it Shooting uses up the only arrow Grabbingpicks
upgoldifinsamesquare Releasingdropsthegoldinsamesquare
Actuators
Left turn, Right turn, Forward, Grab, Release, Shoot
Sensors
Breeze, Glitter, Smell
¾ B.Tech , Department of Computer Science and Engineering, GU Page 5 of 5
CSEN2031: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
Wumpus World Characterization
Observable: NO – Only Local Perception
Deterministic: Yes – Outcomes Exactly Specified
Episodic: No – Sequential at the level of actions
Static: No – Wumpus and Pits Do not Move
Discrete: Yes
Single agent: Yes – Wumpus is essentially a Natural Feature
Exploring a Wumpus World
¾ B.Tech , Department of Computer Science and Engineering, GU Page 6 of 6
CSEN2031: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
OK
OK OK
A
S OK
A
OK OK
A
¾ B.Tech , Department of Computer Science and Engineering, GU Page 7 of 7
CSEN2031: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
W?
S OK W?
A
OK OK
A
¾ B.Tech , Department of Computer Science and Engineering, GU Page 8 of 8
CSEN2031: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
W?
S OK W?
A
OK B OK
A A
¾ B.Tech , Department of Computer Science and Engineering, GU Page 9 of 9
CSEN2031: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
W?
W
S OK W?
A OK
OK B OK
A A
P
¾ B.Tech , Department of Computer Science and Engineering, GU Page 10 of 10
CSEN2031: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
W?
W
S O W?
O
A
O B O
A A
P
¾ B.Tech , Department of Computer Science and Engineering, GU Page 11 of 11
19ECS 302: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
W? OK
W
S O W? OK
O
A K
O B O
A A
P
P
?
B O P
? Breeze in (1,2) and(2,1)
A ⇒ no safe actions
P Assumingpitsuniformlydistributed,
(2,2) has pit w/ prob 0.86, vs. 0.31
OK O
A A
P
?
Smell in (1,1)
⇒ cannot move
Can use a strategy ofcoercion:
¾ B.Tech , DS
epartment of Computer Science and Engineering, GU Page 12 of 34
A
19ECS 302: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
shoot straight ahead
wumpuswasthere ⇒dead⇒safe
wumpuswasn’t there ⇒ safe
Logic in general
Logics are formal languages for representing information such that conclusions can be drawn
Syntaxdefinesthesentencesinthelanguage
Semantics define the ―meaning‖ ofsentences;
i.e., define truth of a sentence in a world
E.g., the language of arithmetic
x +2 ≥ y is a sentence; x2+ y >is not a sentence
x+2≥y istrueiffthenumberx+2 isnolessthanthenumbery x + 2 ≥ y is true in a world where x =7, y =1
x + 2 ≥ y is false in a world where x = 0, y = 6
Entailment
Entailment means that one thing follows fromanother:
KB |= α
A knowledge base KB entails a sentenceα if and only if α is true in all worlds where KB is
true.
E.g.,theKBcontaining―There’sapitahead‖and―There’sgoldtotheleft‖ entails ―Either there’s a pit
ahead or gold to the left‖
E.g., x + y = 4 entails 4 = x + y
Entailment is a relationship between sentences (i.e.,syntax) that is based on semantics
Models
Logicians =typically think in terms of models, whichareformally structured worlds with respect to
which truth can be evaluated
We say m is a model of a sentence α if α is true in m M(α) is the set of all models of α
Then KB |=α if and only if M (KB) ⊆ M(α)
E.g. KB = {there’s a pit ahead, there’s gold to the left }
α = there’s gold to the left
¾ B.Tech , Department of Computer Science and Engineering, GU Page 13 of 13
19ECS 302: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
x
x x x
x
x
x xx
M( ) x x xx
x
x x
x
x x x
x x x
x x
x x x x
xx x xx
x x x
xx x
x
x M(KB) x x
x
x
Entailment in the Wumpus World
Situation after detecting nothing in[1,1], moving right, breeze in [2,1]
? ? B
A
Consider possible models for ?s
A
?
assuming only pits
3Booleanchoices ⇒ 8 possible models
Wumpus Models
¾ B.Tech , Department of Computer Science and Engineering, GU Page 14 of 14
19ECS 302: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
Breeze Breeze
Breeze Breeze Breeze
Breeze Breeze
Breeze
2
2 PIT
1
Breeze
1 PIT Breeze
1 2 3
1 2 3
KB
2
2 PIT PIT
2
1
Breeze
1 Breeze
Breeze PIT
1
1 2 3
1 2 3
1 2 3
2
2 PIT PIT PIT
1
Breeze
1 PIT Breeze
2 PIT PIT
1 2 3
1 2 3
Breeze
1 PIT
¾ B.Tech , Department of Computer Science and Engineering, GU Page 15 of 15
19ECS 302: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
KB = wumpus-world rules + observations
2 PIT
2
Breeze
1
Breeze
1 PIT
1 2 3
1 2 3
KB
1
2
2 PIT PIT
2
1
Breeze
1 Breeze
Breeze PIT
1
1 2 3
1 2 3
1 2 3
2
2 PIT PIT PIT
1
Breeze
1 PIT Breeze
2 PIT PIT
1 2 3
1 2 3
Breeze
1 PIT
KB = wumpus-world rules + observations
α1 = ―[1,2] is safe‖, KB |=α1, proved by model checking
¾ B.Tech , Department of Computer Science and Engineering, GU Page 16 of 16
19ECS 302: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
2 PIT
2
Breeze
1
Breeze
1 PIT
2
1 2 3
1 2 3
KB
2 PIT
2 PIT
2
Breeze
Breeze
1 PIT
1
Breeze
1
1 2 3
1 2 3
1 2 3
2 PIT PIT
2 PIT
Breeze
1
Breeze
1 PIT
2 PIT PIT
1 2 3
1 2 3
Breeze
1 PIT
KB = wumpus-world rules + observations
α2 = ―[2,2] is safe‖, KB |= α2
Inference
KB ⊢i α = sentence α can be derived from KB by procedure i
Consequences of KB are a hay stack;α is a needle.
Entailment=needle in hay stack;
inference=finding it
Soundness: i is sound if
whenever KB ⊢i α, it is also true that KB |= α
Completeness: i is complete if
whenever KB |= α, it is also true that KB ⊢i α
Preview:wewilldefine a logic(first-orderlogic)whichisexpressiveenough tosayalmostanythingof interest,
andforwhichthereexistsasoundand complete inference procedure.
¾ B.Tech , Department of Computer Science and Engineering, GU Page 17 of 17
19ECS 302: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
Thatis, theprocedurewill answer anyquestionwhoseanswerfollowsfrom what is known by the KB.
Propositional logic: Syntax
Propositional logic is the simplest logic—illustrates basic ideas The proposition symbols P1,
P2 etc are sentences
If S is a sentence, ¬S is a sentence(negation)
IfS1 andS2 aresentences,S1∧S2 isasentence(conjunction)
IfS1andS2aresentences,S1∨S2isasentence(disjunction)
IfS1andS2aresentences,S1⇒S2isasentence(implication)
IfS1andS2aresentences,S1⇔S2isasentence(biconditional)
Propositional logic: Semantics
Each model specifies true/false for each proposition symbol
P1,2 P2,2 P3,1
TRUE TRUE FALSE
(With these symbols, 8 possible models, can be enumerated automatically.) Rules for
evaluating truth with respect to a model m:
Truth Tables for Connectives
¾ B.Tech , Department of Computer Science and Engineering, GU Page 18 of 18
19ECS 302: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
Wumpus World Sentences
Let Pi,j be true if there is a pit in [i, j]. LetBi,j be true if there is a breezein[i,j].
¬P1,1
¬B1,1
B2,1
How do we encode ―pits cause breezes in adjacent squares‖?
B1,1 ⇔ (P1,2 ∨ P2,1)
B2,1 ⇔ (P1,1 ∨ P2,2 ∨P3,1)
In other words, ―a square is breezy if and only if there is an adjacent pit‖
Truth Tables for Inference
¾ B.Tech , Department of Computer Science and Engineering, GU Page 19 of 19
19ECS 302: ARTIFICIAL INTELLIGENCE LECTURE NOTES | MODULE IV | PART I
Enumerate rows (different assignments to symbols), if KB is true in row, check that α is too
Inference by Enumeration
Depth-first enumeration of all models is sound and complete
¾ B.Tech , Department of Computer Science and Engineering, GU Page 20 of 20
