Module 2

Chapter 4: Knowledge Representation Issues

1. Representations and Mappings
2. Approaches to Knowledge Representation
3. Issues in Knowledge Representation
4. The Frame Problem
Chapter 5: Using Predicate Logic
5.1 Representing Simple Facts in Logic
5.2 Representing Instance and ISA Relationships
5.3 Computable Functions and Predicates
5.4 Resolution
5.5 Natural Deduction

Chapter 6: Representing Knowledge Using Rules

6.1 Procedural Versus Declarative Knowledge
6.2 Logic Programming
6.3 Forward Versus Backward Reasoning
6.4 Matching
6.5 Control Knowledge

1. Build the Block diagram explaining Representation of Facts

Answer: Knowledge Representation Can Be Structured into Two Levels:
1. Knowledge Level – Describes Facts, Including an Agent's Behaviours and Goals.
2. Symbol Level: Where Representations of Objects at The Knowledge Level Are Defined
Using Symbols That Can Be Manipulated by AI Programs.
Representations of facts
• Two-way mappings between facts and their representations
These mappings are called representation mappings:
1. Forward mapping – Converts facts into representations.
2. Backward mapping – Converts representations back into facts.
• It illustrates how a program models reasoning by transforming initial facts into internal
representations, performing operations, and then using backward representation
mapping to generate the final facts.
• The dotted line represents abstract reasoning, while the solid line represents the program's
concrete reasoning process.

Namyapriya D, Asst Prof, CSE, KSIT

• If the program accurately models the reasoning process, applying backward mapping to the
output will yield correct final facts.

A significant example of fact representation is natural language (e.g., English sentences). AI

programs often require mapping functions between English sentences and internal
representations to process, understand, and generate meaningful information.

2. Convert the following sentence into the predicate logic

i. John likes all kinds of food.
ii. Apples are food.
iii. Chicken is food.
iv. Anything anyone eats and isn’t killed by is food.

3. Describe the Inheritable knowledge approach with an example

Namyapriya D, Asst Prof, CSE, KSIT

4. Convert the following sentence into the predicate logic
“Oscar is a cat”
English Sentence : Oscar is a cat
Logical representation: cat(Oscar)
Facts: All cats have tail
Representation:
∀x: cat(x) → hastail(x)
Using the deductive mechanism
hastail(Oscar)
Using the backward mapping, we write
Oscar has a tail.
5. Describe the Inference Knowledge Approach
Inferential Knowledge :
▪ Knowledge alone is insufficient unless there is an inference procedure to utilize it.
▪ Inference procedures operate in different ways:
1. Forward reasoning: Deduce new facts from known facts.
2. Backward reasoning: Work from a desired conclusion to check if it can be inferred from
existing facts.
▪ A common inference method mentioned is resolution, which uses a proof by contradiction
technique.
▪ Example :
▪ First statement: Describes conditions for an Infield-Fly based on various logical
conditions like the ball being fair, in the air, bases being occupied, etc.
▪ Second statement: Defines when an Out occurs based on a batter flying out under
specific conditions.

Namyapriya D, Asst Prof, CSE, KSIT

6. Illustrate the approaches to handle single-valued attribute
A single-valued attribute is one that can take only a unique value at a time.
Example: A baseball player can have only one height and be part of only one team at a time.
Approaches to Handling Single-Valued Attributes:
1. Use Temporal Intervals – If different values are asserted within the same time frame, it
triggers a contradiction.
2. Assume Present-Time Validity – Always replace the old value with the new one.
No Explicit Support (Logic-based systems) – Instead, knowledge bases can use axioms to
prevent multiple values.

7. Discuss the properties of attributes

8. Identify the various issues in the Knowledge representation

