CHAPTER - 2

Problem solving:
In Artificial Intelligence (AI), the term problem solving is given to the analysis of how computers
can be made to find solutions in well-circumscribed domains.
Problem solving is defined as the way in which an agent finds a sequence of actions that achieves
its goals, when no single action will do.
PROBLEM SOLVING AGENTS
Problem Solving agents which is type of goal based agent. A problem-solving agent firstly
formulates a goal and a problem to solve. Then the agent calls a search procedure to solve it. It
then uses the solution to guide its actions.
It will do whatever the solution recommends as the next thing to do and then remove that step from
the sequence. Once the solution has been executed, the agent will formulate a new goal. Searching
techniques like uninformed and informed or heuristic used in many areas like theorem proving,
game playing, expert systems, natural language processing etc.
Structure of problem solving agent:
Goal state: A state that describes the objective that the agent is trying to achieve is called
as the goal state of the agent.
Action: When there is a transition between the world states an action is said to be performed

Steps in problem solving by problem solving agent

The problem of AI is directly associated with the nature of humans and their activities. So we need
a number of finite steps to solve a problem which makes human easy works.
1. Goal formulation: This one is the first and simple step in problem-solving. It organizes
finite steps to formulate target/goals which require some action to achieve the goal. Today
the formulation of the goal is based on AI agents.
2. Problem formulation: It is one of the core steps of problem-solving which decides what
action and states should be taken to achieve the formulated goal. In AI this core part is
dependent upon software agent which consisted of the following components to formulate
the associated problem.
3. Choosing the best sequence: After Goal formulation and problem formulation, the agent
has to look for a sequence of actions that reaches the goal. This process is called Search. A
search algorithm takes a problem as input and returns a sequence of actions as output. An

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 1

 CHAPTER - 2

agent with several immediate options of unknown value can decidewhat to do by first
examining different possible sequences of actions that lead to the states of known value
and then choosing the best sequence.

In Artificial Intelligence, Search techniques are universal problem-solving methods. Rational

agents or Problem-solving agents in AI mostly used these search strategies or algorithms to solve
a specific problem and provide the best result. Problem-solving agents are the goal-based agents
and use atomic representation. In this topic, we will learn various problem-solving search
algorithms.
Problems and Solutions
Before we get into more about problem formulating phase, we need to first understand what a
problem is in terms of problem solving agents.
The problem can be defined formally in five components:
1. Initial State
2. Actions
3. Transition Model
4. Goal Test
5. Path Cost
1. Initial State
The first component that describes the problem is the initial state that AI agent towards a specified
goal. For example, For example, if a taxi agent needs to get to location(B) but the taxi is currently
at location(A) then the initial state of the problem would be location(A).
2. Actions
The second component that describes the problem is a description of the possible actions available
to the agent. Given a state ‘s’, Actions(s) returns the set of actions that can be executed in ‘s’. We
say that each of these actions is applicable in ‘s’.
3.Transition Model
The third component is the description of what each action does which is called the transition
model. It is specified by a function Result(s , a) that returns the state that results from doing action
‘a’ in state ‘s’.

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 2

 CHAPTER - 2

The initial state, actions and transition model together define the state space of a problem which is
a set of all states reachable from the initial state by any sequence of actions. The state space forms
a graph in which the nodes are states and the links between the nodes are actions.
4. Goal Test
The goal test determines whether a given state is a goal state or not. Sometimes there is an explicit
set of possible goal states and the test simply checks whether the given state is one of them.
Sometimes the goal is specified by an abstract property rather than an explicitly enumerated set of
states.
5. Path Cost
The last component of the problem is the path cost which is a function that assigns a numeric cost
to each path. The problem solving agent chooses a cost function that reflects its own performance
measure.
The solution to the problem is an action sequence that leads from initial state to goal state and the
solution quality is measured by the path cost function. An optimal solution has the lowest path cost
among all the solutions.
Example Problems: Toy Problems
An Example Problem Formulation: Let us take the example of vacuum world, there is a vacuum
cleaner agent and it can move left or right and its jump is to suck up the dirt from the floor.

State space for vacuum world.

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 3
 CHAPTER - 2

The problem for vacuum world can be formulated as follows:

States: The state is determined by both the agent location and the dirt location. The agent is in one
of two locations, each of which might or might not contain dirt.
Initial State:Our vacuum can be in any state of the 8 states shown in the figure. Any state can be
assigned as the initial state in this case.
Action: In this environment there are three actions, Move Left , Move Right , Suck up the dirt.
Transition Model: All the actions have expected effects, except for when the agent is in leftmost
square and the action is Left, when the agent is in rightmost square and the action is Right and the
square is clean when the action is to Suck.
Goal Test: Goal test checks whether all the squares are clean.
Path Cost: Each step costs 1, so the path cost is the number of steps in the path.
The second example we examine is 8 puzzle problems.
The 8-puzzle consists of eight numbered, movable tiles set in a 3x3 frame. Each tile has a number
on it. A tile that is adjacent to the blank space can slide into the space. A game consists of a starting
position and a specified goal position. The goal is to transform the starting position into the goal
position by sliding the tiles around.

