ARTIFICIAL INTELLIGENCE — EXAM

GUIDE
Unit I: Intelligent Agents | Unit II: Problem Solving by Search
T.E. Computer Engineering | 2019 Pattern | Semester II (310253)
SPLIT: 📋 PYQ (Past Questions) + 🔥 WILL ASK (Never Asked Topics)

📌 Answering Pattern: Introduction → Definition → Diagram → Explanation → Points → Example →

Advantages/Disadvantages → Conclusion
🎯 5 marks = 2 pages. 7-8 marks = 3-4 pages. ALWAYS draw diagram. For numericals: write formula →
substitute → solve → state answer.

📋 UNIT I PYQ MASTER TABLE

Q Year Marks Topic
Q1 2023 5 AI Definition + Intelligent Agent + Uses
a
Q1 2023 5 Advantages of Artificial Intelligence
b
Q1 2023 5 Learning Agent Architecture with Diagram
c
Q1 2024 6 Properties of Agent Task Environment (PEAS)
a
Q1 2024 6 Agent + Environment in AI + Types of Environments
b
Q1 2024 3 Real Life Applications of AI
c
Q2 2024 5 Risks and Benefits of AI
a
Q2 2024 5 Rationality and Rational Agent
b
Q2 2024 5 History of AI + Applications
c

📋 UNIT II PYQ MASTER TABLE

Q Year Marks Topic
Q2 2023 5 Evaluation of Search Strategy
a
Q2 2023 5 Different Search Strategies
b
Q2 2023 5 Heuristic Function
 Q Year Marks Topic
c
Q3 2023 10 Hill Climbing Search + Disadvantages
a
Q3 2023 5 Blind Search vs Heuristic Search
b
Q4 2023 7 Simple Problem Solving Technique + Example
a
Q4 2023 8 A* Algorithm with Example
b
Q3 2024 7 A* Algorithm (again — BOTH years)
a
Q3 2024 4 Problem Solving Agent
b
Q3 2024 4 Local Search and Optimization
c
Q4 2024 7 Hill Climbing + Disadvantages (again — BOTH years)
a
Q4 2024 4 Heuristic vs Blind Search (again — BOTH years)
b
Q4 2024 4 DFS vs Best First Search
c

🔥 WILL ASK TABLE

Topic Probability Why
Types of Agents ★★★★★ Explicitly in syllabus — NEVER asked
(Reflex/Model/Goal/Utility) CERTAIN standalone
PEAS Description with Examples ★★★★☆ Very In syllabus, asked partially — full answer
High never given
Uninformed Search: BFS + DFS ★★★★☆ Very Only compared — never explained fully
detailed High alone
State Space Representation ★★★★☆ Very Foundation of search — never appeared
High
Simulated Annealing ★★★☆☆ High In local search — never appeared
Foundations of AI (Disciplines) ★★★☆☆ High In syllabus Unit I — never appeared
UNIT I — INTELLIGENT AGENTS
━━━━━━ SECTION 1: PYQ ━━━━━━
PYQ 1. AI Definition + Intelligent Agent + Uses
📋 PYQ — 2023 Q1a — 5 Marks
[ 5 Marks MARKS ]

▌ INTRODUCTION
Artificial Intelligence is one of the most transformative fields in modern computer science. It aims to
create machines that can perceive their environment, reason about it, and take intelligent actions. An
Intelligent Agent is the fundamental building block of AI — any entity that perceives and acts is an
agent.
▌ DEFINITION
Artificial Intelligence: The branch of computer science concerned with building systems that can
perform tasks that normally require human intelligence — such as reasoning, learning, perception,
problem-solving, understanding language, and decision making. (Russell & Norvig: AI is the study of
rational agents.)

Intelligent Agent: Any entity that perceives its environment through sensors and acts upon it
through actuators. Mathematically, an agent is described by an agent function: f: Percept Sequence
→ Action
▌ AGENT DIAGRAM
┌───────────────────────────┐
│ AGENT │
│ │
ENVIRONMENT ───── │ Sensors ──▶ [?] ──▶ Actuators ───── ENVIRONMENT
(inputs) │ Agent Function │ (outputs)
│ Percepts ──▶ Actions │
└───────────────────────────┘

Example: Vacuum Cleaner Agent

Sensors = Dirt sensor + Location sensor
Actuators = Move Left, Move Right, Suck
Percept = [Location A, Dirty]
Action = Suck

▌ 4 DEFINITIONS OF AI — 2x2 TABLE

Category Human-based Rationality-based
Thinking Think humanly (cognitive science) Think rationally (laws of thought)
Acting Act humanly (Turing Test) Act rationally (rational agent)

▌ USES / APPLICATIONS OF INTELLIGENT AGENTS

Domain Application Agent Type
Healthcare Medical diagnosis, drug discovery Goal-based agent
Finance Stock trading, fraud detection Utility-based agent
Transport Self-driving cars, route planning Model-based agent
 Domain Application Agent Type
Gaming Chess, Go, video game bots Utility-based agent
Web Search engines, recommendations Learning agent
Manufacturing Robotic assembly, quality control Model-based agent
NLP Chatbots, translation, speech Learning agent
recognition

▌ CONCLUSION
Artificial Intelligence aims to build rational agents that act optimally in their environment. An intelligent
agent perceives through sensors and acts through actuators, mapping percept sequences to actions
via an agent function. AI applications span healthcare, finance, transportation, gaming, and
manufacturing — making it one of the most impactful technologies of the 21st century.
PYQ 2. Advantages of Artificial Intelligence
📋 PYQ — 2023 Q1b — 5 Marks
[ 5 Marks MARKS ]

▌ INTRODUCTION
Artificial Intelligence offers transformative advantages across industries by automating complex
tasks, reducing human error, and enabling capabilities beyond human limitations. AI systems can
work 24/7, process massive amounts of data instantly, and continuously improve through learning.
▌ KEY ADVANTAGES
▶ 1. Reduction in Human Error
• AI systems make decisions based on algorithms and data — not emotion or fatigue
• NASA uses AI to control spacecraft with near-zero error in calculations
• In medical diagnosis, AI achieves higher accuracy than humans in detecting cancer
▶ 2. Works 24x7 Without Breaks
• Unlike humans, AI does not need sleep, breaks, or vacations
• Customer service chatbots (like Siri, Alexa) respond instantly at any hour
• Banks use AI fraud detection systems that operate continuously
▶ 3. Handles Repetitive Tasks
• Automates boring, repetitive tasks — freeing humans for creative work
• Manufacturing robots perform same assembly operations thousands of times perfectly
• AI processes thousands of emails, documents, invoices in seconds
▶ 4. Faster Decision Making
• AI processes millions of data points and arrives at decisions in milliseconds
• High-frequency trading AI makes stock buy/sell decisions in microseconds
• Chess AI evaluates billions of moves per second to select the best
▶ 5. Handles Dangerous Situations
• AI robots used in bomb disposal, nuclear plant inspection, deep sea exploration
• Reduces risk to human life in hazardous environments
• Mars rovers (AI-controlled) explore environments impossible for humans
▶ 6. New Capabilities and Innovation
• Enables capabilities impossible for humans — reading billions of web pages
• AlphaFold AI solved the 50-year-old protein folding problem
• AI enables personalized medicine, climate modeling, autonomous vehicles
▌ ADVANTAGES SUMMARY TABLE
Advantage Real Example
No human error AI medical imaging — 99% accuracy in diagnosis
24x7 availability Bank fraud detection — never sleeps
Handles repetition Car assembly robots — same precision every time
 Advantage Real Example
