02-search-part2
Searching the State
Space
Part 2: Pruning, informed search, other strategies
1
The problem with cycles and multiple paths
There is an issue that affects all search strategies in the
framework of generic graph search:
The algorithm can expand multiple paths to the same node.
Can cause:
– Cycles (infinite search tree)
– Wasted computation
Solution:
We “prune” unnecessary branches of the search tree.
2
Pruning
Principle: Do not expand paths to nodes that have already been expanded.
Note: a node is expanded when the frontier returns a path ending in that node to the
generic search algorithm (and thus the algorithm expands that path by outgoing arcs).
Implementation:
• The frontier keeps track of expanded (aka “closed”) nodes.
• When trying to add a new path to the frontier, it is added only if another path to the same
end-node has not been already expanded, otherwise the new path is discarded (pruned).
• When asking for the next path to be returned by the frontier, a path is selected and
removed but it is returned only if the end-node has not been expanded before, otherwise
the path is discarded (pruned) and not returned. The selection and removal is repeated
until a path is returned (or the frontier becomes empty). If a path is returned, its end-
node will be remembered as an expanded node.
In frontier traces, every time a path is pruned (when trying to add or when asking for the
next path), we add an exclamation mark ‘!’ at the end of the line.
3
Example: LCFS with pruning
Trace LCFS with pruning on the following graph:
nodes = {S, A, B, G},
edge_list=[(S,A,3), (S,B,1), (B,A,1), (A,B,1), (A,G,5)],
starting_nodes = [S],
goal_nodes = {G}.
4
Answer:
# expanded={}
+ S,0
– S,0 # expanded={S}
+ SA,3
+ SB,1
– SB,1 # expanded={S,B}
+ SBA,2
– SBA,2 # expanded={S,B,A}
+ SBAB,3! # not added!
+ SBAG,7
– SA,3! # not returned!
– SBAG,7 # expanded={S,B,A,G}
How does LCFS behave?
LCFS explores increasing cost
contours.
The good:
– Finds an optimal solution.
The bad:
– Explores options in every
direction
– No information about goal
location
5
Search heuristic
Idea: don’t ignore information about the goal when selecting paths. Often
there is extra knowledge that can be used to guide the search: heuristics.
h(n) is an estimate of the cost of the shortest path from node n to a goal
node.
h needs to be efficient to compute.
h can be extended to paths: h(⟨n0,…,nk⟩) = h(nk).
h is said to be admissible if and only if:
• ∀n h(n) ≥ 0 [i.e. h is non-negative]; and
• there is no path from n to a goal node with cost less than h(n). In other
words h(n) is less than or equal to the actual optimal cost of getting
from n to a goal node. [Or equivalently h never over-estimates the cost.]
6
Example heuristic functions
• If the nodes are points on a Euclidean plane and the cost is the distance, h(n) can be the
straight-line distance from n to the closest goal.
• If the nodes are locations and cost is time, h(n) can be the straight-line distance to the closest
goal divided by the maximum possible speed.
• If the nodes are locations in a maze where the agent can move in four directions, h(n) can be
Manhattan distance.
• A heuristic function can be found by solving a simpler (less constrained) version of the
problem.
7
Example: Euclidean distance
8
Romania with step costs in km
Bucharest
Giurgiu
Urziceni
Hirsova
Eforie
Neamt
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Sibiu
Fagaras
Pitesti
Rimnicu Vilcea
Vaslui
Iasi
Straight!line distance
to Bucharest
0
160
242
161
77
151
241
366
193
178
253
329
80
199
244
380
226
234
374
98
Giurgiu
Urziceni
Hirsova
Eforie
Neamt
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Sibiu Fagaras
Pitesti
Vaslui
Iasi
Rimnicu Vilcea
Bucharest
71
75
118
111
70
75
120
151
140
99
80
97
101
211
138
146 85
90
98
142
92
87
86
B. Beckert: KI für IM – p.24
Best-first Search
• Idea: select the path whose end is closest to a goal according
to the heuristic function.
• Best-first search is a greedy strategy that selects a path on the
frontier with minimal h-value.
• It treats the frontier as a priority queue ordered by h.
• By exploring more “promising” paths first, in many instances, it
can find a solution faster than LCFS.
• Main drawback: does not guarantee finding an optimal
solution.
9
Best-first search: example
10
Romania with step costs in km
Bucharest
Giurgiu
Urziceni
Hirsova
Eforie
Neamt
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Sibiu
Fagaras
Pitesti
Rimnicu Vilcea
Vaslui
Iasi
Straight!line distance
to Bucharest
0
160
242
161
77
151
241
366
193
178
253
329
80
199
244
380
226
234
374
98
Giurgiu
Urziceni
Hirsova
Eforie
Neamt
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Sibiu Fagaras
Pitesti
Vaslui
Iasi
Rimnicu Vilcea
Bucharest
71
75
118
111
70
75
120
151
140
99
80
97
101
211
138
146 85
90
98
142
92
87
86
B. Beckert: KI für IM – p.24
stages of search tree and frontier
Example: tracing best-first search
• Trace the frontier when using the best-first
(greedy) search strategy for the following graph.
• The starting node is S and the goal node is G.
• Heuristic values are given next to each node.
• SA comes before SB.
11
Answer:
+ S,3
– S,3
+ SA,2
+ SB,1
– SB,1
+ SBG,0
– SBG,0
heuristic function
h(S) = 3
h(A) = 2
h(B) = 1
h(G) = 0
A* search strategy
Idea:
• Don’t be as wasteful as LCFS
• Don’t be as greedy as best-first search.
• Estimate the cost of paths as if they could be extended to reach a goal in the best possible way.
Evaluation function f(p) = cost(p) + h(n)
• p is a path, n is the last node on p
• cost(p) = cost of path p (This is the actual cost from the starting node to node n)
• h(n) = an estimate of cost from n to goal (This is an optimistic estimate to the closest goal node)
• f(p) = estimated total cost of path through p to goal
The frontier is a priority queue ordered by f(p).
12
Example: tracing A* search
• Trace the frontier when using the A* search
strategy for the following graph.
• The starting node is S and the goal node is G.
• Heuristic values are given next to each node.
• SA comes before SB.
13
Answer:
+ S,3 # 0 + 3 = 3
– S,3
+ SA,4 # 2 + 2 = 4
+ SB,3 # 2 + 1 = 3
– SB,3
+ SBG,5 # 5 + 0 = 5
– SA,4
+ SAG,4 # 4 + 0 = 4
– SAG,4
Note: This small example only show the inner working of A*. It
does not demonstrate its advantage over LCFS.
heuristic function
h(S) = 3
h(A) = 2
h(B) = 1
h(G) = 0
Example: tracing A* search
• Same example as the one before
just assume h(A) = 4 instead.
14
Answer:
+ S,3 # 0 + 3 = 3
– S,3
+ SA,6 # 2 + 4 = 6
+ SB,3 # 2 + 1 = 3
– SB,3
+ SBG,5 # 5 + 0 = 5
– SBG,5
Non-optimal solution! Why?
heuristic function
h(S) = 3
h(A) = 4
h(B) = 1
h(G) = 0
Properties of A*
• A* always finds an optimal solution (a solution with the lowest costs)
as long as:
– there is a solution;
– there is no pruning; and
– the heuristic function is admissible.
• Does it halt on every graph?
• How about time and space complexity?
• LCFS vs A* (in average):
15
A*: proof of optimality
When using A* (without pruning) the first path p from a starting node to a goal node that is selected
and removed from the frontier has the lowest cost.
Sketch of proof:
• Suppose to the contrary that there is another path from one of the starting nodes to a goal node
with a lower cost.
• There must be a path p’ on the frontier such that one of its continuations leads to the goal with a
lower overall cost than p.
• Since p was removed before p’:
• Let c be any continuation of p’ that goes to a goal node; that is, we have a path p’c from a start
node to a goal node. Since h is admissible, we have:
• Thus:
f(p) ≤ f(p′ ) ⟹ cost(p) + h(p) ≤ cost(p′ ) + h(p′ ) ⟹ cost(p) ≤ cost(p′ ) + h(p′ )
cost(p′ c) = cost(p′ ) + cost(c) ≥ cost(p′ ) + h(p′ )
cost(p) ≤ cost(p′ ) + h(p′ ) ≤ cost(p′ ) + cost(c) = cost(p′ c)
16
Effect of pruning on A*
Trace the frontier in A* search for the following graph,
with and without pruning.
nodes={s, a, b, g},
estimates = {s:7, a:2, b:6, g:0},
edge_list=[(s,a,3), (s,b,1),
(b,a,1), (a,g,5)],
starting_nodes = [s],
goal_nodes = {g}.
17
s
a
b
g
h(s) = 7
h(a) = 2
h(g) = 0
h(b) = 6
3
1
1
5
Answer without pruning
+ S, 7
– S, 7
+ SA, 5
+ SB, 7
– SA, 5
+ SAG, 8
– SB, 7
+ SBA, 4
– SBA, 4
+ SBAG, 7
– SBAG, 7
Answer with pruning
# expanded={}
+ S, 7
– S, 7 # expanded={S}
+ SA, 5
+ SB, 7
– SA, 5 # expanded={S,A}
+ SAG, 8
– SB, 7 # expanded={S,A,B}
+ SBA, 4!
– SAG, 8 Non-optimal solution!
What went wrong?
• An expensive path, sa, was expanded before a cheaper one sba could
be discovered because f(sa) < f(sb).
• Is the heuristic function h admissible?
‣ Yes.
• So why?
‣ h(a) is too low compared to h(b), this makes sa look better. [or
equivalently h(b) is relatively too high making sb look worse.]
‣ we see that once, sb is expanded to sba, the f-value drops.
• So what can we do?
‣ We need a stronger condition than admissibility to stop this from
happening.
18
Monotonicity
A heuristic function is monotone (or consistent) if for every two nodes n,
and n' which is reachable from n:
h(n) ≤ cost(n,n') + h(n')
With monotone restriction, we have:
f(n') = cost(s,n') + h(n')
= cost(s,n) + cost(n,n') + h(n')
≥ cost(s,n) + h(n)
= f(n)
that is, f(n) is non-decreasing along any path.
Another interpretation for monotone restriction: real cost must always
exceed reduction in heuristic!
Monotonicity is stronger condition than admissibility.
If h meets the monotone requirement, A* using multiple-path pruning yields
optimal solutions.
19
n'
n
g
cost(n, n')
h(n)
h(n')
Finding good heuristics
• Most of the work is in coming up with admissible heuristics.
• A common approach is to solve a less constrained (simpler) version of
the problem.
• Good news: usually admissible heuristics are also consistent.
• Even inadmissible heuristics are often quite effective if we are OK with
sacrificing optimality to some degree (or when we have no choice).
• In fact a known hack is to use a * h(n) where h is admissible and a > 1
(i.e. create an inadmissible heuristic) in order to save more time (but
lose optimality).
• [In COSC367 programming exercises we do not use inadmissible
heuristics.]
20
Example heuristic in 8-puzzle
21
§ Number of tiles
misplaced?
§ Why is it admissible?
§ h(start) = 8 Average nodes expanded when optimal path has length…
…4
steps
…8 steps …12 steps
LCFS 112 6,300 3.6 x 106
A* – TILES 13 39 227
Example heuristic in 8-puzzle (cont’d)
22
§ What if we had an easier
8-puzzle where any tile
could slide any one
direction at any time?
§ Total Manhattan distance
§ Why admissible?
§ h(start) = 3 + 1 + 2 + … =
18
Average nodes expanded when
optimal path has length…
…4
steps
…8 steps …12 steps
A* – TILES 13 39 227
A* – MAN-HATTAN 12 25 73
Best heuristic?
How about using the actual cost as a heuristic?
– Would it be a valid heuristic?
– Would we save on nodes expanded?
– What’s wrong with it?
Choosing a heuristic: a trade-off between quality of estimate
and work per node!
23
Dominance relation
24
Other search strategies
25
Bidirectional search
• Idea: search backward from the goal and forward from the start simultaneously.
• Need to be able to generate the reverse graph (incoming arcs).
• Need to make sure the frontiers meet.
• Can be used with BFS, LCFS, or A*.
• This wins as 2bd/2 ≪ bd. This can result in an exponential saving in time and
space.
26
Bounded depth-first search
• A bounded depth-first search takes a bound (cost or depth) and does not expand paths
that exceed the bound.
– explores part of the search tree
– uses space linear in the depth of the search.
• Which shaded goal will a depth-bounded search find first? [Consider bounds 0, 1, 2, …]
27
Which shaded goal will a depth-bounded search find first?
Q W
T
U
Y
R
V
c�D. Poole and A. Mackworth 2017 Artificial Intelligence, Chapter 3, Page 42
Iterative-deepening search
• Iterative-deepening search:
‣ Start with a bound b = 0.
‣ Do a bounded depth-first search with bound b
‣ If a solution is found return that solution
‣ Otherwise increment b and repeat.
• This will find the same first solution as what other method?
• How much space is used?
• What happens if there is no path to a goal?
• How wasteful is recomputing paths?
28
Iterative-deepening search: illustration
29
Iterative-deepening search: complexity
30
Iterative Deepening Complexity
Complexity with solution at depth k & branching factor b:
level breadth-first iterative deepening # nodes
1 1 k b
2 1 k � 1 b2
. . . . . . . . . . . .
k � 1 1 2 bk�1
k 1 1 bk
total � bk bk
⇣
b
b�1
⌘2
c�D. Poole and A. Mackworth 2017 Artificial Intelligence, Chapter 3, Page 44