Formulation of the Generators for The Example Space

On this page the details of the reasoning used to identify a set of generators that are needed to formulate the Example Space as a State Space are presented. The figure shown immediately below on the left depicts the "Example World." Recall that the language that has been adopted to describe states consists of: two relation constants, the unary relation name, and the binary relation color; the name constants {L, M, R} (left, middle, and right rectangle respectively); the color constants {W, B} ( white and black respectively); the function opp(x) which when given a color constant returns the other color constant; a relation ne (not equal) and variables as required.
Example Space	For example, the state consisting of the three white rectangles is described as: name(L), name(M), name(R) color(L,W), color(M,W), color(R,W) and the description: name(x), name(y), name(z), ne(x,y), ne(x,z), ne(y,z), color(x,i), color(y,i), color(x,opp(i)) refers to states where one rectangle differs in color from the other two rectangles.
The name relation is not really required but is included to make the meaning of the descriptions somewhat more transparent. Note that much of the information about a state; e.g., size of the rectangles, orientation, etc, is not mentioned in the description. In this example space, all of the characteristics of a state are invariant across the states in the space except for color. Factoring the Example Space      Now that the states of the example space have been described, the next step is to capture the links of the Example Space as a set of generators. Formulation of the generators involves identifying the regularities that may hold in the Example Space. The simplest of regularities is invariance. In this case the only invariance that has been represented in state descriptions is the names of the rectangles. If there are remaining regularities in this space, then these regularities will be associated with the generators or partial functions that map one state description into another.
Single Rectangle Changes in the Example Space	All Possible Single Rectangle Changes
One way to approach the problem of identifying regularities associated with change is to consider first the space of all possible changes that could hold between the pairs of states. The matrix on the lower left below catalogs these various changes. The states are listed in the top row and left column. The states are referenced using a notation of W's and B's. W is used to stand for 'white' and B for 'black.' The first position in the string refers to the left rectangle, the second to the middle rectangle, and the the third to the rectangle on the right. For example, 'BWW' refers to the state in which the left rectangle is colored black, the middle rectangle is colored white and the right rectangle is also colored white.      There are 8 states and consequently there are 8 x 7 or 56 possible maps from one state to another. The gray cells in the matrix indicate transitions from the row state to the column which involve a change in the color of a single rectangle, the green cells transitions where the color of two rectangles is changed, and the blue cells transitions where the color of all three rectangles is changed. The letters within the cells refer to the rectangle(s) whose color is changed. The same information is presented in three of the figures shown on this page. The figure to the above right titled "All Possible Single Rectangle Changes" depicts all of the possible transitions that change the color of a single rectangle. The figure below and to the right titled "All Possible Two Rectangle Changes" depicts all of the possible transitions that change the color of a two rectangles. And, the last figure below and to the left titled "All Possible Three Rectangle Changes" depicts all of the possible transitions that change the color of a three rectangles.
WWW WWB WBW WBB BWW BWB BBW BBB WWW    R M  MR  L  LR  LM LMR WWB  R   MR  M  LR  L LMR  LM WBW  M  MR    R  LM LMR  L  LR WBB  MR  M  R   LMR  LM  LR  L BWW  L  LR  LM LMR    R  M  MR BWB  LR  L LMR  LM  R    MR M BBW  LM LMR  L  LR  M  MR    R BBB LMR  LM  LR  L  MR  M  R   All Possible State Transitions	WWW WWB WBW WBB BWW BWB BBW BBB WWW    R  M  X  X  X  X  X WWB  R   MR  M  X X  X  X WBW  M  MR    R  LM LMR  L  X WBB  X  M  R    X  LM  X  X BWW  X  X  LM  X    R  M  X BWB X  X LMR  LM  R    MR X BBW X  X  L  X  M  MR    R BBB X  X  X  X  X  X  R   Realized State Transitions
Writing the generators for such a completely connected world is quite straightforward.The three generators required are: Change the color of one rectangle: 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) Change the color of two rectangles: 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, opp(b)), color(z, c) Change the color of three rectangles: 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, opp(b)), color(z, opp(c))      However, as illustrated in the figure at the top of this page titled "Example Space" as well as in the matrix to the right above, the example world does not exhibit this degree of regularity. Within the matrix titled "Realized State Transitions" the cells marked with an X indicate transitions that are not possible in the example world. Consequently, a set of generators is required that restricts the transitions that are possible.      Consider first the transitions that change the color of only one rectangle. This subspace is shown in the figure above and to the right title "Single Rectangle Changes in the Example Space" and is shown next to the space that illustrates all possible such changes. At least three generators are needed ­ one for each of the different rectangles. Consider first the transitions that involve the rectangle on the left (labeled L in the matrix above). The only transitions possible are between the states labeled WBW and BBW. The first generator listed below captures these two transitions.      Consider next the transitions that involve the rectangle in the middle (labeled M in the matrix above). The only transitions not possible are between the states labeled BWB and BBB. The second generator listed below captures the allowed transitions. Finally, consider the transitions that involve the rectangle on the right (labeled R in the matrix above). In this case, all of the possible transitions involving the change in color of this rectangle are allowed in the world of our example. This regularity is captured in the third generator listed below. Change the color of one rectangle: Rectangle L if name(L), name(M), name(R), color(L, a), color(M, B), color(R, W) then name(L), name(M), name(R), color(L, opp(a)), color(M, B), color(R, W) Rectangle M if name(L), name(M), name(R), color(L, a), color(M, b), color(R, c), ne(a,B), ne(c,B), then name(L), name(M), name(R), color(L, a), color(M, opp(b), color(R, c) Rectangle R if name(L), name(M), name(R), color(L, a), color(M, b), color(R, c), then name(L), name(M), name(R), color(L, a), color(M, b), color(R, opp(c))
Two and Three Rectangle Changes in the Example Space	All Possible Two Rectangle Changes
Next we consider the transitions that involve changing the color of two of the rectangles. The figure to the above right depicts all possible such transitions. And the figure to the immediate above left depicts, using the yellow lines, the actual transition allowed in the example world. Examination of the matrix above shows that none of the allowed transitions involving two rectangles are defined for the pair of rectangles LR. However, there are transitions involving the remaining two pairings; namely LM and MR.      Consider first the transitions that involve the left and middle rectangles, labeled LM in the matrix above. Two pairs of transitions involving these rectangles are allowed; namely, WBW­BWW and WBB­BWB. Here the transition simply switches the colors of LM. The first generator listed below captures this regularity. The other possible transitions involving LM; namely, WWW­BBW and WWB­BBB are disallowed by this rule because the pair that are changed are not opposite in color.      Next consider the transitions involving both the middle and right rectangles. These are labeled MR above. Again there are two transition of this type possible; WWB­WBW and BWB­BBW. Again the colors of the rectangles occupying the middle and right positions are switched on the transition.The second generator listed below captures this regularity. Change the color of two rectangles: Rectangles LM if name(L), name(M), name(R), color(L, a), color(M, opp(a)), color(R, c), then name(L), name(M), name(R), color(L, opp(a)), color(M, a), color(R, c) Rectangles MR if name(L), name(M), name(R), color(L, a), color(M, b), color(R, opp(b)), then name(L), name(M), name(R), color(L, a), color(M, opp(b), color(R, b)
All Possible Three Rectangle Changes	Finally, the figure to the left, titled "All Possible Three Rectangle Changes" depicts all of the possible changes of the colors of all three rectangles on a given transition.The one such transition in the world of our example is depicted by the black line that connects the states labeled WBW and BWB in the figure shown above on the left titled "Two and Three Rectangle Changes in the Example Space." The rule listed below captures the information required to express this last generator.       Had the example world involved states that were completely connected, then three generators would have sufficed to capture the regularities in this example world. In fact, the example world allows 26 state transitions. And, the transitions allowed appear at first glance to be a rather haphazard sample from those that are possible. Nonetheless, six generators sufficed to capture this set of transitions..
Rectangles LMR if name(L), name(M), name(R), color(L, a), color(M, opp(a)), color(R, a), then name(L), name(M), name(R), color(L, opp(a)), color(M, a), color(R, opp(a))
The set of generators developed here are not unique. Obviously, the adoption of a different language for describing the states of the example world can affect the definition of the set of generators. Additionally, we could have chosen to use more generators to represent the transitions and perhaps someone can find a clever way in which to use fewer transitions.      The general strategy that was followed in identifying the set of generators was to consider first the logical or mathematically defined set of possible state transitions. The actual constraints of the world were then viewed from this perspective. Note, that this strategy is possible because the world is described combinatorially; consequently, "its" combinatoric structure can be "discovered". Again, contrast this with the representation of a state of the world simply as a name (or node in a graph) rather than as a state that is described. The shift from an explicitly represented graph to an implicitly represented "graph" has taken us to a world in which the regularities of the world represented must be discovered and exploited!

	Graph Search-An Example
© Charles F. Schmidt	AI and Search -Table of Contents