Advanced Comprehensive Study

Resource for Artificial

Intelligence
SPPU Third Year Computer Engineering -
Semester 6
Units I & II: Introduction and Problem-Solving
Extended Edition with In-Depth Analysis and Practice
Prepared for: Savitribai Phule Pune University (SPPU)
Course: Artificial Intelligence (310251)
Academic Year: 2025-26
Edition: Comprehensive Extended Version (50+ Pages)

Document Features:

Complete syllabus coverage with theoretical depth

50+ worked examples and case studies
Detailed algorithm implementations with complexity proofs
30+ practice problems with solutions
SPPU exam pattern analysis and previous year questions
Quick reference cards and formula sheets

Unit I: Introduction to Artificial

Intelligence (07 Hours)
1.1 Introduction to Artificial Intelligence
What is Artificial Intelligence?
Artificial Intelligence (AI) is the science and engineering of creating
intelligent machines that can perceive their environment, reason
about information, learn from experience, and take actions to
achieve specific goals. AI systems aim to simulate human cognitive
functions such as learning, problem-solving, reasoning, and decision-
making[1].
Formal Definition: AI is the study of agents that receive percepts
from the environment and perform actions. Each such agent
implements a function that maps percept sequences to actions, and
we seek to build agents that exhibit rational behavior—doing the
"right thing" based on what it perceives and the knowledge it
possesses[2].
Four Approaches to AI:

AI research historically follows four distinct approaches, organized

along two dimensions:

Human-Centered Rationality-Centered
Systems that think like Systems that think
Thinking humans (cognitive rationally (logical
modeling) reasoning)
Systems that act like Systems that act
Acting humans (Turing Test rationally (rational agent
approach) approach)

Table 1: Four perspectives on AI

Modern AI Focus: Contemporary AI emphasizes the rational agent
approach—designing agents that achieve the best expected outcome
given available information, rather than perfectly mimicking human
behavior[1][2].
Key Characteristics of AI Systems:

• Perception: Ability to sense and interpret environmental data

through sensors
 • Reasoning: Logical processing of information to draw
conclusions
• Learning: Capability to improve performance based on
experience
• Action: Taking appropriate steps to achieve goals
• Adaptation: Adjusting behavior based on changing
environments
Real-World Applications (2026):

• Healthcare: Medical diagnosis systems, drug discovery,

personalized treatment plans, surgical robots, predictive health
analytics
• Autonomous Vehicles: Self-driving cars using perception and
decision-making, Tesla Autopilot, Waymo autonomous taxis
• Finance: Fraud detection, algorithmic trading, credit scoring,
robo-advisors, risk assessment
• Virtual Assistants: Siri, Alexa, Google Assistant for natural
language interaction, smart home automation
• Recommendation Systems: Netflix, Amazon, YouTube content
suggestions, Spotify music recommendations
• Manufacturing: Quality control, predictive maintenance, supply
chain optimization, collaborative robots
• Agriculture: Crop monitoring, precision farming, yield
prediction, automated harvesting
• Cybersecurity: Threat detection, intrusion prevention, malware
analysis, security orchestration
• Education: Personalized learning platforms, intelligent tutoring
systems, automated grading
• Climate Science: Weather forecasting, climate modeling,
disaster prediction, resource management
Case Study: Medical Diagnosis System

Consider an AI system for diagnosing diabetic retinopathy from

retinal images:
Input: Retinal photographs from patients
Processing: Deep learning model trained on 130,000+ images
analyzes features
 Output: Classification (no DR, mild, moderate, severe,
proliferative)
Performance: Matches or exceeds ophthalmologist accuracy
(94% sensitivity, 98% specificity)
Impact: Enables screening in remote areas without
specialists[1]
This exemplifies AI's potential to democratize expert-level
capabilities.

Foundations of Artificial Intelligence

AI draws upon multiple disciplines to create intelligent systems[1]:

Foundation Contribution to AI
Questions about knowledge, reasoning,
Philosophy
consciousness, and the nature of mind
Formal logic, probability theory, algorithms,
Mathematics
computation theory
Understanding human cognition,
Psychology
perception, learning, and behavior
Data structures, algorithms, programming
Computer Science
languages, software engineering
Natural language processing, syntax,
Linguistics
semantics, pragmatics
Brain structure, neural networks, cognitive
Neuroscience
processes
Feedback systems, optimization, stability
Control Theory
analysis

Table 2: Interdisciplinary foundations of AI

1.2 History of Artificial Intelligence

Key Milestones in AI Development
The Birth of AI (1943-1956)

• 1943: Warren McCulloch and Walter Pitts created the first

mathematical model of neural networks, demonstrating how
 simple artificial neurons could compute logical functions
• 1950: Alan Turing proposed the Turing Test to evaluate machine
intelligence, asking "Can machines think?" and establishing the
imitation game as a benchmark
• 1951: Christopher Strachey wrote the first AI program—a
checkers-playing program
• 1956: The term "Artificial Intelligence" was coined at the
Dartmouth Conference by John McCarthy, Marvin Minsky,
Claude Shannon, and others—marking the official birth of AI as
a field. The proposal stated: "Every aspect of learning or any
other feature of intelligence can in principle be so precisely
described that a machine can be made to simulate it"
Detailed Timeline Insight:

The Dartmouth Conference was remarkably ambitious, predicting

significant AI progress within a generation. While these predictions
proved overoptimistic, the conference established AI as a legitimate
academic discipline and attracted talented researchers and
funding[1].
Early Enthusiasm (1956-1974)

• Development of early AI programs like Logic Theorist and

General Problem Solver
• Chess-playing programs and theorem provers
• Initial optimism about achieving human-level AI

The First AI Winter (1974-1980)

• Limitations in computational power and memory

• Inability to handle real-world complexity
• Reduced funding and interest in AI research

Expert Systems Era (1980-1987)

• Rise of knowledge-based systems

• MYCIN for medical diagnosis, XCON for computer configuration
• Commercial success of AI applications
The Second AI Winter (1987-1993)
 • Limitations of expert systems
• High maintenance costs
• Market disappointment
Modern AI Renaissance (1993-Present)

• Machine learning and deep learning breakthroughs

revolutionize the field
• Big data availability and increased computational power (GPU
acceleration)
• 1997: IBM's Deep Blue defeats world chess champion Garry
Kasparov (6-game match, 3.5-2.5)
• 2005: Stanley wins DARPA Grand Challenge (autonomous
vehicle completes 132-mile course)
• 2011: IBM Watson wins Jeopardy! against human champions
using natural language processing
• 2012: Deep learning breakthrough—AlexNet wins ImageNet
competition by huge margin
• 2014: GANs (Generative Adversarial Networks) introduced by
Ian Goodfellow
• 2016: AlphaGo defeats world Go champion Lee Sedol 4-1
(considered impossible by many experts)
• 2017: Transformer architecture introduced, revolutionizing NLP
• 2018: AlphaZero masters chess, shogi, and Go purely through
self-play
• 2020: GPT-3 demonstrates few-shot learning capabilities with
175 billion parameters
• 2022: ChatGPT launches, bringing conversational AI to
mainstream
• 2023-2024: Multimodal models (GPT-4, Gemini) process text,
images, audio simultaneously
• 2025-2026: AI agents demonstrate complex reasoning, planning,
and tool use
Significance of AlphaGo Victory:

Go was considered the "holy grail" of board game AI due to its vast
search space ( possible board positions vs. in chess).
AlphaGo's victory demonstrated that AI could master intuitive,
pattern-recognition tasks previously thought unique to human
cognition[1].

1.3 State of the Art in AI

Current Capabilities and Trends (2026)
Machine Learning and Deep Learning

AI systems today demonstrate remarkable capabilities in pattern

recognition, natural language processing, and decision-making. Deep
learning models with billions of parameters can understand context,
generate human-like text, create images, and solve complex
problems[1].
Key Areas of Advanced AI:

1. Multimodal AI: Systems processing images, text, audio, and

video simultaneously—models like GPT-4V and Gemini
understand cross-modal relationships
2. Generative AI: Creating new content including text (ChatGPT),
images (DALL-E, Midjourney), music (MuseNet), and code
(GitHub Copilot)
3. Reinforcement Learning: Agents learning optimal strategies
through trial and error—applications in robotics, game playing,
and resource optimization
4. Transfer Learning: Applying knowledge from one domain to
another—foundation models fine-tuned for specific tasks
5. Explainable AI (XAI): Making AI decision-making transparent
and interpretable—critical for healthcare, finance, and legal
applications
6. Edge AI: Running AI models on local devices rather than cloud—
smartphones, IoT devices, autonomous vehicles
7. Federated Learning: Training models across decentralized data
sources while preserving privacy
8. Neural Architecture Search: Automated design of optimal
neural network architectures
9. Few-Shot and Zero-Shot Learning: Learning from minimal
examples or task descriptions
10. Neuro-Symbolic AI: Combining neural networks with symbolic
reasoning for better interpretability
Performance Benchmarks (2026):

Human
Task AI Performance
Performance
ImageNet ~95% top-5
~98% top-5 accuracy
Classification accuracy
Medical Image
~94% (specialists) ~96% (best models)
Analysis
Translation (EN-
- ~40+ BLEU score
FR)
Reading
~91% (SQuAD) ~93% (best models)
Comprehension
2850 (top 3500+
Chess (Elo rating)
humans) (Stockfish/AlphaZero)

Table 3: AI vs. human performance on standardized tasks

Emerging Trends:

Agentic AI: Systems that can plan, use tools, and accomplish
complex goals autonomously
AI Alignment: Ensuring AI systems behave according to human
values and intentions
Sustainable AI: Developing energy-efficient models and
reducing carbon footprint
Embodied AI: Physical robots with advanced perception and
manipulation capabilities[1][5]
Industry Applications:

• Energy Efficiency: Google DeepMind reduced data center

cooling costs by 40 percent using AI optimization
• Game Playing: AlphaGo, AlphaZero achieving superhuman
performance
• Healthcare: AI-powered diagnostic tools matching or exceeding
expert radiologists
• Climate Modeling: Advanced weather prediction and climate
change analysis
1.4 Risks and Benefits of AI
Benefits of AI
1. Automation of Repetitive Tasks: Freeing humans for creative
and strategic work
2. Enhanced Decision-Making: Data-driven insights for better
choices
3. Improved Healthcare: Early disease detection, personalized
medicine
4. Increased Productivity: Optimizing processes across industries
5. Scientific Discovery: Accelerating research in physics, biology,
chemistry
6. Accessibility: Assistive technologies for people with disabilities

Risks and Challenges

1. Job Displacement: Automation replacing human workers in
various sectors
2. Bias and Fairness: AI systems reflecting and amplifying societal
biases
3. Privacy Concerns: Data collection and surveillance capabilities
4. Security Vulnerabilities: AI systems susceptible to adversarial
attacks
5. Lack of Transparency: "Black box" decision-making in complex
models
6. Ethical Dilemmas: Autonomous weapons, deepfakes,
manipulation
7. Dependence: Over-reliance on AI systems reducing human
skills
Example: Bias in AI Systems

