Heuristic Search

Chapter 3

Outline

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

2

Generate-and-Test

Algorithm

1. Generate a possible solution(either a particular point or a path).
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

• If the generation of possible solution is done systematically, then this procedure will find a solution eventually ,if one exists.(large problem space-”eventually” may be a very long time).
• Acceptable for simple problems.
• Inefficient for problems with large space.
• Example: DFS(solution must be generated before tested)
• British museum algorithm

4

Generate-and-Test

• Exhaustive generate-and-test.
• Heuristic generate-and-test: not consider paths that seem unlikely to lead to a solution.(DFS with backtracking)
• Plan generate-test:

− Create a list of candidates.

− Apply generate-and-test to that list.

5

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

​

​

​

6

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.

​

​

​

7

Hill Climbing

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

8

Hill Climbing

• Generate-and-test + direction to move.
• Heuristic function to estimate how close a given state is to a goal state.
• Hill climbing is often used when a good heuristic function is available for evaluating states but when no other useful knowledge is available. Example: downtown.

9

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

​

10

Simple Hill Climbing

• Key different between this algorithm and the one we gave for generate and test is the use of Evaluation function as a way to inject task-specific knowledge into the control process.
• Vague question: is one state better than another?

11

Simple Hill Climbing

Example: coloured blocks

​

Heuristic function: the sum of the number of different

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

​

​

​

12

Steepest-Ascent Hill Climbing (Gradient Search)

• Considers all the moves from the current state.
• Selects the best one as the next state.

13

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.

​

14

Hill Climbing: Disadvantages

Local maximum

A state that is better than all of its neighbours, but not

better than some other states far away.

15

Hill Climbing: Disadvantages

Plateau

A flat area of the search space in which all neighbouring

states have the same value.

16

Hill Climbing: Disadvantages

Ridge

Special kind of local maximum. It is an area of a search space that is better than surrounding areas and that itself has slope.

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.

17

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.

18

Hill Climbing: Disadvantages

• Hill climbing is a local method:

Decides what to do next by looking only at the “immediate” consequences of its choices rather than by exhaustively exploring all the consequences.

• Global information might be encoded in heuristic functions.

​

19

Hill Climbing: Disadvantages

20

B

C

D

A

B

C

Start

Goal

Blocks World

A

D

Hill Climbing: Disadvantages

21

B

C

D

A

B

C

Start

Goal

Blocks World

A

D

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.

0

4

Hill Climbing: Disadvantages

22

B

C

D

B

C

D

A

A

0

2

Hill Climbing: Disadvantages

23

B

C

D

A

B

C

D

A

B

C

D

A

0

0

0

B

C

D

A

2

Hill Climbing: Disadvantages

24

B

C

D

A

B

C

Start

Goal

Blocks World

A

D

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.

−6

6

Hill Climbing: Disadvantages

25

B

C

D

A

B

C

D

A

B

C

D

A

−6

−2

−1

B

C

D

A

−3

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.

​

26

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.

​

​

27

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.

28

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.

29

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.

​

30

Best-First Search

31

A

D

C

B

F

E

H

G

J

I

5

6

6

5

2

1

A

D

C

B

F

E

H

G

5

6

6

5

4

A

D

C

B

F

E

5

6

3

4

A

D

C

B

5

3

1

A

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.

​

32

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

​

33

Best-First Search

• Greedy search:

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

34

Best-First Search

• Uniform-cost search:

g(n) = cost of the cheapest path from the initial state to node n.

35

Best-First Search

• Greedy search:

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

Neither optimal nor complete

36

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

37

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.

38

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.

39

Problem Reduction

40

Goal: Acquire TV set

AND-OR Graphs

Goal: Steal TV set

Goal: Earn some money

Goal: Buy TV set

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

Problem Reduction: AO*

41

A

D

C

B

4

3

5

A

5

6

F

E

4

4

A

D

C

B

4

3

10

9

9

9

F

E

4

4

A

D

C

B

4

6

10

11

12

H

G

7

5

Problem Reduction: AO*

42

A

G

C

B

10

5

11

13

E

D

6

5

F

3

A

G

C

B

15

10

14

13

E

D

6

5

F

3

H

9

Necessary backward propagation

Constraint Satisfaction

• Many AI problems can be viewed as problems of constraint satisfaction.

​

Cryptarithmetic puzzle:

43

SEND

MORE

MONEY

+

Constraint Satisfaction

• As compared with a straightforard search procedure, viewing a problem as one of constraint satisfaction can reduce substantially the amount of search.

​

​

44

Constraint Satisfaction

• 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”.

​

​

45

Constraint Satisfaction

Two-step process:

1. Constraints are discovered and propagated as far as possible.

2. If there is still not a solution, then search begins, adding new constraints.

​

​

46

47

M = 1

S = 8 or 9

O = 0

N = E + 1

C2 = 1

N + R > 8

E ≠ 9

N = 3

R = 8 or 9

2 + D = Y or 2 + D = 10 + Y

2 + D = Y

N + R = 10 + E

R = 9

S =8

2 + D = 10 + Y

D = 8 + Y

D = 8 or 9

Y = 0

Y = 1

E = 2

C1 = 0

C1 = 1

D = 8

D = 9

Initial state:

• No two letters have

the same value.

• The sum of the digits

must be as shown.

SEND

MORE

MONEY

+

Constraint Satisfaction

Two kinds of rules:

1. Rules that define valid constraint propagation.

2. Rules that suggest guesses when necessary.

​

​

48

Homework

Exercises 1-14 (Chapter 3 – AI Rich & Knight)

​

Reading Algorithm A*

(http://en.wikipedia.org/wiki/A%2A_algorithm)

​

​

49