Generate and Test Assignment

The figure to the right depicts two sets of three rectangles. Let the left set of the three rectangles represent the starting state and the right set the goal state. Formulate this problem as one of state space search. That is, provide a set of generators, a test, and a language for representing the states of this world. Include in the generators operators that "paint" the rectangle either black or white. If you have used more than one generator then order your generators randomly. Note that you have not been provided all of the information required to define the semantics of this world. In addition to formulating the problem as one of state space search, also specify the semantics of your world and evaluate the degree to which these semantics have been captured in your formulation of the problem.		Start State / Goal State
Create the search tree associated with your state space formulation when the search is carried out as: a depth-first search, a breadth-first search and a heuristic search using an evaluation function that you define. Consider the following possible semantics as reflected in the changes to the set of generators listed below: The only generator is one that changes the color of a white rectangle to black. A generator, Ga, that when applied to a rectangle destroys the rectangle if it is white. A generator, Gb, such that it destroys the rectangle if it is white but generates an additional rectangle if it is black. How do these changes affect the search space and the search for a solution that you formulated for the original problem?

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