Module 4: Logical Agents - Comprehensive Notes

Module 4: Logical Agents

Knowledge-Based Agents

• Humans can know “things” and “reason”.
• Representation: How are the things stored?
• Reasoning: How is the knowledge used?
  • To solve a problem.
  • To generate more knowledge.
• Knowledge and reasoning are important to artificial agents because they enable successful behaviors difficult to achieve otherwise.
• Useful in partially observable environments.
• Can benefit from knowledge in very general forms, combining and recombining information.

Knowledge-Based Agents: Components

• Knowledge-based agents are composed of two main parts:
  • Knowledge-base.
  • Inference system.

Knowledge-Based Agents: Requirements

A knowledge-based agent must be able to do the following:

• Represent states, actions, etc.
• Incorporate new percepts.
• Update the internal representation of the world.
• Deduce the internal representation of the world.
• Deduce appropriate actions.

Representation of Knowledge

• A KB (knowledge base) always consists of a set of sentences.
• Sentences are written in a knowledge representation language.

Inference System

• Inference means deriving new sentences from old.
• Inference system allows us to add a new sentence to the knowledge base. A sentence is a proposition about the world.
• Inference system applies logical rules to the KB to deduce new information.

Knowledge Base

Knowledge Base: set of sentences represented in a knowledge representation language; represent assertions about the world.

• Inference rule: when one ASKS questions of the KB, the answer should follow from what has been TELLed to the KB previously.

Inference System

• Inference means deriving new sentences from old.
• Inference system allows us to add a new sentence to the knowledge base. A sentence is a proposition about the world.
• Inference system applies logical rules to the KB to deduce new information.
• Inference system generates new facts so that an agent can update the KB.
• An inference system works mainly in two rules which are given as:
  • Forward chaining.
  • Backward chaining.

Inference System - Example

• Anil is intelligent.
• Anil is hardworking.
• If Anil is intelligent and Anil is hardworking then Anil scores high marks.

Why Use a Knowledge Base Agent?

• Knowledge-base is required for updating knowledge for an agent to learn with experiences and take action as per the knowledge.

Operations Performed by KBA

1. TELL: This operation tells the knowledge base what it perceives from the environment.
2. ASK: This operation asks the knowledge base what action it should perform.
3. Perform: It performs the selected action.

Knowledge-Based Agent

• A knowledge-based agent includes a knowledge base and an inference system.
• A knowledge base is a set of representations of facts of the world.
• Each individual representation is called a sentence.
• The sentences are expressed in a knowledge representation language.
• The agent operates as follows:
  1. It TELLs the knowledge base what it perceives.
  2. It ASKs the knowledge base of what action it should perform.
  3. It performs the chosen action.

Architecture of a Knowledge-Based Agent

• Knowledge Level: The most abstract level: describe agent by saying what it knows.
  • Example: A taxi agent might know that the Golden Gate Bridge connects San Francisco with Marin County.
• Logical Level: The level at which the knowledge is encoded into sentences.
  • Example: $Links(GoldenGateBridge, SanFrancisco, MarinCounty)$.
• Implementation Level: The physical representation of the sentences in the logical level.
  • Example: ‘(links goldengatebridge sanfrancisco marincounty)

Approaches to Designing a Knowledge-Based Agent

1. Declarative approach: We can create a knowledge-based agent by initializing it with an empty knowledge base and telling the agent all the sentences with which we want to start. This approach is called the Declarative approach.
2. Procedural approach: In the procedural approach, we directly encode desired behavior as a program code. Which means we just need to write a program that already encodes the desired behavior or agent.

The Wumpus World Environment

• Stench = Near Wumpus.
• Breeze = Near PIT.
• Think:
  • Near PIT: Breeze
  • Near Gold: Stench, Breeze, PIT, Wumpus
  • Near Wumpus: Stench
• PIT = A large hole.
• The task of the agent is to find the Gold and return back to home.
• The room adjacent to Wumpus are smelly(bad)- Stench.
• The room adjacent to pit has Breeze.
• There will be glitter in the room if and only if the room has gold.

Wumpus World PEAS Description

