The problem, play chess, has been described as a problem of moving around in a state space; where each state corresponds to a legal position of the board. Starting from initial state and using a set of rules to move from one state to another can give rise to one of a set of final states. The combination of all these states gives rise to what is called the state space.
The playing of chess is a simple example of problem solving, as the board states here are well organized (structured). The 15-tile problem is also equally structured. The same kind of state representation can also be used in the case of less structured problems, although it may be necessary to use more complex structures than a matrix (array) used here, to describe the state.
In order to show the generality of state space representation let us take another problem Water Jug Problem which is stated as:
We are given two jugs, a 4-gallon one and 3-gallon one. Neither has any measuring marked on it. There is a pump, which can be used to fill the jugs with water. How can we get exactly 2 gallons of water into 4-gallon jug?
ADVERTISEMENTS:
The state space for this problem can be described as the set of ordered pairs of integers (X, Y) such that X = 0, 1, 2, 3 or 4 and Y = 0, 1, 2 or 3; X is the number of gallons of water in the 4-gallon jug and Y the quantity of water in the 3-gallon jug.
The start state is (0, 0) and the goal state is (2, n) for any value of n, as the problem does not specify how many gallons need to be filled in the 3-gallon jug (0, 1, 2, 3). So the problem has one initial state and many goal states. Some problems may have many initial states and one or many goal states.
The operators to be used to solve the problem can be described as shown in Fig. 2.3:
As in chess playing they are represented as rules whose left side are matched against the current state and their right sides describe the new state which results from applying the rule.
ADVERTISEMENTS:
In order to describe the operators completely here are some assumptions, not mentioned, in the problem state.
1. We can fill a jug from the pump.
2. We can pour water out a jug, onto the ground.
ADVERTISEMENTS:
3. We can pour water out of one jug into the other.
4. No other measuring devices are available.
All such additional assumptions need to be given when converting a problem statement in English to a formal representation of the problem, suitable for use by a program.
To solve the water jug problem, all we need, in addition to the problem description given above, is a control structure which loops through a simple cycle in which some rule whose left side matches the current state is chosen, the appropriate change to the state is made as described in the corresponding right side and the resulting state is checked to see if it corresponds to a goal state.
ADVERTISEMENTS:
The loop continues as long as it does not lead to the goal. The speed with which the problem is solved depends upon the mechanism, control structure, which is used to select the next operation.
There are several sequences of operators which will solve the problem, two such sequences are shown in Fig. 2.4:
Thus, the state space representation forms the basis of most of the AI methods for problem solving.
ADVERTISEMENTS:
Its structure corresponds to the structure of problem solving, conforming to the following two steps:
(a) Converts the given situation into some desired situation using permissible operations.
(b) Combines the known operators, each representing a rule defining a single step, in the space.
Thus, the general technique of exploring the space is to try to find some path from the current state to a goal state.
Issues in Water Jug Problem:
It has been shown above how an informal problem state (stated in English) has been converted into a formal one (Fig. 2.4) with the help of a water jug problem.
In doing so some issues which affect the approach towards the solution are:
1. The rules should be stated explicitly and not written because they are allowable. For example, the first rule states that “Fill the 4-gallon jug”, but it should have been written as “if the 4-gallon jug is not already full, fill it” but the rule in its stated form is not wrong as there is no condition that the already filled jug cannot be filled (may be after emptying).
No doubt this is physically possible but not wise; as this won’t change the problem state. In order to increase the efficiency of the problem solving program, it is imperative to encode some constraints in the left side of the rules so that the rules should lead to a solution that is the rules should be made more general.
2. Now consider the rules 3 and 4 should or should not these rules be included in the list of available operators? Emptying an unmeasured amount of water onto the ground is certainly allowed by the problem statement, but do these rules lead us near to a solution. The answer is ‘no’ so these can be ignored. So, such rules which are really applicable to the problem in arriving at the solution should be considered.
3. The rules 11 and 12 are special purpose rules, written to capture special purpose knowledge to solve this problem. This is clear from the above example solution. Consider the last two steps of the solution in Fig. 2.4 (a), once the state (4, 2) is reached it is obvious what to do next? The desired 2-gallons have been produced, but they are in a wrong jug.
Move 2-gallons of water to 4-gallon jug-rule 11 (or rule 9). But before that the water already in 4-gallon jug need to be emptied, rule 12 (or rule 5). These two special purpose rules do not help in solving the problem since the operators they describe are already provided by rules 9 and 5 respectively, so could have been avoided. Sometimes special rules improve performance if preference is given to special case rules.
To formalize a problem the following steps are needed:
(i) Define the problem precisely, giving the specification of what the initial situation (s) and the final situation (s) will be.
(ii) Analyze the problem because a few important features can have immense impact on the suitability of different techniques available for solving the problem.
(iii) Represent the knowledge completely, which is necessary to solve problem in a given domain.
(iv) Choose the best technique(s) and apply it (them) to the particular problem.
Depending upon the control strategy (Fig. 2.4) to be used the performance of problem solving procedure can be improved or degraded. It is thus clear that to create a program for solving a problem simply the formal description of the problem has to be generated using the knowledge about the given problem. This process is called operationalization.
Water jug problem is a simple illustration of solving a problem through state space search. But many difficult problems such as understanding of natural Language which need to be solved by the AI techniques, the water jug problem can act as a strong basis for such tedious problems. This was done in the case of ELIZA, an early AI program.
Summarizingly any problem can be solved by the following series of step:
1. Define a state space which contains all the possible configurations of the relevant objects and even some impossible ones.
2. Specify one or more states within that space which would describe possible situations from which the problem solving process may start. These states are called the initial states.
3. Specify one or more states which would be acceptable as solutions to the problem. These states are called goal states.
4. Specify a set of rules which describe the actions (operators) available and a control strategy to decide the order of application of these rules.
The problem can be solved by collecting all knowledge of the problem, (in the present case, water jug problem) with the help of production rules and using an appropriate control strategy; move through the problem space until a path from an initial state to goal state is found.
This is the process of search which is fundamental to the problem solving process. (This does not, however, mean that other more direct approaches cannot be exploited. Whenever possible, they can be included in the search by embedding them into the rules).
Since search provides the core of many intelligent processes, it is useful to structure AI program in a way which facilitates describing and performing the search process.