Facial recognition systems have shown higher error rates for darker-
skinned individuals, reflecting biases in training data. This
demonstrates the importance of diverse datasets and ethical AI
development practices.
1.5 Intelligent Agents
Definition and Concept
An intelligent agent is an autonomous entity that perceives its
environment through sensors and acts upon it through actuators to
achieve specific goals. Agents form the foundation of AI systems by
creating a formal framework for designing and analyzing intelligent
behavior[2][14].
Formal Agent Definition:

An agent is anything that:

1. Perceives its environment through sensors
2. Acts on that environment through actuators
3. Has a performance measure defining success criteria
4. Makes decisions based on its percept sequence (complete
history of perceptions)
Abstract Agent Model:

Sensors → Agent → Actuators

↑↓
Percepts Actions
↑↓
Environment
The agent's behavior is described by the agent function that maps
percept sequences to actions:

where is the set of all possible percept sequences and is the set
of actions[2][14].
Agent Components:

• Percepts: Information received from the environment via

sensors
• Percept Sequence: Complete history of everything the agent
has perceived
 • Agent Function: Mathematical mapping from percept
sequences to actions
• Agent Program: Implementation of the agent function on a
physical architecture
Mathematical Representation:

where represents all possible percept sequences and represents

the set of possible actions.

Types of Agents
1. Simple Reflex Agents

Simple reflex agents select actions based only on the current percept,
ignoring percept history[14].
• Structure: Condition-action rules (if-then statements)
• Advantage: Fast, simple implementation
• Limitation: Only works in fully observable environments
• Example: Thermostat that turns heating on when temperature
drops below threshold
2. Model-Based Reflex Agents

These agents maintain an internal state to track aspects of the

environment that aren't immediately observable[2][14].
• Structure: Internal model of the world + condition-action rules
• Advantage: Handles partially observable environments
• Components: Tracks how world evolves and how agent's
actions affect it
• Example: Self-driving car maintaining map of surroundings and
traffic conditions
3. Goal-Based Agents

Goal-based agents make decisions by considering future

consequences and whether they achieve desired goals.
• Structure: Goal information + search/planning algorithms
 • Advantage: Flexible, can adapt to different goals
• Process: Evaluates action sequences to find paths to goals
• Example: GPS navigation system finding routes to destinations
4. Utility-Based Agents

Utility-based agents maximize a utility function that measures the

desirability of states.
• Structure: Utility function + decision theory
• Advantage: Handles trade-offs between conflicting goals
• Process: Chooses actions with highest expected utility
• Example: Investment portfolio manager balancing risk and
return
5. Learning Agents

Learning agents improve performance over time through

experience[2][44]. This is the most sophisticated agent type,
combining elements of all previous types with learning capabilities.
Four Key Components:

1. Learning Element: Responsible for making improvements

based on feedback—updates internal knowledge and behavior
patterns
2. Performance Element: Selects external actions (the "doing"
component)—this is essentially one of the agent types described
above
3. Critic: Provides feedback on how well the agent is doing—
compares actual performance to performance standard
4. Problem Generator: Suggests exploratory actions that might
lead to new experiences—ensures agent doesn't get stuck in local
optima
Learning Agent Architecture:

Performance Standard → Critic → Feedback

↓
Sensors → Performance Element → Actuators
↑↓
Learning Element
↑
Problem Generator → Exploratory Actions
Advantage: Adapts to unknown environments, can start with little
knowledge and become competent through experience
Process:

1. Performance element makes decisions and acts

2. Critic evaluates outcomes against performance standard
3. Learning element modifies performance element based on
feedback
4. Problem generator suggests exploratory actions to discover new
knowledge
Example Applications:

• Spam Filter: Learns to identify spam from user corrections

(marking emails as spam/not spam)
• Recommendation System: Learns user preferences from clicks,
ratings, and viewing patterns
• Game-Playing Agent: Improves strategy through self-play and
outcome analysis
• Autonomous Trading: Learns profitable patterns from market
data and trading outcomes
Example: Taxi Driver Learning Agent

Performance Element: Drives the taxi using current knowledge

Critic: Observes outcomes (passenger satisfaction, tips, safety
incidents, fuel efficiency)
Learning Element: Updates driving strategies based on critic
feedback
Problem Generator: Suggests trying new routes during off-peak
hours to discover faster paths
Initially, a learning taxi agent might make poor route choices. Over
time, it learns optimal routes, when to wait for fares, how to interact
with passengers, and how to drive efficiently[2][44].
1.6 Agents and Environments
Environment Properties
The environment significantly shapes agent behavior and
performance. Understanding environment characteristics is crucial
for agent design[2][5].
1. Fully Observable vs. Partially Observable

• Fully Observable: Agent's sensors provide complete state

information
• Example (Fully): Chess game - all pieces visible
• Partially Observable: Agent has incomplete information about
state
• Example (Partially): Poker - hidden cards, self-driving car -
occluded objects
Impact on Performance: In fully observable environments, agents
can plan with certainty. Partial observability requires maintaining
beliefs about unobserved aspects, increasing complexity[5].
2. Deterministic vs. Stochastic

• Deterministic: Next state completely determined by current

state and action
• Example (Deterministic): Sudoku puzzle solving
• Stochastic: Randomness or uncertainty in outcomes
• Example (Stochastic): Dice games, weather prediction, stock
markets
Impact on Performance: Deterministic environments enable precise
planning, while stochastic environments require probabilistic
reasoning and robust strategies[5].
3. Episodic vs. Sequential

• Episodic: Agent's experience divided into independent episodes

• Example (Episodic): Image classification - each image
processed independently
• Sequential: Current decisions affect future situations
 • Example (Sequential): Chess - each move impacts subsequent
positions
4. Static vs. Dynamic

• Static: Environment unchanged while agent deliberates

• Example (Static): Crossword puzzle solving
• Dynamic: Environment changes during agent's decision-making
• Example (Dynamic): Self-driving car navigation with moving
traffic
Impact on Performance: Dynamic environments require real-time
decision-making and continuous monitoring[5][8].
5. Discrete vs. Continuous

• Discrete: Finite number of distinct states and actions

• Example (Discrete): Chess positions
• Continuous: Infinite range of states or actions
• Example (Continuous): Robot arm control, autonomous driving

6. Single-Agent vs. Multi-Agent

• Single-Agent: Only one agent operating in environment

• Example (Single): Maze-solving robot
• Multi-Agent: Multiple agents that may cooperate or compete
• Example (Multi): Autonomous vehicles interacting, multi-
player games

Environment Examples Table

Environment Observable Deterministic Episodic Static
Chess Fully Deterministic Sequential Static
Poker Partially Stochastic Sequential Static
Self-driving
Partially Stochastic Sequential Dynami
car
Image
Fully Deterministic Episodic Static
classification
Robot soccer Partially Stochastic Sequential Dynami
Table 4: Environment characteristics for different AI applications

1.7 Good Behavior: The Concept of Rationality

What is Rationality?
A rational agent is one that does the "right thing" - selecting actions
that maximize its expected performance measure given available
information[18][21][24].
Definition: For each possible percept sequence, a rational agent
should select an action that is expected to maximize its performance
measure, given:
1. The performance measure defining success
2. The agent's prior knowledge of the environment
3. The actions the agent can perform
4. The agent's percept sequence to date

Key Concepts in Rationality

1. Rationality ≠ Omniscience

• An omniscient agent knows the actual outcome of its actions

• A rational agent makes the best decision with available
information
• Unexpected outcomes don't make an agent irrational if the
decision was sound given what was known
Example: Crossing a street rationally after checking both ways
doesn't become irrational if an unexpected speeding car appears.
2. Rationality ≠ Perfection

• Rational agents maximize expected performance, not actual

performance
• Outcomes may be suboptimal due to uncertainty
• Focus is on decision quality, not result quality
3. Information Gathering

Rational agents perform actions to modify future percepts - a crucial

aspect of rationality. This includes:
 • Exploration to learn about the environment
• Sensor adjustments to gather better information
• Experiments to test hypotheses
4. Learning and Adaptation

Rational agents should learn from experience to:

• Compensate for incomplete prior knowledge
• Adapt to environmental changes
• Improve performance over time
• Become independent of initial knowledge after sufficient
experience

The PEAS Framework

PEAS provides a structured approach to specifying agent design
requirements[18][27]:
Components:

• Performance Measure: Criteria defining success

• Environment: The task environment in which the agent
operates
• Actuators: Mechanisms for acting on the environment
• Sensors: Devices for perceiving the environment

Example 1: Autonomous Taxi

Component Specification
Safe travel, maximize profit, minimize fuel
Performance consumption, obey traffic laws, maximize
passenger comfort
Roads, traffic, pedestrians, weather
Environment
conditions, passengers
Steering, accelerator, brake, turn signals,
Actuators
horn, display
Cameras, lidar, GPS, speedometer,
Sensors
accelerometer, passenger input

Table 5: PEAS description for autonomous taxi

Example 2: Medical Diagnosis System

Component Specification
Accurate diagnosis, minimize tests, early
Performance
detection, patient safety
Patient symptoms, medical history, test
Environment
results, medical knowledge base
Test recommendations, treatment
Actuators
suggestions, referrals, reports
Patient input, laboratory data, imaging
Sensors
results, electronic health records

Table 6: PEAS description for medical diagnosis system

1.8 Structure of Agents

Agent Architecture
Agent programs run on physical architectures to produce the agent
function. The architecture provides:
• Computing devices with sensors and actuators
• Operating system and runtime environment
• Programming interfaces for perception and action

General Agent Structure:

Detailed Agent Architectures

Modern AI systems implement various architectural patterns
depending on complexity requirements[32][35][41]:
1. Reactive Architectures

Map current conditions directly to predefined actions through simple

rules[32][35].
Characteristics:

No internal state maintenance

 Direct sensor-to-actuator mapping
Minimal computational overhead
Fast, deterministic responses
Implementation Pattern:

Current Percept → Rule Matching → Action Selection → Execute

Action
Advantages:

Lightning-fast response times (process thousands of decisions

per second)
Simple to implement and debug
Predictable behavior
Suitable for real-time systems
Limitations:

Only works in fully observable environments

Cannot handle history-dependent decisions
No learning or adaptation
Limited to simple, reactive tasks
Real-World Example: Fraud Detection

A reactive fraud detection agent instantly flags transactions based on

simple rules:
Transaction amount > $10,000 → Flag for review
Transaction from blacklisted country → Block immediately
Velocity: >5 transactions in 1 minute → Freeze account
This system processes millions of transactions per second with sub-
millisecond latency[32].
2. Deliberative Architectures

Maintain symbolic world models and use reasoning to make

decisions[35][41].
Components:
 World Model: Symbolic representation of environment state
Planning Module: Search and reasoning algorithms
Execution Monitor: Tracks plan execution and handles failures

Implementation Pattern:

Sensors → Update World Model → Plan Reasoning → Action Selection

→ Actuators
↑↓
└───────────────── Execution Feedback
─────────────────┘

Advantages:

Handles complex, goal-oriented tasks

Reasons about future consequences
Can explain decisions (symbolic representation)
Adapts plans when conditions change
Limitations:

Computationally expensive (planning overhead)

Slower response times
Requires accurate world models
May fail in highly dynamic environments
Real-World Example: Warehouse Robot

A deliberative warehouse robot:

1. Maintains map of warehouse layout (world model)
2. Receives order picking request (goal)
3. Plans optimal route considering obstacles and other robots
4. Executes plan while monitoring for changes
5. Replans if obstacles detected
3. Hybrid Architectures

Combine reactive and deliberative layers—the current state-of-the-art

approach[32][35].
Two-Loop Design:
 Fast Reactive Loop: Handles time-critical operations (safety,
collision avoidance)
Deliberative Layer: Provides strategic planning and high-level
reasoning
Architecture Pattern:

Deliberative Layer (Slow)

↓ Goals/Strategies
┌──────────────────────────────┐
│ Planning & Reasoning │
└──────────────┬────────────────┘
↓ High-level Commands
┌──────────────────────────────┐
│ Reactive Layer (Fast) │
│ - Obstacle Avoidance │
│ - Safety Reflexes │
└──────────────┬────────────────┘
↓ Motor Commands
Environment

Coordination Mechanisms:

Subsumption: Lower layers can override higher layers for

safety
Priority-Based: Assign priorities to different behaviors
Arbitration: Mediator selects between competing actions

Advantages:

Best of both worlds (speed + intelligence)

Robust in dynamic environments
Handles both reactive responses and strategic planning
Suitable for real-world applications
Limitations:

Architectural complexity
Coordination overhead between layers
Difficult to debug interaction between layers
Real-World Example: Autonomous Vehicles

Self-driving cars use hybrid architectures[32][35]:

Reactive Layer (10-100 Hz):

Emergency braking if obstacle detected

Lane keeping corrections
Immediate collision avoidance
Deliberative Layer (1-10 Hz):

Route planning to destination

Lane change decisions
Parking maneuvers
When a pedestrian suddenly steps into the road, the reactive layer
immediately brakes (safety-critical). Meanwhile, the deliberative
layer plans alternative routes around congestion.
4. Layered Architectures

Organize functionality across multiple abstraction levels—common

in enterprise systems[32][35].
Seven Standard Layers:

1. Perception Layer: Environmental sensing and data filtering

2. Knowledge Representation: Structured information storage
(databases, knowledge graphs)
3. Reasoning and Decision-Making: Logic and inference engines
4. Action Selection: Choose appropriate actions based on
reasoning
5. Execution Layer: Translate actions to actuator commands
6. Learning and Adaptation: Update behavior based on
experience
7. Tool Integration: External capability interfaces (APIs, services)
Layer Interaction:

Lower tiers: Fast, low-risk behaviors

Upper tiers: Strategic reasoning and complex decisions
 Vertical communication: Information flows up, commands flow
down
Horizontal communication: Layers at same level can coordinate
Advantages:

Modular design simplifies development

Clear separation of concerns
Easy to add new features at appropriate layer
Scales naturally with complexity
Limitations:

Communication overhead between layers

Potential bottlenecks at layer boundaries
More complex than simpler architectures
Real-World Example: Enterprise Resource Planning (ERP)

Manufacturing ERP system with layered architecture[32]:

Layer 7 (Strategic): Annual production planning, supplier selection
Layer 6 (Tactical): Monthly inventory optimization
Layer 5 (Operational): Weekly scheduling
Layer 4 (Control): Daily task assignment
Layer 3 (Execution): Real-time machine control
Layer 2 (Sensing): Sensor data collection
Layer 1 (Physical): Actuator commands

Lower layers handle fast inventory checks (milliseconds), while

upper layers make strategic procurement decisions (days/weeks).

Modern Agent Components (2026)

Contemporary AI agents incorporate these core modules[32]:
1. Perception Module

Ingests raw signals from APIs, text, sensor feeds, and filters noise to
extract task-relevant information.
Example: Vision system processes camera feeds:
 Raw image (1920×1080 pixels, 3 channels)
Object detection (identify pedestrians, vehicles)
Semantic segmentation (road, sidewalk, obstacles)
Relevant features extracted for decision-making
2. Memory System

Combines short-term context (working memory) with long-term

knowledge storage.
Implementation:

Short-term: Current conversation context, recent observations

Long-term: Vector databases for semantic search, knowledge
graphs for relationships
Episodic: Memory of specific past experiences
Procedural: Learned skills and procedures

Example: Customer service chatbot:

Short-term: Current conversation (last 5 messages)

Long-term: Customer history, product catalog, FAQs
Episodic: Remember previous interactions with this customer
Procedural: Learned responses to common issues
3. Planning Engine

Decomposes goals into ordered steps and adapts strategy when

conditions change[32].
Capabilities:

Break complex tasks into manageable sequences

Handle partial observability and uncertainty
Replan when execution fails
Optimize for multiple objectives
Example: Travel planning agent:

1. Goal: "Plan trip to Paris"

2. Decompose: Book flights → Reserve hotel → Plan itinerary →
Arrange transport
3. For each subtask, generate specific actions
 4. Execute with monitoring and replanning
4. Action Execution Layer

Transforms plans into real-world actions while handling errors and

rollbacks[32].
Features:

Action scheduling and sequencing

Error detection and recovery
Retry logic with exponential backoff
Transaction semantics (rollback on failure)
5. Feedback Loop

Monitors outcomes against goals to refine perception, memory, and

future plans[32].
Closed-Loop Control:

Goals → Planning → Execution → Environment

↑↓
└──────── Feedback & Learning ───────┘

This architecture enables continuous improvement and adaptation to

changing conditions.

Agent Program Design Patterns

Simple Reflex Agent Pseudocode:

function SIMPLE-REFLEX-AGENT(percept) returns action

static: rules // set of condition-action rules

state ← INTERPRET-INPUT(percept)
rule ← RULE-MATCH(state, rules)
action ← [Link]
return action

Model-Based Reflex Agent Pseudocode:

function MODEL-BASED-REFLEX-AGENT(percept) returns action
static: state // current world state
model // how world evolves
rules // condition-action rules
action // most recent action

state ← UPDATE-STATE(state, action, percept, model)

rule ← RULE-MATCH(state, rules)
action ← [Link]
return action

Goal-Based Agent Pseudocode:

function GOAL-BASED-AGENT(percept) returns action

static: state // current world state
model // world model
goal // desired state

state ← UPDATE-STATE(state, action, percept, model)

actions ← GENERATE-ACTIONS(state)

for each action in actions:

result ← PREDICT-RESULT(state, action, model)
if SATISFIES-GOAL(result, goal):
return action

Unit II: Problem-Solving (07 Hours)

2.1 Solving Problems by Searching
Problem-Solving as Search
Many AI problems can be formulated as search problems where an
agent must find a sequence of actions leading from an initial state to a
goal state. This abstraction enables systematic exploration of solution
spaces[3][15].
Key Insight: Problem-solving agents use atomic representations -
states are treated as indivisible "black boxes" with no internal
structure considered during search.

2.2 Problem-Solving Agents

Components of a Well-Defined Problem
A problem is formally defined by five components[9]:
1. Initial State: The starting state of the agent
2. Actions: Set of possible actions available in each state - function
ACTIONS(s) returns applicable actions
3. Transition Model: Function RESULT(s, a) describing the state
resulting from action a in state s
4. Goal Test: Function determining if a state is a goal state
5. Path Cost: Function assigning numeric cost to action sequences -
typically sum of step costs
State Space: The set of all states reachable from the initial state
through any sequence of actions forms a state space, which can be
visualized as a directed graph.
Solution: A sequence of actions leading from the initial state to a goal
state. An optimal solution has the lowest path cost among all
solutions.

Problem Formulation Process

1. Goal Formulation: Define what constitutes success
2. Problem Formulation: Decide what actions and states to
consider
3. Search: Explore state space to find solution
4. Execution: Perform recommended actions

2.3 Example Problems

8-Puzzle Problem
Description: A 3×3 grid with 8 numbered tiles and one blank space.
Goal is to reach a specific configuration by sliding tiles into the blank
space.
Formulation:

• States: All possible arrangements of tiles

• Initial State: Any starting configuration
• Actions: Move blank Left, Right, Up, or Down
• Transition Model: Resulting configuration after moving blank
• Goal Test: Match target configuration
• Path Cost: Number of moves (each move costs 1)

State Space Size: 9! = 362,880 possible states (half unreachable from

any given state)

Traveling Salesperson Problem (TSP)

Description: Find shortest route visiting each city exactly once and
returning to start.
Formulation:

• States: Partial tours (sequence of cities visited)

• Initial State: Starting city
• Actions: Visit any unvisited city
• Goal Test: All cities visited
• Path Cost: Total distance traveled

Complexity: NP-hard problem with possible tours for

cities

Maze Navigation
Description: Agent must find path from start position to goal position
in a maze with obstacles.
Formulation:

• States: Agent's (x, y) position in maze

• Initial State: Start position coordinates, e.g., (0, 0)
• Actions: Move North, South, East, or West (if not blocked by
walls)
• Transition Model: RESULT((x,y), North) = (x, y+1) if no wall
• Goal Test: Position matches goal coordinates, e.g., (9, 9)
• Path Cost: Number of steps (uniform cost of 1 per move)
Example Maze:

S..#.
.#.#.
.....

.#..
....G
Where: S = Start, G = Goal, # = Wall, . = Free space
Solution Path:
S→(0,1)→(0,2)→(1,2)→(2,2)→(2,3)→(3,3)→(4,3)→(4,4)=G
State Space Size: For n×n maze: possible positions (but many
unreachable due to walls)

N-Queens Problem
Description: Place N queens on N×N chessboard so no two queens
attack each other (no two in same row, column, or diagonal).
Formulation:

• States: Arrangements of 0 to N queens on board

• Initial State: Empty board
• Actions: Place queen in any empty square
• Goal Test: N queens placed, none attacking each other
• Path Cost: Not applicable (only final state matters)

Better Formulation (More Efficient):

• States: Arrangements with one queen per column in leftmost k

columns, none attacking
• Initial State: No queens placed
• Actions: Place queen in column k+1 in non-attacking square
• Goal Test: N queens placed (automatically non-attacking)

State Space Reduction:

Naive formulation: states for 8-queens

 Better formulation: states
This demonstrates how problem formulation dramatically affects
search efficiency!

Cryptarithmetic Puzzles
Description: Assign digits 0-9 to letters to make arithmetic valid.

Example: SEND + MORE = MONEY

Formulation:

• States: Partial assignments of digits to letters

• Initial State: Empty assignment
• Actions: Assign unused digit to unassigned letter
• Goal Test: All letters assigned, arithmetic equation holds
• Constraints: Each letter gets unique digit, leading letters ≠ 0

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

Verification: 9567 + 1085 = 10652 ✓

Robot Path Planning

Description: Mobile robot navigating from start to goal in continuous
2D space with obstacles.
Formulation:

• States: (x, y, θ) position and orientation

• Initial State: Starting pose
• Actions: Move forward distance d, rotate by angle α
• Goal Test: Within ε distance of goal position
• Path Cost: Total distance traveled or energy consumed

Challenges:

Continuous state space (infinite states)

Non-holonomic constraints (car-like robots can't move
sideways)
Obstacle avoidance with safety margins
Dynamic obstacles (other robots, people)
Discretization Approaches:

Grid-based: Divide space into cells

Roadmap methods: Graph of collision-free paths
Potential fields: Attractive goal, repulsive obstacles

Water Jug Problem

Description: You have two jugs: 4-gallon and 3-gallon. Goal: Measure
exactly 2 gallons.
Formulation:

• States: (x, y) where x = gallons in 4-gal jug, y = gallons in 3-gal

jug
• Initial State: (0, 0) - both empty
• Actions:
1. Fill 4-gallon jug: (x, y) → (4, y)
2. Fill 3-gallon jug: (x, y) → (x, 3)
3. Empty 4-gallon jug: (x, y) → (0, y)
4. Empty 3-gallon jug: (x, y) → (x, 0)
5. Pour 4-gal into 3-gal: (x, y) → (max(0, x-(3-y)), min(3, x+y))
6. Pour 3-gal into 4-gal: (x, y) → (min(4, x+y), max(0, y-(4-x)))
• Goal Test: x = 2 or y = 2
• Path Cost: Number of operations

Solution Path:

1. (0,0) Fill 3-gal → (0,3)

2. (0,3) Pour 3-gal into 4-gal → (3,0)
3. (3,0) Fill 3-gal → (3,3)
4. (3,3) Pour 3-gal into 4-gal → (4,2) ✓ Goal reached!
Alternative solution exists in 6 steps.

2.4 Search Algorithms

General Search Tree Framework
All search algorithms follow a common pattern of expanding nodes in
a search tree:
Search Node Components:
 • State: The state in the state space
• Parent: Node that generated this node
• Action: Action applied to parent to generate this node
• Path Cost g(n): Cost from initial state to this node

Generic Search Algorithm:

function TREE-SEARCH(problem) returns solution or failure

frontier ← INSERT(MAKE-NODE([Link]-STATE))

loop do
if EMPTY?(frontier) then return failure
node ← REMOVE-FRONT(frontier)

if [Link]-TEST([Link]) then
return SOLUTION(node)

frontier ← INSERT-ALL(EXPAND(node, problem), frontier)

function EXPAND(node, problem) returns set of nodes

successors ← empty set
for each action in [Link]([Link]) do
child ← MAKE-NODE([Link]([Link], action))
[Link] ← node
[Link] ← action
[Link]-COST ← [Link]-COST + STEP-COST
add child to successors
return successors
Frontier/Open List: Set of nodes available for expansion
Explored/Closed Set: Set of nodes already expanded (used in graph
search)

Evaluating Search Algorithms

Search algorithms are evaluated on four criteria:
1. Completeness: Is the algorithm guaranteed to find a solution if
one exists?
2. Optimality: Does it find the optimal (lowest cost) solution?
 3. Time Complexity: How long does it take to find a solution?
4. Space Complexity: How much memory is required?
Complexity Measures:

• = branching factor (maximum successors per node)

• = depth of shallowest goal node
• = maximum depth of search tree
• = cost of optimal solution
• = minimum step cost

Time Complexity: Number of nodes generated during search

Space Complexity: Maximum number of nodes stored in memory

Why Complexity Matters:

For a tree with branching factor and goal depth :

Nodes generated: nodes
If each node takes 1 microsecond: 0.1 seconds (fast!)
But for : nodes = 2.8 hours!
For : nodes = 31,700 years of computation!
This exponential growth is why search algorithm choice matters
critically[33][39].

2.5 Uninformed Search Strategies

Uninformed (blind) search strategies have no additional information
about states beyond the problem definition. They can only distinguish
goal states from non-goal states[3][6][15].

Breadth-First Search (BFS)

Strategy: Expand shallowest unexpanded node first using FIFO
queue[16][22].
Algorithm Behavior:

1. Start at root node

2. Expand all nodes at depth 0
 3. Then expand all nodes at depth 1
4. Continue level-by-level until goal found
Implementation:

function BREADTH-FIRST-SEARCH(problem) returns solution or

failure
node ← MAKE-NODE([Link]-STATE)

if [Link]-TEST([Link]) then return SOLUTION(node)

frontier ← FIFO-QUEUE with node as only element

explored ← empty set

loop do
if EMPTY?(frontier) then return failure
node ← POP(frontier)
add [Link] to explored

for each action in [Link]([Link]) do

child ← CHILD-NODE(problem, node, action)

if [Link] not in explored or frontier then

if [Link]-TEST([Link]) then
return SOLUTION(child)
frontier ← INSERT(child, frontier)

Detailed Example: Maze Solving with BFS

Consider a robot navigating this 5×5 maze from S to G:

S..#.
.#.#.
.....
.#..
....G
BFS Execution Step-by-Step:

Initial State:

Frontier (FIFO Queue): [S(0,0)]

Explored: {}
Depth: 0
Iteration 1: Pop S(0,0)

Goal test: No
Add to explored: {S}
Generate successors: (0,1), (1,0) [no (0,-1) or (-1,0) - out of
bounds]
Frontier: [(0,1), (1,0)]
Depth: 1
Iteration 2: Pop (0,1)

Goal test: No
Explored: {S, (0,1)}
Successors: (0,2) [others blocked or explored]
Frontier: [(1,0), (0,2)]
Iteration 3: Pop (1,0)

Goal test: No
Explored: {S, (0,1), (1,0)}
Successors: None [all neighbors blocked or explored]
Frontier: [(0,2)]
Iteration 4: Pop (0,2)

Goal test: No
Explored: {S, (0,1), (1,0), (0,2)}
Successors: (0,3), (1,2)
Frontier: [(0,3), (1,2)]
Continue this process...

Final path found: S → (0,1) → (0,2) → (1,2) → (2,2) → (2,3) → (3,3) →

(4,3) → (4,4) = G
Path length: 8 steps (optimal)

Nodes explored: 18 nodes total

Key Insight: BFS guarantees finding the shortest path because it

explores all paths of length before exploring paths of length
[22]. Every node at depth is discovered before any node at depth
.
Performance Analysis for This Example:

Branching factor: ~2-3 (average successors per state)

Goal depth: 8
Time complexity: Generated ~18 nodes (much less than worst
case due to obstacles)
Space complexity: Maximum frontier size ~6 nodes
Optimality: Guaranteed (uniform cost)
Completeness: Yes (finite state space)[16][22]
Properties:

Property Value
Complete Yes (if is finite)
Optimal Yes (if step costs are equal)
Time Complexity
Space Complexity

Table 7: BFS performance characteristics

Advantages:

• Guaranteed to find shallowest solution

• Systematic exploration prevents missing solutions
• Works well for problems with shallow solutions

Disadvantages:
 • High memory requirements - stores all nodes at current level
• Slow for problems with deep solutions
• Explores many unnecessary nodes

Uniform-Cost Search (UCS)

Strategy: Expand node with lowest path cost using priority
queue.
Key Difference from BFS: UCS considers path costs, not just depth.
It's optimal for problems with varying step costs.
Algorithm:

function UNIFORM-COST-SEARCH(problem) returns solution or

failure
node ← MAKE-NODE([Link]-STATE)
frontier ← PRIORITY-QUEUE ordered by PATH-COST with node
explored ← empty set

loop do
if EMPTY?(frontier) then return failure
node ← POP(frontier) // lowest cost

if [Link]-TEST([Link]) then return SOLUTION(node)

add [Link] to explored

for each action in [Link]([Link]) do

child ← CHILD-NODE(problem, node, action)

if [Link] not in explored or frontier then

frontier ← INSERT(child, frontier)
else if [Link] in frontier with higher cost then
REPLACE with child in frontier

Properties:
 Complete Yes (if step cost )
Optimal Yes
Time Complexity
Space Complexity

Table 8: UCS performance ( = optimal solution cost)

Depth-First Search (DFS)

Strategy: Expand deepest unexpanded node first using LIFO
stack[19][25].
Algorithm Behavior:

1. Start at root node

2. Expand first child
3. Continue to deepest node before backtracking
4. Backtrack when dead end reached
5. Explore next branch
Implementation:

function DEPTH-FIRST-SEARCH(problem) returns solution or failure

frontier ← LIFO-STACK with MAKE-NODE([Link]-STATE)
explored ← empty set

loop do
if EMPTY?(frontier) then return failure
node ← POP(frontier)

if [Link]-TEST([Link]) then return SOLUTION(node)

add [Link] to explored

for each action in [Link]([Link]) do

child ← CHILD-NODE(problem, node, action)
if [Link] not in explored or frontier then
frontier ← PUSH(child, frontier)
Example: DFS vs BFS Comparison

For tree with branching factor 2 and goal at depth 3:

BFS explores: Level 0 (1 node), Level 1 (2 nodes), Level 2 (4 nodes),
Level 3 (8 nodes) = 15 nodes
DFS explores: Goes deep first, may find goal faster but no guarantee
of shortest path
Properties:

Complete No (can get stuck in infinite paths)

Optimal No
Time Complexity ( = max depth)
Space Complexity (much better than BFS!)

Table 9: DFS performance characteristics

Advantages:

• Low memory requirements - only stores nodes on current path

• Fast for problems where solutions are deep
• Good for exploring all solutions

Disadvantages:

• Can get trapped in infinite loops

• May find suboptimal solutions
• Poor performance if goal is shallow

Depth-Limited Search (DLS)

Strategy: DFS with predetermined depth limit .

Purpose: Addresses DFS problem of infinite paths by imposing depth

cutoff.
Properties:

• Complete if
• Not optimal
• Time:
 • Space:

Iterative Deepening Depth-First Search (IDDFS)

Strategy: Perform DLS with increasing depth limits: 0, 1, 2, 3, ... until
goal found.
Algorithm:

function ITERATIVE-DEEPENING-SEARCH(problem) returns solution

or failure
for depth = 0 to ∞ do
result ← DEPTH-LIMITED-SEARCH(problem, depth)
if result ≠ cutoff then return result
Why It Works: Combines benefits of BFS (completeness, optimality)
with DFS (low memory).
Properties:

Complete Yes
Optimal Yes (if step costs equal)
Time Complexity
Space Complexity

Table 10: IDDFS performance characteristics

Key Insight: Nodes at depth are generated once, depth twice,
depth three times, etc. Overhead is acceptable because most
nodes are at deepest level.

Comparison of Uninformed Search Strategies

 Algorithm Complete Optimal Time Space
BFS Yes Yes*
UCS Yes Yes
DFS No No
DLS No No
IDDFS Yes Yes*
*If all step costs are equal

Table 11: Uninformed search comparison

2.6 Informed (Heuristic) Search Strategies

Informed search uses domain-specific knowledge (heuristics) to guide
the search more efficiently toward the goal[3][6][12].
Heuristic Function : Estimated cost from node to nearest goal
state. For example, straight-line distance to goal in pathfinding
problems[17][20].
Key Advantage: Explores fewer nodes by focusing on promising
paths[3][6].

Greedy Best-First Search

Strategy: Expand node with lowest value (appears closest to
goal).
Evaluation Function:

Algorithm:

function GREEDY-BEST-FIRST-SEARCH(problem, h) returns solution

or failure
node ← MAKE-NODE([Link]-STATE)
frontier ← PRIORITY-QUEUE ordered by h with node
explored ← empty set

loop do
if EMPTY?(frontier) then return failure
node ← POP(frontier)
 if [Link]-TEST([Link]) then return SOLUTION(node)

add [Link] to explored

for each action in [Link]([Link]) do

child ← CHILD-NODE(problem, node, action)
if [Link] not in explored or frontier then
frontier ← INSERT(child, frontier)

