« PreviousContinue »
It would not be unreasonable to expect that current and future exporimentation will lead to the crystallization of additional concepts (such as, perhaps, Minsky's (1974) Prune Systens) that will be incorporated in a dou round of Al laaquages, Dossibly in the late 1970s.
research) are now commonly used in many Al programs and in many of their applications. Most of these techniques make use of heuristically-based evaluation functions that rank-order the unexplored nodes in the graph and thus indicate where search can most efficiently proceed. Purthermore, there are some theorens (Hart et al. (1968)] stating conditions under which these search nothods are guaranteed to Pind optimal paths. The probla of efficiently searching a paph has essentially been solved and thus no longer occupies AI researchers. This one core ara, at least, seems to be well under control.
2,3 First-level applications topics
3.3.1 Game playing (Chart 5)
2.2.4 AI systems and languages (Chart 1)
The programming languages developed and used by AI researchers are included among the core topics because they embody the most useful of the core ideas already discussed. Early Al researchers saw the need for programs that could store, access, and manipulate lists of symbolic information. The means for achieving these and other operations were built into various list processing languages, primarily IPL-V and LISP.
Programs have been written that can play several games that humans find difficult. As the most famous example, wo night mention the chess playing progran, MAC-HACK, of Groenblatt et al. (1967). A version of this progran achieved a United States Chess Federation rating of 1720 in one tournament. Samuel's programs for checkers have benten experts in the game. Several other prograns are mentioned in the chart.
Levy (1970) described a progru vritten by Atkins, Slate, and Gorland at Northwestern University and said that he thought it was stronger than Greenblatt's. He estimated its rating at about 1750, which would make it, he clains, the 500 th best player in Britain.
After some years of research using these languages, it became apparent that Al systens had a common, recurring need for operations such as search, expression-retrieval, and pattern-natching. The next step was to build these operations into the languages themselves. Thus, in the late 1960s, another generation of Al languages emerged, languages such as QA4 and PLANNER.
Computer chess tournaments are now held routinely. Results of these and other news about computer chess have been rather extensively reported in the SIGART Newsletter since 1972,
Edward Feigenbaum once characterized progress in AI research as progress along the "what-to-how" spectrum of computer languages. At the "how" end of this spectrum are the machine languages used by programmers who must give the most detailed instructions to the computer. As one progresses toward the "what" end, the programmer leaves more and more of the details of how operations are to be carried out to the language and can be more and more concerned only with what is to be done. Al languages are now moderately far along toward the "what" end, and the proper goal of AI research (according to this view) is to create languages even closer to the "what" end. It may voll be that, ultimately, the field of Al will in large part be concerned with the development of superpowerful computing languages. In this light, the best way to measure al progress is to look at the AI languages.
Most game playing prograns still use rather straightforward tree-searching ideas and are weak in their use of high-level strategic concepts. It is generally agreed that advances in the use of strategy and in end-game play are necessary bofore chess programs can become substantially better, and they must become substantially better before they can beat human champions(World Champion Bobby Fischer is rated at about 2810.) Levy (1970) is rather pessimistic about the rate of future progress in chess and has nade a £750 bet with Professors McCarthy, Papert, and Nichie that a progru cannot beat hin in a match by August 1978. (Levy's rating in 1970 was 2380.)
2.3.2 Math, science, and engineering aids (Chart 6)
We do not have space here to trace the development of Al languages nor to describe the special features that they make available to al researchers. Fortunately, there is an excellent tutorial paper by Bobrow and Raphael (1973) that gives a very clear account of the new languages.
The chart lists just a few examples of AI techniques that have been applied in systems that help human. professionals. The early Al work on symbolic integration, together with the work on algebraic simplification, contributed to a number of systens for symbolic nathenatical computations. Moses (19716) presents a good review. Systens presently exist that can solve symbolically an equation like ,2x - 3yt + 2 = 0 (for x), and that can integrate symbolically an expression 11ke f(x + e*)? dx. Such systems are quite usefully employed in physics research, for example, in which expressions arise having hundreds of terus.
Currently, 1 large part of Al research is being conducted by experimenting with systens witten in the new languages. The languages provide especially powerful mechanims for representing the extensive knowledge needed by present prograns. Furthermore, this knowledge can now be easily added incrementally us the program evolves under the tutelage of human experts in the donata. Winograd's (1971) natural language understanding syster and Waldinger and Levitt's (1974) system for proviag assertions about programs are good examples of bow the power of there languages is being used.
Another qui te successful application is the DENDRAL program that hypothesizes chemical structures from e combination of mass spectrogram and nuclear magnetic resonance data. The systen is presented with this data from 'a sample of a known chenical compound (that is, its chemical formula is known). It uses poveral lovels of knowledge about chenical structures and how they break up in mass spectroscopy to infer the structure of the compound. It can deal vitt. a large number of organic compounds including complex anines and estrogenic steroids. Its performance on the steroids often exceeds the best human perforance.
results announced wi thout proof in the Notices of the American Mathematical Society. ]
Various strategies were developed to improve the efficiency of the resolution provers. These strategies were mainly based on the form or syntax of the expressions to be proved and not on any special knowledge or semantics of the domain. In automatic theorem proving, just as in other applications areas, semantic knowledge was needed to improve performance beyond the plateau reached by the late 1960s.
The DENDRAL project typifies a style of Al system building that has been quite successfully applied to chemistry and some other domains. This design style involves intensive interaction between Al scientists and applications area scientists. The latter are queried in the minutest detail to extract from them rules and other knowledge that are operationally useful in the domain. These are then coded into the syster by the Al scientists and tests are run to judge their effectiveness. The process is long and involves several iterations. The applications scientists are often confronted with apparent contradictions between how they say they make decisions and how they actually make decisions. Few of them have any really global or completely accurate theory of how they apply their knowledge. Furthermore, this knowledge is often informal and heuristic. As a result, the emerging system is a collection of "minitheories" and special rules of only local effectiveness. To use this design strategy, the system must be one that can deal with many, and some times conflicting, mini-theories.. it must also be a system to which new knowledge can gradually be added and old knowledge modified.
The work of Bledsoe and his students is typical of the third and latest theme in automatic theorem proving. Although they emphasize the importance of manmachine systems, their programs themselves have become knowledge-based specialists in certain mathematical domains. The use of semantic knowledge in theoremproving systems has also renewed interest in heuristics for subgoaling, and so forth. The prograns of this group are capable of proving some rather impressive theorems, and it can be expected that the present nan-machine systems will produce ever more competent and more completely automatic offspring.
2.3.4 Automatic programming (Chart 8)
After several months or years of this sort of gradual shaping of the system, it comes to simulate the performance of the human experts whose knowledge it has gained. This general strategy is beginning to be employed extensively in Al applications. (For example, see also Shortliffe et al. (1973).)
Work in automatic programming has two closely interrelated goals. One is to be able to prove that a given program acts in a given way; the other is to synthesize a program that (provably) will act in a given way. The first might be called program verification and the second program generation. Work on one goal usually contributes to progress toward the other; hence, we combine them in our discussion.
2.3.3 Automatic theorem proving (Chart 7)
There are three major themes evident in attempts to get computer programs to prove theorems in mathematics and logic. First, early work by AI researchers produced heuristic programs that could prove simple theorems in propositional logic and highschool level theorems in plane geometry. These prograns used (but mainly helped to refine) concepts like reasoning backwards, means-ends analysis, use of subgoals, and the use of a model to eliminate futile search paths. The fact that logicians had already developed powerful procedures that effectively eliminated propositional logic as a domain requiring heuristic problem-solving techniques does not detract from the value of this early work.
Most of the work on program verification is based on a technique proposed by Floyd (1967). (See also Turing (1949).] This technique involves associating assertions with various points in the flow chart of a program and then proving these assertions. Originally, the assertions had to be provided by a human, but some recent work has been devoted to generating the assertions automatically. Once proposed, one can attempt to have the assertions proved either by a human or by a machine. The latter course involves a close link between this field and that of automatic theorem proving.
A recent system developed at the Stanford Research Institute (Elspas et al. (1973)) is typical of one in which the assertions are both produced (Elspas (1972)] and proved (Waldinger and Levitt (1973)) automatically. This system has been used to verify several programs including a real-number division algorithm and some sort programs, It has also proved theorems about a pattern matcher and a version of Robinson's (1965) unification algorithm. It is a good example of a modern Al program in that it makes effective use of a large amount of domain-specific knowledge.
Logicians were also developing techniques for proving theorems in the first order predicate calculus. J. A. Robinson (1965) synthesized some of this work into a procedure for using a single rule of inference, resolution, that could easily be mechanized in computer programs. Building resolution-based provers quickly became a second theme in automatic theorem proving, while other approaches languished. Resolution had a great influence on other application areas as well (Charts 1 and 8). Performance of the resolution systems reached impressive, if not superhuman, levels. Programs were written that could prove reasonably complex, sometimes novel, theorems in certain domains of mathematics. The best performance, however, was achieved by man-machine systems in which a skilled human provided strategic guidance leaving the system to verify lemmas and to fill in short chains of deduction. (See especially Guard et al. (1969) and Allen and Luckhan (1970). The latter system has been used to obtain proofs of new na thematical
The closely related work on program generation has succeeded in producing some simple programs. Typical of this work is the system of Buchanan and Luckham (1974). Broadly viewed, the problem of constructing a computer program includes the problem of constructing a plan, say, for a robot, and thus there are close links between work in automatic programming, robotics, and common-sense reasoning and deduction.
Sussman's (1973) HACKER is another system that writes simple programs for a limited domain (the BLOCKS world). Sussman's goal for HACKER is for it to simulate his own programming style. An important feature of HACKER is its strategy of attempting first to
lead to a resurgence of interest in general robot systens, perhaps during the late 1970s.
vrite a simple "let's-hope-that-this-vill-do" program, and then debugging it until it does succeed at its task. To employ this strategy, HACKER uses a great deal of knowledge about likely cluses of program bugs and how to fix then.
2.3.6 Machine vision (Chart 10)
Again, some of the most successful work has been in connection with man-machine systens. We include in this category certain aids to human programmers such as those found in the INTERLISP system (Teitelman (1972a, b, 1973)). In fact, any techniques that help make the production of programs more efficient might be called part of automatic programming. Balzer (1972) provides a good summary of this broad view of the field.
The ability to interpret visual insges of the world 1s adequate enough even in some insects to guide many complex behavior patterns. Yet the analysis of everyday visual scenes by machine still remains a largely unconquered challenge to AI researchers. Early work concentrated almost exclusively on designing systems that could classify two-dimensional images into a small number of categories--alphanumeric character recognition, for example, in fact, much of the AI work during the 1950s was concerned with pattern recognition. Researchers, such as Frank Rosenblatt and Oliver Selfridge, vere influential in shaping this early period. Pattern classilication (or recognition) continues as a separate active research interest, but since about 1965, AI interest in vision has centered on the more difficult problem of interpreting and describing complex three-dimensional scenes. Both aspects, classification and description, are thoroughly and clearly treated in an excellent textbook by Duda and Hart (1973).
2.3,5 Robots (Chart 9)
Every now and then, man gathers up whatever technology happens to be around and attempts to build robots. During the late 1960s, research on robots provided a central focus for integrating much of the AI technology. To build an intelligent robot is to build a model of nan. Such a robot should have general reasoning ability, locomotive and manipulative skills, perceptual (especially visual) abilities, and facility with natural language. Thus, robot research is closely linked with several other applications areas. In fact, most of the research on machine vision (Chart 10) was, and is, being performed in connection with robot projects.
Our problem-solving and representational techniques are probably already adequate to allow useful general purpose robot applications; however, such robots would be perceptually impoverished until we develop nuch more powerful visual abilities. Robotics is a particularly good domain in which to pursue the necessary vision research.
Much of the scene analysis work can be traced to Robert's (1963) influential thesis. It established a trend of analyzing scenes composed of prismatic solids (the so-called "blocks world"). Working with these (sometimes complex) scenes composed of simple objects helped to establish a wide range of techniques for converting raw video images into symbolic descriptions based on concepts such as lines, regions, and simple shapes. The MIT "COPY" system, for example, can use a visual input device to look at a scene consisting of a structure of blocks. The system can analyze the scene to form a representation of how the blocks are arranged. This representation can then later be used (with the robot an system) to reproduce this exact block structure from disarranged blocks.
The robot research of the late 1960s produced systems capable of forming and then intelligently executing plans of action based on an internal model of the world. The Edinburgh, Stanford, HITAC, and MIT systens consisted of manipulator arms and TV cameras or other visual input devices. These became capable of building structures out of simple blocks. In one case (Stanford), the system could assemble an automobile water pump. The Stanford Research Institute system consisted of a mobile cart and TV camera (but no arm). It could form and execute plans for navigating through a simple environment of rooms, doorways, and large blocks, and its visual system could recognize and locate doorways, floor-wall boundaries, and the large blocks. The system had sophisticated techniques to allow it to recover from errors and unforeseen circumstances, and it could store (learn) generalized versions of the plans it produced for future use.
Some successful excursions outside the blocks world have been nade. (See the entries to the right of the dashed line in Chart 10). Indeed, many researchers contend that continuing to work with blocks has actually hindered research progress in nachine vision because it has allowed workers to avoid facing certain key problems associated with domain semantics, distinguishing features of complex objects, and new representational schemes. In any case, working with more complex scenes is now well established. The spirit of recent work is well described in a note by Tenenbaum (1973). Again, knowledge about the domain is crucial to scene interpretation!
2.3.7 Natural language systems (Chart 11)
Since practical applications of general purpose robot systems seen more remote than they do in other applications areas, the increasingly pragmatic research climate of the early 1970s has seen a lessening of activity in general robotics research. In the meantine, various projects with the practical goal of advancing industrial automation have begun to apply some of the already-developed manipulative and visual skills to factory assembly and inspection problens, It seems reasonable to predict that man's historic fascination with robots, coupled with a new round of advances la vision and reasoning abilities, will
Processing written and spoken forms of natural languages has been the subject of so much research that the task of surveying progress in this field alone should humble anyone. How, then, are we to say anything very helpful in just a few sentences. The interested reader should see the GENERAL volumes cited in Chart 11.
Perhaps a description of the power of some representative systems will suffice. Winograd (1971)
because the concepts out of which to construct these theories had not yet beon formulated. Botore we have the concepts (and they are now gradually accumulating) 1t is as impossible to understand human thought us it was impossible to understand navigation, say, before ve had the concept of sonar. Man understands the world by constructing models, and his models are of ten based on concepts drawn from his technological investions. We may not understand aan immediately after building the first robot, but w certainly won't understand him before! (We note in passing that knowledge about the structure and function of the neuron-or any other basic component of the brain is irrele vant to the kind of understanding of intelligence that we are seeking. So long as these components can per forn some very simple logical operations, then it doesn't really matter whether they are neurons, relays, vacuum-tubes, transistors, or whatever.)
An excellent short account of the relationship between AI and psychology has been written by Newell (1970). While he, perhaps prudently, adopts a somewhat less extreme position than nine about the dependence of psychology on AI, he nevertheless shows how thoroughly information processing Ideas have penetrated psychological theory.
Most of the information-processing-based psychology to date has been devoted to explaining either memory (e.8., EPAM and HAM in Chart 12), perception (e.8., Sternberg (1966)), or problem solving (e.8., Newell and Simon (1972)). Probably the most complete attempt at understanding human problem-solving ability is the last-mentioned work of Newell and Simon. This volume proposes an infornation processing theory of problem-solving based on the results of many years of research in psychology and AI.
Animal behavior, while long the special interest of experimental psychologists, has had 11ttle information-processing-based theoretical attention, Some models inspired by ethologists have been proposed by Friedman (1967). I think that the production system model advanced to explain certain human problem solving behavior by Newell (1967) and colleagues might be a starting point for an extensive theory of animal behavior. Newell, himself, notes that these production systems can be viewed as generalizations of stimulus-response systems. (Incidentally, the entire repertoire of what was called "intermediate-level actions" of the Stanford Research Institute robot system (Raphael et al. 1971) vas Independently programned in almost exactly this production formalism, Production systens have been used in other AI programs as well.] Newell and Simon (1972, p. 803) have also stated that they "have a strong premonition that the actual organization of human problem solving 'programs closely resembles the production system organization ...."
" It would seem profitable then to attempt to trace the evolutionary development of this hypothesized production system organization down through some of the higher animals at least.
implemented a syster that carried on "blocks-world" written dialogs like the following:
Man (typing into a terminal): Which cube is sitting
on the table? System (generating text on a display): The large
groen one which supports the red pyramid. W: Is there a large block behind e pyramid? S: Yes, three of them: A large red one, a large
green cube, and the blue one. N: Put a small one onto the green cube which sup
ports a pyranid. S: OK *: Put the littlest pyramid on top of it. S: OK
The system demonstrates its understanding of the last two commands by having a simulated robot an carry out appropriate actions in a simulated blocks world.
The work of Schank (1972) typifies a rather successful trend in natural language understanding. Many of the recent systems, in one way or another, attempt to natch a section of input text or utterance against semantically likely stored structures (that are more or less complex.) These structures are themselves schemas or scenario families having variables that are bound to constants in the input during matching. The instantiated scenarios serve as a sort of deep structure that represent the meaning of the utterance. (See also Minsky (1974).)
The goals of a coordinated scientific effort to produce systems to understand limited utterances of continuous speech are clearly outlined in a plan by Newell et al. (1971). If the goals are met, by 1976 a prototype system should be able (in the context of a limited domain of discourse) to understand (in a few times real time) an American (whose dialect is not extremely regional) speaking (in a "natural" manner) ordinary (although perhaps somewhat simple) English sentences constructed from a 1000-word vocabulary. These projects bring together workers in acoustics and speech research as well as in Al. The projects seem to be more or less on schedule and will probably achieve creditable performance by 1976. (In the spirit of the vagueness of the phrase "a few times real time," the projects ought to achieve the 1976 goals at least sometime in the late 1970s.)
In my opinion, the work in natural language understanding is extremely important both for its obvious applications and for its future potential contributions to the core topics of Al. It is the prime example of a field in which reasonable performance could not be achieved by knowledge-impoverished systems. We now know that understanders need large amounts of knowledge; the challenge is to attempt to build some really large systems that have the adequate knowledge and to learn, by our mistakes, the organizational principles needed to keep these large systems from becoming unwieldy.
2.3.8 Information processing psychology (Chart 12)
Computer science in general and AI in particular have had a tremendous impact on psychology. They provide the concepts and the very vocabulary out of which to construct the most useful theories of human behavior. In my opinion the reason that, say, prior to 1955, there rere, in fact, no adequate theories of human behavi, perception, and cognition 15
In summary, we see that the Al campaign is being waged on several different fronts, and that the victories, as well as the setbacks, contribute to a growing common core of ideas that aspires to be a science of Intelligence. Against this background,
On the other hand, what 11 we already have bost of the ideas that we are going to get, ideas 11ke millions of coordinated mini-theories, procedural embedding of knowledge, associative retrieval, and scenario frames. Suppose that we have now only to devote the large elfort required to build really huge intelligent systems based on these ideas. To my knowledge, no one advocates this alternative view, but consider this: · Whatever the nature of an intelligent system, it will be exceedingly complex, Its performance will derive in large part from its complexity. We will not be sure that Al is ready to build a large, intelligent system until after we have done so. The elegance of the basic ideas and the new and powerful languages alone will not be sufficient indication of our naturity. At some time, we will have to put together exceedingly complex systems. The time at which it is appropriate to try will always be a guess.
My guess is that we still have a good deal of work to do on the problem of how to obtain, represent, coordinate, and use the extensive knowledge we now know is required. But these ideas will not come to those who nerely think about the problen. They will come to those who both think and experiment with much larger systems than we have built so far.
Another problem, of a more practical type, concerns knowledge acquisition. Today, the knowledge in a program must be put in "by hand" by the programmer although there are beginning attempts at getting programs to acquire knowledge through on-line interaction with skilled humans, To build really large, knowledgeable systems, we will have to "educate" existing programs rather than attempt the almost impossible feat of giving birth to already competent ones. (Some researchers (e.g., Papert, 1972) expect that at least some of the principles we discover for educating programs will have an impact, perhaps revolutionary, on how we educate people. ]
In this connection, we have already mentioned that several successful al systems use a combination of man and machine to achieve high performance levels. I expect this research strategy to continue and to provide the setting in which the human expert(s) can gradually transfer skills to the machine. (Woods and Nakhoul (1973) consciously apply a strategy such as this and call it "incremental simulation."]
I have not yet mentioned in this paper the subject of learning. It is because I have come to agree with John McCarthy that we cannot have a program learn a fact before we know how to tell it that fact and before the program knows how to use that fact. We have been busy with telling and using facts. Learning them is still in the future, although some isolated successes have, in fact, occurred. (See especially, Samuel (1959, 1967), Winston (1970), Fikes et al. (1972a), and Sussman (1973).)
it is worth mentioning some of the popular criticisms of AI:
(1) AI hasn't really done anything yet. There are . Tev "toy" programs that play middling chess and solve simple puzzles like "missionaries and cannibals," but the actual accomplishments of AI measured against its proni ses are disappointing. (See, for example, Dreyfus (1965, 1972). ) [My comment about this kind of criticism is that its authors haven't really looked at AI research past about 1960.] (2) Not only has AI not achieved anything, but its goals are actually impossible. Thus, Al is something 11ke alchemy. It is impossible in principle to progran into computers such necessities of intelligence as "fringe consciousness" and "perspicuous grouping." (Again, see Dreyfus (1965, 1972).) [This kind of criticism is actually rather brave in view of the fate of nany previous impossibility predictions. This attack simply looks like a poor bet to me.] (3) The subject matter of Al, namely intelligence, is too broad. It's like claiming science is a field. (This criticism may have some merit.) (4) Everything happening in AI could just as well happen in other parts of computer science, control engineering, and psychology. There is really no need for this AI "bridge" between already established disciplines. (See Lighthill (1973).) (This kind of criticism caused quite a stir in Great Britain recently. I think I have shown that the so-called bridge has quite a bit of internal structure and is contributing a heavy traffic of ideas into its termini.) (5) AI is impossible because it is attempting to reduce (to understanding) something fundamentally "irreducible." Furthermore, this very attempt is profane; there are certain awesome mysteries in life that best remain mysterious. (See Roszak (1972).] (My prejudice about this view is that, at best, it is, of course, nonsense. A blind refusal even to attempt to understand is patently dangerous. By all means, let us not foreclose a "rhapsodic understanding" of these mysteries, but let us also really understand them.] (6) AI is too dangerous, so it probably ought to be abandoned--or at least severely limited. (see Weizenbaum (1972).) (My view is that the potential danger of AI, along with all other dangers that man presents to himself, will survive at least until we have a science that really understands human emotions. Understanding these emotions, no less than understanding intelligence and perception, will be an ultimate consequence of AI research. Not to understand them is to be at their mercy forever, anyway.)
The one criticism having any weight at all, I think, is that Al may be too broad and diverse to remain a cohesive field. So far, it has stayed together reasonably well. Whether it begins to fractionate into separate exotic applications areas of computer science depends largely, I think, on whether these applications continue to contribute core ideas of great generality.
What is the status of these core ideas today? There are two extreme views. I have heard John McCarthy say (perhaps only provocatively to students) that really intelligent prograns are a long way oft and that when we finally achieve them they will be based on ideas that aren't around yet. Their builders will look back at al in 1974 as being a period of pre-history of the field,
Continuing our discussion of the likely future of AI, ve note that the increasingly pragmatic attitude of those who have been sponsoring Al research will have a great offect on the course of this research. There may even be a temporary reduction of effort by AI researchers in the core topics and the f!rst-level applications areas in favor of increase support of engineers and scientists building second-level applications. The results of these second-level efforts nay, in fact, be rather spectacular. I have in mind such things as automated factories, automatic robots