Generate and Test

ARTIFICIAL INTELLIGENCE AND SEARCH

Work on the mathematical study of computation has informed us concerning the the syntax of the minimal instructions/agent that allows computation to be defined. But what is the "minimal agent/syntax" that is required to realize intelligence. This is one of the questions that researchers in the field of Artificial Intelligence have addressed. The "birth date" of AI is generally traced to the Dartmouth Conference which was held in the summer of 1956. Earlier attempts at using computers to realize "intelligent" systems had been attempted within the framework of "neural-like" networks. AI followed a more abstract road in that it sought to understand "intelligence" and design "intelligent" systems within the framework of the kind of symbol systems developed in the mathematical study of computation.

The basic requirement is to again define a kind of "dumb agent" that can carry out certain basic instructions. But, now the desire is for the "dumb agent" to be able to learn or become more intelligent as a result of its activities.The idea of search served as the starting point for our "dumb" or "minimally intelligent" agent. The basic components that are involved in search are:

Some way of representing the information that is available at the start of the search, this is usually referred to as the start state and is often symbolized as s0;
Some way of advancing the search by generating new information from the given information, these ways of generating new information are often referred to as generators or operators, and, they are thought of as partial functions which take the agent from one state of information to another;
Some way of representing the goal as a test that can be evaluated against the agent's state of information at each point in its search.

The search procedure is typically referred to as generate and test. The figure displayed to the right depicts a simple and concrete situation which we will use to discuss the ideas of search. Four colored blocks are depicted. We will pretend that the picture is the "world" and the letters at the top represent the this world.That is, if the expression at the top maps correctly into those aspects of the world that we wish to capture, then the expression is said to represent this world. In this case each block is referred to by the letter that is on its face. Also, the left to right ordering is reflected in the expression. And, finally, the '#' symbol is used to indicate the different stacks of blocks. In this case each stack contains a single block. Note that this expression does not encode the color of the blocks, the separations between the blocks, their size, and so on. For example, if the blocks were all blue, this expression would not change.

Now, assume for the moment that our problem is to create two stacks of blocks, and the situation depicted above is our initial state of the world. This goal situation might be represented by the string #wx#yz# where we treat w, x, y, and z as variables that may take any block in the world as a value.

Now, we will look at the way this problem is approached using the method of generate and test known as State Space Search. To carry out state space search we require generators that correspond to actions that can be done in our world. And, the generators should be rules that when applied to our representation of the world yield a representation of a new world. And, this new world should correspond to the world that would obtain if we had actually carried out the action represented by the generator

Several types of action can be done in our little world. The blocks could be moved about, stacked, and unstacked. Note that although we might be able to change the color of the blocks in our world by painting them, this generator can not be represented because the color of blocks is not represented in our representation language.

Clearly, we will need a stack generator to achieve our goal. The stack generator might look something like: Stack(sx,cy) which might be thought of as indicating that stack is an action that takes two arguments, a stack, sx, and a clear block, cy. To actually realize this action we would need to construct a procedure which would take an expression like #A#B#C#D# and be able to produce an expression like #A#CB#D# which represents the world shown in the next picture. We won't worry about how to actually do this since that would take us into more detail than is necessary at this point.

Now with this stack generator, we can solve the problem. For example, stack can be applied to #A#CB#D# to produce #CB#DA# as is shown in the next picture.

It is obvious that the solution can be obtained. What is less obvious is the nature of the state space within which the solution is to be found. Look again, at the initial state represented as #A#B#C#D#. How many different stacking moves can be made from this state? Well, block A could be put on top of B or C or D; B could be placed on top of A or C or D; and so on. It would appear that there are 12 different possible stacks! And, what are the stacks that could be created from these stacks? Well, take one case. If we had placed B on top of C as in the above example, then we could now place either A or D on top of the CB stack or we could place D on A or A on D. It would appear then that each of our 12 possibilities admits these 4 possibilities...thus 12 x 4 or 48 possible worlds have been considered and half of them achieve the goal.

However, note that if we had just generated those states of the world that had a stack of three blocks, then we could never achieve the goal. Or if the starting state had been #ABC#D# rather than #A#B#C#D# we would not have been able to achieve the goal, because we did not represent the action of unstacking as a generator.

We leave it to the reader to work out the details of what happens to the search space if we add this unstack generator. The world will be more realistically represented in this case and more problems are soluble in this world. But, a much larger space of states must be considered. Add the possibility of exchanging the position of blocks, for example from #A#B#C#D# to #C#B#A#D# and the space grows again.

Now, hopefully you have a better intuitive feel for the basic way in which a state space comes about. And, with this understanding you can now better appreciate the issues that arise when we consider how to systematically control the search through this space for a solution.

In order to give you another way in which to understand the basic control regimes discussed in class, you can click Search Control Stategies below to see animations of a hypothetical breadth first, depth first, and hill climbing search.

Search Control Stategies

