DOC PREVIEW
UMD CMSC 722 - Chapter 2 Representations for Classical Planning

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 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 30 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 30 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 30 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 30 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 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 1 Chapter 2 Representations for Classical Planning Lecture slides for Automated Planning: Theory and Practice Dana S. Nau University of Maryland 4:56 PM January 30, 2012Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 2 location 1 location 2 location 1 location 2 s1 s3 s4 take put location 1 location 2 location 1 location 2 s0 s2 s5 move1 put take move1 move1 move2 load unload Quick Review of Classical Planning move2 move2 ● Classical planning requires all eight of the restrictive assumptions: A0: Finite A1: Fully observable A2: Deterministic A3: Static A4: Attainment goals A5: Sequential plans A6: Implicit time A7: Offline planning location 1 location 2 location 1 location 2Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 3 Representations: Motivation ● In most problems, far too many states to try to represent all of them explicitly as s0, s1, s2, … ● Represent each state as a set of features ◆ e.g., » a vector of values for a set of variables » a set of ground atoms in some first-order language L ● Define a set of operators that can be used to compute state-transitions ● Don’t give all of the states explicitly ◆ Just give the initial state ◆ Use the operators to generate the other states as neededDana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 4 Outline ● Representation schemes ◆ Classical representation ◆ Set-theoretic representation ◆ State-variable representation ◆ Examples: DWR and the Blocks World ◆ ComparisonsDana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 5 Classical Representation ● Start with a first-order language » Language of first-order logic ◆ Restrict it to be function-free » Finitely many predicate symbols and constant symbols, but no function symbols ● Example: the DWR domain ◆ Locations: l1, l2, … ◆ Containers: c1, c2, … ◆ Piles: p1, p2, … ◆ Robot carts: r1, r2, … ◆ Cranes: k1, k2, …Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 6 Classical Representation ● Atom: predicate symbol and args ◆ Use these to represent both fixed and dynamic relations adjacent(l,l’) attached(p,l) belong(k,l) occupied(l) at(r,l) loaded(r,c) unloaded(r) holding(k,c) empty(k) in(c,p) on(c,c’) top(c,p) top(pallet,p) ● Ground expression: contains no variable symbols - e.g., in(c1,p3) ● Unground expression: at least one variable symbol - e.g., in(c1,x) ● Substitution: θ = {x1 ← v1, x2 ← v2, …, xn ← vn} ◆ Each xi is a variable symbol; each vi is a term ● Instance of e: result of applying a substitution θ to e ◆ Replace variables of e simultaneously, not sequentiallyDana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 7 States ● State: a set s of ground atoms ◆ The atoms represent the things that are true in one of Σ’s states ◆ Only finitely many ground atoms, so only finitely many possible states s1 = {attached(p1,loc1), in(c1,p1), in(c3,p1), top(c3,p1), on(c3,c1), on(c1,pallet), attached(p2,loc1), in(c2,p2), top(c2,p2), on(c2,palet), belong(crane1,loc1), empty(crane1), adjacent(loc1,loc2), adjacent(loc2,loc1), at(r1,loc2), occupied(loc2, unloaded(r1)}Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 8 Operators ● Operator: a triple o=(name(o), precond(o), effects(o)) ◆ precond(o): preconditions » literals that must be true in order to use the operator ◆ effects(o): effects » literals the operator will make true ◆ name(o): a syntactic expression of the form n(x1,…,xk) » n is an operator symbol - must be unique for each operator » (x1,…,xk) is a list of every variable symbol (parameter) that appears in o ● Purpose of name(o) is so we can refer unambiguously to instances of o ● Rather than writing each operator as a triple, we’ll usually write like this:Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 9 Actions ● An action is a ground instance (via substitution) of an operator ◆ Let θ = {k ← crane1, l ← loc1, c ← c3, d ← c1, p ← p1} ◆ Then (take(k,l,c,d,p))θ is the following action: take(crane1,loc1,c3,c1,p1) precond: belong(crane,loc1), attached(p1,loc1), empty(crane1), top(c3,p1), on(c3,c1) effects: holding(crane1,c3), ¬empty(crane1), ¬in(c3,p1), ¬top(c3,p1), ¬on(c3,c1), top(c1,p1) ◆ i.e., crane crane1 at location loc1 takes c3 off of c1 in pile p1Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/ 10 Notation ● Let S be a set of literals. Then ◆ S+ = {atoms that appear positively in S} ◆ S– = {atoms that appear negatively in S} ● Let a be an operator or action. Then ◆ precond+(a) = {atoms that appear positively in a’s preconditions} ◆ precond–(a) = {atoms that appear negatively in a’s preconditions} ◆ effects+(a) = {atoms that appear positively in a’s effects} ◆ effects–(a) = {atoms that appear negatively in a’s effects} ● Example: take(crane1,loc1,c3,c1,p1) precond: belong(crane,loc1), attached(p1,loc1), empty(crane1), top(c3,p1), on(c3,c1)


View Full Document
Download Chapter 2 Representations for Classical Planning
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 Chapter 2 Representations for Classical Planning 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 Chapter 2 Representations for Classical Planning 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?