TABLE6.3.-FORMSOFREPRESENTATION AND PROBLEM-SOLVINGUSEDIN TECHNIQUESARTIFICIALINTELLIGENCE Representations
• State space (Van de Brug and Minker, 1975) • First order predicate logic (Nilsson, 1971) • Semantic nets (Woods, 1975) • Procedural embedding of knowledge (Hewitt, 1970) • Frames (Minsky, 1975) • Production rules (Newell, 1963) Problem-solving techniques • Backtrack programming (Goulomb and Baumert, 1965) • Heuristic tree search (Pohl, 1977) • GPS means-ends analysis (Newell, 1963; Ernst and Newell, 1969) • Problem reduction (Amarel, 1968) • Theorem-proving (Nilsson, 1971) • Debugging almost correct plans (Sussman, 1975) • Procedural (Hewitt, 1970) • STRIPS (Fikes and Nilsson, 1971) • ABSTRIPS (Sacerdoti, 1974) • Cooperating knowledge sources (Erman and Lesser, 1975) • Rule-based systems, expert systems (Shortliffe, 1976) and MDS (Srinivasan, 1976). These attempts were anabitious, and while all met with serious difficulties, tile possibility remains that the problems can be overcome. An ideal frame-based programming language could make it easier to structure knowledge into larger coherent units than would otherwise be practical. The controversy between procedural and declarative philosophies of embedding knowledge has dwindled. It is now realized that each has its particular function to perform in an overall system, and that neither alone nor in combination are they an adequate underlying basis for AI theories or for sophisticated program organization. There is a growing trend toward considering tile first order predicate calculus, or minor modifications of it, as the primary mode of representing declarative knowledge in A1 systems. The reason is that this calculus has a well defined semantics and other declarative representation schemes tend to be simply different notional systems struggling to capture the same semantic notions as the predicate calculus. Interest in formal theorem-proving techniques has remained high, and perhaps has even increased slightly, despite tile slow progress in increasing the efficiency of mechanical deduction. While theoretical understanding of mechanical theorem-proving is increasing, to date there is little advancement in efficiency beyond that of a decade ago. Theoretical work on model use in theorem-proving has progressed only slightly (Reiter, 1972; Sandford, 1980), and applications methodologies are nonexistent. Theoretical work has progressed in using first-order Horn logic as a programming language (Kowalski, 1974). Horn logic is a subset of the first-order predicate calculus in which a large number of interesting problems can be expressed. A truly unexpected development is the successful implementation of a workable programming system for Horn logic in which several nontrivial programs have been written (Warren and Pereira, 1977). Much interest has developed in a rule-based type of knowledge embedding for restricted domains. These systems are commonly called expert systems, and have shown interesting and relatively strong problem-solving behavior. A variety of reasoning task domains have been implemented (Feigenbaum et al., 1971; Shortliffe, 1976), and the rulebased knowledge embedding method is robust in its performance. However, several severe defects of such systems must be addressed before realistic problem domains can be adequately handled. Defects include extremely limited domains of application, the large efforts required to construct the knowledge base, and the inability to access a basic theory and perform an a priori analysis. Work is in progress to devise systems avoiding these particular problems (Srinivasan and Sandford, 1980). There are also some relatively minor human interfacing problems with the present systems (see section 6.3). There is a general increased awareness of the importance of the role of meta-knowledge (knowledge about knowledge) in problem-solving and in planning. The important related area of reasoning relative to open world databases is just beginning to be investigated (Reiter, 1980). The general problem of representing the external world in an appropriate machine representation is a fundamental unsolved problem. While many facts are representtable in many ways, no known representation is adequate to handle even such common phenomenon as a glass of water falling to the floor and breaking. It is likely that a fundamental shift in current approaches is required to achieve adequate representations for much of "common" world knowledge. There is little indication at this time what these new approaches should be. However, certain such "common" world knowledge is at least partially tractable with current techniques as, for example, the acquisition and use of knowledge about large-scale spaces (Kuipers, 1977). Identification of critical research areas. Table 6.4 lists a set of critical research areas in the general AI fields of problem-solving, plan formation, scheduling, and plan
