Artificial Intellicence Research Stret..... In the Lltht of AI Models of Scientific Dlecovwy

1. AI Protramt at Theories of Discovery

By a discovery program I mean a computer program whose output Is not Inferable in any obvious way from its input. The phrase, "In any obvious way," is essential to the definition, since we know that a proaram does exactly what we proaram It to do -- which Is usually not at all the same as dolna what we supposed we had programmed It to do.

2. The Nature of Discovery

Novelty, In computers as In human beings, lies In the eye of the beholder. The result Is novel if it was not expected from the outset. But even this definition is ambiguous. As the numerous documented cases of Independent Invention attest, a discovery may be novel to the discoverer but not to the whole society, for others may already have found lt. However, to produce a novelty a second time, without knowledge that it has already been discovered by others, presumably requires the same kinds of coanltlve processes as were required to produce It the first time. Anything we can learn by examlnlna the proaram of the original discoverer we should be able 1 to learn also by examlnlna the program of the reinventer.

It Is probably true today that within any one hour period some computer program somewhere in the world has followed a path never before traversed, to produce a novel successful result. This must occur for example, more than once In almost every aame played by a hobbyist's minicomputer chess program, since chess aames rarely fully repeat others that have been played In the world. However, we aenerally do not apply the term "discovery" to every novelty of this kind, however rational or adaptive the output .may be. We require, In addition, that the novelty be in some sense remarkable or socially valuable. In particular, and borrowlna languaae from the patent law, to be an Invention, a novelty must not be "obvious to a person skilled in the art." While a minicomputer playlna Class D chess discovers many novel solutions to its problems, these solutions would presumably be discovered easily by strong players, hence would not qualify as Inventions In the legal sense.

Even today, after a quarter century of AI efforts, it is hard to point to fully convincing examples of discoveries by arti f icial Intelligence programs that satisfy this stricter definition, of belna neither rediscoveries nor obvious to one skilled In the art. If pressed on this point, I might want to defend certain products of chess programs, programs for musical composition and visual design, and theorem-provins programs as meeting the stricter reQuirements of invention, but such a defense would take me away from my main concern here.

1 Thit cleim requir .. tome qualification·. The reinvtnt., lillY po11 .. 1 know'-dt· -- not the invention ltnlf, but knowltdst reltvent to it -- thlt w .. not evtlltble to the orltlntl inventor, but which 1111kee the job ···ler the Hcond time. Liter, I wiH hive mort to ny on thle point 11 It epplilt tpeciflceHy to AI.

I will draw my examples of discovery from computer proarams that have mainly rediscovered what was already known, but whose discoveries are hardly trivial, and would indeed have been adjudged important If they had been genuinely new. I have in mind such examples as the discovery by Lenat's AM program of the concept of prime number and it8 conjecturing of the fundamental theorem of arithmetic -- that every positive integer can be represented uniquely as a product of powers of primes (Lenat, 1977). Examples of a slightly different kind are BACON's Induction from empirical data of Kepler's Third Law, Ohm's Law, and the Laws of Boyle and Charles (langley, forthcoming).

Before we take the programs that found these concepts and laws as exhibiting the essential processes for discovery, we must satisfy ourselves on one point: that the human programmers did not, in some explicit or implicit way, embed the results at the outset in the programs and their inputs. Since we have already agreed that the outputs of programs are determined by the programs (and data), what can we mean by this requirement? Simply that the derivation of the outputs from program and data be sufficiently non-obvious. This Is, of course, the same criterion we apply to a mathematical theorem to determine whether it Is "deep"; and it is the same as the legal requirement for Invention, quoted above.

This Is not to say that it is a precise criterion, statable in a formal way. The only way I know to decide whether AliA or BACON, or any other program purporting to have powers of discovery (but exhibiting those powers through rediscovery) genuinely possesses such capabilities Is to search the code carefully for hideaways where the conclusions may be concealed in the premises. The severity of the test will depend on how thoroughly the search Is made and how strict a criterion of obviousness Is applied. Since I know of no way at the present time to quantify either of these two dimensions of the test, we must still depend (as we do In evaluating the merit of scientific discoveries) on informal judgement.

From close familiarity with the AM and BACON programs, I am satisfied that these two programs pass any reasonable tests of this kind. Let me, then, comment on the structure of the programs - - on the sources of their powers of discovery. For the sake of those of you who are not acquainted with AM or BACON, I will first state briefly what each program does. As already noted, a fuller description of AM, by Doug Lenat, will be found In the Proceedings of the Fifth IJCAI (1977), and of BACON, by Pat Langley, in the Proceedings of this conference.

