Problem Solving by

Searching
 Example 1: Water Jug Problem
Consider the following problem:
A Water Jug Problem: You are given two jugs, a 4-gallon one and a 3-gallon one, a
pump which has unlimited water which you can use to fill the jug, and the ground on
which water may be poured. Neither jug has any measuring markings on it. How can
you get exactly 2 gallons of water in the 4-gallon jug?

• State Representation and Initial State – we will represent a state of the problem as a
tuple (x, y) where x represents the amount of water in the 4-gallon jug and y
represents the amount of water in the 3-gallon jug. Note 0 ≤ x ≤ 4, and 0 ≤ y ≤ 3.
• Our initial state: (0,0)
• Goal Predicate – state = (2,y) where 0 ≤ y ≤ 3.
• Operators – we must define a set of operators that will take us from one state to
another:
Example: Water jug problem
Given a 3-gallon and a 4-gallon water jug, how can we measure exactly 2 gallons in the 4-g jug in the
minimum number of moves?

1. (x,y)(4,y) Fill the 4-gallon jug

if x < 4
2. (x,y)(x,3) Fill the 3-gallon jug
if y < 3
3. (x,y)(x-d,y) Pour some water out of the 4-gallon jug
if x > 0
4. (x,y)(x,y-d) Pour some water out of the 3-gallon jug
if y > 0
5. (x,y)(0,y) Empty the 4-gallon jug on the ground
if x > 0
7. (x,y)(4,y-(4-x)) Pour the water from the 3-gallon jug
if x +y>=4 and y > 0 into the 4- gallon jug until it is full
8. (x,y)(x-(3-y),3) Pour the water from the
if x +y>=3 4-gallon jug into the
and x > 0 3- gallon jug until the 3- gallon jug is full
9. (x,y)(x+y,0) Pour all the water
if x +y<=4 from the 3-gallon jug
and y > 0 into the 4- gallon jug
10. (x,y)(0,x+y) Pour all the water from the 4-gallon
if x +y<=3 and y > 0 jug into the 3 -gallon jug
11. (0,2)(2,0) Pour the 2- gallons
from the 3- gallons jug into the 4-gallon jug
12. (2,y) (0,y) Empty the 2- gallons in
the 4 - gallons jug on the ground
Fig. Production Rules for the water jug problem
4G Jug 3G jug Production Rule

0 0
Problem solving agents
• Goal Formulation
Desired state of the world.
Organize behavior by limiting the objectives

• Problem Formulation
(successor function).
Process of deciding what action and state to consider, given a goal

• Search
Determine a sequence of actions that lead to a goal state.
• Execute
Perform the actions.
• Assumptions:
Environment is fully observable and deterministic
In order to provide a formal description of a problem, it is necessary to do the following:

• Define a state space containing all the possible configurations of the

relevant objects
(State Space: Method of problem representation used in search and
in machine learning)
Problem can be viewed as a task of finding a path from a given start
state to some desirable state.
• Specify one or more states within that space that describe the possible
situations from which the problem solving process may start.
• Specify one or more states that would be acceptable as solutions to the
problem. These states are called goal states.
• Specify a set of rules that describe the action available.
Formulating a search problem
• State space S (nodes)
• Successor function: the states you can move to by an action (edge)
from the current state
• Initial state
• Transition Model: description of what each
Action does
• Goal test
• is a state x a goal?
• Cost
A problem is defined by four items:

initial state e.g., “at Arad”

successor function S ( x ) = set of action–state pairs e.g., S (Arad) =
{<Arad → Zerind, Zerind >, . . . }
goal test, can be explicit, e.g., x = “at Bucharest” implicit, e.g., NoDirt
(x)
path cost (additive) e.g., sum of distances, number of actions
executed, etc. Usually given as c (x, a, y), the step cost from x to y by
action a, assumed to be ≥ 0.

A solution is a sequence of actions leading from the initial state to a

goal state
Example: The 8-puzzle
Example 2: The 8-puzzle
• State : a 3 × 3 matrix of integers 0 ≤ n ≤ 8
• Initial State : any state
• Actions : move the blank space: left, right, up, down
• Goal test : equal to goal state (given above)
• Path cost: 1 per move
 Example 3: Missionaries and Cannibals