• Performance measure
  • gold +1000, death -1000
  • -1 per step, -10 for using the arrow
• 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 you are facing it
  • Shooting uses up the only Arrow
  • Grabbing picks up Gold if in same square
  • Releasing drops the Gold in same square
• Sensors: Stench, Breeze, Glitter, Bump, Scream
• Actuators: Left turn, Right turn, Forward, Grab, Release, Shoot

Wumpus World Characterization

• Observable? No, only local perception.
• Deterministic? Yes, outcome exactly specified.
• Episodic? No, sequential at the level of actions.
• Static? Yes, Wumpus and Pits do not move.
• Discrete? Yes.
• Single-agent? Yes, Wumpus is essentially a natural feature.

Exploring the Wumpus World

• The KB initially contains only the rules of the environment.
• The Agent is in cell [1,1].
• The first percept is [none, none, none, none, none].
• Move to safe cell, e.g. [2,1].
• Agent is in cell [2,1].
• The agent perceives a Breeze: [none, breeze, none, none, none].
• A Breeze in [2,1] indicates that there is a Pit in [2,2] or in [3,1].
• Thus, neither [2,2] nor [3,1] are safe to move to.
• Return to [1,1] to find other, safe cell to move to.
• Agent is in [1,2]. Perceives a Stench in cell [1,2].
• This means that a Wumpus is in [1,1], [1,3] or [2,2].
• YET … not in [1,1] - has been visited already.
• YET… not in [2,2] or stench would have been detected in [2,1].
• THUS… Wumpus must be in [1,3].
• No breeze in [1,2]. THUS [2,2] is safe.
• Breeze in [2,1] but no Pit in [2,2] THUS Pit in [3,1].
• Move to next safe cell [2,2]. From [2,2] move to [2,3].
• From [2,2] moved to [2,3].
• In [2,3] Agent detects Glitter, Smell, Breeze.
• Perceive Glitter, THUS pick up Gold.
• Perceive Breeze, THUS Pit in [3,3] or [2,4] (cannot be in [2,2]).
• Move back to safe [2,2]. Then to safe [2,1] or [1,2].
• Then to start in [1,1] and leave cave with Gold.

Logic

• Syntax
• Semantics
• Model
• Satisfies
• Logical
• Entailment

Logic in Artificial Intelligence

• Knowledge bases consist of sentences.
• Sentences are expressed according to the syntax of logic.
• Example: "x + y = 4" is a well-formed sentence, whereas "x4y+= " is not
• The semantics defines the truth of each sentence with respect to each possible world (model).

Logic in Artificial Intelligence Example

For the sentence "x + y = 4" where 0 < x,y <= 3

• The possible models are just all possible assignments of numbers to the variables x and y.
• $(1, 1)$, $(1, 2)$, $(1, 3)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(3, 1)$, $(3, 2)$ and $(3, 3)$
• The sentence is true in a world where
  • x is 1 and y is 3, ✓
  • x is 2 and y is 2 and
  • x is 3 and y is 1.
  • but false in all other cases.

Logic in Artificial Intelligence

• Logical entailment between sentences is that a sentence follows logically from another sentence.
• Mathematical notation: $a |= ẞ$ (sentence a entails the sentence B.)
• The formal definition of entailment is this: $a |= ẞ$ if and only if, in every model in which a is true, $ẞ$ is also true.
• $a |= ẞ$ if and only if $M(a) ≤ M(B)$
• $a : x+y=4$
• ẞ: x * y >= 2
• For all x, y <= 3
• $(1, 1)$, $(1, 2)$, $(1, 3)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(3, 1)$, $(3, 2)$ and $(3, 3)$
• a is true when x is 1 and y is 3, x is 2 and y is 2 and x is 3 and y is 1.
• We can apply the same kind of analysis to the wumpus-world reasoning example.
• Consider the situation in Figure: the agent has detected nothing in [1,1] and a breeze in [2,1].
• These percepts, combined with the agent's knowledge of the rules of the wumpus world, constitute the KB.
• The agent is interested in whether the adjacent squares [1,2], [2,2], and [3,1] contain pits.
• Each of the three squares might or might not contain a pit.
• Let us consider two possible conclusions:
  • a1 = "There is no pit in [1,2]."
  • a2 = "There is no pit in [2,2]."
  • KB |= a1
  • KB |= α2

