text: Are you sure?
  This action might not be possible to undo. Are you sure you want to continue?. 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.
  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 ++++++++++> |\ | \++++++++++++++++| | v ++++++> S3 ++++++> S4 ++++++ S5 ^ | |
  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 totalorder 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].
  9.5 Plan-Space Planning Algorithms
  An alternative is to search through the space of plans rather than a space of situations. That is, we start with a simple, incomplete plan, which we call a partial plan. Then we consider ways of expanding the partial plan until we come up with a complete plan that
  Version 2 CSE IIT,Kharagpur
  solves the problem. We use this approach when the ordering of sub-goals affects the solution. Here one starts with a simple, incomplete plan, a partial plan, and we look at ways of expanding the partial plan until we come up with a complete plan that solves the problem. The operators for this search are operators on plans: adding a step, imposing an ordering that puts one step before another, instantiating a previously unbound variable, and so on. Therefore the solution is the final plan. Two types of operators are used:
  •
  Refinement operators take a partial plan and add constraints to it. They eliminate some plans from the set and they never add new plans to it. A modification operator debugs incorrect plans that the planner may make, therefore we can worry about bugs later.
  •
  9.5.1 Representation of Plans
  A plan is formally defined as a data structure consisting of the following 4 components: 1. A set of plan steps 2. A set of step ordering constraints 3. A set of variable binding constraints 4. A set of causal links Example: Plan( STEPS:{S1:Op(ACTION: Start), S2:Op(ACTION: Finish, PRECOND: Ontable(c), On(b,c), On(a,b) }, ORDERINGS: {S1 < S2},.
  Version 2 CSE IIT,Kharagpur
  Start Node in Plan Space The initial plan is created from the initial state description and the goal description by creating two "pseudo-steps:" Start
  P: none E: all positive literals defining the initial state
  Finish
  P:
  • • •
  Goal: Set the table, i.e., on(Tablecloth) ^ out(Glasses) ^ out(Plates) ^ out(Silverware) Initial State: clear(Table)
  Operators: 1. Lay-tablecloth 2. P: clear(Table)
  E: on(Tablecloth), ~clear(Table)
  3. Put-out(x) 4. P: none
  E: out(x), ~clear(Table) •
  Searching for a Solution in Plan Space
  Version 2 CSE IIT,Kharagpur) ---------------/
  3. Solve unsolved subgoal clear(Table) which is a precondition of step S1:
  clear(Table):
  Version 2 CSE IIT,Kharagpur
  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 noninterleaving planner because of its use of a stack to order goals to be achieved.
  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)
  Version 2 CSE IIT,Kharagpur
  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: o 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.
  Version 2 CSE IIT,Kharagpur
  •:
  o -------> S1 --------->p S2 | | -------> S3 ~p
  • • •
  That is, step S3 has effect ~p and from the temporal links could possibly occur inbetween.
  9.5.2 Simple Sock/Shoe Example
  In the following example, we will show how the planning algorithm derives a solution to a problem that involves putting on a pair of shoes. In this problem scenario, Pat is walking around his house in his bare feet. He wants to put some shoes on to go outside. Note: There are no threats in this example and therefore is no mention of checking for threats though it a necessary step To correctly represent this problem, we must break down the problem into simpler, more atomic states that the planner can recognize and work with. We first define the Start operator and the Finish operator to create the minimal partial order plan. As mentioned before, we must simplify and break down the situation into smaller, more appropriate states. The Start operator is represented by the effects: ~LeftSockOn, ~LeftShoeOn, ~RightSockOn, and ~RightShoeOn. The Finish operator has the preconditions that we wish to meet: LeftShoeOn and RightShoeOn. Before we derive a plan that will allow Pat to reach his goal (i.e. satisfying the condition of having both his left and right shoe on) from the initial state of having nothing on, we need to define some operators to get us
  Version 2 CSE IIT,Kharagpur
  there. Here are the operators that we will use and the possible state (already mentioned above)..
  Start ~LeftSockOn, ~LeftShoeOn, ~RightSockOn, ~RightShoeOn
  RightSockOn, LeftSockOn PutRShoeOn( ) RightShoeOn
  LeftShoeOn, RightShoeOn Finish
  Version 2 CSE IIT,Kharagpur ‘RightSockOn’ state. Since the precondition of the ‘PutRightSockOn()’ operator is one of the effects of the Start operator, we can simply draw a causal link between the two operators. These two steps can be repeated for Pat’s.
  Version 2 CSE IIT,Kharagpur
  Questions
  1. Consider the world of Shakey the robot, as shown below.
  Shakey has the following six actions available: • Go(x,y), which moves Shakey from x to y. It requires Shakey to be at x and that x and y are locations in the same room. By convention a door between two rooms is in both of them, and the corridor counts as a room. • Push(b,x,y), which allows Shakey to push a box b from location x to location y. Both Shakey and the box must be at the same location before this action can be used. • ClimbUp(b,x), which allows Shakey to climb onto box b at location x. Both Shakey and the box must be at the same location before this action can be used. Also Shakey must be on the Floor. • ClimbDown(b,x), which allows Shakey to climb down from a box b at location x. Shakey must be on the box and the box must be in location x before this action can be used. • TurnOn(s,x), which allows Shakey to turn on switch s which is located at location x. Shakey must be on top of a box at the switch’s location before this action can be used. • TurnOff(s,x), which allows Shakey to turn off switch s which is located at location x. Shakey must be on top of a box at the switch’s
  Version 2 CSE IIT,Kharagpur
  1. STRIPS description of the operators are:
  2. The initial state is:
  Version 2 CSE IIT,Kharagpur
  3. The plan is
  4. Conflicts: • ActionC cannot come between Start and ActionA. •
  Version 2 CSE IIT,Kharagpur
  Start, A, B, C, D, Finish Start, A, C, B, D, Finish
  Version 2 CSE IIT,Kharagpur