Chapter – 7 Logical Agents

7.1 KNOWLEDGE-BASED AGENTS

• The core of a knowledge-based agent is its knowledge base (KB), a collection of
sentences that represent assertions about the world.
• These sentences are written in a knowledge representation language and are
sometimes referred to as axioms if taken as given, rather than derived from other
sentences.
• A knowledge base must allow new sentences to be added (using the TELL
operation) and permit queries about existing knowledge (using the ASK
operation).
• Both operations may require inference—the process of deriving new knowledge
from existing information.
• The answer to any query should logically follow from what has already been told
to the knowledge base, ensuring consistency in reasoning.
• Each time the agent program runs, it performs three steps:
 It TELLs the knowledge base what it perceives.
 It ASKs the knowledge base which action to take, which may involve reasoning
about the current state, potential actions, and their outcomes.
 It TELLs the knowledge base the action chosen, and then the agent executes it
• Three key functions handle the interaction between the agent’s sensors,
actuators, and core reasoning system:
 MAKE-PERCEPT-SENTENCE creates a sentence about the agent's current
perception.
 MAKE-ACTION-QUERY generates a question about the next action.
 MAKE-ACTION-SENTENCE records the action taken.
• A knowledge-based agent can be created by TELLing it relevant information, starting
from an empty knowledge base and adding sentences until it knows how to function
in its environment. This is known as the declarative approach, where knowledge is
incrementally built up. In contrast, the procedural approach encodes specific
behaviors directly in the program code
7.2 THE WUMPUS WORLD
• Environment Overview: The Wumpus World is a cave environment with rooms
connected by passageways
• The Wumpus: A dangerous beast lurks in one of the rooms. It eats anyone who
enters its room but can be killed if the agent uses its one arrow.
• Hazards: Some rooms contain bottomless pits that trap anyone who enters,
except for the Wumpus, which is too large to fall in
• Reward: There is a possibility of finding a heap of gold in one of the rooms
• Purpose: Although simple by modern game standards, the Wumpus World
demonstrates key concepts of intelligent behavior for knowledge-based agents.
Wumpus world PEAS Description
• 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. Inaddition, each square other than the start can be a pit, with
probability 0.2.
• 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].
• Sensors: The agent has five sensors, each of which gives a single bit of information:
– In the square containing the wumpus and in the directly (not diagonally) adjacent
squares, the agent will perceive a Stench.
– In the squares directly adjacent to a pit, the agent will perceive a Breeze.
– In the square where the gold is, the agent will perceive a Glitter.
– When an agent walks into a wall, it will perceive a Bump.
– When the wumpus is killed, it emits a woeful Scream that can be perceived anywhere in the cave.
• 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].
• We can characterize the wumpus environment along the various dimensions
Clearly, it is discrete, static, and single-agent (The wumpus doesn’t move,
fortunately.)
• 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 agent’s location, the wumpus’s state of health, and the
availability of an arrow
• As for the locations of the pits and the wumpus: we could treat them as
unobserved parts of the state that happen to be immutable—in which case, the
transition model for the environment is completely known; or we could say that
the transition model itself is unknown because the agent doesn’t know which
Forward actions are fatal—in which case, discovering the locations of pits and
wumpus completes the agent’s knowledge of the transition model.
• For an agent in the environment, the main challenge is its initial
ignorance of the configurationof the environment; overcoming this
ignorance seems to require logical reasoning.
• In most instances of the wumpus world, it is possible for the agent to
retrieve the gold safely.
• Occasionally, the agent must choose between going home empty-
handed and risking death to find the gold.
• About 21% of the environments are utterly unfair, because the gold is
in a pit or surrounded by pits.
 1. The initial situation, after percept [none,
none, none, none, none]
2. 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; we
denote that with an “A” and “OK,”
respectively, in square [1,1].
3. 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

7.3(a) The initial situation,

after percept [None, None, None, None,
None].
 4. A cautious agent will move only into a
square that it knows to be OK. Let us
suppose the agent decides to move forward
to [2,1]. The agent perceives a breeze
(denoted by “B”) in [2,1], so there must be
a pit in a neighboring square.
5. The pit cannot be in [1,1], by the rules of
the game, so there must be a pit in [2,2] or
[3,1] or both.
6. The notation “P?” in Figure 7.3(b)
indicates a possible pit in those squares. At
this point, there is only one known square
that is OK and that has not yet been visited.
7.3(b) After one move, with
percept
So the prudent agent will turn around, go
[None, Breeze, None, None, back to [1,1], and then proceed to [1,2].
None].
 7. The agent perceives a stench in [1,2], resulting
in the state of knowledge shown in Figure 7.4(a).
8. The stench in [1,2] means that there must be a
wumpus nearby.
9. But the wumpus cannot be in [1,1], by the
rules of the game, and it cannot be in [2,2] (or
the agent would have detected a stench when it
was in [2,1]).
10. Therefore, the agent can infer that the
wumpus is in [1,3].

7.4(a) After the third move, with

percept
[Stench, None, None, None, None].
 11. The notation W! indicates this inference.