Fast decisions GPS route calculation — milliseconds
Handles danger Nuclear reactor monitoring — no human risk
Continuous learning Netflix recommendations improve with every watch

▌ CONCLUSION
The advantages of AI — reduced errors, 24/7 operation, handling repetition and danger, faster
decision making, and continuous improvement — make it an indispensable technology. AI
complements human intelligence rather than replacing it, enabling humans to focus on creativity,
empathy, and complex judgment while AI handles data-intensive, repetitive, and hazardous tasks.
PYQ 3. Learning Agent Architecture with Diagram
📋 PYQ — 2023 Q1c — 5 Marks
[ 5 Marks MARKS ]

▌ INTRODUCTION
Most agent designs assume the environment is fully known in advance, but real-world environments
are complex and unpredictable. A Learning Agent solves this problem by starting with limited
knowledge and improving its performance over time by learning from experience. It was proposed by
Alan Turing who suggested that instead of programming an adult mind, we should program a child's
mind and let it learn.
▌ DEFINITION
Learning Agent: An agent that can improve its own performance over time through experience. It
starts with basic knowledge and modifies its behavior based on feedback from its environment,
becoming more competent than its initial programming would allow.
▌ LEARNING AGENT DIAGRAM — DRAW THIS
┌──────────────────────────────────────────┐
│ LEARNING AGENT │
│ │
ENVIRONMENT ──────┤► SENSORS │
│ │ │
│ ▼ │
Performance ─────►│ CRITIC ──── feedback ──► LEARNING │
Standard │ ELEMENT │
│ │ │
│ │ changes │
│ ▼ │
│ PROBLEM ── goals ──► PERFORMANCE │
│ GENERATOR ELEMENT │
│ │ │
│ ▼ │
│ ACTUATORS ───────┤► ENVIRONMENT
└──────────────────────────────────────────┘

▌ FOUR COMPONENTS EXPLAINED

▶ 1. Performance Element
• The core of the agent — selects actions based on current knowledge
• Equivalent to the entire agent in non-learning designs
• Uses current knowledge to decide what to do next
• Example: Chess AI that selects which piece to move
▶ 2. Learning Element
• Responsible for making improvements to the agent's knowledge
• Takes feedback from the Critic and updates Performance Element
• Design depends on what information is available from the Critic
• Example: Updating chess strategy after winning or losing a game
▶ 3. Critic
• Evaluates how well the agent is performing against the Performance Standard
• Provides feedback to the Learning Element — tells it how good/bad the actions were
• Performance Standard is fixed outside the agent — cannot be modified by agent
• Example: Critic sees that chess agent lost material — gives negative feedback
▶ 4. Problem Generator
• Suggests exploratory actions to discover new knowledge
• Encourages the agent to take suboptimal actions in short term for long-term improvement
• Acts like a scientist — designs experiments to learn new things
• Example: Tries unusual chess moves to discover their long-term consequences
▌ LEARNING COMPONENTS TABLE
Component Role Analogy
Performance Element Takes current percepts, selects Brain deciding what to do now
action
Learning Element Updates knowledge based on Brain learning from mistakes
feedback
Critic Evaluates current performance Teacher grading your work
vs standard
Problem Generator Suggests Curiosity — trying new things
exploratory/experimental actions

📌 Key insight: The Performance Standard is OUTSIDE the agent. The agent cannot lower its own
standards to claim it is performing well.
▌ CONCLUSION
A Learning Agent consists of four components: Performance Element (takes actions), Learning
Element (improves based on feedback), Critic (evaluates performance against standard), and
Problem Generator (suggests exploration). Unlike static agents, learning agents improve over time,
making them suitable for complex real-world environments where all knowledge cannot be pre-
programmed.
PYQ 4. Properties of Agent Task Environment (PEAS)
📋 PYQ — 2024 Q1a — 6 Marks
[ 6 Marks MARKS ]

▌ INTRODUCTION
Before designing an intelligent agent, the first step is to fully specify the Task Environment — the
problem for which the agent is the solution. The standard way to describe a task environment is using
the PEAS framework, followed by analyzing its properties. The nature of the task environment
directly determines the best agent design.
▌ PEAS FRAMEWORK
PEAS: Performance measure, Environment, Actuators, Sensors — the four components used to
fully describe any task environment

PEAS
Meaning Example (Self-Driving Taxi)
Component
P— What defines success for Safe trips, passenger comfort, minimal fuel, legal
Performance the agent driving, profit
E— The external world the agent Roads, traffic, pedestrians, weather, map, GPS
Environment operates in
A — Actuators The outputs/actions Steering, accelerator, brake, horn, indicators
available to the agent
S — Sensors The inputs the agent Cameras, GPS, speedometer, odometer, sonar,
receives microphone

▌ MORE PEAS EXAMPLES

Agent Performance Environment Actuators Sensors
Medical Healthy patient, low Patient, hospital, staff Display questions, Keyboard
Diagnosis cost diagnoses input, test
results
Chess Program Win game Chess board, Move piece Board state
opponent
Email Filter Correct Email inbox Flag, delete, Email
classification forward headers,
content
Part-picking Parts in correct Conveyor belt, bins Robotic arm, hand Camera,
Robot bins joint angle
sensors

▌ PROPERTIES OF TASK ENVIRONMENTS — 6 DIMENSIONS

▶ 1. Fully Observable vs Partially Observable
• Fully Observable: agent's sensors give complete access to full environment state
• Partially Observable: sensors give limited or noisy information
• Example: Chess = Fully Observable | Poker = Partially Observable (hidden cards)
▶ 2. Single-Agent vs Multi-Agent
• Single-Agent: only one agent in the environment
• Multi-Agent: multiple agents interact — competitive or cooperative
• Example: Crossword puzzle = Single | Chess = Competitive multi-agent
▶ 3. Deterministic vs Stochastic
• Deterministic: next state is completely determined by current state + action
• Stochastic: next state involves some randomness or uncertainty
• Example: Chess = Deterministic | Taxi driving = Stochastic (other drivers)
▶ 4. Episodic vs Sequential
• Episodic: each action is independent — current decision does not affect future
• Sequential: current decision affects all future decisions
• Example: Photo classification = Episodic | Chess = Sequential
▶ 5. Static vs Dynamic
• Static: environment does not change while agent is deliberating
• Dynamic: environment can change while agent is thinking
• Example: Crossword = Static | Taxi driving = Dynamic (traffic changes)
▶ 6. Discrete vs Continuous
• Discrete: finite number of distinct percepts and actions
• Continuous: state, time, percepts are continuous values
• Example: Chess = Discrete | Self-driving car = Continuous
▌ ENVIRONMENT PROPERTIES TABLE
Discret
Environment Observable Agents Deterministic Episodic Static
e
Chess Full Multi Det Seq Static Discrete
Poker Partial Multi Stoch Seq Static Discrete
Taxi Driving Partial Multi Stoch Seq Dynamic Continu
ous
Image Classifier Full Single Det Episodic Static Continu
ous
Medical Diagnosis Partial Single Stoch Seq Static Discrete

