3 State Space Search II

Bhushan Trivedi

A state space search for a problem with more prerequisite

Both problems we have seen in the previous module were comparatively simple as there was little prerequisite for applying rules. To emphasis that important part, let us take one more problem which relies heavily on the prerequisites for applying a rule. This module, thus extends our discussion on state spaces and provides further insights into how one can design a state space for a given problem.

A missionary cannibal problem

Let us take our nextexample to reiterate our understanding of state space, the start state, the end state, the rules and using those rules to solve the problem, especially the preconditions under which a rule is to be applied.

The problem is called a missionaryandcannibal problem. Three missionaries and three cannibals found themselves on one side of a river. All of them have to move to the other side. The only boat available for communication can carry maximum two of them at a time. One of them must comeback to get the boat on the side where others are waiting. Another condition is, at no point of time, the missionaries should be less than the number of cannibals on any side of the river (otherwise they will eat those missionaries).

One of the many ways to represent the state space is as follows.

L(M1,C1)&&R(M2, C2)&&(BL || BR) where

(M1 >= C1 || M1 =0),

(M2 >= C2 || M2 =0),

M1 + M2 = 3, M1, M2 Î (0, 3)

C1 + C2 = 3,C1, C2 Î (0, 3)

L indicates left and R indicates right sides.

M1 is missionaries on the left side while C1 indicates the cannibals on the left side,

M2 and C2 indicates the same for the right side,

Total number of missionaries and cannibals must remain the same as 3 for any valid state so the summation of M1 and M2 and C1 and C2 must be 3 for a valid state.

BL indicates boat on the left side while BR indicates a boat on the right side. We can have boat on one side but not at both sides of the river.

Production rules for missionary cannibal problem

Now let us look at some states to see if they are valid.

1. L(2,0)&&R(1,3)&&BL
2. L(3,3)&&R(0,0)&&BL.
3. L(0,0)&&R (3,3)&&BR
4. L(0,1)&&R (2,2)&&BR

Let us begin from state 1. Total number of missionaries and cannibals are same but we have more number of cannibals on the right side compared to the missionaries on that side so this state is invalid. Second state is valid as all the conditions are satisfied. It is also either a start state, if they start their journey from the left side or a goal (end) state if they commence their journey from the other side. Same can also be said about the next state. The only difference between state 2 and state 3 is that the people involved are on different sides of the river. Let us look at 4th state. This state is invalid as number of total missionaries on both sides of the river is reduced only 2.

Let us write rules for moving from left to right and vice versa.

First we write a rule from moving left to right. Let us call it rule 1.

L(M1,C1)&&R(M2, C2)&&(BL) ,

{ M, C Î (0,1,2) }, // Missionaries (M)and cannibals (C)moving across, can be either 0,1, or 2 {M + C = 1|| M + C = 2}, // Total M + C carried by boat can only be 1 or 2

{(M1 – M >= C1 – C) ||M1 –M =0}, //M missionaries are moving across {(M2 + M >= C2 + C) ||M2 + M =0} // C cannibals are moving across,

// but both moves must satisfy our basic condition

->L(M1 – M,C3 – C)&&R(M2 + M, C2 + C)&&(BR)

Now we write the rule to move from right to left

L(M1,C1)&&R(M2, C2)&&(BR) ,

{ M, C Î (0,1,2) },

{M + C = 1|| M + C = 2},

{(M1 + M >= C1 + C) |M1 + M =0}

{(M2 – M >= C2 – C) |M2 – M =0}

->L(M1 – M,C3 – C)&&R(M2 + M, C2 + C)&&(BL)

We have already learned that a rule will have an LHS state and an RHS state plus some preconditions under which it is possible to move from the LHS state to an RHS state. Both of the above rules are written using that structure.

Let us understand the first rule.

