State Space Search and Graph Search

     Now that the basic ideas of state space search have been presented, we will step back and consider the method of state space search somewhat more carefully. Two issues will be discussed. First, considering state space search syntactically, we will examine the relation between state space search and graph search. Second, considering state space search semantically, we will consider the formulation of a problem domain as a state space search.

      Recall that a graph consists of a finite set of nodes, N together with a finite set of edges, E where E is a subset of N x N.  Consider the figure below. This map depicts some of the air routes between cities in the northeastern portion of the United States. If all that is desired is to represent whether or not two cities are directly linked by an air route, then a graph provides the syntactic distinctions needed to represent this information. Cities correspond to the nodes and air routes between cities correspond to the edges of the graph. Note that much of the information that is depicted in the figure below is lost in this graph representation. For example, the distance between the cities, the direction traveled, the time and number of flights between a pair of cities, the state in which the city is located, and so on. However, if the desire is to obtain a representation within which it is possible to determine the most direct route between a pair of cities, then this representation could accurately capture the semantics of this aspect of the "air route world." And, these are the semantics required to solve problems of finding a most direct route. 

Some Air Routes Over the North East United States

This particular map is visually quite daunting. It explicitly represents connections between various cities. However, it depicts only the air connections between some of the cities and only for one particular airline. The number of cities and connections is quite large. Nonetheless, the technique of breadth first graph search could be used on the graph of this map to determine the most direct route. Could this same information and search be carried out using the method of state space search? What is required is a set of generators that when given a particular city, say Chicago, will return a city that can be reached directly from Chicago. For example: g23(Chicago) –> Houston g26(Chicago) –> Mobile g28(Chicago) –>Boston g29(Boston) –>Chicago etc.

     Note that we can always write down as many generators as there are links in the graph. In this rather trivial sense, it is always possible to substitute state space for graph search. But has anything been gained? or lost? Note that if there are n edges in the graph, then n generators are required. In this case the state space method requires just as much memory to hold this information as the graph method. And, as we will see in the example below, state space search will turn out to be computationally somewhat more expensive due to the added cost of recognizing cycles. The advantage of state space search arises:

• when there are some regularities in the world that can be captured algebraically in the choice of a set of generators. And,
• when an evaluation function can be defined over the state description pairs that provides reliable information concerning the "distance" between the states in the world represented in the state space formulation.

     These are strong requirements and we will spend some time developing an example within which to discuss these aspects of a state space formulation of some problem.

An Example of a Breadth First Search of a Graph 

     For this example a simple world has been constructed in which every state contains exactly three same dimensioned rectangles, the rectangles are all oriented such that the longer side is oriented vertically, the rectangles are arranged along a diagonal moving from 11 o'clock to 5 o'clock, the rectangles are touching any adjacent rectangle along this diagonal, and a rectangle is either black or white. Most of these aspects of the example world remain invariant. The only property that changes is the color of a rectangle. The figure shown below on the right depicts the set of possible states of such a world. Since there are three rectangles in each state and each can be colored either white or black, there are 2 to the 3 or 8 logical possibilities. It turns out that our world allows each of these possibilities. The problem around which our example is organized is shown below on the left. The problem involves changing the color of each of the three rectangles from white to black.

information about our world which is required to carry out a graph search. Note, that we needn't describe the states in any way but simply insure that each is represented uniquely -- in this case by "naming" them with a distinct color.

     A QuickTime "movie" presented below serves to illustrate the details of a breadth first graph search. For this example we have taken the liberty of choosing the node associated with the starting state of our problem as the starting point of the graph search. And we assume that our algorithm recognizes when the node associated with the goal node is encountered. The example search will terminate when the node associated with the goal is encountered. The movie begins by reviewing the steps that we have just described. The actual search begins with a

    Note that "cycle checking" is trivial in graph search. States (or nodes) are not generated in graph search and consequently each node is unique. Thus, marking a node as visited allows us to easily keep track of which aspects of the graph have already been searched. In our example a visited node is either gray or black. You will notice that concomitantly with the search, a tree is drawn on the right of the figure. This provides another representation of the state of the search. The nodes of the tree are given the color of the corresponding node in the graph.

An Example of a Breadth First Search in a State Space

     In order to solve the example problem in a state space, it is necessary to provide a description that represents the legal states and a set of generators (or partial functions) which mirror the legal transitions in the "Example" World. The "Example" World is shown again in the figure below. To its left is shown a world which has a simpler algebraic structure than the Example World. This world is labeled the "Paint Any One Rectangle" World since in this world any single rectangle can be painted a color opposite its current color. For this world, the legal transitions can be captured in a single generator. Let us simply describe a state using a one place relation, name and a two place relation, color. The single argument for the name relation is from the set {L, M, R} and the first argument for the color relation is from this same set and the second argument is from the set {B,W}. Then the description of the state consisting on three white rectangles is {name(L), name(M), name(R), color(L,W),color(M,W),color(R,W)}. We also include the functions opp(x) which returns the value B when x is W and W when x is B and the relation ne which is used to insure that the value assigned to two variables is unique. Then the single generator can be stated as:

if name(x), name(y), name(z), ne(x,y), ne(x,z), ne(y,z), color(x, a), color(y, b), color(z, c)

then name(x), name(y), name(z), color(x, opp(a)), color(y, b), color(z, c)

"Paint Any One Rectangle" World

"Example" World