✅

2-MARK ANSWERS
⸻
1) What is knowledge and data?

Data refers to raw facts, numbers, symbols, or observations that have no

meaning by themselves. It is unprocessed information, such as values,
measurements, or simple text.
Knowledge is derived from data after applying interpretation, understanding,
and context. It represents processed and organized information that allows
reasoning, decision-making, and problem-solving. Knowledge connects data
with rules and experience to form meaningful conclusions.
⸻
2) Explain AI benefits.

AI provides numerous benefits:

• It performs high-speed computations that humans cannot complete
manually, improving efficiency in tasks like data analysis, prediction, and
automation.
• AI reduces human effort by automating repetitive and complex
tasks, thereby minimizing errors and increasing accuracy.
• It enables better decision-making by analyzing large amounts of
information and identifying useful patterns.
• AI contributes significantly in fields like healthcare, finance, robotics,
and transportation by improving productivity and reliability.
⸻
3) Define Backward Chaining.

Backward chaining is a goal-driven inference technique in which the

reasoning process begins with the desired conclusion and works backward to
find supporting facts. The system checks which rules can satisfy the goal, and
recursively proves the conditions of those rules until it reaches known facts in
the knowledge base. It is used in expert systems and logic programming for
efficient problem-solving.
⸻
4) List AI applications.

AI is widely used in several real-world domains like:

• Games, where AI competes with humans (Chess, Go, etc.).
• Natural Language Processing, which enables translation, speech
recognition, and chatbots.
• Robotics, where robots perform tasks such as assembly, surgery,
and exploration.
• Computer Vision, used in face detection, medical imaging, and
autonomous driving.
• Healthcare, finance, education, and e-commerce, enhancing
 decision-making and automation.
⸻

5) Describe any two characteristics of a problem.

1. Initial State: This represents the starting condition from which
the agent begins its search or planning process. Clearly defining the
initial state is essential for formulating the problem accurately.
2. Goal State: This specifies the required or desired final state.
The problem is considered solved when the agent reaches any state
that satisfies the goal conditions. The goal state guides search
strategies and evaluation functions.
⸻
6) What is Classical Planning in AI?

Classical planning assumes an environment that is fully observable,

deterministic, static, and has sequential actions. All states, actions, and
their effects are completely known to the agent. The planner generates an
ordered sequence of symbolic actions that transform the initial state into the
goal state. This approach is useful for well-structured, predictable
environments.
⸻
7) What is Intelligent Agent?

An intelligent agent is a system that perceives its environment using sensors

and acts upon it using actuators to achieve specific goals. It follows rational
decision-making principles, meaning it chooses actions that maximize its
performance measure. Intelligent agents may use learning, reasoning, and
planning to operate autonomously and effectively within their environment.
⸻
8) Define Search Strategy terminology.

A search strategy includes concepts such as:

• Node: A data structure that stores a state, its parent, action taken,
and path cost.
• Frontier (Open List): The set of nodes generated but not yet
expanded.
• Explored Set (Closed List): Contains states that have already been
visited to avoid repetition.
• Path Cost: The total cost incurred from the initial state to the current
node, used for evaluating optimality.
⸻
9) Explain Language Model in AI.

A language model predicts the likelihood of sequences of words and helps

machines understand and generate human language. It assigns probabilities to
sentences and guides tasks like translation, text completion, summarization,
and speech recognition. A strong language model captures grammar, meaning,
and contextual relationships among words.
⸻
10) Define Artificial Intelligence (AI) and explain its importance.

Artificial Intelligence is the study of creating machines capable of performing

tasks that require human intelligence, such as reasoning, learning, perception,
and problem-solving.
Importance: AI enhances productivity by automating complex tasks, supports
decision-making using data-driven insights, and plays a vital role in modern
technologies like autonomous vehicles, medical diagnosis, robotics, and
communication systems.
⸻
11) What are the primary goals of AI?

The goals of AI include:

• Developing systems that can act intelligently and autonomously.
• Understanding the principles of human intelligence to replicate them
in machines.
• Solving real-world complex problems through rational decision-
making.
• Building agents that learn from experience and adapt to dynamic
environments.
⸻
12) Define heuristic search and explain its role.
Heuristic search uses approximate cost estimates (heuristics) to guide the
search toward the goal more efficiently than uninformed search. It reduces the
time and space needed by exploring the most promising states first. It is
essential for solving large and complex problems where blind search is
impractical.
⸻
13) Distinguish between knowledge & data.
Data Knowledge
Raw, unprocessed facts without Processed and meaningful
context information
Does not support reasoning Helps in reasoning and decision-
making
Example: numbers, symbols Example: rules, relations, concepts
No interpretation Derived through experience and
analysis
⸻
14) What is NLP and its primary goals?

Natural Language Processing (NLP) enables computers to understand,

interpret, and generate human language.
Primary goals include:
• Language Understanding: Allowing machines to comprehend human
 input.
• Language Generation: Producing meaningful sentences and
responses.
• Information Extraction: Identifying useful knowledge from
unstructured text.
⸻
15) Write a note on categories and objects.
In knowledge representation, categories are classes or groups that share
common properties. They help organize knowledge by grouping similar objects
together.
Objects are individual instances that belong to categories. Each object has
unique attributes but also inherits features of the category it belongs to. This
structure is essential for reasoning, classification, and semantic networks.
⸻
16) Explain Unification with example.

Unification is a process used in logic to make two expressions identical by

finding suitable substitutions for variables.
Example:
To unify P(x, a) and P(b, y), we substitute x = b and y = a, making both
expressions identical.
Unification is crucial in inference algorithms such as resolution.
⸻
17) Describe the impact of Information Extraction (IE).

Information Extraction automatically identifies useful information from large,

unstructured text.
• In healthcare, IE extracts symptoms, diagnoses, and reports to
support faster medical decisions.
• In finance, it identifies trends from reports for accurate forecasting.
• In e-commerce, it extracts product details and customer sentiment
to improve recommendations.
This improves efficiency, accuracy, and decision-making in multiple
industries.
⸻
18) Define Artificial Intelligence.

AI is the branch of computer science that focuses on designing machines

