Tab 1

Unit 4. Problem Solving and Search

Syllabus
Problem Solving Agents, Problem formulation, state space, and search strategies, Uninformed
Search Strategies, Informed Search Strategies.

Sr. No. Name Page No

Chapter 4 : Problem Solving and Search

4.1 Problem Solving Agents,

4.2 Problem formulation

4.3 state space

4.4 search strategies

4.5 Uninformed Search Strategies

4.6 informed Search Strategies

4.1 Problem Solving Agents/Problem Solving in AI
Problem solving is a core aspect of artificial intelligence (AI) that mimics human cognitive
processes. It involves identifying challenges, analyzing situations, and applying strategies to find
effective solutions.
Types of Problems in AI
1. Ignorable Problems
2. Recoverable Problems
3. Irrecoverable Problems
1.Ignorable Problems
Description: These are problems or errors that have minimal or no impact on the overall
performance of the AI system. They are minor and can be safely ignored without significantly
affecting the outcome.
Examples:
●​ Slight inaccuracies in predictions that do not affect the larger goal (e.g., small
variance in image pixel values during image classification).
●​ Minor data preprocessing errors that don’t alter the results significantly.
Handling: These problems often don’t require intervention and can be overlooked in real-time
systems without adverse effects.
2. Recoverable Problems
Description:Recoverable problems are those where the AI system encounters an issue, but it can
recover from the error, either through manual intervention or built-in mechanisms, such as
error-handling functions.
Examples:
●​ Missing data that can be imputed or filled in by statistical methods.
●​ Incorrect or biased training data that can be retrained or corrected during the process.
●​ System crashes that can be recovered through checkpoints or retraining.
Handling: These problems require some action—either automated or manual recovery. Systems
can be designed with fault tolerance or error-correcting mechanisms to handle these.
3.Irrecoverable Problems
Description: These are critical problems that lead to permanent failure or incorrect outcomes in
AI systems. Once encountered, the system cannot recover, and these problems can cause
significant damage or misperformance.
Examples:
Complete corruption of the training dataset leading to irreversible bias or poor performance.
Security vulnerabilities in AI models that allow for adversarial attacks, rendering the system
untrustworthy.
Overfitting to the extent that the model cannot generalize to new data.
Handling: These problems often require a complete overhaul or redesign of the system,
including retraining the model, rebuilding the dataset, or addressing fundamental issues in the AI
architecture.
Steps in Problem Solving in Artificial Intelligence (AI)
The process of problem solving in AI consists of several finite steps that parallel human
cognitive processes. These steps include:
Problem Definition: This initial step involves clearly specifying the inputs and acceptable
solutions for the system. A well-defined problem lays the groundwork for effective analysis and
resolution.
Problem Analysis: In this step, the problem is thoroughly examined to understand its
components, constraints, and implications. This analysis is crucial for identifying viable
solutions.
Knowledge Representation: This involves gathering detailed information about the problem
and defining all potential techniques that can be applied. Knowledge representation is essential
for understanding the problem’s context and available resources.
Problem Solving: The selection of the best techniques to address the problem is made in this
step. It often involves comparing various algorithms and approaches to determine the most
effective method.
4.2 Problem Formulation
In artificial intelligence (AI) and machine learning, an agent is an entity that perceives its
environment, processes information and acts upon that environment to achieve specific goals.
The process by which an agent formulates a problem is critical,
as it lays the foundation for the agent's decision-making and problem-solving capabilities.
Steps in Problem Formulation:
Step 1: Define the Initial State: The initial state is the starting point of the agent. It includes all
the relevant information about the environment that the agent can perceive and use to begin the
problem-solving process.
Example: In a navigation problem, the initial state could be the agent's starting location on a
map.
Step 2: Specify the Goal State: The goal state defines the desired outcome that the agent aims
to achieve. It represents the condition or set of conditions that signify the completion of the task.
Example: For the navigation problem, the goal state is the destination location
Step 3: Determine the Actions: Actions are the set of operations or moves that the agent can
perform to transition from one state to another. Each action should be well-defined and feasible
within the given environment.
Example: In a robot navigation scenario, actions could include moving forward, turning left, or
turning right.
Step 4: Establish the Transition Model: The transition model describes how the environment
changes in response to the agent's actions. It defines the rules that govern state transitions.
Example: In a game, the transition model would include the rules that specify how the game state
changes based on the player's moves.
Step 5: Set Constraints and Conditions: Constraints are the limitations or restrictions within
which the agent must operate. These can include physical limitations, resource constraints, and
safety requirements.
Example: For a delivery drone, constraints might include battery life, weight capacity, and no-fly
zones.
Step 6: Define the Cost Function (if applicable): The cost function evaluates the cost
associated with different actions or paths. It helps the agent to optimize its strategy by
minimizing or maximizing this cost.
Example: In route planning, the cost function could represent the distance traveled, time taken,
or energy consumed.
Step 7: Criteria for Success: The criteria for success determine how the agent evaluates its
progress and final solution. This includes metrics for measuring the effectiveness and efficiency
of the solution.
Example: For a puzzle-solving agent, success criteria could be the completion of the puzzle
within the shortest time or the fewest moves.
Importance of Problem Formulation
Effective problem formulation is essential because:
Clarity: It provides a clear understanding of the problem, making it easier to devise a solution.
Efficiency: Proper formulation can significantly reduce the computational resources required to
solve the problem.
Optimal Solutions: It helps in finding the most optimal or satisfactory solution by accurately
defining the goals and constraints.
4.3 State Spaces
One general formulation of intelligent action is in terms of a state space.A state contains all of
the information necessary to predict the effects of an action
determine whether a state satisfies the goal
State Spaces searching assumes:
The agent has perfect knowledge of the state space.
• At any time, it knows what state it is in; the world is thus fully observable
• The agent has a set of actions with known deterministic effects .
• The agent has a goal to achieve and can determine whether a state satisfies the goal.
In AI, a state space represents all possible configurations or states of a problem, and a classic
example is the 8-puzzle, where the goal is to rearrange tiles in a 3x3 grid from an initial state to a
final state by sliding them into a blank space.
What is a state space?
In AI, a state space encompasses all possible configurations or states of a problem or system that
an AI agent can be in.
8-Puzzle Example:
Problem: The 8-puzzle is a sliding puzzle game where you have 8 numbered tiles and one blank
space arranged in a 3x3 grid.
Goal: Rearrange the tiles from their initial state to a specific final state by sliding them into the
blank space.
State: Each arrangement of the tiles (including the blank space) represents a state in the state
space.
State Space: The collection of all possible tile arrangements forms the state space.
4.4 Searching strategies
Searching is a process to find the solution for a given set of problems.
This in artificial intelligence can be done by using either uninformed searching strategies of
either informed searching strategies
Types of searching strategies-
●​ Uninformed Search Strategy
●​ Informed Search Strategy

