Uninformed Search 2 Today’s Class

Informed Search •  Rest of blind search “An informed search

strategy—one that uses
AI Class 5 (Ch. 3.5-3.7) •  Heuristic search
problem specific
•  Best-first search knowledge… can find
•  Greedy search solutions more efficiently
•  Beam search then an uninformed
•  A, A* strategy.”
•  Examples
– R&N pg. 92
•  Memory-conserving
variations of A*
Based on slides by Dr. Marie desJardin. Some material also adapted from slides by Dr.
Matuszek @ Villanova University, which are based on Hwee Tou Ng at Berkeley, which
•  Heuristic functions
Dr. Cynthia Matuszek – CMSC 671 are based on Russell at Berkeley. Some diagrams are based on AIMA.
2

Things to Differentiate
Questions? •  Goal testing
•  Expanding
•  Generating

3
4

Blind Search (Redux) “Satisficing”

•  Wikipedia: “Satisficing is … searching until
•  Last time: •  This time: an acceptability threshold is met”
• Bread-first • Iterative •  Contrast with optimality Another piece of
deepening •  Satisficable problems do not get more problem
• Depth-first benefit from finding an optimal solution definition
• Uniform-cost • Bidirectional •  Ex: You have an A in the class. Studying for four hours will
get you a 95 on the final. Studying for four more (eight
• Holy Grail hours) will get you a 99 on the final. What to do?
Search •  A combination of satisfy and suffice
•  Introduced by Herbert A. Simon in 1956

5 6

1
 Depth-First Iterative Deepening (DFID) Depth-First Iterative Deepening (DFID)

1.  DFS to depth 0 (i.e., treat start node as until solution found do: 1.  DFS to depth 0 (i.e., treat start node as until solution found do:
having no successors) DFS with depth cutoff c; having no successors) DFS with depth cutoff c;
2.  Iff no solution found, do DFS to depth 1 c = c+1 2.  Iff no solution found, do DFS to depth 1 c = c+1

•  Complete •  Complete

•  Optimal/Admissible if all operators have the same cost •  Optimal/Admissible if all operators have the same cost
•  Otherwise, not optimal, but guarantees finding solution of shortest length
The key: at every stage,
•  Otherwise, not optimal, but guarantees finding solution of shortest length

•  Time complexity is a little worse than BFS or DFS because nodes near
the top of the search tree are generated multiple times
throw away work from
•  Time complexity is a little worse than BFS or DFS because nodes near
the top of the search tree are generated multiple times

•  Because most nodes are near the bottom of a tree, worst case time • 
previous stages (or you
Because most nodes are near the bottom of a tree, worst case time
complexity is still exponential, O(bd) don’t save
complexity is still exponential, O(bd) anything!)

7 8

Iterative deepening search (c=1) Iterative deepening search (c=2)

Iterative deepening search (c=3) Depth-First Iterative Deepening

•  If branching factor is b and solution is at depth d, then nodes
at depth d are generated once, nodes at depth d-1 are
generated twice, etc.
•  Hence bd + 2b(d-1) + ... + db ≤ bd / (1 - 1/b)2 = O(bd).
•  If b=4, then worst case is 1.78 * 4d, i.e., 78% more nodes searched than
exist at depth d (in the worst case).

•  Linear space complexity, O(bd), like DFS

•  Has advantage of both BFS (completeness) and DFS
(limited space, finds longer paths more quickly)
•  Generally preferred for large state spaces where solution
depth is unknown

12

2
 S

Depth-First Search 3 8
Example for Illustrating Search Strategies 1
A B C
3
7 15 20 5
D E G
S Expanded node Nodes list
8 { S0 }
3 1 S0 { A3 B1 C8 }
A B C A3 { D6 E10 G18 B1 C8 }
3 D6 { E10 G18 B1 C8 }
15
7 20 5 E10 { G18 B1 C8 }
G18 { B1 C8 }
D E G Solution path found is S A G, cost 18
Number of nodes expanded (including goal node) = 5

13 14

S S

Depth-First Search Breadth-First Search

3 1 8 3 1 8