capable of performing tasks requiring human-like intelligence such as
reasoning, learning, perception, and decision-making. It aims to create systems
that behave rationally and autonomously.
⸻
19) What is Production System?

A production system consists of:

• A set of production rules in IF–THEN format,
• A working memory storing the current problem state,
 • A control mechanism that decides which rule to apply.
It is widely used in problem-solving agents, expert systems, and planning
models.
⸻
20) What is FOPL?

First-Order Predicate Logic (FOPL) is a powerful knowledge representation

system that uses predicates, variables, constants, and quantifiers to express
relationships. It allows representation of complex statements about objects and
their properties, making it more expressive than propositional logic.
⸻
21) Define heuristic search.

Heuristic search uses domain knowledge in the form of heuristics to estimate

Text
the cost of reaching the goal. It prioritizes exploring states that appear more
promising, making the search faster and more efficient than uninformed
methods. Algorithms like A*, Greedy Search, and Hill Climbing rely on
heuristics.
⸻
22) What is Explainable AI?

Explainable AI (XAI) focuses on making the internal decision-making process of

AI systems clear and understandable to humans. It helps users trust AI
decisions by providing transparency, reasoning steps, and justification for the
output, especially in critical fields like healthcare, law, and finance.
⸻
23) What do you mean by Agent?

An agent is an entity that perceives its environment using sensors and acts
upon it using actuators. It follows rational behavior rules, meaning it selects
actions that maximize its performance measure. Agents can be simple reflex-
based or intelligent, goal-driven entities.
⸻
24) What is Hierarchical Planning?

Hierarchical planning divides a complex problem into smaller sub-problems by

representing actions at multiple levels of abstraction. High-level tasks are
decomposed into simpler, low-level actions. This makes planning easier, more
organized, and more efficient in large domains.
⸻
25) Explain Game Theory in AI.

Game theory studies decision-making in competitive environments involving

multiple agents attempting to maximize their own outcomes. AI uses game
theory to design strategies such as minimax, analyze opponent behavior, and
solve adversarial problems like chess, economics, and negotiation tasks.
 3-MARK ANSWERS

1) Explain Water Jug Problem in detail.

The Water Jug Problem is a classic AI state-space search problem. You are
given two jugs with specific capacities (for example, 4 liters and 3 liters), and
the goal is to measure an exact amount of water using only these jugs.

A problem is defined by:

• States: Represent amounts of water in both jugs, written as (x, y).
• Initial State: Usually (0, 0), meaning both jugs are empty.
• Goal State: Any state where one jug contains the required amount,
e.g., (2, y).
• Actions/Operators:
• Fill a jug completely
• Empty a jug
• Transfer water from one jug to another until one becomes
full or the other becomes empty

The problem demonstrates how search algorithms explore the state

space until a solution sequence of actions is found.

2) Describe the A Algorithm.*

A* is an informed search algorithm that combines the advantages of Uniform

Cost Search and Greedy Best-First Search. It uses an evaluation function:
f(n) = g(n) + h(n)
• g(n): Actual cost from the start state to node n
• h(n): Heuristic estimate from n to the goal

A* selects the node with the lowest f(n) value, ensuring optimal and
complete results if the heuristic is admissible (never overestimates).
A* explores promising paths first while still guaranteeing the best solution,
making it efficient for pathfinding and planning problems such as route
navigation, robot movement, and puzzle solving.

⸻
3) Discuss in brief the various issues in Knowledge Representation.

The major issues include:

1. Representation of Complex Knowledge: Some knowledge (like
emotions, uncertainty, temporal information) is hard to represent
symbolically.
2. Choosing the Right Level of Granularity: Too much detail
makes reasoning slow, while too little detail makes solutions inaccurate.
3. Incomplete or Uncertain Knowledge: Real-world environments
often contain uncertain or missing information.
4. Multiple Representations: The same concept can be
represented in different ways; choosing a consistent scheme is
challenging.
5. Efficiency: Representations must support efficient storage,
retrieval, and reasoning.

4) Explain the MINIMAX Procedure.

The MINIMAX procedure is used in game-playing AI to make optimal decisions

in adversarial environments, such as chess or tic-tac-toe.
• The game tree has MAX nodes (AI’s turn) and MIN nodes
(opponent’s turn).
• MAX tries to maximize the score, while MIN tries to minimize it.
• The leaf nodes contain utility values that represent the outcome of
the game.
The MINIMAX algorithm recursively evaluates all possible moves, assuming
the opponent plays optimally. The move that leads to the best guaranteed
outcome is selected by the AI.

5) Convert the statements to FOPL and prove.

i) John likes all kinds of food.

FOPL: ∀x Food(x) → Likes(John, x)

ii) Apple and vegetable are food.

Food(Apple)
Food(Vegetable)

iii) Anil eats peanuts and is still alive.

Eats(Anil, Peanuts)
Alive(Anil)

Proof Idea: Using universal instantiation on statement (i), since Apple and
Vegetable are food, it follows that:
Likes(John, Apple)
Likes(John, Vegetable)

Thus conclusions logically follow.

6) Describe how heuristic functions impact performance.

A heuristic function estimates the cost to reach the goal and significantly
improves efficiency:
• Guides the search: Instead of exploring all nodes, it directs the
algorithm toward promising paths.
• Reduces search space: Good heuristics drastically cut unnecessary
exploration.
• Improves speed and accuracy: Algorithms like A*, Greedy Search
become optimal and faster with admissible heuristics.
A poor heuristic slows down the process, while a well-designed heuristic
leads to near-optimal performance.

7) Explain forward chaining and backward chaining with example.

Forward Chaining:
• Starts from known facts and applies rules to infer new facts until the
goal is reached.
• Example:
• Rules: If A → B, If B → C
• Fact: A
• Forward chaining derives B, then C.

Backward Chaining:
• Starts from the goal and works backward to verify whether the goal
can be satisfied using available facts and rules.
• Example:
• Goal: C
• Rule: If B → C
• Check if B is true or can be derived from another rule.
⸻

8) What is Best-First Search, and how does it differ from DFS & BFS?

Best-First Search (BeFS) selects the next node to explore based on a heuristic
evaluation function. It always expands the “best-looking” node first.

