Friday, September 28, 2018

Mini Max Search Procedure.

  • The Min-Max algorithm evaluates decision-based on the current situation of the game.
  • This algorithm needs a deterministic environment with exact information.
  • Min-Max algorithm directly implements the defining equation.
  • Every time based on the successor state min-max value is calculated using simple recursive computation.
  • Algorithm:
1)Create the entire game tree including all the terminal states.
2)For every terminal state, find out utility. This means that 1 means win and 0 means draw.
3)Apply min and max operators on the nodes of the current stage and propagate the utility value upward in the tree.
4)With the max utility value, select the action at root node using min-max decision.
  • Example,
First iteration Procedure:
Min= inf
Min(inf,10)=10
Min(10,11)=10
Min=inf
Min(inf,9)=9
Min(9,11)=9
.
.

Second iteration Procedure:
Max=-inf
Max(-inf,10)=10
Max(10,9)=10
Max=-inf
Max(-inf,14)=14
Max(14,13)=14
.
.

Again Min Procedure:
Min=inf
Min(inf,10)=10
Min(10,14)=10
.
.

.
If we keep going, the final answer will be 10.

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)