Computational Approach

© Charles F. Schmidt

Work on the mathematical study of computation has informed us concerning the the syntax of the minimal instructions/agent that allows computation to be defined. But what is the "minimal agent/syntax" that is required to realize intelligence. This is one of the questions that researchers in the field of Artificial Intelligence have addressed. The "birth date" of AI is generally traced to the Dartmouth Conference which was held in the summer of 1956. Earlier attempts at using computers to realize "intelligent" systems had been attempted within the framework of "neural-like" networks. AI followed a more abstract road in that it sought to understand "intelligence" and design "intelligent" systems within the framework of the kind of symbol systems developed in the mathematical study of computation. The basic requirement is to again define a kind of "dumb agent" that can carry out certain basic instructions. But, now the desire is for the "dumb agent" to be able to learn or become more intelligent as a result of its activities.The idea of search served as the starting point for our "dumb" or "minimally intelligent" agent. The basic components that are involved in search are: Some way of representing the information that is available at the start of the search, this is usually referred to as the start state and is often symbolized as s0; Some way of advancing the search by generating new information from the given information, these ways of generating new information are often referred to as generators or operators, and, they are thought of as partial functions which take the agent from one state of information to another; Some way of representing the goal as a test that can be evaluated against the agent's state of information at each point in its search.
The search procedure is typically referred to as generate and test. The figure displayed to the right depicts a simple and concrete situation which we will use to discuss the ideas of search. Four colored blocks are depicted. We will pretend that the picture is the "world" and the letters at the top represent the this world.That is, if the expression at the top maps correctly into those aspects of the world that we wish to capture, then the expression is said to represent this world. In this case each block is referred to by the letter that is on its face. Also, the left to right ordering is reflected in the expression. And, finally, the '#' symbol is used to indicate the different stacks of blocks. In this case each stack contains a single block. Note that this expression does not encode the color of the blocks, the separations between the blocks, their size, and so on. For example, if the blocks were all blue, this expression would not change.
Now, assume for the moment that our problem is to create two stacks of blocks, and the situation depicted above is our initial state of the world. This goal situation might be represented by the string #wx#yz# where we treat w, x, y, and z as variables that may take any block in the world as a value. Now, we will look at the way this problem is approached using the method of generate and test known as State Space Search. To carry out state space search we require generators that correspond to actions that can be done in our world. And, the generators should be rules that when applied to our representation of the world yield a representation of a new world. And, this new world should correspond to the world that would obtain if we had actually carried out the action represented by the generator Several types of action can be done in our little world. The blocks could be moved about, stacked, and unstacked. Note that although we might be able to change the color of the blocks in our world by painting them, this generator can not be represented because the color of blocks is not represented in our representation language.
Clearly, we will need a stack generator to achieve our goal. The stack generator might look something like: `Stack(sx,cy)` which might be thought of as indicating that stack is an action that takes two arguments, a stack, `sx`, and a clear block, `cy`. To actually realize this action we would need to construct a procedure which would take an expression like #A#B#C#D# and be able to produce an expression like #A#CB#D# which represents the world shown in the next picture. We won't worry about how to actually do this since that would take us into more detail than is necessary at this point.
Now with this stack generator, we can solve the problem. For example, stack can be applied to #A#CB#D# to produce #CB#DA# as is shown in the next picture.
It is obvious that the solution can be obtained. What is less obvious is the nature of the state space within which the solution is to be found. Look again, at the initial state represented as #A#B#C#D#. How many different stacking moves can be made from this state? Well, block A could be put on top of B or C or D; B could be placed on top of A or C or D; and so on. It would appear that there are 12 different possible stacks! And, what are the stacks that could be created from these stacks? Well, take one case. If we had placed B on top of C as in the above example, then we could now place either A or D on top of the CB stack or we could place D on A or A on D. It would appear then that each of our 12 possibilities admits these 4 possibilities...thus 12 x 4 or 48 possible worlds have been considered and half of them achieve the goal.
However, note that if we had just generated those states of the world that had a stack of three blocks, then we could never achieve the goal. Or if the starting state had been #ABC#D# rather than #A#B#C#D# we would not have been able to achieve the goal, because we did not represent the action of unstacking as a generator. We leave it to the reader to work out the details of what happens to the search space if we add this unstack generator. The world will be more realistically represented in this case and more problems are soluble in this world. But, a much larger space of states must be considered. Add the possibility of exchanging the position of blocks, for example from #A#B#C#D# to #C#B#A#D# and the space grows again. Now, hopefully you have a better intuitive feel for the basic way in which a state space comes about. And, with this understanding you can now better appreciate the issues that arise when we consider how to systematically control the search through this space for a solution. In order to give you another way in which to understand the basic control regimes discussed in class, you can click Search Control Stategies below to see animations of a hypothetical breadth first, depth first, and hill climbing search.


Search Control Stategies		Computational Approach
© Charles F. Schmidt