State space representation and problem reduction

In this section, we will describe two methods commonly used in problem representation. As a sample problem the 8-puzzle will be used. The 8-puzzle consists of 8 numbered, movable tiles set in a 3 X 3 frame. One of the cells of the frame is always empty, which makes it possible to move the tiles.

A sample 8-puzzle is given in fig. [*]. Consider the problem of transforming the first configuration into the second one, our goal.

Figure: The 8-puzzle.
\begin{figure}\centering
\begin{tabular}{rrrcrrr}
2 & 1 & 6 \hspace{2cm} & 1 &...
... & 0 & 4 \\
7 & 5 & 3 \hspace{2cm} & 7 & 6 & 5 \\
\end{tabular} \end{figure}

To solve this puzzle we try out various moves producing new configurations until we produce the goal configuration. To give a more formal definition of this problem we say that we are trying to reach a certain goal  configuration starting with an initial configuration by using some set of operators . An operator transforms one configuration into another, in the case of the 8-puzzle it is most natural to think of 4 such operators, each corresponding to moving the empty tile: move empty tile left, move empty tile right, move empty tile up, move empty tile down.

What we just have done is defining the problem of solving the 8-puzzle in terms of a state space search . In a state space search the object is to reach a certain goal state  starting with an initial state. In the case of the 8-puzzle the start and goal state are the configurations given in fig. [*]. More generally we can say that every configuration we produce when trying to solve the 8-puzzle corresponds to one state in the state space. All these states together, i.e., all possible  configurations make up the state space. It is possible of course to define the state space without explicitly enumerating all states. Indeed, most of the time this is impossible and the state space will be defined implicitly by providing rules specifying how each state can be derived from another. The state space may be small as in the case of the 8-puzzle, but for most every day problems or other board games it is quite large (e.g., in chess the total number of possible board configurations, this is the total number of possible states, equals roughly 10120). Obviously it would be impossible to explore the entire state space and often this is not needed, because we are interested in finding only one solution to a problem, i.e., only one path leading from the start state to the goal state. This means that we do not have to search the state space exhaustively , but a small(er) portion instead. The problem of course is, which portion?

But before we are going to discuss this point it will be helpful to look somewhat further at the approach we have described so far. We said that to solve a problem it is necessary to represent the problem as a state space search. That is, we define a start state, a goal state and a set of operators that transform one state into another. The actual search consists in moving around in the state space, looking for a path from the initial state to the goal state. In this case the search process proceeds forward because we start with the initial state and move towards the goal state. Hence it is called a forward reasoning system . The opposite behaviour is also possible: a system starting the search with the goal state and moving backward to the initial state. In this method, often called backchaining  we reason backward  from the goal states. These two techniques can be combined, resulting in a bidirectional search . In the case of the 8-puzzle it does not make much difference if we move forward or backward, because about the same number of paths will be generated in either case, but some problems can be solved more efficiently when searching in one direction rather than the other (see Rich (1983), p.58).

A different technique, or rather a different way to represent problems, that has not been mentioned so far is that of problem reduction . In this type of representation each operator used may divide the problem into a set of sub-problems that each have to be solved seperately. Additionally, there may be restrictions on the order in which these sub-problems have to be solved1. The object of problem reduction is to eventually produce a set of primitive problems whose solutions are regarded as trivial: at this stage the process of dividing problems into sub-problems halts.

These two approaches, state space search and problem reduction, are two of the most common methods used in problem representation, although variations of these approaches, as used in, e.g., game-playing are also possible (see Barr(1981), p.84ff., Ritch(1983), p.113ff., Nilsson(1971), p.137ff).