Module No : 03

Knowledge Representation,
Reasoning and Planning
 Syllabus

3.1 Knowledge based agents

3.2 First order logic:

❖ syntax and Semantic
❖ Knowledge Engineering in FOL
❖ Inference in FOL :
❖ Unification,
❖ Forward Chaining,
❖ Backward Chaining and
❖ Resolution
3.3 Planning
❖ Partial Order Planning
❖ Hierarchical Planning and
❖ Conditional Planning
Agent
Relation between Knowledge and Intelligence

Sensing from
Environment Decision Knowledge
Action to making
Environment

An intelligent agent needs knowledge about the real world for taking
decisions and reasoning to act efficiently
 Knowledge-Based Agent
• Knowledge based agents are those agents who have the capability of maintaining
an internal state of knowledge, reason over that knowledge, update their
knowledge after observations and take actions.

• Knowledge based agents are composed of two main parts:

-knowledge based
-Inference system
• A knowledge base is a set of sentences in a formal language (knowledge
representation language) representing facts about the world

• Inference system derives new sentences from the input and knowledge base
 Knowledge-Based Agent
• Knowledge based agents must able to do the following:
-An agent should be able to represent states, actions, etc.
-An agent should be able to incorporate new percept's
-An agent can update the internal representation of the world
-An agent can deduce the internal representation of the world
-An agent can deduce appropriate actions
• Knowledge and Knowledge representation

• Understanding theoretical or practical aspects of the subject is

called as knowledge

• We can gain knowledge through experience acquired based on the

facts, information etc. about the subject
• After gaining knowledge about some subject we can apply that
knowledge to derive conclusions about various problems related
to that subject based on some reasoning
The architecture of knowledge-based agent
Why use a knowledge base?
• Knowledge-base is required for updating knowledge for an agent to learn
with experiences and take action as per the knowledge.

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
• Forward chaining is a data-driven, bottom-up reasoning
method that starts with known facts to derive conclusions,
ideal for planning and monitoring.

• Backward chaining is a goal-driven, top-down technique

starting from a hypothesis to find supporting facts, best for
diagnostics and debugging
• Simple analogy:
• Forward chaining: “I know these facts. What conclusion can I
derive?”
• Backward chaining: “I want to prove this conclusion. What
facts are required?”
Operations Performed by KBA

Following are three operations which are performed by KBA in order to

show the intelligent behavior:

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.
 Types of Knowledge
• Knowledge and Reasoning
The five main categories of knowledge branching from the central
node are:

1. Declarative Knowledge
1. Refers to factual information, objects, and concepts.
2. It is also known as descriptive knowledge.
3. Example: "Paris is the capital of France."
4. Associated term: Objects, Facts
2. Procedural Knowledge
1. Refers to the knowledge of how to perform a task or execute a procedure.
2. It is action-oriented and involves sequences of steps.
3. Example: "How to ride a bicycle" or "How to drive a car."
4. Associated term: Rules, Procedures
3. Heuristic Knowledge
1. Refers to knowledge gained through experience, intuition, or rules of thumb.
2. It is often used in problem-solving and decision-making.
3. Example: "If a road is wet, drive slowly."
4. Associated term: Rules of Thumb
4. Structural Knowledge
1. Defines relationships between objects, concepts, and ideas.
2. Helps in organizing and connecting knowledge in a meaningful way.
3. Example: "A dog is a mammal, and mammals are warm-blooded animals."
4. Associated term: Relationships between Objects, Concepts
5. Meta-Knowledge
5. Refers to knowledge about knowledge, i.e., understanding how knowledge is
structured and used.
6. Helps in improving problem-solving efficiency and learning new concepts.
7. Example: "Knowing how to organize a knowledge base for AI systems."
8. Associated term: Knowledge about Knowledge
• A Knowledge Based Agent

• Knowledge base is a set of representations of facts and

information
• Knowledge level is a base level(initial knowledge) of an agent,
which consists of domain-specific content (information about the
surrounding in which the agent is working)
• Knowledge based agent make use of the existing Knowledge
along with the current input from the environment in order to infer
hidden aspects of the current state
• Agent makes use of TELL and ASK mechanism
• A Knowledge Based Agent
• TELL(K): is a function that adds knowledge ‘K’ to the
knowledge base (what needs to know about surrounding to
perform some action)

• ASK(K): is a function that queries the agent about the truth of ‘K’
(what actions should be carried out to get desired output)
 AI knowledge cycle
• An Artificial intelligence system has the following components for
displaying intelligent behavior ( explain various methods of knowledge
representation)

• Perception
• Learning
• Knowledge Representation and Reasoning
• Planning
• Execution

Execution
 Approaches to knowledge representation
• There are mainly four approaches to knowledge representation,
which are given below:

1. Simple relational knowledge:

• It is the simplest way of storing facts which uses the relational method,
and each fact about a set of the object is set out systematically in
columns.
• This approach of knowledge representation is famous in database systems
where the relationship between different entities is represented.

• This approach has little opportunity for inference.

 Approaches to knowledge representation

2. Inheritable knowledge:
• In the inheritable knowledge approach, all data must be stored into a hierarchy
of classes.
• All classes should be arranged in a generalized form or a hierarchal manner.
• In this approach, we apply inheritance property.

• Elements inherit values from other members of a class.

• This approach contains inheritable knowledge which shows a relation between
instance and class, and it is called instance relation.
• Every individual frame can represent the collection of attributes and its value.
• In this approach, objects and values are represented in Boxed nodes.
• We use Arrows which point from objects to their values.
3. Inferential knowledge:
• Inferential knowledge approach represents knowledge in the form of formal
logics.
• This approach can be used to derive more facts.
• It guaranteed correctness.
• Example: Let's suppose there are two statements:
1. Marcus is a man

– All men are mortal

Then it can represent as;

