Cs 540 Lecture Notes_ Partial-order Planning

CS 540 Lecture Notes: Partial-Order Planning

1 / 10

http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html

University of Wisconsin - Madison

CS 540 Lecture Notes

C. R. Dyer

Partial-Order Planning (Chapter 11) Partial-Order Planning Total-Order vs. Partial-Order Planners Any planner that maintains a partial solution as a totally ordered list of steps found so far is called a total-order planner, or a linear planner. Alternatively, if we only represent partial-order constraints on steps, then we have a partial-order planner, which is also called a non-linear planner. In this case, we specify a set of temporal constraints between pairs of steps of the form S1 < S2 meaning that step S1 comes before, but not necessarily immediately before, step S2. We also show this temporal constraint in graph form as S1 +++++++++> S2

STRIPS is a total-order planner, as are situation-space progression and regression planners Principle of Least Commitment The principle of least commitment is the idea of never making a choice unless required to do so. In other words, only do something if it's necessary. The advantage of using this principle is that we try to avoid doing work that might have to be undone later, hence avoiding wasted work. In planning, one application of this principle is to never order plan steps unless it's necessary for some reason. So, partial-order planners exhibit this property because constraints ordering steps will only be inserted when necessary. On the other hand, situation-space progression planners make commitments about the order of steps as they try to find a solution and therefore may make mistakes from poor guesses about the right order of steps. Representing a Partial-Order Plan A partial-order plan will be represented as a graph that describes the temporal constraints between plan steps selected so far. That is, each node will represent a single step in the plan (i.e., an instance of one of the operators), and an arc will designate a temporal constraint between the two steps connected by the arc. For example, S1 ++++++++> S2 ++++++++++> S5 |\ ^ | \++++++++++++++++| | | v | ++++++> S3 ++++++> S4 ++++++

graphically represents the temporal constraints S1 < S2, S1 < S3, S1 < S4, S2 < S5, S3 < S4, and S4 < S5. This partial-order plan implicitly represents the following three total-order plans, each of which is consistent with all of the given constraints: [S1,S2,S3,S4,S5], [S1,S3,S2,S4,S5], and [S1,S3,S4,S2,S5].

Plan-Space Planning How to create partial-order plans? By searching through the plan space of (partial-order) plans. That is, each node in plan space represents a partial-order plan, and each arc in plan space represents a transformation from one plan to another plan, created, for example, by adding a new step or adding temporal constraints between existing steps.

2/16/2009 14:27

CS 540 Lecture Notes: Partial-Order Planning

2 / 10

http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html

Key Difference Between Plan-Space Planning and Situation-Space Planning In Situation-Space planners all operations, all variables, and all orderings must be fixed when each operator is applied. Plan-Space planners make commitments (i.e., what steps in what order) only as necessary. Hence, Plan-Space planners do least-commitment planning. Start Node in Plan Space The initial plan is created from the initial state description and the goal description by creating two "pseudo-steps:" 1. Start P: none E: all positive literals defining the initial state

2. Finish P: literals defining the conjunctive goal to be achieved E: none

and then creating the initial plan as: Start ---------> Finish Searching Through Plan Space There are two main reasons why a given plan may not be a solution: 1. Unsatisfied goal. That is, there is a goal or sub-goal that is not satisfied by the current plan steps. 2. Possible threat caused by a plan step that could cause the undoing of a needed goal if that step is done at the wrong time So, define a set of plan modification operators that detect and fix these problems.

Example Goal: Set the table, i.e., on(Tablecloth) ^ out(Glasses) ^ out(Plates) ^ out(Silverware) Initial State: clear(Table) Operators: 1. Lay-tablecloth P: clear(Table) E: on(Tablecloth), ~clear(Table)

2. Put-out(x) P: none E: out(x), ~clear(Table)

Searching for a Solution in Plan Space 1. Initial Plan Start -----------> Finish