Propositional Logic

• Propositional logic (PL) is the simplest form of logic where all the statements are made by propositions.
• A proposition is a declarative statement which is either true or false.
• It is a technique of knowledge representation in logical and mathematical form.

Propositional Logic Components

• Logical constants: true, false
• Propositional symbols: P, Q, S, … (atomic sentences)
• Wrapping parentheses: (…)
• Sentences are combined by connectives:
  • ^ …and [conjunction]
  • $v$ …or [disjunction]
  • $⇒$…implies [implication/conditional]
  • $⇔$..is equivalent [biconditional]
  • $¬$ …not [negation]
• Literal: atomic sentence or negated atomic sentence

Examples

• P means "It is hot."
• Q means "It is humid."
• R means "It is raining."
• $(P^Q) → R$
  • "If it is hot and humid, then it is raining"
• $Q→ P$
  • “If it is humid, then it is hot”

Wumpus World Sentences

• Let $P_{ij}$ be true if there is a pit in $[i, j]$.
• Let $B_{ij}$ be true if there is a breeze in $[i, j]$.
• start: $¬P_{1,1}$
• $¬B_{1,1}$
• $B_{2,1}$
• "Pits cause breezes in adjacent squares"
• $B<em>{1,1} ⇔ (P</em>{1,2} V P_{2,1})$
• $B<em>{2,1} ⇔ (P</em>{1,1} V P<em>{2,2} V P</em>{3,1})$

KB can be expressed as the conjunction of all of these sentences. Note that these sentences are rather long-winded!
E.g., breeze "rule" must be stated explicitly for each square. First-order logic will allow us to define more general patterns.

Two Types of Propositional Logic

• Atomic Proposition: Atomic propositions are the simple propositions. It consists of a single proposition symbol.
  • For Example 2+2 is 4, it is an atomic proposition as it is a true fact.
  • The Sun is cold " is also a proposition as it is a false fact.
• Compound proposition: Compound propositions are constructed by combining simpler or atomic propositions, using parenthesis and logical connectives.
  • For Example "It is raining today, and street is wet.
  • Ankit is a doctor, and his clinic is in Mumbai.

Propositional Logic: Semantics

• A sentence is interpreted in terms of models, or possible worlds.
• These are formal structures that specify a truth value for each sentence in a consistent manner.

More on Possible Worlds

• m is a model of a sentence a if a is true in m
• M(α) is the set of all models of α
• Possible worlds ~ models
• Possible worlds: potentially real environments
• Models: mathematical abstractions that establish the truth or falsity of every sentence
  Example:
• x + y = 4, where x = #men, y = #women
• Possible models = all possible assignments of integers to x and y.
• For CSPs, possible model = complete assignment of values to variables.

Propositional Logic: Formal Semantics

Each model/world specifies true or false for each proposition symbol
E.g.

• $P_{1,2} = false$
• $P_{2,2} = true$
• $P_{3,1} = false$

With these symbols, 8 possible models, can be enumerated automatically.

• Rules for evaluating truth with respect to a model m:

  • $¬S$ is true iff S is false
  • $S<em>1 ⋀ S</em>2$ is true iff $S<em>1$ is true and $S</em>2$ is true
  • $S<em>1 ⋁ S</em>2$ is true iff $S<em>1$ is true or $S</em>2$ is true
  • $S<em>1 ⇒ S</em>2$ is true iff $S<em>1$ is false or $S</em>2$ is true
    • i.e., is false iff $S<em>1$ is true and $S</em>2$ is false
  • $S<em>1 ⇔ S</em>2$ is true iff $S<em>1 ⇒ S</em>2$ is true and $S<em>2 ⇒ S</em>1$ is true
    Simple recursive process evaluates every sentence, e.g.,
    $P<em>{12} ⋀ (P</em>{22} ⋁ P_{3.1}) = true ⋀ (true ⋁ false) = true ⋀ true = true$

Compound Proposition