Lenat's AliA Program AM Is a system that discovers new concepts and that conjectures new relations among them. Its Input consists of an Initial stock of concepts (in one application, the basic notions of set theory), goals and cri teria (the goal of discovering new concepts and possible relations among concepts, and criteria for evaluating the worth or interest of concepts), and heuristics for searching for new concepts. Among the criteria for judging if a concept is interesting is how closely it is related to other Interesting concepts, and whether examples of it can be constructed -- not too easily, but with not too much difficulty. The search heur istics include the acivlce to construct examples, to pay particular attention to borderline examples, to particularize when examples are found too easily, to generalize when they are hard to find. This is the kind of initial information available to AM -- initial concepts, goals and criteria, and search heuristics.

The control structure of AM guides it in a best-first search; the criteria of concept worth determine which of the concepts already attained should be the starting point for the next quantum of search. On its most celebrated run, starting with the concepts of set theory, A~ discovered -- among other things -- the integers, the arithmetic operations of addition, subtraction, multiplication and division, the concept of prime number, and, as I mentioned earlier, the prime number representation theorem. When it began concerning itself with numbers possessing maximal (Instead of minimal) numbers of prime factors, Lenat thought it had entered on truly new ground, only to find that this territory had earlier been explored by the self-taught Indian mathematician, Srinivasa Ramanujan. Therefore, AM must be evaluated as a rediscoverer, rather than a discoverer of new mathematical truths.

Langley's ~ Program BACON is a program that Induces general laws from empirical data. Given sets of observations on two or more variables, BACON searches for functional relations among the variables. Again, it carries out a form of best-first search, in which a criterion of "simple things before complex" guides what to try next.

BACON's search is highly selective; it does not try all possibilities. It arranges the observations monotonically according to the values of one of the variables. Then it determines whether the values of some other variables follow the same (or the inverse) ordering. Picking one of these other variables, it searches for an invariant by considering the ratio (resp., product) of this variable with the original one. If the ratio (product) Is not constant, it is introduced as a new variable, and the process continues. Thus, the newly defined variables in BACON correspond to the new concepts in AM, and the process Is driven by a search for invariants.

It Is easy to see how BACON, discovering that the product of electrical current by resistance in an electrical circuit was constant, would be led to Ohm's Law. The case of Kepler's Third Law requires BACON to generate, successively, ratios of powers of the radii of the planets orbits to powers Rf t~eir periods of revolution, arrivins at the invariant, D" /P , after a search of a small number of possibilities.

I have mentioned only a few of the salient features of BACON. The system has at least crude means for ignoring noise as data, and a number of other interesting features, but I will leave their fuller description to the program's author. What is interesting for our purposes is that a program, equipped and organized as I have described, detects regularities in data sufficiently perceptively to rediscover important scientific laws.

AM and BACON use similar schemes of memory organization. The ability to apply the 'Same basic processes to given information and to newly generated concepts or variables, respectively, hence to operate recursively, Is guaranteed by using a homogeneous format for the storage of all data. Though the detail$ of the data structures are different for the two programs, both use schemas -- structures of property lists -- to describe the objects with which they deal or which they generate. The main element of rigidity in their memory organizations Is that the specific properties that may occur In these schemes -- the "slots· -- are specified In advance and known to the programs.

Discovery Mechanisms The theory of discovery that emerges from an examination of how these programs work contains little that should surprise us - - unless we have been seduced by the often-repeated myth that discovery processes, being "creative," somehow stand apart from the other actions of the human mind. In AM and BACON we see discoveries being produced by precisely the same kinds of symbolic processes that account for the efficacy of other AI problem-solvina programs: theorem provers, chess players, puzzle solvers, diagnosis systems. A space of possible concepts and relations (AM), or of possible invariants (BACON) Is searched in a highly selective, best-f irst manner. The search mainly works forward inductively from the alven concepts or date.

The discovery programs are dlstln,ulshed from most other problem-solving systems in the vagueness" of the tasks presented to them and of the heuristic criteria that guide the search and account for its selectivity. Because the goals are very general (·find an interesting concept or relations, "find an invariant·), the use of means-ends analysis to work backward from a desired result Is not very common. By and large, the programs work forward inductively from the givens of the problem and from the new concepts and variables generated from these givens.