▌ CONCLUSION
PEAS (Performance, Environment, Actuators, Sensors) provides a complete specification of any task
environment. The six properties — observability, number of agents, determinism, episodic/sequential,
static/dynamic, discrete/continuous — determine the complexity of the environment and directly
influence the appropriate agent design. Real-world environments like taxi driving are typically partially
observable, multi-agent, stochastic, sequential, dynamic, and continuous — making them the most
challenging to design agents for.
PYQ 5. Rationality and Rational Agent
📋 PYQ — 2024 Q2b — 5 Marks
[ 5 Marks MARKS ]

▌ INTRODUCTION
The central concept of AI as studied in this course is rational behavior. Rather than trying to mimic
human behavior exactly, we focus on building agents that do the right thing — agents that are
rational. Rationality is a precisely defined mathematical concept based on expected performance.
▌ DEFINITION
Rationality: For each possible percept sequence, a rational agent should select an action that is
expected to maximize its performance measure, given the evidence provided by the percept
sequence and whatever built-in knowledge the agent has.

Rational Agent: An agent that acts so as to maximize the expected value of its performance
measure, given its current percept sequence and built-in knowledge. Rationality ≠ Omniscience,
Clairvoyance, or Perfection.
▌ FOUR KEY FACTORS DETERMINING RATIONALITY
Factor Description
Performance Measure Defines what 'success' means — what the agent is trying to achieve
Prior Knowledge What the agent knows about the environment before it starts
Available Actions What actions the agent can perform
Percept Sequence All percepts the agent has received so far

▌ RATIONALITY vs OMNISCIENCE — CRITICAL DISTINCTION

Omniscience = knows the ACTUAL outcome of actions (impossible in real world)
Rationality = maximizes EXPECTED performance based on available information

Example: Crossing a road

- Rational agent: looks both ways, no car visible → crosses
- If a car appears from nowhere after checking → not irrational!
- Rationality is judged on what the agent COULD KNOW, not what it could not

Rational ≠ Successful (outcome may be bad due to unforeseeable events)

Rational = Best possible action given available information

▌ RATIONAL AGENT EXAMPLE

▶ Vacuum Cleaner Agent
• Performance Measure: +1 point for each clean square at each time step
• Environment: 2-room world with dirt
• Sensors: Location sensor (A or B) + Dirt sensor (Clean/Dirty)
• Actuators: Move Left, Move Right, Suck
Rational actions:
[A, Dirty] → Suck (dirt is here — clean it)
 [A, Clean] → Right (A clean — check B)
[B, Dirty] → Suck (dirt is here — clean it)
[B, Clean] → Left (B clean — go back to A)

This agent maximizes expected clean squares = RATIONAL

▌ INFORMATION GATHERING — RATIONAL BEHAVIOR

• Rational agents must GATHER INFORMATION before acting
• A rational agent exploring an unknown area looks around before moving
• Performing actions to modify future percepts = rational information gathering
• Example: Medical agent should request tests before making diagnosis
▌ CONCLUSION
A rational agent selects actions that maximize expected performance based on its performance
measure, prior knowledge, available actions, and percept sequence. Rationality is NOT omniscience
— a rational agent does the best it can with available information. This concept is central to AI: we
design agents that are rational rather than trying to exactly copy human behavior, because rationality
is mathematically well-defined and universally applicable.
PYQ 6. History of AI + Real Life Applications
📋 PYQ — 2023 Q1c (Applications) + 2024 Q2c (History + Applications) — 5 Marks
[ 5 Marks MARKS ]

▌ INTRODUCTION
Artificial Intelligence has a rich history spanning over 70 years, with dramatic cycles of optimism,
disillusionment, and revival. Understanding this history helps explain why modern AI uses the
approaches it does today — moving from rule-based logic to statistical learning to the current deep
learning revolution.
▌ HISTORY TIMELINE
Period Key Event Significance
1943 McCulloch & Pitts — first neural Showed neurons can compute logical functions
network model
1950 Alan Turing — 'Computing First formal test of machine intelligence
Machinery and Intelligence' —
Turing Test
1956 Dartmouth Conference — John Birth of AI as a formal field
McCarthy coins 'Artificial
Intelligence'
1956-1969 Early enthusiasm — Logic Theorist, First AI programs — proved theorems, played
General Problem Solver checkers
1966-1973 First AI Winter — funding cut, NLP and combinatorial explosion problems
limitations exposed found
1969-1979 Knowledge-based systems Expert systems — domain knowledge works
(MYCIN, DENDRAL) better
1980s Expert Systems boom — AI industry reaches $1 billion
commercial AI products
1987-1993 Second AI Winter — hardware Expert systems too expensive to maintain
costs, limitations
1990s Machine learning, neural networks Statistical approaches, data-driven learning
return
2012-Now Deep Learning revolution — Neural networks with massive data + GPU
ImageNet breakthrough compute

▌ REAL LIFE APPLICATIONS OF AI

Domain Application Example
Healthcare Disease diagnosis, drug IBM Watson diagnoses cancer; AlphaFold folds
discovery proteins
Transportation Self-driving cars, traffic Tesla Autopilot; Google Waymo
control
Finance Fraud detection, algorithmic PayPal detects fraud; HFT systems
 Domain Application Example
trading
E-Commerce Recommendation systems Amazon 'Customers who bought this also
bought'
NLP Speech recognition, Google Translate; Siri; Alexa; ChatGPT
translation
Gaming Game-playing AI DeepMind AlphaGo beats world chess/Go
champions
Manufacturing Robotics, quality control Tesla Gigafactory robots assemble cars
Agriculture Crop monitoring, yield AI drone surveys detect crop diseases
prediction

📌 Kroger Case Study (Syllabus): Kroger uses AI and robotics for inventory management, personalized
marketing, automated fulfillment centers with robots, and predictive restocking — preparing for the 4th
Industrial Revolution.
▌ RISKS AND BENEFITS — QUICK REFERENCE
Benefits Risks
Automation of dangerous/repetitive tasks Job displacement and unemployment
Faster, more accurate medical diagnosis Privacy violations from surveillance AI
Scientific breakthroughs (protein folding) Autonomous weapons and lethal AI
Personalized education and healthcare Algorithmic bias and discrimination
24/7 availability, no fatigue Deepfakes and misinformation
Energy efficiency in smart grids Concentration of power in tech companies

▌ CONCLUSION
AI has evolved over 70+ years from symbolic logic to machine learning to deep learning. Key
milestones include the Turing Test (1950), the Dartmouth Conference (1956), Expert Systems
(1980s), and the Deep Learning revolution (2012-present). AI now transforms healthcare, transport,
finance, manufacturing, and communication — while also raising important ethical concerns about
jobs, privacy, bias, and safety that must be addressed proactively.
━━━━━━ UNIT I: WILL ASK ━━━━━━
WILL ASK 1. Types / Structure of Agents
🔥 WILL ASK — Explicitly in syllabus — NEVER asked standalone — HIGHEST probability
[ 5 Marks MARKS ]

