We seek here to determine the exact quantitative dependence of performance of best-first search (i.e., A* algorithm) on the amount of error in the heuristic function's estimates of distance to the goal. Comparative performance measurements for three families of heuristics for the 8-puzzle suggest general conjectures that may also hold for more complex best-first search systems. As an example, the conjectures are applied to the coding pnase of the PSI program synthesis system. A new worst case cost analysis of uniform trees reveals an exceedingly simple general formula relating cost to relative error. The analytic model is realistic enough to permit reasonably accurate performance predictions for an 8-puzzle heuristic. The analytic results also sharpen the distinction between "Knowledge itself" and the "Knowledge engine itself". One has the sense that the men who conceived these high buildings [Gothic cathedrals] were intoxicated by their newfound command of the force in the stone. How else could they have proposed to build vaults of 125 feet and 150 feet at a time when they could not calculate any of the stresses?

Reprinted as Chapter 3 (pp.250-271) of Webber & Nilsson, Readings in Artificial IntelligenceElcock, E. W. and Michie, D. (Eds.), Machine Intelligence 8, pp. 94-€“138. Ellis Horwood.

The Platonic assumption that the world is made up entirely of objects with flat surfaces obviously does not hold; and yet, as with so many other simplifications of reality for the sake of tractability, it has been immensely productive in establishing a paradigm for scene analysis. There is a coherent evolving body of research based on the notion that a polyhedral world is the simplest we can consider without eliminating any of the essential aspects of scene analysis, namely, the picture-taking process, models, lighting, support, occlusion, and so on. The thesis is that once we achieve ways of dealing intelligently with those aspects for a simple, but nonetheless real, world we could then consider the fuzzy world of teddy bears (Michie, 1974) and the like. This should not be taken as suggesting that each of those aspects presents simply a separate, independent subproblem to be solved. The most important question to be faced was how to write programs that coordinate the use of these separate, but interrelated, knowledge systems to achieve sensible picture interpretations. Roberts (Roberts, 1965) was the first to give an answer to this question. We shall examine his answer in some detail, because he exposed in it the issues that became themes of the first decade of scene analysis.

The Open Mind Common Sense project is an attempt to construct a database of commonsense knowledge through the collaboration of a distributed community of thousands of non-expert netizens. We give an overview of the project, describe our knowledge acquisition and representation strategy of using natural language rather than formal logic, and demonstrate this strategy with a search engine application that employs simple commonsense reasoning to reformulate problem queries into more effective solution queries.

Earlier work by Newell, Simon, Shaw, and Gelernter in the middle and late 1950s emphasized the heuristic approach, but the weight soon shifted to various syntactic methods culminating in a large effort on resolution type systems in the last half of the 1960s. It was about 1970 when considerable interest was revived in heuristic methods and the use of human supplied, domain dependent, knowledge. It is not my intention here to slight the great names in automatic theorem proving, and their contributions to all we do, but rather to show another side of it. For recent books on automatic theorem proving see Chang and Lee [19], Loveland [44], and Hayes [31]. Also see Nilsson's recent review article [61]. The word "resolution" has come to be associated with general purpose types of theorem provers which use very little domain dependent information and few if any special heuristics besides those of a syntactic nature. It has also connoted the use of clauses and refutation proofs. There was much hope in the late 60's that such systems, especially with various exciting improvements, such as set of support, model elimination, etc., would be powerful provers. But by the early 70's there was emerging a belief that resolution type systems could never really "hack" it, could not prove really hard mathematical theorems, without some extensive changes in philosophy.

Many of the recent expert rule-based systems [Dendral, Mycin, AM, Pecos] have architectures that differ significantly from the simple domainindependent architectures of "pure" production systems. The purpose of this paper is to explore, somewhat more systematically than has been done before, the various ways in which the simplicity constraints can be relaxed, and the benefits of doing so. The most significant benefits arise from three sources: (i) the grain size of a typical rule can be increased until it captures a unit of advice which is meaningful in that system's task domain, (ii) the interpreter can become accessible to the rules and thus become dynamically modifiable, and (iii) meaningful permanent Knowledge can be stored in data memories, not just within productions. Although there are costs associated with relaxing the simplicity constraints, for many task domains the benefits outweigh the costs.

Further progress in the application of computers to many practical fields seems to depend heavily on the success in implementing learning and inductive processes within machines. For example, to develop a consultation system for medical or plant disease diagnosis, prognosis and decision making in general, it is very desirable, perhaps even necessary, to be able to'teach' the system through examples of correct and/or incorrect decisions, rather than by precisely describing the decision process in its full generality and then transforming this description into a computer program. A similar situation exists in computer chess. The development of computer programs playing at the master level (especially the end games) seems to be a formidable task if the programs are not eventually able to learn and improve on their decision making rules through the specific examples of games, rather than by being explicitly told all the rules. Due to easy access to human knowledge about chess and the relative simplicity of testing the results, chess is one of the most attractive testing domains for inductive inference programs.

To use language one must be able to make inferences about the information which language conveys. This is apparent in many ways. For one thing, many of the processes which we typically consider "linguistic" require inference making. For example, structural disambiguation: (1) Waiter, I would like spaghetti with meat sauce and wine. You would not expect to be served a bowl of spaghetti floating in meat sauce and wine. That is, you would expect the meal represented by structure (2) rather than that represented by (3).

Machine intelligence problems are sometimes defined as those problems which (i) computers can't yet do, and (ii) humans can. We shall further consider how much "knowledge" about a finite mathematical function can, on certain assumptions, be credited to a computer program. Although our approach is quite general, we are really only interested in programs which evaluate "semihard" functions, believing that the evaluation of such functions constitutes the defining aspiration of machine intelligence work. If a function is less hard than "semihard," then we can evaluate it by pure algorithm (trading space for time) or by pure lookup (making the opposite trade), with no need to talk of knowledge, advice, machine intelligence, or any of those things. We call such problems "standard." If however the function is "semihard," then we will be driven to construct some form of artful compromise between the two representations: without such a compromise the function will not be evaluable within practical resource limits. If the function is harder than "semihard," i.e. is actually "hard," then no amount of compromise can ever make feasible its evaluation by any terrestrial device.

How can we get a computer to understand natural language? Our view of the problem has progressed over the years to a point where an answer to that question today would look quite different from one given ten or even five years ago. Originally, researchers felt that the most relevant issue was syntax. Later, most people agreed that semantics was the most relevant field of study (although few would have agreed on what semantics was). Five years ago, or so, our research was concentrated on finding an adequate meaning representation for sentences.