2. Solve 4 unsolved goals in Finish by adding 4 new steps with the minimal temporal constraints possible: on(Tablecloth) Start ------> S1: Lay-tablecloth ------------------------->Finish \ \ \ out(Glasses) ^ ^ ^ \ \ \----> S2: Put-out(Glasses) -----------------| | | \ \ out(Plates) / / \ \-----> S3: Put-out(Plates) ------------------/ / \ out(Silverware) / \------> S4: Put-out(Silverware) ---------------/

3. Solve unsolved subgoal clear(Table) which is a precondition of step S1: 2/16/2009 14:27

CS 540 Lecture Notes: Partial-Order Planning

3 / 10

http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html

clear(Table) on(Tablecloth) Start -----------> S1: Lay-tablecloth ----------------------->Finish \ \ \ out(Glasses) ^ ^ ^ \ \ \---------> S2: Put-out(Glasses) ----------------| | | \ \ out(Plates) | | \ \----------> S3: Put-out(Plates) ------------------/ | \ out(Silverware) / \-----------> S4: Put-out(Silverware) ---------------/

4. Fix threats caused by steps S2, S3, and S4 on the link from Start to S1. That is, clear(Table) is a necessary precondition of S1 that is created by step Start. But S2 causes clear(Table) to be deleted (negated), so if S2 came before S1, clear(Table) wouldn't be true and step S1 couldn't be performed. Therefore, add a temporal constraint that forces S2 to come anytime after S1. That is, add constraint S1 < S2. Similarly, add S1 < S3, and S1 < S4, resulting in the new plan: clear(Table) on(Tablecloth) Start -----------> S1: Lay-tablecloth ---------------------->Finish | | | |\--|---| ^ ^ ^ | | | | | v out(Glasses) | | | | | |--------------+---+-> S2: Put-out(Glasses) --------------/ | | | | | v out(Plates) / | | |----------------+-> S3: Put-out(Plates) --------------------/ | | v out(Silverware) / |---------------> S4: Put-out(Silverware) ----------------------/