1. Important attributes
2. Relationship between attributes
3. An isa hierarchy of attributes
4. Techniques for reasoning about values
5. Single valued attributes
9. Convert the following sentence into the predicate logic
i. Max is a dog.
ii. Lily is a bird.
iii. Charlie is a rabbit.
iv. Bella is a fish.
Here is the predicate logic representation for the given sentences:
1. Max is a dog → Dog(Max)
2. Lily is a bird → Bird(Lily)
3. Charlie is a rabbit → Rabbit(Charlie)
4. Bella is a fish → Fish(Bella)
Each sentence is represented using a unary predicate indicating the category of the entity.
10 . Describe Frame Problem along with an Example
▪ The Frame Problem is a fundamental issue in Artificial Intelligence (AI) and knowledge
representation. It refers to the difficulty of specifying what does not change when an action

Namyapriya D, Asst Prof, CSE, KSIT

 occurs, without having to explicitly list all the unchanged facts. This problem arises when
designing AI systems that need to reason about the world dynamically.
▪ For example, consider a robot in a room:
• If the robot picks up an object, the object’s location changes (this needs to be
updated in the knowledge base).
However, many facts do not change—the color of the walls, the presence of other objects,
or the robot's own identity.
11. Explain Simple Relational Knowledge
• This method represents declarative facts using relational structures, similar to database
systems.
• Figure 4.4 provides an example of a relational system containing player statistics (Height,
Weight, and Bats-Throws).
▪ Knowledge Representation Issues
• This representation is simple but offers weak inferential capabilities on its own.
• For example, it cannot directly answer, "Who is the heaviest player?" without an additional
procedure to compute the answer.
• However, when combined with inference mechanisms, it becomes useful for decision-
making (e.g., choosing the best hitter against a pitcher).
• Since relational knowledge is already well-handled by database systems, it is not discussed
further.
• Many commercial products already incorporate these capabilities into knowledge
representation systems.

12. Describe Procedural Knowledge and Procedural Knowledge as rules

Procedural Knowledge
• While previous sections focused on static, declarative knowledge, this section
discusses procedural knowledge, which defines what to do and how to do it rather
than just stating facts.
• Procedural knowledge is often represented in code, like in LISP, and is executed
when needed.
• This form of knowledge is useful for performing tasks but has limitations:
• Low inferential adequacy: Difficult for a program to reason about another
program's behavior.
• Low acquisition efficiency: Updating/debugging large codebases becomes
cumbersome.
Example Comparison: Declarative vs. Procedural Representation

Namyapriya D, Asst Prof, CSE, KSIT

 • Figure 4.6 represents knowledge using attributes and values (declarative).

• Figure 4.8 represents the same knowledge using LISP code, demonstrating a
procedural approach.

•
• The LISP representation is more powerful because it explicitly refers to the node
whose value needs to be retrieved.
• However, declarative representation is easier to reason about, making it preferable
for straightforward knowledge storage.
Procedural Knowledge as Rules
• Challenges in reasoning with LISP have led to alternative ways of representing
procedural knowledge that can be easily manipulated by both programs and people.
• Production rules are a common method in AI for representing procedural knowledge.
• Figure 4.9 presents a production rule used by a baseball player to decide whether to
walk a batter.
• Production rules encode decision-making processes explicitly, making procedural
knowledge more structured and applicable in AI.
• How knowledge is used (i.e., manipulated by procedures) matters more than its
structure in distinguishing between procedural and declarative forms.

13. How do you Representing Simple Facts in Logic?

Namyapriya D, Asst Prof, CSE, KSIT

This section introduces propositional logic as a
method for representing world knowledge in AI.
Propositional logic is appealing because it is simple
to use and has a clear decision procedure. It allows
real-world facts to be represented as logical
propositions, which are written as well-formed
formulas (wff’s) in propositional logic.
Propositional logic helps express facts clearly and
allows inference, such as concluding that it is not
sunny if it is raining.
▪ This section introduces predicate logic as a
more expressive way to represent knowledge compared to propositional logic. It
demonstrates this through an example set of sentences about Marcus, Pompeians,
Romans, and Caesar.
Example Sentences:
1. Marcus was a man.
2. Marcus was a Pompeian.
3. All Pompeians were Romans.
4. Caesar was a ruler.
5. All Romans were either loyal to Caesar or hated him.
6. Everyone is loyal to someone.
7. People only try to assassinate rulers they are not loyal to.
8. Marcus tried to assassinate Caesar.
To solve all 8 sentences in predicate logic, we define predicates and translate the statements
accordingly.
Predicates Used:
man(x) → x is a man
pompeian(x) → x is a Pompeian
roman(x) → x is a Roman
ruler(x) → x is a ruler
loyal(x, y) → x is loyal to y
hates(x, y) → x hates y
assassinate(x, y) → x tried to assassinate y
Predicate Logic Representation
1. Marcus was a man.
man(Marcus)
2. Marcus was a Pompeian.
pompeian(Marcus)
3. All Pompeians were Romans.
∀x (pompeian(x)→roman(x ))
(For all x, if x is a Pompeian, then x is a Roman.)
4. Caesar was a ruler.
ruler(Caesar)
5. All Romans were either loyal to Caesar or hated him.