L(M1,C1)&&R(M2, C2)&&(BL) is the LHS state while (M1 – M,C3 – C)&&R(M2 + M, C2 + C)&&(BR) is the RHS state. We assume M missionaries and C cannibals moving from left to right and thus we have  decrement on the left while increment on the right hand side. Symbol&&is used for AND operation and || is used to indicate OR operation. Now let us look at the preconditions. Possible values of M and C can be any integer from 0 to 2.  If M is 0, C can be 1 or 2 (why? Remember the boat can carry only two maximum). If M is 1, C can be 0 or 1 and so on. In short M + C (total person carried by the boat) can only be 1 or

2. Hence the next set of preconditions.

We also want to have both missionaries and cannibals to remain in balance on either side so we have next set of preconditions. They indicate that missionaries on either side of the river can be either greater than the number of cannibals or equal to zero. Let us take one typical solution to the problem. Each row shows how the movement takes place with the values of M and C and which rule to apply.

One solution
Movement	Rule	M	C
L(3,3)&&R (0,0)&&BL -> L(3,1)&&R (0,2)&&BR	1	0	2
L(3,1)&&R (0,2)&&BR->L(3,2)&&R (0,1)&&BL	2	0	1
L(3,2)&&R (0,1)&&BL-> L(3,0)&&R (0,3)&&BR	1	0	2
L(3,0)&&R (0,3)&&BR ->L(3,1)&&R (0,2)&&BL	2	0	1
L(3,1)&&R (0,2)&&BL ->L(1,1)&&R (2,2)&&BR	1	2	0
L(1,1)&&R (2,2)&&BR ->L(2,2)&&R (1,1)&&BL	2	1	1
L(2,2)&&R (1,1)&&BL -> L(0,2)&&R (3,1)&&BR	1	2	0
L(0,2)&&R (3,1)&&BR -> L(0,3)&&R (3,0)&&BL	2	0	1
L(0,3)&&R (3,0)&&BL -> L(0,1)&&R (3,2)&&BR	1	0	2
L(0,1)&&R (3,2)&&BR -> L(0,2)&&R (3,1)&&BL	2	0	1
L(0,2)&&R (3,1)&&BL -> L(0,0)&&R (3,3)&&BR	1	0	2

Do you think it is simple to generate such rules? Absolutely not, even for this simple problem1. The bottom line is, converting a problem into a state space representation requires lot of work, introduction of additional variables (like M and C), detailing of prerequisites which ensures a movement from a valid state to another valid state only and write rules which covers every possible case.

Another question that we have already asked; how do we decide values of M and C at each stage? That means how to choose a move leading to solution? Again there is no clear cut strategy or algorithm to decide. The range of M and C is such small that one can exhaustively try all possible combinations and would succeed. That is not possible in a real world so we need some other strategy.

• 1 It took me a few hours to design this solution and lot of more time to fine tune it.

The farmer fox chicken grain problem

Another interesting example is in order. We will look at multiple representation of this problem. Though this problem is as trivial as the previous one (our interpretation of trivial is that it is possible to write complete solution sequence by humans in real time, simple does not imply simple to write production rules or representing as a state space.)

A farmer, a fox, a chicken and grain found themselves on one side of a river; a boat can carry only two items, only farmer can row the boat. If the farmer is not around, chicken may eat grain and the fox may eat chicken. This problem sound similar to previous problem but it is quite different. Let us begin with one typical representation of the problem. We begin with the initial state value.

L(Fr,fx,ch,Gr)&&R(˜Fr,˜fx,˜ch,˜Gr) where ~ represent not. This represent indicates that all four of them, the farmer, the fox and the chicken are on the left side and none on the right side.

Following is a final state.

L(˜Fr,˜fx,˜ch,˜Gr)&&R(Fr,fx,ch,Gr) which indicates that everybody is on right side.

What could be the state space? Following is one typical way to represent.

L(A,B,C,D)&&R(˜A,˜B,˜C,˜D) where A Î (Fr, ~Fr), B Î(Fx, ~Fx), CÎ(Ch,~Ch), D Î (Gr, ~Gr), ((A == ~Fr)&&~(B==Fx&&C== Ch)&&~(B==Ch&&C==Gr))

(When farmer not around, fox and chicken and chicken and grain cannot be on that side together)