Importance of searching strategies

Efficient Problem Solving: Search strategies help AI systems explore large problem spaces
systematically, ensuring solutions are found quickly without having to check every possibility.​
Optimization: Effective search strategies, like A* or greedy algorithms, help ensure that the AI
finds the best or near-best solutions while minimizing computation time and resources.
Handling Large and Complex Problem Spaces: AI problems often involve complex
environments with numerous possible states. Search strategies make it possible to manage and
explore these vast spaces efficiently.​

Adaptability in Dynamic and Uncertain Environments: In real-world applications, the

environment is often uncertain or dynamic. Search strategies enable AI to adapt, making
decisions in uncertain conditions, such as in robotics or autonomous systems.
Scalability and Real-time Decision Making: Search strategies are crucial for scaling AI
systems and enabling them to make fast, real-time decisions, which is important in domains like
gaming, navigation, and autonomous vehicles.
Differentiate between Informed and Uninformed Search

Parameters Informed Search Uninformed Search

Utilizing It uses knowledge during It does not require using any

Knowledge the process of searching. knowledge during the process of
searching.

Speed Finding the solution is Finding the solution is much slower

quicker. comparatively.

Completion It can be both complete It is always bound to be complete.

and incomplete.

Consumption of Due to a quicker search, Due to slow searches, it consumes

