Heuristic Search

Heuristic Search
The search techniques we have seen so far...

• Breadth first search

• Uniform cost search
• Depth first search uninformed search
• Depth limited search blind search
• Iterative Deepening
• Bi-directional Search

...are all too slow for most real world problems

8-Puzzle
Solution in Node 46
 Solution in Node 31
8-Puzzle
Sometimes we can tell that some states
appear better than others...
7 8 4 1 2 3
3 5 1 4 5 6
6 2 7 8
...we can use this knowledge of the relative merit of states to guide search

Heuristic Search (informed search)

A Heuristic is a function that, when applied to a state, returns a
number that is an estimate of the merit of the state, with respect to
the goal.

In other words, the heuristic tells us approximately how far the state
is from the goal state*.

Note we said “approximately”. Heuristics might underestimate or

overestimate the merit of a state. But for reasons which we will see,
heuristics that only underestimate are very desirable, and are called
admissible.
*I.e Smaller numbers are better
 Heuristics for 8-puzzle I
1 2 3
Current
State 4 5 6
7 8 11 22 33
•The number of
misplaced tiles 44 55 66
1 2 3 77 8
(not including Goal 8
the blank) State 4 5 6
7 8
N N N
In this case, only “8” is misplaced, so the heuristic
function evaluates to 1. N N N
In other words, the heuristic is telling us, that it thinks a N Y
solution might be available in just 1 more move.

Notation: h(n) h(current state) = 1

 Heuristics for 8-puzzle II
3 2 8 3 3
Current
State 4 5 6 2 spaces
7 1
•The Manhattan
Distance (not 8
including the 1 2 3
blank) Goal 3 spaces
State 4 5 6
8
7 8
1
In this case, only the “3”, “8” and “1” tiles are
misplaced, by 2, 3, and 3 squares respectively, so 3 spaces
the heuristic function evaluates to 8. 1
In other words, the heuristic is telling us, that it thinks a
solution is available in just 8 more moves. Total 8

Notation: h(n) h(current state) = 8

 Heuristic Search
 Heuristic
 heuriskein (Greek word)-to discover
 original: eureka
-heurika (I have found): Archimedes uttering when determining the purity of gold
 Heuristic Function
 a way to inform the search about the direction to a goal.
 provides an informed way to guess which neighbor of a node will lead
to a goal.
 Pros
 Like a tour guide
 Good to the extent that they point in generally interesting direction
 Improve the quality of the paths that are explored
 Using good heuristic, we can hope to get good solutions to hard
problem
 It is possible to construct special-purpose heuristics that exploit
domain-specific knowledge to solve particular problems
 Heuristic Search
 A heuristic is a method that
-might not always find the best solution
-but is guaranteed to find a good solution in reasonable time.
 By sacrificing completeness it increases efficiency.
 Useful in solving tough problems which
– could not be solved any other way.
– solutions take an infinite time or very long time to
compute.
 The classic example of heuristic search methods is the
travelling salesman problem.
 Heuristic Search
Traveling Salesman Problem
1. Arbitrarily select a starting city
2. To select the next city, look at all cities not yet
visited,
-Select the one closest to the current city.
-Go to it next
3. Repeat step 2 until all cities have been visited
 Heuristic Function
 A heuristic function is a function that maps from problem state
descriptions to measure of desirability, usually represented as numbers
-Which aspects of the problem state are considered?
-How those aspects are evaluated?
-The weights given to individual aspects are chosen in such a way that the
value of the heuristic function at a given node in the search process gives as
good an estimate as possible of whether that node is on the desired path to a
solution
 Well-designed heuristic functions can play an important part in
efficiently guiding a search process toward a solution
 The purpose of a heuristic function is to guide the search process in
the most profitable direction by suggesting which path to follow first
when more than one is available
 The more accurately the heuristic function estimates the true merits of
each node in the search tree/graph, the more direct the solution process
 Heuristic Search
 Generate –and- test
 Hill Climbing
o Simple Hill Climbing
o Steepest-Ascent Hill Climbing
o Simulated Annealing
 Best-First Search
o OR Graphs
o A* Algorithm
o Greedy Best-First Search
 Problem Reduction
o AND-OR Graphs
o AO* Algorithm
 Constraint Satisfaction
 Means-ends Analysis
 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.
Acceptable for simple problems.
Inefficient for problems with large space.
14
 Hill Climbing
A variant of generate-and-test in which feedback
from the test procedure is used to help the generator
decide which direction to move in the search space.
Searching for a goal state = Climbing to the top of a
hill
Generate-and-test + direction to move.
Heuristic function to estimate how close a given state
is to a goal state.
15
 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

16
 Steepest-Ascent Hill Climbing
(Gradient Search)
• Considers all the moves from the current
state.

• Selects the best one as the next state.

17
 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.
18
 Hill Climbing: Disadvantages
Local maximum
A state that is better than all of its
neighbours, but not better than some other
states far away.

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

20
 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.

21
 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.
22
 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.

23
Hill Climbing: Disadvantages
Start Goal
A D
D C
C B
B A
Blocks World

24
 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.
25
Hill Climbing: Disadvantages
0 A 2

D D
C C
B B A

26
Hill Climbing: Disadvantages
2
D
C
B A

A 0
0
D
C C D C 0

B B A B A D

27
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. 28
Hill Climbing: Disadvantages
D -3
C
B A

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

B B A B A D

29
 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.

30
 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.
31
 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.

32
 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.

33
NEXT CLASS
 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.
35
 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
36
 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.

37
 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

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

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

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

41
 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
42
 Best-First Search
• Algorithm A* (Hart et al., 1968):
f(n) = g(n) + h(n)

h(n) = cost of the cheapest path from node

n to a goal state.
g(n) = cost of the cheapest path from the
initial state to node n.
43
 Best-First Search
• Algorithm A*:
f*(n) = g*(n) + h*(n)

h*(n) (heuristic factor) = estimate of h(n).

g*(n) (depth factor) = approximation of

g(n) found by A* so far.
44
OR-Graph
 Problem Reduction
Goal: Acquire TV set

Goal: Steal TV set Goal: Earn some money Goal: Buy TV set

AND-OR Graphs

Algorithm AO* (Martelli & Montanari 1973, Nilsson 1980)

46
 Problem Reduction: AO*
A A 6
5 9
B C D
3 4 5

A 9 A 11
9 12
B C D 10 B 6 C D 10
3 4 4
E F G H E F
4 4 5 7 4 4

47
 Problem Reduction: AO*
A 11 A 14

B 13 C 10 B 13 C 15

D 5 E 6 F 3 D 5 E 6 F 3

G 5 G 10

Necessary backward propagation H 9

48
TO BE CONTINUE…