Plan Spaces and Partial-Order Planning

Plan Spaces and Partial-Order Planning

Plan generation can be done by using two approaches, 

1. State space search. 
2. Plan-space search.

1) State-Space Search :

It uses STRIP rules in a space of formulas inorder to generate successor set of formulas and continues this procedure Until it produces a state description which satisfies goal formula. t is shown in Fig. 3.10.8.

Fig. 3.10.8 State-Space Search 

2) Plan-Space Search :

If the search is in set of plans then instead of using STRIPS operators, the operators are used which will convert the plans which are not complete, not instantiated and not adequate into improved version of plans, this process continues until the goal description is achieved. The plan-space search can be shown in Fig. 3.10.9. 

Fig. 3.10.9 Plan-Space Search 

The operations that are performed on plan-space to articulate the plans are, 

• i) New steps are added to the plan. 
• ii) The steps in the plan are reordered
• iii) A plan which is partially ordered is converted into fully ordered 
• iv) A plan schema which consists of un-instantiated variables is converted into some instance of the schema.

These operations are be illustrated in the Fig. 3.10,10. 

Fig. 3.10.10 Plan Transforming Operators 

• By using Systematic Nonlinear Planning (SNLP) technique let us explain how the plan-space search methods are applied to Sussman Anomaly.
• Here the basic components used are STRIPS rules.
• A graph representation of a STRIPS rule is shown in Fig. 3.10.11. 

Fig. 3.10.11 Graphical Representation of a STRIPS Rule 

• In the graphical representation the oval shape nodes are used to mention of the STRIPS operator.
• The box shaped nodes are used to represent the effects and precondition.
• The boxes above the operator denote the effects of operation and the boxes below denote the preconditions for the operation- to be performed.
• Start and finish are used to represented the initial and goal wffs.
• The effect of finish is Nil as goal wff is satisfied, the precondition of start is denoted by W. 
• The start and finish graphs, for Sussman Anomaly is represented as in Fig. 3.10.12. 

Fig. 3.10.12 Graphical Representation of Finish and Start Rules  

• The Fig. 3.10.12 just gives the initial and goal states but does not give the plan. 
• Now we search for a plan to reach goal wff using the plan-transformation operators.
• To achieve goal wff one of its conjuncts have to achieved first, so on we select a conjunct and inorder to reach it we extend the initial plan structure by addition of a rule.
• Let us select On(P, Q) conjunct to reach the operation that must be performed is move(P, x, R).
• If this move(Q, x, P) have to be added its preconditions and effects should also be added and linked o the conjunct On(Q, P) as this has to be achieved.
• The rule instance of move(P, y, Q) is shown in Fig. 3.10.13. 

Fig. 3.10.13  Rule Instance of move(P, x, Q) 

• Now this rule instance is added to precondition On(P, Q) of finish in Fig. 3.10.12 to generate next plan structure.
• The next step is to instantiate x, this can be instantiated to F and a link is established between On(P, F) in the initial-state and On(P, F) of instantiated move operator. 
• There can also be a link between two Clear(Q)'s.
• In order to move(P, F, Q) we-must have Clear(P) established. So we add rule instance move(u, P, v) that is something which is on P must be moved on to somewhere.
• The move(u, P, v) can be instantiated by substituting u to R and v to F so that links can be established to initial state.
• All these steps can be shown in Fig. 3.10.14.
• In the Fig. 3.10.14 the two move operators are labelled as a and b in order to mention that b should occur before a. 

Fig. 5.2.14 A Subsequent Plan Structure 

• The symbol < is used to represent 'before' action, i.e., .b < a.
• This has to be mentioned because, in some cases the effects of the move operations may cause threats. In the move operations performed in the case as in Fig. 3.10.14 as Clear(F), product of move(P, F, Q) and On(R, F), product of move(R, P, F) does not cause a threat as long as they do not oppose some conditions which have to be true. 
• As one of the conjunct On(P, Q) is satisfied now we select other conjunct of goal wff that is On(Q, R). 
• To satisfy the condition move(Q, y, R) is used.
• Now we instantiate y to F so that it can be connected to initial conditions directly as Q is clear, R is clear in initial conditions.
• The Fig. 3.10.15 shows the plan structure which is resulted from all the Operations. 

Fig. 3.10.15 Later Stage of Plan Structure with Threat Arcs  

• In the Fig. 3.10.15 a, b, c are partially ordered. 
• If they are not executed in correct order the effect of one operation may undo the preconditions of other operation. 
• These effects which may cause danger are represented by threat arcs denoted with a dashed line in Fig. 3.10.15. 
• In the plan-structure the threat is caused by move(P, F, Q) as it Clear(B) which is one of the precondition of move(Q, F, R) if this 'a' occurs before 'c'. 
• Another threat is by 'c' that is move(Q, P, R) which deletes Clear(R) where it is precondition of move(R, P, F) i.e. 'b'. 
• So here 'a' threatens 'c' if a occurs before c and c threatens b, if c occurs before b. 
• So a constraint should be used to impose correct ordering of operations so that the threat arcs are discharged. 
• The constraint imposed in this case will be b < c; c < a therefore the ordering constraint is b < c < a. 
• If the threat arcs are discharged and all the conditions required by the operators are satisfied the plan is said to be complete. 
• Therefore, the final plan is, 

                {move(R, P, F), move(Q, F, R), move(P, F, Q)}