Difference from other algorithms:

• DFS: Goes deep into the tree without regard to cost; BeFS considers
heuristic values.
• BFS: Expands nodes level by level; BeFS chooses node based on
estimated closeness to goal.
• BeFS is more efficient and goal-directed compared to blind search
strategies.

9) Explain the MINIMAX Procedure.

(Already answered in Q4, but here is another 3-mark version)

MINIMAX evaluates game states by considering both players’ optimal
strategies. It builds a game tree, assigns utility values at terminal states, and
propagates them upward.
• MAX chooses the move with the highest value.
• MIN chooses the move with the lowest value.
The AI chooses the action that ensures the best guaranteed outcome even
in the worst-case scenario.

10) Define CSP and explain the role of constraints.

A Constraint Satisfaction Problem (CSP) consists of:

• A set of variables,
• A set of domains (possible values),
• A set of constraints restricting allowable value combinations.

Role of constraints:
• They eliminate invalid combinations early.
• Reduce the search space dramatically.
• Ensure the final solution satisfies all required conditions.
Examples include map coloring, scheduling, and Sudoku.
⸻

11) Explain generate and test heuristic algorithm.

Generate-and-test works in two phases:

1. Generate: Produce candidate solutions using heuristics or
randomly.
2. Test: Evaluate each candidate to check whether it meets the
goal conditions.

This method is simple but effective for search problems where the
solution space is large, and constraints can eliminate invalid solutions
quickly. It is used in puzzle solving, optimization, and design tasks.

12) Write the characteristics of Intelligent Agents.

Important characteristics include:

• Autonomy: Ability to operate without human intervention.
• Reactivity: Responds to environmental changes promptly.
• Pro-activeness: Takes initiative to achieve goals.
• Social ability: Interacts with other agents or humans.
• Goal-oriented behavior: Selects actions that maximize success.

13) Write the benefits of Artificial Intelligence.

AI provides several advantages such as:

• Automation: Reduces human effort in repetitive or dangerous tasks.
• Accuracy: Helps make precise predictions and diagnoses.
• High Efficiency: Machines can process data faster than humans.
• Enhanced Decision-Making: AI evaluates multiple possibilities
quickly.
• Improved services: Used in robotics, healthcare, finance, and
transportation for better outcomes.

14) Explain Constraint Satisfaction Algorithm.

A constraint satisfaction algorithm solves CSPs by:

 1. Selecting a variable with the smallest domain or highest
constraint.
2. Assigning a value consistent with constraints.
3. Backtracking if the assignment violates a constraint.

Advanced methods include forward checking, constraint propagation,

and arc-consistency, which reduce the search space and make solving
faster and more efficient.

15) Construct the truth tables.

i) p v q~ q ->p

p q ¬q p ∨ ¬q (p ∨ ¬q) → p
T T F T T
T F T T T
F T F F T
F F T T F

ii) (~( p^ q)v r)-> ~ p

p q r p∧q ¬(p∧q) ¬(p∧q) ¬p Final
∨r
T T T T F T F F
T T F T F F F T
T F T F T T F F
T F F F T T F F
F T T F T T T T
F T F F T T T T
F F T F T T T T
F F F F T T T T

4 MARK ANSWERS — SET 1 (Q1 to Q8)

1) Explain Hill Climbing Algorithm in detail.

Hill Climbing is a heuristic search algorithm that continuously moves in the

direction of increasing value (uphill) to reach the best solution. It is inspired by
climbing a hill where the objective is to reach the highest peak.

Key Steps:
1. Start with an initial state (random or selected).
2. Evaluate all neighboring states of the current state.
3. Move to the neighbor with the highest heuristic value (best
improvement).
4. Repeat until:
• No better neighbors exist → local maximum reached
• Goal is reached
• A plateau or ridge causes algorithm to get stuck

Types of Hill Climbing:

• Simple Hill Climbing: Chooses the first better neighbor encountered.
• Steepest-Ascent Hill Climbing: Examines all neighbors and selects
the best one.
• Stochastic Hill Climbing: Randomly selects among better moves to
avoid local maxima.

Drawbacks:
• Gets stuck in local maxima, plateaus, and ridges.
• No backtracking—once going uphill stops, search ends.

Hill Climbing is commonly used in optimization, scheduling, and machine

learning parameter tuning.

2) Explain Monte Carlo Tree Search (MCTS) technique.

Monte Carlo Tree Search is a decision-making algorithm used in games (e.g.,

Go, Chess variants). It explores the game tree using random simulations to
estimate the most promising moves.

MCTS follows four main steps:

1) Selection

Start at the root node and recursively select child nodes using a strategy like
UCB1 until a node with unexplored moves is found.

2) Expansion

Add a new child node by selecting an unvisited action from the current state.
3) Simulation (Rollout)

From this new node, play a random sequence of moves until a terminal state is
reached. This approximates the potential outcome.

4) Backpropagation

Update statistics (wins, visits) for all nodes on the path back to the root.

Advantages:
• Does not require full game tree exploration.
• Works well with enormous search spaces (e.g., Go).
• Balances exploration and exploitation.

Applications:

Used in AlphaGo, board games, and planning systems.

3) Define CSP. Solve SEND + MORE = MONEY using CSP.

Definition:

A Constraint Satisfaction Problem (CSP) is defined by:

• A set of variables
• A domain of values for each variable
• A set of constraints restricting allowable combinations

SEND + MORE = MONEY (Cryptarithmetic CSP)

Variables:

S, E, N, D, M, O, R, Y

Domains:

0–9 (all digits), but with constraints:

• S≠0
• M≠0
• All letters represent unique digits

Equation:
 SEND
+ MORE
------
MONEY

9567
+ 1085
------
10652

Thus: S = 9,E = 5 ,N = 6 ,D = 7,M = 1,O = 0,R = 8,Y = 2

4) Construct truth tables for:

i) i) p^(~ q v q)
Since (~ q v q)is always TRUE, the entire expression simplifies to p.
p q ¬q ¬q ∨ q p ∧ (¬q ∨ q)
T T F T T
T F T T T
F T F T F
F F T T F