Properties:

• Complete: No (can get stuck in loops)

• Optimal: No (ignores accumulated cost)
• Time: (but often much better with good heuristic)
• Space:

Example: In map navigation, always choose road that points most

directly toward destination. Fast but may miss cheaper routes.

A* Search Algorithm
A* is the most widely used informed search algorithm, combining
actual cost from start with estimated cost to goal[17][20]. It is
optimally efficient—no other optimal algorithm using the same
heuristic will expand fewer nodes.
Evaluation Function:

where:
• = actual cost from start to node (known, computed)
• = estimated cost from to goal (heuristic, estimated)
• = estimated total cost of cheapest solution through
(combined)
Intuition: At each step, A* selects the node that appears to be on the
best path to the goal—the one with lowest estimated total cost .
By combining what we know ( ) with what we estimate ( ), A*
balances between exploring closer nodes and nodes that seem to lead
more directly to the goal.
Why A Works:*
A* is a best-first search that uses as the
evaluation function. The key insight: if never overestimates,
then the first time A* selects a goal node, it has found the optimal
path[17][20][36].
Proof of Optimality (with Admissible Heuristic):

Let be a suboptimal goal with (where is optimal

cost).
Let be an unexpanded node on the optimal path to optimal goal .
Since is admissible:

But for suboptimal goal:

Therefore:
This means A* will expand before selecting . This argument
applies to all nodes on the optimal path, so A* must find the optimal
goal first before any suboptimal goal[17][34][43].
Consistency and Its Advantages:

A heuristic is consistent (monotonic) if:

for every node and successor , where is the step cost.

Geometric Interpretation: Triangle inequality—direct path can't be
longer than indirect path.
Theorem: Consistency implies admissibility[34][37][43][46].

Proof: By induction from goal backwards:

Base case: ✓
 Inductive step: Assume
By consistency:
✓

Key Advantage of Consistency: A* with consistent heuristic never

needs to reopen explored nodes. Once a node is expanded, the path
found is optimal for that node. This is because:

So -values along any path are non-decreasing. A* expands nodes in

order of increasing -value[34][40][46].
Algorithm:

function A-STAR-SEARCH(problem, h) returns solution or failure

node ← MAKE-NODE([Link]-STATE)
frontier ← PRIORITY-QUEUE ordered by f = g + h with node
explored ← empty set

loop do
if EMPTY?(frontier) then return failure
node ← POP(frontier) // lowest f value

if [Link]-TEST([Link]) then return SOLUTION(node)

add [Link] to explored

for each action in [Link]([Link]) do

child ← CHILD-NODE(problem, node, action)

if [Link] not in explored or frontier then

frontier ← INSERT(child, frontier)
else if [Link] in frontier with higher f then
REPLACE with child in frontier

Admissibility: Heuristic is admissible if it never overestimates

the cost to reach the goal: where is true cost[17]
[23].
Theorem: A* with admissible heuristic is optimal and complete.

Consistency (Monotonicity): Heuristic is consistent if for every node

and successor :

where is the step cost. Consistent heuristics are admissible.

Properties:

Complete Yes (with finite branching)

Optimal Yes (with admissible heuristic)
Time Complexity (but often much better)
Space Complexity (all nodes in memory)

Table 12: A* search performance

Comprehensive A Example: Grid Pathfinding*
Find shortest path from S to G on 5×5 grid with obstacles:
S..#.
.#.#.
.....

.#..
....G
Heuristic: Manhattan distance
Goal: G at position (4, 4)
Step cost: 1 per move (4-connected grid)

Detailed A Execution:*
Initialization:

Frontier (Priority Queue by ): [S(0,0)]

Explored: {}
For S: , ,
Iteration 1: Pop S (lowest )
Current: S(0,0),
Goal test: No
Add to explored: {S}
Generate successors:
(0,1): , ,
(1,0): , ,
Frontier: [(0,1) , (1,0) ] (tie—arbitrary order)
Iteration 2: Pop (0,1) (tied , chose first)
Current: (0,1),
Generate successors:
(0,2): , ,
(0,0): already explored
(1,1): blocked by obstacle #
Frontier: [(1,0) , (0,2) ]
Iteration 3: Pop (1,0) (tied )
Current: (1,0),
Generate successors:
(2,0): , ,
Others: explored or blocked
Frontier: [(0,2) , (2,0) ]
Iteration 4: Pop (0,2) (tied )
Current: (0,2),
Generate successors:
(0,3): , ,
(1,2): , ,
Frontier: [(2,0) , (0,3) , (1,2) ]
Key Observation: All nodes at are equally promising!
Iteration 5-12: Continue expanding nodes with , then ,
etc.
When (2,2) is expanded: , ,
 Successors include (2,3): , ,
When (3,3) is expanded: , ,
Successors include (4,3): , ,
When (4,3) is expanded: , ,
Successors include (4,4)=G: , ,
GOAL FOUND!

Optimal Path Reconstruction:

G(4,4) ← (4,3) ← (3,3) ← (2,3) ← (2,2) ← (1,2) ← (0,2) ← (0,1) ← S(0,0)
Solution: S → (0,1) → (0,2) → (1,2) → (2,2) → (2,3) → (3,3) → (4,3) → G

Path Cost: 8 steps (optimal)

Performance Analysis:

Metric BFS A*
Nodes expanded ~18 nodes ~12 nodes
Path length 8 (optimal) 8 (optimal)
Max frontier size ~6 nodes ~5 nodes
Guaranteed optimal? Yes Yes

Table 13: BFS vs A* on this example

Why A is Better:*
A* expands fewer nodes by using the heuristic to focus search toward
the goal. The Manhattan distance heuristic guides A* to explore paths
that move closer to G, avoiding wasteful exploration in wrong
directions[17][20].
Heuristic Quality:

Manhattan distance is:

Admissible: Never overestimates (straight-line distance is lower
bound)
 Consistent: for adjacent nodes (satisfies
triangle inequality)
This guarantees A* optimality and never reopening nodes[34][40].
What if we used a worse heuristic?

With (uninformed), A* becomes equivalent to Uniform-Cost

Search and expands as many nodes as BFS. The better the heuristic
estimates true distance, the fewer nodes A* must expand[17].

2.7 Heuristic Functions

Designing Good Heuristics
Characteristics of Effective Heuristics:

1. Admissible: Never overestimate actual cost to goal (necessary

for optimality)
2. Consistent: Satisfy triangle inequality (ensures efficiency,
implies admissibility)
3. Informative: Close to actual cost—higher values are better
(more informed)
4. Efficient to compute: Fast calculation—computation time
shouldn't exceed search savings
The Admissibility-Informativeness Trade-off:

An ideal heuristic would be (perfect knowledge of

remaining cost). But computing requires solving the problem!
Practical heuristics balance:
Being admissible (never overestimate)
Being as close to as possible (informative)
Being fast to compute
Example: For 8-puzzle:

(trivial heuristic): Admissible but uninformative—A*

becomes UCS
= misplaced tiles: Admissible, more informative, fast
= Manhattan distance: Admissible, even more
informative, still fast
 = actual cost: Perfect but requires solving the puzzle!
Effective Branching Factor:

Measures heuristic quality empirically. For a search tree with

nodes expanded to depth , the effective branching factor satisfies:

Good heuristics have lower (closer to 1 is better).

Example for 8-puzzle:

With :
With :
With :
Lower effective branching factor means exponentially fewer nodes
expanded![17][29]

Common Heuristic Functions

1. Manhattan Distance (L1 distance)

For grid-based problems with 4-way movement:

Use case: Maze navigation, tile puzzles

Properties: Admissible for problems without diagonal movement

2. Euclidean Distance (L2 distance)

For problems with unrestricted movement:

Use case: Real-world navigation, continuous space

Properties: Admissible for straight-line paths

3. Chebyshev Distance

For grid with 8-way movement (including diagonals):

4. Domain-Specific Heuristics

8-Puzzle Heuristics:

• = number of misplaced tiles (admissible)

• = sum of Manhattan distances of tiles from goal positions
(admissible)
Dominance: If for all , then dominates . A*
with will never expand more nodes than with .
For 8-puzzle: dominates and provides better guidance,
expanding fewer nodes on average.

Generating Heuristics from Relaxed Problems

Relaxation: Remove constraints from original problem to create
easier version. Optimal solution cost in relaxed problem becomes
heuristic for original problem.
Why Relaxation Works:

If a problem is a relaxation of problem (fewer restrictions),

then:
Any solution to is also a solution to
Cost of optimal solution to is ≤ cost of optimal solution to
Therefore, solution cost is admissible heuristic for
8-Puzzle Example:

Original Problem:

Tile can move from square A to square B if:

1. A and B are adjacent (horizontally or vertically)
2. B is blank
Relaxation 1: Remove constraint 2

Tile can move to any adjacent square (even if occupied)

Solution: Count misplaced tiles (each needs ≥1 move)
 Gives heuristic: = number of misplaced tiles
Relaxation 2: Remove both constraints

Tile can move to any square in one step

Solution: Sum of Manhattan distances for each tile
Gives heuristic: = sum of Manhattan distances
Admissibility Proof:

For : Each misplaced tile must move at least once, so

✓

For : Manhattan distance is minimum moves needed if tiles could

pass through each other, so ✓

Why Dominates :

For any state: because:

Manhattan distance counts every move needed to reach correct
position
Misplaced tiles only counts which tiles need to move (not how
far)
Example State:

123
456
7 - 8 (goal position)
123
456
7 8 (current state)
= 2 tiles misplaced (7 and blank)
= 2 moves (7 needs 1, blank needs 1) = 2
In this case equal, but always holds
Practical Impact:

For random 8-puzzle instances with optimal solution depth 12:

 expands ~3,644 nodes on average
expands ~227 nodes on average
is 16× more efficient[20][29]

Pattern Databases
Advanced Technique: Precompute exact solution costs for
subproblems.
Method:

1. Solve relaxed/simplified version of problem exhaustively

2. Store solutions in database (pattern database)
3. Use database lookups as heuristic values
8-Puzzle Pattern Database Example:

Create database for positions of tiles {1,2,3,4}:

Solve puzzle considering only these 4 tiles (ignore others)
Store optimal cost for every possible configuration
Database size: entries
Lookup is fast O(1) and gives admissible heuristic
Multiple Pattern Databases:

Can use multiple disjoint pattern databases and sum their values (still
admissible because they solve independent subproblems):

Example: Pattern DB for {1,2,3,4} + Pattern DB for {5,6,7,8}

This additive heuristic is even more informed than Manhattan

distance and dramatically reduces search!
Trade-off: Memory for speed—large pattern databases require
significant storage but provide excellent heuristics[17][29].
Landmark Heuristics
Idea: Precompute distances from key "landmark" states.

For any state , estimate distance as:

Uses triangle inequality to bound remaining distance.

Advantage: Works well for road networks and graph-based
problems where precomputation is feasible.

2.8 Local Search and Optimization Problems

Local search algorithms operate using a single current state and
move to neighboring states, without maintaining search paths. Useful
for optimization problems where path is irrelevant[29].
Characteristics:

• Use very little memory (only current state)

• Can find reasonable solutions in large/infinite state spaces
• Useful when goal is the solution itself, not the path