• start state — 3 missionaries, 3 cannibals, and a boat that holds two
people, on one side of river
• goal state — all on other side
• states— description of legal configurations (ie. where no-one gets
eaten) of where the missionaries, cannibals, and boat are
• operators (Action)— state changes possible using 2-person boat
• CCR - transport two cannibals to the right bank
• MCL - transport a missionary and a cannibal to the left bank
Initial state: (3,3,L) Goal: (0,0,R)
The 8-queens problem
Incremental formulation
• States? Any arrangement of 0 to 8 queens
on the board
• Initial state? No queens
• Actions? Add queen in empty square
• Goal test? 8 queens on board and none
attacked
• Path cost? None
64 x 63 x … 57 ~ 3 x 1014 states to
investigate
Another incremental formulation:

• States? n (between 0 and 8) queens on the board, one in each of the

n left-most columns; no queens attacking each other.
• Initial state? No queens
• Actions? Add queen in leftmost empty column such that it does not
attack any of the queens already on the board.
• Goal test? 8 queens on board
 Search
•Easiest way to implement various search strategies is to maintain a queue of
unexpanded search nodes.
•Different strategies result from different methods for inserting new nodes in
the queue.

Uniformed search strategies (blind, exhaustive, bruteforce) do not guide the

search with any additional information about the problem.

•Informed search strategies (heuristic, intelligent) use information about the

problem (estimated distance from a state to the goal) to guide the search.
 Generic Search
Algorithm
• Fringe = set of nodes generated but not expanded

• fringe := {initial state}

• loop:
• if fringe empty, declare failure
• choose and remove a node v from fringe
• check if v’s state s is a goal state; if so, declare success
• if not, expand v, insert resulting nodes into fringe
• Key question in search: Which of the generated nodes do we expand
next?
Properties of search strategies

-Completeness
-Time Complexity
-Space Complexity
-Optimality

Complexity:
branching factor: maximum number of successor of any node.
depth: shallowest goal node.
m:maximum length of any path in a state space.
Uninformed search
• Given a state, we only know whether it is a goal state or not
• Cannot say one non goal state looks better than another non
goal state
• Can only traverse state space blindly in hope of somehow
hitting a goal state at some point

• Also called blind search

• Blind does not imply unsystematic!
Breadth-first search
Properties of breadth-first search
• Nodes are expanded in the same order in which they are generated
• Fringe can be maintained as a First-In-First-Out (FIFO) queue
• BFS is complete: if a solution exists, one will be found
• BFS finds a shallowest solution
• Not necessarily an optimal solution
• If every node has b successors (the branching factor), first solution
is at depth d, then fringe size will be at least bd at some point
• This much space (and time) required
Depth-first search
Implementing depth-first search
• Fringe can be maintained as a Last-In-First-Out (LIFO)
queue (or a stack)
• Also easy to implement recursively:
• DFS(node)
• If goal(node) return solution(node);
• For each successor of node
• Return DFS(successor) unless it is failure;
• Return failure;
 Properties of depth-first search
• Not complete (might cycle through nongoal states)
• If solution found, generally not optimal/shallowest
• If every node has b successors (the branching factor), and we search
to at most depth m, fringe is at most bm
• Much better space requirement
• Actually, generally don’t even need to store all of fringe
• Time: still need to look at every node
• bm + bm-1 + … + 1 (for b>1, O(bm))
• Inevitable for uninformed search methods…
 Combining good properties of BFS and DFS
• Limited depth DFS: just like DFS, except never go deeper than some depth d
• Iterative deepening DFS:
• Call limited depth DFS with depth 0;
• If unsuccessful, call with depth 1;
• If unsuccessful, call with depth 2;
• Etc.

• Complete, finds shallowest solution

• Space requirements of DFS
• May seem wasteful time wise because replicating effort
• Really not that wasteful because almost all effort at deepest level
• db + (d-1)b2 + (d-2)b3 + ... + 1bd is O(bd) for b > 1
 Let’s start thinking about cost