Time it consumes much less comparatively more time.
time.

Cost Incurred The expenses are much The expenses are comparatively
lower. higher.

Suggestion/ The AI gets suggestions The AI does not get any suggestions
Direction regarding how and where regarding what solution to find and
to find a solution to any where to find it. Whatever knowledge
problem. it gets is out of the information
provided.
Efficiency It costs less and generates It costs more and generates slower
quicker results. Thus, it is results. Thus, it is comparatively less
comparatively more efficient.
efficient.

Length of Implementation is shorter The implementation is lengthier using

Implementation using AI. AI.

Examples A few examples include A few examples include Breadth-First

Graph Search and Greedy Search or BFS and Depth-First Search
Search. or DFS.

Figure. Types of Search Algorithm

4.5 Uninformed Search

●​ Breadth First Search
●​ Depth First Search
 ●​ Uniform Cost Search (UCS)

Informed search algorithms are a class of algorithms in artificial intelligence that use heuristic
functions to guide the search process. A heuristic is a function that estimates the cost of reaching
the goal from a given node, providing additional information that helps the algorithm make
smarter decisions.
Breadth First Search
In Breadth First Search(BFS), the root node of the graph is expanded first
then all the successor nodes are expanded and then their successor and so on i.e. the nodes are
expanded level wise starting at root level.

Figure. Breadth First Search

Originally it starts at the root node, then it expands all of its successors, it systematically explores
all its neighbouring nodes before moving to the next level of node It starts from the root node A
then expands its successors B
This process of extending the root node’s immediate neighbours, then to their neighbours, and so
on, lasts until all the nodes within the graph have been visited or until the specific condition is
met.
after visiting the node B it moves to node C. when the level 1 is completed, it further moves to
the next level i.e 2 and explore node D. it will move systematically to node E, node F and node
G. After visiting the node G it will terminate.
Key characteristics Breadth First Search
First-in-First-Out (FIFO): The FIFO queue is typically preferred in BFS because the FIFO
queue will be faster than a priority queue and often results in the correct order of nodes. When
FIFO is applied to BFS, new nodes deeper in the search tree are added to the back of the queue.
The old nodes which are shallowest than the new nodes get expanded first.
Early goal test: In traditional BFS implementations, the algorithm maintains a set of states
reached during the search process. However, instead of storing all reached states, it selectively
stores only the set of reached states that allow for an early goal test. This test involves checking
whether the newly generated node meets the goal criteria as soon as it is generated.
Cost-optimal: BFS always aims to find a solution with a minimum cost prioritizing the shortest
path, when BFS generates nodes at a certain depth d, it has already explored and generated all
the nodes at the previous depth d-1. Consequently, if a solution exists within a search space, BFS
can discover it as soon as it reaches that depth level. Therefore, BFS is said to be a cost-optimal
solution
Applications of BFS in AI
Pathfinding Algorithms
Breadth-First Search (BFS) is widely used for finding the shortest path in unweighted graphs. It
systematically explores nodes level by level, ensuring the shortest route to the destination is
identified.
Example: In maze-solving or robot navigation tasks, BFS is used to traverse possible paths and
determine the shortest exit. Google Maps also employs BFS-like algorithms for route
optimization in cases of unweighted graphs.
Web Crawling
BFS plays a crucial role in web crawling, where websites are explored level by level to collect
data systematically. Starting from a root URL, BFS ensures that all links on the same page (same
depth) are visited before moving to deeper levels of linked pages. This technique is efficient for
building search engine indexes or gathering structured web data.
Social Network Analysis
In social networks like Facebook or LinkedIn, BFS is used to find connections between users or
measure degrees of separation. For instance, BFS helps determine mutual friends, the shortest
path between two individuals, or influencers within a network. It enables understanding and
visualization of complex social relationships.