⚡ 'Structure of Agents' is in Unit I syllabus. Types (Reflex/Model/Goal/Utility/Learning) have never

appeared as a dedicated question. Very likely this year.
▌ INTRODUCTION
An agent's behavior is implemented by an agent program running on a physical architecture. The
agent program maps percepts to actions. There are four basic types of agent programs, each
handling progressively more complex environments.

◈ TYPE 1 — SIMPLE REFLEX AGENT

┌──────────────────────────────────────┐
│ SIMPLE REFLEX AGENT │
│ Percepts ──▶ Condition-Action Rules ──▶ Action │
│ 'If dirty THEN suck' │
└──────────────────────────────────────┘
• Acts only on CURRENT percept — ignores history
• Works on condition-action rules: IF <condition> THEN <action>
• Simple but limited — fails in partially observable environments
• Example: Thermostat (if temp < 20 → turn on heater), basic vacuum cleaner

◈ TYPE 2 — MODEL-BASED REFLEX AGENT

┌─────────────────────────────────────────────────┐
│ MODEL-BASED REFLEX AGENT │
│ Percepts + Internal State (World Model) ──▶ Action │
│ Maintains memory of what it cannot currently see │
└─────────────────────────────────────────────────┘
• Maintains internal STATE to track parts of world not currently visible
• Uses a MODEL: 'How does the world work?' + 'How do my actions change it?'
• Can handle partially observable environments
• Example: Self-driving car remembers the car that passed out of camera view

◈ TYPE 3 — GOAL-BASED AGENT

┌─────────────────────────────────────────────────┐
│ GOAL-BASED AGENT │
│ State + Goals ──▶ Search/Planning ──▶ Action │
│ Considers future actions to achieve goal │
└─────────────────────────────────────────────────┘
• Has explicit GOALS — desired states it wants to achieve
• Uses search and planning to find action sequences that reach the goal
• More flexible than reflex — can adapt when goal changes
• Example: GPS navigation — goal is destination; plans route to get there

◈ TYPE 4 — UTILITY-BASED AGENT

┌─────────────────────────────────────────────────┐
│ UTILITY-BASED AGENT │
 │ State + Utility Function ──▶ Best Action │
│ Maximizes expected happiness/utility │
└─────────────────────────────────────────────────┘
• Uses a UTILITY FUNCTION that measures 'how happy' the agent is in each state
• Chooses actions that maximize expected utility — handles tradeoffs
• Example: Fast route (shorter but risky) vs safe route (longer but safe) — utility decides
• Example: Chess AI evaluates positions numerically and picks highest utility move
▌ COMPARISON TABLE — ALL 5 TYPES
Type Memory Goal Decision Basis Example
Simple Reflex No No Current percept only Thermostat
Model-Based Yes (world No Percept + internal Autonomous car
model) state
Goal-Based Yes Yes State + goal GPS navigation
(planning)
Utility-Based Yes Yes State + utility function Chess, airline
booking
Learning Yes (learns) Yes Experience + AlphaGo, spam
feedback filter

▌ CONCLUSION
The five agent types form a hierarchy of increasing capability: simple reflex agents react to current
percepts, model-based agents maintain world state, goal-based agents plan to achieve goals, utility-
based agents maximize expected happiness, and learning agents improve through experience. The
choice of agent type depends on the complexity of the task environment.
UNIT II — PROBLEM SOLVING BY SEARCH
━━━━━━ SECTION 1: PYQ ━━━━━━
PYQ 7. Problem Solving Agent + Simple Problem Solving
📋 PYQ — 2023 Q4a (7 marks) + 2024 Q3b (4 marks)
[ 4–7 Marks MARKS ]

▌ INTRODUCTION
A problem-solving agent is a goal-based agent that uses search to find a sequence of actions that
leads to a desired goal state. It works by formulating the problem, searching through possible action
sequences, and executing the solution. This is the foundation of all search-based AI.
▌ DEFINITION
Problem-Solving Agent: A goal-based agent that decides what to do by finding a sequence of
actions that lead from the current state to a goal state, using search algorithms.
▌ STEPS IN SIMPLE PROBLEM SOLVING
Step 1: GOAL FORMULATION
Define what states are acceptable as the goal
Example: Goal = 'Be in Bucharest'

Step 2: PROBLEM FORMULATION

Define the states, actions, transition model, cost function
What can the agent do? What does each action change?

Step 3: SEARCH
Find a sequence of actions that leads from initial state to goal
Agent considers various possible action sequences

Step 4: EXECUTE
Carry out the recommended actions, one at a time

▌ PROBLEM FORMULATION — 5 COMPONENTS

Component Definition Example: Romania Route
Initial State Starting state of the agent In(Arad)
Actions Set of actions available in Go(Sibiu), Go(Timisoara), Go(Zerind)
each state
Transition Model Result of each action in Result(In(Arad), Go(Sibiu)) = In(Sibiu)
each state
Goal Test Checks if current state is a In(Bucharest) = True/False
goal state
Path Cost Numeric cost of each path Sum of road distances in km
(sum of step costs)

▌ EXAMPLE — ROUTE FINDING PROBLEM

Problem: Find route from Arad to Bucharest in Romania

Initial State : In(Arad)

Actions : Drive to adjacent city
Transition : Result(In(Arad), Drive(Sibiu)) = In(Sibiu)
 Goal Test : Is current city = Bucharest?
Path Cost : Total distance in km

State Space (partial):

Arad ──(140)── Sibiu ──(99)── Fagaras ──(211)── Bucharest
Arad ──(118)── Timisoara
Arad ──(75)── Zerind

Optimal Path: Arad→Sibiu→Rimnicu Vilcea→Pitesti→Bucharest = 418 km

▌ 8-PUZZLE EXAMPLE — CLASSIC EXAM PROBLEM

Initial State: Goal State:
┌───┬───┬───┐ ┌───┬───┬───┐
│ 7 │ 2 │ 4 │ │ 1 │ 2 │ 3 │
├───┼───┼───┤ ├───┼───┼───┤
│ 5 │ │ 6 │ │ 4 │ 5 │ 6 │
├───┼───┼───┤ ├───┼───┼───┤
│ 8 │ 3 │ 1 │ │ 7 │ 8 │ │
└───┴───┴───┘ └───┴───┴───┘

Initial State: [7,2,4,5,_,6,8,3,1]

Actions: Move blank UP, DOWN, LEFT, RIGHT
Goal Test: State matches [1,2,3,4,5,6,7,8,_]
Path Cost: Number of moves

▌ CONCLUSION
A problem-solving agent formulates its task as a search problem with five components: initial state,
actions, transition model, goal test, and path cost. It then searches through the state space to find a
sequence of actions (a solution path) from the initial state to a goal state. Classic examples include
route finding (Romania map) and the 8-puzzle, which illustrate how real problems are abstracted into
tractable search problems.
PYQ 8. Search Strategies + Evaluation of Search
📋 PYQ — 2023 Q2a (Evaluation) + 2023 Q2b (Strategies) — 5+5 Marks
[ 5 Marks each MARKS ]