Namyapriya D, Asst Prof, CSE, KSIT

∀x (roman(x)→(loyal(x,Caesar)∨hates(x,Caesar)))
(For all x, if x is a Roman, then x is either loyal to Caesar or hates Caesar.)
6. Everyone is loyal to someone.
∀x ∃y loyal(x,y)
(For all x, there exists some y such that x is loyal to y.)
7. People only try to assassinate rulers they are not loyal to.
∀x,y (assassinate(x,y)→(ruler(y)∧¬loyal(x,y)))
(For all x and y, if x tries to assassinate y, then y must be a ruler, and x must not be loyal to y.)
8. Marcus tried to assassinate Caesar.
assassinate(Marcus,Caesar)assassinate(Marcus, Caesar)assassinate(Marcus,Caesar)
9. All men are people
∀x (man(x)→person(x))
14. Illustrate three ways to represent knowledge in logic.
Unary predicates represent
class membership (e.g.,
"Roman(x)" means x is a
Roman).
Explicit instance predicates
are used to directly state that
an object belongs to a class.
Subclass relationships use
implication rules, where if an
object is an instance of a
subclass (e.g., Pompeian), it
is also an instance of a
superclass (e.g., Roman).
Using the isa predicate
simplifies subclass relationships, but it requires an additional axiom to combine instance and
isa relations into a new instance relation. This axiom is general and does not need to be
separately defined for every new subclass relationship.
1. Using Unary Predicates
▪ Facts are represented using unary predicates like man(Marcus),
Pompeian(Marcus), and ruler(Caesar).
▪ Subclass relationships are handled using an implication rule (e.g., all
Pompeian(x) are also Roman(x)).
▪ Logical rules define relationships, such as Romans being either loyal to or
hating Caesar.
2. Using Explicit Instance Predicates
▪ Instead of unary predicates, objects are explicitly assigned to classes using
instance(x, Class).
▪ Example: instance(Marcus, Pompeian), instance(Caesar, ruler).

Namyapriya D, Asst Prof, CSE, KSIT

 ▪ A rule states that if an object belongs to a subclass, it also belongs to a superclass
(e.g., instance(x, Pompeian) → instance(x, Roman)).
3. Using Both Instance and ISA Predicates
▪ Introduces the isa predicate to define subclass relationships (isa(Pompeian,
Roman)).
▪ Axiom (Statement 6) generalizes the inheritance rule: If an object belongs to a
subclass and that subclass is related to a superclass, then the object also belongs
to the superclass.

15. What are Computable Functions?

Understanding What Can Be Solved by Machines
▪ Computable functions help define what problems can be solved algorithmically and
what problems are undecidable. This is foundational to computer science and AI.
• Computable function = A task a computer can do.
Example: Adding two numbers like 5 + 7.
• Used in AI to build logic and decision-making.
Example: If the temperature is above 30°C, turn on the fan.
• Can be simple or complex.
Simple: Sorting a list of names.
Complex: Recognizing faces in a photo.
• AI systems use many computable functions together.
Example: In a self-driving car, functions to recognize roads, detect people, decide speed,
etc.
• Not all problems are computable.
Some problems are too hard or take too long for any machine.
16. Explain Resolution Method
Resolution Method: Automated Logical Reasoning
▪ The resolution method is a rule of inference used in automated theorem proving and
logic programming. It is particularly useful in AI, databases, and verification
systems.
▪ Resolution is the foundation of AI, theorem proving, and logical inference.