man(Marcus)
∀x = man (x) ----------> mortal (x)s
4. Procedural knowledge:
• Procedural knowledge approach uses small programs and codes which
describes how to do specific things, and how to proceed.
• In this approach, one important rule is used which is If-Then rule.
• In this knowledge, we can use various coding languages such as LISP
language and Prolog language.
• We can easily represent heuristic or domain-specific knowledge using
this approach.

• But it is not necessary that we can represent all cases in this approach.
Requirements for knowledge Representation system:

• A good knowledge representation system must possess the following properties.

1. Representational Accuracy:
KR system should have the ability to represent all kind of required knowledge.
2. Inferential Adequacy:
KR system should have ability to manipulate the representational structures to
produce new knowledge corresponding to existing structure.
3. Inferential Efficiency:
The ability to direct the inferential knowledge mechanism into the most
productive directions by storing appropriate guides.

4. Acquisitional efficiency- The ability to acquire the new knowledge easily using
automatic methods.
 Techniques of knowledge representation
• There are mainly four ways of knowledge representation which are given
as follows:

1. Logical Representation
2. Semantic Network Representation
3. Frame Representation
4. Production Rules
1. Logical Representation
• Logical representation is a language with some concrete rules which deals with
propositions and has no ambiguity in representation.

• Logical representation means drawing a conclusion based on various conditions.

• This representation lays down some important communication rules. It consists of

precisely defined syntax and semantics which supports the sound inference.

• Each sentence can be translated into logics using syntax and semantics.

Syntax:

• Syntaxes are the rules which decide how we can construct legal sentences in the logic.
• It determines which symbol we can use in knowledge representation.
• How to write those symbols.

Semantics:

• Semantics are the rules by which we can interpret the sentence in the logic.
• Semantic also involves assigning a meaning to each sentence.
Logical representation can be categorized into mainly two logics:

1. Propositional Logics
2. Predicate logics

Advantages of logical representation:

1. Logical representation enables us to do logical reasoning.
2. Logical representation is the basis for the programming languages.

Disadvantages of logical Representation:

1. Logical representations have some restrictions and are challenging to work

with.
2. Logical representation technique may not be very natural, and inference may
not be so efficient.
2. Semantic Network Representation
• Semantic networks are alternative of predicate logic for knowledge
representation.

• In Semantic networks, we can represent our knowledge in the form of

graphical networks.

• This network consists of nodes representing objects and arcs which

describe the relationship between those objects.

• Semantic networks can categorize the object in different forms and can
also link those objects.

• Semantic networks are easy to understand and can be easily extended.

• This representation consist of mainly two types of relations:

1. IS-A relation (Inheritance)

2. Kind-of-relation
 • Example: Following are some statements which we need to represent in the form of
nodes and arcs.

• Statements:

1. Jerry is a cat.
2. Jerry is a mammal
3. Jerry is owned by Priya.
4. Jerry is brown colored.
5. All Mammals are animal.
• Reasoning(Logic)

• Reasoning is associated with thinking, cognition, and intellect.

• The philosophical field of logical studies in which humans reason formally
through arguments
• Reasoning may be subdivided into many forms, we are going to study only
following

✔ Propositional Logic(PL)
✔ First Order Predicate Logic
• Propositional Logic(PL)

• PL is a simple knowledge representation language

• A proposition is the statement of a fact. We usually assign a symbolic variable
(Symbols are denoted by capital letters like A,B,C, etc.) to represent a
proposition, e.g.
• P = It is raining
• Q = I carry an umbrella
• A proposition is a sentence whose truth values may be determined. So, each
proposition has a truth value,(Constants have truth values i.e. 0 is False and 1 is
True) e.g.
• The proposition ‘A rectangle has four sides’ is true
• The proposition ‘The world is a cube’ is false.
• PL is the foundation for higher logics like First Order Logic(FOL)
 • Propositional Logic(PL)

• Different propositions may be logically related and we can form

compound statements of propositions using logical connectives.
• Common logical connectives are:
1. ˄ AND (Conjunction)
2. ˅ OR (Disjunction)
3. ¬ NOT (Negation)
4. => If … then (Conditional)
5. <=> If and only if (bi-conditional)
• Propositional Logic(PL)
• Propositional Logic(PL)
• To define logical connectives truth tables are used
• Following Truth Table shows five connectives

A B A˄B A˅B ¬A A=>B A<=>B

T T

T F

F T

F F
• Propositional Logic(PL)
• To define logical connectives truth tables are used
• Following Truth Table shows five connectives

A B A˄B A˅B ¬A A=>B A<=>B

T T T

T F F

F T F

F F F
• Propositional Logic(PL)
• To define logical connectives truth tables are used
• Following Truth Table shows five connectives

A B A˄B A˅B ¬A A=>B A<=>B

T T T T

T F F T

F T F T

F F F F
• Propositional Logic(PL)
• To define logical connectives truth tables are used
• Following Truth Table shows five connectives

A B A˄B A˅B ¬A A=>B A<=>B

T T T T F

T F F T F

F T F T T

F F F F T
• Propositional Logic(PL)
• To define logical connectives truth tables are used
• A=>B equal to ¬A ˅ B

A B A˄B A˅B ¬A A=>B A<=>B

T T T T F T

T F F T F F

F T F T T T

F F F F T T
• Propositional Logic(PL)
• To define logical connectives truth tables are used
• A<=>B equal to (A=>B) ˄ (B=>A)

A B A˄B A˅B ¬A A=>B A<=>B

T T T T F T T

T F F T F F F

F T F T T T F

F F F F T T T
 • Propositional Logic(PL)
Conversion of sentences into PL
1. It is hot and sunny
• A: it is hot
• B: it is sunny
✔ A˄B

3. She can have either tea or coffee

• A: She can have tea
• B: she can have coffee
✔ A˅ B
• Propositional Logic(PL)
Conversion of sentences into PL
3. I don’t like Stephen but I like Peter
• A: I like Stephen
• B: I like Peter
✔ ¬A˄B