▌ INTRODUCTION
A search strategy determines the order in which nodes in the search tree are expanded. Different
strategies have vastly different performance characteristics. A good search strategy finds a solution
without exploring unnecessary states. All strategies are evaluated on four criteria.
▌ EVALUATION CRITERIA — 4 PARAMETERS
Criterion Definition Best Value
Completeness Does the algorithm always find a Yes (complete)
solution if one exists?
Optimality Does the algorithm find the LOWEST Yes (optimal)
COST solution?
Time Complexity How long does it take? (nodes O(b^d) or less
generated/expanded)
Space Complexity How much memory does it need? O(b*d) or less
(nodes stored)

b: Branching factor — maximum number of successors of any node

d: Depth of the shallowest goal node
m: Maximum depth of the state space (may be infinite)

◈ UNINFORMED (BLIND) SEARCH STRATEGIES

No information about which non-goal states are more promising than others.
▶ 1. Breadth-First Search (BFS)
Expands shallowest unexpanded node first
Uses QUEUE (FIFO) as frontier

Level 0: A
Level 1: B C
Level 2: D E F G

Order: A → B → C → D → E → F → G
Property BFS
Complete YES (if b is finite)
Optimal YES (if step costs are equal)
Time O(b^d)
Space O(b^d) — stores all nodes at depth d

▶ 2. Depth-First Search (DFS)

 Expands deepest unexpanded node first
Uses STACK (LIFO) as frontier

Level 0: A
Level 1: B C
Level 2: D E F G

Order: A → B → D → E → C → F → G
Property DFS
Complete NO (fails in infinite-depth spaces or loops)
Optimal NO (may find suboptimal solution)
Time O(b^m) — worst case
Space O(b*m) — linear space — major advantage

▶ 3. Uniform Cost Search (UCS)

• Expands node with LOWEST PATH COST g(n) first
• Complete and Optimal for non-negative step costs
• Like BFS but ordered by path cost, not depth
▶ 4. Iterative Deepening DFS (IDDFS)
• Combines benefits of BFS and DFS: optimal + complete + linear space
• Runs DFS with depth limit 0, then 1, then 2... until goal found
• Time: O(b^d) | Space: O(b*d) — best of both worlds
▌ COMPARISON TABLE — ALL UNINFORMED STRATEGIES
Strategy Complete Optimal Time Space
BFS Yes Yes* O(b^d) O(b^d)
DFS No No O(b^m) O(bm)
UCS Yes Yes O(b^(C*/ε)) O(b^(C*/ε))
IDDFS Yes Yes* O(b^d) O(bd)

📌 * = optimal when step costs are equal

◈ INFORMED (HEURISTIC) SEARCH STRATEGIES

Uses problem-specific knowledge — a heuristic function — to guide the search.
▶ Greedy Best-First Search
• Expands node that appears closest to goal using heuristic h(n)
• NOT optimal — can go down wrong paths
• Fast but not reliable
▶ A* Search
• Combines actual cost g(n) and heuristic h(n): f(n) = g(n) + h(n)
• Optimal and complete if heuristic is admissible
• Best informed search algorithm — widely used
▌ CONCLUSION
Search strategies are evaluated on completeness, optimality, time complexity, and space complexity.
Uninformed strategies (BFS, DFS, UCS, IDDFS) use no problem-specific knowledge, while informed
strategies (Greedy, A*) use heuristic functions to guide the search. BFS is complete and optimal but
memory-intensive. DFS uses little memory but is neither complete nor optimal. A* is complete,
optimal, and uses heuristics efficiently — making it the preferred algorithm for most practical
problems.
PYQ 9. Heuristic Function
📋 PYQ — 2023 Q2c — 5 Marks
[ 5 Marks MARKS ]

▌ INTRODUCTION
In many search problems, the state space is astronomically large and uninformed strategies cannot
find solutions in reasonable time. A heuristic function allows the search algorithm to use problem-
specific knowledge to focus on the most promising paths — dramatically reducing search effort.
▌ DEFINITION
Heuristic Function h(n): A function that estimates the cost of the cheapest path from a given node
n to the goal state. It provides a 'hint' about which states are worth exploring. h(n) = 0 if n is the goal
state.
▌ ADMISSIBILITY — CRITICAL PROPERTY
Admissible Heuristic: A heuristic that NEVER overestimates the actual cost to reach the goal. i.e.,
h(n) ≤ h*(n) for all nodes n, where h*(n) is the true cost.
An admissible heuristic is OPTIMISTIC — it assumes the path will be at least
as good as it estimates

Example: Straight-line distance (hSLD) to Bucharest

Arad → Bucharest: hSLD = 366 km
Actual road distance may be MORE than 366 km
But NEVER LESS than straight-line distance
Therefore: hSLD is ADMISSIBLE

▌ HEURISTIC FOR 8-PUZZLE — TWO EXAMPLES

▶ h1 — Misplaced Tiles
• Count of tiles NOT in their goal position
• Admissible — each misplaced tile needs at least 1 move
State: 1 2 3 Goal: 1 2 3
4 _ 6 4 5 6
7 5 8 7 8 _

Misplaced tiles: 5 and 8 are wrong → h1 = 2

▶ h2 — Manhattan Distance
• Sum of distances (horizontal + vertical) each tile must move to reach goal
• Admissible — each tile needs at minimum Manhattan distance moves
• h2 DOMINATES h1 — always greater or equal — more informed
Tile 5 is at (2,1), should be at (1,1): distance = |2-1| + |1-1| = 1
Tile 8 is at (2,2), should be at (2,0): distance = |2-2| + |2-0| = 2
h2 = 1 + 2 = 3 (larger than h1=2 → more informative → fewer nodes expanded)

▌ HEURISTIC DOMINANCE
If h2(n) ≥ h1(n) for all nodes n, and both are admissible, then h2 DOMINATES h1. Using h2 results in
fewer nodes being expanded. Always prefer the larger (more informed) admissible heuristic.
Comparing h1 vs h2 on 8-puzzle:
 Average nodes expanded with h1 = ~13,000 at depth 14
Average nodes expanded with h2 = ~400 at depth 14
→ h2 is ~32x more efficient than h1

Property Definition
Admissible h(n) ≤ h*(n) — never overestimates — guarantees optimal solution with A*
Consistent/ h(n) ≤ c(n,a,n') + h(n') — triangle inequality — guarantees A* optimality with
Monotone graph search
Dominant h2(n) ≥ h1(n) for all n — h2 is more informed — expands fewer nodes

▌ CONCLUSION
A heuristic function h(n) estimates the cost from node n to the goal, enabling informed search
algorithms to prioritize promising paths. An admissible heuristic never overestimates, guaranteeing
that A* finds the optimal solution. For the 8-puzzle, Manhattan distance (h2) dominates misplaced
tiles (h1) because it is always greater or equal and more accurately estimates remaining cost —
resulting in dramatically fewer node expansions.
PYQ 10. Blind Search vs Heuristic Search
📋 PYQ — 2023 Q3b (5 marks) + 2024 Q4b (4 marks) — BOTH YEARS
[ 4–5 Marks MARKS ]