A B C A B C
3 3
7 15 20 7 15 20
5 5
D E G Expanded node Nodes list D E G
Expanded node Nodes list { S0 }
{ S0 } S0 { A3 B1 C8 }
S0 { A3 B1 C8 } A3 { B1 C8 D6 E10 G18 }
A3We won’t go through these in
{ D6 E10 G18 B1 C8 } B1 { C8 D6 E10 G18 G21 }

D6 { E10 G18 B1 C8 } C8 { D6 E10 G18 G21 G13 }

E10
detail, but please make sure
{ G18 B1 C8 } D6 { E10 G18 G21 G13 }

G18 you understand

{ B1 C8 } them. E10 { G18 G21 G13 }
G18 { G21 G13 }
Solution path found is S A G, cost 18
Solution path found is S A G , cost 18
Number of nodes expanded (including goal node) = 5
Number of nodes expanded (including goal node) = 7
15 16

Uniform-Cost Search How they Perform

3 1 8

A B C
3
7 15 20 5
Expanded node Nodes list D E •  Depth-First Search:
G
{ S0 } S
•  Expanded nodes: S A D E G
•  Solution found: S A G (cost 18) 3 1 8
S0 { B1 A3 C8 }
B1 { A3 C8 G21 } •  Breadth-First Search: A B C
A3 { D6 C8 E10 G18 G21 } •  Expanded nodes: S A B C D E G 3 15
7 20
•  Solution found: S A G (cost 18) 5
D6 { C8 E10 G18 G1 }
D E G
C8 { E10 G13 G18 G21 } •  Uniform-Cost Search:
•  Expanded nodes: S A D B C E G
E10 { G13 G18 G21 }
•  Solution found: S C G (cost 13)
G13 { G18 G21 } This is the only uninformed search that worries about costs.
Solution path found is S C G, cost 13
•  Iterative-Deepening Search:
Number of nodes expanded (including goal node) = 7 •  nodes expanded: S S A B C S A D E G
•  Solution found: S A G (cost 18)
17

3
 Bi-directional Search Bi-directional Search
•  Alternate searching from •  Alternate searching from
•  start state à goal •  start state à goal
•  goal state à start •  goal state à start

•  Stop when the frontiers intersect. •  Stop when the frontiers intersect.
Thought problems: What’s a real-
•  Works well only when there are •  Works well only when there are
unique start and goal states world
unique start problem where
and goal states you can’t
•  Requires ability to generate •  generate
Requires ability predecessors?
to generate
“predecessor” states. “predecessor” states.
•  Can (sometimes) find a solution fast •  Can (sometimes) find a solution fast

19 20

Comparing Search Strategies Avoiding Repeated States

•  Ways to reduce size of state space (with increasing
computational costs)
•  In increasing order of effectiveness:

1.  Do not return to the state you just came from.

2.  Do not create paths with cycles in them.
3.  Do not generate any state that was ever created before.

•  Effect depends on frequency of loops in state space.

21 22

S
A State Space that Generates an
Holy Grail Search 3 1 8

Exponentially Growing Search Space 3

A B C
7 15 20 5
Expanded node Nodes list D E G
{ S0 }
S0 {C8 A3 B1 }
C8 { G13 A3 B1 }
G13 { A3 B1 }

Solution path found is S C G, cost 13 (optimal)

Number of nodes expanded (including goal node) = 3
(minimum possible!)
23 24

4
 Holy Grail Search
Why not go straight to the solution, without
Informed Search
any wasted detours off to the side?

“An informed search strategy—one that

<foreshadowing> If only we knew where
uses problem specific knowledge… can
we were headed… </foreshadowing>
find solutions more efficiently then an
uninformed strategy.” – R&N pg. 92

27
25

Weak vs. Strong Methods Heuristic

•  Weak methods: Free On-line Dictionary of Computing*
•  Extremely general, not tailored to a specific situation 1.  A rule of thumb, simplification, or educated guess
•  Examples 2.  Reduces, limits, or guides search in particular domains
•  Subgoaling: split a large problem into several smaller ones that can 3.  Does not guarantee feasible solutions; often used with no
be solved one at a time. theoretical guarantee
•  Space splitting: try to list possible solutions to a problem, then try
to rule out classes of these possibilities WordNet (r) 1.6*
•  Means-ends analysis: consider current situation and goal, then
look for ways to shrink the differences between the two 1.  Commonsense rule (or set of rules) intended to increase
the probability of solving some problem
•  Called “weak” methods because they do not take
advantage of more powerful domain-specific heuristics