Namyapriya D, Asst Prof, CSE, KSIT

 ▪ Resolution proof works by
refutation, meaning we assume the
negation of what we want to prove and
show that it leads to a contradiction.
▪ The logical steps use substitution and
simplification, leading to a
contradiction with known facts.
▪ Computation steps (e.g., age
comparison) are applied as necessary
to simplify the problem.

Namyapriya D, Asst Prof, CSE, KSIT

17. Mention the steps for Converting Statements into Clause form

Namyapriya D, Asst Prof, CSE, KSIT

18. Write an Algorithm to design Prepositional Resolution Algorithm

Namyapriya D, Asst Prof, CSE, KSIT

19. Design the unification Algorithm.

20. Describe Resolution in Predicate Logic Algorithm

21. Illustrate Natural Deduction

Natural deduction is a formal system of reasoning that provides a way to derive logical
conclusions from premises using a set of inference rules. It was developed to closely resemble
human reasoning in mathematics and logic.
It explains natural deduction as a method for proving statements in propositional and predicate
logic by applying introduction and elimination rules systematically.
Key Features of Natural Deduction
▪ Rule-Based Deduction
▪ Uses rules of inference to transform statements and derive new conclusions.
▪ These rules operate on logical connectives (e.g., AND, OR, NOT, IMPLIES).
Goal-Oriented Proofs
▪ Unlike resolution, which focuses on refuting contradictions, natural deduction builds
proofs step by step toward a conclusion.
Structured Proofs
▪ Proofs are structured like mathematical derivations, where each step follows
logically from the previous ones.

Namyapriya D, Asst Prof, CSE, KSIT

22. Distinguish Between Logic representation & PROLOG representation.

23. Consider the following sentences:

• John likes all kinds of food.
• Apples are food.
• Chicken is food.
• Anything anyone eats and isn’t killed by is food.
• Bill eats peanuts and is still alive.
• Sue eats everything Bill eats.
Answer the following questions:
(a) Translate these sentences into formulas in predicate logic.
(b) Prove that John likes peanuts using backward chaining.
(c) Convert the formulas of part (a) into clause form.
Solution:
(a) Translate the sentences into predicate logic
Let’s define some predicates and constants:
• Food(x): x is food
• Likes(john, x): John likes x
• Eats(x, y): x eats y
• KilledBy(x, y): x is killed by y
• Alive(x): x is alive
• Constants: John, Apples, Chicken, Peanuts, Bill, Sue
Now, the translation:
1. John likes all kinds of food.
∀x (Food(x) → Likes(John, x))
2. Apples are food.
Food(Apples)
3. Chicken is food.
Food(Chicken)
4. Anything anyone eats and isn’t killed by is food.
∀x ∀y [(Eats(x, y) ∧ ¬KilledBy(x, y)) → Food(y)]
5. Bill eats peanuts and is still alive.
Eats(Bill, Peanuts) ∧ Alive(Bill)
6. Sue eats everything Bill eats.
∀x (Eats(Bill, x) → Eats(Sue, x))

Namyapriya D, Asst Prof, CSE, KSIT

(c) Convert the formulas from part (a) into clause form
1. ∀x (Food(x) → Likes(John, x))
→ Clause form: ¬Food(x) ∨ Likes(John, x)
2. Food(Apples)
→ Already atomic
3. Food(Chicken)
→ Already atomic
4. ∀x ∀y [(Eats(x, y) ∧ ¬KilledBy(x, y)) → Food(y)]
→ CNF:
o Original: ¬(Eats(x, y) ∧ ¬KilledBy(x, y)) ∨ Food(y)
o ≡ ¬Eats(x, y) ∨ KilledBy(x, y) ∨ Food(y)
5. Eats(Bill, Peanuts) ∧ Alive(Bill)
→ Two atomic clauses:
o Eats(Bill, Peanuts)
o Alive(Bill)
6. ∀x (Eats(Bill, x) → Eats(Sue, x))
→ Clause form: ¬Eats(Bill, x) ∨ Eats(Sue, x)
Extra rule (assumed in (b)):
• ∀x ∀y [(Eats(x, y) ∧ Alive(x)) → ¬KilledBy(x, y)]
→ CNF: ¬Eats(x, y) ∨ ¬Alive(x) ∨ ¬KilledBy(x, y)

