Section 4.3.2 Computerized Psychopharmacology Advisor We hope that this level of documentation will continue to be maintained in the future. We are increasingly concerned with the level of system loading. We find ourselves increasingly restricting our work sessions to the 8am-10am period, as only during this time is a moderate level of load guaranteed. III. Research Plans (August 1979 - July 1981) A. Long Range Project Goals and Plans. 1. Evaluation of the Psychopharmacology Advisor. When the performance of the Psychopharmacology Advisor approaches an optimal level in the judgment of the Principal Investigators and the Advisory Panels, a formal evaluation will be performed. Elaborate plans have been made for three types of evaluation: as a simulation of the Principal Investigator; as a national expert; and as an actual psychopharmacology advisor. In each evaluation the system will be tested on two sets of cases: one which represents the population of patients likely to be encountered in practice, thereby measuring whether HEADMED can do well what it must do most often; and one which represents unusual or exceedingly complicated cases, thereby measuring whether the program can do well in situations where usual practices may not suffice. Details of the evaluation plans are available upon request. In order to evaluate the EMYCIN formalism regarding both its inherent properties as a consulting algorithm and its appropriateness for the domain of clinical psychopharmacology, we are seeking the answers to five questions: 1) Is it beneficial to capture knowledge and control structure in the same formalism 2) Are certainty factors a useful way in which to encode uncertain information 3) Can the needed input be captured through the parameter/value system 4) Are the rules really modular 5) Is the backward chaining rule structure appropriate B. Justification and Requirements for Continued SUMEX Use. As mentioned in the preceding section, we consider the use of the EMYCIN software as integral to our project, at least for the next two years, or until we have learned enough about the domain of clinical psychopharmacology to know how to supersede the EMYCIN formalism. 201 E. A. Feigenbaum Computerized Psychopharmacology Advisor Section 4.3.2 C. Our Needs and Plans for Other Computational Resources, beyond SUMEX/AIM. Our only immediate need for other computational] resources beyond SUMEX/AIM continues to be for local, high-speed printing, preferably combined with local file storage. Our current slow-speed printing is unsuitable for listings of large rule sets or of system code. The planned acquisition of a 1200 baud printing terminal may substantially reduce the problem. Our future plans will depend greatly on the outcome of our current effort. If the EMYCIN formalism proves suitable for our domain, we may find the conversion effort sufficiently worthwhile to transport EMYCIN to our local environment. If we discover that a major redesign is needed, we will make our future computing plans in light of that design. B. Recommendations for Future Community and Resource Development. We recommend the acquisition of additional computing power for the SUMEX resource. Alternatively, consideration should be given to developing portable versions of major systems so that users can run them at their own sites ona variety of host machines. E. A. Feigenbaum 202 Section 4.4 Pilot Stanford Projects 4.4 Pilot Stanford Projects The following are descriptions of the informal pilot projects currently using the Stanford portion of the SUMEX-AIM resource pending funding, and full review and authorization. 203 E. A. Feigenbaum Quantum Chemical Investigations Section 4.4.1 4.4.1 Quantum Chemical Investiaqations Theoretical Investigations of Biomolecular Structures Or. Gilda Loew Molecular Theory Laboratory Department of Genetics Stanford University Medical Schoo] I. Summary of Research Program The focus of the molecular theory laboratory is the application and development of computer-based techniques for characterizing molecular conformation, electronic structures, molecular interactions, and chemical and biochemical reactivity. A variety of biomedical problems is under investigation using interactive computational tools that guide biochemists and pharmacologists in modeling metabolic processes and drug-receptor interactions, and in screening chemicals for carcinogenicity. A brief summary of our major research interests is given below. A. Chemical Carcinogenesis We are developing screening algorithms for twelve classes of known and suspected carcinogens under a three-year contract with the National Cancer Institute. The goal of this project is to determine mechanistically meaningful molecular parameters which correlate with known mutagenic and carcinogenic potencies, and to incorporate these parameters into heuristic screening procedures for untested compounds. A particular emphasis is on understanding alternative models for metabolic activation and ultimate interaction with BNA (references 1-6). B. Mechanisms of Opiate Action We have continued our studies to identify and calculate the molecular properties that regulate the ratio of agonism to antagonism in morphine-like, flexible, and peptide opiates. We are also studying the interaction of opiates with model anionic receptor sites such as methy! sulfate and methyl phosphate. This work is in its sixth year of support from the National Institute of Drug Abuse. The results of these studies can serve as a guide to medicinal chemists and pharmacologists interested in the design of non-addictive analgesics and their mode of action. We are currently collaborating with two such groups: one at SRI and one at UCSF Medical Center, Department of Pharmacology (Ref 7-10). C. Mixed-Function Oxygenase Metabolism The cytochrome P~450 family of enzymes plays an important role in activating and detoxifying a wide range of drugs and chemicals in mammalian organ systems. Under grants from NSF, NIH, and NCI, we are using computer programs to E. A. Feigenbaum 204 Section 4.4.1 Quantum Chemical Investigations characterize models of the biologically active states of the P-450 family, and to calculate electromagnetic properties of states leading to enzyme activation. In complementary activity, we are developing chemical reactivity criteria for different classes of substrates such as aromatic carcinogens and general anesthetics. The goal of this work is to provide programs which will predict major metabolites of different drug classes and potential carcinogens, and thus serve as a guide in estimating their toxicity. To test the predictors developed, drug toxicity and chemical mutagenicity data generated by Professor Bruce Ames at U.C. Berkeley and other laboratories are being used (references 1,4,11,12). 0. Structure, Function, and Electromagnetic Properties of Heme Proteins The procedure for the characterization of heme proteins initially requires a determination of a model for the active site. The model has to be large enough to realistically describe interactions at the active site, but not so large that it becomes economically infeasible to perform a calculation on the molecule. Once a general model is chosen, the specific geometry for the molecule must be determined. With the aid of experimental crystal structures of related compounds, we use the SUMEX-AIM facility to interactively determine an approximate model geometry. The atomic coordinates are transmitted over the ARPANET to the COC-7600 computer at LBL, where large scale molecular orbital programs are used to calculate the electronic structure and conformation, as well as the mode of binding of a number of biologically relevant ligands such as CO, 02, and CN- . The calculated electronic structures and conformations are then transmitted back to SUMEX where a set of auxiliary programs is used interactively to determine if the model yields values in agreement with experiment. These Programs calculate measurable electromagnetic properties such as quadrupole splitting observed in Mossbauer resonance spectra, g-values and hyperfine splittings in electron spin resonance spectra, and magnetic moments. This correspondence between observables and basic molecular structure enhances the usefulness of experimental data in inferring such fundamental molecular properties as the nature of metal-ligand binding and how smal] changes in conformation at the active site affect bislogical function. This work has had continual support from NSF for the past twelve years (references 12,13). E. Studies of Peptide Conformation The specific Tink between amino acid sequence and three dimensional protein structure has been difficult to establish. Thus far X-ray crystallographic studies have provided the main source of information on protein structure. Statistical analyses of frequency of occurrence of individual amino acids and short peptide sequences in different protein conformations €e.g., helical and beta-turn regions) have recently been performed by Chou and Fasman at Brandeis University. With the tabulated frequencies they have transmitted to us as a data base, we have begun a program at SUMEX to determine the feasibility of using energy-conformation studies to link amino acid sequence to conformation. A Pilot study of eight tetrapeptides (ref 14) has yielded favorable results. A related interest is conformers of peptides with specific pharmacological or biological activity. In particular, conformational studies of endogenous peptide opiates and their analogs have been made to determine likely candidate structures for interactions at the opiate receptor. Results of such studies can serve as a guide to design of clinically useful peptide opiates. 205 E. A. Feigenbaum Quantum Chemical Investigations Section 4.4.1 II. Interactions with SUMEX-AIM Resource A. Opiate Narcotics: Two groups, one at SRI and one at Beckman Corporation, are using our computer~generated results as a guide in the synthesis and testing of clinically useful alkaloid and peptide opiates. A group under Professor Horace Loh at the UCSF Pharmacology Department is using our results to study the mode of action of opiates with model receptors which are nerve-cell membrane components. B. Or. George Pack, now at the Illinois School of Medicine in Rockford, is using our programs via the TYMNET facility to study mechanisms of DNA denaturation. C. Collaboration with NASA-Ames Life Science Division: SUMEX-AIM is used to communicate with a complex computer graphics system at NASA-Ames, which in turn is coupled to programs that search for low-energy molecular conformations. This combination of facilities is a powerful tool for investigating the interactions in drug-receptor and enzyme-inhibitor complexes. Using these programs, structure-activity profiles and energetically permissible conformational subspaces may be determined for different classes of compounds. D. The National Resource for Computation in Chemistry recently became a part of the Lawrence Berkeley Laboratory computer center. We are utilizing SUMEX to exchange programs and expertise with NRCC staff. E. The community of AIM scientists is a valuable resource in itself, and we have exchanged a great deal of information about hardware, software, and chemistry with other SUMEX users and staff. We are currently pursuing a new collaboration with Jim Nourse and Dennis Smith of the CONGEN and DENDRAL projects, linking their structure-generating capabilities with our programs to determine energetically feasible conformations. Such a set of conformations is necessary to aid in the interpretation and enhance the utility of NMR spectral data. TII. Research Plans We plan to continue research in the same general areas as our current projects: systematic studies of iron-containing proteins; structure-activity studies of opiates and other drugs; drug metabolism and activation of chemical carcinogens; structure-activity studies of classes of chemical carcinogens; structure of adducts of small drugs and carcinogens to DNA components; and studies of peptide conformation. A. Long Range Goals and Plans 1. We plan to continue developing programs that will aid in screening large numbers of compounds for carcinogenic/mutagenic activity. Such programs would provide a much needed cost- and time-effective alternative to current animal testing procedures. 2. We plan to continue studies of drug metabolism by cytochrome P-450 Our study will be broadened by consideration of many classes of drugs where E. A. Feigenbaum 206 Section 4.4.1 Quantum Chemical Investigations oxidative metabolism would contribute to toxicity or significantly alter efficacy or duration of action. These programs could aid the clinician in choice of drugs, and pharmacologists and medicinal chemists in design of safer and more effective analogs. 3. We plan to continue studies of opiate narcotics to understand the basis for agonist vs. antagonist behavior, and the mode in which diverse classes of opiates can bind to analgesic receptors. 4. We plan to continue studies linking structure, spectra, and biological function of heme proteins in their role as oxygen transport and electron transfer agents. B. Justification for Continued SUMEX Use Because of its unique interactive capability, SUMEX-AIM has become essential to our research efforts. The SUMEX system is an excellent environment for creating, debugging, and distributing programs and results. In addition, the communications facilities, such as software for handling messages and distributing bulletins of general interest, are unique to SUMEX and essential to keeping in touch with colleagues in computer science as wel] as in medicinal chemistry. SUMEX will continue to play a central role in our research efforts, and we are looking at auxiliary equipment to optimize our use of the facility. We have recently enhanced our ability to communicate with SUMEX by acquiring a hard-copy terminal capable of transmitting and receiving at speeds up to 9600 baud. This unit is the first component of an intelligent preprocessing capability that we are developing. The system will be based on microcomputer technology and will provide virtually unlimited flexibility in distributing our processing load across several host computers. In the short term, however, we envision a need for a modest (20%) increase in our file space allocation. References 1. Loew, G.H., Wong, J., Phillips, J., Hjelmeland, L., Pack,G., Quantum Chemical Studies of the Metabolism of Benzo(a)pyrene, Can. Biochem. Biophys., 2, 125 (1978). 2. Loew, G.H.,» Phillips, J., Wong, J., Hjelmeland, L., Pack, G., Quantum Chemical Studies of the Metabolism of Seven Polycyclic Aromatic Hydrocarbons, Can. Biochem. Biophys., 2,113 (1978). 3. Loew, G.H., Phillips, J. and Pack, G.R., Arylnitrenium Ions : Calculation of their Formation and Electrophilic Properties in Relation to Arylamine Carcinogenesis, Can. BioChem. BioPhys. in press (1979). 4. Loew, G.H., Sudhindra, 8.S., Johnson, H., Walker, J. and Sigman, C., Correlations of Calculated Electronic Properties of Aniline Derivatives with their Mutagenic Potencies, J. Tox. and Envir. Health, in press (1979) 207 E. A. Feigenbaum Quantum Chemical Investigations Section 4.4.1 10. 11. 12. 13. 14, Loew, G.H. and Ferrell, J.E., Mechanistic Studies of Arene Oxide and Diol Epoxide Rearrangement and Hydrolysis Reactions, J. Amer. Chem. Soc., 101,1385 (1979). Loew, G.H., Sudhindra, 8.S., Ferrell, J.E., Quantum Chemical Studies of the Transformation of Polycyclic Aromatic Hydrocarbons to Candidate Ultimate Carcinogens: Correlations to Carcinogenic Potency, Chem. Biol. Inter., in press (1979). DeGraw, J.I., Lawson, J.A., Crase, J.L., Johnson, H.L., Ellis, M., Uyeno, E.T., Loew, G.H. and Berkowitz, 0.S., Analgesics I. Synthesis and Analgesic Properties of N-Sec-Alkyl and N-Tert-Alkylnormorphines, J. Med. Chem. 21, 415 (1978). Loew, G.H., Berkowitz, D.S., and Burt, S., Structure Activity Studies of Narcotic Agonists and Antagonists from Quantum Chemical Calculations, in "Quantitative Structure Activity Relationships of Analgesics, Narcotic Antagonists, and Hallucinogens,” Barnett, G., Trsic, M., and Willette, R.E., eds., NIDA Research Monograph 22,278 ( 1978). Loew, G.H and Berkowitz, D.S., Effect of C7 Substitution on Agonist- Antagonist Activity in Oripavines, in "Character and Function of Opioides," Van Ree, J.M. and Terenius, L., eds., Elsevier/North Holland Biomedical Press (1978), p. 223. Loew, G.H. and Berkowitz, D.S., Intramolecular Hydrogen Bonding and Conformational Studies of Bridged Thebaine and Oripavine Opiate Narcotic Agonists and Antagonists, in press, J. Med. Chem. (1979). Rohmer, M.M. and Loew, G.H., Electronic Structure and Properties of Model Oxy and Carboxy Ferrous Cytochrome P450, in press, Int. J. Quant. Chem., Quantum Biology Sym. VI (1979). Loew, G.H., Kirchner, R.F., Structure and Properties of Tense and Relaxed BDeoxyheme Units, Biophys. J. 22, 179 (1978). Loew, G.H., Kirchner, R.F., Binding of 02, NO, and CO to Model Active Sites in Ferrous Heme Proteins, Int. J. Quant. Chem., QBS 5, 403 (1978). Anderson, W., Burt, S.K., and Loew, G.H., Energy-Conformation Studies of Frequency of Beta-Turns in Tetrapeptide Sequences, in press, Int. J. Peptide and Protein Research (1979). E. A. Feigenbaum 208 Section 4.4.2 Ultrasonic Imaging Project 4.4.2 Ultrasonic Imaging Project Ultrasonic Imaging Project James F. Brinkley, M.D. (Depts. Computer Science, Obstetrics and Gynecology) W. D0. McCallum, M.D. (Dept. Obstetrics and Gynecology) Stanford University I. Summary of Research Program A. Technical Goals The long range goal of this project is the development of an ultrasonic imaging and display system for three-dimensional modeling of body organs. The models wil] be used for non-invasive study of anatomic structure and shape as well as for calculation of accurate organ volumes for use in clinical diagnosis. Initially, the system will be used to determine fetal volume as an indicator of fetal weight; later it might be adapted to measure left ventricular volume, or liver and kidney volume. The general method we plan to use is the reconstruction of an organ froma series of ultrasonic cross-sections taken in an arbitrary fashion. In this technique a real-time ultrasonic scanner is coupled to a three-dimensional acoustic position locating system so that the three-dimensional orientation of the scan plane is known at all times. A series of scans is recorded over the organ whose volume is being determined; at a later time a light pen is used to outline the borders of the organ for input to SUMEX. The computer then combines the position and light pen information into the reconstruction which may be displayed or used to find volume. We plan to develop this system in phases, starting with an earlier version developed at the University of Washington. During the first phase the previous system will be adapted and extended to run in the SUMEX environment. A clinical study will then be carried out to determine its effectiveness in predicting fetal weight. At the same time computer vision techniques will be used to develop the system further in the direction of increased applicability and ease of use. We thus hope to develop a limited system in order to demonstrate the feasibility of the technique, and then to gradually extend it with more complex computer Processing techniques, to the point where it becomes a useful clinical tool. B. Medical relevance This project is being developed in collaboration with the Ultrasound Division of the Department of Obstetrics at Stantord, of which WD. McCallum is the head. Fetal weight is known to be a strong indicator of fetal well-being: smal] babies generally do more poorly than larger ones. In addition, the rate of growth is an important indicator: fetuses which are "small-for-dates" tend to have higher morbidity and mortality. It is thought that these small-for-dates fetuses may be suffering from placental insufficiency, so that if the diagnosis could be 209 E. A. Feigenbaum Ultrasonic Imaging Project Section 4.4.2 made soon enough early delivery might prevent some of the complications. In addition such growth curves would aid in understanding the normal physiology of the fetus. Several attempts have been made to use ultrasound for predicting fetal weight since ultrasound is painless, noninvasive, and apparently risk-free. These techniques generally use one or two measurements such as abdominal circumference or biparietal diameter in a multiple regression against weight. We recently studied several of these methods and concluded that the most accurate were about +7-200 gmsvkg, which is not accurate enough for adequate growth curves (the fetus grows about 200 gms/week). The method we are Proposing is based on the assumption that fetal weight is directly related to volume since the density of fetal tissue is nearly constant. We are hoping that by utilizing three dimensional information more accurate volumes and hance weights can be obtained. In addition to its use in predicting fetal weight, this system could be used to determine other organ volumes such as that of the left ventricle. Left ventricular volumes are routinely obtained by means of cardiac catheterization in order to help characterize left ventricular function. Attempts to determine ventricular volume using one or two dimensional information from ultrasound has not as yet demonstrated the accuracy of angiography. Therefore, three-dimensijonal information should provide a more accurate means of non-invasively assessing the state of the left ventricle. C. Progress Summary During the four months since this project was approved we have concentrated on setting up the initial system to determine volume. The main projects have been to adapt the previous software to SUMEX, and to develop the data acquisition system necessary for obtaining the ultrasound scans and associated position information. The following tasks have been accomp! ished: 1. A three-dimensional line drawing package has been adapted to run with the OMNIGRAPH graphics system at SUMEX., 2. Most of the previously written data analysis programs have been extended and adapted to run at SUMEX. 3. Most of the data acquisition hardware has been obtained and is now ready to be integrated into a complete system. The hardware includes: a) A Toshiba real-time ultrasonic phased array scanner, in routine clinical use at the Dept. of Obstetrics. b) A Sony video tape recorder and Hitachi moniter, for use in recording the scans prior to their being outlined with the light pen. c)} A custom built acoustic position locating system for determining the position of the scan plane in space, supplied to us by W.E. Moritz at the University of Washington. d) A Datamedia computer terminal for communicating with SUMEX and controlling the procedure. E. A. Feigenbaum 219 Section 4.4.2 Ultrasonic Imaging Project e) A microprocessor-based video graphics system supplied to us by Varian Corporation. This system includes a light pen, dual floppy disks and video display memory. During the data acquisition phase of a volume determination it will be used to outline the borders of the organ being imaged from scans recorded on video tape. The outline and position information will be stored on floppy disk prior to being transferred to SUMEX for analysis. During the analysis phase the system will act as a low resolution graphics terminal for confirming that the computer has developed an accurate model of the organ. (Higher resolution graphics will be displayed on the GT-40 terminal associated with SUMEX). D. Publications Brinkley, J.F., Moritz, W.E., Baker, D.W., "Ultrasonic Three-Dimensional Imaging and Volume From a Series of Arbitrary Sector Scans", to be published in Ultrasound in Medicine and Biology. McCallum, W.0., Brinkley, J.F., "Estimation of Fetal Weight from Ultrasonic Measurements”, American Journal of Obstetrics and Gynecology, 133:2, pp.195- 200, Jan. 1979. It. Interactions with SUMEX-AIM resource A. Callaborations None at present, although we hope to work with some of the many people in this community who have expertise in image processing. B. Sharing and Interactions Mostly personal contacts with the Heuristic Programming Project and MYCIN project at Stanford. The message facilities of SUMEX have been especially useful for maintaining these contacts. C. Resource management Generally acceptable at present since we are still developing programs. However we may have problems later if we try te do the clinical study in the afternoon since we often get bumped off the system. 241 E. A. Feigenbaum Ultrasonic Imaging Project Section 4.4.2 IIT. Research Plans A. Long Range project goals and plans As mentioned in Part I we plan to implement this system in phases, each phase requiring use of more sophisticated artificial intelligence techniques. The major phases are as follows: 1) Set up prototype system and test its ability to predict fetal weight. We are currently in the process of doing this. Most of the hardware has been acquired, and most of the programs for SUMEX have been written. At present we are programming the video graphics system and starting to integrate the components into a complete system for determining fetal volume. We will then have to calibrate the system on test objects before starting the clinical study. The clinical study is expected to take about two years, during which time we will be continuing to develop the protetype system. 2) Improve volume calculations The method presently used to find volume is very cumbersome and works only for very regular objects. (For this reason we are not including the limbs in our initial fetal volume studies). The present method takes about 15 minutes of operator interaction with the computer (beyond the time taken to outline the scans with the light pen). The time required is due to the fact the the program uses a very simple algorithm to interpolate the points necessary for finding volume, and it often makes mistakes. By utilizing artificial intelligence techniques of heuristic search we hope to decrease this time. 3) Extend the technique to more irregular objects Since fetal limbs clearly contribute to volume, and since we ultimately would like to develop accurate three+dimensional models of organs, we would like to extend this technique to handle more irregular objects. For this step we plan to utilize some of the results of the computer vision groups, particularly Tom Binford's group at the Stanford Artificial Intelligence Lab, to develop an internal model of an organ which can guide the program in its attempt to fit the outline information to a three-dimensional model. The most likely representation for this model would be some modification of the generalized cones developed by Binford for computer vision. 4) Automatic border recognition In addition to the time taken to compute volume, a significant amount of time is required to outline the ultrasonic cross-sections with a Tight pen since about 20 scans are required for each volume. This fact alone may make the system too difficult to use except in a research setting. Therefore we would ultimately like the computer to do the outlining. Although ultrasonic image quality is still fairly poor, there is much work being devoted to improving the images, so ina few years we should see images which are more amenable to direct computer border recognition. In our proposed system the scans would be directly digitized and the model developed in phase 3 used to guide the program in its search for borders. E. A. Feigenbaum 212 Section 4.4.2 Ultrasonic Imaging Project B. Justification for continued use of SUMEX The goals of this project seem to be compatible with the general goals of SUMEX, ie to develop the uses of artificial intelligence in medicine. By concentrating on simple objectives at first we hope to demonstrate the utility of this method and therefore of the artificial intelligence techniques which will increasingly become a part of it. In addition, our ability te use a general purpose system will greatly speed up our ability to develop new programs and to collaborate with others. We expect the SUMEX network connections to be especially useful for interacting with other groups working .on image processing problems. C. Needs for resources For the first phase of our project the present system should be adequate unless we get bumped too often. The only additional resource we will need is a dedicated hardwired line to allow us to transfer data to SUMEX at a reasonable rate. (At present we operate at 150 baud). Once we get to the point of directly digitizing the ultrasound scans our needs will increase dramatically, and we will have to rethink them at that point. 213 E. A. Feigenbaum Appendix I AI Handbook Outline Appendix I AI Handbook Qutline E. A. Feigenbaum and A. Barr Computer Science Department Stanford University This is a list of the Chapters in the Handbook. ‘Articles in the first eight Chapters are expected to appear in Volume I. A tentative list of the all of articles in each Chapter follouws. I. Introduction II. Search III. AI Programming Languages IV. Representation of Knowledge Vv. Natural Language Understanding VI. Speech Understanding VII. Applications-oriented AI Research VIII. Automatic Programming IX. Theorem Proving X. Vision XI. Robotics XII. Information Processing Psychology XIII. Learning and Inductive Inference XIV. Planning, Reasoning, and Problem Solving I. INTRODUCTION A. The AI Handbook (Cintent, audience, style, use, outline) B. Overview of AI C. History of AI BD. An Introduction to the AI Literature II. Heuristic Search A. Overview B. Problem representation 1. State-space representation 2. Problem-reduction representation 3. Game trees E. A. Feigenbaum 214 AI Handbook Outline C. Search Methods 1. 2. 3. BN Blind state-space search Blind AND/OR graph search Heuristic search in problem-solving a. Basic concepts in Heuristic Search b. A*¥: optimal search for an optimal solution c. Relaxing the optimality requirement d. Bidirectional search Heuristic search of an AND/OR graph Game tree search a. Minimax b. Alpha-beta c. Heuristic Search of Game Trees D. Example Search Programs Am hWN — * 6 «© «© @ Logic Theorist General Problem Solver Gelernter’s geometry theorem-proving machine Symbolic Integration Programs STRIPS - ABSTRIPS III. AI Programming Languages A. Historical Overview of AI Languages B. Comparison of AI Language Features C. LISP IV. Representation of Knowledge A. Issues and problems in representation theory B. Survey of representation techniques C. Representation Schemes NOMA WN ¥. Natural Logic Semantic nets Production systems Procedural representations Semantic primitives Direct (Analogical) representations Higher Level Knowledge Structures Language Understanding A. Overvien - History & Issues B. Grammars 1 2. 3. 4. Review of formal grammars Transformational grammars Systemic grammars Case Grammars 215 E. A. Appendix !f Feigenbaum Appendix I Al C. Parsing techniques 1. 2. 3. Overview of parsing techniques Augmented transition nets, Hoods CHARTS - GSP D. Text Generating systems E. Machine Translation 1. 2. Overvien & history Wilks’ machine translation work F. Natural Language Processing Systems om h Wh — e © © e #6 Early NL systems PARRY MARGIE LUNAR SHROLU SAM VI. Speech Understanding Systems A. Overview B. Some early ARPA speech systems 1. DRAGON 2. HEARSAY I 3. SPEECHLIS C. Recent Speech Systems 1. HARPY 2. HEARSAY II 3. HIM 4. SRI-SDC System VII. Applications-oriented AI Research A. Overview of AOAIR B. TEIRESIAS - Issues in Expert Systems Design C. Medicine 1. Overview of Medical Applications Research 2. MYCIN 3. CASNET 4. INTERNIST 5. Present Illness Program (PIP) 6. Digitalis Advisor 7. IRIS D. Chemistry 1. Overview of Applications in Chemistry 2. Applications in Chemical Analysis 3. The DENDRAL Programs a. DENDRAL b. CONGEN and its extensions c. Meta-DENDRAL 4. CRYSALIS 5. Applications in Organic Synthesis E. A. Feigenbaum 216 Handbook Outline AI Handbook Outline Appendix I E. Mathematics 1. REDUCE 2. MACSYMA 3. AM F. Education 1. Overviews a. Historical Overview of AI Research in Educational Applications b. Issues and Components of Intelligent CAI Systems . SCHOLAR - SOPHIE . WEST . BUGGY - WUMPUS - EXCHECK . WHY G. Miscellaneous Applications Research - SRI Comp. Based Consultant 2. PROSPECTOR 3. RITA (Rand) 4. AI applications to Information Retrieval 2 3 4 5 6 7 8 i 1 VIII. Automatic Programming A. Automatic Programming Overview B. Techniques for Program Specification C. Approaches to AP D. AP Systems 1. PSI 2. SAFE 3. Programmer's Apprentice 4. PECOS 5. DAEDALUS 6. PROTOSYSTEM-1 7. Heidorn's IBM System 8. LIBRA - Program Optimization IX. THEOREM PROVING A. Overview B. Logic C. Resolution Theorem Proving 1. Basic resolution method 2. Syntactic ordering strategies 3. Semantic & syntactic refinement 0. Non-resolution theorem proving QO. Overview 1. Natural deduction 2. Boyer-Moore 3. LCF 217 E. A. Feigenbaum Appendix I Al E. Uses of theorem proving 1. Use in question answering 2. Use in problem solving 3. Theorem Proving languages 4. Man-machine theorem proving 5. In Automatic Programming F. Proof checkers X. VISION A. Overview B. Image-level processing 1. Overview 2. Edge Detection 3. Texture 4. Region growing 5. Overview of Pattern Recognition C. Spatial-level processing 1. Overview 2. Stereo information 3. Shading 4. Motion D. Object-level Processing 1. Overview 2. Generalized cones and cylinders E. Scene level processing F. Vision systems 1. Polyhedral or Blocks World Vision a. Overview b. COPYDEMO b. Guzman c. Falk d. Waltz e. Navatya 2. Robot vision systems 3. Perceptrons XI. ROBOTICS Overview Robot Planning and Problem Solving Arms Present Day Industrial Robots Robotics Programming Languages moO wD YP E. A. Feigenbaum 218 Handbook Outline AI Handbook Outline Appendix I XII. Information Processing Psychology A. Overview B. Memory Models 1. Overview 2. EPAM 3. Semantic Net Models a. Quillian & Collins b. HAM-ACT (Anderson & Bower) c. LNR ASNs 4. Production Systems a Memory Models (Newell, Moran, ACT) 5. Higher level structures (Schemas, scripts & Frames) C. Human Problem Solving D. Behavioral Modeling 1. Belief Systems 2. PARRY 3. Conversational Postulates (Grice, TW) 4. Abelson, J. Carbonell, Jr., XIII. Learning and Inductive Inference A. Overvieu B. Simple Inductive Tasks 1. Sequence Extrapolation 2. Grammatical Inference C. Pattern Recognition 1. Character Recognition (Selfridge, etc.) 2. Other (e.g. Speech) D. Learning Rules and Strategies of Games 1. Formal Analysis 2. Individual Examples of Games-learning programs Single Concept Formation Multiple Concept Formation: Structuring a Domain CAM, Meta-DENDRAL) G. Interactive Cumulation of Knowledge (TEIRESIAS) "a rm XIV. Problem Solving, Planning & Reasoning by Analogy A. Overvien of Problems Solving B. Planning 1. Overview (pointers to discussions in Search, Robotics, AI Langs) 2. STRIPS (see IIDS5}) 3. ABSTRIPS (see IID6) 4. NOAH 5. HACKER 6. INTERPLAN (Tate) 7. Rieger's inference engine ? 8. Rutgers work (Schmidt, Sridharan) ? 7. QA3 (see IXE1) 219 E. A. Feigenbaum Appendix I AI Handbook Outline C. Reasoning by Analogy 1. Overview 2. Evans's ANALOGY Program 3. ZORBA 4. Ninston (see Learning) D. Constraint relaxation 1. Waltz (see Vision) 2. REF-ARF E. Game playing (This overview must point to work in search and discuss GP programs of various misc. sorts) E. A. Feigenbaum 220 Satellite Machine Evaluation Appendix I! Appendix II Satellite Machine Evaluation In the Council award for our present three-year grant term, funds were approved to purchase an additional computer that would meet two pressing needs of the SUMEX-AIM community. First, it would serve as a dedicatable machine for more operational evaluation of mature programs such as INTERNIST, PUFF/VM, MYCIN, and DENDRAL. Second, it would augment the existing SUMEX capacity to help alleviate the chronically heavy load for program development. The following provides more detailed background information about future computing trends relevant to SUMEX- AIM community needs and evaluation summaries for the two candidate systems available to meet current SUMEX augmentation requirements. Computing Trends: As We projected in our application, this past year has indeed been a time of rapid change in the computing scene. Recently, however, the direction of future DEC and ARPANET community development efforts has clarified to the extent that a preferred course for near term SUMEX computer planning is clear. 1) DEC*S LONG-TERM PLANS - Over the past few months there has been increasing confirmation (although certainly no formal announcement) that DEC may be moving their development efforts from the PDP-10/20 series of machines to the VAX series. This decision is apparently based on the limited address space of the PDOP-10 and the difficulty of changing this aspect of its architecture. We will likely not see a tangible effect of this decision for 2-3 years on TOPS-20 support. We also will not see the previously expected, more cost- effective version of the 2020 that could have extended our current design options. This trend toward VAX raises many additional questions for long-term planning including when large capacity VAX systems will be available; what time- sharing monitor will be able to provide comparable services to TENEX/TOPS-20; and when languages and software functionally equivatent to TENEX/TOPS-20 systems will be available on VAX. A usable VAX for AI work will probably take more than 2 years to mature. 22 INTERLISP STATUS - Also over the past year, Xerox has withdrawn its support for INTERLISP development and maintenance. INTERLISP, of course, forms the basis of many of our AI programs and its continued support is critical to SUMEX projects. A number of approaches to solve this problem have been under discussion in the ARPANET AI community. In view of DEC's apparent plans to concentrate its future work on VAX, ARPA has tentatively decided to support moving INTERLISP to VAX as the best long-term solution. This effort will also likely take 1-2 years for completion. Based on this forecast, 2-3 years appears to be the time frame over which today's decision about how best to meet current SUMEX community needs must be assessed. It is clear that the optimum strategy is to purchase a relatively inexpensive PDP-10-compatible system as soon as possible. The technological 221 E. A. Feigenbaum Appendix II Satellite Machine Evaluation transition getting under way will take some time to become established and this will tend to preserve the value of such an investment even beyond the next 2-3 year period. Evaluation of Currently Available Machines There are only two candidate machines that are available, meet our requirements for software compatibility, and are priced within our budget; the DEC 2020 and the Foonly F2. Promises of additional alternatives have not materialized to date and we do not expect this situation to change. Following is a comparison of the strong and weak points of each of these candidates. 1) DEC 2020 - This machine was first announced near the end of 1977 and has a good field reliability record. It is fully supported by DEC and runs under the TOPS-20 operating system. Versions of INTERNIST, MYCIN, CONGEN, etc. already exist compatible with TOPS-20 INTERLISP so software compatibility is not an issue. LISP benchmarks done at SRI indicate the 2020 averages 5-10% faster than a KA-10 (a single KI-10 averages 70% faster than a KA-10). However, the 2020 is considerably slower than this average for floating point arithmetic since it has no floating point hardware. Also, the 2020 can be expected to support no more than 3 large LISP users simultaneously since its swapping performance is poor under load because of limited 1/0 capacity. Figure 3 gives a comparison of the performance of a 384K 2020 against single- and dual-processor KI-10's under increasing load. Curves for CPU~intensive and page-swapping-intensive loads are shown in the figure. It will be seen that the elapsed time needed to accumulate 1 KI-10-equivalent CPU minute on the 2020 is larger not only because of the intrinsically slower speed of the 2020 but also because of the poorer swapping performance of the disk paging used in TOPS-20 systems. The SUMEX KI-10 system uses a a fixed head swapping device to significant advantage. With these load limitations and a list price of about $250,000, the price/performance index of the 2020 would not be very impressive. However, we have recently been offered a used machine at a substantial discount that would be available almost immediately. This discount improves the price/performance index substantially and makes the 2020 a very attractive choice to meet current community needs. There is also some hope that the list price of 2020's will drop over the next year so that other groups may be able to acquire more cost-effective versions if desired. 2) FOONLY F2 - This machine has been under development for the past year by a small company (Faonly, Inc.) that is an offshoot of the Stanford AI Laboratory. The first machine (a proprietary version) has recently been installed at TYMSHARE. It jis not working yet to an extent to evaluate performance. Another F2 is to be delivered to Systems Control, Inc. in Palo Alto about the end of May. Based on design specifications, this machine will likely perform comparably to the DEC 2020 or slightly faster. It has the advantage of lower cost ($122,500 for a configuration comparable to the 2020 above). The major disadvantages of the F2 are that Foonly is a very smal] company and few machines have been ordered or produced to date. In addition to raising questions about future support for the machine, these factors show E. A. Feigenbaum 222 Satellite Machine Evaluation Appendix II up in delays for integrated circuit deliveries and hence slow production of new machines. The SCI machine has slipped more than a month already and future deliveries are quoted to take at least 120 days "depending on semi- conductor availability". The F2 would run a version of TENEX so software compatibility should be no problem. However, hardware and software maintenance would likely have to be done in-house with no long-term assurance of the availability of vendor assistance or parts. Another machine, the F4, has been discussed by Foonly and may have a factor of 1.5-2 increase of speed and would be priced comparably to the 2020. No orders for the F4 have been placed yet, however, and none has been built. Based on this background, we feel the discounted DEC 2020 is the better solution. It is deliverable immediately, meets our needs for software compatibility, will be supported and maintainable by DEC for a Tong time, and will likely retain better future resale value. Given the unpredictable delivery schedule for Foonly machines, the smallness of the company, and the investment we would have to make in a "one of a kind” machine, we feel that the F2 does not have a sufficient price advantage to override the other attendant risks. 223 E. A. Feigenbaum Appendix III AIM Management Committee Membership Appendix ITI AIM Management Committee Membership The following are the membership lists of the various SUMEX~-AIM management committees at the present time: AIM EXECUTIVE COMMITTEE: E. A. Feigenbaum LEDERBERG, Joshua, Ph.D. (LEDERBERG) (Chairman) President The Rockefeller University 1230 York Avenue New York, New York 10021 (212) 360-1234, 360-1235 AMAREL, Saul, Ph.D. CAMAREL) Department of Computer Science Rutgers University New Brunswick, New Jersey 08903 €201) 932-3546 BAKER, William R., Jr., Ph.D. CBAKER) (Executive Secretary) Biotechnology Resources Program National Institutes of Health Building 31, Room 5B43 9000 Rockville Pike Bethesda, Maryland 20014 (301) 496-5411 COHEN, Stanley N., M.D. CCOHEN) Division of Clinical Pharmacology, S155 Department of Medicine Stanford University Medical Center Stanford, California 94305 (415) 497-5315 FEIGENBAUM, Edward, Ph.D. CFEIGENBAUM) Principal Investigator - SUMEX Department of Computer Science Margaret Jacks Hall, Room 216 Stanford University Stanford, California 94305 (415) 497-4079 LINOBERG, Donald, M.D. CLINDBERG) (Adv Grp Member) 605 Lewis Hall University of Missouri Columbia, Missouri 65201 €314) 882-6966 224 AIM Management Committee Membership Appendix III MYERS, Jack D., M.D. (MYERS) School of Medicine Scaife Hall, 1291 University of Pittsburgh Pittsburgh, Pennsylvania 15261 (412) 624-2649 225 E. A. Feigenbaum Appendix ITI AIM Management Committee Membership IM ADVISORY GROUP: E. A. Feigenbaum LINDBERG, Donald, M.D. (LINDBERG) (Chairman) 605 Lewis Hall University of Missouri Columbia, Missouri 65201 (314) 882-6966 AMAREL, Saul, Ph.D. CAMAREL) Department of Computer Science Rutgers University New Brunswick, New Jersey 08903 (201) 932-3546 BAKER, William R., Jr., Ph.D. CBAKER) (Executive Secretary) Biotechnology Resources Program National Institutes of Health Building 31, Room 5B43 9000 Rockville Pike Bethesda, Maryland 20014 (301) 496-5411 COHEN, Stanley N., M.O. CCOHEN) Division of Clinical Pharmacology, $155 Department of Medicine Stanford University Medical Center Stanford, California 394305 (415) 497-5315 FEIGENBAUM, Edward, Ph.D. (FEIGENBAUM) (Ex-officio) Principal Investigator - SUMEX Department of Computer Science Margaret Jacks Hall, Room 216 Stanford University Stanford, California 94305 €415) 497-4079 LEDERBERG, Joshua, Ph.D. (LEDERBERG) President The Rockefeller University 1230 York Avenue New York, New York 10021 (212) 360-1234, 360-1235 MINSKY, Marvin, Ph.D. (MINSKY) Artificial Intelligence Laboratory Massachusetts Institute of Technology 545 Technology Square Cambridge, Massachusetts 02139 (617) 253-5864 226 AIM Management Committee Membership MOHLER, William C., M.D. CMOHLER) MYERS, PAUKER> SIMON, Associate Director Division of Computer Research and Technology National Institutes of Health Building 12A, Room 3033 9000 Rockville Pike Bethesda, Maryland 20014 (301) 496-1168 Jack D., M.D. CMYERS) School of Medicine Scaife Hall, 1291 University of Pittsburgh Pittsburgh, Pennsylvania 15261 (412) 624-2649 Stephen G., M.D. (CPAUKER) Department of Medicine ~- Cardiology Tufts New England Medical Center Hospital 171 Harrison Avenue Boston, Massachusetts 02111 (617) 956-5910 Herb, Ph.D. CSIMON) Department of Psychology Baker Hall, 339 Carnegie-Mellon University Schenley Park Pittsburgh, Pennsylvania 15213 (412) 578-2787 or 578-2000 227 E. A. Appendix III Feigenbaum Appendix III AIM Management Committee Membership STANFORD COMMUNITY ADVISORY COMMITTEE: FEITGENBAUM, Edward, Ph.D. (Chairman) Department of Computer Science Margaret Jacks Hall, Room 216 Stanford University Stanford, California 94305 (415) 497-4079 COHEN, Stanley N., M.D. Department of Genetics and Division of Clinical Pharmacology, Department of Medicine, $155 Stanford University Medical Center Stanford, California 94305 (415) 497-5315 DJERASSI, Carl, Ph.o. Department of Chemistry, Stauffer I-106 Stanford University Stanford, California 94305 (415) 497-2783 LEVINTHAL, Elliott C., Ph.bB. Department of Genetics, $047 Stanford University Medical Center Stanford, California 94305 (415) 497-5813 E. A. Feigenbaum 228