▌ INTRODUCTION
Search strategies fall into two fundamental categories based on whether they use additional
knowledge about the problem. Blind (uninformed) search uses only the problem definition, while
heuristic (informed) search uses additional domain knowledge to guide the search toward promising
areas of the state space.
▌ COMPARISON TABLE — MAIN ANSWER
Aspect Blind/Uninformed Search Heuristic/Informed Search
Knowledge used Problem definition only Problem + heuristic function h(n)
Direction Systematic — explores all directions Guided — focuses on promising paths
Efficiency Low — expands many irrelevant High — expands fewer nodes
nodes
Heuristic Not used h(n) estimates cost to goal
Time complexity Higher — O(b^d) or worse Lower — depends on heuristic quality
Space complexity Higher Lower
Optimality BFS/UCS optimal; DFS not A* optimal with admissible heuristic
Completeness BFS complete; DFS may not be A* complete with admissible h(n)
Examples BFS, DFS, UCS, IDDFS Greedy Best-First, A*
Use case When no domain knowledge When problem-specific knowledge
available exists

▌ VISUAL ANALOGY — EXPLAIN THIS IN EXAM

Blind Search: Heuristic Search:
Like finding a key in a Like finding a key using a
dark room by checking metal detector — goes directly
every corner systematically toward where the key likely is

Blind: A→B→C→D→E→F→GOAL Heuristic: A→C→F→GOAL

(7 nodes expanded) (4 nodes expanded)

Heuristic is SMARTER — uses knowledge to skip unlikely paths

▶ Blind Search Algorithms

• BFS: Level by level — complete + optimal but memory-intensive
• DFS: Deep paths first — memory-efficient but not optimal
• UCS: Lowest cost first — optimal for varying step costs
• IDDFS: Combines BFS+DFS — optimal, complete, linear space
▶ Heuristic Search Algorithms
• Greedy Best-First: Expands node closest to goal by h(n) — fast but not optimal
• A*: Expands by f(n) = g(n) + h(n) — optimal, complete, most efficient
▌ CONCLUSION
Blind search strategies use only the problem definition and explore the state space without guidance
— they are complete and sometimes optimal but often inefficient. Heuristic search uses a heuristic
function h(n) to estimate distance to goal, focusing exploration on promising paths and dramatically
reducing nodes expanded. A* combines the benefits of both: it uses actual cost g(n) plus heuristic
h(n) and is both optimal and efficient with an admissible heuristic.
PYQ 11. A* Algorithm with Example
📋 PYQ — 2023 Q4b (8 marks) + 2024 Q3a (7 marks) — BOTH YEARS — MUST KNOW
[ 7–8 Marks MARKS ]

⚡ A* appeared in BOTH 2023 and 2024. It WILL appear again. Master the numerical example.
▌ INTRODUCTION
A* (pronounced A-star) is the most widely used informed search algorithm in AI. It combines the
completeness and optimality of Uniform Cost Search with the efficiency of Greedy Best-First Search.
A* is used in GPS navigation, game AI, robotics path planning, and countless other applications.
▌ DEFINITION
A* Algorithm: An informed search algorithm that evaluates nodes using f(n) = g(n) + h(n), where
g(n) is the actual cost from start to node n, and h(n) is the heuristic estimate from n to goal. It
expands nodes in order of increasing f-value.
▌ THE KEY FORMULA — WRITE THIS FIRST
f(n) = g(n) + h(n)

where:
f(n) = total estimated cost of cheapest solution through n
g(n) = actual cost of path from START to current node n
h(n) = heuristic estimate of cost from n to GOAL

A* expands the node with MINIMUM f(n) first

If h(n) is ADMISSIBLE → A* is OPTIMAL and COMPLETE

▌ A* ALGORITHM STEPS
1. Initialize: Add start node to OPEN list
f(start) = g(start) + h(start) = 0 + h(start)