Namyapriya D, Asst Prof, CSE, KSIT

24. Distinguish between the procedural and declarative knowledge representation.

25. Distinguish Between Forward-Chaining & Backward-Chaining Rule Systems.

26. What is Logic Programming?

• Logic Programming is a paradigm where logical assertions are treated as programs.
• PROLOG is a popular
logic programming
language.
• A PROLOG program
consists of Horn clauses,
which contain at most
one positive literal.
• The figure provides two
representations: Logic
representation uses
logical implications.
• PROLOG representation
expresses the same logic
as rules and facts in a procedural format.

Namyapriya D, Asst Prof, CSE, KSIT

• Any logical expression can be converted into clause form, ensuring it adheres to Horn
clause rules.
• PROLOG programs consist only of Horn clauses, making them efficient and decidable
compared to full first-order logic.
• PROLOG's control structure:
o Uses backward reasoning to prove goals.
o Searches depth-first with backtracking.
o Reads top to bottom, left to right.
• Statements in PROLOG:
• Facts: Statements about specific objects (constants, no variables).
• Rules: Statements about classes of objects (contain variables).
27. Describe Forward-Chaining Rule Systems
• Definition: Forward-chaining systems are driven by incoming data rather than predefined
goals.
• Process: Follows a recognize-act cycle, where rules match a state description, modify the
state, and repeat.
• Complexity: Matching is more complex than in backward-chaining since fired rules can
remain valid and fire repeatedly.
• Challenges: Requires mechanisms to prevent repeated firings if the state remains
unchanged.
• Example System: OPS5 (Brownston et al., 1985) is an efficient forward-chaining system
with optimized matchers.
• Control Mechanisms: Uses strategies to prioritize rules and improve efficiency in rule
selection.
• Steps:
▪ Initialize with Facts: Start with a set of known facts.
▪ Evaluate Rules: Find rules where the conditions match the current facts.
▪ Infer New Facts: Apply the rule, derive the conclusion, and add it to the knowledge
base.
▪ Repeat: Continue evaluating and applying rules until:
▪ The desired goal is reached.
▪ No more rules can be applied.
▪ Terminate: Output the inferred conclusions or declare the goal unreachable.
Example : Suppose we want to determine if "Tom can eat in the restaurant."
1. Facts:
1. Tom has a reservation.
2. Tom is on time.
2. Rules:
1. Rule 1: If someone has a reservation and is on time, they are allowed entry.
2. Rule 2: If someone is allowed entry, they can eat in the restaurant.
3. Process:
1. Rule 1 matches: Tom has a reservation and is on time → Tom is allowed
entry.

Namyapriya D, Asst Prof, CSE, KSIT

 2. Rule 2 matches: Tom is allowed entry → Tom can eat in the restaurant.
