Introduction to Problem Solving

AI Unit II

1

• Problem solving is a method of deriving solution steps beginning

from initial description of the problem to the desired solution

• It is one the focus areas of AI and can be characterized as a systematic search using a range of possible steps to achieve some predefined solution
• The problems are frequently modelled as a state space problem where the state space is a set of all possible states from start to goal states

Introduction to Problem Solving

AI Unit II

2

• There are two types of problem solving methods:
• General-purpose method: Applicable to a wide variety of

problems

• Special -purpose method: Tailor-made for a particular problem
• The most general approach for solving a problem is to generate the

solution and test it

• For generating a new state in the search space, an action/ operator/ rule is applied and tested whether the state is the goal state or not. In case the state is not the goal state, the procedure is repeated
• The order of application of the rules to the current state is called

Control Strategy

General Problem Solving

AI Unit II

3

Production System (PS)

• PS is one of the formalisms that helps AI programs to do search

process more conveniently in state space problems

• This system comprises of start (initial) state(s) and goal(final) state(s) of the problem along with one or more databases consisting of suitable and necessary information for the particular task
• PS consists of number of production rules in which each production rule has left side that determines the applicability of the rule and a right side that describes the action to be performed

General Problem Solving

AI Unit II

4

Production System (PS)

• PS consists of control strategies that specify the sequence in which the

rules are applied when several rules match at once

• One of the examples of PS is an Expert System which is used for expert

opinion in a specific domain

• Advantages of PS:
• It is a good way to model the strong state-driven nature of intelligent action
• New rules can be easily added to account for new situations without

disturbing the rest of the system

• It is quite important in real-time environment and applications where new

input to the database changes the behaviour of the system

General Problem Solving

AI Unit II

5

Water Jug Problem: We have two jugs, a 5-gallon and 3-gallon capacity respectively with no measuring marker on them. There is endless supply of water through tap

5 -g Jug

3 -g Jug

General Problem Solving

AI Unit II

6

Water Jug Problem : Our task is to get 4 gallon of water in the 5-g jug

5 -g Jug

3 -g Jug

4 Gallon

General Problem Solving : Water Jug Problem

AI Unit II

7

• State Space for this problem can be described as the set of ordered pairs of integers (X, Y) such that X represents the number of gallons of water in 5-g jug and Y for 3-g jug

​

​

• Start state: (0,0)

​

​

• Goal state: (4,N) where N ≤ 3

General Problem Solving : Water Jug Problem

AI Unit II

8

Possible operations that can be used in this problem are as follows:

• Fill the 5-g jug from the tap and empty the 5-g jug by throwing water

down the drain

• Fill the 3-g jug from the tap and empty the 3-g jug by throwing water

down the drain

• Pour some or 3-g water from 5-g jug into the 3-g jug to make it full
• Pour some or full 3-g water into the 5-g jug

​

​

These rules can be formally be defined as production rules

Table 1: Production rules for Water Jug problem

AI Unit II

9

Table 2: Solution Path 1

AI Unit II

10

• There could be more than one solutions for a given problem

Table 3: Solution Path 2

AI Unit II

11

State Space Search

AI Unit II

12

• State space is another method of problem representation that facilitates

easy search

• Using this method, one can also find a path from start state to goal state while solving a problem
• A state space basically consists of four components:
1. A set S containing start states of the problem
2. A set G containing goal states of the problem
3. Set of nodes (states) in the graph/tree. Each node represents the state in problem-solving process
4. Set of arcs connecting nodes. Each arc corresponds to operator, that is a step in a problem-solving process

State Space Search

AI Unit II

13

• A solution path is a path through the graph from a node S to a node G
• The main objective of the algorithm is to determine a solution path in the

graph

• There may be more than one ways of solving a problem
• One solution path is selected based on some criteria of goodness or on

some heuristic function

• Commonly used approach is to apply appropriate operator to transfer one

state of problem to another

The Eight Puzzle Problem

AI Unit II

14