Depth First Search

Depth-first search is a traversing algorithm used in tree and graph-like data structures. It
generally starts by exploring the deepest node in the frontier. Starting at the root node, the
algorithm proceeds to search to the deepest level of the search tree until nodes with no successors
are reached. Suppose the node with unexpanded successors is encountered then the search
backtracks to the next deepest node to explore alternative paths.
 Example. Depth First Search

it starts at the root node, then it expands all of its one branch until it reaches a dead end, then
backtracks to the most recent unexplored node, repeating until all nodes are visited or a specific
condition is met.
Starting from node A, DFS explores its successor B, then proceeds to its descendants until
reaching a dead end at node D. It then backtracks to node B and explores its remaining
successors i.e E.
This systematic exploration continues until all nodes are visited or the search terminates
after exploring all the nodes of B. DFS explores the right side node i.e C then F and and then G.
After exploring the node G. All the nodes are visited. It will terminate.
Key characteristics of Depth First Search
DFS is not cost-optimal since it doesn't guarantee to find the shortest paths.
DFS uses the simple principle to keep track of visited nodes: It uses a stack to keep track of
nodes that have been visited so far which helps in the backtracking of the graph. When the DFS
encounters a new node, it adds it to the stack to explore its neighbours. If it reaches a node with
no successors (leaf node), it works by backtracking such as popping nodes off the stack to
explore the alternative paths.

Backtracking search: The variant of DFS is called backtracking search which uses less memory
than traditional depth-first search. Rather than generating all the successors, the backtracking
search enables the DFS to generate only one successor at a time. This approach allows dynamic
state modification, such as generating successors by directly modifying the current state
description instead of allocating the memory to a brand-new state. Thus reducing the memory
requirements to store one state description and path of actions.
Applications of DFS in AI
Maze generation:
The Maze generation consists of designing a layout of passages and walls within a maze. This
maze generation makes use of a randomized approach of the Depth-first search algorithm
because it leverages the recursive method and stack. For instance, assume that the space is a
large grid of cells where each cell holds the four walls. The DFS performs by selecting any
random neighbor at first that has not been visited. It removes the wall between the two cells that
are not connected and then it adds the new cell to the stack. This process continues until no more
solution can be generated, resulting in a complete maze.
Puzzle-solving:
Puzzle-solving including Japanese nonograms can employ Depth-first search as a method for
systematically exploring possible solutions. In Japanese nonograms, DFS is utilized to explore
different combinations of filled and empty cells in the grid.
Pathfinding in robotics: ​
DFS can be employed for pathfinding in robotics, especially in scenarios where simplicity,
memory efficiency, and adaptability are important considerations.
Uniform Cost Search (UCS)
Uniform Cost Search is a pathfinding algorithm that expands the least cost node first, ensuring
that the path to the goal node has the minimum cost.
Unlike other search algorithms like Breadth-First Search (BFS), UCS takes into account the cost
of each path, making it suitable for weighted graphs where each edge has a different cost.
step-by-step process of how UCS works:
Initialization: UCS starts with the root node. It is added to the priority queue with a cumulative
cost of zero since no steps have been taken yet.
Node Expansion: The node with the lowest path cost is removed from the priority queue. This
node is then expanded, and its neighbors are explored.
Exploring Neighbors: For each neighbor of the expanded node, the algorithm calculates the
total cost from the start node to the neighbor through the current node. If a neighbor node is not
in the priority queue, it is added to the queue with the calculated cost. If the neighbor is already
in the queue but a lower cost path to this neighbor is found, the cost is updated in the queue.
Goal Check: After expanding a node, the algorithm checks if it has reached the goal node. If the
goal is reached, the algorithm returns the total cost to reach this node and the path taken.
Repetition: This process repeats until the priority queue is empty or the goal is reached
Example:
Application of Uniform Cost Search
Pathfinding in Maps: Determining the shortest route between two locations on a map,
considering different costs for different paths.
Network Routing: Finding the least-cost route in a communication or data network.
Puzzle Solving: Solving puzzles where each move has a cost associated with it, such as the
sliding tiles puzzle.
Resource Allocation: Tasks that involve distributing resources efficiently, where costs are
associated with different allocation strategies.
4.6 Informed search strategies
●​ Greedy Best-First Search
●​ A* Search Algorithm
Greedy Best-First Search
Greedy Best-First Search works by evaluating the cost of each possible path and then expanding
the path with the lowest cost. This process is repeated until the goal is reached.
The algorithm uses a heuristic function to determine which path is the most promising.
The heuristic function takes into account the cost of the current path and the estimated cost of the
remaining paths.
If the cost of the current path is lower than the estimated cost of the remaining paths, then the
current path is chosen. This process is repeated until the goal is reached.
Example:
Application of Greedy Best First Search
Robot Navigation: Helps autonomous robots in exploring environments by guiding them
through the closest possible route to a goal.