4. Conclusion: Tom can eat in the restaurant.
28. Describe Backward-Chaining Rule Systems
• Definition: Backward-chaining systems start with a goal and work backward to determine
which facts or rules can satisfy it.
• Process: Given a query, the system searches for rules that can prove it, recursively checking
preconditions until known facts are reached.
• Efficiency: Generally, more efficient when the number of possible rules and facts is large,
as it only explores relevant paths.
• Complexity: Requires handling multiple rule dependencies and managing recursion depth
to avoid infinite loops.
• Example System: Prolog uses backward chaining to derive logical conclusions.
• Control Mechanisms: Uses goal-driven strategies, often requiring heuristics to optimize
search paths and reduce redundant queries.
• Steps:
• Identify the Goal: Start with a hypothesis or a goal to prove.
• Search for Rules: Find rules where the goal appears as the conclusion.
• Check Conditions: For each rule, verify if the conditions or premises are true.
• Recursion: If a condition is not known, treat it as a sub-goal and repeat the process to
establish its validity.
• Stop: If all conditions are satisfied, the goal is true. If no more rules apply and
conditions are unmet, the goal is false.
▪ Example: Suppose we want to determine if "Tom is allergic to peanuts."
1. Goal: Is "Tom is allergic to peanuts" true?
2. Rule: If someone eats peanuts and develops a rash, they are allergic.
1. Premises:
1. Tom ate peanuts.
2. Tom developed a rash.
3. Verification:
1. Check if "Tom ate peanuts" is true.
2. Check if "Tom developed a rash" is true.
4. If both conditions are true, conclude the goal.
29. Write a note on Hybrid Approach.
• Hybrid Approach: Some problems are best solved by combining forward and backward
chaining.
• Example: A medical diagnosis program can use forward chaining on patient data but switch
to backward chaining when additional information is needed.
• Efficiency: If most preconditions of a rule are met, backward reasoning can be used to
satisfy the remaining conditions instead of waiting for forward chaining.
• Reversible vs. Irreversible Rules:
o If both sides of a rule contain pure assertions, the rule can be used in both forward
and backward reasoning.

Namyapriya D, Asst Prof, CSE, KSIT

 o If the right side has arbitrary procedures, the rule is not reversible and can only be
used in one direction.
o Some production languages support only reversible rules, while others allow
irreversible ones, requiring a commitment to a specific direction at the time of
writing.
• Control Knowledge: Writing rules with direction control can enhance efficiency and
adaptability in reasoning systems.
30. Explain Conflict Resolution and its Approaches.
▪ Conflict resolution is the process of deciding the order in which matched rules are applied
in a production system.
▪ The matching process generates a list of applicable rules along with variable bindings.
▪ The search method determines rule application order, but integrating decision-making into
matching can be beneficial.
Three Approaches to Conflict Resolution:
1. Preference based on the rule that matched – Prioritize certain rules over others.
There are two primary ways to assign preferences based on rules in a production system:
1. Ordering Rules Explicitly
1. Rules are prioritized based on their predefined order, such as their appearance
in the system.
2. Example: PROLOG follows this approach by executing rules in sequence.
2. Prioritizing Special-Case Rules Over General Rules
1. Specific rules are given priority over more general rules to help solve problems
directly without additional search.
2. Example: In the water jug problem, certain rules were designated as special
cases of others.
3. This prevents unnecessary rule expansion, which could otherwise increase
search space.
How to Determine Rule Generality
A matcher can determine if one rule is more general than another using:
• Subset Precondition Matching: If one rule’s preconditions include all of another’s
plus additional conditions, it is more specific.
• Variable vs. Constant Matching: If a rule has variables where another has constants,
the first rule is more general.

2. Preference based on the objects that matched – Prioritize rules based on the objects
they involve.
In rule-based systems, prioritizing objects during the matching process can improve efficiency
by focusing on important objects first.
Key Approaches:
1. Matching Based on Object Importance
1. Example: ELIZA chatbot
1. ELIZA prioritized significant keywords in user input.

Namyapriya D, Asst Prof, CSE, KSIT

 2. If a sentence contained multiple known words, ELIZA responded based
on the most meaningful one.
3. Example: In "I know everybody laughed at me", both "I" and
"everybody" are known words.
4. Since "everybody" is rarer and more significant, ELIZA responds to it:
"Who in particular are you thinking of?"
2. Matching Based on Object Position (Short-Term Memory - STM)
1. This method prioritizes recently entered information over older data.
2. Example: In human decision-making, a person escaping a fire would prioritize
grabbing a baby over turning off the lights.
3. In AI, rules can be applied based on recent STM contents to improve reaction
speed and relevance.