Problem Statement : It has a 3 x 3 Grid with 8 randomly numbered (1 to 8) tiles arranged on it with one empty cell. At any point, the adjacent tile can move to the empty cell, creating a new empty cell. Tiles are arranged such that we get the goal state from start state.

The Eight Puzzle Problem

AI Unit II

15

Start State

Goal State

The Eight Puzzle Problem

AI Unit II

16

• A state for this should keep track of the position of all tiles on the game board
• Empty cell on the board is represented by 0
• Start State : [ [3, 7, 6] , [5, 1, 2] , [ 4, 0, 8] ]
• Goal State: [ [5, 3, 6] , [7, 0, 2] , [ 4, 1, 8] ]
• Valid operators – { Up, Down, Left, Right } , the direction in which blank space effectively moves

AI Unit II

17

Partial Search Tree for Eight

Puzzle Problem

Right

Up

Left

Up

Left

Right

Initial State

Control Strategies

• Control Strategy is one of the most important components of problem solving
• It describes the order of application of the rules to the current state
• It should cause motion towards a solution
• One approach is to select a rule randomly from the applicable rules. This

approach is not systematic.

• Breadth First and Depth First search are Systematic control strategies. They are

exhaustive, uninformed, blind searches in nature

• If the problem is simple, then any control strategy that causes motion and is

systematic will lead to a solution.

• To solve some real world problems, effective control strategy must be used.

AI Unit II

18

Control Strategies

There are two directions in which a search could proceed

• Data-driven search, called forward chaining, from the start state
• Goal-driven search, called backward chaining, from the goal state
• Forward Chaining- The process of forward chaining begins with known facts

and works towards a conclusion.

For eg. Language OPS5 uses forward reasoning rules. Rules are expressed in the form of if-then rules.

• Backward Chaining-It is a goal-directed strategy that begins with the goal state and continues working backward, generating more sub-goals that must also be satisfied to satisfy main goal until we reach to start state. Prolog language uses

this strategy

AI Unit II

19

Control Strategies

AI Unit II

20

• The computational effort in both the strategies is the same.
• Same state space is searched but in different order.
• If there are a large set of explicit goal states and one start state, then it would not be efficient to solve using backward chaining strategies because we do not know which goal state is closest to the start state. Forward Chaining is better in such situations.
• Move from the smaller set of states to the larger set of states and proceed in the direction with the lower branching factor (the average number of nodes that can be reached directly from single node)
• Theorem proving from a small set of axioms uses backward strategy as the branching factor is significantly greater going forward from axioms to theorem rather than going from theorems to axioms.

Characteristics of Problem

AI Unit II

21

• Type of problem: There are three types of problems in real life:
• Ignorable-These are the problems where we can ignore the solution steps For eg. In proving a theorem, if some lemma is proved to prove a theorem and later on we realize that it is not useful, then we can ignore this solution step and prove another lemma
• Recoverable-These are the problems where the solutions steps can be undone

For eg. In Water Jug Problem, if we have filled the jug, we can empty it also

• Irrecoverable- The problems where the solution steps cannot be undone

For eg. Any two player game such as Chess, Playing Cards, Snake and Ladder

Characteristics of Problem

AI Unit II

22

• Decomposability of a problem: Divide the problem into a set of independent smaller sub-problems, solve them and combine the solutions to get the final solutions
• Role of Knowledge: Knowledge plays an important role in solving any problem. Knowledge could be in the form of rules and facts which help generating search space for finding the solution
• Consistency of Knowledge Base used in solving problem: Make sure that knowledge base used to solve problem is consistent. Inconsistent knowledge base will lead to wrong solutions

For eg. If it is humid, it will rain. If it is sunny, it is daytime. It is sunny day. It is

nighttime.

Characteristics of Problem

AI Unit II

23

• Requirement of Solution – We should analyze the problem whether solution required is absolute or relative.
• We call a solution to be absolute if we have to find exact solution.

For eg. Water Jug problem –Any path problem-Solved in reasonable amount

of time

• A solution is relative if we have reasonably good and approximate solution. For eg. Travelling salesman problem-Best path problem- Computationally harder compared to any-path problem.

Exhaustive Searches

AI Unit II

