The Best of Creative Computing Volume 2 (published 1977)
The Thinking Computer (General Problem Solver, Natural Language, Perception)
in a computer program, called the General Problem Solver
(GPS), demonstrates a way to redirect a single central
mechanism to a variety of different tasks with a minimum of
effort.
An important feature of GPS is that it separates taskdependent information-the
detailed description of a
particular problem, the actions or "operators" available for
use in solving the problem, and the desired results or
"goal"-from task-independent reasoning methods that
may be useful for many different types of problems. Various
strategies for finding an effective sequence of operators can
be proposed, and the GPS computer program. developed at
Carnegie-Mellon University, is a tool for comparing and experimenting with such
proposals.
GPS has a major advantage over more formal search
algorithms. It does not have to select operators in sequence from the first
operator, which is to be applied to the
initial problem, to the last operator, which is to reach the
goal. Instead, it looks atthe initial problem and the goal, and
goes to work on trying to reduce the most important difference between them. The
operator that succeeds in reducing this difference might eventually have to be
applied
somewhere in the middle of the complete sequence of
operators that solves the problem. By deciding upon this
operator first, the problem solver overcomes a major hurdle
and replaces the entire task by two simpler subtasks:
getting from the initial situation to one in which the chosen
key operator can properly be used, and getting from the
state that exists after that operator is used to a final solution.
Consider Mr. Pollack's chain-mounting problem again. A
straight-forward search procedure for figuring out how to
put on the chains would consider first the alternative
actions that are immediately possible when he stops his
car: wait for the snow to melt, or try to drive on without
chains, or turn around and go back home, or get out of the
car. If we assume he gets out of the car and is standing in
the snow storm, his next choices might include: get back
into the car, or open the trunk, or jump up and down to keep
warm. If he opens the trunk, then he can get the chains out,
or get the jack out, or get the suitcases out, or crawl in, and
so on. Eventually, if he follows the most direct course of
action, he will find himself lying in the slush under the car,
with the chain wrapped around the wheel, and his fingers
jammed up between the freezing axle housing and the hot
exhaust pipe, trying to figure out how the new-fangled linking mechanism works.
The GPS approach might begin by observing that a key
difference between having no chains on the wheels and
having chains that work correctly on the wheels is that each
chain must be linked onto a wheel. Therefore an understanding of the linking
mechanism may be singled out as
the first problem that must be solved. This problem can be
tackled by studying the manufacturer's directions or by
experimenting with the actual chains, while seated in the
warm dry car. Once the linking mechanism is understood,
the next problem is how to get to a situation in which it is
appropriate to close the links, so he might then focus attention on the
wrap-the-chain-around-the-wheel problem.
Thus the overall task is broken down into a sequence of progressively less
crucial subproblems whose solutions each
fill in a different portion of the overall solution.
Around 1969 scientists at Stanford Research Institute
developed a problem-solving system to control an experimental robot. This
system, called STRIPS, combines some
of the best features of deductive theorem-proving methods,
with informal GPS-like problem solving. One of the difficulties with using GPS
was that the user had very little
guidance as to how to represent his problem in the
computer. GPS dealt purely with abstract notions such as
objects, operators, and differences, and its success depended to a great extent
upon special characteristics of
those objects, operators, and differences, that the user
invented for himself. The principal contribution of STRIPS is
to embed into a GPS-like framework a set of specifications
for the nature of objects and operators, and a resulting automatic method for
obtaining differences. Of course, the user
must still construct a specific representation for each
specific problem, but STRIPS at least tells him the form that
that representation must take.
Current directions in problem-solving research include
the development of new programming languages that
incorporate earlier problem-solving techniques; studies of
ways to use man-machine systems more effectively in
cooperative problem-solving activities; methods to allow
problem-solving systems to use computer simulation techniques when appropriate;
and the growth of large data
bases so that problem-solving systems can have access to
the general knowledge they require.
Natural Language
Linguists are actively working on theories to explain the
nature of language and its semantics. However, technology does not usually wait
for theories to be completed.
While the linguists carry on their theoretical studies, computer scientists have
also been studying how computers
can be made to understand natural language. These studies
have been conducted from an experimental engineering
point of view.
Many of the experimental language-processing programs fall in a general category
called question-answering
systems. A question-answering system may be defined as
any computer program that understands the information
typed into it, and demonstrates that it understands by
answering questions about the information. The ideal
question-answering system should be able to: (1) accept
facts and questions, and make appropriate responses, all in
the form of natural English; (2) store, remember, and make
efficient use of a large amount of data-at least thousands
of elementary facts; (3) answer questions that require it to
figure out the logical consequences of the facts stored
explicitly in its memory; and (4) operate conversationallye.g., via a
time-sharing computer terminal-without frustrating delays. Although no system
yet developed has all
four of these capabilities a significant degree of success in
each of the four areas has been separately achieved by
various systems. In the next few years we should begin to
see these capabilities combined and improved, producing
the first true, complete question-answering systems.
We would like computers to be able to understand not
only typed and printed, but also spoken natural language.
For many years research in the field of "speech recognition" focused upon
identifying individual words purely on
the basis of their sounds, and progress was limited. Now
scientists recognize that understanding spoken language
involves using many sources of knowledge-such as
knowledge of vocabulary, syntax, and subject matter-in
addition to the perceived sounds themselves. Speechunderstanding systems now
under development integrate
such multiple sources of knowledge about language in
order to come up with an accurate understanding of what
has been said.
Perception
Suppose you are about to open some presents. Do you
need to unwrap each item completely and look at it in a
strong light in order to recognize what it is? Not usually. One
handlebar sticking out of a large, formless wrapping is
enough to identify the bicycle you had been expecting. If it's
Christmas morning and a small flat box has a tag showing
that it came from Aunt Agnes, you might know it contains
another hideous tie. On the other hand, if the occasion is
44