• BFS finds shallowest solution because always works on shallowest
nodes first
• Similar idea: always work on the lowest-cost node first (uniform-cost
search)
• Will find optimal solution (assuming costs increase by at least constant
amount along path)
• Will often pursue lots of short steps first
• If optimal cost is C, and cost increases by at least L each step, we can
go to depth C/L
• Similar memory problems as BFS
• Iterative lengthening DFS does DFS up to increasing costs
Informed search
• So far, have assumed that no non-goal state looks better than another
• Unrealistic
• Even without knowing the road structure, some locations seem closer to the goal
than others
• Some states of the 8s puzzle seem closer to the goal than others
• Makes sense to expand closer-seeming nodes first
Heuristics: To find or discover
• A heuristic is a rule of thumb, strategy, trick, simplification or any kind of
device which drastically limits search for solution in large problem space.
Heuristics
• Key notion: heuristic function h(n) gives an estimate of the distance
from n to the goal
• h(n)=0 for goal nodes
• E.g. straight-line distance for traveling problem
C 2
B 9
2
3 F goal state
A E
start state D 4
3 4
• Say: h(A) = 9, h(B) = 8, h(C) = 9, h(D) = 6, h(E) = 3, h(F) = 0
• We’re adding something new to the problem!
• Can use heuristic to decide which nodes to expand first
 Example Heuristics: 8-puzzle

Consider the following heuristics:

• h1 = number of misplaced tiles (=7 in example)
• h2 = total Manhattan distance (i.e., no. of squares from desired location of
each tile) (= 2+3+3+2+4+2+0+2 = 18 in example)
• Which one is better?
• Intuitively, h2 seems better: it varies more across the state space, and its
estimate is closer to the true cost.
Where Do Heuristics Come From?
• Prior knowledge about the problem
• Exact solution cost of a relaxed version of the problem
– E.g. If the rules of the 8-puzzle are relaxed so that a tile can move anywhere,
then h1 gives the shortest solution
– If the rules are relaxed so that a tile can move to any adjacent square, then h2
gives the shortest solution
• Learning from prior experience
AI Problems
• The Knight’s tour problem
• Crypt Arithmetic Problem
Generate-and-Test

Algorithm
1. Generate a possible solution.
2. Test to see if this is actually a solution.
3. Quit if a solution has been found.
Otherwise, return to step 1.

38
Generate-and-Test

• Acceptable for simple problems.

• Inefficient for problems with large space.

39
Generate-and-Test

• Exhaustive generate-and-test.
• Heuristic generate-and-test: not consider paths that seem unlikely to
lead to a solution.
• Plan generate-test:
- Create a list of candidates.
- Apply generate-and-test to that list.

40
Generate-and-Test

Example: coloured blocks

“Arrange four 6-sided cubes in a row, with each side of
each cube painted one of four colours, such that on all
four
sides of the row one block face of each colour is
showing.”

41
Generate-and-Test

Example: coloured blocks

Heuristic: if there are more red faces than other

colours
then, when placing a block with several red faces, use
few
of them as possible as outside faces.

42
Hill Climbing

• Searching for a goal state = Climbing to the top of a

hill

43
Hill Climbing

• Generate-and-test + direction to move.

• Heuristic function to estimate how close a given state is to a goal
state.

44
Simple Hill Climbing

Algorithm
1. Evaluate the initial state.
2. Loop until a solution is found or there are no new
operators left to be applied:
- Select and apply a new operator
- Evaluate the new state:
goal  quit
better than current state  new current state

45
Simple Hill Climbing
• Evaluation function as a way to inject task-specific knowledge into the
control process.

46
Simple Hill Climbing

Example: coloured blocks

Heuristic function: the sum of the number of different

colours on each of the four sides (solution = 16).

47
Steepest-Ascent Hill Climbing (Gradient
Search)
• Considers all the moves from the current state.
• Selects the best one as the next state.

48
Steepest-Ascent Hill Climbing (Gradient
Search)
Algorithm
1. Evaluate the initial state.
2. Loop until a solution is found or a complete
iteration produces no change to current state:
- SUCC = a state such that any possible successor of the
current state will be better than SUCC (the worst state).
- For each operator that applies to the current state, evaluate
the new state:
goal  quit
better than SUCC  set SUCC to this state
- SUCC is better than the current state  set the current
state to SUCC.
49
Hill Climbing: Disadvantages
Local maximum
A state that is better than all of its neighbours, but not
better than some other states far away.

