2 State Space Search I

Bhushan Trivedi

Introduction

Many AI problems are hard to solve because they are difficult to be characterized. Not only the problem but a path to the solution is also hard to be characterized. In this module we will learn the process of solving AI problems using state space search. We will also see the difficulties a designer might face.

Let us take an example of a chess problem. How can we represent chess as a problem which a program can solve? That means if we want our program to play a game of chess, how can we go about it?

First of all let us begin with an example which showcases how the chess problem can be represented in a computer understandable form. One can think of a matrix of 8*8 with different values indicating the piece which occupies that position. If we design our problem that way, following figure 2.1 describes an opening position. The values on the leftmost column and lowest raw indicate coordinates which we will use to identify the position of each piece. In actual matrix, these column and raw are not present. In subsequent figures, we will not show these additional raw and column.

One can also define a move as follows using that matrix representation.

The move shown in figure 2.2 has two states, the state on the LHS of the -> operator indicates what was the position of matrix before the move taken and RHS describes the position after that. This figure indicates the movement of a back pawn in the beginning. A move is described by one typical position (using a matrix) on the LHS while having a final position on the right. We need eight such moves for pawns on one side for such a case.

In fact, we can go on and describe many chess situations (called moves) in form of a matrix -> another matrix. How many moves do you thing we need to describe all possible instances? If your answer is infinity, you are not far.

State Space

A state space is a space which describes all possible valid states of this chess board. The initial board position in figure 2.1 and another position as an outcome of a move described in 2.2 are two examples. You can easily understand that describing all chess moves is a humongous task. If we go and write every chess move in this fashion, we may not be able to complete it in our lifetime. We must find an alternate way.

One can also describe such moves in form of rules which may encompass multiple moves together. For example we can write a rule describing many moves (including rule described in figure 2.2) in figure 2.3. It says that if a pawn is at position (i,2) and both the positions in forward direction (for black pieces, forward direction actually is reduction in value of j) are empty, a pawn can move two places up. As this is only allowed in the initial run where j is 7 (second raw from the player’s perspective), this is a general move. In fact a pawn can move from any position to one position forward when it is empty. That rule is shown in figure 2.4. This rule encompasses many rules for a black pawn movement.

If we write rules that way, it is still a very large but manageable set of rules for moves of chess. First type of rules is known as specific while next type is called general rules. One can write more generic rules using more generic variables as shown in figure 2.4. This rule defines a move for moving a black pawn anywhere in chess board.

Exploring chess problem is very complicated so we take two more trivial problems.

Solving AI Problems

First problem is called 3-4 gallon water jug problem as described in the book by Elaine Rich. We begin with two empty jugs of capacity of 3 and 4 gallons respectively. We have an infinite supply of water available and we want the 4 gallon jug to be filled with exactly 2 gallons of water.

Another problem is called 8-5-3 milk jug problem which begins with 8 gallon milk jug completely full while other two are empty. We want exactly 4 gallons of milk in the 8 gallon jug.

In either case, there are no other measuring devices available to us. One solution for the first problem is

0-0, 0-4, 3-1, 0-1, 1-0, 1-4, 3-2.

(Where n-m indicates quantity of water in 3 and 4 gallon jugs respectively) One solution of the second problem is

8-0-0, 3-5-0, 3-2-3, 6-2-0, 6-0-2, 1-5-2, 1-4-3, 4-4-0.

Where n-m-l are respective volumes of milk in 8, 5 and 3 gallon jugs.

What do these solutions indicate? Let us discuss some important points.

