CIS 471/571(Fall 2020): Introduction to Artificial Intelligence
Lecture 3: Informed Search
Thanh H. Nguyen
Most slides are by Pieter Abbeel, Dan Klein, Luke Zettlemoyer, John DeNero, Stuart Russell, Andrew Moore, or Daniel Lowd
Source: http://ai.berkeley.edu/home.html
Reminder
§ Homework 1: Search § Deadline: Oct 10, 2020
§ Project 1: Search
§ Deadline: Oct 13, 2020
Thanh H. Nguyen
10/5/20
2
Today
§Uninformed Search §Uniform Cost Search
§Informed Search §Heuristics §Greedy Search §A* Search
§Graph Search
Recap: Search
§Search problem:
§ States (configurations of the world) § Actions and costs
§ Successor function (world dynamics) § Start state and goal test
§Search tree:
§ Nodes: represent plans for reaching states § Plans have costs (sum of action costs)
§Search algorithm:
§ Systematically builds a search tree
§ Chooses an ordering of the fringe (unexplored nodes) § Optimal: finds least-cost plans
Uninformed Search
Thanh H. Nguyen
10/5/20
5
Uniform-Cost Search(UCS)
2 3d2ef
Strategy: expand a cheapest node first:
Fringeisapriorityqueue (priority: cumulative cost)
b
1
1
a G 8 c 2
S
9 h 8 2 15 q
1
r
p
d3
S0
e9 p1
h17r11 q16
b4c11 e5
a 6 a h 13 r 7 p q f
pqf
q 11 c a
8qcG
G 10
a
Thanh H. Nguyen
10/5/20
6
UCS Properties
§ What nodes does UCS expand?
§ Processes all nodes with cost less than cheapest solution!
§ If that solution costs C* and arcs cost at least e , then the “effective depth” is roughly C*/e
§ Takes time O(bC*/e) (exponential in effective depth) § How much space does the fringe take?
§ Has roughly the last tier, so O(bC*/e) § Is it complete?
b
…
c£e
c £ 2e
c £ 3e
C*/e “tiers”
§ Assuming best solution has a finite cost and minimum arc cost is positive, yes!
§ Is it optimal? § Yes!
Uniform Cost Search
§Strategy: expand lowest path cost
§The good: UCS is complete and optimal!
§The bad:
§Explores options in every “direction” §No information about goal location
c£e
c £ 2e
…
c £ 3e
Start
Goal
Informed Search
Search Heuristics
§ A heuristic is:
§ A function that estimates how close a state is to a goal
§ Designed for a particular search problem
§ Examples: Manhattan distance, Euclidean distance for pathing
10
5
11.2
Example: Heuristic Function
h(x)
Example: Pancake Problem
Cost: Number of pancakes flipped
Example: Pancake Problem
State space graph with costs as weights 4
2
4 3
3 4
3
2
3
42
2
2
3
Example: Heuristic Function
Heuristic: the number of the largest pancake that is still out of place
4
4
4 4
4
3
3
3
3
3 4
2
h(x)
0
Greedy Search
Greedy Search
§Expand the node that seems closest…
h(x)
Greedy Search
§Expand the node that seems closest…
§What can go wrong?
Greedy Search
§A common case:
§Best-first takes you straight to the (wrong) goal
b …
§Worst-case: like a badly-guided DFS
b …
A* Search
Combining UCS and Greedy
§ Uniform-cost orders by path cost, or backward cost g(n) § Greedy orders by goal proximity, or forward cost h(n)
8
S1a3d2G
S
g=0 h=6
e 1
h=1
g=1 h=5
a bdg=4e
g=3 h=7
g=9 h=1
g = 10 h=2
g = 12 h=0
h=6 1 h=5 c1b
h=7 h=6
h=2 h=0
g=2 h=6
h=2
cGg=6d h=0
§ A* Search orders by the sum: f(n) = g(n) + h(n)
G
When should A* terminate?
§Should we stop when we enqueue a goal? h=2
2A2
Sh=3 h=0G
2B3
h=1
§No: only stop when we dequeue a goal
Is A* Optimal?
h=6
1A3
S
h=7
G
h=0
§What went wrong?
§ Actual bad goal cost < estimated good goal cost § We need estimates to be less than actual costs!
5
Admissible Heuristics
Idea: Admissibility
Inadmissible (pessimistic) heuristics Admissible (optimistic) heuristics never break optimality by trapping good plans outweigh true costs
on the fringe
Admissible Heuristics
§A heuristic h is admissible (optimistic) if: where is the true cost to a nearest goal
§Examples:
15
4
§Coming up with admissible heuristics is most of what’s involved in using A* in practice.
Optimality of A* Tree Search
Optimality of A* Tree Search
§Heuristic function h is admissible §Claim: A* tree search is optimal
Optimality of A* Tree Search
Assume:
§A is an optimal goal node §B is a suboptimal goal node §h is admissible
Claim:
§ A will exit the fringe before B
...
Optimality of A* Tree Search: Blocking
Proof:
§Imagine B is on the fringe
§Some ancestor n of A is on the fringe, too (maybe A!)
§ Claim: n will be expanded before B 1. f(n) is less or equal to f(A)
...
Definition of f-cost Admissibility of h h = 0 at a goal
Optimality of A* Tree Search: Blocking
Proof:
§Imagine B is on the fringe
§Some ancestor n of A is on the fringe, too (maybe A!)
§ Claim: n will be expanded before B
1. f(n) is less or equal to f(A)
2. f(A) is less than f(B)
...
B is suboptimal h = 0 at a goal
Optimality of A* Tree Search: Blocking
Proof:
§Imagine B is on the fringe
§Some ancestor n of A is on the fringe, too (maybe A!)
§ Claim: n will be expanded before B
...
1. 2. 3.
f(n) is less or equal to f(A) f(A) is less than f(B)
n expands before B
§ All ancestors of A expand before B §A expands before B
§A* search is optimal
Properties of A*
Uniform-Cost A*
b ...
b ...
UCS vs A* Contours
§Uniform-cost expands equally in all “directions”
§A* expands mainly toward the goal, but does hedge its bets to ensure optimality
Start
Goal
Start Goal
A* Applications
§Video games
§Pathing / routing problems §Resource planning problems §Robot motion planning §Language analysis §Machine translation §Speech recognition
§...
Example: 8 Puzzle
Start State
§What are the states? §How many states? §What are the actions?
Actions Goal State
§ How many successors from the start state? §What should the costs be?
8 Puzzle I
§Heuristic: Number of tiles misplaced §Why is it admissible?
§h(start) = 8
§This is a relaxed-problem heuristic
Start State
Goal State
UCS
TILES
Average nodes expanded when the optimal path has...
...4 steps
112
13
...8 steps
6,300
39
...12 steps
3.6 x 106
227
Statistics from Andrew Moore
8 Puzzle II
§ What if we had an easier 8-puzzle where any tile could slide any direction at any time, ignoring other tiles?
§Total Manhattan distance
§Why is it admissible?
§h(start) =
3 + 1 + 2 + ... = 18
Start State
Goal State
TILES
MANHATTAN
Average nodes expanded when the optimal path has...
...4 steps
13
12
...8 steps
39
25
...12 steps
227
73
8 Puzzle III
§How about using the actual cost as a heuristic? §Would it be admissible?
§Would we save on nodes expanded?
§What’s wrong with it?
§With A*: a trade-off between quality of estimate and work per node
§ As heuristics get closer to the true cost, you will expand fewer nodes but usually do more work per node to compute the heuristic itself
Creating Admissible Heuristics
§Most of the work in solving hard search problems optimally is in coming up with admissible heuristics
§Often, admissible heuristics are solutions to relaxed problems, where new actions are available
366
15
§ Inadmissible heuristics are often useful too (why?)
Trivial Heuristics, Dominance
§Dominance: ha ≥ hc if §Heuristics form a semi-lattice:
§ Max of admissible heuristics is admissible
§Trivial heuristics
§ Bottom of lattice is the zero heuristic (what
does this give us?)
§ Top of lattice is the exact heuristic
Tree Search: Extra Work!
§Failure to detect repeated states can cause exponentially more work. Why?
Graph Search
§In BFS, for example, we shouldn’t bother expanding some nodes (which, and why?)
S
d
bcehr
aahr pqf
qc a
ep
q
pqf qc
G
G a
Graph Search
§Very simple fix: never expand a state type twice
§Can this wreck completeness? Why or why not? § How about optimality? Why or why not?
A* Graph Search Gone Wrong
State space graph
A
Search tree
S (0+2)
1
S
1
B
h=1
1 C 2 3
G
h=0
h=2
h=4
h=1
A (1+4) C (2+1) G (5+0)
B (1+1) C (3+1) G (6+0)
Consistency of Heuristics
A
h=4 1 C h=1
§ Main idea: estimated heuristic costs ≤ actual costs § Admissibility: heuristic cost ≤ actual cost to goal
h(A) ≤ actual cost from A to G
§ Consistency: heuristic “arc” cost ≤ actual cost for each arc
h(A) – h(C) ≤ cost(A to C)
§ Consequences of consistency:
§ The f value along a path never decreases
h(A) ≤ cost(A to C) + h(C)
f(A) = g(A) + h(A) ≤ g(A) + cost(A to C) + h(C) ≤ f(C) § A* graph search is optimal
h=2
3
G
Optimality of A* Graph Search
Optimality of A* Graph Search
§Sketch: consider what A* does with a consistent heuristic:
§Fact 1: In tree search, A* expands ... nodes in increasing total f value (f-
contours)
§ Fact 2: For every state s, nodes that reach s optimally are expanded before nodes that reach s suboptimally
§Result: A* graph search is optimal
f£1
f £ 2
f£3
Optimality
§Tree search:
§ A* is optimal if heuristic is admissible §UCS is a special case (h = 0)
§Graph search:
§ A* optimal if heuristic is consistent § UCS optimal (h = 0 is consistent)
§Consistency implies admissibility
§In general, most natural admissible heuristics tend to be consistent, especially if from relaxed problems
A*: Summary
A*: Summary
§A* uses both backward costs and (estimates of) forward costs
§A* is optimal with admissible / consistent heuristics §Heuristic design is key: often use relaxed problems
Tree Search Pseudo-Code
Graph Search Pseudo-Code
Optimality of A* Graph Search
§Consider what A* does:
§ Expands nodes in increasing total f value (f-contours)
Reminder: f(n) = g(n) + h(n) = cost to n + heuristic
§ Proof idea: the optimal goal(s) have the lowest f value, so it must get expanded first
f£1 f£2
...
f£3
There’s a problem with this argument. What are we assuming is true?
Optimality of A* Graph Search
Proof:
§ New possible problem: some n on path to G* isn’t in queue when we need it, because some worse n’ for the same state dequeued and expanded first (disaster!)
§ Take the highest such n in tree
§ Let p be the ancestor of n that was on the
queue when n’ was popped
§ f(p) < f(n) because of consistency
§ f(n) < f(n’) because n’ is suboptimal
§ p would have been expanded before n’
§ Contradiction!