Heuristic Search

Outline

• Generate-and-test
• Hill climbing
• Best-first search
• Problem reduction
• Constraint satisfaction

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

3
 Generate-and-Test

• Acceptable for simple problems.

• Inefficient for problems with large space.

4
 Generate-and-Test

• Exhaustive generate-and-test
• Heuristic generate-and-test
Does 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.

 Systematic (Exhaustive) generate-and-test is

implemented as a DFS tree with backtracking.
5
 Hill Climbing

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

6
 Hill Climbing

• Generate-and-test + direction to move.

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

7
 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

8
 Simple Hill Climbing

• Evaluation function as a way to inject task-specific

knowledge into the control process.

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

10
 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. 11
 Hill Climbing: Disadvantages

Local maximum
A state that is better than all of its neighbours, but not
better than some other states far away.

12
 Hill Climbing: Disadvantages

Plateau
A flat area of the search space in which all neighbouring
states have the same value.

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

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

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

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

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

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

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

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

21
 Best-First Search (OR Graphs)

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

23
 Best-First Search
Algorithm
1. Put the initial node on a list OPEN.
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 do:
new  evaluate it, add it to OPEN, record its parent.
generated before  change parent if this new path is
better than the previous one, update the cost of getting
to this node and to any successors that this node may
already have.

24
 Best-First Search

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

25
 Best-First Search

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

26
 Best-First Search

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

27
 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

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

29
 Best-First Search

Algorithm A*:

• Modified form of Best-First Search

• Used especially on path problems where the cost of a

path is the sum of the cost of the moves.

• Finds a minimal cost path joining the open node and a

goal node in a state space graph using Best-First
Search

30
 Algorithm A*
• Evaluation Function (Future)– how far a particular
node is from the goal.
• Cost Function (Past) – how much resources have been
spent in reaching a particular node from the start.
f '(n) = g(n) + h '(n)

f ' = fitness number for a node.

h' = cost of the cheapest path from node n to a

goal state.
g = actual cost from the open node s to the current
node n along the cheapest path found so far by
the Best-First Search
31
 Algorithm A*
Algorithm
1. Put the initial node on a list OPEN.
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 do:
new  evaluate it, add it to OPEN, record
its parent.
generated before  change parent if this
new path is better than the previous one,
update the cost of getting to this
node and to any successors that this node
may already have. 32
 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)

33
AND-OR Graphs

34
Problem Reduction

35
 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

36
 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

37
 Constraint Satisfaction

• Many AI problems can be viewed as problems of

constraint satisfaction in which the goal is to discover
some problem state that satisfies a given set of
constraints.
SEND
Cryptarithmetic puzzle:
 MORE
MONEY

38
 Constraint Satisfaction

• As compared with a straightforward search procedure,

viewing a problem as one of constraint satisfaction can
reduce substantially the amount of search.

39
 Constraint Satisfaction

Constraint Satisfaction is a search procedure that -

• Operates in a space of constraint sets.

• Initial state contains the original constraints given in the

problem.

• A goal state is any state that has been constrained

“enough”.

40
 Constraint Satisfaction

Two-step process:
1. Constraints are discovered and propagated as far as possible
throughout the system.
2. If there is still not a solution, then search begins. A guess
about something is made and new constraints are added.

41
 Initial state:

M=1
•No two letters have
S = 8 or 9 SEND
the same value. O=0 
• The sum of the digits N=E+1 MORE
C2 = 1
must be as shown.
N+R>8
E9 MONEY
E=2
N=3
R = 8 or 9
2 + D = Y or 2 + D = 10 + Y

C1 = 0 C1 = 1

2+D=Y 2 + D = 10 + Y
N + R = 10 + E D=8+Y
R=9 D = 8 or 9
S =8
D=8 D=9
Y=0 Y=1
42
Cryptarithmetic

43
Cryptarithmetic

44
45
Constraint Satisfaction

46
 Constraint Satisfaction

Two kinds of rules:

1. Rules that define valid constraint propagation.
2. Rules that suggest guesses when necessary.

47
 Search Techniques in Game Playing
Game playing is one of the most practical direct applications
of the search problem-solving paradigm.

Reasons why games appeared to be fit domain in which to

explore machine intelligence:

 They provide structured tasks with which it was very easy

to measure success or failure.

 They did not obviously require a large amount of knowledge

. They allowed solutions by straightforward search from
starting state to a wining position.
48
 Game Playing
• To find solution to a problem using search procedure is to
generate moves through the problem space until a goal state
is reached.

• In the context of game playing, a goal state is one in which we

win.

• Unfortunately for game like Chess, it in not usually possible,

even with a good plausible move generator, to search until a
goal state is found.

• The depth of the resulting tree or graph is too much and its
branching factor too high 49
 Game Playing

• One-person game or puzzle - A* Algorithm

• Two-person games like Chess - MiniMax Procedure

• (Reference : Artificial Intelligence and Intelligent Systems,

N.P. Padhy, Oxford University Press, 2005)

50
 Knowledge Representation

51