1 of 36

Informed Search

2 of 36

A* search example

Stages in a greedy best-first tree search for Bucharest with the straight-line distance heuristic hSLD. Nodes are labeled with their h-values.

Stages in an A^* search for Bucharest. Nodes are labeled with f = g +h. The

h values are the straight-line distances to Bucharest

3 of 36

A* search example

4 of 36

Comparing A* and greedy search

greedy search path 🡺 140 + 99 + 211 = 450

A* search path 🡺 140 + 80+ 97 + 101 = 418

5 of 36

A* search: another example

Assume h(n)=

6 of 36

A* search: another example

f(n) = g(n) + h(n)

7 of 36

8 of 36

Example

Uniform Cost Search

A^* Search

9 of 36

Example (A^*search)

10 of 36

Results on A*�

A heuristic is called admissible if it always under-estimates, that is we always have h(n)<=f*(n) where f*(n) denotes minimum distance to a goal state from n

For finite state spaces, A* always terminates

At any time before A* terminates, there exists in OPEN a state n that is an optimal path from s to a goal state with f(n) <= f*(s)

If there is a path from s to goal state, A* terminates (even when the state space is infinite)

11 of 36

Results on A*�

Algorithm A* is admissible, that is, if there is a path from s to a goal state, A* terminates by finding an optimal path.

If A1 and A2 are two versions of A* such that A2 is more informed than A1, then A1 expends at least as many states as does A2

If we are given two or more admissible heuristic we can take their max to get a stronger admissible heuristic.

12 of 36

B

A

C

E

D

H

I

G

K

L

Z

14

12

9

11

8

13

10

9

A* search another example

13 of 36

Admissible heuristics

A heuristic h(n) is admissible if for every node n,

h(n)≤ h^*(n), � h^*(n): true cost to reach the goal state from n

An admissible heuristic never overestimates the cost to reach the goal, i.e., it is optimistic
Example: h_SLD(n) (never overestimates the actual road distance)
Theorem: If h(n) is admissible, A^* using TREE-SEARCH is optimal

13

14 of 36

CONSISTENCY or MONOTONICITY

15 of 36

Consistent heuristics

A heuristic is consistent if for every node n, every successor n' of n generated by any action a,

h(n) ≤ c(n,a,n') + h(n')�

If h is consistent, we have

