Planning-Goal Stack Algorithm

One of the earliest techniques is planning using goal stack. Problem solver uses single stack that contains

• sub goals and operators both
• sub goals are solved  linearly and then finally the conjoined sub goal is solved.

Plans generated by this method will contain complete sequence of operations for solving one goal followed by complete sequence of operations for the next etc.

Problem solver also relies on 

• A database that describes the current situation.
• Set of operators with precondition, add and delete lists. 

Let us assume that the goal to be satisfied is:

                    GOAL = G1 ^ G2 ^ … ^Gn

Sub-goals G1, G2, … Gn are stacked with compound goal G1 ^ G2 ^ …^ Gn at the bottom.

  

                  Top                        G1

                                                 G2

                                                   :

                                                  Gn 

                     Bottom                 G1 ^ G2 ^ … ^ G4

At each step of problem solving process, the top goal on the stack is pursued.

Algorithm

Find an operator that satisfies sub goal G1  (makes it true) and replace G1 by the operator.

• If more than one operator satisfies the sub goal then apply some heuristic to choose one.

In order to execute the top most operation, its preconditions are added onto the stack.

• Once preconditions of an operator are satisfied, then we are guaranteed that operator can be applied to produce a new state. 

• New state is obtained by using ADD and DELETE lists of an operator to the existing database.

Problem solver keeps tract of operators applied.

• This process is continued till the goal stack is empty and problem solver returns the plan of the problem.

 Goal Stack Example

  With this example,let us explain the working method of  Goal Stack Algorithm.

Initial State:  ON(B, A) ^ ONT(C) ^ ONT(A) ^ ONT(D) ^ CL(B) ^CL(C) ^ CL(D) ^ AE

Goal State:  ON(C, A) ^ ON(B, D) ^ ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE

We notice that following sub-goals in goal state are also true in initial state.

                        ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE 

Represent for the sake of simplicity - TSUBG.

Only sub-goals ON(C, A) & ON(B, D) are to be satisfied and finally make sure that TSUBG remains true.

Either start solving first ON(C, A) or ON(B, D). Let us solve first ON(C, A).

Goal Stack:

                                                ON(C, A)

                                                ON(B, D)

                                                ON(C, A) ^ ON(B, D)  ^ TSUBG  

• To solve ON(C, A), operation S(C, A) could only be applied.
• So replace ON(C, A) with S(C, A) in goal stack.

Goal Stack:

                                                S (C, A)

                                                ON(B, D)

                                                ON(C, A) ^ ON(B, D)  ^ TSUBG  

S(C, A) can be applied if its preconditions are true. So add its preconditions on the stack.

Goal Stack:

CL(A)

HOLD(C)                             Preconditions of STACK

CL(A)  ^  HOLD(C)

S (C, A)                                 Operator

ON(B, D)

ON(C, A) ^ ON(B, D)  ^ TSUBG

 

To do the S(C,A) operation all preconditions should be true. In the given problem CL(A) is not true.So,to make the state true ,replace CL(A) by U(B,A) and write the preconditions of Unstack operator.

Goal Stack: 

ON(B, A)

CL(B)                     Preconditions of  UNSTACK

AE

ON(B, A) ^ CL(B)  ^ AE

US(B, A)               Operator             

HOLD(C)                Preconditions of  STACK

CL(A) )  ^  HOLD(C)

S (C, A)                 Operator

ON(B, D)

ON(C, A) ^ ON(B, D)  ^ TSUBG

• ON(B, A), CL(B)  and AE are all true in initial state, so pop these along with its compound goal.

• Next pop top operator US(B, A) and produce new state by using its ADD and DELETE lists.

• Add US(B, A) in a queue of sequence of operators.

                       SQUEUE = US (B, A)

State_1:              

                ONT(A) ^ONT(C) ^ ONT(D) ^ HOLD(B) ^CL(A) ^ CL(C) ^ CL(D)

 

Goal Stack:

 

HOLD(C)                Preconditions of  STACK

CL(A) )  ^  HOLD(C)

S (C, A)                 Operator

ON(B, D)

ON(C, A) ^ ON(B, D)  ^ TSUBG 

To execute the S(C,A),all the preconditions of Stack operator should be true.But in this case HOLD(C) is not true .To make the state true use the operator S(B,D)

S(B,D)                                      Operator               

 HOLD(C)

CL(A) )  ^  HOLD(C)                Preconditions of  STACK

S (C, A)                                      Operator

ON(B, D)

ON(C, A) ^ ON(B, D)  ^ TSUBG 

Write down the preconditions of S(B,D)

Goal Stack

 

CL (D) ^ HOLD (B)             Preconditions of STACK

 

S(B,D)                                      Operator               

 

HOLD(C)

CL(A) )  ^  HOLD(C)                Preconditions of  STACK

S (C, A)                                      Operator

ON(B, D)

ON(C, A) ^ ON(B, D)  ^ TSUBG 

Add S(B, D) in a queue of sequence of operators.

                      
 SQUEUE = US (B, A), S (B, D)

State_2:              

                ONT(A) ^ONT(C) ^ ONT(D) ^ ON(B, D) ^ CL(A) ^ CL(C) ^ CL(B) ^ AE

 

Goal Stack

 

HOLD(C)       

CL(A) )  ^  HOLD(C)                Preconditions of  STACK

S (C, A)                                      Operator

ON(B, D)

ON(C, A) ^ ON(B, D)  ^ TSUBG 

 To execute S(C,A) all the preconditions should be true.here HOLD(C) is not true,to make the state true use the operator PU(C) and write the preconditions .

Goal Stack

ONT (C)^CL (C)^ AE               Preconditions of PICKUP

PU (C)                                      Operator 

HOLD(C)       

CL(A) )  ^  HOLD(C)                Preconditions of  STACK

S (C, A)                                      Operator

ON(B, D)

ON(C, A) ^ ON(B, D)  ^ TSUBG

 

Here, all the preconditions of PU operator is true,so add PU(C) in a queue of sequence of operators.

                      
 SQUEUE = US (B, A), S (B, D),PU(C)

State_3:              

                ONT(A) ^ HOLD(C) ^ ONT(D) ^ ON(B, D) ^ CL(A) ^  CL(B)

Goal Stack

 

HOLD(C)       

CL(A) )  ^  HOLD(C)                Preconditions of  STACK

S (C, A)                                      Operator

ON(B, D)

ON(C, A) ^ ON(B, D)  ^ TSUBG

Here all the preconditions of  S(C,A) is true ,so add S(C,A) in queue

 SQUEUE = US (B, A), S (B, D),PU(C),S(C,A)

State_4:              

                ONT(A)^ON(C, A)^ ONT(D) ^ON(B, D) ^CL(C) ^CL(B)^ AE

   
Finally ,we reached goal state after S(C,A) using Goal Stack algorithm,so the plan for the given problem is,

 
UnStack (B, A)
Stack (B, D)
PickUp(C)
Stack(C,A)