Set 3: Informed Heuristic Search: ICS 271 Fall 2014 Kalev Kask
Set 3: Informed Heuristic Search: ICS 271 Fall 2014 Kalev Kask
Set 3: Informed Heuristic Search: ICS 271 Fall 2014 Kalev Kask
271-Fall 2014
What is a heuristic?
271-Fall 2014
Heuristic Search
• State-Space Search: every problem is like search of a map
• A problem solving robot finds a path in a state-space graph from start
state to goal state, using heuristics
h=374
h= 253
h=329
271-Fall 2014
State Space for Path Finding in a Map
271-Fall 2014
Greedy Search Example
271-Fall 2014
State Space of the 8 Puzzle
Problem 1 2 3
Initial state goal
8-puzzle: 181,440 states 4 5 6
15-puzzle: 1.3 trilion
7 8
24-puzzle: 10^25
Use Heuristics
as people do
271-Fall 2014
State Space of the 8 Puzzle
Problem 1 2 3
4 5 6
7 8
h1 = number of misplaced tiles
h2 = Manhattan distance
h1=4 h1=5
h2=9 h2=9
271-Fall 2014
What are Heuristics
• Rule of thumb, intuition
• A quick way to estimate how close we are to the
goal. How close is a state to the goal..
• Pearl: “the ever-amazing observation of how much
people can accomplish with that simplistic, unreliable
information source known as intuition.”
8-puzzle
– h1(n): number of misplaced tiles h1(S) = ? 8
– h2(n): Manhattan distance h2(S) = ? 3+1+2+2+2+3+3+2 = 18
• Path-finding on a map
– Euclidean distance
Problem: Finding a Minimum Cost Path
• Previously we wanted an path with minimum number of
steps. Now, we want the minimum cost path to a goal G
– Cost of a path = sum of individual transitions along path
• Examples of path-cost:
– Navigation
• path-cost = distance to node in miles
– minimum => minimum time, least fuel
– VLSI Design
• path-cost = length of wires between chips
– minimum => least clock/signal delay
– 8-Puzzle
• path-cost = number of pieces moved
– minimum => least time to solve the puzzle
• Algorithm: Uniform-cost search… still somewhat blind
271-Fall 2014
Heuristic Functions
• 8-puzzle
– Number of misplaced tiles
– Manhattan distance
– Gaschnig’s
• 8-queen
– Number of future feasible slots
– Min number of feasible slots in a
row
– Min number of conflicts (in
complete assignments states)
C
• Travelling salesperson
– Minimum spanning tree B
– Minimum assignment problem A D
F
E
Best-First (Greedy) Search:
f(n) = number of misplaced tiles
271-Fall 2014
Romania with Step Costs in km
271-Fall 2014
Greedy Best-First Search
• Evaluation function f(n) = h(n) (heuristic)
= estimate of cost from n to goal
271-Fall 2014
Greedy Best-First Search Example
271-Fall 2014
Greedy Best-First Search Example
271-Fall 2014
Greedy Best-First Search Example
271-Fall 2014
Problems with Greedy Search
• Not complete
271-Fall 2014
A* Search
• Idea:
– avoid expanding paths that are already expensive
– focus on paths that show promise
271-Fall 2014
A* Search Example
271-Fall 2014
A* Search Example
271-Fall 2014
A* Search Example
271-Fall 2014
A* Search Example
271-Fall 2014
A* Search Example
271-Fall 2014
A* on 8-Puzzle with h(n) = # misplaced tiles
271-Fall 2014
A*- a Special Best-First Search
• Goal: find a minimum sum-cost path
• Notation:
– c(n,n’) - cost of arc (n,n’)
– g(n) = cost of current path from start to node n in the search tree.
– h(n) = estimate of the cheapest cost of a path from n to a goal.
– evaluation function: f = g+h
• f(n) estimates the cheapest cost solution path that goes through n.
– h*(n) is the true cheapest cost from n to a goal.
– g*(n) is the true shortest path from the start s, to n.
– C* is the cost of optimal solution.
271-Fall 2014
1 4
A B C
2
S 2 5 G
5 3
2 4
D E F
A 10.4 B C
6.7 4.0
11.0 G
S
8.9 3.0
6.9
D E F
271-Fall 2014
Example of A* Algorithm in Action
1
2 +10.4 = 12.4
S 5 + 8.9 = 13.9
2 D
3 + 6.7 = 9.7 A 5
B 3 D 4 + 8.9 = 12.9
7 + 4 = 11 4 8 + 6.9 = 14.9 6
C E 6 + 6.9 = 12.9
E
7
Dead End
B F 10 + 3.0 = 13
1 4 11 + 6.7 = 17.7
A B C 8
2 A10.4 B C
6.7 4.0 G
5 G 13 + 0 = 13
2
S S 11.0 G
5 3
2 4 8.9 3.0
D
271-Fall 2014 E F D E 6.9 F
Algorithm A* (with any h on search Graph)
• Input: an implicit search graph problem with cost on the arcs
• Output: the minimal cost path from start node to a goal node.
– 1. Put the start node s on OPEN.
– 2. If OPEN is empty, exit with failure
– 3. Remove from OPEN and place on CLOSED a node n having minimum f.
– 4. If n is a goal node exit successfully with a solution path obtained by
tracing back the pointers from n to s.
– 5. Otherwise, expand n generating its children and directing pointers
from each child node to n.
• For every child node n’ do
– evaluate h(n’) and compute f(n’) = g(n’) +h(n’)= g(n)+c(n,n’)+h(n’)
– If n’ is already on OPEN or CLOSED compare its new f with the old f. If the
new value is higher, discard the node. Otherwise, replace old f with new f
and reopen the node.
– Else, put n’ with its f value in the right order in OPEN
– 6. Go to step 2.
271-Fall 2014
Behavior of A -
Termination/Completeness
271-Fall 2014
Admissible A*
• The heuristic function h(n) is called admissible if h(n) is never
larger than h*(n), namely h(n) is always less or equal to true
cheapest cost from n to the goal.
271-Fall 2014
A* with inadmissible h
513=220+293
→293
271-Fall 2014
Consistent (monotone) Heuristics
• A heuristic is consistent if for every node n, every successor n' of n generated by any action a,
• If h is consistent, we have
271-Fall 2014
Consistent Heuristics
– Proof: Assume g(n) > g*(n) and n expanded along a non-optimal path.
– Let n’ be the shallowest OPEN node on optimal path p to n
– g(n’) = g*(n’) and therefor f(n’)=g*(n’)+h(n’)
– Due to consistency we get f(n’) <=g*(n’)+k(n’,n)+h(n)
– Since g*(n) = g*(n’)+k(n’,n) along the optimal path, we get that
– f(n’) <= g*(n) + h(n)
– And since g(n) > g*(n) then f(n’) < g(n)+h(n) = f(n), contradiction
271-Fall 2014
Behavior of A* - Optimality
• Theorem (completeness for optimal solution) (HNL, 1968):
– If the heuristic function is
• admissible (tree search or graph search with explored node re-opening)
• Consistent (graph search w/o explored node re-opening)
– then A* finds an optimal solution.
• Proof:
– 1. A*(admissible/consistent) will expand only nodes whose f-values are
less (or equal) to the optimal cost path C* (f(n) is less-or-equal C*).
– 2. The evaluation function of a goal node along an optimal path equals
C*.
• Lemma:
– Anytime before A*(admissible/consistent) terminates there exists and
OPEN node n’ on an optimal path with f(n’) <= C*.
271-Fall 2014
Inconsistent but admissible
271-Fall 2014
Summary of Consistent Heuristics
• h is consistent if the heuristic function satisfies triangle inequality for every n and
its child node n’: h(ni) <= h(nj) + c(ni,nj)
271-Fall 2014
Summary so far
• Best-First Search : f
• A* : f = g + h
• Admissible heuristic : h <= h*
• Consistent heuristic : h(ni) <= c(ni,nj) + h(nj)
• Optimality guaranteed if admissible/consistent
271-Fall 2014
A* properties
• A* expands every path along which f(n) < C*
• Therefore, A* expands all the nodes for which f(n) < C* and
a subset of the nodes for which f(n) = C*.
expanded by h is smaller.
2
271-Fall 2014
Complexity of A*
• A* is optimally efficient (Dechter and Pearl 1985):
– It can be shown that all algorithms that do not expand a node
which A* did expand (inside the contours) may miss an optimal
solution
• A* worst-case time complexity:
– is exponential unless the heuristic function is very accurate
• If h is exact (h = h*)
– search focus only on optimal paths
• Main problem: space complexity is exponential
• Effective branching factor:
– Number of nodes generated by a “typical” search node
– Approximately : b* = N^(1/d)
271-Fall 2014
The Effective Branching Factor
271-Fall 2014
271-Fall 2014
1 4
A B C
2
S 2 5 G
5 3
2 4
D E F
A 10.4 B C
6.7 4.0
11.0 G
S
8.9 3.0
6.9
D E F
271-Fall 2014
Example of Branch and Bound in action
S 1 5+8.9=13.9
2+10.4=12.4
A 2 D
3+6.7=9.7 8
7+4=11
B 3 D 4+8.9=12.9
8+6.9=14.9 5
C 4 E 9
E 6+6.9=12.9
10+8.9=18.9
12+3=15
F 6
D 11+6.7=17.7
10+3=13 F 10 B
L=15+0=15
G 7 A10.4 B C
6.7 4.0
L=13+0=13
A 1 B 4 C G 11 S 11.0 G
2
S 5 G
2271-Fall 2014 8.9 3.0
5 3 D E 6.9 F
D 2 E 4 F
Example of A* Algorithm in Action
1
2 +10.4 = 12.4
S 5 + 8.9 = 13.9
2 D
3 + 6.7 = 9.7 A 5
B 3 D 4 + 8.9 = 12.9
7 + 4 = 11 4 8 + 6.9 = 14.9 6
C E 6 + 6.9 = 12.9
E
7
Dead End
B F 10 + 3.0 = 13
1 4 11 + 6.7 = 17.7
A B C 8
2 A10.4 B C
6.7 4.0 G
5 G 13 + 0 = 13
2
S S 11.0 G
5 3
2 4 8.9 3.0
D
271-Fall 2014 E F D E 6.9 F
Pseudocode for Branch and Bound Search
(An informed depth-first search)
Initialize: Let Q = {S}, L=∞
271-Fall 2014
Properties of Branch-and-Bound
• Not guaranteed to terminate unless
– has depth-bound
– admissible f and reasonable L
• Optimal:
– finds an optimal solution (f is admissible)
• Time complexity: exponential
• Space complexity: can be linear
• Advantage:
– anytime property
• Note : unlike A*, BnB may (will) expand nodes f>C*.
271-Fall 2014
Iterative Deepening A* (IDA*)
(combining Branch-and-Bound and A*)
• Initialize: f <-- the evaluation function of the start node
• until goal node is found
– Loop:
• Do Branch-and-bound with upper-bound L equal to current evaluation function f.
• Increment evaluation function to next contour level
– end
• Properties:
– Guarantee to find an optimal solution
– time: exponential, like A*
– space: linear, like B&B.
271-Fall 2014
Relationships among Search Algorithms
271-Fall 2014
Effectiveness of heuristic search
• How quality of heuristic impact search?
271-Fall 2014
Admissible and Consistent Heuristics?
E.g., for the 8-puzzle:
• h1(S) = ? 8
• h2(S) = ? 3+1+2+2+2+3+3+2 = 18
271-Fall 2014
Effectiveness of A* Search Algorithm
Average number of nodes expanded
2 10 6 6
4 112 13 12
8 6384 39 25
12 364404 227 73
271-Fall 2014
Heuristic’s Dominance and Pruning Power
• Definition:
– A heuristic function h2 (strictly) dominates h1 if both are
admissible and for every node n, h2(n) is (strictly) greater than
h1(n).
• Theorem (Hart, Nilsson and Raphale, 1968):
– An A* search with a dominating heuristic function h2 has the
property that any node it expands is also expanded by A*
with h1.
• Question: Does Manhattan distance dominate the
number of misplaced tiles?
• Extreme cases
– h=0
– h = h*
271-Fall 2014
Inventing Heuristics automatically
• Examples of Heuristic Functions for A*
– The 8-puzzle problem
• The number of tiles in the wrong position
– is this admissible?
• Manhattan distance
– is this admissible?
271-Fall 2014
Inventing Heuristics Automatically (cont.)
• How did we
– find h1 and h2 for the 8-puzzle?
– verify admissibility?
– prove that straight-line distance is admissible? MST admissible?
• Hypothetical answer:
– Heuristic are generated from relaxed problems
– Hypothesis: relaxed problems are easier to solve
• In relaxed models the search space has more operators or more
directed arcs
• Example: 8 puzzle:
– Rule : a tile can be moved from A to B, iff
• A and B are adjacent
• B is blank
– We can generate relaxed problems by removing one or more of the
conditions
• … A and B are adjacent & B is blank
• ... if B is blank
271-Fall 2014
Relaxed Problems
• A problem with fewer restrictions on the actions is called a
relaxed problem
• If the rules of the 8-puzzle are relaxed so that a tile can move
anywhere, then h1(n) (number of misplaced tiles) gives the
shortest solution
• If the rules are relaxed so that a tile can move to any h/v
adjacent square, then h2(n) (Manhatten distance) gives the
shortest solution
271-Fall 2014
Generating heuristics (cont.)
• Example: TSP
• Find a tour. A tour is:
– 1. A graph with subset of edges
– 2. Connected
– 3. Total length of edges minimized
– 4. Each node has degree 2
• Eliminating 4 yields MST.
271-Fall 2014
271-Fall 2014
Automating Heuristic generation
• Use STRIPs language representation:
• Operators:
– pre-conditions, add-list, delete list
• 8-puzzle example:
– on(x,y), clear(y) adj(y,z) ,tiles x1,…,x8
• States: conjunction of predicates:
– on(x1,c1),on(x2,c2)….on(x8,c8),clear(c9)
• move(x,c1,c2) (move tile x from location c1 to location c2)
– pre-cond: on(x1,c1), clear(c2), adj(c1,c2)
– add-list: on(x1,c2), clear(c1)
– delete-list: on(x1,c1), clear(c2)
• Relaxation:
– Remove from precondition: clear(c2), adj(c2,c3) #misplaced tiles
– Remove clear(c2) Manhattan distance
– Remove adj(c2,c3) h3, a new procedure that transfers to the empty
location a tile appearing there in the goal
• The space of relaxations can be enriched by predicate refinements
– adj(y,z) = iff neigbour(y,z) and same-line(y,z)
271-Fall 2014
Heuristic generation
• Theorem: Heuristics that are generated from relaxed models
are consistent.
271-Fall 2014
Heuristic generation
• Total (time) complexity = heuristic computation + nodes
expanded
• More powerful heuristic – harder to compute, but more pruning
power (fewer nodes expanded)
• Problem:
– not every relaxed problem is easy
• How to recognize a relaxed easy problem
• A proposal: a problem is easy if it can be solved optimally
by a greedy algorithm
• Q: what if neither h1 nor h2 is clearly better? max(h1, h2)
• Often, a simpler problem which is more constrained is easier;
will provide a good upper-bound.
271-Fall 2014
Improving Heuristics
• Reinforcement learning.
• Pattern Databases: you can solve optimally a
sub-problem
271-Fall 2014
Pattern Databases
• For sliding tiles and Rubic’s cube
• For a subset of the tiles compute shortest path to the goal using
breadth-first search
• For 15 puzzles, if we have 7 fringe tiles and one blank, the number of
patterns to store are 16!/(16-8)! = 518,918,400.
• For each table entry we store the shortest number of moves to the
goal from the current location.
• Use different subsets of tiles and take the max heuristic during IDA*
search. The number of nodes to solve 15 puzzles was reduced by a
factor of 346 (Culberson and Schaeffer)
271-Fall 2014
AND/OR search spaces
non-deterministic actions : the erratic vacuum world
271-Fall 2014
AND/OR Graphs
• Nodes represent subproblems
• Solution graph
– It is an AND/OR subgraph such that:
• It contains the start node
• All its terminal nodes (nodes with no successors) are solved primitive
problems
• If it contains an AND node A, it must contain the entire group of AND links
that leads to children of A.
271-Fall 2014
Algorithms searching AND/OR graphs
• All algorithms generalize using hyper-arc successors rather than simple
arcs.
• The cost of a solution graph is the sum cost of it arcs. It can be defined
recursively as: k(n,N) = c_n+k(n1,N)+…k(n_k,N)
• h*(n) is the cost of an optimal solution graph from n to a set of goal nodes
271-Fall 2014
Local Search
271-Fall 2014
271-Fall 2014
Summary
• In practice we often want the goal with the minimum cost path
• Heuristic estimates of the path cost from a node to the goal can
be efficient in reducing the search space.
271-Fall 2014