Artificial Intelligence Planning: GBFS is used in problem-solving scenarios where multiple

solutions exist, and an efficient path is required to achieve the goal.

A* Search Algorithm
Consider a square grid having many obstacles and we are given a starting cell and a target
cell. Wewant to reach the target cell (if possible) from the starting cell as quickly as
 possible.
What A* Search Algorithm does is that at each step it picks the node according to a
value-‘f’ which is a parameter equal to the sum of two other parameters – ‘g’ and ‘h’. At
each step it picks the node/cell having the lowest ‘f’, and process that node/cell.

g = the movement cost to move from the starting point to a given square on the grid,
following the path generated to get there.

h = the estimated movement cost to move from that given square on the grid to the final
destination.
f(n)=g(n)+h(n)

Example of A* Search Algorithm

Consider Heuristic values:
Home 120
Bank 80
Garden 100
School 70
Railway Station 20
Post Office 110
Police station 26
Application of A* search
Pathfinding in Navigation Systems: Used to calculate the shortest route from a point A to point
B on a map.
Game Playing: Helps in determining the best moves in games like chess or Go by evaluating the
most promising moves first.
Robotics: Utilized in autonomous navigation where a robot must find the best path through an
environment.
Problem Solving in AI: Applied to a range of problems from scheduling and planning to
resource allocation and logistics.
Problems on A*:

1.​ Identify the shortest path from Start State (S) to Goal State (D) using A*
algorithm. Heuristic function values are given for each node.

Given:

●​ Start State = S, Goal State = D.

●​ Heuristic values h(n) are provided for each node.
●​ Edge costs are provided on the graph.​

A* uses f(n) = g(n) + h(n),​

where:

●​ g(n) = actual cost to reach node n from the start node

●​ h(n) = heuristic estimate from node n to the goal

Step-by-Step Solution:

Step 1: Start at S

●​ f(n)=g(n)+h(n)=0+7=7

Expand S → Children: A and B.

Step 2: Calculate f(n) for Children (A and B)

For A:

S -> A

●​ f(n)=g(n)+h(n)=1+6=7

For B:

S -> B

●​ f(n)=g(n)+h(n)=4+2=6

Step 3: Choose Node with Lowest f(n)

●​ Compare: A & B node f(n) → Expand B next (lower f value).

Expand B → Child: C.

Step 4: Expand B and Calculate for C

For C:

S -> B -> C

●​ f(n)=g(n)+h(n)=6+1=7

Step 5: Choose Node with Lowest f(n)

Now, nodes available:

●​ Node A: S -> A (f = 7)
●​ Node C: S -> B -> C(f = 7)