24

Systematic uninformed exhaustive searches:

1. Breadth-First Search
2. Depth-First Search
3. Depth-First Iterative Deepening Search
4. Bidirectional Search

1. Breadth-First Search(BFS)

AI Unit II

25

• The Breadth-First search expands all the states one step away from the start state and then expands all states two steps from start state, then three steps, etc., until a goal state is reached.
• All successor states are examined at the same depth before going deeper.
• The BFS always gives an optimal path or solution.
• This search is implemented using two lists called OPEN and CLOSED
• The OPEN list contains those states that are to be expanded and CLOSED list keeps track of states already expanded
• OPEN list is maintained as a queue and CLOSED list as a stack.

Breadth-First Search(BFS) Algorithm

AI Unit II

26

Input: START and GOAL states

Local Variables: OPEN, CLOSED, STATE-X, SUCCs, FOUND;

Output: Yes or No Method:

• Initialize OPEN list with START and CLOSED =Φ;
• FOUND = false;
• while (OPEN ≠ Φ and FOUND =false ) do

{

• remove the first state from OPEN and call it STATE-X;
• put STATE-X in the front of CLOSED list; /*maintained as Stack*/
• if STATE-X = GOAL then FOUND = true else

{

• perform EXPAND operation on STATE-X, producing a list of SUCCs;
• remove from successors those states, if any, that are in the CLOSED list;
• append SUCCs at the end of the OPEN list; /* queue*/

}

}

• If FOUND = true then return Yes else return No
• Stop

Table 1: Production rules for Water Jug problem

AI Unit II

27

AI Unit II

28

Search Tree Generation using BFS for Water Jug Problem

1. Breadth-First Search(BFS)

AI Unit II

29

• Solution Path : (0,0) 🡪 (5,0) 🡪 (2,3) 🡪 (2,0) 🡪 (0,2) 🡪 (5,2) 🡪 (4,3)
• The path information can be obtained by modifying CLOSED list in the algorithm by putting pointer back to its parent.
• It is not memory efficient as partially developed tree is to be kept in the memory but it finds optimal solution or path

2. Depth-First Search (DFS)

AI Unit II

30

• In the Depth-First Search, we go as far down as possible into the search tree/graph before backing up and trying alternatives
• It works by always generating a descendant of the mostly recently expanded node until some depth cut off is reached and then backtracks to next most recently expanded node and generates one of its descendants
• DFS is memory efficient, as it only stores a single path from the root to leaf node along with the remaining unexpanded siblings for each node on the path
• DFS can be implemented by using two lists called OPEN and CLOSED
• OPEN list contains those states that are to be expanded and CLOSED list

keeps track of states already expanded. Both are maintained as stacks.

Depth-First Search (DFS) Algorithm

AI Unit II

31

Input: START and GOAL states

Local Variables: OPEN, CLOSED, RECORD_X, SUCCESSORS, FOUND;

Output: A path sequence from START to GOAL state, if one exists, otherwise return No

Method:

• Initialize OPEN list with (START, nil) and set CLOSED =Φ;
• FOUND = false;
• while (OPEN ≠ Φ and FOUND =false ) do

{

• Remove the first record ( initially (START, nil)) from OPEN list and call it RECORD_X;
• put RECORD_X in the front of CLOSED list; /*maintained as Stack*/
• if (STATE-X of RECORD_X = GOAL) then FOUND = true else

{

• perform EXPAND operation on STATE-X producing a list of records called SUCCESSORS ; create each record by associating parent link with its state ;
• remove from SUCCESSORS any record that is already in the CLOSED list;
• insert SUCCESSORS in the front of the OPEN list; /* Stack*/

}

}

• If FOUND = true then return the path by tracing through the pointers to the parents on

the CLOSED list else return No

• Stop

AI Unit II

32

Search Tree Generation using DFS

AI Unit II

33

2. Depth-First Search (DFS)

The path is obtained from the list stored in CLOSED. The solution path is (0,0) 🡪 (5,0) 🡪 (5,3) 🡪 (0,3) 🡪(3,0) 🡪 (3,3) 🡪 (5,1) 🡪 (0,1) 🡪 (1,0) 🡪