⸻
ii) ii)~ (p v q) v (~ p^~ q)
p q p∨q ¬(p∨q) ¬p ¬q ¬p ∧ Final
¬q Expres
sion
T T T F F F F F
T F T F F T F F
F T T F T F F F
F F F T T T T T

5) Explain Means–Ends Analysis (MEA) algorithm.

Means–Ends Analysis is a search strategy that reduces the difference between

the current state and the goal state by selecting appropriate actions.

Steps of MEA:
1. Identify the differences between the current state and goal
state.
2. Select an operator that reduces the most significant difference.
3. Check preconditions of that operator.
4. If preconditions are not satisfied:
 • Treat them as subgoals
• Apply MEA recursively
5. Apply the operator and continue until the goal is achieved.

Features:
• Uses problem decomposition
• Works well for complex tasks such as theorem proving and robot
planning
• Reduces unnecessary exploration by focusing on differences

MEA is used in GPS (General Problem Solver).

6) Describe any two approaches of representing knowledge.

1) Semantic Networks
• Graph-based representation using nodes for objects/concepts and
edges for relationships.
• Supports inheritance (e.g., A robin is a bird → birds can fly → robin
can fly).
• Easy visualization and efficient querying.

2) Frames
• Data structures that store attribute–value pairs.
• Represent knowledge about objects, events, or situations.
• Support default values and inheritance.
• Used in natural language understanding and expert systems.

7) Explain Mental and Modal Object Logics.

Mental Logic:

Mental logic represents knowledge based on human reasoning patterns.

Humans naturally use mental rules like implication, negation, and conjunction. It
attempts to model how humans actually think rather than how machines
compute.

Modal Logic:

Modal logic extends classical logic with modal operators:

• □ (necessarily)
• ◇ (possibly)
 It helps represent beliefs, intentions, obligations, and uncertainties.
Examples:
• □P → P is necessarily true
• ◇Q → Q is possibly true

Modal logic is essential for representing agent knowledge, time, beliefs,

actions, and intentions in AI.

8) Explain Knowledge-Based Agent and the operations performed by KBA.

A Knowledge-Based Agent (KBA) uses a knowledge base to make decisions. It

stores facts, rules, and relationships to reason about the environment.

Operations performed by a KBA:

1) Tell Operation
• Updates the knowledge base with new information from the
environment.
• Example: “Tell the agent that the room is dirty.”

2) Ask Operation
• The agent queries the KB to infer new facts or make decisions.
• Example: “Is there danger ahead?”

3) Inferencing
• The agent applies logical rules (forward chaining or backward
chaining) to derive conclusions.

Characteristics:
• Reasoning, logical thinking
• Ability to handle incomplete information
• Makes decisions based on stored knowledge

KBA forms the foundation of expert systems and intelligent agents.

9) What are the different types of Agent? Explain the advantages and
disadvantages of AI.

Types of Agents:

1) Simple Reflex Agents

Act only on the basis of the current percept.
• Use condition–action rules like “if dirty → clean”.
• Do not consider history.

2) Model-Based Reflex Agents

Maintain an internal state to track invisible aspects of the environment.

• Can handle partially observable environments.

3) Goal-Based Agents

Select actions by considering desired outcomes (goals).

• More flexible than reflex agents.

4) Utility-Based Agents

Choose the action that maximizes the utility (happiness, safety, profit).
• Useful when goals conflict.

5) Learning Agents

Improve their performance over time by learning from experience.

• Adapt to changing environments.

Advantages of AI:
• High efficiency and speed: Can perform repetitive tasks faster and
more accurately than humans.
• Reduced human error: AI systems follow algorithms and avoid
emotional or careless mistakes.
• 24/7 Availability: Machines don’t require breaks.
• Improved decision-making: AI analyzes large data sets and
identifies patterns humans may miss.

Disadvantages of AI:
• High development cost: Requires expensive hardware, data, and
skilled developers.
• Job displacement: Automation can replace human workers.
• Lack of creativity: AI cannot replicate true human creativity or
emotions.
• Dependence: Overuse of AI may reduce human critical thinking.

⸻
10) Analyze various planning approaches in detail.

Planning is the process of deciding a sequence of actions to achieve a goal.

1) Classical Planning
• Assumes a fully observable, deterministic, static world.
• States, actions, and effects are precisely known.
• Uses STRIPS-like operators.

2) Hierarchical Planning (HTN)

• Breaks a large problem into subtasks.
• High-level actions → decomposed into simpler steps.
• Efficient for real-world robotics and workflows.

3) Conditional Planning
• Handles uncertainty by creating a plan with conditions:
“If X happens, do A; otherwise, do B.”
• Useful in unpredictable environments.

4) Partial-Order Planning
• Does not fix the exact order of actions unless necessary.
• Multiple valid action sequences exist.
• Flexible and avoids unnecessary ordering constraints.

5) Probabilistic Planning
• Accounts for uncertain effects of actions.
• Uses Markov Decision Processes (MDPs).
• Appropriate for robots navigating real environments.

Each approach is suited to different types of problems depending on the

degree of uncertainty, observability, and complexity.

11) Compare and contrast BFS with A and other informed searches.*

Breadth-First Search (BFS):

• Uninformed search.
• Explores level by level.
• Guarantees optimal solution only when all step costs are equal.
• High memory usage.

A* Search (Informed Search):

• Uses evaluation function f(n) = g(n) + h(n).
• Combines cost so far (g) and heuristic (h).
 • Guarantees optimality if heuristic is admissible.
• More efficient than BFS for large search spaces.

Greedy Best-First Search:

• Uses only heuristic: f(n) = h(n).
• Fast but not optimal.
• May follow a misleading path.

Comparison Summary:
Feature BFS A* Greedy BFS
Uses Heuristic No Yes Yes
Completeness Yes Yes Not
guaranteed
Optimality Sometimes Always (with No
good heuristic)
Speed Slow Fast Very fast
Memory High High Moderate
12) Discuss the role of logic in KR, including propositional logic and first-
order logic.

Logic is fundamental in Knowledge Representation (KR) because it allows AI

systems to store, infer, and manipulate knowledge systematically.

Role of Logic in KR:

• Provides a formal language to represent facts.
• Allows reasoning, deriving new facts logically.
• Supports consistency checking of knowledge.
• Enables building expert systems and intelligent agents.

Propositional Logic (PL):

• Represents knowledge using simple propositions like P, Q, R.
• Connectives: ∧, ∨, →, ↔, ¬
• Suitable for simple domains without relationships.
• Easy to compute but not expressive enough for real-world
knowledge.

First-Order Logic (FOL):

• Extends PL by adding:
• Predicates
• Quantifiers (∀, ∃)
 • Variables and functions
• Represents relationships between objects.
• Much more expressive and closer to natural language.
• Suitable for planning, diagnosis, and reasoning tasks.

Example:

PL: “John is a student” → S

FOL: Student(John)

FOL allows representing general rules and relationships, making it essential for
AI reasoning.

13) What is classical planning in artificial intelligence?

Classical planning assumes a simplified world with clear and predictable

behavior.

Key Characteristics:
• Fully observable: The agent knows everything about the current
state.
• Deterministic: Actions have fixed outcomes.
• Static environment: World does not change unless the agent acts.
• Sequential actions: Actions occur one after another.

How Classical Planning Works:

• Represents states and actions symbolically.
• Uses operators with preconditions and effects (STRIPS).
• Plans a sequence of actions that transforms the initial state into the
goal state.

Example Use Cases:

• Robot arm rearranging blocks
• Navigation in structured maps
• Scheduling tasks

Classical planning is the foundation for more advanced planning

approaches.

14) Define Information Retrieval (IR) and explain its significance.

Definition:

Information Retrieval (IR) refers to the process of locating and retrieving

relevant information from large collections such as documents, databases, web
pages, and datasets.

Significance of IR:
• Manages large volumes of data: Essential in the era of big data and
digital content.
• Improves information accessibility: Helps users find the right
information quickly using indexing, search engines, and ranking algorithms.
• Used in major applications: Web search engines (Google), digital
libraries, e-commerce search, recommendation systems.
• Supports decision-making: Provides quick access to relevant
knowledge for business, medicine, education, and research.

Good IR systems use ranking algorithms, NLP, and machine learning to

deliver accurate results to the user.

15) Give a real-world example solved using MEA with initial state, goal, and
steps.

Problem: Robot moving a block from Table to Shelf using MEA

Initial State:
• Block A is on the table.
• Robot arm is empty.

Goal State:
• Block A is on the shelf.

Steps using MEA:

1. Difference: Block A is not on the shelf.
• Operator needed: Place(A, Shelf)
• Preconditions: Robot must be holding A.
2. Subgoal: Robot should hold Block A.
• Operator: Pick(A)
• Preconditions: Arm must be empty, A must be clear.
3. Actions:
• Ensure A is clear → it is clear.
• Pick(A) → robot holds A.
• Move arm to shelf.
• Place(A, Shelf).
Final Result:

Robot achieves the goal by reducing differences step-by-step through MEA.

16) Explain Means–End Analysis Algorithm.

(Already answered earlier but here is a 4-mark expanded version.)

Means-End Analysis is used to reduce the difference between the current state
and the goal by selecting operators that minimize this difference.

Steps in MEA:
1. Identify differences between current and goal states.
2. Choose an operator that reduces the biggest difference.
3. Check operator preconditions:
• If preconditions are not met, set them as subgoals.
4. Apply the operator once preconditions are satisfied.
5. Repeat until all differences are eliminated.

Features:
• Focuses on ends (goal) and means (operators to reach that goal).
• Uses recursive decomposition.
• Improves efficiency by avoiding unnecessary explorations.

MEA is used in the GPS system, planning, robotics, and problem-solving

tasks.

17) Difference between predicate logic and propositional logic.

Propositional Logic (PL):

• Deals with simple statements that are either true or false.
• Uses propositional variables: P, Q, R…
• Connectives used: AND, OR, NOT, IMPLIES.
• No internal structure to statements.
• Cannot express relationships or properties of objects.

Predicate Logic (FOL / Predicate Calculus):

• Uses predicates to express properties and relations.
• Includes variables, quantifiers (∀, ∃), functions, constants.
• Can represent complex knowledge:
• Example: Likes(John, Mango)
• Much more expressive and descriptive than propositional logic.
• Suitable for real-world reasoning and AI knowledge representation.
Comparison Table:
Feature Propositional Logic Predicate Logic
Expressiveness Low High
Can represent No Yes
relationships?
Uses quantifiers? No Yes (∀, ∃)
Example P∨Q Loves(x, y)
Suitable for Simple problems Complex KR &
reasoning

18) Difference between Breadth-First Search and Depth-First Search.

Breadth-First Search (BFS):

• Explores nodes level by level.
• Uses a queue (FIFO).
• Guarantees shortest path if cost is uniform.
• Memory requirement is high (stores all children in frontier).
• Complete and optimal (under equal cost).

Depth-First Search (DFS):

• Explores deep into the tree before backtracking.
• Uses stack (LIFO) or recursion.
• May get stuck in infinite depth.
• Memory efficient — stores only a path at a time.
• Not guaranteed optimal; not complete in infinite space.

Comparison Table:
Feature BFS DFS
Data Structure Queue Stack
Explores Level order Depth-wise
Optimal Yes No
Complete Yes No (in infinite paths)
Memory Use High Low
Use Case Shortest path Deeper solution
search
19) Explain Optimal Decisions in Games.

Optimal decisions in games refer to strategies that guarantee the best

possible outcome for an AI agent, assuming the opponent also plays optimally.

Key Concepts:

1) Minimax Principle
 • MAX tries to maximize utility.
• MIN tries to minimize utility.
• AI chooses a move that guarantees the highest minimum payoff.

2) Utility Values

Leaf nodes have values representing the final game result (win/lose/draw).
Optimal move = the one that leads to the highest guaranteed utility.

3) Optimality Condition

A decision is optimal when:

• It considers all possible opponent responses.
• It ensures the AI avoids worst-case outcomes.
• It selects the move with the best guaranteed payoff.

4) Use in Adversarial Search

Optimal decisions are crucial in:

• Chess
• Tic-tac-toe
• Checkers
• Strategic decision-making

Example:

If one move can lead to win or draw, and another can lead to win or loss, AI
chooses the win/draw option to minimize risk.

AI uses Minimax with Alpha-Beta pruning to compute optimal moves efficiently.

20) Difference between Forward Chaining and Backward Chaining.

Forward Chaining (Data-driven):

• Starts with known facts and applies rules to derive new facts.
• Continues until the goal is reached.
• Suitable for diagnosis, monitoring, expert systems.
• Useful when all data is available upfront.

Backward Chaining (Goal-driven):

• Starts with a goal and works backward to find required supporting
facts.
• Tries to prove the goal by checking rule conclusions.
 • Suitable for problem-solving, theorem proving.
• Efficient when goal is known but facts are limited.

Comparison Table:
Feature Forward Chaining Backward Chaining
Direction Fact → Goal Goal → Facts
Trigger New facts Query
Uses Expert systems Logic programming
Efficiency Good when many facts Good when few goals
Example Medical diagnosis Proving theorems

21) Explain AO* Algorithm with suitable example.

AO* (And-Or Search) is used to find optimal solutions in problems with

decomposable subproblems, typically represented as AND-OR graphs.

Key Concepts:
• OR nodes: Choose one action among many.
• AND nodes: Must solve all subproblems to proceed.
• Uses heuristics to evaluate partial solution graphs.
• Expands the most promising path first.

Steps in AO* Algorithm:

1. Evaluate the heuristic value of each node.
2. Select a node that promises the lowest cost.
3. If it is an OR node → select best child.
4. If it is an AND node → expand all children.
5. Update cost until solution graph is complete.
6. Repeat until optimal AND-OR solution is found.

Example:

Suppose a problem decomposes as:

• Solve A → leads to either B or C (OR node).
• B requires solving D and E (AND node).

AO* will evaluate B’s children, compute total cost, and compare with C’s
cost, selecting the optimal path.

Used in planning, diagnosis, and hierarchical reasoning.

22) Explain Alpha-Beta Pruning with example.

Alpha-Beta pruning improves Minimax by eliminating branches that cannot
affect the final decision.

Key Concepts:
• Alpha (α): Best value MAX can guarantee so far.
• Beta (β): Best value MIN can guarantee so far.
• If α ≥ β → prune the branch (no need to explore).

Steps:
1. Traverse game tree using Minimax.
2. Keep updating α at MAX nodes, β at MIN nodes.
3. If a node can’t possibly improve the result → prune.

Example:

Suppose MAX explores left branch and gets value 8.

At a MIN node in the right branch, if the child node already gives ≤ 8, MAX will
not choose this path.
Thus, MIN node is pruned without exploring further children.

Benefits:
• Does not affect final result (optimality preserved).
• Reduces time complexity significantly.
• Allows deeper game tree exploration.

Alpha-Beta pruning is essential for chess engines and adversarial search.

23) Explain Best-First Search.

Best-First Search (BeFS) is an informed search strategy that selects the next
node to expand based on a heuristic evaluation function.

Key Features:
• Uses a priority queue to store nodes ordered by heuristic value.
• Chooses the “best” node according to the heuristic (lowest cost).
• Combines concepts from BFS and DFS but guided by heuristics.

Algorithm Steps:
1. Insert the start node into a priority queue.
2. Select node with minimum heuristic value.
3. Expand the node and evaluate its successors.
4. Continue until goal is reached or queue is empty.

Advantages:
 • Very efficient when heuristics are good.
• More goal-directed than BFS or DFS.
• Reduces unnecessary exploration.

Limitations:
• Not guaranteed optimal.
• May get stuck in local minima if heuristic is poor.

Used in navigation systems, pathfinding, puzzle-solving, and robotics.

5 MARK ANSWERS

1) What is Hierarchical Planning? Explain in detail.

Hierarchical Planning, also known as Hierarchical Task Network (HTN)

Planning, is a planning approach in which complex tasks are broken down into
smaller, simpler sub-tasks. Instead of directly searching for primitive actions,
hierarchical planning uses high-level tasks, which are recursively decomposed
until executable (primitive) steps are reached.

Key Concepts in Hierarchical Planning

a) Tasks
• High-level tasks: Abstract tasks like “Prepare Dinner” or “Travel to
Destination.”
• Primitive tasks: Concrete operations the agent can directly execute
(e.g., “Boil water”, “Cut vegetables”).

b) Task Decomposition (Reduction)

Each high-level task is decomposed using predefined methods or rules.

Example:
Task: Travel(CityA, CityB)
Methods:
• Travel by Car
• Travel by Train
• Travel by Flight

c) Planning Process
1. Start with the main goal.
2. Replace high-level tasks with valid methods.
 3. Break them into subtasks.
4. Continue until all tasks are primitive.
5. Execute tasks sequentially.

2) Explain First-Order Logic with example.

First-Order Logic (FOL) is a powerful knowledge representation system that

extends propositional logic by allowing quantifiers, variables, predicates, and
functions. It captures relationships between objects rather than just facts.

Components of First-Order Logic

a) Constants

Represent specific objects.

Example: John, Apple.

b) Predicates

Describe properties or relations.

Example:
• Likes(John, Apple)
• Greater(x, y)

c) Quantifiers

Two quantifiers exist:

• Universal quantifier (∀): Applies to all.
• Existential quantifier (∃): There exists at least one.

d) Variables

Generic placeholders like x, y, z.

e) Functions

Map objects to other objects.

Example: Father(John) → returns the father of John.

Example 1: “All humans are mortal.”

FOL:
∀x (Human(x) → Mortal(x))

Example 2: “John likes apples.”

Likes(John, Apple)

Example 3: “Everyone who studies works hard.”

∀x (Studies(x) → WorksHard(x))

Why FOL is powerful?

• Can represent complex, relational knowledge.
• Used for expert systems, reasoning, planning, and AI inference
engines.

3) State components using which a problem can be formulated.

Every AI problem must be clearly defined using the following components:

1) Initial State

The starting point of the problem.

Example: Initial position of a robot.

2) State Space