28 29 *Heavily edited for clarity

Heuristic Search Heuristic Search

•  Uninformed search is generic •  Romania: Aradà Bucharest (for example)
•  Node selection depends only on shape of tree and node
expansion strategy.

•  Sometimes domain knowledge à Better decision

•  Knowledge about the specific problem

30 31

5
 Heuristic Search Heuristics Examples
•  8-puzzle:
•  Romania:
•  # of tiles in wrong place
•  Eyeballing it à certain cities first
•  They “look closer” to where we are going •  8-puzzle (better):
•  Sum of distances from goal
•  Can domain
•  Captures distance and
knowledge be number of nodes
captured in a
heuristic? •  Romania:
•  Straight-line distance from
S

start node to Bucharest

G

•  Captures “closer to Bucharest”

32 33

Heuristic Function Example Search Space Revisited

start state
•  All domain-specific knowledge is encoded in
heuristic function h
S 8 arc cost
•  h is some estimate of how desirable a move is 1 8
5
•  How “close” (we think, maybe) it gets us to our goal
A 8 B 4 C 3
•  Usually:
3 9 h value
•  h(n) ≥ 0: for all nodes n 7 4 5
•  h(n) = 0: n is a goal node
•  h(n) = ∞: n is a dead end (no goal can be reached from n)
D ∞ E ∞ G 0

34 35 goal state

Domain Information Is It A Heuristic?

•  Informed methods add domain-specific information! •  A heuristic function is:
•  Goal: select the best path to continue searching • An estimate of how close we are to a goal
•  Define h(n) to estimate the “goodness” of node n •  We don’t assume perfect knowledge
•  h(n) = estimated cost (or distance) of minimal cost path from •  That would be holy grail search
n to a goal state •  The estimate can be wrong
• Based on domain-specific information
• Computable from the current state description

36 37

6
 Straight Lines to Budapest (km) Admissible Heuristics
hSLD(n)
•  Admissible heuristics never overestimate cost
•  They are optimistic – think goal is closer than it is
•  h(n) ≤ h*(n)
•  where h*(n) is true cost to reach goal from n
•  hLSD(Lugoj) = 244
•  Can there be a shorter path?

•  Using admissible heuristics guarantees that the first

solution found will be optimal

38 R&N pg. 68, 93 39

Best-First Search Best-First Search (more)

•  A generic way of referring to informed methods •  Order nodes on the list by
•  Increasing value of f (n)
•  Use an evaluation function f (n) for each node
à estimate of “desirability” •  Expand most desirable unexpanded node
•  f (n) incorporates domain-specific information •  Implementation:
•  Order nodes in frontier in decreasing order of desirability
•  Different f (n) à Different searches
•  Special cases:
•  Greedy best-first search
•  A* search

40 41

Greedy Best-First Search Greedy Best-First Search

•  Idea: always choose “closest node” to goal •  Admissible?
•  Most likely to lead to a solution quickly a a
•  Why not?
•  So, evaluate nodes based only h=2 b g h=4 h=2 b g h=4
on heuristic function •  Example:
•  f(n) = h(n)
h=1 c h h=1 •  Greedy search will find: h=1 c h h=1
•  Sort nodes by increasing aàbàcàdàeàg ; cost = 5
values of f h=1 d h=0 h=1 d h=0
i •  Optimal solution: i
•  Select node believed to be closest aàgàhài ; cost = 3
to a goal node (hence “greedy”) h=1 e h=1 e
•  That is, select node with smallest f value •  Not complete (why?)
h=0 g h=0 g
42 43

7
Straight Lines to Budapest (km) Greedy Best-First Search: Ex. 1
hSLD(n) What can we
say about the
search space?

224
G
242

44 R&N pg. 68, 93

Greedy Best-First Search: Ex. 2 Greedy Best-First Search: Ex. 2