50
Hill Climbing: Disadvantages
Plateau
A flat area of the search space in which all neighbouring
states have the same value.

51
Hill Climbing: Disadvantages
Ridge
The orientation of the high region, compared to the set
of available moves, makes it impossible to climb up.
However, two moves executed serially may increase
the height.

52
Hill Climbing: Disadvantages

Ways Out
• Backtrack to some earlier node and try going in a different direction.
• Make a big jump to try to get in a new section.
• Moving in several directions at once.

53
Hill Climbing: Disadvantages
• Hill climbing is a local method:
Decides what to do next by looking only at the “immediate”
consequences of its choices.
• Global information might be encoded in heuristic functions.

54
Hill Climbing: Disadvantages

Start Goal
A D
D C
C B
B A
Blocks World

55
Hill Climbing: Disadvantages

Start Goal
A D
0 4
D C
C B
B A
Blocks World
Local heuristic:
+1 for each block that is resting on the thing it is supposed to be
resting on.
-1 for each block that is resting on a wrong thing.

56
Hill Climbing: Disadvantages

0 A 2

D D
C C
B B A

57
Hill Climbing: Disadvantages

D 2
C
B A

A 0
0
D
C C D C 0

B B A B A D

58
Hill Climbing: Disadvantages

Start Goal
A D
-6 6
D C
C B
B A
Blocks World
Global heuristic:
For each block that has the correct support structure: +1 to
every block in the support structure.
For each block that has a wrong support structure: -1 to
every block in the support structure.
59
Hill Climbing: Disadvantages

D -3
C
B A

A -6
-2
D
C C D C -1

B B A B A D

60
Hill Climbing: Conclusion
• Can be very inefficient in a large, rough problem space.
• Global heuristic may have to pay for computational complexity.
• Often useful when combined with other methods, getting it started
right in the right general neighbourhood.

61
Simulated Annealing
• A variation of hill climbing in which, at the beginning of the process,
some downhill moves may be made.

• To do enough exploration of the whole space early on, so that the

final solution is relatively insensitive to the starting state.
• Lowering the chances of getting caught at a local maximum, or
plateau, or a ridge.

62
Temperature reduction Rules
Simulated Annealing
Physical Annealing
• Physical substances are melted and then gradually cooled until some
solid state is reached.
• The goal is to produce a minimal-energy state.
• Annealing schedule: if the temperature is lowered sufficiently slowly,
then the goal will be attained.
• Nevertheless, there is some probability for a transition to a higher
energy state: e-E/kT.

64
Simulated Annealing
Algorithm
1. Evaluate the initial state.
2. Loop until a solution is found or there are no new
operators left to be applied:
- Set T according to an annealing schedule
- Selects and applies a new operator
- Evaluate the new state:
goal  quit
E = Val(current state) - Val(new state)
E < 0  new current state
else  new current state with probability e-E/kT.
65
Best-First Search
• Depth-first search: not all competing branches having to be expanded.
• Breadth-first search: not getting trapped on dead-end paths.
 Combining the two is to follow a single path at a time, but
switch paths whenever some competing path look more
promising than the current one.

66
Best-First Search
A A A

B C D B C D
3 5 1 3 5
E F
4 6
A A

B C D B C D
5 5
G H E F G H E F
6 5 4 6 6 5 6
I J
2 1
67
Best-First Search
• OPEN: nodes that have been generated, but have not examined.
This is organized as a priority queue.

• CLOSED: nodes that have already been examined.

Whenever a new node is generated, check whether it has been
generated before.

68
Best-First Search

Algorithm
1. OPEN = {initial state}.
2. Loop until a goal is found or there are no nodes left
in OPEN:
- Pick the best node in OPEN
- Generate its successors
- For each successor:
new  evaluate it, add it to OPEN, record its parent
generated before  change parent, update successors

69
Best-First Search
• Greedy search:
h(n) = estimated cost of the cheapest path from node n to a goal
state.

70
Best-First Search
• Uniform-cost search:
g(n) = cost of the cheapest path from the initial state to node
n.

71
Best-First Search
• Greedy search:
h(n) = estimated cost of the cheapest path from node n to a
goal state.
Neither optimal nor complete

