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 5 Plan-Space Planning Lecture slides for Automated Planning: Theory and Practice Dana S. Nau University of Maryland 5:10 PM February 6, 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 ● Problem with state-space search ◆ In some cases we may try many different orderings of the same actions before realizing there is no solution ● Least-commitment strategy: don’t commit to orderings, instantiations, etc., until necessary Motivation a b c b a b a b a c b c a c b goal … … … … … … dead end dead end dead end dead end dead end dead endDana 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 ● Basic idea ● Open goals ● Threats ● The PSP algorithm ● Long example ● CommentsDana 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 Plan-Space Planning - Basic Idea ● Backward search from the goal ● Each node of the search space is a partial plan » A set of partially-instantiated actions » A set of constraints ◆ Make more and more refinements, until we have a solution ● Types of constraints: ◆ precedence constraint: a must precede b ◆ binding constraints: » inequality constraints, e.g., v1 ≠ v2 or v ≠ c » equality constraints (e.g., v1 = v2 or v = c) and/or substitutions ◆ causal link: » use action a to establish the precondition p needed by action b ● How to tell we have a solution: no more flaws in the plan ◆ Will discuss flaws and how to resolve them foo(x) Precond: … Effects: p(x) bar(y) Precond: ¬p(y) Effects: … baz(z) Precond: p(z) Effects: … p(z) x ≠ y x = zDana 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 ● Open goal: ◆ An action a has a precondition p that we haven’t decided how to establish ● Resolving the flaw: ◆ Find an action b • (either already in the plan, or insert it) ◆ that can be used to establish p • can precede a and produce p ◆ Instantiate variables and/or constrain variable bindings ◆ Create a causal link Flaws: 1. Open Goals p(z) p(x) foo(x) Precond: … Effects: p(x) baz(z) Precond: p(z) Effects: … foo(x) Precond: … Effects: p(x) baz(z) Precond: p(z) Effects: …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 Flaws: 2. Threats ● Threat: a deleted-condition interaction ◆ Action a establishes a precondition (e.g., pq(x)) of action b ◆ Another action c is capable of deleting p ● Resolving the flaw: ◆ impose a constraint to prevent c from deleting p ● Three possibilities: ◆ Make b precede c ◆ Make c precede a ◆ Constrain variable(s) to prevent c from deleting p clobber(y) Precond: … Effects: ¬p(y) foo(x) Precond: … Effects: p(x) baz(x) Precond: p(x) Effects: … p(x)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 The PSP Procedure ● PSP is both sound and complete ● It returns a partially ordered solution plan ◆ Any total ordering of this plan will achieve the goals ◆ Or could execute actions in parallel if the environment permits itDana 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 Example ● Similar (but not identical) to an example in Russell and Norvig’s Artificial Intelligence: A Modern Approach (1st edition) ● Operators: ◆ Start Precond: none Effects: At(Home), sells(HWS,Drill), Sells(SM,Milk), Sells(SM,Banana) ◆ Finish Precond: Have(Drill), Have(Milk), Have(Banana), At(Home) ◆ Go(l,m) Precond: At(l) Effects: At(m), ¬At(l) ◆ Buy(p,s) Precond: At(s), Sells(s,p) Effects: Have(p) Start and Finish are dummy actions that we’ll use instead of the initial state and goalDana 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 Example (continued) ● Need to give PSP a plan π as its argument ◆ Initial plan: Start, Finish, and an ordering constraint Sells(SM,Milk), Sells(SM,Bananas) At(Home), Sells(HWS,Drill), Have(Drill) Have(Milk) Have(Bananas) Start Finish Effects: Precond: At(Home)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 Example (continued) ● The first three refinement steps ◆ These are the only possible ways to establish the Have preconditions At(s1) At(s2) At(s3) Buy(Drill, s1) Have(Drill) Start Buy(Drill, s1) Finish Have(Milk) Have(Bananas) Sells(s1, Drill) Sells(s2,Milk) Sells(s3,Bananas) Why don’t!we use Start to establish At(Home)? At(Home) Buy(Bananas, SM) Buy(Milk, SM)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/ 11 Example (continued) ● Three more refinement steps ◆ The only possible ways to establish the Sells preconditions At(HWS) At(SM) At(SM) Buy(Drill, s1) Have(Drill) Start Buy(Drill, HWS) Finish Have(Milk) Have(Bananas) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Bananas) At(Home) Buy(Bananas, SM) Buy(Milk, SM)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/ 12 Example (continued) ● Two more


View Full Document
Download Chapter 5 Plan-Space 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 5 Plan-Space 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 5 Plan-Space 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?