3. Preference based on the action of the matched rule – Prioritize rules based on their
intended effects.
1. When multiple rules are ready to fire, a system can decide which to execute by:
2. Temporarily firing all rules to examine their outcomes.
3. Using a heuristic function to evaluate the resulting states.
4. Selecting the best outcome based on these evaluations.
5. Discarding or storing the less favorable results for future use.
Key Points:
6. This approach is similar to best-first search in AI.
7. It is often used as a conflict resolution strategy in rule-based systems.
8. A major drawback is that procedural control knowledge (e.g., in LISP) is hard to
modify.
9. AI systems that learn from experience prefer declarative control strategies for
flexibility.
31. Describe Control knowledge and syntax.
• Search in AI can be computationally
expensive, especially in large
knowledge bases with thousands of
rules.
• Control knowledge helps manage search
complexity by guiding which paths are
more likely to lead to a solution.
• It involves rules that determine the
usefulness of other rules based on
conditions.
• The syntax for a control rule (as shown in Fig. 6.8) helps classify rules as useful or useless
in specific contexts.
• This concept, also known as search control knowledge, helps avoid wasting time on
unproductive paths in reasoning.
1. Search Control Knowledge:

Namyapriya D, Asst Prof, CSE, KSIT

 • Helps guide the search process in AI systems to make it more efficient.
• Can take forms such as:
• Choosing preferable states over others.
• Selecting the right rules to apply in specific situations.
• Deciding the order in which subgoals should be pursued.
• Planning useful sequences of rule applications.
• Various representations exist, such as labeling and partitioning rules (e.g., in medical
diagnosis).
• Meta-knowledge, or knowledge about knowledge, is crucial for structuring problem-
solving processes.
2. SOAR System (Laird et al., 1987):
▪ Security orchestration, automation and response (SOAR) technology helps coordinate,
execute and automate tasks between various people and tools all within a single
platform.
• A cognitive architecture for human-like problem-solving in AI.
• Based on insights from short-term and long-term memory:
• Long-term memory stores productions (rules).
• Short-term (working) memory acts as a temporary buffer for perceptions and
facts.
• Problem-solving occurs as state-space traversal, where reasoning is done about
which states to explore and which rules to apply.
• Learning is achieved through chunking, storing important results for future use.
• Uses rules to express preferences for applying sequences of rules in problem-
solving.
• Learns from experience and builds new control rules to improve future decision-
making.
• Can implement search strategies like depth-first, breadth-first, or hill-climbing
by prioritizing certain states based on heuristic functions.
• Combines general strategies with domain-specific knowledge for more efficient
search control.
3. PRODIGY System (Minton et al., 1989):
• General-purpose problem solver that automatically constructs control rules to optimize
searches.
• Learns from experience, unlike SOAR, which learns from failures.
• Acquires control rules through:
• Programming (manually coded by developers).
• Static analysis of domain operations.
• Tracing its own problem-solving behavior.
• Handles subgoal interactions, avoiding decisions that might undo previous steps.
• Example: When building wooden furniture, sanding should be done before painting, as
painting first may require unnecessary repetition.
• PRODIGY builds explanations for why certain paths failed and uses that to improve
future search strategies.

Namyapriya D, Asst Prof, CSE, KSIT

32. Describe issues in Control Knowledge.
1. Utility Problem (Minton, 1988):
• Adding more control knowledge helps improve search efficiency, reducing unnecessary
node expansions.
• However, too many control rules can slow down decision-making because the system
must evaluate all rules before taking action.
• This can worsen performance instead of improving it, especially in systems that
automatically generate control knowledge.
2. Complexity of the Production System Interpreter:
• AI systems are shifting towards explicitly representing meta-rules (rules that define
when to apply other rules).
• This makes interpreters more complex over time, especially as systems evolve from
simple rule-based systems (like PROLOG) to more advanced ones.
• However, declarative representations of control knowledge help streamline interpreters
by removing hardcoded functions (e.g., LISP functions).
Exercise Problems:

Namyapriya D, Asst Prof, CSE, KSIT

Namyapriya D, Asst Prof, CSE, KSIT
Namyapriya D, Asst Prof, CSE, KSIT
Answers: Q1

Namyapriya D, Asst Prof, CSE, KSIT

Namyapriya D, Asst Prof, CSE, KSIT
Namyapriya D, Asst Prof, CSE, KSIT
Namyapriya D, Asst Prof, CSE, KSIT
Namyapriya D, Asst Prof, CSE, KSIT
Namyapriya D, Asst Prof, CSE, KSIT
9)

