Session No. 2 Applications 59 CHALLENGE TO ARTIFICIAL INTELLIGENCE: PROGRAMMING PROBLEMS TO BE SOLVED Abstract J. E. Sammet IBM Corporation Cambridge, Mass. U. S. A. This paper is in the nature of a challenge to artificial intelligence experts. It suggests that the techniques of artificial intelligence should be applied to some realistic problems which exist in the programming and data processing fields. After a brief review of the little related existing work which has been done, the characteristics of programming problems which make them suitable for the application of artificial intelligence techniques are given. Specific illustrations of problems are provided under the broad categories of data structure and organization, program structure and organization, improvements and corrections of programs, and language. Descriptors artificial intelligence applications programming heuristic techniques I. INTRODUCTION It has been over 15 years since computers were first used for anything resembling "artificial intelligence". The pioneering work of Newell, Shaw, and Simon on proving theorems in the propositional calculus is so well known as not to need discussion for the people knowledgeable in the field of artificial intelligence.

Early programs were written to demonstrate that a particular task could be accomplished and could not periorm other tasks, even if quite similar, without being extensively rewritten. Generality unnecessary for the task at hand was sacrificed to keep the programs as *Currently on leave to The University of Jerusalem **Now at Computer Science Department, Rutgers University ***Is now at NIH, Bethesda, Maryland ****With Lockheed Palo Alto Research Labs //This research was supported by the Advanced research Projects Agency of the Department of Defense under Contract No. SD-183. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the Advanced Research Projects Agency of the U.S. Government. Bmall as possible so they would fit the core limitations of our computer. The main result of this research was the development of programs which could find and stack cubes, either sorting them by size (1), or ordering them by voice command (2).

The general strategy of Meta-DENDRAL is to reason from data to plausible generalizations and then to organize the generalizations into a unified theory. Three main subprobleras are discussed: (1) explain the experimental data for each individual chemical structure, (2) generalize the results from each structure to all structures, and (3) organize the generalizations into a unified theory. The program is built upon the concepts and programmed routines already available in the Heuristic DENDRAL performance program, but goes beyond the performance program in attempting to formulate the theory which the performance program will use. I. Introduction Theory formation in science embodies many elements of creativity which make it both an interesting and challenging task for artificial intelligence research. One of the goals of the Heuristic DENDRAL project has long been the study of processes underlying theory formation.

This edge follower could easily find the outlines of white cubes on a black table, but was prone to error in less carefully controlled environments. Our studies of its inadequacies have stimulated the development of a more powerful edge follower, which overcomes most of the limitations of the old one. This program is currently the initial stage of visual processing in the Stanford hand-eye system (2). It has demonstrated an ability to track weak edges under adverse lighting conditions 2. HARDWARE The edge follower uses a standard vidicon television camera, modified to provide computer control of orientation (a pan-tilt head), focal length (a lens turret), color filter, focus, and target voltage. The lens iris is set manually. The pan-tilt head, lens turret, and focus motor *This research was supported by the Advanced research Projects Agency of the Department of Defense under Contract No. SD-183. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the Advanced Research Projects Agency of the U.S. Government.

This system accepts as input a scene represented as a line drawing. Based on a set of known object models, the program attempts to determine the identity and location of each object viewed. The most significant feature of the system is its ability to deal with imperfect input data. This ability appears essential in light of our current stock of preprocessing techniques and the variation that is possible in real world data. INTRODUCTION A hand-eye system is a problem solving system with an eye (camera) for input and a hand (manipulator) for output. Such a system must have at least 1) a set of scene analysis (perception) programs which interpret the real world in a meaningful way, 2) a set of manipulation programs which control movement of the hand in 3-space, and 3) an executive (problem solver, strategy) program which directs the perceptual and motor processes toward a desired goal.

Invited paper presented at the IEEE Systems Science and Cybernetics Conference, Miami

Research Memorandum MIP-R-92. University of Edinburgh: Department of Machine Intelligence, School of Artificial Intelligence

In R. J. O'Brien (Ed.), Report of the twenty-second annual round table meeting on linguistics and language studies. (Monograph Series on Languages and Linguistics, No. 24.) Washington, D.C.: Georgetown University Press, 35-56.

Ph.D. dissertation "Bi-directional and heuristic search in path problems" (Stanford, Computer Science, 1970) summarized in this article in Machine Intelligence 6 (1971).In the uni-directional algorithms, the search proceeds from an initial nodeforward until the goal node is encountered. Problems for which the goal nodeis explicitly known can be searched backward from the goal node. Analgorithm combining both search directions is bi-directional.This method has not seen much use because book-keeping problems werethought to outweigh the possible search reduction. The use of hashingfunctions to partition the search space provides a solution to some of theseimplementation problems. However, a more serious difficulty is involved.To realize significant savings in bi-directional search, the forward andbackward search trees must meet in the 'middle' of the space. The potentialbenefits from this technique motivates this paper's examination of thetheoretical and practical problems in using bi-directional search.

Inference systems Τ and search strategies E for T are distinguished from proof procedures β = (T,E) The completeness of procedures is studied by studying separately the completeness of inference systems and of search strategies. Completeness proofs for resolution systems are obtained by the construction of semantic trees. These systems include minimal α-restricted binary resolution, minimal α-restricted M-clash resolution and maximal pseudo-clash resolution. Certain refinements of hyper-resolution systems with equality axioms are shown to be complete and equivalent to refinements of the pararmodulation method for dealing with equality. The completeness and efficiency of search strategies for theorem-proving problems is studied in sufficient generality to include the case of search strategies for path-search problems in graphs. The notion of theorem-proving problem is defined abstractly so as to be dual to that of and" or tree. Special attention is given to resolution problems and to search strategies which generate simpler before more complex proofs. For efficiency, a proof procedure (T,E) requires an efficient search strategy E as well as an inference system T which admits both simple proofs and relatively few redundant and irrelevant derivations. The theory of efficient proof procedures outlined here is applied to proving the increased efficiency of the usual method for deleting tautologies and subsumed clauses. Counter-examples are exhibited for both the completeness and efficiency of alternative methods for deleting subsumed clauses. The efficiency of resolution procedures is improved by replacing the single operation of resolving a clash by the two operations of generating factors of clauses and of resolving a clash of factors. Several factoring methods are investigated for completeness. Of these the m-factoring method is shown to be always more efficient than the Wos-Robinson method. The University of Edinburgh