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