UMD CMSC 722 - Chapter 2 Representations for Classical Planning (30 pages)

Previewing pages 1, 2, 14, 15, 29, 30 of 30 page document View the full content.
View Full Document

Chapter 2 Representations for Classical Planning



Previewing pages 1, 2, 14, 15, 29, 30 of actual document.

View the full content.
View Full Document
Unformatted text preview:

Lecture slides for Automated Planning Theory and Practice Chapter 2 Representations for Classical Planning Dana S Nau University of Maryland 4 56 PM January 30 2012 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 Quick Review of Classical Planning 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 s1 s0 put take location 1 location 2 move2 location 1 location 2 move2 move1 move1 s3 s2 put take location 1 location 2 unload location 1 location 2 load s4 s5 move2 move1 location 1 location 2 location 1 location 2 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 2 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 statetransitions Don t give all of the states explicitly Just give the initial state Use the operators to generate the other states as needed 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 3 Outline Representation schemes Classical representation Set theoretic representation State variable representation Examples DWR and the Blocks World Comparisons 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 4 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 5 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 sequentially 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 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 7 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 8 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 p1 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 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 effects holding crane1 c3 empty crane1 in c3 p1 top c3 p1 on c3 c1 top c1 p1 effects take crane1 loc1 c3 c1 p1 holding crane1 c3 top c1 p1 effects take crane1 loc1 c3 c1 p1 empty crane1 in c3 p1 top c3 p1 on c3 c1 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 10 Applicability Let s be a state and a be an action a is applicable to or executable in s if s satisfies precond a precond a s precond a s An 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 A state it s applicable to 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


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

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 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?