4. If it is humid then it will rain

• A: it is humid
• B: it will rain
✔ A => B
• Propositional Logic(PL)
Conversion of sentences into PL
5. John is good looking and wealthy but not healthy
• A: John is good looking
• B: John is wealthy
• C: John is healthy
✔ (A ˄ B) ˄ ¬C

6. Ram is the English teacher but not Maths teacher

• A: Ram is a English teacher
• B: Ram is a Maths teacher
✔ A˄¬B
• Propositional Logic(PL)
Conversion of sentences into PL
7. If it is rainy I will stay at home
• A: it is rainy
• B: I will stay at home
• A => B

8. If John brought an i-phone today then he either sold his old mobile
or took a bank loan
• A: John brought i-phone
• B: John sold his old mobile
• C: John took a bank loan
✔ A => (B ˅ C)
• Propositional Logic(PL)
Conversion of sentences into PL
9. If it is hot and humid then it is raining
• A: it is hot
• B: it is humid
• C: it is raining
✔ (A ˄ B) => C

10. Cat chases mice or bird but not at a same time

• A: cat chases mice
• B: cat chases bird
✔ (A ˅ B) ˄ ¬ (A ˄ B)
• Propositional Logic(PL)
Conversion of sentences into PL
11. Dolphin’s neither literate not able to read but they are intelligent
• A: Dolphin’s are literate
• B: Dolphin’s are able to read
• C: Dolphin’s are intelligent
✔ (¬ A ˅ ¬ B) ˄ C
• Propositional Logic(PL)
Conversion of sentences into PL
Sentence_1: "If it is a weekday, then I have to go to work."

Propositional Logic: p -> q, where p represents "it is a weekday" and q

represents "I have to go to work."

Sentence_2: "The car will start if the battery is charged and the fuel tank is
full."

Propositional Logic: p ∧ q -> r, where p represents "the battery is

charged," q represents "the fuel tank is full," and r represents "the car will
start."

Sentence_3: "I will go to the concert only if I can find a good seat."

Propositional Logic: p → q, where p represents "I can find a good seat"

and q represents "I will go to the concert."
• Propositional Logic(PL)
Conversion of sentences into PL
Sentence_4: "If the car does not start and I miss my meeting, then I will lose
my job."

Propositional Logic: (p ∧ q) -> r, where p represents "the car does not

start," q represents "I miss my meeting," and r represents "I will lose my job.“
Sentence_5: "John is happy if and only if he gets the promotion or his wife
agrees to move."

Propositional Logic: (p ∨ q) ↔ r, where p represents "John gets the

promotion," q represents "John's wife agrees to move," and r represents "John
is happy."
• Propositional Logic(PL)
Conversion of sentences into PL
Sentence_6: "If the temperature is below freezing and it is snowing, then the
roads will be slippery and dangerous."
Propositional Logic: (p ∧ q) -> (r ∧ s), where p represents "the
temperature is below freezing," q represents "it is snowing," r represents "the
roads will be slippery," and s represents "the roads will be dangerous."

Sentence_7: "If the plane is delayed or I miss my connection, then I will not
arrive on time for the meeting unless I can reschedule."

Propositional Logic: (p ∨ q) -> ~(r ∧ ~s), where p represents "the plane

is delayed," q represents "I miss my connection," r represents "I arrive on time
for the meeting," and s represents "I can reschedule."
• Propositional Logic(PL)
Conversion of sentences into PL

Sentence_8: "If it is raining and the wind speed is greater than 30 mph, then
the roof will leak unless it has been recently repaired."

Propositional Logic: (p ∧ q) -> ~(r ∧ ~s), where p represents "it is

raining," q represents "the wind speed is greater than 30 mph," r represents
"the roof will leak," and s represents "the roof has been recently repaired."

Sentence_9: "If I do not finish my homework and I fail the exam, then I will
not be able to graduate unless I retake the course."

Propositional Logic: (p ∧ q) -> ~(r ∧ ~s), where p represents "I do not

finish my homework," q represents "I fail the exam," r represents "I will be
able to graduate," and s represents "I retake the course."
• Propositional Logic(PL)
• Propositional Logic(PL)
• Inference in PL:
• If knowledge base is having initial knowledge A=B and B=C
then inference is A=C
• Inference is a new sentence created logically according to
knowledge base
 First-Order Logic (FOL)

• First-Order Logic (FOL) is a formal language used in

Artificial Intelligence to represent knowledge about
objects, their properties, and relationships between
objects.
• Unlike propositional logic, FOL can represent
individual objects and relationships using variables,
predicates, and quantifiers.
Basic Components of FOL
• First Order Logic(FOL)
• FOL is also called as First Order Predicate Logic
• It is much more expressive than PL to represent knowledge
• In FOL we can represent information using relations, variables
and quantifiers
• e.g. 1. “It is Sunday today” can be represented as : today(Sunday)
• e.g. 2. “Gorilla is Black” can be represented as : Gorilla(X)
Black(X)
• Rules has two parts predecessor and successor. If the predecessor
is evaluated to true successor will be true
• It uses the implication symbol
• e.g. “if the bag is of Blue colour, I will buy it” will be
represented as
• colour(bag, blue) buy(bag)
 Identify keywords
English keyword FOL pattern
All / Every (\forall x)
Some / There exists (\exists x)
(\forall x(P(x)\rightarrow \neg
No / None
Q(x)))
If...then (P\rightarrow Q)
And (P\land Q)
Or (P\lor Q)
Not (\neg P)
Usually implication in the
Only
reverse direction
Someone / Something (\exists x)
 Remember this sequence

• English sentence → Find keyword → Identify predicates →

Add quantifier → Connect predicates
• First Order Logic(FOL)
• Quantifiers:
• They quantify the number of variables taking part in the relation