hSLD(n)

46 47

Greedy Best-First Search: Ex. 2 Greedy Best-First Search: Ex. 2

48 49

8
 Beam Search Quick Terminology Reminders
•  Use an evaluation function f (n) = h(n), but the •  What is f (n)? •  What is h*(n)?
maximum size of the nodes list is k, a fixed constant •  An evaluation function •  A heuristic function that
that gives… gives the…
•  Only keeps k best nodes as candidates for expansion, •  A cost estimate of...
•  True cost to reach goal from n
and throws the rest away •  The distance from n to G
•  Why don’t we just use that?
•  More space-efficient than greedy search, but may •  What is h(n)?
•  What is g(n)?
throw away a node that is on a solution path •  A heuristic function
that… •  The path cost of getting from
•  Not complete •  Encodes domain S to n
knowledge about... •  describes the “already spent”
•  Not admissible •  The search space costs of the current search

50

Algorithm A* A* Search
•  Use evaluation function f (n) = g(n) + h(n) •  Idea: Evaluate nodes by combining g(n), the cost of
reaching the node, with h(n), the cost of getting from
•  g(n) = minimal-cost path from any S to state n the node to the goal.
•  That is, the cost of getting to the node so far 0 S cost
•  Evaluation function: 8 h
•  Ranks nodes on frontier by estimated cost of solution
f(n) = g(n) + h(n)
•  From start node, through given node, to goal •  g(n) = cost so far to reach n
8 C 3
•  h(n) = estimated cost from n to goal 5
•  Not complete if h(n) can = ∞ g
•  f(n) = estimated total cost of path
through n to goal 9 G 0

59 60

A* Search A* Example 1
•  Avoid expanding paths that are already expensive
•  Combines costs-so-far with expected-costs

•  A* is complete iff 0 S cost

•  Branching factor is finite 8 h

•  Every operator has a fixed positive cost

8 C 3
•  A* is admissible iff
5 g
•  h(n) is admissible
9 G 0

61 62

9
A* Example 1 A* Example 1

63 64

A* Example 1 A* Example 1

65 66

A* Example 1 Algorithm A*
•  Algorithm A with constraint that h(n) ≤ h*(n)
•  h*(n) = true cost of the minimal cost path from n to a goal.

•  Therefore, h(n) is an underestimate of the distance to the

goal
•  h() is admissible when h(n) ≤ h*(n)
•  Guarantees optimality

•  A* is complete whenever the branching factor is finite,

and every operator has a fixed positive cost
•  A* is admissible

67 68

10
Example Search Space Revisited Example
start state n g(n) h(n) f (n) h*(n)
parent pointer 0 S 8
S 0 8 8 9 cost

0 S 8 arc cost A1 8 9 9 1 5 8 h

B5 4 9 4 1 A 8 5 B 4 8 C 3
1 5 8 C8 3 11 5 3 9
7 4 5
D4 ∞ ∞ ∞ g
4 D ∞ 8 E ∞ 9 G 0
1 A 8 E8 ∞ ∞ ∞
5 B 4 8 C 3 G9 0 9 0
3 9 h value
7 4 5 •  h*(n) is the (hypothetical) perfect heuristic.
g value
•  Since h(n) ≤ h*(n) for all n, h is admissible
4 D ∞ 8 E ∞ 9 G 0
•  Optimal path = S B G with cost 9.
69 goal state 70

Greedy Search A* Search 0 S 8 cost

1 5 8 h
0 S 8 cost
f (n) = h(n) 1 5 8 h f (n) = g(n) + h(n) 1 A 8 5 B 4 8 C 3
3 9
Node Node
 1 A 8 node exp. nodes list 7 4
5 B 4 8 C 3 5 g
expanded list 3 9
7 4 { S(8) } 4 D ∞ 8 E ∞ 9 G 0
5 g
{ S(8) } 4 D ∞ 8 E ∞ 9 G 0 S { A(9) B(9) C(11) }
S { C(3) B(4) A(8) } A { B(9) G(10) C(11) D(∞) E(∞) }
C { G(0) B(4) A(8) } B { G(9) G(10) C(11) D(inf) E(∞) }
G { B(4) A(8) }
G { C(11) D(∞) E(∞) }
•  Solution path found is S C G, 3 nodes expanded.
•  Solution path found is S B G, 4 nodes expanded..
•  Fast!! But NOT optimal.
•  Still pretty fast, and optimal
71 72