72
Best-First Search
• Greedy search:
h(n) = estimated cost of the cheapest path from node n to a
goal state.
Neither optimal nor complete

• Uniform-cost search:
g(n) = cost of the cheapest path from the initial state to node
n.
Optimal and complete, but very inefficient

73
 AND/OR graphs
• Some problems are best represented as achieving subgoals, some
of which achieved simultaneously and independently (AND)
• Up to now, only dealt with OR options

Possess TV set

Steal TV Earn Money Buy TV

Searching AND/OR graphs
• A solution in an AND-OR tree is a sub tree whose leafs
are included in the goal set

• Cost function: sum of costs in AND node

f(n) = f(n1) + f(n2) + …. + f(nk)
 AND/OR search
• We must examine several nodes simultaneously
when choosing the next move

A
(9) A
(3) B D (5)
(4) C 38
B C D
17 9 27
E F G H I J
(5) (10) (3) (4) (15) (10)
AND/OR Best-First-Search
• Traverse the graph (from the initial node) following
the best current path.
• Pick one of the unexpanded nodes on that path and
expand it. Add its successors to the graph and
compute f for each of them
• Change the expanded node’s f value to reflect its
successors. Propagate the change up the graph.
• Reconsider the current best solution and repeat until
a solution is found
AND/OR Best-First-Search example
1. 2.
A A
(5) (9)
(3) B D (5)
(4) C
3. A
(9) D (10)
B (3) C (4)
(10)
E (4) F (4)
AND/OR Best-First-Search example

4.
A
(12)
B (6) C (4) D (10)

(10)
G (5) H (7) E (4) F (4)
A Longer path may be better
A

B C D A

G H E F Unsolvable B C D

I J G H E F Unsolvable

I J
 Means-ends analysis
• All the above search strategies reason either forward or backward.
• However, often a mixture of forward and backward is needed.
• --So solve major parts of the problem first. And then go back and solve these
small problems to glue by pieces together.
• --centers around detection of differences between the current and goal state.
• --When detected reduce the difference by choosing the appropriate
operator.
• --But operator may not be applicable on current state.
• --So setup a sub problem of getting on to a state in which it can be applied.
 MEA
• This backward chaining in which operators are selected and subgoals are
set up to establish precondition of operators is called operator
subgoaling.
• MEA process applied recursively
• Each rule (operator) has
• LHS preconditions and RHS aspects of problem state changed.
• Difference table of rules and differences they can reduce.
• Problem for household robot: moving desk with 2 things on it from one room to
another.
• Main difference between start and goal state is location.
• Choose PUSH and CARRY
Move desk with 2 things on it to new room

Push Carry Walk Pickup Putdown Place

Move * *
object

Move *
robot
Clear *
object

Get object *
on object

Get arm
empty * *
Be holding
object *
Operator Preconditions Results

PUSH (obj, loc) at(robot,obj) at(obj, loc)

&large (obj) & at (robot, loc)
&clear (obj) &
arm empty
CARRY (obj, loc) at(robot, obj) &Small at(obj, loc) &at(robot,
(obj) loc)

WALK(loc) none At(robot, loc)

PICKUP(obj) At(robot, obj) Holding(obj)

PUTDOWN(obj) Holding(obj) Not holding (obj)

PLACE(obj1, obj2) At(robot,obj2) & holding on(obj1, obj2)
(obj1)
CARRY: preconditions cannot be met
PUSH: 4 preconditions
WALK to object, clear desk using PICKUP and PLACE. After PUSH
objects not on desk. Must WALK to collect them and put on table using
PICKUP and CARRY
Means-Ends Analysis
• 1. Compare CURRENT to GOAL. If no differences, return.
• 2. Otherwise select most important difference and reduce it by doing the following until
success or failure is indicated.
(a) Select an as yet untried operator O that is applicable to the current difference. If there are no
such operators then signal failure.
(b) Attempt to apply O to the current state. Generate descriptions of two states O-START a state in
which O’s preconditions are satisfied and O-RESULT, the state that would result if O were
applied in O-START.
(c) If (FIRST-PART MEA (CURRENT,O-START) AND (LAST-PART MEA (O-RESULT, GOAL) are successful
then signal success.
• Example MEA