• Universal Quantifier(∀):
• Pronounced as “for all” and it is applicable to all the variables in the
predicate
• “ ∀ x A” means A is true for every replacement of x
• is the main connective with ∀
• E.g. “Every Gorilla is Black” can be represented by
• ∀ x (Gorilla(x) Black(x) )
• E.g. “Everyone in TE Comps is smart” can be represented by
• ∀ x (x, TE Comps smart(x) )
• First Order Logic(FOL)
• Existential Quantifier(∃):
• Pronounced as “there exists”
• “∃ x A” means A is true for at least one replacement of x
• ˄ is the main connective with ∃
• E.g. “There is a white Dog” can be represented by
• ∃ x (Dog(x) White(x) )
• E.g. “Someone killed the cat and is guilty” can be represented by
• ∃ x Killed(x, Cat) ˄ guilty(x)
❑ Convert the following sentences into FOL
1. Apple is a fruit
fruit(apple)
2. John is tall
tall(John)
3. Country China is an enemy of India
Enemy(China, India)
4. Anish only likes easy courses
∀ x : Courses(x) ˄ Easy(x) Likes(Anish, x)
5. If it is Saturday and warm then Sam is in the Park
day(Saturday) ˄ whether(Warm) in_the_park(Sam)
❑ Convert the following sentences into FOL
6. Ravi likes all kind of food
∀x : Food(x) Likes(Ravi, x)
7. Ajay eats peanuts and still alive
Eats(Ajay, Peanuts) ˄ Alive(Ajay)
8. Anything anyone eats and not killed is food
∀x ∀y : Eats(x, y) ˄ ¬ Killed(x)
9. Every perfect square is divisible by some prime
∀x ∃y : Square(x) ˄ Divides(Prime, x)
10. All the missiles were sold to PAK by China
∀x Missile(x) ˄ Owns(PAK, x) Sell (China, x, PAK)
❑ Convert the following sentences into FOL

11. Bill takes either Image Processing or Soft Computing

Takes (Bill, IP) V Takes (Bill, SC)
12. Some students loves Bill, All students loves Bill
∃x students(x) ˄ Loves(x, Bill)
∀x students(x) Loves(x, Bill)
• Convert FOL(First Order Logic) to CNF (Conjunctive Normal Form)
• Steps to convert FOL to CNF:
1. Conversion of sentences into FOL
2. Eliminate implications
3. Standardize variables
4. Move negative inwards
5. Skolemization(Remove Existential Quantifiers)
6. Drop universal quantifier
• Convert FOL(First Order Logic) to CNF (Conjunctive Normal Form)
1. Eliminate implications:
A→B = ¬ A ∨ B
A ↔ B = (A→B) ∧ (B→A)
= (¬ A ∨ B) ∧ (¬ B ∨ A)
2. Standardize variables:
All people who are graduating are happy. All happy people smile.
Someone is graduating.
∀(X) Smile(X)
∃(X) Graduating(X)
∀(X) Happy(X)
instead of using same variable name use different
∀(X) Smile(X)
∃(Y) Graduating(Y)
∀(Z) Happy(Z)
• Convert FOL(First Order Logic) to CNF (Conjunctive Normal Form)
3. Move negation inwards:

¬ [ ∀(X). P(X) ] = ∃(X) . ¬ P(X)

¬ [∃(X). P(X) ] = ∀(X) . ¬ P(X)
¬ (A ∧ B) = ¬ A ∨ ¬B
¬ (A ∨ B) = ¬ A ∧ ¬B
¬ (¬ A) = A
• Convert FOL(First Order Logic) to CNF (Conjunctive Normal Form)
4. Skolemization:
Replace Existential quantifiers(∃) with Skolem constants
e.g.
Before skolemization
1. someone is smiling ∃(X)Smile(X)
2. someone is graduating ∃(X)Graduating(X)

After skolemization
1. Smile(A)
2. Graduating(B)
• Convert FOL(First Order Logic) to CNF (Conjunctive Normal Form)
5. Drop universal quantifiers:
Replace universal quantifiers(∀) with constants
e.g.
Before dropping universal quantifier
1. All are smiling ∀(X)Smile(X)
2. All are graduating ∀(X)Graduating(X)

After dropping universal quantifier

1. Smile(X)
2. Graduating(Y)
• First Order Logic(FOL)
Q. Consider the following facts about people
1. All people who are graduating are happy
2. All happy people smile
3. Someone is graduating
• Convert to FOL
• Convert FOL to CNF
• Prove that “Is someone smiling?” using resolution
• Draw resolution graph/tree
• Convert FOL(First Order Logic) to CNF (Conjunctive Normal Form)
• Steps to convert FOL to CNF:
Conversion of sentences into FOL
1. Eliminate implications
2. Standardize variables
3. Move negative inwards
4. Skolemization
5. Drop universal quantifier
 • Convert to FOL
Q. Consider the following facts about people
1. All people who are graduating are happy
2. All happy people smile
3. Someone is graduating
Answers:
A. All people who are graduating are happy
∀ x (Graduating(x) → Happy(x) )
B. All happy people smile
∀ x (Happy (x) → Smile(x) )
C. Someone is graduating
∃ x Graduating(x)
We are going to prove that ‘someone is smiling?’, so will write this in FOL
∃ x Smiling(x)
 • Convert to CNF
Step:1 Eliminate implications [use formula A→B = ¬ A ∨ B]
Answers:
A. All people who are graduating are happy
∀ x [Graduating(x) → Happy(x) ]
∀ x [¬ Graduating(x) ∨ Happy(x) ]
B. All happy people smile
∀ x [ Happy (x) → Smile(x) ]
∀ x [¬ Happy (x) ∨ Smile(x) ]
C. Someone is graduating
∃ x Graduating(x)
Someone is smiling ∃ x Smiling(x) … we will consider Someone is not
smiling and prove it is wrong i.e. assume ¬ [∃ x Smiling(x)]
 • Convert to CNF