5. No threats and no unsolved goals in this plan, so it is a complete plan (i.e., a solution to the planning problem). Any total ordering of the steps implied by this partial-order plan is a solution plan. Here, there are six possible plans, where the first step is S1, and the steps S2, S3, and S4 follow in any order. (Don't include the pseudo-steps Start and Finish.)

Interleaving vs. Non-Interleaving of Sub-Plan Steps Given a conjunctive goal, G1 ^ G2, if the steps that solve G1 must either all come before or all come after the steps that solve G2, then the planner is called a non-interleaving planner. Otherwise, the planner allows interleaving of sub-plan steps. This constraint is different from the issue of partial-order vs. total-order planners. STRIPS is a non-interleaving planner because of its use of a stack to order goals to be achieved. While a pure non-interleaving planner cannot solve the Sussman Anomaly, an interleaving planner can solve it by interleaving the steps associated with solving the two goals, on(A,B) and on(B,C). For example, the following plan solves this problem: unstack(C,A), Pickup(B), Stack(B,C), Stack(A,B). Notice that the first and last steps of this plan were created as part of the sub-plan to solve on(A,B), and the middle two steps are used to solve on(B,C).

Partial-Order Planner (POP) Algorithm function pop(initial-state, conjunctive-goal, operators) // non-deterministic algorithm plan = make-initial-plan(initial-state, conjunctive-goal); loop: begin if solution?(plan) then return plan; (S-need, c) = select-subgoal(plan) ; // choose an unsolved goal choose-operator(plan, operators, S-need, c); // select an operator to solve that goal and revise plan resolve-threats(plan); // fix any threats created end end function solution?(plan)

2/16/2009 14:27

CS 540 Lecture Notes: Partial-Order Planning

4 / 10

http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html

if causal-links-establishing-all-preconditions-of-all-steps(plan) and all-threats-resolved(plan) and all-temporal-ordering-constraints-consistent(plan) and all-variable-bindings-consistent(plan) then return true; else return false; end function select-subgoal(plan) pick a plan step S-need from steps(plan) with a precondition c that has not been achieved; return (S-need, c); end procedure choose-operator(plan, operators, S-need, c) // solve "open precondition" of some step choose a step S-add by either Step Addition: adding a new step from operators that has c in its Add-list or Simple Establishment: picking an existing step in Steps(plan) that has c in its Add-list; if no such step then return fail; add causal link "S-add --->c S-need" to Links(plan); add temporal ordering constraint "S-add < S-need" to Orderings(plan); if S-add is a newly added step then begin add S-add to Steps(plan); add "Start < S-add" and "S-add < Finish" to Orderings(plan); end end procedure resolve-threats(plan) foreach S-threat that threatens link "Si --->c Sj" in Links(plan) begin // "declobber" threat choose either Demotion: add "S-threat < Si" to Orderings(plan) or Promotion: add "Sj < S-threat" to Orderings(plan); if not(consistent(plan)) then return fail; end end

Plan Modification Operations The above algorithm uses four basic plan modification operations to revise a plan, two for solving a goal and two for fixing a threat: Establishment -- "Solve an Open Precondition" (i.e., unsolved goal) If a precondition p of a step S does not have a causal link to it, then it is not yet solved. This is called an open precondition. Two ways to solve: Simple Establishment Find an existing step T prior to S in which p is necessarily true (i.e., it's in the Effects list of T). Then add causal link from T to S. Step Addition Add a new plan step T that contains in its Effects list p. Then add causal link from T to S. Declobbering -- Threat Removal A threat is a relationship between a step S3 and a causal link S1 --->p S2, where p is a precondition in step S2, that has the following form:

2/16/2009 14:27

CS 540 Lecture Notes: Partial-Order Planning

5 / 10

http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html

-------> S1 --------->p S2 | | -------> S3 ~p

That is, step S3 has effect ~p and from the temporal links could possibly occur in-between steps S1 and S2, which have a causal link between them. If this occurred, then S3 would "clobber" the goal p "produced" by S1 before it can be "consumed" by S2. Fix by ensuring that S3 cannot occur in the "protection interval" in between S1 and S2 by doing either of the following: Promotion Force threatening step to come after the causal link. I.e., add temporal link S2 < S3. Demotion Force threatening step to come before the causal link. I.e., add temporal link S3 < S1.

Example -- Solving the Sussman Anomaly using the POP Algorithm In the following plans, links shown as -----> are causal links and are labeled with the open precondition that is solved by this link. Links shown as ++++++> are temporal links, though most of these are not shown in order to keep the figures neater. Of course, for each causal link there should also be a temporal link connecting the same two nodes, but this is not shown.

1. Create initial-plan: Start +++++++++++++> Finish P: none P: on(A,B) E: on(C,A) on(B,C) handempty ontable(A) ontable(B) clear(B) clear(C)

2. Solve open precondition on(A,B) in step Finish by Step Addition using Stack(A,B). Notes: a. Stack is the only operator that can be used to solve this open precondition. b. The figure below should include a temporal link from the new step to Finish, but it is not included in order to keep the figure more readable. Also, the temporal link connecting Start to Finish has been omitted for the same reason. on(A,B) Start +++++++++++++> Stack(A,B) ------------> Finish P: none P: holding(A) P: on(A,B) E: on(C,A) clear(B) on(B,C) handempty E: on(A,B) ontable(A) clear(A) ontable(B) handempty clear(B) ~holding(A) clear(C) ~clear(B)

3. Solve open precondition on(B,C) in step Finish by Step Addition using Stack(B,C). Notes: a. Stack is the only operator applicable here. b. The figure below should include temporal links from Start to the new step, as well as from the new step to Finish, but these are not explicitly shown in order to keep the figure more readable.

2/16/2009 14:27

CS 540 Lecture Notes: Partial-Order Planning

http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html

on(A,B) Start +++++++++++++> Stack(A,B) ------------> Finish P: none P: holding(A) ^ P: on(A,B) E: on(C,A) clear(B) | on(B,C) handempty E: on(A,B) | ontable(A) clear(A) | ontable(B) handempty | clear(B) ~holding(A) | clear(C) ~clear(B) | | on(B,C) | Stack(B,C) ------------| P: holding(B) clear(C) E: on(B,C) clear(B) handempty ~holding(B) ~clear(C)

4. Solve open precondition holding(B) in step Stack(B,C) by Step Addition using Pickup(B). Notes: a. There are two possible operators (Pickup and Unstack) that could be used to solve this open precondition, so this is a choice point for the algorithm. b. The figure below should include temporal links from Start to the new step, as well as from the new step to Stack(B,C), but these are not explicitly shown in order to keep the figure more readable. on(A,B) Start +++++++++++++> Stack(A,B) ------------> Finish P: none P: holding(A) ^ P: on(A,B) E: on(C,A) clear(B) | on(B,C) handempty E: on(A,B) | ontable(A) clear(A) | ontable(B) handempty | clear(B) ~holding(A) |on(B,C) clear(C) ~clear(B) | | holding(B) | Pickup(B) -----------> Stack(B,C) P: ontable(B) P: holding(B) clear(B) clear(C) handempty E: on(B,C) E: holding(B) clear(B) ~ontable(B) handempty ~clear(B) ~holding(B) handempty ~clear(C)

5. Solve open precondition holding(A) in step Stack(A,B) by Step Addition using Pickup(A). Notes: a. There are two possible operators (Pickup and Unstack) for solving this open precondition, so this is a choice point for the algorithm. b. The figure below should include temporal links from Start to the new step, as well as from the new step to Stack(A,B), but these are not explicitly shown in order to keep the figure more readable. holding(A) on(A,B) Start ++++++++> Pickup(A) ----------> Stack(A,B) --------> Finish P: none P: ontable(A) P: holding(A) ^ P: on(A,B) E: on(C,A) clear(A) clear(B) | on(B,C) handempty handempty E: on(A,B) | ontable(A) E: holding(A) clear(A) | ontable(B) ~clear(A) handempty | clear(B) ~ontable(A) ~holding(A) |on(B,C)

6 / 10

2/16/2009 14:27

CS 540 Lecture Notes: Partial-Order Planning

clear(C)

http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html

~handempty

~clear(B)

| | |---------| holding(B) | Pickup(B) -----------> Stack(B,C) P: ontable(B) P: holding(B) clear(B) clear(C) handempty E: on(B,C) E: holding(B) clear(B) ~ontable(B) handempty ~clear(B) ~holding(B) handempty ~clear(C)

6. Solve open precondition clear(A) in step Pickup(A) using Step Addition with Unstack(C,A): Start P: none E: on(C,A) handempty ontable(A) ontable(B) clear(B) clear(C) clear(A) holding(A) on(A,B) Unstack(C,A) ----> Pickup(A) ----------> Stack(A,B) -------> Finish P: clear(C) P: ontable(A) P: holding(A) ^ P: on(A,B) on(C,A) clear(A) clear(B) | on(B,C) handempty handempty E: on(A,B) | E: holding(C) E: holding(A) clear(A) | clear(A) ~clear(A) handempty | ~clear(C) ~ontable(A) ~holding(A) |on(B,C) ~on(C,A) ~handempty ~clear(B) | ~handempty | |-----------| holding(B) | Pickup(B) -----------> Stack(B,C) P: ontable(B) P: holding(B) clear(B) clear(C) handempty E: on(B,C) E: holding(B) clear(B) ~ontable(B) handempty ~clear(B) ~holding(B) handempty ~clear(C)

7. Solve open precondition handempty in Pickup(B) using Step Addition with Putdown(C): Start P: none E: on(C,A) handempty ontable(A) ontable(B) clear(B) clear(C) clear(A) holding(A) on(A,B) Unstack(C,A) ----> Pickup(A) ----------> Stack(A,B) -------> Finish P: clear(C) P: ontable(A) P: holding(A) ^ P: on(A,B) on(C,A) clear(A) clear(B) | on(B,C) handempty handempty E: on(A,B) | E: holding(C) E: holding(A) clear(A) | clear(A) ~clear(A) handempty | ~clear(C) ~ontable(A) ~holding(A) |on(B,C) ~on(C,A) ~handempty ~clear(B) | ~handempty | |-----------| handempty holding(B) | Putdown(C) --------> Pickup(B) -----------> Stack(B,C)

7 / 10

2/16/2009 14:27

CS 540 Lecture Notes: Partial-Order Planning

8 / 10

P: holding(C) E: ontable(C) clear(C) handempty ~holding(C)

http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html

P: ontable(B) clear(B) handempty E: holding(B) ~ontable(B) ~clear(B) handempty

P: holding(B) clear(C) E: on(B,C) clear(B) handempty ~holding(B) ~clear(C)

8. Solve open preconditions using Simple Establishment for each of the following:

Open Precond

in Step

Solved by Step

clear(C)

Unstack(C,A)

Start

on(C,A)

Unstack(C,A)

Start

handempty

Unstack(C,A)

Start

For each of the above, add a causal link from Start to Unstack(C,A). 9. Detect threat ~clear(C) in step Stack(B,C) to causal link from Start to Unstack(C,A). Fix by Promotion: add temporal link from Unstack(C,A) to Stack(B,C) so that Stack(B,C) forced to come after Unstack(C,A). Start ---------P: none | E: on(C,A) | handempty |clear(C) ontable(A) |on(C,A) ontable(B) |handempty clear(B) | clear(C) | | |----------| | V clear(A) holding(A) on(A,B) Unstack(C,A) ----> Pickup(A) ----------> Stack(A,B) -------> Finish P: clear(C) + P: ontable(A) P: holding(A) ^ P: on(A,B) on(C,A) + clear(A) clear(B) | on(B,C) handempty + handempty E: on(A,B) | E: holding(C) + E: holding(A) clear(A) | clear(A) + ~clear(A) handempty | ~clear(C) + ~ontable(A) ~holding(A) |on(B,C) ~on(C,A) ++++ ~handempty ~clear(B) | ~handempty ++++++++++++++++++++++++++ | + |-----------| handempty holding(B) v | Putdown(C) --------> Pickup(B) -----------> Stack(B,C) P: holding(C) P: ontable(B) P: holding(B) E: ontable(C) clear(B) clear(C) clear(C) handempty E: on(B,C) handempty E: holding(B) clear(B) ~holding(C) ~ontable(B) handempty ~clear(B) ~holding(B) handempty ~clear(C)

10. Solve open preconditions using Simple Establishment for each of the following:

2/16/2009 14:27

CS 540 Lecture Notes: Partial-Order Planning

9 / 10

http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html

Open Precond

in Step

Solved by Step

Holding(C)

Putdown(C)

Unstack(C,A)

ontable(B)

Pickup(B)

Start

clear(B)

Pickup(B)

Start

handempty

Pickup(B)

Putdown(C)

For each of the above, add a causal link. 11. Detect threat ~handempty at step Pickup(A) to causal link from Putdown(C) to Pickup(B). Fix by Promotion: add temporal link from Pickup(B) to Pickup(A). Note: This fix means there is no threat at step Stack(A,B) to causal link from Start to Pickup(B) because now Stack(A,B) is after Pickup(A) which is after Pickup(B), so Stack(A,B) must occur after Pickup(B). Start ---------P: none | E: on(C,A) | handempty |clear(C) ontable(A) |on(C,A) ontable(B) |handempty clear(B) | clear(C) | | |----------| | V clear(A) holding(A) on(A,B) Unstack(C,A) ----> Pickup(A) ----------> Stack(A,B) -------> Finish | P:clear(C) + ^ P: ontable(A) P: holding(A) ^ P: on(A,B) | on(C,A) + + clear(A) clear(B) | on(B,C) | handempty + + handempty E: on(A,B) | | E:holding(C) + + E: holding(A) clear(A) | | clear(A) + + ~clear(A) handempty | | ~clear(C) + + ~ontable(A) ~holding(A) |on(B,C) | ~on(C,A) ++++ ~handempty ~clear(B) | | ~handempty + +++++++++++++++++++++++++ | | + + | |holding(C) ++++ + |------------| | + + | v handempty + holding(B) v | Putdown(C) --------> Pickup(B) -----------> Stack(B,C) P: holding(C) P: ontable(B) P: holding(B) E: ontable(C) clear(B) clear(C) clear(C) handempty E: on(B,C) handempty E: holding(B) clear(B) ~holding(C) ~ontable(B) handempty ~clear(B) ~holding(B) handempty ~clear(C)

12. Solve open preconditions using Simple Establishment for each of the following:

Open Precond

in Step

Solved by Step

clear(C)

Stack(B,C)

Putdown(C)

2/16/2009 14:27

CS 540 Lecture Notes: Partial-Order Planning

10 / 10

http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html

ontable(A)

Pickup(A)

Start

handempty

Pickup(A)

Stack(B,C)

clear(B)

Stack(A,B)

Stack(B,C)

For each of the above, add a causal link. Start ---------------------P: none | | E: on(C,A) | | handempty |clear(C) |ontable(A) ontable(A) |on(C,A) | ontable(B) |handempty | clear(B) | | clear(C) | | | |------| |----------| | | | V clear(A) v holding(A) on(A,B) Unstack(C,A) ----> Pickup(A) ----------> Stack(A,B) -------> Finish | P:clear(C) + ^ ^P: ontable(A) ^ P: holding(A) ^ P: on(A,B) | on(C,A) + + | clear(A) | clear(B) | on(B,C) | handempty + + | handempty | E: on(A,B) | | E:holding(C) + + |E: holding(A) | clear(A) | | clear(A) + + | ~clear(A) | handempty | | ~clear(C) + + | ~ontable(A) | ~holding(A) |on(B,C) | ~on(C,A) + + | ~handempty | ~clear(B) | | ~handempty + + |------| |--------| | | + + | handempty | | | +++++++++ |--------------------| | | | + + | |clear(B) | |holding(C) +++++ ++++++++++++++++++++++ | | | | + + | | |--------| v handempty + holding(B) v | | | Putdown(C) --------> Pickup(B) -----------> Stack(B,C) P: holding(C) \ P: ontable(B) ^ P: holding(B) E: ontable(C) \ clear(B) | clear(C) clear(C) \ handempty | E: on(B,C) handempty \ E: holding(B) | clear(B) ~holding(C) \ ~ontable(B) | handempty | ~clear(B) | ~holding(B) | handempty | ~clear(C) | | | clear(C) | |------------------------

13. No open preconditions and no threats, so halt. The only consistent total ordering that is implied from the final complete partial-order plan is: Unstack(C,A), Putdown(C), Pickup(B), Stack(B,C), Pickup(A), Stack(A,B). Notice that this interleaves the steps in the solutions to the two original goals, on(A,B) and on(B,C).

POP Summary POP algorithm is sound and complete. That is, if the algorithm returns a "complete" plan, then any total ordering implied by it solves the planning problem (soundness). And, if there is a solution to a planning problem, the POP algorithm will eventually solve it (completeness). Usual implementation of POP is to maintain a queue of partial plans, and sort the queue using some kind of ranking function. Copyright © 1996-2003 by Charles R. Dyer. All rights reserved.

2/16/2009 14:27