An instance of 8-puzzle problem

This can be formulated as problem as follows:
1) States: Location of eight tiles and blank.
2) Initial state: Any state can be designed as the initial state.
3) Actions: Move blank left, right, up or down.
4) Goal test: This checks whether the states match the goal configuration.
5) Path cost: Each step cost is 1.
The third example is 8-Queen problem:

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 4

 CHAPTER - 2

The goal of the 8-queens problem is to place eight queens on a chessboard such that no queen
attacks any other. (A queen attacks any piece in the same row, column or diagonal.)
This can be formulated as problem as follows:
1) States: Any arrangement of 0 to 8 queens on the board is a state
2) Initial state: No queens on board.
3) Actions: Add a queen to any empty square.
4) Transition Model: Returns the board with a queen added to the specified square.
5) Goal Test: 8 queens are on the board, none attacked.

Searching for Solution:

A solution is an action sequence, so search algorithms work by considering various possible action
sequences. The possible action sequences starting at the initial state form a search tree with the
initial state at the root; the branches are actions and the nodes correspond to states in the state space
of the problem. A search problem where we aim not only at reaching our goal but also at doing so
at minimal cost is an optimisation problem.

UNINFORMED SEARCH:

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 5

 CHAPTER - 2

This topic covers several search strategies that come under the heading of uninformed search or
blind search. These search strategies use only the information available in the problem definition
1. Breadth First Search (BFS):
Breadth-first search is the most common search strategy for traversing a tree or graph. This
algorithm searches breadthwise in a tree or graph, so it is called breadth-first search.
BFS algorithm starts searching from the root node of the tree and expands all successor
node at the current level before moving to nodes of next level.
The breadth-first search algorithm is an example of a general-graph search algorithm.
Breadth-first search implemented using FIFO queue data structure.

In the above tree structure, we have shown the traversing of the tree using BFS algorithm from the
root node S to goal node K. BFS search algorithm traverse in layers, so it will follow the path
which is shown by the dotted arrow, and the traversed path will be:

1. S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K

Function BFS search

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 6

 CHAPTER - 2

Advantages:
BFS will provide a solution if any solution exists.
If there are more than one solutions for a given problem, then BFS will provide the minimal
solution which requires the least number of steps.
Disadvantages:

It requires lots of memory since each level of the tree must be saved into memory to expand
the next level.
BFS needs lots of time if the solution is far away from the root node.
Breadth First Search (BFS):
Time complexity: Equivalent to the number of nodes traversed in BFS until the shallowest
solution.
Space complexity: Equivalent to how large can the fringe get.
Completeness: BFS is complete, meaning for a given search tree, BFS will come up with
a solution if it exists.
Optimality: BFS is optimal as long as the costs of all edges are equal.

2. Depth-first Search

Depth-first search is a recursive algorithm for traversing a tree or graph data structure.
It is called the depth-first search because it starts from the root node and follows each path
to its greatest depth node before moving to the next path.
DFS uses a stack data structure for its implementation.
The process of the DFS algorithm is similar to the BFS algorithm

In the above search tree, we have shown the flow of depth-first search, and it will follow the order
as:
Root node--->Left node ----> right node.

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 7

 CHAPTER - 2

It will start searching from root node S, and traverse A, then B, then D and E, after traversing E, it
will backtrack the tree as E has no other successor and still goal node is not found. After
backtracking it will traverse node C and then G, and here it will terminate as it found goal node.

Function for DFS search

Advantage:

DFS requires very less memory as it only needs to store a stack of the nodes on the path
from root node to the current node.
It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right
pa

Disadvantages:

There is the possibility that many states keep re-occurring, and there is no guarantee of
finding the solution.
DFS algorithm goes for deep down searching and sometime it may go to the infinite loop.

3. Depth-Limited Search
A depth-limited search algorithm is similar to depth-first search with a predetermined limit. Depth-
limited search can solve the drawback of the infinite path in the Depth-first search. In this
algorithm, the node at the depth limit will treat as it has no successor nodes further.
Depth-limited search can be terminated with two Conditions of failure:
Standard failure value: It indicates that problem does not have any solution.
Cut off failure value: It defines no solution for the problem within a given depth limit.

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 8

 CHAPTER - 2

In the above example start node is S, Goal node is J and limit is 2.

