Goal Stack Planning

Explain goal stack planning with example.

• Goal stack planning is one of the most basic and earliest planning techniques.
• Here is what the stack contains:

1)Goals
2)operators – ADD, DELETE and PREREQUISITE list
3)A database that maintains current situation for each operator

• Each sub-goal is solved separately and then the conjoined sub-goal is solved.
• For example,

Blocks World Problem In Artificial Intelligence

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

• The following goals are already true in the initial state:

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

• The only goals to solve are ON(C, A) and ON(B, D).
• So, let’s solve ON(C, A)

Goal stack:

ON(C,A)

ON(B,D)

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

• To solve ON(C, A), we can apply S(C, A) operation. So, replace it.

Goal Stack:

  S (C, A)

 ON(B, D)

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

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)  ^ ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE

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)  ^ ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE

ON(B, A), CL(B)  and AE are all true in an 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 a 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)  ^ ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE

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)  ^ ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE

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)  ^ ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE

Add S(B, D) in a queue of a 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)  ^ ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE

 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)  ^ ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE

Here, all the preconditions of PU operator are true, so add PU(C) in a queue of a 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)  ^ ONT(A) ^ ONT(D) ^ CL(C) ^ CL(B) ^ AE

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)