f(n') = g(n') + h(n')

= g(n) + c(n,a,n') + h(n')

≥ g(n) + h(n)

= f(n)�

i.e., f(n) is non-decreasing along any path.
Theorem: If h(n) is consistent, A* using GRAPH-SEARCH is optimal

15

16 of 36

Optimality of A^* (proof)

Suppose some suboptimal goal G₂ has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G.

f(G₂) = g(G₂) since h(G₂) = 0
g(G₂) > g(G) since G₂ is suboptimal
f(G) = g(G) since h(G) = 0
f(G₂) > f(G) from above

16

17 of 36

Optimality of A^* (proof)

Suppose some suboptimal goal G₂ has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G.

f(G₂) > f(G) from above
h(n) ≤ h*(n) since h is admissible
g(n) + h(n) ≤ g(n) + h^*(n)
f(n) ≤ f(G)

🡪 f(G₂) > f(n), and A^* will never select G₂ for expansion�

17

18 of 36

A* search example

Stages in a greedy best-first tree search for Bucharest with the straight-line distance heuristic hSLD. Nodes are labeled with their h-values.

Stages in an A^* search for Bucharest. Nodes are labeled with f = g +h. The

h values are the straight-line distances to Bucharest

19 of 36

Optimality of A^*

A^* expands nodes in order of increasing f value

Gradually adds "f-contours" of nodes
Contour i has all nodes with f=f_i, where f_i < f_i+1

19

Map of Romania showing contours at f = 380, f = 400, and f = 420, with Arad as the start state. Nodes inside a given contour have f-costs less than or equal to the

contour value.

20 of 36

Properties of A*

Complete? �Yes (unless there are infinitely many nodes with f ≤ f(G) )
Time?

Exponential

Space?

Keeps all nodes in memory

Optimal?

Yes

20

21 of 36

About Heuristics

Heuristics are intended to orient the search along promising paths
The time spent computing heuristics must be recovered by a better search
A heuristic function could consist of solving the problem; then it would perfectly guide the search
Deciding which node to expand is sometimes called meta-reasoning
Heuristics may not always look like numbers and may involve large amount of knowledge

21

22 of 36

Heuristic Accuracy

h(N) = 0 for all nodes is admissible and consistent. Hence, breadth-first and uniform-cost are specific A* !

Let h1 and h2 be two admissible and consistent heuristics such that for all nodes N: �h1(N) ≤ h2(N). �h2 is more informed (or more accurate) than h1.

h₂ dominates h₁

Claim 3: �Every node expanded by A* using h2 is also expanded by A* using h1.

22

23 of 36

Example of Evaluation Function

23

f(N) = (sum of distances of each tile to its goal)

+ 3 x (sum of score functions for each tile)

score function: for a non-central tile is 2 if it is

not followed by the correct tile in clockwise order

and 0 otherwise

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

N

goal

f(N) = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1

3x(2 + 2 + 2 + 2 + 2 + 0 + 2)

= 49

24 of 36

Heuristic Function

Function h(N) that estimates the cost of the cheapest path from node N to goal node.
Example: 8-puzzle

24

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

N

goal

h(N) = number of misplaced tiles� = 6

25 of 36

Heuristic Function

Function h(N) that estimates the cost of the cheapest path from node N to goal node.
Example: 8-puzzle

25

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

N

goal

h(N) = sum of the distances of

every tile to its goal position

= 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1

= 13

26 of 36

8-Puzzle

26

4

5

3

4

3

4

2

1

2

0

3

4

3

f(N) = h(N) = number of misplaced tiles

27 of 36

8-Puzzle

27

0+4

1+5

1+3

3+3

3+4

3+2

4+1

5+2

5+0

2+3

2+4

2+3

f(N) = g(N) + h(N) with h(N) = number of misplaced tiles

28 of 36

8-Puzzle

28

5

6

4

2

1

2

0

5

3

f(N) = h(N) = Σ distances of tiles to goal

29 of 36

Robot Navigation

29

h(N) = Straight-line distance to the goal

= [(X_g – X_N)² + (Y_g – Y_N)²]^1/2

X_N

Y_N

N

30 of 36

Robot navigation

30

Cost of one horizontal/vertical step = 1

Cost of one diagonal step = √2

h(N) = straight-line distance to the goal is admissible

31 of 36

Robot Navigation

31

32 of 36

Robot Navigation

32

0

2

1

5

8

7

3

4

7

6

7

6

3

2

8

6

4

5

2

3

6

5

2

4

3

5

4

6

5

6

4

5

f(N) = h(N), with h(N) = Distance to the goal

33 of 36

Robot Navigation

33

0

2

1

5

8

7

3

4

7

6

7

6

3

2

8

6

4

5

2

3

6

5

2

4

3

5

4

6

5

6

4

5

f(N) = h(N), with h(N) = Distance to the goal

7

0

34 of 36

Robot Navigation

34

f(N) = g(N)+h(N), with h(N) = Distance to goal

0

2

1

5

8

7

3

4

7

6

7

6

3

2

8

6

4

5

2

3

6

5

2

4

3

5

4

6

5

6

4

5

7+0

6+1

8+1

7+0

7+2

6+1

7+2

6+1

8+1

7+2

8+3

7+2

6+3

5+4

4+5

3+6

2+7

8+3

7+4

6+5

5+6

6+3

5+6

2+7

3+8

4+7

5+6

4+7

3+8

4+7

3+8

2+9

3+10

2+9

3+8

2+9

1+10

0+11

35 of 36

Robot Navigation

35

Cost of one horizontal/vertical step = 1

Cost of one diagonal step = √2

f(N) = g(N) + h(N), with h(N) = straight-line distance from N to goal

36 of 36

8-Puzzle

36

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

N

goal

h1(N) = number of misplaced tiles = 6

is admissible

h2(N) = sum of distances of each tile to goal = 13� is admissible

h3(N) = (sum of distances of each tile to goal)� + 3 x (sum of score functions for each tile) = 49� is not admissible