Both progr ems work at 1 very concrete level. AM makes a major use of ewamples, which It is capable of generating, in searching for new concepts. BACON works with numerical data. If we observed human scientists working In the manner of these programs, we would regard them as very pragmatic. We are reminded of Fareday·s notebooks, In which he recorded, day after day the ewperiments that were suggested to a curious mind by the findings of the previous day·s experiment. Or, we think of Mendeleev arranging end reerranaina his lists of the elements until their periodic structure begins to emerge from his worksheets.

Both pro1rams discover, they do not prove. Their task is to find regularity and pattern In nature, not to demonstrate the necessity of that pattern. Althouah their heuristics appear very aeneral and weak -- they do not rely at all on semantic Information about the task domain that is being explored -- they accomplish the search tasks with a remarkably small amount of trial and error. In the best tradition of heuristic schemes, they operate without eny gu~rantees that they will succeed, but they do succeed In fmdlng many Interesting results. We would not even know how to define completeness for proarams alven these kinds of ill-defined tasks.

Because the tasks addresssed by these systems are poorly defined, we do not have good measures of how powerful they are. Of course, we can make our personal evaluations of the quality of their discoveries -- of how Impressed we are that AM finds the prime number factorization theorem, or thet BACON readily lnduc:es Ohm's law from the dele. But we do not have the precision of comparison with human performance that a chess program gives us, or a program for medical diagnosis. The difficulty of evaluating them Is compounded by the absence of a yardstick for measurlna the knowledge with which they are endowed at the outset, or that Is embedded in the program structures. We do not know whether BACON had the same starting point as Ohm, or whether one of them was faced with an essent ially simpler problem of induction than the other. Of course the same uncertainties surround all of our attempts to evaluate human discovery also. AM and BACON pose no new methodological puzzles In this respect.

How does the behavior of these programs compare with the behavior of the human scientists who have labored In the vineyards of artificial intelligence during the past 25 years? Do AM and BACON provide a true, if rough and approximate, description of that discovery effort? And what of the future of AI? Can these discovery programs help us In either prediction or strategy? Let me turn first to the history.

3. The Discovery Process In AI

Ar.tificial intelligence has sometimes been criticized as being atheoretical, and consequently as having no solid substance. Of course, the premise might be true but the consequent false, unless we believe that all truth takes the form of rigorously proved theorems. Artificial intelligence has certainly been short of theorems, and in a field as densely populated with mathematicians and former mathematicians as is computer science, its nakedness in this respect has not gone unnoticed.

It may be objected that I am neglecting the A* algori thm, or the various interesting properties of Alpha-Beta searchbor even the theorems that Kadane and I have proved a out optimal evaluation functions for best-first all-or-none search (Simon & l<adance, 1975). But these Isolated examples, even if we add to them all the others known to us, do not constitute a theory of artificial intelligence. At best, they provide us with some islands of theory, separated by wide expanses of an atheoretlcal ocean. Moreoever, the heuristics of best-f irst search implied by these examples were known empir ically and used in running AI programs for many years before 1 the mathematics was developed (Newell & Simon, 1956). .

AI n Empirical !ngyjry I am afraid that we must resian ourselves to the fact (or celebrate it, depending on our taste In science) that artificial intelligence has not been a branch of mathematics, but rather a field of inductive, empi rical inquiry. The main strategy of investigation has been to propose tasks requiring intelligence for their performance, to write programs for handling those tasks, and to test the efficacy and efficiency of the proarams by giving them a sample of tasks drawn from the domain in question. Nearly everything we have learned about artificial Intelligence over the past 25 years (and much of what we have learned about human Intelligence as well), has been found by following this experimental strateay. And the body of knowledge that exists In AI today Is better described as a store of experimental data and Inferences drawn from them than as a collection of mathematical truths.

