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)