(1,3) 🡪 (4,0)

AI Unit II

34

Comparison between BFS and DFS:

• BFS is effective when the search tree has a low branching factor
• BFS can work even in trees that are infinitely deep
• BFS requires a lot of memory as number of nodes in level of the tree increases exponentially
• BFS is superior when the GOAL exists in the upper right portion of a

search tree

• BFS gives optimal solution
• DFS is effective when there are few sub trees in the search tree that have

only one connection point to the rest of the states

• DFS is best when the GOAL exists in the lower left portion of the search

tree

• DFS can be dangerous when the path closer to the START and farther

from the GOAL has been chosen

• DFS is memory efficient as the path from start to current node is stored. Each node should contain state and its parent
• DFS may not give optimal solution

Measuring Problem Solving Performance

The output of the problem solving algorithm is either failure or a solution.

We can evaluate an algorithm’s performance in four ways.

​

Completeness: Is the algorithm guaranteed to find a solution when there is one?

Optimality: Does the strategy find the optimal solution?

Time Complexity: How long does it take to find a solution?

Space Complexity: How much memory is needed to perform the search?

Searching with Partial Information

What happens when knowledge of the states or actions is incomplete?

We find that different types of incompleteness lead to three distinct problem types:

1. Sensorless Problems:

3. Depth-First Iterative Deepening Search(DFID)

AI Unit II

37

• It takes advantages of both BFS and DFS searches on trees.
• It expands all nodes at a given depth before expanding any nodes at greater depth
• It is guaranteed to find the shortest path or optimal solution from start to

goal state

Depth-First Iterative Deepening Search(DFID) Algorithm

AI Unit II

38

Input: START and GOAL states Local Variables: FOUND Output: Yes or No

Method:

• Initialize d=1 , FOUND = false
• while( FOUND = false) do

{

• perform a depth first search from start to depth d
• if goal state is obtained then FOUND = true else discard the nodes generated in the search of depth d
• d = d+1

}

• if FOUND = true then return Yes otherwise return No
• Stop

AI Unit II

39

Search Tree Generation using DFID

3. Depth-First Iterative Deepening Search(DFID)

AI Unit II

42

• At any given time, it is performing a DFS and never searches deeper than depth ‘d’
• The space it uses is O(d)
• Disadvantage of DFID is that it performs wasted computation before

reaching the goal depth

4. Bidirectional Search

AI Unit II

43

• Bidirectional Search is a graph search algorithm that runs two simultaneous searches
• One search moves forward from the start state and other moves backward

from the goal and stops when the two meet in the middle

• It is useful for those problems which have a single start state and single goal

state

• The DFID can be applied to bidirectional search for k=1, 2, … .The k^th iteration consists of generating all states in the forward direction from start state up to depth k using BFS, and from goal state using DFS, one to depth k and other to

depth k+1, not storing states but simply matching against the stored states

generated from forward direction

4. Bidirectional Search

AI Unit II

44

• Here the backward search to depth k+1 is necessary to find odd length solutions
• If match is found, then path can be traced from start to the matched state and

from matched state to goal state

• Each node has link to its successors as well as to its parent. These links will

help generating complete path from start to goal states

• The reason for this search is that each of the two searches has time complexity O(b ^d/2) and O(b ^d/2 + b ^d/2) is much less than the running time of one search from the beginning to the goal, which would be O(b^d )
• This search can be made in already existing graph/tree or search graph/tree

can be generated as a part of search

Find a route /path from node labeled 1 to node labeled 16

AI Unit II

45

Graph to be searched using Bidirectional Search

Trace of Bidirectional Space

AI Unit II

46

Analysis of Search Methods

Effectiveness of any search strategy in problem solving is measured in terms of :

​

• Completeness : An algorithm guarantees a solution if it exists

​

• Time Complexity: Time required by an algorithm to find a solution

​

• Space Complexity: Space required by an algorithm to find a solution
• Optimality: Algorithm finds the highest quality solution when there are several different solutions for the problem

