DOC PREVIEW
Pitt CS 2710 - A Review

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 - A Review

Documents in this Course
Learning

Learning

24 pages

Planning

Planning

25 pages

Lecture

Lecture

12 pages

Load more
Download A Review
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 A Review 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 A Review 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?