Step:2 Standardized variables (Use different variable name for every
statement)
Answers:
A. All people who are graduating are happy
∀ X [¬ Graduating(X) ∨ Happy(X) ]
B. All happy people smile
∀ Y [¬ Happy (Y) ∨ Smile(Y) ]
C. Someone is graduating
∃ Z [ Graduating(Z) ]
Assume ¬ [ ∃ W Smiling(W) ]
 • Convert to CNF
Step:3 Move negation inwards
Answers:
A. All people who are graduating are happy
∀ X [¬ Graduating(X) ∨ Happy(X) ] …remain as it is
B. All happy people smile
∀ Y [¬ Happy (Y) ∨ Smile(Y) ] … remain as it is
C. Someone is graduating
∃ Z [ Graduating(Z) ] … remain as it is

Assume ¬ [ ∃ W Smiling(W) ] .. It will change to ∀ W (¬ Smile(W) )

 • Convert to CNF
Step:4 Skolemization (Remove ∃ operator)
Answers:
A. All people who are graduating are happy
∀ X [¬ Graduating(X) ∨ Happy(X) ] …remain as it is
B. All happy people smile
∀ Y [¬ Happy (Y) ∨ Smile(Y) ] … remain as it is
C. Someone is graduating
∃ Z [ Graduating(Z) ] … It will change to Graduating(A)

∀ W (¬ Smile(W) ) ….remain as it is
 • Convert to CNF
Step:4 Drop universal quantifier (Remove ∀ operator)
Answers:
A. All people who are graduating are happy
∀ X [¬ Graduating(X) ∨ Happy(X) ] … It will change to
¬ Graduating(X) ∨ Happy(X)……(Fact 1)
B. All happy people smile
∀ Y [¬ Happy (Y) ∨ Smile(Y) ] … It will change to
¬ Happy (Y) ∨ Smile(Y) …… (Fact 2)
C. Someone is graduating
Graduating(A)….. remain as it is….. (Fact 3)

