Informed Heuristic Search

Basic search scheme

• We have 3 kinds of states
– Explored (past) – only graph search
– Frontier (current)
– Unexplored (future) – implicitly given
General approach
• Loop until found solution or exhausted state space
a. Pick/remove first node from frontier using search strategy
priority queue – FIFO (BFS), LIFO (DFS)
b. Check if goal
c. Add this node to explored,
d.Expand this node, add children to frontier
Q: what if better path is found to a node already on explored
list? 2016
271-Fall
 What is a heuristic?

 A heuristic is a technique that is used to solve a problem faster than the classic methods.
 These techniques are used to find the approximate solution of a problem when classical methods do
not.
 Heuristics are said to be the problem-solving techniques that result in practical and quick solutions.
 Heuristics are strategies that are derived from past experience with similar problems.
 Heuristics use practical methods and shortcuts used to produce the solutions that may or may not

be optimal, but these solutions are sufficient in a given limited timeframe.

271-Fall 2016
 Heuristic Search
Heuristic - Proceeding to a solution by trial and error or by rules that are only loosely defined.

• State-Space Search: every problem is like search of a map

• A problem solving agent finds a path in a state-space graph from start
state to goal state, using heuristics

h=374

h= 253

h=329

271-Fal l 2016
 State Space for Path Finding in a Map

271-Fall 2016
 State Space for Path Finding on a Map

271-Fall 2016
 Greedy Search Example

271-Fall 2016
 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 trilion24-
puzzle: 10^25 7 8

Search space exponential

Use Heuristics
as people do

271-Fall 2016
 State Space of the 8 Puzzle
Problem 1 2 3
4 5 6
7 8
h1 = number of misplaced tiles

(Heuristic functions)

h2 = Manhattan distance
h1=4 h1=5

h2=9 h2=9

271-Fall 2016
 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.
8-puzzle
(Heuristic function)
– h1(n): number of misplaced tiles h1(S) = ? 8
– h2(n): Manhattan distance h2(S) = ? 3+1+2+2+2+3+3+2
– h3(n): Gaschnig’s

• 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 steps along the 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
271-Fall 2016
 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 2016
 Greedy Best-First Search
• Evaluation function f(n) = h(n) (heuristic)
= estimate of cost from n to goal

• e.g., hSLD(n) = straight-line distance from n to

Bucharest

• Greedy best-first search expands the node

that appears to be closest to goal
271-Fall 2016
 Greedy Best-First Search Example

271-Fall 2016
Greedy Best-First Search Example

271-Fall 2016
Greedy Best-First Search Example

271-Fall 2016
Greedy Best-First Search Example

271-Fall 2016
 Problems with Greedy Search
• Not complete
– Gets stuck on local minimas and plateaus
• Infinite loops
• Irrevocable
• Not optimal
• Can we incorporate heuristics in systematic
search?

271-Fall 2016
 Informed Search - Heuristic Search
• How to use heuristic knowledge in systematic search?
• Where? (in node expansion?
• Best-first:
– select the best from all the nodes encountered so far in OPEN.
• Heuristic estimates value of a node
– promise of a node
– difficulty of solving the subproblem
– quality of solution represented by node
– the amount of information gained.
• f(n) - heuristic evaluation function.
– depends on n, goal, search so far, domain

271-Fall 2016
 A* Search
• Idea:
– avoid expanding paths that are already expensive
– focus on paths that show promise

• Evaluation function f(n) = g(n) + h(n)

• g(n) = cost so far to reach n

• h(n) = estimated cost from n to goal

• f(n) = estimated total cost of path through n to goal

271-Fall 2016
 A* Search Example

271-Fall 2016
 A* Search Example

271-Fall 2016
 A* Search Example

193+220 = 413
(Min)

271-Fall 2016
 A* Search Example

271-Fall 2016
 A* Search Example

271-Fall 2016
 A* Search Example

271-Fall 2016
 Effectiveness of heuristic search
• How quality of the heuristic impacts search?

• What is the time and space complexity?

• Is any algorithm better? Worse?

• Case study: the 8-puzzle

271-Fall 2016
 Admissible and Consistent Heuristics?
E.g., for the 8-puzzle:

•
h1(n) = number of misplaced tiles
•
h2(n)
(i.e., no. of=squares
total Manhattan distance
from desired location of each tile)
The true cost is 26.

• h1(S) = ? 8
• h2(S) = ? 3+1+2+2+2+3+3+2 = 18

271-Fall 2016
 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?

How can we invent admissible heuristics in

general?
• look at “relaxed” problem where constraints are
removed
– e.g.., we can move in straight lines between cities
– e.g.., we can move tiles independently of each
271-Fall 2016
other
 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
• … if A and B are adjacent
• ... if B is blank

271-Fall 2016
 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

moveanywhere, 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 2016
 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 2016
271-Fall 2016
 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 2016
 Beyond Classical Search
• AND/OR search spaces
– Decomposable independent problems
– Searching with non-deterministic actions (erratic vacuum)
– Using AND/OR search spaces; solution is a contingent plan
• Local search for optimization
– Greedy hill-climbing search
– Local search in continuous spaces

271-Fall 2016
 AND/OR search spaces
Non-deterministic actions : The erratic vacuum world

271-Fall 2016
 AND/OR Graphs
• Nodes represent sub problems

– AND links represent subproblem decompositions

– OR links represent alternative solutions
– Start node is initial problem
– Terminal nodes are solved 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 2016
 Summary
• In practice we often want the goal with the minimum cost path

• Exhaustive search is impractical except on small problems

• Heuristic estimates of the path cost from a node to the goal can
be efficient in reducing the search space.

• The A* algorithm combines all of these ideas with admissible

heuristics (which underestimate) , guaranteeing optimality.
• Properties of heuristics:
– admissibility, consistency, dominance, accuracy