人工智能原理复习3

Informed Search

Blind search vs. “warmer” “colder”
Info about where goal is.
Optimal solution, explore less of the tree.

Search Heuristics

A heuristic is:
A function that estimates how close a state is to a goal
Designed for a particular search problem
Pathing?
Examples: Manhattan distance, Euclidean distance for pathing

Function takes a state, returns a number.
Not everyday term. Not “Look both ways before you cross the street”
How far I am? Could run search, but that defeats the purpose!
Not perfect, but something!

A* expanded 8100 ; Path cost = 33
UCS expanded 25263 . Path cost = 33
Greedy expanded 10 . Path cost = 41
[0, 7, 5, 3, 2, 1, 4, 6]
(7, 0, 5, 3, 2, 1, 4, 6)
(6, 4, 1, 2, 3, 5, 0, 7)
(3, 2, 1, 4, 6, 5, 0, 7)
(1, 2, 3, 4, 6, 5, 0, 7)
(5, 6, 4, 3, 2, 1, 0, 7)
(6, 5, 4, 3, 2, 1, 0, 7)
(0, 1, 2, 3, 4, 5, 6, 7)

Expand the node that seems closest…

Is it optimal?
No. Resulting path to Bucharest is not the shortest!

Numbers of heuristic, since that’s what greedy cares about.
Got to Bucharest, but not by shortest path.
End up with some kind of goal, but not what you want. You get a smelly shoe instead of to the airport on time.

Strategy: expand a node that you think is closest to a goal state

Heuristic: estimate of distance to nearest goal for each state

A common case:
Best-first takes you straight to the (wrong) goal

Worst-case: like a badly-guided DFS

A* Search

What we’ve been building to. Cornerstone. Goes to the goal like greedy, but backtracks as needed.
When it works, it’s magic!

Uniform-cost orders by path cost, or backward cost g(n)

Greedy orders by goal proximity, or forward cost h(n)

A* Search orders by the sum: > f(n) = g(n) + h(n)

UCS. Cumulative cost of arcs back to root. backward cost g(n). Computed as you go as part of the fringe.

Greedy. Heuristic forward cost h(n). NOT cumulative. Just a function of the state.

What is A*. Sum of the two! Doesn’t go to c early cuz h is high (far from goal).

Doesn’t do a->e branch g is high (expensive).

When should A* terminate?

No: only stop when we dequeue a goal

Inadmissible (pessimistic) heuristics break optimality by trapping good plans on the fringe

Admissible (optimistic) heuristics slow down bad plans but never outweigh true costs

If heuristic lies, and overestimates. Mistake.
Underestimate might reduce to UCS.

Coming up with admissible heuristics is most of what’s involved in using A* in practice.

Optimality of A* Tree Search

UCS ragged based on cost.
A* narrows when near goal, heuristic

Uniform-cost expands equally in all “directions”

A* expands mainly toward the goal, but does hedge its bets to ensure optimality

Change problem – same or easier. And cheaper.
Imagine a new direct road.
Walk through walls spell.
Inadmissible – a little bit suboptimal is okay.

Another relaxation, but “harder” than previous.
Lower bound.
Show it’s relaxed or prove.
At LEAST 18 away.
As heuristic gets close to the true cost, you do less search.

Looks great. Each node launches search as hard as the original problem.
You’ll might see this in P1. Come up with great heuristic, makes solution slower.

Graph Search

Failure to detect repeated states can cause exponentially more work.

Exponential unrolling. Generally what happens.
May need to consider both paths to B, but what’s underneath B is the same.
Should be able to save the work.

Idea: never expand a state twice

How to implement:
Tree search + set of expanded states (“closed set”)
Expand the search tree node-by-node, but…
Before expanding a node, check to make sure its state has never been expanded before
If not new, skip it, if new add to closed set

Important: store the closed set as a set, not a list

Can graph search wreck completeness? Why/why not?

How about optimality?

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

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

There’s a problem with this argument. What are we assuming is true?

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!