All possible states reachable from the initial state through valid actions.
Defines the complete structure of the problem.

3) Actions / Operators

Describe how the agent moves from one state to another.

Example: “Move Left”, “Pick Up Block”.

4) Transition Model

Defines the result of performing an action in a state.

Written as:
Result(state, action).

5) Goal State / Goal Test

Defines success criteria.
Example: “Block A is on Block B”.

6) Path Cost (Cost Function)

Assigns numeric cost to actions to measure solution quality.

Example: distance traveled, time taken.

7) Constraints (if any)

Restrictions that must be satisfied.

Example: In CSPs, coloring a map requires adjacent states to have different
colors.

Why these components matter?

They help structure the problem fully, allowing search algorithms to find valid
and optimal solutions.

4) AO* Algorithm (Detailed 5-Mark Answer)

The AO* algorithm is used for solving problems represented as AND-OR

graphs. Unlike OR trees where one path solves the problem, AND-OR graphs
require solving multiple subproblems (AND nodes) together.

Key Features
• Uses heuristic values to guide the search.
• Expands the most promising node first.
• Ensures optimal solution graphs, not just paths.

Node Types:
1. OR Node: Choose one child that leads to the goal.
2. AND Node: All children must be solved to satisfy the parent.

Steps in AO* Algorithm:

1) Initialization

Begin with the initial problem/state.

2) Node Selection

Pick a leaf node whose path has the lowest estimated cost.
3) Expansion

Expand the node:

• At OR node → create branches for alternative actions.
• At AND node → create subproblem branches.

4) Cost Revision

Update the cost using the formula:

• OR node: choose minimum cost child.
• AND node: sum of children’s costs.

5) Marking Solution Graph

Mark the optimal subgraph that leads to the goal.

6) Continue until optimal solution graph is found.

Simple Example:

Problem:
To solve A, you can choose either:
• B AND C (both must be solved)
• OR directly solve D.

Costs:
• B=2
• C=4
• D = 10

AO* compares:
• A→B&C=2+4=6
• A → D = 10

So the optimal solution chosen is A → (B AND C).

5) AI Architecture (Detailed Explanation)

AI architecture refers to the overall structure or design of an AI system,

defining how different components interact to perform intelligent tasks.

Key Components of AI Architecture

1) Perception Module

Receives input through sensors or data streams.

Examples: cameras, microphones, text input.

2) Knowledge Base (KB)

Stores facts, rules, ontologies, semantic networks.

Provides the foundation for reasoning and decision-making.

3) Reasoning/Inference Engine

Applies logical rules to derive new knowledge.

Used in expert systems, planning, and diagnosis.

4) Learning Module

Allows the AI to improve over time using ML algorithms.

Examples: neural networks, reinforcement learning.

5) Planning and Decision-Making Module

Determines the sequence of actions needed to reach goals.

Uses algorithms like A*, Minimax, or CSP solvers.

6) Action/Execution Module

Uses actuators or output channels to perform actions.

Examples: robots moving, software making decisions.

Types of AI Architectures

a) Reactive Architecture
• Responds instantly to inputs.
• No memory or internal model.
• Example: simple robotics.

b) Deliberative Architecture
• Builds internal models.
• Performs planning and logical reasoning.

c) Hybrid Architecture
• Combines reactive and deliberative features.
• Used in autonomous vehicles, intelligent robots.
⸻

6) Regression

Regression is a supervised learning technique used in AI and machine

learning to predict a continuous numerical value based on input variables. It
establishes a mathematical relationship between dependent and independent
variables.

Types of Regression:

1) Linear Regression

Models the relationship as a straight line:

y = mx + c
Used for price prediction, demand forecasting, etc.

2) Multiple Linear Regression

Uses more than one independent variable:

y = b_0 + b_1x_1 + b_2x_2 + ... + b_nx_n

3) Polynomial Regression

Fits nonlinear curves by using higher-degree terms.

4) Logistic Regression (Classification)

Even though it has “regression” in name, it predicts binary classes using a

sigmoid function.

7) Automated Planning

Automated Planning refers to the capability of an AI system to generate a

sequence of actions that leads from an initial state to a desired goal state
without human intervention.

Key Elements of Automated Planning:

a) Initial State

The starting situation of the world.

b) Actions
Each action has:
• Preconditions
• Effects
Example:
Move(A, B) requires robot at A and results in robot at B.

c) Goal State

Defines success, e.g., “package delivered”.

d) Plan

A series of actions that transform the initial state into the goal.

Types of Automated Planning:

1) Classical Planning

Assumes a deterministic and fully observable world.

2) Hierarchical Planning (HTN)

Breaks tasks into subtasks.

3) Partial-Order Planning

Does not enforce strict ordering unless necessary.

4) Conditional Planning

Includes conditional branches (if–else) for uncertain situations.

5) Probabilistic Planning

Uses probability models (MDPs) for uncertain environments.

8) Write a short note on AO* Algorithm.

The AO* algorithm is used to search AND-OR graphs, where some problems
require solving multiple subproblems simultaneously.

Key Features:
 • Handles decomposition-based problems.
• Works with heuristic estimates.
• Produces solution graphs, not just paths.
• Expands the most promising branch first.

How AO* Works:

1. Start from root node.
2. For OR nodes → choose best child.
3. For AND nodes → expand all children.
4. Update costs using heuristic information.
5. Mark nodes that belong to optimal solution graph.
6. Continue until complete problem is solved.
⸻

9) Write a short note on Information Extraction.

Information Extraction (IE) automatically extracts structured information from

unstructured text, such as documents, webpages, or reports.

Key Tasks in Information Extraction:

1) Named Entity Recognition (NER)

Identifies entities like persons, dates, organizations.

2) Relation Extraction

Finds relationships, e.g., “John works at Google”.

3) Event Extraction

Detects events like “earthquake occurred”, “company launched product”.

4) Template Filling

Extracts specific information into fixed formats.

Applications:
• Healthcare: extracting symptoms, diagnoses
• Finance: extracting company information, stock reports
• E-commerce: product details, sentiment analysis
• Digital assistants: answering user queries

10) What is the significance of the “cutoff” in Alpha-Beta Pruning?