AI Unit II

54

Analysis of Search Methods

AI Unit II

55

Let b be the branching factor and d be the depth of tree in worst case

Analysis of Search Methods

AI Unit II

56

• Above mentioned searches are blind and are not of much use in real-life applications
• There are problems where combinatorial explosion takes place as the size

of the search tree increases, such as Travelling Salesman Problem

• We need to have some intelligent searches which take into account some

relevant problem information and finds solutions faster

• Let us consider a problem of travelling salesman
• In Travelling Salesman Problem(TSP), one is required to find the shortest route of visiting all the cities once and returning back to starting point

Analysis of Search Methods

AI Unit II

57

• All possible paths of the search tree are explored and the shortest path is

returned

• If there are n cities, then (n-1)! paths need to be examined . If number of

cities grows, then the time required to wait a salesman to get the information about the shortest path is not a practical solution. This phenomenon is called a combinatorial explosion

• Above strategy could be improved using the following techniques:
• Stop generating complete paths, keep track of the shortest path found so far
• Stop exploring any path as soon as its partial length becomes greater

than the shortest path length found so far

• This method is efficient than first one but still requires exponential time

that is directly proportional to some number raised to ‘n’

AI Unit II

58

Graph for Travelling Salesman Problem

AI Unit II

61

Performance

Comparison

Heuristic Search Techniques

AI Unit II

60

• Heuristic Technique is a criterion for determining which among several

alternatives will be the most effective to achieve some goal

• It improves the efficiency of a search process by sacrificing claims of

systematic and completeness

• It no longer guarantees to find the best solution but almost always find a

very good solution

• We can hope to get good solution to hard problems like Travelling Salesman Problem in less than exponential time.
• There are two types of heuristics :
• General-purpose heuristics that are useful in various problem domains
• Special purpose heuristics that are domain specific
• Searches which use some domain knowledge are called Informed Search

Strategies

Hill Climbing

AI Unit II

61

• Hill Climbing is variant of Generate and Test Strategy
• It is an optimization technique that belongs to the family of local searches
• It can be used to solve problems that have many solutions but where some

solutions are better than others

• Travelling Salesman problem can be solved with hill climbing
• Hill Climbing proceeds in a depth first order, but the choices are ordered according to some heuristic value (i.e. measure of remaining cost from current to goal state)

Simple Hill Climbing Algorithm

AI Unit II

62

Input: START and GOAL states

Local Variables: OPEN, NODE, SUCCs, FOUND;

Output: Yes or No

Method:

• initially store the start node in a OPEN list (maintained as stack); FOUND = false;
• while (OPEN ≠ empty and FOUND =false ) do

{

• remove the top element from OPEN list and call it NODE;
• if NODE is the goal node, then FOUND = true else

{

• find SUCCs of NODE, if any;
• sort SUCCs by estimated cost from NODE to goal state and add them to the

front of OPEN list;

}

}

• If FOUND = true then return Yes otherwise return No;
• Stop

Problems with Hill Climbing

AI Unit II

63

• The search process may reach to a position that is not a solution but from there no move improves the situation. This will happen if we have reached a local maximum, a plateau or a ridge
• Local maximum : It is a state that is better than all its neighbours but not better than some other states which are far away. From this state all

moves look to be worse. In such case backtrack to some earlier state and try going in different direction to find a solution

• Plateau: It is a flat area of the search space where all neighbouring states have the same value. It is not possible to determine the best direction. In such situation make a big jump to some direction and try to get a new

section of the search space

Problems with Hill Climbing

AI Unit II

64

• Ridge : It is an area of search space that is higher than surrounding areas but that cannot be traversed by single moves in any one direction. It is a special kind of local maxima. Here apply two or more rules before doing the test i.e. moving in several directions at once.

Best First Search

AI Unit II

65

• It is based on expanding the best partial path from current node to goal node
• Here forward motion is from the best open node so far in the partially developed tree
• The cost of partial paths is calculated using some heuristic
• If the state has been generated earlier and new path is better than the previous one, then change the parent and update the cost
• In hill climbing, sorting is done on successor nodes, whereas in the best first

