Unit 3

Lecture Notes on Knowledge-Based Agents and Logical

Reasoning
1. Knowledge-Based Agents
1.1 Definition
A knowledge-based agent is an intelligent agent that
makes decisions using a knowledge base (KB) and an
inference mechanism. It perceives the environment,
updates its knowledge, and derives new facts using
logical reasoning.
1.2 Components of a Knowledge-Based Agent
1. Knowledge Base (KB): A repository of facts and
rules about the world, typically represented in logic
(propositional or first-order logic).
2. Inference Engine: Mechanism that derives new facts
from known facts using logical rules and inference
techniques such as resolution and chaining.
3. Perception: Sensors collect information from the
environment, which updates the knowledge base.
4. Action Selection: Based on the knowledge and
inference, the agent decides on the best action to
take.
5. Execution: The chosen action is carried out by
actuators, affecting the environment.
1.3 Characteristics of Knowledge-Based Agents
 Explicit Knowledge Representation: Facts and rules
are stored in a structured format.
 Reasoning Ability: The agent applies logical
inference to make decisions.
 Dynamic Updates: The knowledge base is
continuously updated with new perceptions.
  Goal-Oriented Behaviour: The agent makes
decisions to achieve predefined objectives.
2. Wumpus WorldNet
2.1 Description
The Wumpus World is a benchmark problem in AI,
representing a simple yet challenging environment
where an agent must navigate a grid while avoiding
hazards like pits and the Wumpus monster to find gold
and exit safely.
2.2 Features
 Grid-Based Environment: Typically, a 4×4 or larger
grid where the agent moves between cells.
 Percept’s:
o Stench: Detects the Wumpus in adjacent cells.
o Breeze: Indicates a pit in neighbouring cells.
o Glitter: Signifies gold in the current cell.
o Bump: Occurs when the agent hits a wall.
o Scream: Heard if the Wumpus dies after being
shot.
 Actions:
o Move Forward: Advances to the next cell.
o Turn Left/Right: Changes direction.
o Grab: Picks up the gold.
o Shoot: Uses an arrow to kill the Wumpus.
o Climb: Exits the cave (used at the starting
position).
2.3 Logical Representation in Wumpus World
Knowledge is represented in propositional logic to make
inferences about safe moves:
  If there is a stench at (x, y), then at least one
neighbouring cell contains the Wumpus.
o Stench(x,y)→Wumpus(x+1,y)∨Wumpus(x−1,y)∨
Wumpus(x,y+1)∨Wumpus(x,y−1)Stench(x,y) \
right arrow Wumpus(x+1,y) \vee Wumpus(x-
1,y) \vee Wumpus(x,y+1) \vee Wumpus(x,y-1)
 If there is a breeze at (x, y), then at least one
neighbouring cell has a pit.
o Breeze(x,y)→Pit(x+1,y)∨Pit(x−1,y)∨Pit(x,y+1)∨
Pit(x,y−1)Breeze(x,y) \right arrow Pit(x+1,y) \
vee Pit(x-1,y) \vee Pit(x,y+1) \vee Pit(x,y-1)
3. Propositional Logic
3.1 Syntax
 Atomic Propositions: Statements that can be true or
false (e.g., "P1,2" means "there is a pit in (1,2)").
 Logical Connectives:
o AND (∧): True if both operands are true.
o OR (∨): True if at least one operand is true.
o NOT (¬): Negates the truth value.
o IMPLICATION (→): If the first statement is true,
the second must also be true.
o BICONDITIONAL (↔): True if both statements
have the same truth value.
 Well-formed Formulas (WFFs): Valid logical
statements composed of atomic propositions and
connectives.
3.2 Semantics
 Truth values: Each proposition is either True or
False.
 Truth tables: Define the outcome of logical
expressions.
  Models: A model is an assignment of truth values to
all propositions that make a set of logical
statements true.
4. Propositional Theorem Proving
4.1 Methods
1. Direct Proof: Uses logical equivalences and
inference rules to derive a conclusion.
2. Proof by Contradiction: Assumes the negation of
the theorem and derives a contradiction.
3. Resolution: A rule of inference that simplifies
propositional logic proofs by eliminating variables.
5. Propositional Model Checking
 A method to verify if a knowledge base satisfies a
given formula.
 Truth Table Method: Checks all possible truth
assignments.
 DPLL Algorithm: Optimized version using
backtracking.
 SAT Solvers: Efficient tools for model checking.
6. Agents Based on Propositional Logic
 Agents use propositional logic to reason about their
environment.
 Example: In Wumpus World, agents deduce safe
paths using logical rules.
7. First-Order Logic (FOL)
7.1 Representation
FOL extends propositional logic by introducing:
 Constants: Objects in the domain.
 Predicates: Relations between objects (e.g.,
"Brother (John, Mike)").
  Functions: Maps from objects to objects (e.g.,
"Father (John)").
 Quantifiers:
o Universal (∀x): The statement is true for all x.
o Existential (∃x): The statement is true for at
least one x.
7.2 Syntax and Semantics
 Syntax: Defines how statements are constructed
using predicates, functions, and logical
connectives.
 Semantics: Assigns meaning to FOL statements
based on interpretations.
8. Using First-Order Logic in Knowledge Engineering
 Defining Objects, Relations, and Rules: Example:
"∀x Human(x) → Mortal(x)".
 Building Knowledge Bases: Encoding domain-
specific knowledge using FOL.
9. Inference in First-Order Logic
9.1 Unification and Lifting
 Unification: Finds substitutions to make different
expressions identical.
 Lifting: Extends propositional inference methods to
first-order logic.
9.2 Forward and Backward Chaining
 Forward Chaining: Starts with known facts and
applies inference rules to derive conclusions.
 Backward Chaining: Starts with a goal and works
backward to find supporting facts.
9.3 Resolution in FOL
 Converts FOL statements into clause form and
applies resolution to derive conclusions.
 Example:
o Given: ∀x (Human(x) → Mortal(x)), and Human
(Socrates)
o Resolution proves Mortal (Socrates)