Advantages:
Depth-limited search is Memory efficient.
Disadvantages:
Depth-limited search also has a disadvantage of incompleteness.
It may not be optimal if the problem has more than one solution.
4. Uniform-cost Search
Uniform-cost search is a searching algorithm used for traversing a weighted tree or graph.
This algorithm comes into play when a different cost is available for each edge.
The primary goal of the uniform-cost search is to find a path to the goal node which has
the lowest cumulative cost.
Uniform-cost search expands nodes according to their path costs form the root node. It can
be used to solve any graph/tree where the optimal cost is in demand.
A uniform-cost search algorithm is implemented by the priority queue.
It gives maximum priority to the lowest cumulative cost.
Uniform cost search is equivalent to BFS algorithm if the path cost of all edges is the same.

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 9

 CHAPTER - 2

Advantages:
Uniform cost search is optimal because at every state the path with the least cost is chosen.
Disadvantages:
It does not care about the number of steps involve in searching and only concerned about
path cost. Due to which this algorithm may be stuck in an infinite loop.
5. Iterative deepening depth-first Search:
The iterative deepening algorithm is a combination of DFS and BFS algorithms. This
search algorithm finds out the best depth limit and does it by gradually increasing the limit
until a goal is found.
This algorithm performs depth-first search up to a certain "depth limit", and it keeps
increasing the depth limit after each iteration until the goal node is found.
This Search algorithm combines the benefits of Breadth-first search's fast search and depth-
first search's memory efficiency.
The iterative search algorithm is useful uninformed search when search space is large, and
depth of goal node is unknown.

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 10

 CHAPTER - 2

IDDFS algorithm performs various iterations until it does not find the goal node. The iteration
performed by the algorithm is given as:
1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C, F, G
4'th Iteration------>A, B, D, H, I, E, C, F, K, G
In the fourth iteration, the algorithm will find the goal node.
Advantages:
It combines the benefits of BFS and DFS search algorithm in terms of fast search and
memory efficiency.
Disadvantages:
The main drawback of IDDFS is that it repeats all the work of the previous phase.
6. Bidirectional Search Algorithm
Bidirectional search algorithm runs two simultaneous searches, one form initial state called
as forward-search and other from goal node called as backward-search, to find the goal
node.
Bidirectional search replaces one single search graph with two small subgraphs in which
one starts the search from an initial vertex and other starts from goal vertex.
The search stops when these two graphs intersect each other.

In the below search tree, bidirectional search algorithm is applied. This algorithm divides one
graph/tree into two sub-graphs. It starts traversing from node 1 in the forward direction and starts
from goal node 16 in the backward direction.
The algorithm terminates at node 9 where two searches meet.
Advantages:
Bidirectional search is fast.

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 11

 CHAPTER - 2

Bidirectional search requires less memory

Disadvantages:
Implementation of the bidirectional search tree is difficult.

In bidirectional search, one should know the goal state in advance.

INFORMED SEARCH STRATEGIES OR HEURISTIC SEARCH

So far we have talked about the uninformed search algorithms which looked through search space
for all possible solutions of the problem without having any additional knowledge about search
space. But informed search algorithm contains an array of knowledge such as how far we are from
the goal, path cost, how to reach to goal node, etc. This knowledge help agents to explore less to
the search space and find more efficiently the goal node.
The informed search algorithm is more useful for large search space. Informed search algorithm
uses the idea of heuristic, so it is also called Heuristic search.
The term Heuristic is used for algorithms which find solutions among all possible ones. Heuristic
is a rule of thumb or judgement technique that leads to a solution but provides no guarantee of
success.
Heuristics function: Heuristic is a function which is used in Informed Search, and it finds the
most promising path. It takes the current state of the agent as its input and produces the estimation
of how close agent is from the goal. The heuristic method, however, might not always give the
best solution, but it guaranteed to find a good solution in reasonable time. Heuristic function
estimates how close a state is to the goal. It is represented by h(n), and it calculates the cost of an
optimal path between the pair of states. The value of the heuristic function is always positive.
h(n) <= h*(n)
Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic cost should be less than
or equal to the estimated cost.
Heuristic Search:
Heuristic search is the simplest form of heuristic search algorithms. It expands nodes based on
their heuristic value h(n). It maintains two lists, OPEN and CLOSED list. In the CLOSED list, it
places those nodes which have already expanded and in the OPEN list, it places nodes which have
yet not been expanded.

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 12

 CHAPTER - 2