The cutoff in Alpha-Beta pruning refers to stopping further exploration of a
branch in the game tree because it cannot influence the final decision.

Why Cutoff Happens:

• If the value at a MIN node becomes ≤ current alpha
• If the value at a MAX node becomes ≥ current beta

Significance:

1) Improves Efficiency

Cutoff eliminates the need to explore irrelevant branches, reducing time

complexity from:
O(b^d) \quad \text{to approximately} \quad O(b^{d/2})

2) Enables Deeper Search

By ignoring useless branches, the algorithm explores deeper levels of the game
tree.

3) Does Not Affect Optimality

Pruned branches would never affect the final Minimax decision.

4) Saves Memory

Less number of nodes stored during evaluation.

5) Crucial for Real-Time Games

Games like Chess, Checkers, Go require deep searching; cutoffs make

computation feasible.

11) Describe a scenario where the A* algorithm might expand more nodes
than necessary and difference between Uniform Cost Search and A*.

Scenario Where A* Expands More Nodes

A* may expand unnecessary nodes when:

• The heuristic function underestimates too much (admissible but not
accurate).
• Several nodes have similar f(n) values, leading to wide exploration.
• The search graph has many equal-cost alternative paths, causing
tie-breaking expansions.
 • Heuristic is very weak (close to zero), making A* behave like Uniform
Cost Search.

Example: In a grid search where heuristic = 0 for all nodes, A* becomes

identical to UCS and expands almost every node.

Difference Between Uniform Cost Search (UCS) and A*

Feature Uniform Cost Search A* Search
Formula f(n) = g(n) f(n) = g(n) + h(n)
Heuristic Not used Used
Efficiency Slow Faster with good
heuristic
Optimality Always optimal Optimal if h(n) is
admissible
Search Type Uninformed Informed
Expansion Explores lowest cost Explores most
path promising path

12) What is Hill Climbing? Write algorithm for it. What are the problems in
Hill Climbing Algorithm?

Hill Climbing Definition:

Hill climbing is a heuristic search algorithm that moves continuously toward

higher-valued (better) states based on a heuristic evaluation function. The main
goal is to reach a local or global maximum by iteratively improving the current
state.

Algorithm (Steepest-Ascent Hill Climbing):

1. Start with an initial state.
2. Loop until no better neighbors exist:
a) Evaluate current state's neighbors.
b) Select the neighbor with the highest heuristic value.
c) If neighbor is better → move to that neighbor.
d) Else → stop (local maximum reached).
3. Return the best state found.

Problems in Hill Climbing:

1) Local Maxima

The search may reach a peak that is not the highest but has no better
neighbors. It gets stuck and stops prematurely.
2) Plateaus

A region where neighboring states have the same heuristic value. The
algorithm cannot decide in which direction to move.

3) Ridges

The optimal path may require moves that are not directly uphill, but the
algorithm only moves uphill, causing failure to reach the actual peak.

4) No Backtracking

Once a move is made, the algorithm never goes back. This causes the search to
get stuck easily.

5) Sensitive to Initial State

Different starting states may result in different solutions.

Hill climbing is simple but often unreliable without enhancements like random
restart or stochastic selection.

13) Explain IDDFS (Iterative Deepening Depth First Search) Algorithm.

Iterative Deepening Depth First Search combines the advantages of DFS (low
memory) and BFS (completeness and optimality).

Key Idea:

IDDFS performs DFS repeatedly with increasing depth limits, starting from
depth 0, then 1, then 2, and so on.

Why IDDFS Works Well:

• It behaves like BFS in terms of completeness and optimality.
• It uses memory like DFS (linear space).
• Avoids infinite looping of DFS because depth limit restricts
exploration.

IDDFS Algorithm:
IDDFS(start, goal):
 for depth = 0 to ∞:
result = DLS(start, goal, depth)
if result = goal:
return success

14) Explain A* Algorithm with a suitable example.

A* Algorithm Overview:

A* uses both actual cost (g(n)) and estimated cost to goal (h(n)) to evaluate
nodes:
f(n) = g(n) + h(n)
It is an informed, optimal, and complete search algorithm when h(n) is
admissible.

A Algorithm Steps:
1. Initialize OPEN list (priority queue).
2. Insert start node with f = h(start).
3. Loop:
• Remove node with smallest f(n).
• If node is goal → return solution.
• Expand node, compute f for children.
• Insert children into OPEN list.
4. Repeat until OPEN is empty or goal found.

Example: Pathfinding on a Grid

Grid with start S, goal G.

Suppose heuristic = Manhattan distance.

Assume:
• g(n) = cost so far
• h(n) = |x1 − x2| + |y1 − y2|

If from S, two nodes A and B are available:

• f(A) = g(A) + h(A) = 2 + 5 = 7
• f(B) = g(B) + h(B) = 3 + 2 = 5

A* chooses B because f(B) < f(A).

 A* always selects path with smallest f(n), combining both real cost and
heuristic.

15) Give symbolic form of following statements (predicate logic)

Let the domain be persons, numbers, or entities as appropriate.

I) Some men are genius.

∃x (Man(x) ∧ Genius(x))

II) For every x, there exists a y such that x² + y² ≥ 100

∀x ∃y (x² + y² ≥ 100)

III) Given any positive integer, there is a greater positive integer.

∀x (PositiveInteger(x) → ∃y (PositiveInteger(y) ∧ y > x))

IV) Everyone who likes fun will enjoy each of these plays.

∀x (LikesFun(x) → ∀y (Play(y) → Enjoy(x, y)))

V) Some students are clever.

∃x (Student(x) ∧ Clever(x))

These predicate forms allow expressing universal and existential relationships

accurately.

16) Symbolic form using p and q

Let:
p: He is intelligent
q: He is tall

I) He is tall but not intelligent.

q ∧ ¬p

II) He is neither tall nor intelligent.

¬q ∧ ¬p
(or ¬(p ∨ q))

III) He is intelligent or he is tall.

p∨q

IV) It is not true that he is intelligent or tall.

¬(p ∨ q)

V) It is not true that he is not tall or not intelligent.

¬(¬q ∨ ¬p)
This simplifies to:
p∧q