« PreviousContinue »
Nils J. NILSON
Artificial Intelligence Center, Stanford Research Institute
Menlo Park, California 94025, USA
This paper is a survey of Artificial Intelligence (AI). It divides the field into four core topics
Can we ever hope to understand the nature of intelligence in the same sense that we understand, say, the nature of flight? Will our understanding of intelligence ever be sufficient to help us build working models--machines that think and perceive--in the same way that our understanding of aerodynamics helps us build airplanes? Intelligence seems so varied. We see it when a chemist discovers the structure of a complex molecule, when a computer plays chess, when a mathematician finds a proof, and even when a child walks home from school. Are there basic mechanisms or processes that are common to all, of these activities and to all others commonly thought to require intelligence?
These are the emerging beliefs of a group of computer scientists claiming to be founding a new science of intelligence. While attempting to discover and understand the basic mechanisms of intelligence, these researchers have produced working models in the form of computer programs capable of some rather impressive feats: playing competent chess, engaging in limited dialogs with humans in English, proving reasonably difficult mathematical theorems in set theory, analysis, and topology, guessing (correctly) the structure of complex organic molecules from massspectrogram data, assembling mechanical equipment with a robot hand, and proving the correctness of small computer programs.
Whether the activities of these workers constitute a new scientific field or not, at the very least Al is a major campaign to produce some truly remarkable computer abilities. Like going to the moon or creating life, it is one of man's grandest enterprises. As with all grand enterprises, it will have profound influences on Ran's way of life and on the
way in which he views himself. In this paper, I will try to describe the AI campaign, how it seems to be organized into subcampaigns, who is doing what, some of the current internal controversies, and the main achievements. There is the usual word of caution: I've made some rather large simplifications in attempting to stand aside from the field and look at it with perspective. Not all workers would necessarily agree with what follows.
Before beginning we must discuss an important characteristic of AI as a field, namely, that it does not long retain within it any of its successful applications. Computer aides to mathematicians, such as differential equation solvers, that originated (at least partly) from Al research, ultimately become part of applied mathematics. A system, named DENDRAL, that hypothesizes chemical structures of organic molecules based on mass-spectrogram data is slowly escaping its Al birthplace and will likely become one of the standard tools of chemists. This phenomenon is well-recognized by Al researchers and has led one of them to state that Al is known as the "no-win" field. It exports all of its winning ideas.
On reflection, this is not surprising. When a field takes as its subject matter all of thinking, and then when particular brands of that thinking are applied to chemistry, mathematics, physics, or whatever, these applications become parts of chemistry, mathematics, physics, etc. When people think about chemistry, we call it part of chemistry--not an application of psychology. The more successful Al becomes, the more its applications will become part of the application area.
Destined apparently to lack an applied branch, is there a central core or basic science of Al that will continue to grow and contribute needed ideas to applications in other areas? I think the answer is
Just what form these central ideas will ultimately take is difficult to discern now. Will Al be something like biology--diverse but still united by the common structure of DNA? What will be the DNA of AI?
Or will the science of Al be more like the whole of science itself--united by little more than some vague general principles such as the scientific method? It is probably too early to tell. The the applications areas themselves. Until all of the principles of intelligence are uncovered, AI researchers will continue to search for then in various first-level applications areas.
As a tactic in attenpting to discover the basic principles of intelligence, Al researchers have set thenselves the preliminary goal of building computer programs that can perform various intellectual tasks that humans can perform. There are major projects currently under way whose goals are to understand natural language (both written and spoken), play master chess, prove non-trivial na thematical theorens, write. computer programs, and so forth. These projects serve two purposes. First, they provide the appropriate settings in which the basic mechanisms of intelligence can be discovered and clarified. Second, they provide non-trivial opportunities for the application and testing of such mechanisms that are already known. I am calling these projects the first-level applications of Al.
If an application is particularly successful, it might be noticed by specialists in the application area and developed by then as a useful and economically viable product. Such applications we night call second-level applications to distinguish them from the first-level applications projects undertaken by the AI researchers themselves. Thus, when Al researchers work on a project to develop a prototype system to understand speech, I call it a firstlevel application. 11 General Motors were to develop and install in their assembly plants a systen to interpret television images of automobile parts on a conveyor belt, I would call it a secondlevel application. (We should humbly note that perhaps several second-level applications will energe without benefit of obvious AI parentage. In fact, these may contribute nightily to Al science itsell.)
Thus, even though I agree that Al is a field that cannot retain its applications, it is the secondlevel applications that it lacks. These belong to
Figure 1, then, divides work in Al into twelve major topics. I have attempted to show the major papers, projects, and results in each of these topics in Charts I through 12, each containing references to an extensive bibliography at the end of this paper. These charts help organize the literature as well as indicate some thing about the structure of work in the field. By arrows linking boxes within the charts we attempt to indicate how work has built on (or has been provoked by) previous work. The items in the bibliography are coded to indicate the subheading to which they belong. I think that the charts (taken as a whole) fairly represent the important work even though there may be many differences of opinion among workers about some of the entries* (and especially about how work has built on previous work).
Obviously, a short paper cannot be exhaustive. But in this section I will summarize what is going on in Al research by discussing the major accomplishments and status of research in each of the twelve subheadings.
2.2 The core topics
Fundamentally, Al is the science of knowledge--how to represent knowledge and how to obtain and use knowledge. Our core topics deal with these fundamentals. The four topics are highly interdependent, and the reader should be warned that it is probably wrong to attempt to think of them separately even though we are forced to write about them separately.
2.2.1 Common-sense reasoning, deduction, and
problem-solving (Chart 1)
By reasoning, etc., we mean the major processes involved in using knowledge: Using it to make inferences and predictions, to make plans, to answer questions, and to obtain additional knowledge. As a core topic, we are concerned mainly with reasoning about everyday, common domains (hence, common sense) because such reasoning is fundamental, and we want also to avoid the possible trap of developing techniques applicable only to some specialized domain. Nevertheless, contributions to our ideas about the use of knowledge have come from all of the applications areas.
There have been three major themes evident in this core topic. We might label these puzzle-solving, question-answering, and common-sense reasoning.
Puzzle-solving. Early work on reasoning concentrated on writing computer programs that could solve simple puzzles (tower of Hanoi, missionaries and cannibals, logic problems, etc.). The Logic Theorist and GPS (see Chart 1) are typical examples. From this work certain problem-solving concepts were developed and clarified in an uncluttered atmosphere. Among the se were the concepts of heuristic search, problem spaces and states, operators (that transformed one problem sta te into ano ther), goal and subgoal states, meansends analysis, and reasoning backwards. The fact
In particular, some might reasonably clain machine vision (or more generally, perception) and language understanding to be core topics.
CONCEPTS McCarthy (1954)
GPS Howell, Show and
Simon (1960) Ernst and Nowell (1969)
DEDUCOM Staple (1965)
REF-ARF Files (1961, 1970)
PLANNER Hewitt (1989, 1971, 1972)
SMADLU Winoprad (1971)
ZORBA Kling (1971)
STRIPS Fikus and Nitason (1971) Fikes, at al (1972) Sucerdoti (1973)
QAL Derksem, at al
(1972) Rulitson, at al (1972)
HACKER Summan (1973)
STORIES Chorniak (1972)
BUILD Fahimon (1973)
SEMANTIC NETS Quillian (1968, 1969)
PROBLEMS OF REPRESENTATION McCarthy and
Mayu (1969) Mayus (1971, 1973) Sundowall (1971,
1972 a, D)
SYSTEMS Newell (1967) Newell (19720,0)
MERLIN loon and Mowell (1973)
PROCEDURAL REPRESENTATIONS Hewitt (1969, 1971,
1972) Winograd (1971) Rulitaon, et al (1971,
1972) Minsky and Papert (1972)
STRUCTURAL DESCRIPTIONS Winston (1970)
CHRONOS Bruce (1972)
VERRS Schonk, et al (1972) Schenk (1973)
FRAME SYSTEMS Minsky (1974)
and Luckham (1974)
CHART 1: COMMON-SENSE REASONING, DEDUCTION AND PROBLEM SOLVING
CHART 2: MODELING AND REPRESENTATION OF KNOWLEDGE
CHART 3: HEURISTIC SEARCH