Namyapriya D, Asst Prof, CSE, KSIT

Namyapriya D, Asst Prof, CSE, KSIT
Namyapriya D, Asst Prof, CSE, KSIT
Namyapriya D, Asst Prof, CSE, KSIT
Exercise 1: Knowledge Base (WFFs):

1. ∀x ∀y (cat(x)∧fish(y)→likes_to_eat(x,y))

2. ∀x (calico(x)→cat(x))

3. ∀x (tuna(x)→fish(x))

4. tuna(Charlie)

5. tuna(Herb)

6. calico(Puss)

(a) Convert into Horn clauses

Horn clauses are implications with at most one positive literal.

Converted Horn Clauses:

1. likes_to_eat(x,y)←cat(x),fish(y)

2. cat(x)←calico(x)

3. fish(x)←tuna(x)

4. tuna(Charlie)

5. tuna(Herb)

6. calico(Puss)

(b) Convert to a PROLOG program

likes_to_eat(X, Y) :- cat(X), fish(Y).
cat(X) :- calico(X).
fish(X) :- tuna(X).
tuna(charlie).
tuna(herb).
calico(puss).
(c) PROLOG query: What does Puss like to eat?
?- likes_to_eat(puss, What).

Execution flow:
• calico(puss) → cat(puss)

Namyapriya D, Asst Prof, CSE, KSIT

 • tuna(charlie) → fish(charlie)
• tuna(herb) → fish(herb)
• likes_to_eat(puss, charlie) and likes_to_eat(puss, herb)
Output:
What = charlie ;
What = herb.

(d) Another PROLOG program that gives a different result

Let’s modify the rule so that Puss only eats herb.
likes_to_eat(X, herb) :- cat(X).
cat(X) :- calico(X).
fish(X) :- tuna(X).
tuna(charlie).
tuna(herb).
calico(puss).

Now Run

?- likes_to_eat(puss, What).

Out put :
What = herb.

2: Search Direction Factors

Forward search: from initial state → goal
Backward search: from goal → initial state
Factor Forward Backward
Known initial state Best May not be usable
Known goal
condition May need to generate Best
Branching factor Small from start Small from goal
Multiple goals Inefficient Targeted
Vague goals: prefer Specific goals: prefer
Goal specificity
forward backward

3. Determine whether the search should proceed forward or backward:

(a) Water Jug Problem
• Search Direction: Forward
• Reason: In the water jug problem, you start from a known initial state (e.g., jugs with
0 liters of water) and aim to reach a specific goal state (e.g., 4 liters in one jug).
Forward search is appropriate because the starting state is fully known and operations
can be applied progressively.
(b) Blocks World
• Search Direction: Forward
• Reason: Like the water jug problem, blocks world problems start from a known
configuration of blocks. The goal is to reach a specific arrangement, making forward
search suitable by applying legal moves until the goal is achieved.
(c) Natural Language Understanding
• Search Direction: Backward
• Reason: In natural language understanding, the system often starts with a sentence
and tries to infer possible interpretations or intentions, working backward from

Namyapriya D, Asst Prof, CSE, KSIT

 expected meanings to validate them. It involves goal-driven reasoning, so backward
search is more appropriate.

4. Program the interpreter for a production system (for solving water jug problems):
To solve this, you’d implement the following:
Production System Components:
1. Rule Table – A list of rules of the form:
o IF (condition) THEN (action)
o Example:
IF (Jug A has x liters and Jug B has y liters)
AND (pour A to B is valid)
THEN (update x, y based on pour)
2. Matcher – Compares current state to the LHS (Left-Hand Side) of rules to find
applicable rules.
3. Control Strategy – A mechanism to:
o Resolve conflicts if multiple rules match (e.g., prioritize based on goal
proximity).
o Select the next rule to apply.
4. Interpreter Loop – Executes:
while not goal_state(current_state):
matched_rules = match_rules(current_state, rule_table)
selected_rule = choose(matched_rules)
current_state = apply(selected_rule, current_state)

Namyapriya D, Asst Prof, CSE, KSIT