2. Loop:
a. Pick node n with MINIMUM f(n) from OPEN list
b. If n is GOAL → return solution path
c. Move n to CLOSED list
d. For each neighbor n' of n:
- Calculate g(n') = g(n) + cost(n, n')
- Calculate f(n') = g(n') + h(n')
- If n' not in OPEN or CLOSED: add to OPEN
- If n' in OPEN with higher f: update it

3. If OPEN list empty → no solution

▌ NUMERICAL EXAMPLE — ROMANIA MAP (STANDARD EXAM EXAMPLE)

Find shortest path from Arad to Bucharest. h(n) = straight-line distance to Bucharest.
Straight-line distances h(n) to Bucharest:
Arad=366, Sibiu=253, Timisoara=329, Zerind=374
Fagaras=176, Rimnicu Vilcea=193, Pitesti=100
Bucharest=0

Road distances (step costs):

Arad→Sibiu=140, Arad→Timisoara=118, Arad→Zerind=75
 Sibiu→Fagaras=99, Sibiu→Rimnicu Vilcea=80
Fagaras→Bucharest=211, Rimnicu→Pitesti=97
Pitesti→Bucharest=101

STEP 1: Expand Arad (f=0+366=366)

OPEN: Sibiu(f=140+253=393), Timisoara(f=118+329=447), Zerind(f=75+374=449)

STEP 2: Expand Sibiu (lowest f=393)

g(Sibiu)=140
Fagaras: g=140+99=239, f=239+176=415
Rimnicu Vilcea: g=140+80=220, f=220+193=413
OPEN: Rimnicu(413), Fagaras(415), Timisoara(447), Zerind(449)

STEP 3: Expand Rimnicu Vilcea (lowest f=413)

g(Rimnicu)=220
Pitesti: g=220+97=317, f=317+100=417
OPEN: Fagaras(415), Pitesti(417), Timisoara(447), Zerind(449)

STEP 4: Expand Fagaras (lowest f=415)

g(Fagaras)=239
Bucharest: g=239+211=450, f=450+0=450
OPEN: Pitesti(417), Bucharest(450), Timisoara(447), Zerind(449)

STEP 5: Expand Pitesti (lowest f=417)

g(Pitesti)=317
Bucharest: g=317+101=418, f=418+0=418
Update Bucharest: f=418 (better than 450)
OPEN: Bucharest(418), Timisoara(447), Zerind(449)

STEP 6: Expand Bucharest (lowest f=418)

GOAL REACHED!

OPTIMAL PATH: Arad→Sibiu→Rimnicu Vilcea→Pitesti→Bucharest

TOTAL COST: 140+80+97+101 = 418 km

▌ PROPERTIES OF A*
Property Value Condition
Complete YES If branching factor b is finite
Optimal YES If h(n) is admissible (never overestimates)
Time Complexity O(b^d) Depends on heuristic quality
Space Complexity O(b^d) Keeps all nodes in memory

▌ CONCLUSION
A* evaluates each node using f(n) = g(n) + h(n) — combining actual path cost with heuristic estimate.
It expands the node with minimum f-value first, ensuring that the first goal node expanded is on the
optimal path. With an admissible heuristic (one that never overestimates), A* is both complete and
optimal. In the Romania example, A* finds the optimal path Arad→Sibiu→Rimnicu
Vilcea→Pitesti→Bucharest with total cost 418 km, correctly preferring it over the shorter-appearing
path through Fagaras (450 km).
PYQ 12. Hill Climbing Search + Disadvantages
📋 PYQ — 2023 Q3a (10 marks) + 2024 Q4a (7 marks) — BOTH YEARS
[ 7–10 Marks MARKS ]

⚡ Hill Climbing appeared in BOTH years with high marks. Master the 8-Queens example and all 3
problems.
▌ INTRODUCTION
Hill Climbing is a local search algorithm that continuously moves toward improving states without
maintaining a search tree. Like climbing a hill in fog — always step upward — until you reach the top.
It is memory-efficient and fast, but suffers from getting stuck at local optima.
▌ DEFINITION
Hill Climbing: A local search algorithm that starts from an initial state and iteratively moves to the
neighboring state with the highest value (or lowest cost), stopping when no neighbor is better than
the current state.
▌ HILL CLIMBING ALGORITHM
function HILL-CLIMBING(problem):
current = initial_state
loop:
neighbor = highest_valued_successor(current)
if [Link] <= [Link]:
return current // local maximum found
current = neighbor

(Uses heuristic h(n) — but minimizes cost, not maximizes value)

▌ DIAGRAM — HILL CLIMBING LANDSCAPE

Value
│ ╭─╮ ← Global Maximum
│ ╭─╮ │ │
│ LOCAL→ ─╯ │ PLATEAU│ │
│ MAX ╰──╮ │ │
│ │ │ │
│ ╭╮ RIDGE │ │ │
│ ╭──╯╰──╮ ╰─────╯ │
│──╯ ╰──────────────╯
└─────────────────────────── State

Hill climbing gets STUCK at local maximum

Cannot cross valleys to reach global maximum

▌ 8-QUEENS EXAMPLE — STANDARD EXAM NUMERICAL

Problem: Place 8 queens on 8x8 chessboard so no queen attacks another. Heuristic h = number of
attacking pairs (minimize this).
Initial State: Queens placed randomly
h = 17 (17 attacking pairs)

Hill Climbing evaluates all moves (move each queen within its column)
Best move reduces h from 17 to 12
Apply that move → h = 12
 Continue: 12 → 10 → 7 → 5 → 3 → 1 → ...

STUCK at local minimum with h=1:

One pair of queens is attacking
EVERY possible move increases h
Hill climbing STOPS here — stuck in local minimum

Solution: h=0 (no attacking pairs) — hill climbing may not reach it

▌ THREE MAIN PROBLEMS

▶ 1. Local Maxima (Most Common Problem)
• Agent reaches a state that is better than ALL neighbors but NOT the global optimum
• Algorithm stops here thinking it's the best — it's actually just locally best
Like climbing a small hill next to Mount Everest
You reach the top of the small hill — but Everest is elsewhere

▶ 2. Plateaus (Flat Local Maxima)

• Area of the state space where all neighboring states have the SAME value
• Algorithm cannot determine which direction to move — gets confused
• Variant: Sideways moves allowed to escape plateaus (but risk infinite loops)
▶ 3. Ridges
• A sequence of local maxima that are not directly connected to each other
• The slope goes up in a direction that cannot be taken as a single action
• Very difficult for hill climbing to navigate
▌ VARIANTS OF HILL CLIMBING
Variant How it works Advantage
Simple Hill Climbing Moves to first neighbor that Fast but very greedy
improves current
Steepest Ascent Moves to BEST neighbor at Better quality — standard version
each step
Stochastic Randomly chooses from uphill Avoids some local maxima
moves
Random Restart Restarts from random state Complete with enough restarts — best fix
after getting stuck
Simulated Annealing Allows occasional downhill Escapes local maxima — globally optimal
moves with probability
e^(ΔE/T)

▌ DISADVANTAGES OF HILL CLIMBING

• NOT Complete — may not find solution even if one exists
• NOT Optimal — stops at local maximum, not global maximum
• Highly sensitive to initial state — different starts give different results
• Gets permanently stuck at local maxima, plateaus, and ridges
• No backtracking — cannot recover from bad moves
• Performance depends heavily on the landscape of the state space
▌ CONCLUSION
Hill Climbing is an efficient local search algorithm that iteratively moves to the best neighboring state
without storing the entire search path. It is memory-efficient and fast but suffers three major
problems: local maxima (suboptimal peaks), plateaus (flat regions), and ridges (oblique peaks). The
8-queens example illustrates how hill climbing succeeds quickly in about 86% of cases but gets stuck
in 14% of cases. Random-restart hill climbing addresses this limitation by running multiple times from
different initial states, making it probabilistically complete.
PYQ 13. Local Search and Optimization Problems
📋 PYQ — 2024 Q3c — 4 Marks
[ 4 Marks MARKS ]

▌ INTRODUCTION
Classical search algorithms find paths to goals, but many problems only care about the solution
STATE, not the path to reach it. Local search operates on a single 'current state' and improves it
iteratively — like tuning a radio dial to find the clearest signal rather than planning a route to reach
the transmitter.
▌ DEFINITION
Local Search: A search algorithm that operates on a single current state (rather than maintaining a
frontier of unexplored paths) and moves to neighboring states to improve the solution. It does NOT
retain the path.
▌ OBJECTIVE FUNCTION LANDSCAPE
Objective
Function
Value ← Global Maximum (GOAL)
│ ╭────╮
│ ╭──╮ │ │
│ │ │ │ ╰─────╮
│ │ ↑ local │ │
│ │ max │ │
└──────────────────────── State Space

Goal: Find state at GLOBAL MAXIMUM

Local search: climbs hill but may stop at local max

▌ KEY ADVANTAGES OF LOCAL SEARCH

• Uses very little memory — only stores current state (constant space)
• Can find reasonable solutions in HUGE or infinite state spaces
• Suitable when solution path doesn't matter — only final state
• Good for optimization problems (maximize/minimize objective function
▌ EXAMPLES OF OPTIMIZATION PROBLEMS
Problem Objective Function State
8-Queens Minimize attacking pairs Board configuration
Traveling Salesman Minimize total tour distance City visit order
Job Scheduling Minimize completion time Task assignment
Neural Network Minimize prediction error Network weights
Training

▌ LOCAL SEARCH ALGORITHMS

Algorithm Method Escapes Local Max?
Hill Climbing Always move to best neighbor No — gets stuck
 Algorithm Method Escapes Local Max?
Simulated Annealing Random moves; accept worse with Yes — probabilistically
probability e^(ΔE/T)
Local Beam Search Maintain k states simultaneously; Partially
move all to best neighbors
Genetic Algorithm Combine best states to produce Yes — through crossover
offspring

▌ CONCLUSION
Local search algorithms are ideal for optimization problems where only the final state matters and the
state space is too large for systematic exploration. Unlike tree search, they use constant memory by
maintaining only the current state. The main challenge is escaping local maxima — hill climbing gets
stuck while simulated annealing and genetic algorithms use probabilistic techniques to overcome this
limitation.
PYQ 14. DFS vs Best-First Search
📋 PYQ — 2024 Q4c — 4 Marks
[ 4 Marks MARKS ]

▌ COMPARISON TABLE — MAIN ANSWER

Aspect Depth-First Search (DFS) Best-First Search
Type Uninformed (blind) Informed (heuristic)
Data Structure Stack (LIFO) Priority Queue (min-heap)
Expansion Order Deepest node first Node with lowest h(n) first
Heuristic Not used Uses h(n) to guide search
Complete No (may loop infinitely) Yes (with repeated state check)
Optimal No No (Greedy BFS not optimal)
Time Complexity O(b^m) O(b^m) worst case
Space Complexity O(b*m) — linear O(b^m) — stores frontier
Good for Memory-limited problems Large spaces with good heuristic
Weakness Gets lost in infinite paths Gets trapped in local optima

▌ VISUAL COMPARISON
DFS (follows deepest path): Best-First (follows best h(n)):

A A
/ \ / \
B C h: B=5, C=3 B C
/ \ \ D=6, E=2 B=5 C=3
D E F F=4, G=1

DFS order: A→B→D→E→C→F Best-First: A→C→G (follows h)

(goes deep into B's subtree (skips to most promising node)
before exploring C)

▌ CONCLUSION
DFS is an uninformed strategy that explores the deepest path first using a stack, using linear memory
but risking infinite loops and suboptimal solutions. Best-First Search uses a heuristic h(n) to prioritize
the most promising nodes, making it more directed and efficient in practice. However, Greedy Best-
First is not optimal — it can be led astray by a misleading heuristic. A* improves on Best-First by
combining h(n) with actual cost g(n) to guarantee optimality.
━━━━━━ UNIT II: WILL ASK ━━━━━━
WILL ASK 2. State Space Representation + Simulated Annealing
🔥 WILL ASK — State Space never explained alone — Simulated Annealing never appeared — Both
high probability
[ 4–5 Marks MARKS ]

◈ PART A — STATE SPACE REPRESENTATION

▌ Definition
State Space: The set of all possible states that can be reached from the initial state by applying any
sequence of valid actions. It is represented as a graph where nodes are states and edges are
actions.
▌ STATE SPACE COMPONENTS
Component Symbol Meaning
Initial State S Starting point of the agent
State Set S All possible configurations
Action Function A(s) Set of actions available in state s
Transition Model T(s,a) Result of taking action a in state s
Goal Test G(s) Returns true if s is a goal state
Path Cost C(p) Sum of step costs along path p

▌ WATER JUG PROBLEM — STATE SPACE EXAMPLE

Given two jugs: 4-liter (X) and 3-liter (Y). Goal: Get exactly 2 liters in the 4-liter jug.
State: (x, y) where x = water in 4-liter jug, y = water in 3-liter jug
Initial State: (0, 0) Goal State: (2, 0)

Actions (operators):
1. Fill X: (x,y) → (4,y)
2. Fill Y: (x,y) → (x,3)
3. Empty X: (x,y) → (0,y)
4. Empty Y: (x,y) → (x,0)
5. Pour X→Y: (x,y) → (x-d, y+d) where d = min(x, 3-y)
6. Pour Y→X: (x,y) → (x+d, y-d) where d = min(y, 4-x)

Solution Path:
(0,0)→Fill X→(4,0)→Pour X into Y→(1,3)→Empty Y→(1,0)
→Pour X into Y→(0,1)→Fill X→(4,1)→Pour X into Y→(2,3)→GOAL!

Answer: (2,3) — 2 liters in 4-liter jug ✓

◈ PART B — SIMULATED ANNEALING

▌ Definition
 Simulated Annealing: A probabilistic local search algorithm that, unlike hill climbing, sometimes
accepts moves to WORSE states — with a probability that decreases over time. Based on the
annealing process in metallurgy — slowly cooling metal to minimize defects.
▌ KEY IDEA
Hill Climbing: NEVER accepts worse states → gets stuck
Simulated Annealing: SOMETIMES accepts worse states → escapes local maxima

Acceptance probability = e^(ΔE / T)

where ΔE = (new_value - current_value) = negative if worse
T = Temperature (high early, decreases over time)

If T is high (early): accepts bad moves frequently → extensive exploration

If T is low (late): rarely accepts bad moves → converges to good solution

▌ ALGORITHM
function SIMULATED-ANNEALING(problem, schedule):
current = initial_state
for t = 1 to ∞:
T = schedule(t) // temperature decreases over time
if T = 0: return current
next = random_successor(current)
ΔE = [Link] - [Link]
if ΔE > 0: // next is better
current = next // always accept improvement
else: // next is worse
current = next with probability e^(ΔE/T) // sometimes accept

Property Hill Climbing Simulated Annealing

Accept worse moves Never Yes, with probability e^(ΔE/T)
Complete No Yes (with slow enough cooling)
Optimal No Yes (theoretically, if T→0 slowly)
Inspiration Greedy ascent Metallurgy — cooling steel
Application Quick solutions VLSI design, TSP, scheduling

▌ CONCLUSION
State space representation formalizes any search problem as a graph of states connected by actions
— the Water Jug problem is a classic example. Simulated Annealing extends hill climbing by
occasionally accepting moves to worse states based on temperature T, allowing escape from local
maxima. As temperature decreases (cooling schedule), the algorithm converges to a good global
solution — trading thorough exploration early for refinement later.
QUICK REVISION CHEAT SHEET — AI EXAM

◈ UNIT I — RAPID RECALL

AI = build rational agents (Russell & Norvig)
Agent = perceives via SENSORS, acts via ACTUATORS
Agent Function: Percept Sequence → Action
Rational = maximizes expected performance (not omniscient)
PEAS = Performance, Environment, Actuators, Sensors

AGENT TYPES: Reflex→Model→Goal→Utility→Learning

Reflex: IF dirty THEN suck (no memory)
Model: has internal world state (memory)
Goal: plans to achieve goals (GPS)
Utility: maximizes happiness function (chess AI)
Learning: improves from experience (4 components)

LEARNING AGENT 4 PARTS:

Performance Element = takes actions
Learning Element = updates knowledge from feedback
Critic = evaluates vs Performance Standard
Problem Generator = explores to discover new knowledge

ENV PROPERTIES: Fully/Partial | Single/Multi | Det/Stoch

Episodic/Seq | Static/Dynamic | Discrete/Continuous

◈ UNIT II — RAPID RECALL

PROBLEM FORMULATION: Initial State, Actions, Transition,
Goal Test, Path Cost

SEARCH EVALUATION: Completeness, Optimality, Time, Space

b = branching factor, d = goal depth, m = max depth

BFS: Complete YES, Optimal YES*, Time O(b^d), Space O(b^d)

DFS: Complete NO, Optimal NO, Time O(b^m), Space O(bm)
UCS: Complete YES, Optimal YES, Time O(b^C*/ε)
IDDFS: Complete YES, Optimal YES*, Time O(b^d), Space O(bd)

HEURISTIC h(n) = estimate of cost from n to goal

Admissible: h(n) ≤ h*(n) — NEVER overestimates
h1 (8-puzzle) = misplaced tiles
h2 (8-puzzle) = Manhattan distance (DOMINATES h1)

A* FORMULA: f(n) = g(n) + h(n)

g(n) = actual cost from start to n
h(n) = heuristic estimate from n to goal
A* is COMPLETE + OPTIMAL if h(n) is ADMISSIBLE

ROMANIA PATH (A*): Arad→Sibiu→Rimnicu→Pitesti→Bucharest=418km

HILL CLIMBING: move to best neighbor, stop when no better neighbor

Problems: Local Maxima, Plateaus, Ridges
Fix: Random Restart Hill Climbing

SIMULATED ANNEALING: accept worse with prob e^(ΔE/T)

T high = explores freely | T low = refines solution

ALL THE BEST! GO ACE THAT AI EXAM! 🔥