1. In both cases we have an initial state which we indicate as (0,0) in first and (8,0,0) in second problem. We had a similar type of initial state in chess. The states to represent both problems are represented in form of a vector.
2. We also have a final state in both cases which we indicate as (3-2) in problem 1 and (4-4-0) in problem 2. Please note that other final states are also possible. In a game like chess, numerous final states are possible.
3. Solution is a process of moving from one valid state to another. There must be a rule for moving from some valid state to another valid state. For example we cannot move from 0-0 to 1-0 or 2- 0 as we have no other measuring device, on the contrary 0-0 to 3-0 is possible when we can pour water into the 3 gallon water jug till it is full. Check in above solution sequences; we have used all valid moves.
4. For every problem, there are some are implicit assumptions which dictates validity of some possible moves. For example, from 1-3 to 1-0 is possible in problem 1 as water can be poured out (as it is inexpensive). The milk jug problem cannot be handled that way. Finding out such implicit assumptions about any problem and code them into a move is a challenging job.
5. How each state change is chosen, or how each move is chosen over other applicable moves?For example, how we decide to move from 6-2-0 to 6-0-2? In fact we must ask two questions here, for example, what possible moves are at the state 6-2-0, and why we chose 6-0-2 from that list. However simple both questions may look like, we will soon see that answering these two questions for a real world problem is much harder. Almost all AI problems are harder than one can possibly think at the first sight. Take any middle game position in chess to check.
6. One can enumerate in both of above cases to list all valid states like (0,0)…(4,3) or (8,0,0),(5,0,3),… (4, 4, 0). One can also write a formula, for example one can write (x,y) where xE (0,4), y E (0,3) to represent the collection of states for the first problem.The collection of all possible states is called a state space. A state space can be represented using an enumeration of all states or some formula describing the same.
7. The solution to the problem now is summarized as beginning from a start state, move around in the state space using valid rules for movement and reach to a final state.

Examples of production rules

One important outcome of above discussion is that we need to have some rules (called production rules) for movement in state Space. We already have seen examples of specific and general rules for chess. Let us see a specific and a general rules for two trivial problems that we discussed so far.

A 3-4 gallon water jug problem

(0,3) -> (3,0) [specific]

(0,Y) , Y> 0, Y<=3 -> (Y,0) [general]

An 8-5-3 gallon milk jug problem

(5, 0, 3) -> (5, 3, 0)[specific]

(X,0,Z) and Z>0 -> (X,Z,0)[general]

In both cases one can go and write many possible rules out of which only a subset is needed for solving the problem. Many books including Nilsson’s and Rich and Knight’s include complete set of rules for the water jug and few other problems.

Let us take one typical set for the milk jug problem.

We have two things to state before proceeding further.

1. The state space is represented by a three element integer vector (X,Y,Z) where X+Y+Z = 8, X,Y,Z

>=0 , X <=8, Y<=5 and Z<=3

2. The initial state is (8,0,0).

Now let us state the rules.

1. (X,Y,Z) , Y+Z< 3 -> (X,0,Y+Z) –pouring milk from 5 gallon jug to a 3 gallon jug if total milk from 5 and 3 gallon jugs is less than 3 gallon

2. (X,Y,Z) , Y>=3 -> (X,Y+Z -3,3)- filling the three gallon jug from five gallon jug while total milk from 5 and 3 gallon jugs is more than 3 gallons

3. (X, Y,Z), Y+Z < 5  -> (X,Y+Z , 0) –pouring milk from 3 gallon jug to a 5 gallon jug when total milk from 3 and 5 gallon is less or equal to 5 gallon

4. (X, Y,Z),Y+Z > 5   -> (X,5, Y+Z-5) –pouring milk from 3 gallon jug to a 5 gallon jug when total milk from 3 and 5 gallon is more than 5 gallon

5. (X,Y,Z) , X+Z>=3 -> (X+Z -3,Y,3)- filling the three gallon jug from eight gallon jug while 8 and 3 gallon jug total having more milk than 3 gallons

6. (X,Y,Z) , X+Z<=3 -> (0,Y,X+Z) – filling the three gallon jug from eight gallon jug while both having less total milk than 3 gallons

7. (X,Y,Z), X+Y < 5 ->  (0, X + Y, Z), filling the five gallon jug from eight gallon jug while both having less total milk than 5 gallons

8. (X,Y,Z), X+Y > 5 ->  (X + Y-5 ,5 , Z) filling the five gallon jug from eight gallon jug while both having more total milk than 5 gallons

9. (X,Y,Z) -> (X + Y ,0 , Z)pouring all milk from a five gallon jug into an 8 gallon jug.

10. (X,Y,Z) -> (X + Z ,Y , 0)pouring all milk from a three gallon jug into an 8 gallon jug.

Let us try to see how these rules are written. First, X Y and Z represent amount of milk contained by an 8,5 or 3 gallon jug. Each rule has two parts, a left part and a right part. A left part contains the values of variables describing a state where the rule is to be applied. The left part additionally contains a condition under which this rule is to be applied. For example, take rule 8, it is applicable only if the total milk in 8 and 5 gallon jugs exceed 5 gallons. When the rule is applied, a move is taken and the result is as shown in the right hand side. For example, if 8th rule is applied, the five gallon jug is full and rest of the total of 8 and 5 gallon jug remains in 8 gallon jug.

