Recursive STRIPS-Strips Planning Systems

 Strips Planning Systems -Recursive STRIPS 

• Divide and conquer method is used for forward search when the goal condition consists of a combination of literals.
• This is a recursive process, where one of the conjuncts is achieved first and then the next one and so on. 
• In order make the forward search efficient we identify islands. An island in a search space is a state description in which one of the conjuncts is satisfied. 
• Operations are applied to the island which is identified in order to get a state description so that the corresponding conjunct is satisfied. The process then continues towards another island. 
• The search space islands are exploited, by a system called General Problem Solver (GPS). 
• A process called "Means-end-analysis" has found the operators for achieving islands. 
• In this technique, an instance of one of the conjunct in the goal condition is selected and the corresponding STRIPS rule which achieves it is also selected. 
• To apply the rule the preconditions which are needed are created by recursively working towards it until it is satisfied after which an operator is applied to create an island. 
• This process continues to identify another is-and and so on. 

THE RECURSIVE PROGRAM STRIPS 

    Here it is explained how to solve a conjunctive goal formula g, 

STRIPS(g): A global data structure S_d is used by this procedure which consists of ground literals. S_d is first set to initial state description and changed while the procedure is applied. 

1. repeat: The procedure is repeated until goal state g is achieved. A substitution σ is produced by test in step 9, so that some of the conjuncts of gσ may appear in S_d. While performing test several substitutions are made so the test may become possible point for backtracking.
2. e ← : It is an element of gσ such that S_d, |=/= e and acts as a point for backtracking. 
3. f ← : It is a STRIPS rule which contains a literal λ in its add list and combines with e with mgu s. It acts as another point of backtracking. 
4. f' ←  fs: It may not be a ground instance and may have contain variables in its precondition. 
5. p ←  : It is the precondition formula of f'. 
6. STRIPS(p): This call is a recursive call to produce a state description which may satisfy the sub-goal. The data structure S_d may change because of this call. 
7. f''←: This can be obtained by substitution in f' i.e. a ground instance of f' which is applicable in S_d. 
8. S_d ← : It is a result which is got by applying f" to S_d. S_d contains conjunction of ground literals. 
9. Until S_d |== g

Let us take an example to illustrate the working of the algorithm. Consider the Fig. 3.10.2. 

• If the goal state to be achieved is On(P, F) ∧ On(Q, F) ∧ On(R, Q). 
• No conjuncts that are present in the state description in Fig. 3.10.2 satisfy the goal test in step 9.
• If STRIPS selects On(P, F) as e. 
• The add list of STRIP contains On(P, F) for the rule instance move(P, x, F).
• The precondition of the rule instance move(P, x, F) is achieved by recursively calling STRIPS, i.e. Clear(P) ∧ Clear(F) ∧ On(P, x). 
• A substitution of R/x is produced by test in step 9-in the recursive call procedure.
• In the initial state description, we have both Clear(F) and On(P, R) so in order to achieve Clear(P) the rule move(y, P, .z) is selected.
• In order to achieve the preconditions for the rule the STRIPS is called recursively again and the precondition is Clear(y) ∧ Clear(z) ∧ Only(y,  P).
• By performing the test in step 9, we get Q/y and F/z as substitutions.
• In Clear(Q) ∧ Clear(F) ∧ On(Q, P) as every literal appears in the initial state description we can pop the recursive call which is made for the second time to apply an operator that is, move(Q, P, F), then the 'initial state description becomes, 

                On(Q, F) 

                On(P, R) 

                On(R, F)

                Clear(P) 

                Clear(Q)

                Clear(F)

• As now we have clear(P) then the operator move(P, R, F) in the recursive call made first can be applied. So the state description becomes, 

                On(Q, F) 

                On(P, F) 

                On(R, F) 

                Clear(P) 

                Clear(Q) 

                Clear(R) 

                Clear(F) 

• Again we perform the test is step 9, the conjunct that is present in the goal state and not present in the new state description is On(R, Q).
• The conjunct can be satisfied by again calling the recursive STRIP and note that the precondition for the operation move(R, F, Q) is satisfied. So this action is applied to get the goal state and the recursive STRIP process is terminated at this stage.