Proof of the Optimality of A* Admissible heuristics

•  Assume that A* has selected G2, a goal state with a E.g., for the 8-puzzle:
suboptimal solution (g(G2) > f *). •  h1(n) = number of misplaced tiles
•  We show that this is impossible. •  h2(n) = total Manhattan distance
•  Choose a node n on the optimal path to G. (i.e., # of squares each tile is
•  Because h(n) is admissible, f (n) ≤ f *. from desired location) Start
•  If we choose G2 instead of n for expansion, f(G2) ≤ f(n).
•  This implies f (G2) ≤ f *.
•  G2 is a goal state: h(G2) = 0, f (G2) = g(G2). •  h1(S) = ?
•  Therefore g(G2) ≤ f * •  h2(S) = ?
•  Contradiction.
Goal
73 74

11
 Admissible heuristics Dealing with Hard Problems
E.g., for the 8-puzzle: •  For large problems, A* often requires too much space.
•  h1(n) = number of misplaced tiles •  Two variations conserve memory: IDA* and SMA*
•  h2(n) = total Manhattan distance •  IDA* – iterative deepening A*
(i.e., # of squares each tile is •  uses successive iteration with growing limits on f. For example,
from desired location) Start •  A* but don’t consider any node n where f (n) > 10
•  A* but don’t consider any node n where f (n) > 20
•  A* but don’t consider any node n where f (n) > 30, ...

•  h1(S) = 8 •  SMA* – Simplified Memory-Bounded A*

•  uses a queue of restricted size to limit memory use.
•  h2(S) = 3+1+2+2+2+3+3+2 = 18 •  throws away the “oldest” worst solution.
Goal
75 76

What’s a Good Heuristic? What’s a Good Heuristic? (2)

•  If h1(n) < h2(n) ≤ h*(n) for all n, then: 3. Use statistical estimates to compute h
•  Both are admissible •  May lose admissibility
•  h2 is strictly better than (dominates) h1.

•  How do we find one? 4. Identify good features, then use a learning

algorithm to find a heuristic function
1. Relaxing the problem: •  Also may lose admissibility
•  Remove constraints to create a (much) easier problem
•  Use the solution cost for this problem as the heuristic function •  Why are these a good idea, then?
•  Machine learning can give you answers you don’t “think of”
2. Combining heuristics:
•  Take the max of several admissible heuristics •  Can be applied to new puzzles without human intervention
•  Still have an admissible heuristic, and it’s better! •  Often work

77 78

Some Examples of Heuristics? Summary: Informed Search

•  8-puzzle? •  Best-first search: general search where the minimum-cost
•  Manhattan distance nodes (according to some measure) are expanded first.
•  Greedy search: uses minimal estimated cost h(n) to the
•  Driving directions? goal state as measure. Reduces search time but, is neither
•  Straight line distance complete nor optimal.
•  Crossword puzzle? •  A* search: combines UCS and greedy search
•  f (n) = g(n) + h(n)
•  Making a medical diagnosis? •  A* is complete and optimal, but space complexity is high.
•  Time complexity depends on the quality of the heuristic function.

•  IDA* and SMA* reduce the memory requirements of A*.

79 80

12
 In-Class 8
In-class Exercise: Creating Heuristics S
Remove 5 Exercise 8
8-Puzzle Boat Problems Sticks 3 1
arc 4
cabbage
sheep cost A 8 B C 3
wolf
3 15
7 20 5 h value

Route Planning
D ∞ E ∞ G 0
N-Queens Water Jug Problem
Apply the following to search this space. At each search step, show:
the current node being expanded, g(n) (path cost so far), h(n) (heuristic
estimate), f (n) (evaluation function), and h*(n) (true goal distance).
5
2 Depth-first search Breadth-first search A* search
Uniform-cost search Greedy search
81

13