DOC PREVIEW
Pitt CS 2710 - LECTURE NOTES

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

A* Review  A* uses both backward costs g and forward estimate h: f(n) = g(n) + h(n)  A* tree search is optimal with admissible heuristics (optimistic future cost estimates)  Heuristic design is key: relaxed problems can helpCombining UCS and Greedy  Uniform-cost orders by path cost, or backward cost g(n)  Best-first orders by goal proximity, or forward cost h(n)  A* Search orders by the sum: f(n) = g(n) + h(n) S a d b G h=5 h=6 h=2 1 5 1 1 2 h=6 h=0 c h=7 3 e h=1 1UCS vs A* Contours  Uniform-cost expanded in all directions  A* expands mainly toward the goal, but does hedge its bets to ensure optimality Start Goal Start Goal [Is A* Optimal? A G S 1 3 h = 6 h = 0 5 h = 7  What went wrong?  Actual bad goal cost < estimated good goal cost  We need estimates to be less than actual costs!A* Graph Search Gone Wrong S A B C G 1 1 1 2 3 h=2 h=1 h=4 h=1 h=0 S (0+2) A (1+4) B (1+1) C (2+1) G (5+0) C (3+1) G (6+0) S A B C G State space graph Search treeConsistency 3 A C G h=4 h=1 1 The story on Consistency: • Definition: cost(A to C) + h(C) ≥ h(A) • Consequence in search tree: Two nodes along a path: NA, NC g(NC) = g(NA) + cost(A to C) g(NC) + h(C) ≥ g(NA) + h(A) • The f value along a path never decreases • Non-decreasing f means you’re optimal to every state (not just


View Full Document

Pitt CS 2710 - LECTURE NOTES

Documents in this Course
Learning

Learning

24 pages

Planning

Planning

25 pages

Lecture

Lecture

12 pages

Load more
Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?