1 l'.M 1.21.1s. I.bl.2a . Mlshlnt. In I 958, alrHCiy lncorpo,.ted beat-firat heurlatic Hlrch, while the Alpha-S.te heurletic It to be found In che11 P'OI'''"' II "'ly II 11151.

But the process I am describing corresponds closely to the kind of process that is carried out by AM and BACON. We have seen that both programs are inductive and experimental -- even if the product of the former's efforts are matliematlcal constructs and conjectures, and of the latter's, postulated functional relations among numer ical variables. Neither AM nor BACON proves anything. If they produce conviction, it is the conviction of the empirical scientist, relying on some postulate of the uniformity of nature, rather than the conviction of the mathematician, relying on the certainty of the laws of logic.

Inferring Principles From Programs The problem-solving tasks that AI research has addressed during the past 25 years, like the tasks addressed by AM and BACON, seem largely fortuitous -- targets of opportunity: theorem- proving in logic and group theory, the Eights Puzzle and Missionaries & Cannibals, chess, Euclidean geometry, medical diagnosis, mass spectrogram analysis, speech recognit ion, parsing natural language, to ment ion a few. An assiduous historian could no doubt track down the reasons why each of these domains was attempted, but those reasons would not add up to a grand strategy for artificial intelligence. Probably the choice was neither much more nor much less considered than the choice of sweet peas and fruit flies as favored organisms for genetic research.

The true comparison is between these tasks, on the one hand, and the examples generated by AM or the data sets of BACON, on the other. The central inductive problem for AI has been to generalize from the performance of programs dedicated to individual .tasks some principles (empirical principles, not necessarily theorems) about the mechanslms required for Intelligent problem-solving behavior. How successfully this problem has· been solved can be judged by assessing how far new AI programs make use of th~ heuristics and structural principles of the programs already in existence, and by examining the extent to which AI textbooks are organized in terms of general principles.

On both scores there Is evidence of steady progress In AI. In the first decade or two, one can find a number of reinventions of general principles by Investigators who were exploring different task domains (or even, occasionally, the same task domain). For example, best-first search apparently appeared intially, as already noted, as a component of one version of The Logic Theory Machine, disappeared in early versions of GPS, which tended to be oriented towared depth-first search, and reappeared In the MATER chess combinations program (Baylor & Simon, 1966). As another example, schemas appear in programs as early as 1956, but were subsequently reinvented and rechristened "templates" or "frames" (Minsky, 1975; and Simon, 1972). During the past five or ten years, however, the main structural components of AI programs have been identified, and a reasonably consistent vocabulary adopted for referring to them.

This gradual progress toward awareness of general principles Is reflected by the textbooks In the field. Early textbooks were little more than collections of examples of more or less successful problem-solving programs. Beginning with Nilsson's book, Problem-solving Methods !.!1 Artificial Intelligence (Nilsson, 1971 ), some general threads of organization began to appear, and specific programs were not merely described, but were analyzed for their contributions to these threads. With all this progress, the contemporary books still reflect the pragmatic and empirical foundations of the field, and resemble textbooks in geology more than they resemble treatises in analytical mechanics.

Departures .from the Discovery Model There is one respect in which the history of AI research departs significantly from the trace of a computer discovery program, for in the AI world, many lines of inquiry can be pursued simultaneously -- provided that the discipline is sufficiently well populated by researchers, and that the researchers are not too much driven by fads. Hence, when we try to interpret the annals as exemplifying best-first search, we must use that term loosely. To be sure, there was a period of several years during which attempts at theorem- proving nearly dominated At research, and a more recent period when much of the Inquiry was focused on problem-solving in knowledge-rich domains. When a topic like one of these seems to be progressing rapidly, it attratts much of the field's researth effort, as would be true of a best-first search system. But other lines of investigation are never wholly dormant.

What has happened when the At research strategy has departed from the discovery model? The most instructive examples are the cases where pragmatism was sacrificed to the demand for more theory and formal development. One such case is theorem-proving, where mathematical tastes have exercised greater influence than in most other AI task domains.

From the time of Hao Wang's early and successful program for proving theorems in the propositional calculus (Wang, 1960), most theorem-proving efforts have placed great emphasis on the completeness of their programs and upon employing elegant proof methods (e.g., natural deduction and resolution) from symbolic logic. Since completeness Is most easily proved for breadth-first programs that do not use pragmatically constructed selective heuristics, the mainstream of research eschewed best-first search and heuristics that lacked guarantees of completeness.

When heuristics could be used that did not threaten completeness (e.g., set of support), they were adopted readily, but heuristics po!.sessing this guarantee were not in sufficiently long supply to prevent the exponential explosion of searc.h trees. The net result has been a general disillusionment with the progress of theorem-proving research, and a diversion of effort to other task domains within AI. Some exceptions can be found, of course. For example, in the impressive work of Bledsoe and his associates, we see exhibited a much more pragmatic attitude towards heuristics than has been char acterlstic of theorem-proving research in general (Bledsoe, 1977).

AI ~ ! Residual Domain Some years ago, Allen Newell described artificial intelligence as the domain of weak methods, a description that still seems to hold (Newell, 1969). This Is not because anyone prefers weak methods to stronc. No one would solve a problem by heuristic search if he thought that the simplex algorithm of linear programming would do the job. But strong methods apply only in domains that have sufficiently rich and smooth structure to support them. The simplex method works only in a problem space that is convex, bounded by linear Inequalities, and with a linear criterion function to be maximized. The method exploits the mathematical structure of the spac.e to home in on solutions In a relatively direct and straightforward fashion.

AM, and to a lesser extent BACON, are designed to work in spaces that have little regular structure, or which have structure that is intiailly unknown to the program. They use the weak methods of heuristic search for the same reason that artificial intelligence has used those methods -- because not enough was known, in advance, of the shape of the problem space for stronger methods to be used.

Similarly, attempts to derive measures of computational complexity for typical AI domains have not yet yielded much of a mathematical harvest. Proofs about the dependence of amount of computation, in the worst or average cases, upon problem size depend on knowledge of structural features of .the problem domain, and where such structural features are unknown or absent it becomes difficult to obtain strong mathematical results.

Necessity should not be redefined as a virtue. Vet, it makes some sense to define artificial intelligence as a residual domain -- the domain in which it has not yet been possible to substitute powerful special -purpose techniques for weak methods. At any time that such techniques are discovered for a particular subset of problems, those problems are removed from the jurisdiction of AI to that of operations research or numerical analysis. But human Intelligence, applied, for Instance to the discovery of new knowledge, is not limited to working in orderly domains that have strong structure, and it is the task of AI to show how intelligence works, and even to complement its working, In less well structured domains.

4. F'rom Past to Future

If we take AM and BACON as our models of the discovery process, then we should despair of making exact forecasts of where artificial intelligence research is likely to go in the next few years. For the discovery process illustrated by those programs is myopic, Its best-first search responding to intimations of opportunity. Consequently, targets will continue to shift, as they have shifted in the past, to those task domains that exhibit from time to time, most promise of movement.

Allocation of Effort One important difference has already been noted between a discovery process programmed for a serial digital computer and the social discovery process of the AI community. That community is a parallel, rather than a serial, machine. With the increase in manpo iller that has been attracted to the field in the past five years, the prospects are now brighter than they were earlier for maintaining sustained research activity in a number of AI domains at the same time. At the present time, for example, a more or less continuous effort of several research groups is being devoted to chess programs, to natural language understanding, to visual pattern recognition, to medical diagnosis, and to various kinds of information retrieval tasks.

The fact that a computing system has modest parallel capaci ty does not, however, Invalidate the main features of the best-first search model. The parallel capacity Is sti ll highly limited, and does not grow exponentailly (at least not for long), as it would have to in order to avoid decisions about what part of the tree to search next. The effort allocation problem for a parallel, but not exponentially growing, system Is merely a little less poignant than the problem for a strictly serial system. At any given moment, several branches that are most promising for exploration have to be chosen, instead of a single branch. Hence, with limits of both manpower and funding in AI, increased activity in some directions means decreased activity in others.

For example, research on speech recognition appears to have receded again to a relatively low level of activity with the termination of the special ARPA funding, as has AI research on robotry. 0 will have a bit more to hy about robotry research later, but will simply observe now that the current boom in industrial robotry is only tenuously connected with the main stream of AI research, and makes only limited use of AI methods.) Automatic programming has never reached the level of attention that Its potential importance and centrality to AI would seem to justify. Theorem- proving and problem-solving in general -- appear to be attracting relatively little effort currently.

Judged in terms of the contents of the Proceedings of IJCAI5 (I don't have the corresponding numbers for the cur rent conference), natural language is attracting the most attention in AI research, followed closely by vision and the representation and acquisition of knowledge. These three areas together accounted for about 601. of all the papers.

The Evaluation function From the shifts in allocation of research effort, we can draw some conclusions about the evaluat ion function that is used to guide the best-first search. But we must note carefully whose evaluation functi on it Is. To those of us who have been working in AI, It is obvious that the shifts in emphasis among speech recognition, robotry, and automatic programming (these especially, but not exclusively) have been determined to a much greater degree by the judgments of funding agencies as to what kinds of work were more likely to lead promptly to practical application, than by the judgments of the researchers as to what lines of Inquiry held the greatest promise for advancing fundamental knowledge.

In part, this vulnerability of the research agenda to genuine or imagined priorities for applications is the price that AI pays for being a "big science" field, dependent for its progress on the availabity of expensive computing .equipment. But some other big science fields -- for example, radio astronomy -- have attained considerable freedom In selecting their research goals, and we can only hope that AI can gradually acquire similar autonomy as the field becomes better established and the fundamental character of the phenomena it studies more widely understood.

If I were to contrast my own personal evaluat ion function with the function Inferred from the actual present alloca.tlon of effort, I would be Inclined to give considerably more attention to the domains of robotry

(that Is, the AI aspects of robotry) and automatic programming than these areas are now receiving. Later, I will have a few words to say about the reasons for my preferences.

Common Themes One factor that mitigates the possible damage done by the whims of funding agencies and the fads of AI research itself, is that there is a considerable overlap in the basic problems encountered, and In the basic AI mechanisms required to solve those problems In all the task domains where AI research is carried on. Best-first search, for example, is a recurring theme, regardless of whether we are concerned with theorem-proving, chess playing, or robot plannlna. Similar problems of data representation, organization, and access must be faced In almost all task domains. Many tasks call for natural language capabilities of wider or narrower extent. The context-dependence of knowledge acquired through search, and the extrapolation of knowledge from one context to another Is a recurrent theme. Because of these commonalities, progress in our understanding of any new task is likely to contribute substantially to progress for other, temporarily dormant tasks.

But these benefits of commonality will be realized only If we pay explicit attention to the transfer problem. The existence of multiple parallel research efforts In different tasks domains increases the danger that the same principles and mechanisms will be reinvented, perhaps more than once, by specialized investigators who are unaware of work going on outside their own narrow areas. As the AI research field grows and more Investigators enter it, specialization will undoubtedly grow also (it has already), and the dangers of duplication will increase correspondingly.

Perhaps the most Important preventive step against reinventing wheels is to define research goals not simply in terms of constructing programs that will perform specific tasks well, but In terms of using programs as examples and test beds for generating and illuminating general principles. Computer science has its roots In both scientific and engineering traditions. For the engineer -- at least the nonacademic engineer -- the device is the thing; the proof of his pudding is in how well the system he has designed works. For the computer scientist, the device (the program) is not an end in itself, but a means for testing whether particular methods and principles, Incorporated In the device, perform the functions for which they are Intended. Journal referees and reviewers of funding proposals can contribute much to the development of AI by Insisting on these broader goal specifications for AI research projects.

There would also appear to be room in AI research for more generalists and theorists who would devote their attention to extracting general principles by comparative analysis of programs in different task domains. Of course such activity goes on at the present time, but perhaps It would be enc<'uraged further If we did not restrict the term "theory" to formal, mathemat ical developments.

It might appear that I have fallen into a contradiction. Using AM and BACON as my models of discovery programs, 1 pointed out the futility of trying to predict the course of discovery. Now, only a few paragraphs later, I am expressina my views about the allocation of effort. There is, in fact, no contradiction. In best-first search, choosing an evaluation function and using it to guide the allocation of effort is unavoidable. This does not mean that one can predict where the search will lead; but a well-choosen evaluation function can indicate the most productive points at which it can start. Let me offer a few illustrations.

Research Qn Robots One criterion of a promising task domain is that successful AI programs in the domain will rely on important components of intelligence that have not been much explored in other research. Robotry is a promising domain, because it takes us away from planning actions in simple worlds of the Imagination -- where the consequences of our actions can be deduced precisely -­ into planning actions In complex real worlds, where we must be prepared to readjust our estimates of the state of the world repeatedly as our actions fall short of or beside our intentions.

Methods for matching the predicted to the actual state of the world, and for correcting the former to reflect the littler, are fundamental to the success of systems that can survive in complex environments and particularly in environments where there is much uncertainty.

When I refer to robotry research, I have in mind something rather different from the development of Industrial robots that is now burgeoning in a number of countries. Most industrial robots are being designed to carry out fairly restricted ranges of tasks in factory environments that are carefully tailored to the robots. Moreover, AI techniques have not played a prominent role in these developments, most of which come out of the tradition of engineering control theory.

In this application, the residual status of AI methods is again apparent. If an environment can be sufficiently smoothed and simplified, then the methods of servomechanism and control theory may provide the best means for designing flexible devices to operate in that environment. AI methods are likely to have a comparative advantage in rough and complex environments that have to be dealt with in their raw, natural form. For this reason, research on vehicles capable of locomotlng autonomously on remote planets Is probably more relevant to basic issues in artificial Intelligence than is research on industrial robots that are to operate in factory environments. The former kinds of systems will have to be flexibly intelligent to a much higher degree than the latter.

However, I do not want to overstate the case. As the development of industrial robots goes forward, there is a need for strong capabilities in visual pattern recognition, a domain in which artificial intelligence concepts are likely to play a role of increasing prominence. The point of my example is that we don't simply want to seize on robotry as a task domain, but want to ask what aspects of robotry call especially for AI approaches, and what light is likely to be cast on general AI concerns by research focused on those aspects.

Automatic Programming A second domain I singled out as promising for Af research today is automatic programming. Here again, the general value of the research for advancing our basic understanding of artificial Intelligence depends on how the problem Is defined. I have especially In mind systems that would take ill-structured and incomplete descriptions of a desired program (of the sort we would give as instructions to a human programmer), and transfer them into executable code. Automatic programming, so defined, is an excellent domain in which to experiment with the automatic design of problem representations -- a problem we must address if we are to extend AI further into ill-structured domains.

An additional reason why automatic programming tasks deserve high priority on the research agenda is that they offer excellent opportunities for work on natural language and knowledge representation. Research in the latter two fields has sometimes suffered from vagueness in the specification of the task. To study natural language effectively we must study particular kinds of situations in which information and meanings have to be communicated for a definite purpose. The automatic programming task defines that purpose (as does also the closely related task of understanding problem instructions written in natural language). By the same token, we are apt to learn most effectively about the problems of knowledge representation . in the context of a specific task domain like automatic programming.

If we accept necessity as the mother of invention, we must remember that another parent is needed too. Automatic programming deserves a high rating for Its research potential only If there is reason to believe It can be done -- that our basic knowledge has reached the point where it is reasonable to talk about automat ic design of task representation. I would argue that both the progress -- modest though it be -- that has already been made in automatic programming, and the progress in the design of representations for other domains provide favorable indications that we are ready for the next step (Hayes & Simon, 1974).

Local and Q!g_l:>_M Knowledge A problem that has plagued heuristic search systems from the beginning is that information gathered at one node In a search through a problem space is not generally usable by the system to guide its search in other parts of the space. The same information may have to be generated again and again at different nodes.

Partly, this is a problem of information organization, solvable through such devices as blackboard schemes (lesser & Erman, 1977). In such schemes, information Is not stored in association with the nodes at which it is generated, but is placed in a common space where it becomes permanently available to all parts of the program, and at all times during the exploration of the problem space.

But there is a deeper problem with making information ~ore broadly available: the information may be true only tn a local context. Then the boundaries of this context must be determined and associated with the information before it can be exported safely. There is still not much theory (or experience) in the AI literature as to how this is to be done, but some progress has been made toward solving the problem In connection with research on speech recognition programs and chess programs, both of which are promising environments in which to pursue this Issue (Lesser & Erman, 1977; Perdue & Berliner, 1977).

Leeroing Systems In AI a great deal more progress hts been made In constructing performance programs than In designing programs that learn. In the early history of art ificial intelligence, the topic of self-organizing systems was pursued vigorously but, as it turned out, not particularly successfully. As the best-first search progressed, the nodes associated with this topic received low evaluations, and were gradually abandoned.

Yet the topic of learning In AI Is not at all dead; rather It has been redefined. In early efforts, great importance was attached to starting systems off at or near ground lovel. The guarantee that they were learning was that they started off knowing almot nothing. Today, we characterize learning In a somewhat different way; we look for adaptive change, and we look for that change to be recursive and cumulative.

In the broadest sense, any program Is a learning program that gradully changes over time so that on each new encounter with a particular kind of task it behaves In a more appropriate way. In neither human beings nor computers should we expect to find just a very limited number of processes called "learning processes," for there generally are a multitude of ways In which a complex system can modify Itself adaptively.

Learning will generally be incremental. That is, each new step In adaptaatlon will Itself improve the capacity for further adaptation. A problem-solving system becomes a learning system whenever it is designed so that problem solutions can be stored and used to contribute to subsequent problem-solving. Clearly, discovery programs like AM and BACON are learning programs, since their explicit task Is to produce novel outputs and to use those outputs recursively.

With this broader definition of learning, a whole spectrum of AI systems qualify as learning systems. Learning can connote all degrees of pasivity or activity of the learner. Thus, at one extreme, we have interactive systems aimed at makins it easier for the programmer to add new knowledge to an information structure, where the program Itself Is a wholly passive learner. At the other extreme, we have adaptive production systems that are able to extract information from their experiences, and use the information to .Improve themselves even without explicit instruction from outside. Most systems that learn from experience are aided, of course, if the experience Is organized for them In a favorable way -- In a succession of carefully graded lessOtlS. It is the skill of a good teacher to present experience in this way.

One mlaht ask whether it Is time to revive learning " a major explicit goal of AI research. Since learning pervades almost all aspects of intelligent performance, the right search strategy is probably to lncorpooate lear ning goals In our performance systems. That se .. ms to be a quite naiural thing to do in building systems for visual pattern r~acognltion, for example, for automatic programmlna, or for understanding natural languaae Instructions.

But there are apprentices In the wor ld as well as journeyman! and presumably the apprentice's first concern In his learnlna rather that his performance. So perhaps there Is room, on the tree of AI research, for an ·ctlve branch that works with tasks In which learnlna and adaptation are the central concerns. Considering the recent r apid progress that has been made In constructlna adaptive production systems, good progress can be ant icipated along that branch, and I would assign It a r ather favorable evaluation. But the fact that some Investigators specialize In learning processes should not deter the rest of us from experimenting with learnina components In our performance systems.

5. Conclusion

In this paper I have reviewed the AI community as if it were a medium-size slightly parallel processor searching its way in inductive, best-first fashion through the problem space of Intelligent action. I have compared it with some of the existing AI programs that best characterize the discovery process. The comparison does not yield any great surprises, but perhaps provides some reassurance.

As a typical example of a discovery program, the AI community uses weak methods uder the guidance of a somewhat Imprecise evaluation function and vague ultimate goals. It tries to discover the mechanisms that enable a system like the human mind to behave purposefully, adaptively, and sometimes even effectively over a wide range of diff icult and ill-structured tasks.

The search is highly pragmatic, steered and redirected by concrete empirical evidence culled from experiments with programs operating in an accidentally determined collection of task environments. The output of the research Is mostly encapsulated in heuristics, not yet formalized in coherent theories of broad scope. All Is confusion and mild chaos, as it should be at an exciting front ier of fundamental scientific inquiry. Although only a quarter of a century old, the search has already yielded a solid body of empirical knowledge about the nature of lntelltaence and the means of capturing It In programs.

6. References

Baylor, G.W., & Simon, H.A. A chess mating combinations program. AFIPS Conference Proceedings, 1966 Sru.i.n& Joint Computer Conference, Boston, April 26-28, 1966, ~ 431-447. Washington, DC: Spartan Books.

Bledsoe, W.W. Non-resolution theorem proving. Artificial Intelligence, 1977, 2. (1 ), 1-35.

Hayes, J.R., & Simon, H.A. Understanding written problem Instructions. In L.W. Gregg (Ed.), Knowledge and cognition. Potomac, MD: Lawrence Erlbaum Associates, 1974.

Langley, P. Rediscovering physics with BACON.3. Proceedings of the 6th International Joint Conference on Artificial Intelligence, forthcoming.

Lenat, D.B. The ubiwuity of discovery. Proceedings Qf the 5th International Joint Conference on Artificial lnfelliSence, 1977, L 1093-1105. -

Lesser, V.R., & Erman, L.D. A retrospective view of the HEARSAY-II architecture. Proceedings of the 5th International Joint Conference on Artificial Intelligence, 1977, ~ 790-800.

Minsky, M. A framework for representing knowledge. In P.H. Winston (Ed.), The psychology of computer vision. NY: McGraw-Hill, 1975.

Newell, A. Heuristic programming: Ill-structured problems. In J. Aronofsky (Ed.), Progress in operations research, Vol. Ill. NY: Wiley, 1969.

Newell, A., & Simon, H.A. Computer science as empirical inquiry: Symbols and search. Communications of the ACM. 1976, 1.2, 111-126.

Newell, A., & Simon, H.A. The logic theory machine. IRE Transactions on Information Theory, Vol. IT -2, No. 3, Sept. 1956.

Ni :sson, N.J. Problem-solving methods in artificial intelligence. NY: McGraw-Hill, 1971.

Simon, H.A. Artificial intelligence systems that understand. Proceedings of the 5th International Joint Conference on Artificial Intelligence, 1977, ~ 1059-1073.

Simon, H.A. The heuristic compiler. In H.A. Simon & L. Siklossy (Ed.), Representation and meaning: Experiments with irlformatlon processing systems. Englewood Cliffs, NJ: PrMtice-Hall, 1972.

Simon, H.A., & Kadane, J.B. Optimal problem-solving search A! :-o~-none solutions. Artificial Intelligence, 1975, §.. ~35-248.

Simon, 1-l.A., & l'~~wall, A. 1-'..al.iristic problem solving: The next adv11~:e iil c;:>erations research. Operations Research, 1958, §, ~-10.

Wang, H. Toward mechanical mathematics. IBM Journal of Research and envelopment, January 1960, 2-22.