Applying rules to solve the problem

Now let us see the sequence of rules applied for the solution.

1.	8-0-0	->	3-5-0	(rule 8, X+Y =8 > 5)
2.	3-5-0	->	3-2-3	(rule 4, Y + Z = 5 > 3)
3.	3-2-3	->	6-2-0	(rule 10, X +Z =6)
4.	6-2-0	->	6-0-2	(rule 1, Y+Z = 2 < 3)
5.	6-0-2	->	1-5-2	(rule 8, X + Y = 6 >5)
6.	1-5-2	->	1-4-3	(rule 2, Y + Z = 7 > 3)
7.	1-4-3	->	4-4-0	(rule 10, X + Z =4)

4-4-1  is a final state.

Let us summarize. We have an initial state called (8,0,0), we apply a typical rule, record the new status, apply another rule and again look at the status and continue until we reach to a state which is qualified as a final state.

Can you guess the types of components required for solving a problem using a state space? Let us list down.

1. Not all rules are used in solving the problem in a typical way. For example rule 3,5,6,7 and 9 are not applied in the proposed solution sequence. Anyway, they may be needed in solving some other problem involving the three jugs. Which rules are needed and which are not for a given case is hard but one needs to have at least a temporary set to begin with. One can continue augmenting it when there is a need.

2. A clear indication of what consists of start and end state(s) and also clear indication of what are valid states, in other words, a clear definition of a stat space for a given problem.

3. A set of rules to provide legal movement in state space.

4. A data structure (in our case a vector with three integer values) for indicating current state. When a typical rule is applied, this data structure changes to hold the new state as a result of application of this rule.

5. A logic which changes the state as per the applied rule, something which help the current vector value to change to a new vector value.

6. When more than one rule is applicable, a mechanism to decide which rule to be applied.

Last three requirements sound exaggerating, especially looking at the problem at hand. It is not really if one looks at real problem. Consider an auto navigator problem which helps the driver to navigate to the destination. How on earth, the navigator represents the problem itself (the data structure design)? Consider frames coming from various cameras in from various places in the car, its speed and other measurements coming from various gauges implemented on the dashboard, information coming from app like map and so on. The data structure is going to be a huge challenge, especially while considering the real time navigation requirements. When a driver decides to take a left turn while the program is deliberating over going straight or taking a right turn (due to some obstacle or police restrictions auto driver is not aware of), changing the landscape that fast is an equally difficult challenge.

In fact the requirement no 6 is daunting even for our trivial case. Consider our seven step solution. In many cases, the solution could have gone in different direction had we apply another rule there. For example in case of 4th step, we could have applied rule 9, 8, 6 etc but we chose rule 1, why? How do we know that rule 1 is more likely to lead to the solution?

In fact, the problem was so trivial that we could solve it manually and decide the next move based on the manual solution. Solving a problem that way is cheating as the program does not decide but the designer decides the next move. Such a cheating is not advisable for two reasons. The program acts like a dumb following designer’s instructions which we do not want. We want a program which can decide like human being. Second, such a cheating cannot help solve real world problems like chess. How can we decide each possible move sequences in chessa priory and encode them? Not only a human cannot enter all such move sequences, even if one somehow gathers them, it would be a non-trivial problem to store such a huge volume of data and also search such humongous database in real time.

You might be getting the feel for the problems AI researchers are facing over the years. You may have seen or heard about chess playing programs which can actually play at reasonably good level. That is possible due to some advances and efforts of the researchers in this domain.

You might be wondering that if we could  produce chess playing programs why can’t we produce programs which can manage other tasks, for example rating an essay or driving a car, or building a house robot which can work like a servant. The reason is, even though the chess playing program looks pretty complex on the face of it, it is quite structured. The moves are chosen based on information like the number of pieces, their respective ratings (for example the rating of king is higher than the summation of ratings of all others, a queen has a higher rating than a rook and so on), the center control (if pieces are at the center they have more control over the game) and many other things. A good chess playing program is equipped with heuristics based on those measures and thus capable to assume reasonably good move in real time.

We will take two more trivial but little different examples in next module to understand conversion to state space further.