• Complex sentences are constructed from simpler sentences, using parentheses and logical connectives.
• There are five connectives in common use:
  • Negation: A sentence such as ¬P is called negation of P. A literal can be either Positive literal or negative literal.
    • $P$= Anil is intelligent.
    • ¬P Means?

Compound Proposition

• Disjunction: A sentence which has v connective, such as $P ⋁ Q$. is called disjunction, where $P$ and $Q$ are the propositions.
  • For Example: "Ritika is a doctor or Engineer", Here $P$= Ritika is Doctor.
    • $P$= Ritika is Doctor.
    • $Q$= Ritika is Engineer.
    • $P ⋁ Q$

Compound Proposition

• Implication: A sentence such as $P→ Q$, is called an implication. Implications are also known as if-then rules.
  • It can be represented as: If it is raining, then the street is wet.
  • Let $P$= It is raining, and $Q$= Street is wet, so it is represented as $P→ Q$

Compound Proposition

• Biconditional(if and only if): A sentence such as P⇔Q is a Biconditional sentence. example If I am breathing, then I am alive
  $P$= I am breathing, $Q$= I am alive, it can be represented as P ==> Q.

Truth Tables for Connectives

Evaluation Demo - Tarki's World

Implication is always true when the premise is false

Why? P=>Q means “if P is true then I am claiming that Q is true otherwise no claim"

Only way for this to be false is if P is true and Q is false

Wumpus Models

• KB = all possible wumpus-worlds consistent with the observations and the "physics" of the Wumpus world.

Entailment

One sentence follows logically from another $α |= β$

a entails sentence β if and only if β is true in all worlds where a is true.
e.g., x+y=4 |= 4=x+y

Entailment is a relationship between sentences that is based on semantics.

Schematic Perspective

If KB is true in the real world, then any sentence a derived from KB by a sound inference procedure is also true in the real world.

Inference Rules

In artificial intelligence, we need intelligent computers which can create new logic from old logic or by evidence, so generating the conclusions from evidence and facts is termed as Inference.

Types of Inference Rules

Modus Ponens

The Modus Ponens rule is one of the most important rules of inference, and it states that if P and P→Q is true, then we can infer that Q will be true. It can be represented as:

P→Q, P
Q

If (WumpusAhead ∧ WumpusAlive) => Shoot and (WumpusAhead ∧ WumpusAlive) are given, then shoot can be inferred.

• Statement-1: "If I am sleepy then I go to bed" ==> P→ Q
• Statement-2: "I am sleepy" ==> P
• Conclusion: "I go to bed." ==> Q.
  Hence, we can say that, if $P ⇒ Q$ is true and $P$ is true then Q will be true.

AND Elimination

From a conjunction any of the conjuncts can be inferred:
$α ⋀ B$
α

(WumpusAhead ∧ WumpusAlive), WumpusAlive can be inferred.

Bi-conditional Elimination

$α ⇔ B$ and $(a ⇒ B) ⋀ (ẞ ⇒ a)$

Limitations of Propositional Logic

• We cannot represent relations like ALL, some, or none with propositional logic. Example:
  • All the girls are intelligent.
  • Some apples are sweet.
• Propositional logic has limited expressive power.
• In propositional logic, we cannot describe statements in terms of their properties or logical relationships.

Propositional Logic

• A proposition is a declarative statement that’s either true (T) or false (F), but not both

Propositional Logic

• Translating English sentence into a logical expression “You can access the internet from campus only if you are a computer science major or you are not a freshman”
  • a: “You can access the internet from campus”
  • b: “you are a computer science major”
  • c: “you are a freshman”
    Where a,b,c are propositional variables
  • $a → (b ⋁ ¬c)$

Propositional Logic Translation

(System specifications)
Express the specification ”The automated reply cannot be sent when the file system is full“ using logical connectives.
$P$: “The automated reply can be sent”

q: “The file system is full”

$q → ¬p$

System specifications should be consistent
They should not contain conflicting requirements that could be used to drive a contradiction

Propositional Logic Translation

(System specifications) determine whether these system specifications are consistent:

• “The diagnostic message is stored in the buffer or it is retransmitted”
• “The diagnostic message is not stored in the buffer”
• “if the diagnostic message is stored in the buffer, then it is retransmitted”
  • $P$: “The diagnostic message is stored in the buffer”
    $q$: “The diagnostic message is retransmitted”
    $p ⋁ q$
    $¬p$
    $p→q$

Propositional Theorem Proving

Standard Logical Equivalences

Logical equivalence is one of the features of propositional logic. Two propositions are said to be logically equivalent if and only if the columns in the truth table are identical to each other.

Standard Logical Equivalences

• $(a ⋀ B) = (B ⋀ a)$ commutativity of ⋀
• $(a ⋁ B) = (B ⋁ a)$ commutativity of ⋁
• $((a⋀B) ⋀y) = (a⋀ (B ⋀Y))$ associativity of ⋀
• $((a ⋁ B) ⋁ y) = (a ⋁ (B ⋁ Y))$ associativity of ⋁
• $¬(¬α) = a$ double-negation elimination
• $(a ⇒ B) = (¬B ⇒¬a)$ contraposition
• $(a ⇒ B) = (¬a ⋁ B)$ implication elimination
• $(a ⇔ B) = ((a ⇒ B) ⋀ (B ⇒ a))$ biconditional elimination
• $¬(α ⋀ B) = (¬α ⋁¬B)$ de Morgan
• $¬(α ⋁ B) = (¬α ⋀¬B)$ de Morgan
• $(a ⋀ (B ⋁y)) = ((a ⋀ B) ⋁ (a⋀y))$ distributivity of ⋀ over ⋁
• $(a ⋁ (B⋀y)) = ((a ⋁ B) ⋀ (a ⋁ y))$ distributivity of ⋁ over ⋀

Agents Based on Propositional Logic

• What we have learned so far in order to construct agents that operate using propositional logic.
• Wumpus world.

Wumpus World Sentences

• Let $Pij$ be true if there is a pit in $[i, j]$.
• Let $Bij$ be true if there is a breeze in $[i, j]$.
• start: $¬P_{1,1}$
• $¬B_{1,1}$
• $B_{2,1}$
• "Pits cause breezes in adjacent squares"
• $B<em>{1,1} ⇔ (P</em>{1,2} ⋁ P_{2,1})$
• $B<em>{2,1} ⇔ (P</em>{1,1} ⋁ P<em>{2,2} ⋁ P</em>{3,1})$

KB can be expressed as the conjunction of all of these sentences. Note that these sentences are rather long-winded!
E.g., breeze "rule" must be stated explicitly for each square. First-order logic will allow us to define more general patterns.

Wumpus World Model-Checking / Truth Table Approach

A model-checking / Truth Table approach is a simple inference procedure
Our goal is to decide whether KB |= α for some sentence a.

• Steps in the model-checking approach:
  * enumerate the models (models are assignments of true or false to every proposition symbol),
  * Select the KB where the model is True
  * check that α is true in every model in which KB is true.

Let us consider two conclusions:
* a1 = "There is no pit in [1,2]."
* a2 = "There is no pit in [2,2]."
* KB |= α1
* KB |= α2

To construct a knowledge base for the wumpus world. 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 [×, y].

There is no pit in [1,1]:
$– R<em>1 : ¬P</em>{1,1}$

A square is breezy iff there is a pit in a neighboring square:

$– R<em>2 : B</em>{1,1} ⇔ (P<em>{1,2} ⋁ P</em>{2,1})$