search, sorting is done on the entire list

• It is not guaranteed to find an optimal solution, but generally it finds some

solution faster than solution obtained from any other method

• Performance varies directly with the accuracy of the heuristic evaluation

function

Best First Search Algorithm

AI Unit II

66

Input: START and GOAL states

Local Variables: OPEN, CLOSED, NODE, FOUND;

Output: Yes or No

Method:

• Initialize OPEN list by root node; CLOSED =Φ; FOUND = false;
• while (OPEN ≠ Φ and FOUND =false ) do

{

• if the first element is the goal node , then FOUND = true else remove it from

OPEN list and put it in CLOSED list;

• add its successor, if any, in OPEN list;
• sort the entire list by the value of some heuristic function that assigns to each

node, the estimate to reach to the goal node;

}

• If FOUND = true then return Yes otherwise return No;
• Stop

Best First Search

AI Unit II

67

Condition for termination

• Instead of terminating when a path is found, terminate when the shortest incomplete path is longer than the shortest complete path

A* Algorithm

AI Unit II

68

• It is a combination of Branch and Bound and Best Search Methods combined with the dynamic programming principle
• It uses a heuristic or evaluation function usually denoted by f(X) to

determine the order in which the search visits nodes in the tree

• The heuristic function for a node N is defined as follows:

f(N) = g(N) + h(N)

where –

g is a measure of the cost of getting from the start node to the current node N i.e. sum of costs of the rules that were applied along the best path to the current node

h is an estimate of additional cost of getting from current node N to the

goal node

A* Algorithm

AI Unit II

69

• It is called the OR graph / tree search algorithm
• It incrementally searches all the routes starting from the start node until it

finds the shortest path to a goal

• Starting with a given node, the algorithm expands the node with the lowest

f(X) value

The Eight Puzzle Problem

AI Unit II

Start State

70

Goal State

• Consider the eight puzzle problem
• f(X) = g(X) + h(X)

where h(X) = number of tiles not in their goal position in a given state X

g(X) = depth of node X in the search tree

AI Unit II

71

AI Unit II

• The following Eight Puzzle Problem cannot be solved using the heuristic function

mentioned before

^{Start State} Goal State

• A better estimate of h function might be as follows.
• The function g may remain same
• h(X) = the sum of the distances of the tiles (1 to 8) from their goal position

in a given state X

• Here start state has h(start_state)= 3+2+1+0+1+2+2+1=12

72

A* Algorithm

AI Unit II

73

1. Initialize: set OPEN=[s], CLOSED=[], g(s)=0, f(s)=h(s)
2. Fail: If OPEN=[], then terminate and fail
3. Select: Select a state with minimum cost ,n, from OPEN and save in CLOSED
4. Terminate: If n∈G then terminate with success and return f(s)
5. Expand: For each successor, m of n

For each successor, m, insert m in OPEN only if if m∉ [OPEN𝖴CLOSED]

set g(m)= g[n]+C[n,m]

set f(m)=g(m)+h(m)

if m∈[OPEN𝖴CLOSED]

set g(m)= min{g[m], g(n)+C[n,m]} set f(m)=g(m)+h(m)

if f[m] has decreased and m∈CLOSED move m to OPEN

6. Loop: Goto step 2

Optimal Solution by A* Algorithm

AI Unit II

• Underestimation – Here we are underestimating heuristic value of each

node in the graph/tree.

Example search graph for Underestimation

74

Optimal Solution by A* Algorithm

AI Unit II

Example search graph for Overestimation

75

• Overestimation – Here we are overestimating heuristic value of each node in the graph/tree. By overestimating h we cannot guarantee to find shortest path

Optimal Solution by A* Algorithm

AI Unit II

76

• Admissibility of A*
• A search algorithm is admissible if for any graph, it always terminates

in an optimal path from start state to goal state, if path exists

• If heuristic function ‘h’ underestimates the actual value from current state to goal state, then it bounds to give an optimal solution and hence is called admissible function.
• A* always terminates with the optimal path in case h is an admissible

heuristic function