12. Moreover, the lack of a breeze in [1,2] implies that
there is no pit in [2,2].
13. Yet the agent has already inferred that there must be a
pit in either [2,2] or [3,1], so this means it must be in [3,1].
14. This is a fairly difficult inference, because it combines
knowledge gained at different times in different places and
relies on the lack of a percept to make one crucial step.
15. The agent has now proved to itself that there is neither
a pit nor a wumpus in [2,2], so it is OK to move there.
16. We do not show the agent’s state of knowledge at
[2,2]; we just assume that the agent turns and moves to
[2,3], giving us Figure 7.4(b). In [2,3], the agent detects a
glitter, so it should grab the gold and then return home.
7.4(b) After the fifth move, with
percept
[Stench, Breeze,Glitter, None,
None].
Note that in each case for which the agent draws a
conclusion from the available information, that conclusion is
guaranteed to be correct if the available information is
correct
7.3 LOGIC
Overview of Logical Representation and Reasoning
Fundamental concepts are independent of specific logic forms.
Uses arithmetic as an example to explain basic concepts
Syntax
Defines the structure and well-formedness of sentences.
Example: “x + y = 4” is syntactically correct; “x4y+=” is not
Semantics
Defines the meaning of sentences and their truth in each possible world.
Example: "x + y = 4" is true when x = 2 and y = 2; false when x = 1 and y = 1
Possible Worlds and Models
Possible worlds represent real or hypothetical scenarios.
Models are mathematical abstractions that assign truth values to sentences.
Example: In a model where x = 2 and y = 2, "x + y = 4" is true
Satisfaction and Model Notation
A model satisfies a sentence if the sentence is true within that model.
Notation: M(α) represents all models where sentence α is true
Logical Entailment
Describes when a sentence logically follows from another.
Notation: α |= β
to mean that the sentence α entails the sentence β. The formal definition of
entailment is this: α |= β if and only if, in every model in which α is true, β is
also true. Using the notation just introduced, we can write α |= β if and only
if M(α) ⊆ M(β) (entailment)
PROPOSITIONAL LOGIC: A VERY SIMPLE LOGIC
• Propositional logic is a branch of logic that deals with propositions, which are
statements that can be either true or false but not both. It is a formal system that uses
simple, declarative statements (propositions) and logical connectives (such as AND, OR,
NOT, and IMPLIES) to build more complex statements
• Entailment—the relation between a sentence and another sentence that follows from it
• The syntax of propositional logic defines the allowable sentences
• Atomic Sentences in Propositional Logic : Definition: Atomic sentences are the simplest
sentences in propositional logic, consisting of a single proposition symbol
• Proposition Symbols: These symbols represent statements that can be true or false, like
P, Q, R, or W1,[Link] start with an uppercase letter and may include other letters or
subscripts (e.g., W1,3).
• Names are arbitrary but often have mnemonic value (e.g., W1,3 could mean "the
wumpus is in [1,3]"). Symbols like W1,3 are atomic—subparts (like W, 1, 3) have no
individual meaning
• Complex Sentences in Propositional Logic
• Definition: Built from simpler sentences using parentheses and logical
connectives.
• Common Connectives: Five main connectives are used in propositional logic
to create complex statements.
• There are five connectives in common use:
￢ (not). A sentence such as ￢ W1,3 is called the negation of W1,3. A
literal is either an L atomic sentence (a positive literal) or a negated
atomic sentence (a negative literal).
∧ (and). A sentence whose main connective is ∧, such as W1,3 ∧
P3,1, is called a conjunction; its parts are the conjuncts. (The ∧ looks
like an “A” for “And.”)
• ∨ (or). A sentence using ∨, such as (W1,3∧P3,1)∨W2,2, is a disjunction of the
disjuncts (W1,3 ∧ P3,1) and W2,2. (Historically, the ∨ comes from the Latin “vel,”
which means “or.” For most people, it is easier to remember ∨ as an upside-down
∧.)
• ⇒ (implies). A sentence such as (W1,3∧P3,1) ⇒ ￢ W2,2 is called an implication
(or conditional). Its premise or antecedent is (W1,3 ∧P3,1), and its conclusion or
consequent is ￢ W2,2. Implications are also known as rules or if–then
statements. The implication symbol is sometimes written in other books as ⊃ or
→.
• ⇔ (if and only if). The sentence W1,3 ⇔ ￢ W2,2 is a biconditional. Some other
books write this as ≡.
Semantics
• The semantics defines the rules for determining the truth of a
sentence with respect to a particular model.
• In propositional logic, a model simply fixes the truth table – true or
false- for every propositional symbol
• For example if the sentences in the knowledge base make use of the
proposition symbols P1,2, P2,2, and P3,1, then one possible model is
m1 = {P1,2 =false, P2,2 =false, P3,1 =true} .
• With three proposition symbols, there are 2^3 =8 possible models
Rules for atomic sentences

• True is true in every model and False is false in every model.

• The truth value of every other proposition symbol must be specified
directly in the model.
For example, in the model m1 given earlier, P1,2 is false.
m1 = {P1,2 =false, P2,2 =false, P3,1 =true} .
For complex sentences, we have five rules
• ￢ P is true iff P is false in m.
• P ∧ Q is true iff both P and Q are true in m.
• P ∨ Q is true iff either P or Q is true in m.
• P ⇒ Q is true unless P is true and Q is false in m.
• P ⇔ Q is true iff P and Q are both true or both false in m.
A simple knowledge base
• 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].
• 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) .
• 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,
R4 : ￢ B1,1 .
R5 : B2,1 .
A simple inference procedure

• The goal is to determine if a knowledge base (KB) logically entails a

specific sentence α. In this example, we want to see if ¬P1,2 (no pit at
location [1,2]) follows from KB
• The first method for inference used here is model checking, where all
possible models (assignments of true/false values to each proposition)
are enumerated to check if α holds in every model where KB is true.
• In the wumpus-world example, there are seven relevant propositions,
resulting in 128 possible models
• Only three of these models make KB true, and in each of these, ¬P1,2
holds, confirming there is no pit at [1,2]. However, for P2,2, it’s true in
two models and false in one, so we can't conclude whether there’s a
pit at [2,2].