∀ W (¬ Smile(W) ) ….it will change to (¬ Smile(W) …. (Fact 4)

 Resolution Tree

• Resolution algorithm is a rule used in Artificial Intelligence

(AI) for logical reasoning.
• It helps our AI system to figure out if the given statement is
logically proven from a set of known facts or not.
• It operates mainly on statements expressed in Conjunctive
Normal Form (CNF) and is most commonly used
in Propositional Logic and First-Order Predicate Logic.
• A Resolution Tree is a graphical representation of the
resolution proof method used in Artificial Intelligence and
Automated Theorem Proving to show how a contradiction is
derived from a set of clauses.
• A Resolution Tree is a tree structure showing step-by-step application
of the resolution rule between clauses until an empty clause (□) is
obtained.
• The empty clause indicates that a contradiction has been derived,
meaning the original statement is logically valid.
• Resolution Rule
• The resolution rule states:
If we have two clauses:
𝐴∨𝐵
¬𝐴∨𝐶
Resolving them gives:
𝐵∨𝐶
• Example of Resolution Tree
• Given Clauses
• P∨Q
• ¬P∨R
• ¬Q
• ¬R
• Step 1: Resolve Clause (1) and (3)
• P and (¬ P V R)
• Result: R
• Step 2: Resolve with Clause (2)

Result: R
Step 3: Resolve with Clause (4)

Result:
(Empty clause — contradiction)
• Resolution Tree Diagram

Explanation
•Leaves = Original clauses
•Internal nodes = Resolved clauses
•Root = Empty clause (□)
• Steps to Construct a Resolution Tree
• Convert statements into Clause Form (CNF).
• Negate the goal statement.
• Apply resolution rule between clauses.
• Create a tree showing derived clauses.
• If empty clause (□) appears → theorem is proved.

Advantages
•Systematic proof method
•Used in logic programming
•Basis of automated theorem provers
• Resolution Tree
If fact ‘F’ is to be proved then assume ‘¬F’ and start
It contradict all the other rules in knowledge base
The process stops, when it returns ‘NULL’
Prove that “Is someone smiling?” using resolution
So, start with what you want to prove with negative value

¬ Smile(W)

Now search into the list of rules for smile (i.e. Fact 2) and draw it in front
of first box, like

¬ Smile(W) ¬ Happy (Y) ∨ Smile(Y)

• Resolution Tree
Now contradict/compare above two boxes, positive smile and
negative smile get cancelled

¬ Smile(W) ¬ Happy (Y) ∨ Smile(Y)

¬ Happy (W) Y has been replaced by W

• Resolution Tree
Now find/search happy from the list of facts (i.e. fact 1)

¬ Smile(W) ¬ Happy (Y) ∨ Smile(Y)

¬ Happy (W) ¬ Graduating(X) ∨ Happy(X)

Now contradict above two boxes,

positive Happy and negative Happy get
¬ Graduating(W)
cancelled
X has been replaced by W
• Resolution Tree
Now find/search Graduation from the list of facts (i.e. fact 3)

¬ Smile(W) ¬ Happy (Y) ∨ Smile(Y)

¬ Happy (W) ¬ Graduating(X) ∨ Happy(X)

¬ Graduating(W) Graduating(A)
Now contradict above two boxes,
positive Graduation and negative Graduation
get cancelled
NULL
• Final Resolution Tree
Hence “Someone is not smiling” is Wrong, so “Someone is smiling” is Proved

¬ Smile(W) ¬ Happy (Y) ∨ Smile(Y)

¬ Happy (Y) ¬ Graduating(X) ∨ Happy(X)

¬ Graduating(W) Graduating(A)

NULL
• FOL-CNF-Resolution
Exercise:
Q. Consider the following facts
1. Ravi likes all kind of food
2. Apple and Chicken are food
3. Anything anyone eats and is not killed is food
4. Ajay eats peanuts and still alive
5. Rita eats that Ajay eats
• Convert to FOL
• Convert FOL to CNF
• Prove that “Ravi likes Peanuts” using resolution
• Draw resolution Graph/Tree
• FOL-CNF-Resolution
Exercise:
Q. Consider the following facts
1. It is a crime for an America to sell weapons to the enemy nations
2. Country Nono is an enemy of America
3. Nono has some missiles
4. All the missiles were sold to Nono by Colonel
5. Missile is a weapon
6. Colonel is an American
• Convert to FOL
• Convert FOL to CNF
• Prove that “Colonel is a Criminal” using resolution
• Draw resolution Graph/Tree
 First-Order Logic (FOL)
Representation and Inference
• Represent the following statements using First-Order Logic (FOL). Apply
an appropriate inference rule to derive the conclusion.
• All humans are mortal.
• Socrates is a human.
• All mortals are subject to death.
Using the above knowledge, determine whether Socrates is subject to
death .
• First-Order Logic (FOL) Representation
and Inference
• Let:
• Human(x): x is a human
• Mortal(x): x is mortal
• SubjectToDeath(x): x is subject to death
• s: Socrates
• 1. Represent the statements in FOL
• Statement 1: All humans are mortal.
– ∀x(Human(x)→Mortal(x))
• Statement 2: Socrates is a human.
– Human(s)
• Statement 3: All mortals are subject to death.
– ∀x(Mortal(x)→SubjectToDeath(x))
• Goal:
– SubjectToDeath(s)
2. Apply inference rules
• Step 1: From Statement 1
– ∀x(Human(x)→Mortal(x))
• Using Universal Instantiation for x=s:
– Human(s)→Mortal(s)
• We already know:
– Human(s)
• Therefore, using Modus Ponens:
– Mortal(s)
• So, Socrates is mortal.
• Step 2: From Statement 3
– ∀x(Mortal(x)→SubjectToDeath(x))
• Using Universal Instantiation for x=s:
– Mortal(s)→SubjectToDeath(s)
• Since we derived:
– Mortal(s)
• Using Modus Ponens:
– SubjectToDeath(s)
• Final Conclusion
• ∴SubjectToDeath(Socrates)
• Therefore, Socrates is subject to death.
• Inference Chain
– Human(Socrates)
– ⇓All humans are mortal
– Mortal(Socrates)
– ⇓All mortals are subject to death
SubjectToDeath(Socrates)
• Inference in First Order Logic
Inference- (conclusion/decision)
Inference engine:
It is component of the system that applies logical rules to the
knowledge base to deduce new information
There are two modes of inference engine
1. Forward chaining: start with the known facts and asserts new
facts
2. Backward chaining: start with goal and work backward to
determine what facts must be asserted so that the goal can be
achieved
• Inference in First Order Logic
1. Forward chaining:
Conclude from A and A => B to B
It is raining(A); if it is raining the road is wet(A=>B)
Infer: the road is wet(B)
2. Backward chaining
Conclude from B and A => B to A
The road is wet(A); if it is raining the road is wet(A=>B)
Infer: It is raining(A)
• Inference in First Order Logic
Forward chaining
• Let’s look at how a doctor goes about diagnosing a patient.
• He asks the patient for symptoms and then infers diagnosis from
symptoms.
• When based on the available data a decision is taken then the
process is called as the forward chaining
• It works from an initial state and reaches to goal state
• Inference in First Order Logic
• Inference in First Order Logic
Backward chaining
• Backward chaining : start with goal and work backward to
determine what facts must be asserted so that the goal can be
achieved
• Backward chaining is an inference strategy that works backward
from a hypothesis to a proof.
• You begin with a hypothesis about what the situation might be.
Then you prove it using given facts,
• e.g. a doctor may suspect some disease and proceed by inspection
of symptoms.
• In backward chaining terminology, the hypothesis to prove is
called the goal.
• Inference in First Order Logic
 Outline
• Planning with state space search
Types of planning
• Partial order planning
• Hierarchical planning
• Conditional planning
 Planning
• Planning is required for every task. Foe ex: reaching particular
destination requires planning

• To reach a particular destination, first we should find the best route and
then identify a set of actions to be done at a particular time is called as
planning.

• Planning is nothing but deciding set of actions to be performed , in

agent environment based on the perception to achieve the decided goal.
 Planning
The Planning Problem
Definition: Planning is the process of finding a sequence of
actions that leads from an initial state to a goal state.
Key Components:
Initial state
Goal state
Actions (with preconditions & effects)
Example:
Initial: Robot at location A, box at B
Goal: Box at C
Actions: Move, Pickup, Drop
 What is planning in
AI?
• What is planning in AI?
• The planning in Artificial Intelligence is about
the decision making tasks performed by the
robots or computer programs to achieve a
specific goal.
• The execution of planning is about choosing a sequence
of actions with a high likelihood to complete the
specific task.
 What is a Plan?
• We require domain description, task specification, and
goal description for any planning system. A plan is
considered a sequence of actions, and each action has its
preconditions that must be satisfied before it can act and
some effects that can be positive or negative.

• So, we have Forward State Space Planning

(FSSP) and Backward State Space Planning (BSSP) at
the basic level.
 Action Plan

• An action schema includes:

▪ Action names & parameter list (variables)
▪ Precondition: a conjunction of function-free positive literals. The
action variable must also appear in precondition
▪ Effect: a conjunction of function-free literals (positive or
negative)

• Add-list: positive literals

• Delete-list: negative literals
At(p) Sells(p, x)
• Example:
• Action: Buy(x) Buy(x)
• Precondition: At(p), Sells(p,
x) Have(x)
• Effect: Have(x)
Planning
Planning
Example: Air cargo transport
A problem involving transportation of air cargo
between airports
 Planning with State Space Search
• The most straightforward approach of planning algorithm is state
space search: Finding a sequence of actions by exploring the state
space
• Types of Search:
- Forward state space search (Progression)
- Backward state space search (Regression)

• The description of actions in planning problem, and specify both

preconditions and effects

• It is possible in search in both direction: either forward from initial to

backward from the goal

• We can also use the explicit action and goal representations, to derive
effective heuristic automatically.
 Forward State Space Search
• It is also called Progression. It starts from the initial state and searches in
the forward direction till we reach the goal.
• This is how the problem formulation looks like.
• Initial state: start state
• Actions:
- Applicable to the current state
- first action’s preconditions are satisfied, successor states are generated
- Add positive literals to add list and negative literals to delete list

• Goal test: To check if the current state is the goal state or not.
• Step cost: Cost of each step which is assumed to be 1.
FSSS starts from the initial state and applies actions to reach the next
state. It then checks whether this state is the goal state or not. If not,
it continues to apply other actions till the goal is reached.
 FSSS Algorithm

1. Compute whether or not a state is goal state

2. Find the set of all actions that are applicable to a state, and

3. Compute a successor state, that is the result of applying an action to

state

• Algorithm takes as input statement P = (O, s0, g) of a planning

problem P. (O contains list of actions)

• If P is solvable, the Forward search (O, s0, g) returns a solution plan;

otherwise it returns failure
 Algorithm for FSSS

1. Forward-Search(O, s0, g)

2. s ← s0

3. Π ← the empty plan

4. loop
1. if s satisfies g then return Π
2. applicable ← { a| a is ground instance of an operator in O, and
precond(a) is true in s}
3. if applicable = ϕ then return failure
4. Non-deterministically choose an action a є applicable
5. s ← (s, a)
6. Π ← Π.a
 Backward State Space Planning (BSSP)

• BSSP behaves similarly to backward state-space search. In

this, we move from the target state g to the sub-goal g, tracing
the previous action to achieve that goal.

• This process is called regression (going back to the

previous goal or sub-goal). These sub-goals should also be
checked for consistency. The action should be relevant in this
case.

• So for an efficient planning system, we need to combine the

features of FSSP and BSSP, which gives rise to target stack
planning which will be discussed in the next article.
 . Backward State Space Planning (BSSP)
• BSSS starting from goal state
• Using the inverse of actions to search backward for the
initial state
 . BSSS Algorithm
• Start at the goal
• Test the goal is initial state, otherwise
• Apply inverse of the planning operations to produce sub
goals
• The algorithm will stop, if we produce a set of sub goals
that satisfies the initial state
 . BSSS Algorithm
1. Backward-Search(O, s0, g)

2. Π ← the empty plan

3. loop
1. if s0 satisfies g then return Π
2. applicable ← { a| a is ground instance of an operator in O that is
relevant
for g}
3. if applicable = ϕ then return failure
4. Non-deterministically choose an action a є applicable
5. Π ← a. Π
6. g ← - 1(s, a)
Types of planning
 Total Order Planning
▪ Forward / Backward state space searches are forms of totally
ordered plan search
▪ Explore only strictly linear sequences of actions, directly connected
to the start or goal state

▪ Cannot take advantage of problem decomposition

 Partial Order Planner (Non linear
planning)
▪ A partial order planner is planning technique that decomposes a
problem into subproblems.
▪ It designs several independent subgoals and solves them with
several subplans.
▪ It generate various sub solutions for respective subgoals and then
combines subplans to achieve the whole plan which is the solution
for original problem.
 Partial Order Planning
▪ Works on several sub goals independently
▪ Solves them with sub plans
▪ Combine the sub plans
▪ Flexibility in ordering the sub plan
▪ Least commitment strategy: delaying a choice during searching
Representation of Action schema in planning
problem
The representation of actions collectively called as Action schema

1. The action name and the parameter list that serves to identify the action

2. The precondition: which is conjunction of function free positive literal. Any

variables in the precondition must appear in actions parameter list.

3. The effects: it is a conjunction of function free literals describing, how the

state changes, when the action is executed.
POP Example: putting on pair of shoes
A planner should be able to come up with two action sequence:

1. Rightsock followed by Rightshoe to achieve the first conjunct of the goal

2. Leftsock followed by Leftshoe for the second conjuct

Then the two sequences can be combined to yield the final plan
Simple Graphical Notation
POP vs TOP
 How to define Partial order planning
Components of a Plan

1. A set of actions
2. A set of ordering constraints
• A ˂ B reads “A before B” but not necessarily immediately before
3. ABset of causal links (protection intervals) between
p
actions
• A B reads “A achieves p for B” and p must remain true from the
A is applied
timeto the time B is
applied “RightSock RightSockOn
• Example
RightShoe
4. A set of open preconditions
• A precondition is open, if it is not achieved by some action in the
plan
The Initial Plan
Initial Plan contains:
Start:
PRECOND: None
EFFECT: Add all propositions that are initially
true
Finish:
PRECOND: Goal state
OrderingEFFECT: NoneStart < Finish
constraints
Casual links: {}
Open preconditions:
{preconditions of finish}
Successor function

Arbitrarily picks one open precondition p on an action B and

generates a successor plan, for every possible consistent way
of choosing an action A, that achieves p.

Consistency:
Casual link P B and the ordering constraints are
A
added
(A<()B Start < A A< Finish)

Resolve Conflict: add B < C or C < A

Goal Test:
There are no open preconditions
 Final Plan
The final plan has the following components:
Actions: {RightSock, RightShoe, LeftSock, LeftShoe, Start,
Finish}
Orderings: {RightSock < RightShoe, LeftSock < LeftShoe}
Open preconditions: {}
Links
RightSock RightSockOn RightShoe

LeftSock LeftSockOn LeftShoe

RightShoe RightShoeOn
Finish
LeftShoe LeftShoeOn Finish
 Hierarchical Planning
• Here the plans are organized in a hierarchical format. It works on
plan decomposition. Complex actions are decomposed into simpler or
primitive ones and it can be denoted with the help of links between various
states at different levels of the hierarchy. This is called operator expansion.

• In Hierarchical Planning, we find a sequence of primitive tasks by

decomposition of compound tasks, in order to reach the goal.
Example : One level planner
▪ Planning for ”Going to Goa this Cristmas”
■ Switch on computer
■ Start web browser
■ Open Indian Railways website
■ Select date
■ Select class
■ Select train
■ ... so on

▪ Practical problems are too complex to be solved at

one level
• Scenario: Planning a Trip from City A to City B
• Hierarchical Task Network (HTN) planning decomposes the high-level
goal into manageable sub-tasks.
• High-Level Goal: Travel from City A to City B
• Task Decomposition:
• Plan the mode of travel
– If distance < 500 km → Take a train
– If distance ≥ 500 km → Take a flight
• Booking & Preparation
– Book tickets (train/flight)
– Pack luggage
– Arrange transportation to the station/airport
• Execute the travel
– Go to the station/airport
– Board the train/flight
– Travel to City B
• Post-Arrival Tasks
– Collect luggage
– Arrange transport to the hotel/home
 Hierarchy in Planning
■ Hierarchy of actions
■ In terms of major action or minor action

■ Lower level activities would detail more precise steps for

accomplishing the higher level tasks.
 Example

■ Planning for ”Going to Goa this Cristmas”

■ Major Steps :
■ Hotel Booking
■ Ticket Booking
■ Reaching Goa
■ Staying and enjoying there
■ Coming Back
■ Minor Steps :
■ Take a taxi to reach station / airport
■ Have candle light dinner on beach
■ Take photos
■ Hierarchy of conditions reflect the intrinsic
difficulty
of achieving various conditions.
Indicated ▪ Actions required
Example:by criticality value. for “Travelling to Goa”:
▪ Opening [Link] (1)
▪ Finding flight (2)
▪ Buy Ticket (3)
▪ Get taxi(2)
▪ Reach airport(3)
▪ Pay-driver(1)
▪ Check in(1)
▪ Boarding plane(2)
▪ Reach Goa(3)
Example
■ st level Plan :
1
■ Buy Ticket (3), Reach airport(3), Reach
■ 2ndGoa(3)
level Plan :
■ Finding flight (2), Buy Ticket (3), Get taxi(2),
Reach airport(3), Boarding plane(2), Reach Goa(3)
■ 3rd level Plan (final) :
■ Opening [Link] (1), Finding flight (2), Buy
Ticket (3), Get taxi(2), Reach airport(3),
Pay-driver(1), Check in(1), Boarding plane(2), Reach
Goa(3)
 Hierarchical Planning : Example 2

Example:
Suppose you want to visit a friend in London but you have
limited amount of cash to spend.
First preference will be to find the airfares, since finding an
affordable flight which is most difficult part of task.
You should not worry about your drive way, planning a
route to the airport etc.. Until you are sure you have a flight
Structure of Hierarchical Planning
Hierarchical Task Networks (from here on abbreviated as
HTN) is a hierarchical planning technique where actions are
divided into different levels, or hierarchies.

There are different types of actions residing within these

hierarchies, one of then being High Level Actions
(HLA)

These HLAs could be any action that you can divide into
smaller actions called refinements. These refinements may be
sequences of actions or even other HLAs.

Refinement in turn are broken down into implementations

(called as primitive actions) which refer to any action that
has no further refinements or implementations
Hierarchical Planning
Hierarchical Planning
Hierarchical Planning
Hierarchical Planning
Hierarchical Planning
 Criticality
▪ A operation having minimum criticality can be
trivially achievable, i.e., the operations having very
less or no precondition.
▪ Example : Opening [Link]

▪ Similarly operation having many preconditions to

satisfy will have higher criticality.
Conditional Planning
• What’s Conditional Planning?
■ It’s a planning method for handling bounded indeterminacy.
•Bounded Indeterminacy – actions can have unpredictable effects,
but the possible effects can be determined.
• Ex: flip a coin (outcome will be head or tail)

■ It constructs a conditional plan with different branches for the

different contingencies that could arise.

■ It’s a way to deal with uncertainty by checking what isactually

happening in the environment at predetermined points in the
plan. (Conditional Steps)

■ Example:
•Check whether SFO airport is operational. If so, fly there;
otherwise, fly to Oakland.
• Three kind of Environments
■ Fully Observable
•The agent always knows the current state

■ Partially Observable
•The agent knows only a certain amount about the
actual state. (much more common in real world)

■ Unknown

•The agent knows nothing about the current state

Conditional Planning in Fully Observable
Environments

■ Agent used conditional steps to check the state of the

environment to decide what to do next.

■ Plan information stores in a library

• Ex: Action(Left) € Clean v Right

■ Syntax:
• If <test> then plan_A else plan_B
 Conditional Planning
• Definition: Planning under uncertainty with condition-dependent
actions
• Approach:
– Plans contain branches for different outcomes
• Example:
– Self-driving car encounters traffic jam (change route)

• Conditional Plans & Execution

• If-Else Structure: Handle uncertainties
• Example:
– Robot vacuum: If low battery → return to dock, else continue
• Applications & Challenges
• Applications: Robotics, autonomous systems
• Challenges: Handling large state spaces
 Example
• Robot Vacuum Cleaner
• A robot vacuum needs to clean a room efficiently while handling
uncertainties like obstacles and battery levels.
• Conditional Plan:
• Start Cleaning
– If obstacle detected, then change direction.
– If dust level high, then increase suction power.
– If low battery, then return to charging dock.
• Recharging
– If battery > 80%, then resume cleaning.
– If battery still low, then wait until fully charged.
• Completion
– If entire floor cleaned, then return to base and shut down.
– If missed spots detected, then re-clean specific areas.