On each iteration, each node n with the lowest heuristic value is expanded and generates all its
successors and n is placed to the closed list. The algorithm continues until a goal state is found.
In the informed search we will discuss two main algorithms which are given below:
Best First Search Algorithm(Greedy search)
A* Search Algorithm
1. Greedy Best-First Search
Greedy best-first search algorithm always selects the path which appears best at that
moment.
It is the combination of depth-first search and breadth-first search algorithms.
It uses the heuristic function and search. Best-first search allows us to take the advantages
of both algorithms.
With the help of best-first search, at each step, we can choose the most promising node.
In the best first search algorithm, we expand the node which is closest to the goal node and
the closest cost is estimated by heuristic function, i.e. f(n)= h(n).
Were, h(n)= estimated cost from node n to the goal.
The greedy best first algorithm is implemented by the priority queue.
It maintains two lists, OPEN and CLOSED list. In the CLOSED list, it places those nodes which
have already expanded and in the OPEN list, it places nodes which have yet not been expanded.
1. Step 1: Place the starting node into the OPEN list.
2. Step 2: If the OPEN list is empty, Stop and return failure.
3. Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n), and
places it in the CLOSED list.
4. Step 4: Expand the node n, and generate the successors of node n.
5. Step 5: Check each successor of node n, and find whether any node is a goal node or not.
If any successor node is goal node, then return success and terminate the search, else
proceed to Step 6.
6. Step 6: For each successor node, algorithm checks for evaluation function f(n), and then
check if the node has been in either OPEN or CLOSED list. If the node has not been in
both list, then add it to the OPEN list.
7. Step 7: Return to Step 2.

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 13

 CHAPTER - 2

Consider the above search problem, and we will traverse it using greedy best-first search. At each
iteration, each node is expanded using evaluation function f(n)=h(n) , which is given in the table.
In this search example, we are using two lists which are OPEN and CLOSED Lists. Following are the
iteration for traversing the above example.

Expand the nodes of S and put in the CLOSED list

Initialization: Open [A, B], Closed [S]

Iteration 1: Open [A], Closed [S, B]
Iteration 2: Open [E, F, A], Closed [S, B]
: Open [E, A], Closed [S, B, F]
Iteration 3: Open [I, G, E, A], Closed [S, B, F]
: Open [I, E, A], Closed [S, B, F, G]

Hence the final solution path will be: S----> B----->F----> G

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 14

 CHAPTER - 2

Advantages:
Best first search can switch between BFS and DFS by gaining the advantages of both the
algorithms.
This algorithm is more efficient than BFS and DFS algorithms.
Disadvantages:
It can behave as an unguided depth-first search in the worst case scenario.
It can get stuck in a loop as DFS.
This algorithm is not optimal.

2. A* Search Algorithm:
A* search is the most commonly known form of best-first search.
It uses heuristic function h(n), and g(n) gives the path cost from the start node to node n
It has combined features of UCS and greedy best-first search, by which it solve the problem
efficiently.
A* search algorithm finds the shortest path through the search space using the heuristic
function. This search algorithm expands less search tree and provides optimal result faster.
A* algorithm is similar to UCS except that it uses g(n)+h(n) instead of g(n).
In A* search algorithm, we use search heuristic as well as the cost to reach the node. Hence we can
combine both costs as following, and this sum is called as a fitness number.

Algorithm of A* search:
Step1: Place the starting node in the OPEN list.
Step 2: Check if the OPEN list is empty or not, if the list is empty then return failure and stops.
Step 3: Select the node from the OPEN list which has the smallest value of evaluation function
(g+h), if node n is goal node then return success and stop, otherwise

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 15

 CHAPTER - 2

Step 4: Expand node n and generate all of its successors, and put n into the closed list. For each
successor n', check whether n' is already in the OPEN or CLOSED list, if not then compute
evaluation function for n' and place into Open list.
Step 5: Else if node n' is already in OPEN and CLOSED, then it should be attached to the back
pointer which reflects the lowest g(n') value.
Step 6: Return to Step 2.

In this example, we will traverse the given graph using the A* algorithm. The heuristic value of
all states is given in the table so we will calculate the f(n) of each state using the formula f(n)=
g(n) + h(n), where g(n) is the cost to reach any node from start state.
Here we will use OPEN and CLOSED list.
Solution:

Initialization: {(S, 5)}

Iteration1: {(S--> A, 4), (S-->G, 10)}
Iteration2: {(S--> A-->C, 4), (S--> A-->B, 7), (S-->G, 10)}
Iteration3: {(S--> A-->C--->G, 6), (S--> A-->C--->D, 11), (S--> A-->B, 7), (S-->G, 10)}
Iteration 4 will give the final result, as S--->A--->C--->G
It provides the optimal path with cost 6

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 16

 CHAPTER - 2

Advantages:
A* search algorithm is the best algorithm than other search algorithms.
A* search algorithm is optimal and complete.
This algorithm can solve very complex problems.
Disadvantages:
It does not always produce the shortest path as it mostly based on heuristics and
approximation.
A* search algorithm has some complexity issues.
The main drawback of A* is memory requirement as it keeps all generated nodes in the
memory, so it is not practical for various large-scale problems.

Prepared by: Chandrashekhar K, Asst. Prof, Dept. of BCA Page 17