Hill-Climbing Search
Strategy: Continually move to neighbor with highest value (steepest
ascent).
Algorithm:

function HILL-CLIMBING(problem) returns state (solution)

current ← [Link]-STATE

loop do
neighbor ← highest-valued successor of current

if VALUE(neighbor) ≤ VALUE(current) then

return current
 current ← neighbor

Problems with Hill-Climbing:

1. Local Maxima: Peak that is not the highest point

2. Ridges: Sequence of local maxima difficult to navigate
3. Plateaus: Flat area of state space with no uphill direction
Solutions:

• Random restarts from different initial states

• Stochastic hill climbing (probabilistic moves)
• Random sideways moves on plateaus

Simulated Annealing
Strategy: Allow occasional downhill moves to escape local maxima,
with probability decreasing over time.
Inspired by: Metallurgical annealing process where controlled
cooling allows atoms to find low-energy configurations.
Algorithm:

function SIMULATED-ANNEALING(problem, schedule) returns

solution
current ← [Link]-STATE

for t = 1 to ∞ do
T ← schedule(t) // temperature
if T = 0 then return current

next ← random successor of current

ΔE ← VALUE(next) - VALUE(current)

if ΔE > 0 then
current ← next
else
current ← next with probability e^(ΔE/T)
Key Parameter: Temperature controls probability of downhill
moves. High allows more exploration; low focuses on
exploitation.

Genetic Algorithms
Strategy: Evolve population of solutions using operations inspired by
biological evolution: selection, crossover, mutation.
Components:

• Individuals: Candidate solutions encoded as strings

(chromosomes)
• Fitness Function: Evaluates quality of each individual
• Selection: Choose parents based on fitness
• Crossover: Combine parent genes to create offspring
• Mutation: Random changes to maintain diversity

Algorithm:

function GENETIC-ALGORITHM(population, FITNESS) returns

individual
repeat
new_population ← empty

for i = 1 to SIZE(population) do
parent1 ← SELECT(population, FITNESS)
parent2 ← SELECT(population, FITNESS)
child ← CROSSOVER(parent1, parent2)

if random < mutation_probability then

child ← MUTATE(child)

add child to new_population

population ← new_population

until some individual is fit enough or time elapsed

 return best individual in population

Advantages: Can explore large search spaces; inherently parallel;

good for complex optimization.

2.9 Memory-Bounded Search Algorithms

Real-world applications often face memory limitations. These
algorithms address A*'s exponential space complexity[36].

Iterative Deepening A* (IDA*)

Strategy: Apply iterative deepening with -cost cutoff instead of
depth cutoff.
Algorithm:

function IDA-STAR(problem, h) returns solution or failure

cutoff ← h(initial state)

loop do
result ← DFS-F-LIMITED(initial_node, cutoff)

if result = FOUND then return solution

if result = ∞ then return failure

cutoff ← result // next f-cost threshold

function DFS-F-LIMITED(node, cutoff) returns solution or f-cost

if f(node) > cutoff then return f(node)
if GOAL-TEST(node) then return FOUND

min_cost ← ∞

for each successor of node do

result ← DFS-F-LIMITED(successor, cutoff)

if result = FOUND then return FOUND

 if result < min_cost then min_cost ← result

return min_cost

Properties:

Time: Same as A* (may expand some nodes multiple times)

Space: (linear!)
Optimal: Yes (with admissible heuristic)
Complete: Yes
Overhead Analysis:

Nodes at cutoff level expanded once, cutoff- level twice, etc. Similar
to IDDFS, overhead is acceptable because most nodes are at deepest
level[36].
Best For: Problems where solution depth is relatively shallow and
heuristic has few distinct values.

Simplified Memory-Bounded A* (SMA*)

Strategy: Use all available memory, drop least promising node when
memory full.
Key Ideas:

Track backed-up -values for dropped nodes

When memory fills, drop worst leaf node (highest -value)
Regenerate node if it becomes best option again
Properties:

Optimal: If solution fits in memory

Complete: If solution fits in memory
Space: Uses exactly the memory available
Time: Can be high if regeneration frequent
Advantage: Utilizes all available memory efficiently—no memory
wasted.
Limitation: Performance degrades if optimal solution path doesn't fit
in memory (thrashing).

Recursive Best-First Search (RBFS)

Strategy: Recursive depth-first search that mimics best-first with
linear space.
Mechanism:

Explore current best path recursively

Track alternative path costs
Backtrack if alternative becomes better
Update -values to avoid reexpanding
Properties:

Space: (linear)
Time: Higher than A* due to regeneration
Optimal: Yes (with admissible heuristic)
Complete: Yes
Trade-off: Sacrifices time for space—may regenerate nodes multiple
times but uses minimal memory[36].

Key Formulas and Concepts Summary

Important Mathematical Relations
Agent Function:

A Evaluation Function:*

Manhattan Distance:

Euclidean Distance:
Admissibility Condition:

Consistency Condition:

Time and Space Complexity Table

Algorithm Complete Optimal Time Space
BFS Yes Yes*
DFS No No
IDDFS Yes Yes*
UCS Yes Yes
Greedy No No
A* Yes Yes**
*Equal step costs, **Admissible heuristic

Table 14: Complete algorithm comparison

Advanced Practice Problems and Solutions

Problem Set 1: Agent Design
Problem 1.1: Design complete PEAS specifications for these systems:

(a) Automated Stock Trading Agent

Solution:
 Component Specification
Maximize profit, minimize risk, maintain
Performance diversified portfolio, comply with
regulations, minimize transaction costs
Stock exchanges (NYSE, NASDAQ), market
data feeds, news sources, regulatory
Environment
requirements, other traders, economic
indicators
Buy orders, sell orders, limit orders, stop-
Actuators
loss orders, portfolio rebalancing commands
Real-time price feeds, trading volume data,
Sensors news sentiment analysis, technical
indicators, fundamental data APIs

Agent Type: Utility-based agent (balancing profit vs. risk) with

learning capabilities
Environment Classification:

Partially observable (can't see all market information)

Stochastic (unpredictable market movements)
Sequential (current trades affect future positions)
Dynamic (market changes continuously)
Continuous (prices, quantities continuous)
Multi-agent (competing with other traders)
(b) Smart Agricultural Drone

Solution:
 Accurate crop health assessment, efficient
field coverage, battery conservation, early
Performance
problem detection, actionable insights for
farmers
Agricultural fields, crops at various growth
Environment stages, weather conditions, soil types, pests,
diseases
Flight controls (altitude, direction, speed),
Actuators camera positioning, spray dispensers (for
targeted treatment), data upload commands
Multispectral camera, GPS, thermal sensor,
Sensors altitude sensor, battery monitor, weather
sensors

Problem 1.2: Classify these environments along all six dimensions:

(a) Multiplayer Online Battle Arena (MOBA) Game Agent

Solution:

Dimension Classification Justification

Partially Fog of war hides enemy
Observable
Observable positions
Critical hits, random damage
Deterministic Stochastic
ranges
Actions affect future game
Episodic Sequential
state
Game state changes during
Static Dynamic
deliberation
Finite abilities, positions,
Discrete Discrete
states
Agents Multi-agent 10 players competing (5v5)

This is one of the most complex environment types!

(b) Warehouse Inventory Management System

Solution:

Fully Complete inventory database

Observable
Observable access
Uncertain demand, delivery
Deterministic Stochastic
delays
Ordering decisions affect future
Episodic Sequential
stock
Inventory changes while system
Static Dynamic
computes
Discrete Discrete Integer quantities, discrete SKUs
Multiple facilities, suppliers,
Agents Multi-agent
customers

Problem Set 2: Uninformed Search

Problem 2.1: Apply BFS to find shortest path from S to G:

Graph:
S -- A -- C
|||
B -- D -- G
Edge costs all equal to 1.
Solution:

BFS Execution:

Frontier (FIFO Queue): [S]

Explored: {}

Iteration 1: Pop S

Explored: {S}
Successors: A, B
Frontier: [A, B]
Iteration 2: Pop A
 Explored: {S, A}
Successors: S(explored), C, D
Frontier: [B, C, D]
Iteration 3: Pop B

Explored: {S, A, B}
Successors: S(explored), D(in frontier)
Frontier: [C, D]
Iteration 4: Pop C

Explored: {S, A, B, C}
Successors: A(explored), G
Frontier: [D, G]
Iteration 5: Pop D

Explored: {S, A, B, C, D}
Successors: A(explored), B(explored), G(in frontier)
Frontier: [G]
Iteration 6: Pop G → GOAL FOUND!

Path Reconstruction:
G←C←A←S
Optimal Path: S → A → C → G
Path Cost: 3

Nodes Expanded: 6 (S, A, B, C, D, G)

Nodes Generated: 9 total

Why Optimal: BFS explores all paths of length 2 before length 3,

guaranteeing shortest path.
Problem 2.2: Compare DFS vs BFS on tree:

A
/\
B C
 /\ \
D E F

Goal: F
DFS Solution:

Stack: [A]
Explored: {}
Pop A → Push C, B (right to left)
Pop B → Push E, D
Pop D → Leaf, backtrack
Pop E → Leaf, backtrack
Pop C → Push F
Pop F → GOAL FOUND
Path: A → C → F
Cost: 2
Nodes Expanded: 6 (A, B, D, E, C, F)

BFS Solution:

Queue: [A]

Pop A → Add B, C
Pop B → Add D, E
Pop C → Add F
Pop D → Leaf
Pop E → Leaf
Pop F → GOAL FOUND
Path: A → C → F
Cost: 2
Nodes Expanded: 6

Analysis:

Both found optimal path (cost 2)

DFS explored left subtree first (D, E before C)
BFS explored level-by-level (B, C before D, E)
Space: DFS used O(h)=O(2), BFS used O(b^d)=O(4)
 DFS got lucky here—won't always find optimal path!

Problem Set 3: Informed Search

Problem 3.1: Apply A* to graph with heuristics:

Graph edges (bidirectional):

S-A: 2, S-B: 3
A-C: 2, A-D: 4
B-D: 1, B-E: 3
C-G: 4, D-G: 3, E-G: 2
Heuristics to G:
h(S)=7, h(A)=6, h(B)=5, h(C)=4, h(D)=3, h(E)=2, h(G)=0
Solution:

A Execution Table:*

Iter Expand g h f Successors Added

1 S 0 7 7 A(g=2,f=8), B(g=3,f=8)
2 A 2 6 8 C(g=4,f=8), D(g=6,f=9)
3 B 3 5 8 D(g=4,f=7)*, E(g=6,f=8)
4 D 4 3 7 G(g=7,f=7)
5 G 7 0 7 GOAL!

Note: D discovered via B with better cost (4 vs 6), so frontier updated

Optimal Path: S → B → D → G
Optimal Cost: 7

Nodes Expanded: 5 (S, A, B, D, G)

Nodes Generated: 7

Key Observations:

A* didn't explore C or E (heuristic guided away)

Node D was updated when better path found via B
First goal discovery was optimal (admissible heuristic
guarantee)
Verify Admissibility:

h(S)=7 ≤ h*(S)=7 ✓
h(A)=6 ≤ h*(A)=6 ✓
h(B)=5 ≤ h*(B)=5 ✓ (via D to G)
h(D)=3 ≤ h*(D)=3 ✓
All heuristics admissible!
Problem 3.2: Design heuristic for 15-puzzle and prove admissibility.

Solution:

15-Puzzle: 4×4 grid with 15 numbered tiles and one blank.

Heuristic 1: Manhattan Distance

Admissibility Proof:

Each tile must move at least its Manhattan distance to reach

goal position
Moving one tile by one step reduces Manhattan distance by at
most 1
Therefore, ✓

Heuristic 2: Linear Conflict + Manhattan Distance

Linear conflict: Two tiles and are in the same row/column, their
goal positions are also in that row/column, but they're reversed
relative to their goals.
Example:
Row: [2] [1] ...
Tiles 1 and 2 both belong in this row, but 2 is left of 1 (reversed). This
requires at least one extra move beyond Manhattan distance.
Admissibility Proof:
 Manhattan distance is admissible (base)
Each linear conflict requires ≥2 additional moves (one tile must
temporarily leave row/column)
Therefore, where k = conflicts ✓
Heuristic Comparison:

For typical 15-puzzle:

expands ~50,000 nodes on average
expands ~5,000 nodes on average
10× improvement from more informed heuristic!

Problem Set 4: Heuristic Analysis

Problem 4.1: Given two admissible heuristics and , prove that
is also admissible.
Solution:

Proof:

Given:
is admissible: for all
is admissible: for all

We want to prove:
Case 1: If , then ✓

Case 2: If , then ✓

In both cases, , therefore is admissible. Q.E.D.

Practical Significance: Taking the maximum of multiple admissible
heuristics gives a more informed heuristic that's still admissible. This
is useful for combining different perspectives on the problem.
Problem 4.2: Given two admissible heuristics and , is
admissible?
Solution:
Answer: Not necessarily! Counterexample:

Consider state with true cost .

Let:
(admissible: 9 ≤ 10)
(admissible: 8 ≤ 10)

But , so violates admissibility!

Exception: Sum is admissible if and measure costs for

completely independent subproblems.
Example: For 8-puzzle:

= Manhattan distance for tiles {1,2,3,4}

= Manhattan distance for tiles {5,6,7,8}
These are independent (moving one set doesn't affect other), so
is admissible.
Problem 4.3: Prove that consistency implies admissibility.

Complete Formal Proof:

Given: Heuristic is consistent:

for all nodes and successors , and for goal .

Prove: is admissible: for all .
Proof by induction on path length:

Base Case: For goal node :

So ✓

Inductive Hypothesis: Assume for node .

Inductive Step: Consider node with successor on optimal
path to goal.
By consistency:

By inductive hypothesis:

Therefore:

The last equality holds because

(optimal path cost).
By induction, for all nodes . Q.E.D.
Converse is false: Admissibility does NOT imply consistency.

Counterexample:

Graph: S → A → G
↓
B
With costs: S-A: 1, A-G: 1, S-B: 5
Define inconsistent but admissible heuristic:
h(S) = 2 (admissible: actual cost is 2)
h(A) = 5 (admissible: actual cost is 1, but 5 ≤ ∞ if we allow
overestimation for non-goal states... wait, this violates
admissibility!)
Actually, correct counterexample:
h(S) = 1.5
h(A) = 1
h(B) = 0
h(G) = 0
Check admissibility:
h(S) = 1.5 ≤ 2 = h*(S) ✓
h(A) = 1 ≤ 1 = h*(A) ✓
All admissible
Check consistency for S → A:
h(S) ≤ c(S,A) + h(A)?
1.5 ≤ 1 + 1 = 2 ✓
Check consistency for S → B:
h(S) ≤ c(S,B) + h(B)?
1.5 ≤ 5 + 0 = 5 ✓
Actually this is consistent too. Finding valid counterexample is tricky
—most admissible heuristics are consistent in practice[34][37][43].

Problem Set 5: Complete Search Problem

Problem 5.1: Romania Road Trip

You're planning a road trip from Arad to Bucharest. Apply A* search

using straight-line distance heuristic.
Map (distances in km):

Cities and road connections:

Arad-Zerind: 75, Arad-Sibiu: 140, Arad-Timisoara: 118
Zerind-Oradea: 71
Oradea-Sibiu: 151
Sibiu-Fagaras: 99, Sibiu-Rimnicu: 80
Timisoara-Lugoj: 111
Lugoj-Mehadia: 70
Mehadia-Drobeta: 75
Drobeta-Craiova: 120
Rimnicu-Craiova: 146, Rimnicu-Pitesti: 97
Craiova-Pitesti: 138
Fagaras-Bucharest: 211
Pitesti-Bucharest: 101
Straight-line distances to Bucharest (heuristic):
h(Arad)=366, h(Zerind)=374, h(Oradea)=380, h(Sibiu)=253,
h(Timisoara)=329, h(Lugoj)=244, h(Mehadia)=241, h(Drobeta)=242,
h(Craiova)=160, h(Rimnicu)=193, h(Fagaras)=178, h(Pitesti)=98,
h(Bucharest)=0
Complete A Solution:*
Iteration 1: Expand Arad (g=0, h=366, f=366)

Add: Zerind(g=75,h=374,f=449), Sibiu(g=140,h=253,f=393),

Timisoara(g=118,h=329,f=447)
Frontier: [Sibiu(393), Timisoara(447), Zerind(449)]
Iteration 2: Expand Sibiu (g=140, f=393)

Add: Arad(explored), Oradea(g=291,h=380,f=671),

Fagaras(g=239,h=178,f=417), Rimnicu(g=220,h=193,f=413)
Frontier: [Rimnicu(413), Fagaras(417), Timisoara(447),
Zerind(449), Oradea(671)]
Iteration 3: Expand Rimnicu (g=220, f=413)

Add: Sibiu(explored), Craiova(g=366,h=160,f=526),

Pitesti(g=317,h=98,f=415)
Frontier: [Pitesti(415), Fagaras(417), Timisoara(447),
Zerind(449), Craiova(526), Oradea(671)]
Iteration 4: Expand Pitesti (g=317, f=415)

Add: Bucharest(g=418,h=0,f=418), Craiova(g=455,h=160,f=615),

Rimnicu(explored)
Frontier: [Fagaras(417), Bucharest(418), Timisoara(447),
Zerind(449), Craiova(526), Craiova(615), Oradea(671)]
Iteration 5: Expand Fagaras (g=239, f=417)

Add: Sibiu(explored), Bucharest(g=450,h=0,f=450)

Frontier: [Bucharest(418), Bucharest(450), Timisoara(447), ...]
Iteration 6: Expand Bucharest (g=418, f=418) → GOAL FOUND!

Optimal Path: Arad → Sibiu → Rimnicu → Pitesti → Bucharest

Total Cost: 418 km

Performance:

Nodes expanded: 6
Optimal path found (proven by admissible heuristic)
Much better than uninformed search (would expand 20+ nodes)

Examination Tips and Practice

Important Topics for SPPU Exams
Based on typical SPPU examination patterns and previous year
analysis:
High Priority Topics (Expected Almost Every Year):

1. PEAS framework with examples (5-7 marks)

2. Environment types and characteristics classification (7-10
marks)
3. Rationality and agent types comparison (5-7 marks)
4. BFS and DFS algorithms with worked examples (8-10 marks)
5. A* algorithm with complete execution (10 marks)
6. Heuristic function design and admissibility proofs (7-10 marks)
7. Problem formulation for given scenarios (5-7 marks)
Medium Priority Topics:

8. AI history and development timeline (3-5 marks)

9. Agent architectures and structures (5-7 marks)
10. Uninformed search comparison (5-7 marks)
11. Informed vs uninformed search advantages (5 marks)
12. Local search algorithms (5-7 marks)
13. Heuristic generation from relaxed problems (5 marks)
Lower Priority (Occasional):

15. Detailed AI foundations from multiple disciplines (3-5 marks)

16. AI risks and benefits discussion (3-5 marks)
17. State-of-the-art AI capabilities (3-5 marks)
18. Memory-bounded search algorithms (3-5 marks)
Common Question Patterns with Mark Distribution:

Question Pattern Typical Marks

Define and explain intelligent agents with
7-10
types and examples
Compare informed vs uninformed search
5-7
with advantages/disadvantages
Apply BFS/DFS/A* to given graph problem
8-10
showing complete execution
Design PEAS framework for specific real-
5-7
world application
Classify environment properties with
7-10
justification and examples
Derive and prove admissibility of heuristic
7-10
functions
Formulate problem (states, actions, goal test,
5-7
path cost)
Trace algorithm execution showing frontier
8-10
and explored set
Compare agent architectures (reactive,
5-7
deliberative, hybrid)
Explain rationality with PEAS example 7

SPPU Previous Year Question Analysis

Common Combinations:

CO1 (Introduction) Questions:

Define AI agent with components (sensors, actuators, percepts,

actions)
PEAS specification for real-world system
Environment classification with justification
Agent types comparison table
Rationality concept with examples
CO2 (Problem-Solving) Questions:
 Apply uninformed search (BFS/DFS/IDDFS/UCS) on graph
Apply A* search with heuristic function
Design admissible heuristic for given problem
Compare search algorithms (completeness, optimality,
complexity)
Problem formulation for scenario
Local search algorithm explanation
Typical Full Question (10 marks):

"For the given graph, apply A* search algorithm to find optimal path
from node S to node G. Show the step-by-step expansion with g(n),
h(n), and f(n) values. Also verify whether the given heuristic is
admissible."
Answer Structure:

1. Define A* (1 mark)
2. Show evaluation function f(n) = g(n) + h(n) (1 mark)
3. Create table with iterations (5 marks)
4. State final path and cost (1 mark)
5. Verify admissibility for each node (2 marks)

Quick Revision Checklist

Day Before Exam - Must Know:

□ PEAS framework and 3-4 complete examples

□ All 6 environment properties with examples
□ 5 agent types with differences
□ BFS algorithm and properties
□ DFS algorithm and properties
□ A* algorithm and evaluation function
□ How to verify admissibility
□ How to verify consistency
□ Manhattan and Euclidean distance formulas
□ Problem formulation 5-component structure
□ Complexity notation: O(b^d), O(bd), etc.

Formulas to Memorize:
Exam Writing Tips
For Algorithm Questions:

1. Draw table with columns: Iteration | Node Expanded | g | h | f

| Successors Added
2. Show frontier state after each iteration
3. Mark explored nodes clearly
4. Reconstruct path from goal to start using parent pointers
5. State final cost and verify optimality
For PEAS Questions:

1. Create neat table with 4 rows (P, E, A, S)

2. Be specific - "temperature sensor" not just "sensors"
3. Include multiple items for each component (3-5 each)
4. Match performance to application - what defines success?
For Environment Classification:

1. Create 6×2 table (dimension | classification | justification)

2. Explain reasoning - don't just state classification
3. Give concrete examples from the specific environment
For Comparison Questions:

1. Use table format for clarity

2. Include all criteria: completeness, optimality, time, space
3. Give example showing key difference
4. State when each is preferred
Mock Exam Questions
Question 1 (10 marks):

Design a complete PEAS specification for an autonomous agricultural

drone used for crop health monitoring and precision pesticide
spraying. Also classify the environment along all six dimensions with
proper justification.
Expected Answer Structure:

PEAS table (4 marks)

Environment classification table (4 marks)
Justifications (2 marks)
Question 2 (10 marks):

Apply A* search algorithm on the following graph to find optimal

path from S to G. Show complete step-by-step execution. Given
heuristic values: h(S)=10, h(A)=8, h(B)=7, h(C)=4, h(D)=5, h(G)=0. Edge
costs: S-A:3, S-B:5, A-C:4, B-C:2, B-D:5, C-G:6, D-G:5. Verify if the
heuristic is admissible.
Expected Answer Structure:

A* execution table (5 marks)

Path and cost (2 marks)
Admissibility verification (3 marks)
Question 3 (10 marks):

Compare BFS, DFS, and A* search algorithms with respect to

completeness, optimality, time complexity, and space complexity. For
which type of problems is each most suitable? Explain with examples.
Expected Answer Structure:

Comparison table (4 marks)

Suitability discussion (3 marks)
Examples for each (3 marks)
Question 4 (10 marks):
For the 8-puzzle problem:
(a) Formulate the problem clearly stating states, initial state, actions,
transition model, goal test, and path cost (5 marks)
(b) Design two different admissible heuristics and prove their
admissibility (3 marks)
(c) Which heuristic would perform better and why? (2 marks)
Question 5 (7 marks):

Explain the concept of rationality in AI agents. What are the factors

that determine rational behavior? Design PEAS for a rational medical
diagnosis system.
Expected Answer Structure:

Rationality definition (2 marks)

Four factors (2 marks)
PEAS table (3 marks)

Time Management Strategy

For 3-Hour Exam (80 marks):

Read all questions: 10 minutes

Question selection: 5 minutes
Per 10-mark question: 20-22 minutes
Per 7-mark question: 14-16 minutes
Per 5-mark question: 10-12 minutes
Revision: 15-20 minutes
Question Priority:

1. Do easiest first - builds confidence, secures marks

2. Then do high-value questions - 10-mark questions
3. Save difficult for last - partial marks better than none
4. Leave time for diagrams - neat diagrams earn marks
Common Mistakes to Avoid
❌ Algorithm execution without table - Hard to follow, marks
deducted
❌ No justification for classifications - Just stating isn't enough
❌ Incomplete PEAS - Missing sensors/actuators loses marks
❌ Wrong complexity notation - Confusing b, d, m parameters
❌ No path reconstruction - Must show final path clearly
❌ Forgetting to verify admissibility - When question asks for it
❌ Poor handwriting in tables - Make tables neat and readable
❌ No examples when asked - "With example" means provide one!
❌ Mixing up g(n) and h(n) - Clearly label each value
❌ Not showing work for proofs - Step-by-step is crucial

Summary Quick Reference Cards

Card 1: Agent Types at a Glance
Type Key Feature Best For
Current percept only Fully
Simple Reflex
observable envs
Internal state Partially
Model-Based
tracking observable envs
Explicit goal Flexible goal
Goal-Based
information changes
Maximize utility Trade-off
Utility-Based
function decisions
Improve with Unknown
Learning
experience environments

Card 2: Search Algorithm Quick Comparison

 Algorithm Complete Optimal Time Space
BFS ✓ ✓*
DFS ✗ ✗
IDDFS ✓ ✓*
UCS ✓ ✓
A* ✓ ✓**
IDA* ✓ ✓**
*If step costs equal, **If heuristic admissible

Card 3: Essential Formulas

A Evaluation:*

Distance Heuristics:

Heuristic Properties:

Complexity Parameters:

= branching factor
= solution depth
= maximum depth
= optimal cost
= minimum cost
Card 4: Environment Property Checklist
For any environment, ask:
1. Observable? Can agent see complete state?
2. Deterministic? Is next state completely determined?
3. Episodic? Are decisions independent?
4. Static? Does environment change during deliberation?
5. Discrete? Finite states and actions?
6. Agents? Single agent or multiple?

Card 5: Problem Formulation Template

1. States: What configurations are possible?
2. Initial State: Where do we start?
3. Actions: ACTIONS(s) returns available actions
4. Transition Model: RESULT(s,a) returns new state
5. Goal Test: How to recognize goal?
6. Path Cost: How to measure solution quality?

Glossary of Key Terms

Admissible Heuristic: Heuristic that never overestimates true cost
to goal ( )
Agent: Autonomous entity that perceives environment and acts to
achieve goals
Agent Function: Mathematical mapping from percept sequences to
actions
Branching Factor (b): Average number of successors per node

Completeness: Property of algorithm guaranteed to find solution if

one exists
Consistent Heuristic: Heuristic satisfying
(triangle inequality)
Deliberative Agent: Agent that maintains world model and plans
actions
Effective Branching Factor: Empirical measure of heuristic quality

Evaluation Function f(n): Function assigning priority to nodes (in

A*: )
Frontier: Set of nodes available for expansion (open list)

Heuristic Function h(n): Estimated cost from node to goal

Informed Search: Search using domain-specific knowledge

(heuristics)
Optimality: Property of algorithm guaranteed to find best solution

PEAS: Framework describing agent: Performance, Environment,

Actuators, Sensors
Rational Agent: Agent that acts to maximize expected performance
measure
Reactive Agent: Agent that directly maps percepts to actions without
internal state
State Space: Set of all states reachable from initial state

Uninformed Search: Search without domain-specific knowledge

(blind search)
Utility-Based Agent: Agent that maximizes utility function
measuring state desirability

References
[1] Applied AI Course. (2025). "Agents and Environment in Artificial
Intelligence." Retrieved from [Link]
[2] GeeksforGeeks. (2024). "Intelligent Agent in AI." Retrieved from
[Link]
[3] GeeksforGeeks. (2026). "Informed vs Uninformed Search in AI."
Retrieved from [Link]
[4] SPPU. (2025). "Artificial Intelligence Course Syllabus - Computer
Engineering." Savitribai Phule Pune University
[5] Smythos Developers. (2026). "Exploring AI Agent Environments:
How They Shape Agent Behavior." Retrieved from [Link]
[6] upGrad Blog. (2025). "Difference between Informed and
Uninformed Search." Retrieved from [Link]
[7] Army Institute of Technology. (2021). "Third Year Computer
Engineering Curriculum." Retrieved from [Link]
[8] Toloka AI. (2026). "AI Agent Environments - The Proving Ground
for Artificial Intelligence." Retrieved from [Link]
[9] Baeldung. (2024). "The Informed vs. Uninformed Search
Algorithms." Retrieved from [Link]
[10] College Communication Gateway. (2024). "[Link]. Artificial
Intelligence and Machine Learning Syllabus." Savitribai Phule Pune
University
[11] Hello Tars Blog. (2025). "Understanding AI Agents and
Environments - A Comprehensive Guide." Retrieved from
[Link]
[12] AlgoScale. (2025). "Comparing Blind Search vs Heuristic Search in
AI." Retrieved from [Link]
[13] Army Institute of Technology. (2021). "Theory of Computation
Course Objectives." Retrieved from [Link]
[14] GeeksforGeeks. (2018). "Agents in AI." Retrieved from
[Link]
[15] GeeksforGeeks. (2024). "Uninformed Search Algorithms in AI."
Retrieved from [Link]
[16] Tpoint Tech. (2025). "BFS and DFS Examples in Artificial
Intelligence." Retrieved from [Link]
[17] DataCamp. (2024). "The A* Algorithm: A Complete Guide."
Retrieved from [Link]
[18] Think201. (2025). "Rational Agent in AI: Types, Importance, and
Future Trends." Retrieved from [Link]
[19] GeeksforGeeks. (2024). "Depth First Search (DFS) for Artificial
Intelligence." Retrieved from [Link]
[20] GeeksforGeeks. (2024). "A* Algorithm and Its Heuristic Search
Strategy in Artificial Intelligence." Retrieved from [Link]
[21] Portland State University. "Intelligent Agents Lecture Notes."
Retrieved from [Link]
[22] GeeksforGeeks. (2024). "Breadth First Search (BFS) for Artificial
Intelligence." Retrieved from [Link]
[23] Stack Overflow. (2012). "Heuristic Function for Finding the Path
Using A Star." Retrieved from [Link]
[24] GeeksforGeeks. (2024). "Intelligent Agent in AI - Rational Agents
and Rationality." Retrieved from [Link]
[25] Pickl AI. (2024). "Depth First Search (DFS) Algorithm in Artificial
Intelligence." Retrieved from [Link]
[26] YouTube - Mahesh Huddar. (2024). "A Star Search Algorithm
Solved Example." Retrieved from [Link]
[27] GeeksforGeeks. (2020). "Understanding PEAS in Artificial
Intelligence." Retrieved from [Link]
[28] YouTube - Gate Smashers. (2019). "Depth First Search (DFS) with
Example." Retrieved from [Link]
[29] Stanford Theory. (2017). "Heuristics in Pathfinding." Retrieved
from [Link]
[30] YouTube - Mahesh Huddar. (2024). "Concept of Rationality
Rational Agent Irrational Agent." Retrieved from [Link]
[31] Galileo AI. (2025). "7 Types of AI Agent Architecture." Retrieved
from [Link]
[32] Galileo AI. (2025). "AI Agent Architecture Components and
Patterns." Retrieved from [Link]/blog/ai-agent-architecture
[33] GeeksforGeeks. (2019). "Time and Space Complexity Analysis of
Binary Search Algorithm." Retrieved from [Link]
[34] Carnegie Mellon University. (2019). "Designing & Understanding
Heuristics - Recitation Solutions." Retrieved from [Link]
[35] Hatchworks. (2025). "Understanding Agent Architecture: The
Frameworks Powering AI." Retrieved from [Link]/blog/ai-a
gents/agent-architecture
[36] Wikipedia. (2002). "A* Search Algorithm - Complexity Analysis."
Retrieved from [Link]
[37] Stack Overflow. (2020). "Proof of Consistent Heuristic Implies
Admissible Condition." Retrieved from [Link]
[38] Red Hat. (2025). "Understanding AI Agent Types: A Guide to
Categorizing Complexity." Retrieved from [Link]
[39] Computer Science Cafe. "Search Algorithms: Properties,
Complexity, and Implementation." Retrieved from
[Link]
[40] University of Illinois. (2020). "Admissible, Consistent, Zero,
Relaxed, Dominant Heuristics." Retrieved from
[Link]
[41] Smythos Developers. (2026). "Types of Agent Architectures."
Retrieved from [Link]/developers/agent-development
[42] Big-O Cheat Sheet. "Algorithm Complexity Reference." Retrieved
from [Link]
[43] R. Niwa. (2009). "Proof: Every Consistent Heuristic is Also
Admissible." Retrieved from [Link]
[44] IBM Think. (2025). "Types of AI Agents." Retrieved from
[Link]/think/topics/ai-agent-types
[45] WS Cube Tech. (2026). "Searching Algorithms in Data Structure."
Retrieved from [Link]
[46] Wikipedia. (2007). "Consistent Heuristic." Retrieved from
[Link]

End of Document

This comprehensive study resource covers Units I and II of the SPPU

Third Year Computer Engineering Artificial Intelligence course. For best
results, work through examples systematically, practice algorithm
execution by hand, and attempt all problem sets before exams.
Total Pages: 50+
Total Practice Problems: 30+
Total Worked Examples: 50+
Total References: 46

Good luck with your studies!