John Wiley and Sons, Inc. Robinson, J.A. (1965) "A Machine Oriented Logic Based on the Resolution Principle".

A computer program has been written that successfully discovers syntheses for complex organic chemical moleculeB. The definition of the search space and strategies for heuristic search are described in this paper. It is not growing like a tree... ...In small proportions we just beauties see; - Ben Jonson. Introduction The design of application of artificial intelligence to a scientific task such as Organic Chemical Synthesis was the topic of a Doctoral Thesis completed in the summer of 197I. Chemical synthesis in practice involves i) the choice of molecule to be synthesized; ii) the formulation and specification of a plan for synthesis (involving a valid reaction pathway leading from commercial or readily available compounds to the target compounds with consideration of feasibility regarding the purposes of synthesis); iii) the selection of specific individual steps of reaction and their temporal ordering for execution; iv) the experimental execution of the synthesis and v) the redesign of syntheses, if necessary, depending upon the experimental results. In contrast to the physical synthesis of the molecule, the activity in ii) above can be termed the'formal synthesis'. This development of the specification of syntheses involves no laboratory technique and is carried out mainly on paper and in the minds of chemists (and now within a computer's memory!). Importance and Difficulty of Chemical Synthesis The importance of chemical synthesis is undeniable and there is emphatic testimony to the high regard held by scientists for synthesis chemists.

At the present stage of research in artificial intelligence , machines are stil l remote from achieving a level of intelligence comparable in complexity to human thought. As computer applications become more sophisticated, however, and thus more influential in human affairs , it becomes increasingly important to understand both the capabilities and limitations of machine Intelligence and its potential impact on society. To this end, the artificial intelligence field was ex­amined in a systematic manner. The study was divided into two parts : (1) Delineation of areas of artificial intelligence, and postulatio " of hypothetical prod­ucts resulting from progress in the field , and (2) A judgmental portion, which involved appli­cations and implications of the products to society . For the latter purpose, a Delphi study was conducted among experts in the artificial intelligence field to solicit their opinion concerning prototype and com­mercial dates for the products, and the possibility and desirability of their applications and implications .In IJCAI-73: THIRD INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 20-23 August 1973, Stanford University Stanford, California.

This framework is in large part due to various res trictions imposed upon the heuristic that guides the search and the resulting effect on the search algorithm itself. In order to discuss some of these restrictions it is necessary to introduce the following notation. For a node n of a tree or graph, the following functions are defined as part of the problem.

Unfortunately, by using such heuristics, it is not possible to solve any reasonably complex set of problems in a reasonably complex domain. Regardless of how good such heuristics are at directing search, attempts to traverse a complex problem space can be caught in a combinatorial quagmire. This paper presents an approach to augmenting the power of the heuristic search process. The essence of this approach is to utilize a means for discriminating between important information and details in the problem space. By planning in a hierarchy of abstraction spaces in which successive levels of detail are introduced, significant increases in problem-solving power have been achieved. Section II sketches the hierarchical planning approach and gives motivation for its use. Sections III and IV describe the definition and use of abstraction spaces by ABSTRIPS (Abstraction-Based STRIPS), a modification of the STRIPS problem-solving system that incorporates this approach. Section V describes the performance of the system.

Additive AND/OR graphs are defined as AND/ /ORgraphs without circuits, which can be considered as folded AND/OR trees; i.e. the cost of a common subproblem is added to the cost as many times as the subproblem occurs, but it is computed only once. Additive AND/OR graphs are naturally obtained by reinterpreting the dynamic programming method in the light of the problem-reduction approach. An example of this reduction is given. A top-down and a bottom-up method are proposed for searching additive AND/OR graphs. These methods are, respectively, extensions of the "arrow" method proposed by Nilsson for searching AND/OR trees and Dijkstra's algorithm for finding the shortest path. A proof is given that the two methods find an optimal solution whenever a solution exists. 1) introduction In the literature on artificial intelligence, AND/OR trees have proved to be a good formalism for representing the problem-reduction approach to problem solving. Usually, the search is for any solution tree, but in a paper by Nilsson the problem is presented of finding the best solution tree, where arcs have a given cost, and the cost of a tree is simply the sum of the costs of the arcs. Nilsson gives there an algorithm which assumes available, for each node, an estimate of the cost of the "optimal solution tree rooted at that node.

A Universal Modular ACTOR Formalism for Artificial Intelligence Carl Hewitt Peter Bishop Richard Steiger Abstract This paper proposes a modular ACTOR architecture and definitional method for artificial intelligence that is conceptually based on a single kind of object: actors [or, if you will, virtual processors, activation frames, or streams]. The formalism makes no presuppositions about the representation of primitive data structures and control structures. Such structures can be programmed, micro-coded, or hard wired 1n a uniform modular fashion. In fact it is impossible to determine whether a given object is "really" represented as a list, a vector, a hash table, a function, or a process. The architecture will efficiently run the coming generation of PLANNERlike artificial intelligence languages including those requiring a high degree of parallelism. The efficiency is gained without loss of programming generality because it only makes certain actors more efficient; it does not change their behavioral characteristics. The architecture is general with respect to control structure and does not have or need goto, interrupt, or semaphore primitives. The formalism achieves the goals that the disallowed constructs are intended to achieve by other more structured methods. PLANNER Progress "Programs should not only work, but they should appear to work as well." PDP-1X Dogma The PLANNER project is continuing research in natural and effective means for embedding knowledge in procedures. In the course of this work we have succeeded in unifying the formalism around one fundamental concept: the ACTOR. Intuitively, an ACTOR is an active agent which plays a role on cue according to a script" we" use the ACTOR metaphor to emphasize the inseparability of control and data flow in our model. Data structures, functions, semaphores, monitors, ports, descriptions, Quillian nets, logical formulae, numbers, identifiers, demons, processes, contexts, and data bases can all be shown to be special cases of actors. All of the above are objects with certain useful modes of behavior. Our formalism shows how all of the modes of behavior can be defined in terms of one kind of behavior: sending messages to actors. An actor is always invoked uniformly in exactly the same way regardless of whether 1t behaves as a recursive function, data structure, or process.

Given an axiomatic description of its capabilities in some world, she generates her own procedures to embody these capabilities.

Dept. of Computer Science, Carnegie-Mellon University. "Many game-playing programs must search very large game trees. Use of the alpha-beta pruning algorithm instead of the simple minimax search reduces by a large factor the number of bottom positions which must be examined in the search. An analytical expression for the expected number of bottom positions examined in a game tree using alpha-beta pruning is derived, subject to the assumptions that the branching factor N and the depth D of the tree are arbitrary but fixed, and the bottom positions are a random permutation of ND unique values. A simple approximation to the growth rate of the expected number of bottom positions examined is suggested, based on a Monte Carlo simulation for large values of N and D. The behavior of the model is compared with the behavior of the alpha-beta algorithm in a chess playing program and the effects of correlation and non-unique bottom position values in real game trees are examined."

For the past several years research on robot problem-solving methods has centered on what may one day be called'simple' plans: linear sequences of actions to be performed by single robots to achieve single goals in static environments. Recent speculation and preliminary work at several research centers has suggested a variety of ways in which these traditional constraints could be relaxed. In this paper we describe some of these possible extensions, illustrating the discussion where possible with examples taken from the current Stanford Research Institute robot system.