-(P1,2 ⋁ P2,1

$– R<em>3 : B</em>{2,1} ⇔ (P<em>{1,1} ⋁ P</em>{2,2}⋁ P_{3,1})$

The preceding sentences are true in all wumpus worlds.
Breeze percepts for the first two squares visited

$– R<em>4:¬B</em>{1,1}$
$R<em>5: B</em>{2,1}$

The relevant proposition symbols are
$–B<em>{1,1}, B</em>{2,1}, P<em>{1,1}, P</em>{1,2}, P<em>{2,1}, P</em>{2,2}, and P_{3,1}$

There are $2^7 = 128$ possible models

Wumpus World Model-Checking / Truth Table Approach

$R<em>1:¬P</em>{1,1}$
$R<em>2: B</em>{1,1} ⇔ (P<em>{1,2} ⋁ P</em>{2,1})$
$R<em>3: B</em>{2,1} ⇔ (P<em>{1,1} ⋁ P</em>{2,2}⋁ P<em>{3,1})$$R</em>4: ¬B<em>{1,1}$$R</em>5: B_{2,1}$

Wumpus World Model-Checking / Truth Table Approach

Let us consider two possible conclusions:

• a1 = "There is no pit in [1,2]."
• KB|= a1
• a2 = "There is no pit in [2,2]."
• KB|= α2

Normal Clausal Form

We first rewrite into conjunctive normal form (CNF). Eventually we want to prove:
A “conjunction of disjunctions
$(A ⋁ ¬B) ⋀ (B ⋁ ¬C ⋁ ¬D)$

Clause
literal

• Theorem: Any KB can be converted into an equivalent CNF.
• k-CNF: exactly k literals per clause Knowledge base KB entails sentence α

Example: Conversion to CNF

$B<em>{1,1} ⇔ (P</em>{1,2} ⋁ P_{2,1})$

Eliminate ⇔, replacing $α ⇔ β$ with $(α ⇒ β)⋀(β ⇒ α)$.
$(B<em>{1,1} ⇒ (P</em>{1,2} ⋁ P<em>{2,1})) ⋀ ((P</em>{1,2} ⋁ P<em>{2,1}) ⇒ B</em>{1,1})$

Eliminate ⇒, replacing $α ⇒ β$ with $¬α⋁ β$
$(¬B<em>{1,1}⋁ P</em>{1,2} ⋁ P<em>{2,1}) ⋀ (¬(P</em>{1,2} ⋁ P<em>{2,1}) ⋁ B</em>{1,1})$

Move ¬ inwards using de Morgan's rules and double-negation:
$(¬B<em>{1,1}⋁ P</em>{1,2} ⋁ P<em>{2,1}) ⋀ ((¬P</em>{1,2} ⋀ ¬P<em>{2,1}) ⋁ B</em>{1,1})$

Apply distributive law (⋀ over ⋁) and flatten:
$(¬B<em>{1,1}⋁ P</em>{1,2} ⋁ P<em>{2,1}) ⋀ (¬P</em>{1,2} ⋁ B<em>{1,1}) ⋀ (¬P</em>{2,1} ⋁ B_{1,1})$

A Resolution Algorithm

Each pair that contains complementary literals is resolved to produce a new clause which is added to the set if it is not already present
The process continues until one of two things happens:

• there are no new clauses that can be added, in which case KB does not entail α; or,
• two clauses resolve to yield the empty clause, in which case KB entails α.

The empty clause—a disjunction of no disjuncts—is equivalent to False because a disjunction is true only if at least one of its disjuncts is true.

$KB =(B<em>{1,1} ⇔ (P</em>{1,2} ⋁ P<em>{2,1})) ⋀ ¬B</em>{1,1}$
Prove: ¬P1,2
Convert: (KB ⋀ ¬α) into CNF

Horn Clauses and Definite Clauses

• Definite Clause:
  • Disjunction of literals of which exactly one is positive.
    • Eg., ($¬L<em>{1,1} ⋁ ¬Breeze ⋁ B</em>{1,1}$) -> definite clause
    • ($¬B<em>{1,1} ⋁ P</em>{1,2} ⋁ P_{2,1}$) -> is not
• Horn Clause:
  • disjunction of literals of which at most one is positive.
  • So all definite clauses are Horn clauses
• Goal Clause:
  • clauses with no positive literals
• Horn clauses are closed under resolution: if you resolve two Horn clauses, you get back a Horn clause.

Summary

• Logical agents apply inference to a knowledge base to derive new information and make decisions
• Basic concepts of logic:
  • syntax: formal structure of sentences
  • semantics: truth of sentences wrt models
  • entailment: necessary truth of one sentence given another
  • inference: deriving sentences from other sentences
  • soundness: derivations produce only entailed sentences
  • completeness: derivations can produce all entailed sentences.