Both have the same f(n), but we can pick A

Expand A → Children: B , C and D.

For B:
S -> A -> B
f(n)=g(n)+h(n)=3 +2 =5
For C:
S -> A -> C
f(n)=g(n)+h(n)=6+1=7
For D:
S -> A -> D
f(n)=g(n)+h(n)=13+0=13

Step 6: Choose Node with Lowest f(n)

S -> A -> B (f = 5)
S -> B -> C(f = 7)
S -> A -> C(f = 7)
S -> A -> D(f = 13)
f=5 is lowest So Expand B

Step 7: Expand B from A and Calculate C

For C:
S -> A -> B -> C
f(n)=g(n)+h(n)=5+1=6

Step 8: Choose Node with Lowest f(n)

S -> A -> B -> C(f = 6)
S -> B -> C(f = 7)
S -> A -> C(f = 7)
S -> A -> D(f = 13)
f=6 is lowest So Expand C

Step 9: Expand D from S -> A -> B -> C and calculate f(n)

For D:
S -> A -> B -> C -> D
f(n)=g(n)+h(n)=8+0=8

Step 10: Choose Node with Lowest f(n)

S -> B -> C(f = 7)
S -> A -> C(f = 7)
S -> A -> D(f = 13)
S -> A -> B -> C -> D(f = 8)
Do sorting and choose node with lowest f(n)
Step 11: Expand D from S -> B -> C and calculate f(n)
For D:
S -> B -> C -> D
f(n)=g(n)+h(n)=9+0=9

Step 12: Choose Node with Lowest f(n)

S -> A -> C(f = 7)
S -> A -> D(f = 13)
S -> A -> B -> C -> D(f = 8)
S -> B -> C -> D(f = 9)
Do sorting and choose node with lowest f(n)

Step 13: Expand D from S -> A -> C and calculate f(n)

For D:
S -> A -> C -> D
f(n)=g(n)+h(n)=9+0=9

Step 14: Choose Node with Lowest f(n)

S -> A -> D(f = 13)
S -> A -> B -> C -> D(f = 8)
S -> B -> C -> D(f = 9)
S -> A -> C -> D(f = 9)

In This step Goal D is reached by different paths.

But final optimal path from start start S to Goal state D with lowest f(n) is
S -> A -> B -> C -> D (f = 8)
2.Identify the shortest path from Start State (Home) to Goal State (University) using A*
algorithm. Heuristic function values are given for each node.
Step 5 shows the final least cost path from Home to University.

Home -> Bank -> Police -> University.

 Unit 4

No Questions Marks
1 List types of informed search and Uninformed search . 2
2 Define State space search and list its types. 2
3 Describe Ignorable problem in AI 2
4 Describe recoverable problem in AI 2
5 Describe irrecoverable problem in AI 2
Give Examples of recoverable and irrecoverable(2 Examples
6 each) 2
Differentiate between Informed and Uninformed Search(any
7 four) 2
8 What is Heuristic function? 2

1 Explain the PEAS property 4

2 Explain different search strategies 4
3 Explain A* algorithm 4
4 Explain Steps of Problem Formulation with examples. 4
5 Explain components of Problem Formulation with examples. 4
List and explain the different types of problems in Artificial
6 Intelligence. 4

Describe informed search .Explain any one type of informed

1 search. 6
Describe Uninformed search .Explain any one type of
2 Uninformed search. 6
3 Explain Breadth First Search with suitable example 6
4 Explain Depth First Search with an example. 6
5 Explain Best-First Search ?Explain with examples. 6
 Identify the shortest path from Start State (S) to Goal State
(D) using A* algorithm. Heuristic function values are given
for each node.

6 6

Solve for BFS using Queue Start State is A & Goal State is
N

7 6

Identify the shortest path from Start State (Home) to Goal

State (University) using A* algorithm. Heuristic function
values are given for each node.

8 6
 Solve for DFS using Stack for preorder traversal

9 6