• || ((A==Fr)&&~(~B==Fx&&~C== Ch)&&~(~B==Ch&&~C==Gr)) (Otherwise, the same is applicable to the other side)

Look at how the state space description uses negation.

Here is one more candidate representation. Let us begin with the initial state.

at (L,Fr)&&at(L,Fx)&&at(L,Ch)&&at(L,Gr)

Here is a final state  at (R,Fr)&&at(R,Fx)&&at(R,Ch)&&at(R,Gr)

Here is a state space

at (A,Fr)&&at(B,Fx)&&at(C,Ch)&&at(D,Gr), where A, B, C, D Î (L,R) , (at (R,Fr)&&(~at(L,Fx) ||~at(L,Ch))&&(~at(L,Ch) || (~at(L,Gr))))

||

(at (L,Fr)&&(~at(R,Fx) ||~at(R,Ch))&&(~at(R,Ch) || (~at(R,Gr))))

Like in a previous case symbol && is used for AND operation and || is used to indicate OR operation.

Let us take one more representation.

L(1,2,4,8) Λ R (0,0,0,0) is an initial state,

L (0,0,0,0) Λ R(1,2,4,8) is a final state

1 indicates farmer, 2 indicates fox, 4 chicken and 4 the grain.

Following is a state space representation.

L(A,B,C,D) Λ R (E,F,G,H)

• Λ A,E Î (1,0), B,F Î (0,2), C,G Î(0,4), D,H Î(0,8)
• Λ (A+E =1) Λ (B + F =2) Λ (C + G = 4) Λ (D + H = 8) // all of them can only be on one side
• Λ (A + B + C + D) != (6, 12, 14)
• Λ (E + F + G + H) !=(6, 12, 14)

   This representation uses a typical property of numbers of multiple of two which is quite known to people in computer science. Summation 6 indicates fox (2) and chicken (4) on one side, 12 indicates chicken (4) and grain (8) on that side and 14 indicates all three of them on one side.

Why we looked at multiple state space representations of the same problem?

We wanted to emphasize a few vital points.

1. It is possible to generate multiple representations for the same problem
2. A clever idea can simplify the representation or precondition to a large extent
3. Variables can be defined and manipulated in multiple ways.
4. Some presentations are simpler compared to others. Some representations are more readable than others.

Here is one typical sequence for a solution.

1.	L(Fr, Fx, Ch, Gr)	&&R(__,__,__,__)
2.	L(__,Fx,__, Gr)	&&R( Fr,__,Ch,__)
3.	L(Fr, Fx,__ , Gr)	&&R( __,__Ch,__ )
4.	L(__,__,__ , Gr)	&&R(Fr, Fx,Ch,__ )
5.	L(Fr,__ , Ch, Gr)	&&R( __,Fx,__,__ )
6.	L(__,__ , Ch,__)	&&R(Fr,Fx,__,Gr)
7.	L( Fr, __, Ch,__)	&& R( __,Fx,__, Gr)
8.	L( __,__,__,__ )	&& R(Fr, Fx, Ch, Gr)

You may try writing production rules for movement, using any representation you may prefer.

The combinatorial explosion

If you have already guessed that most AI problems are plagued by this problem you are right. Number of combinations and permutations, for most but trivial AI problems, is so large that even the fastest computer in the world cannot check them in real time. This problem is known as combinatorial explosion and many solutions are proposed to handle but none of them solves the problem in a general and satisfactory way. We will look at some proposals in due course.

Now let us turn back to the point we have begun with. The problems that we have mentioned above are able to be characterized so we can propose a solution. Now, can we write rules for parsing an English statement? Or design rules for robot moving in a space shuttle? If we have complete description of the domain, we can. One can easily understand the importance of converting the domain knowledge into a state space reorientation and a set of production rules.

Let us reiterate the requirement of managing combinatorial explosion. Without a clear strategy to manage combinatorial explosion, we entangle ourselves into exploring seemingly endless avenues even after successfully converting the domain knowledge into state space representation and set of production rules. We will study how heuristics can be used to handle them in the next module.