程序代写代做代考 algorithm graph go C game html CIS 471/571(Fall 2020): Introduction to Artificial Intelligence

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!