Tài liệu The handbook of artificial intelligence volume 1

  • Số trang: 440 |
  • Loại file: PDF |
  • Lượt xem: 105 |
  • Lượt tải: 0

Mô tả:

The handbook of artificial intelligence volume 1
T J ©dk L ©if. Avron oarr^ ^H A. reigenbaurn r Edwa.rcl VOLUME ial Avron Intelligence Systemic grammar Case grammars Parsing 5arr& Fdwqrd A reigenboum I. Overview of parsing techniques }. This three-volume work contains some 200 — on AI research the design of computer programs that exhibit near-human levels of intelligence. Each article describes a key concept, an important programming technique, or one of the outstanding examples of AI articles Augmented transition networks The General Syntactic Processor Text generation Natural language processing systems Early natural language systems I. Wilks's machine translation system LUNAR ;. !. SHRDLU MARGIE SAM and PAM LIFER programs. In addition, there are overview ar- about approaches within a subfield, the issues, and the problems. ticles Volume contains five chapters, as well as I an index and bibliography. The first chapter discusses the goals of AI research, the history of the field, and the current active areas of research. It includes an article on The Hand- how the literature of the field, explaining how book that describes itself organized. Finally, there is iderstanding Spoken Language )verview peech systems architecture ARPA SUR HEARSAY ^he projects HARPY HWIM The SRI/SDC speech systems book is an article on the to access volume n journal articles and technical reports for further reading. Chapters two and three cover the key concept of "search," computer problem-solving techniques, reduction search-space algorithms, and heuristic problemsearch and minimax methods, computer implementations rogramming Languages . . . computer programs, basic representation paradigms in AI, mathematical knowledge, in semantic networks, production programming languages Overview and comparison Data structures features of AI . knowledge . . Control structures Pattern matching Programming environment Truth maintenance AI programming languages Vlajor LISP systems, frames, etc. PLANNER AI research on "natural languages": grammars and parsing techniques that have been employed in AI pro- QLISP Chapter grams, four describes programs language to that translate another, from methods puter wants to say, including the ten most im- portant programs in this area. Chapter five discusses the design of programs that understand spoken language. Major projects are all described in some detail, and the chapter's overview article discusses current status, problems, and directions of research. and CONNIVER SAIL POP-2 FUZZY one for "generating" text to express what the com- Finally, AI Research Historical overview of search techniques, techniques for representing for ipplications-oriented AI Research: Science and Mathematit Overview of applications-oriented AI research TEIRESIAS-Issues in designing expert systems Research on applications in chemistry Applications in chemical analysis b. DENDRAL programs DENDRAL CONGEN and its extensions c. Meta-DENDRAL The a. Digitized by the Internet Archive in 2012 http://archive.org/details/handbookofartific01barr The Handbook of Artificial Intelligence The Handbook of Artificial Intelligence Volume I Edited by Avron Barr and Edward A. Feigenbaum Department of Computer Science Stanford University HeurisTech Press Stanford, California William Kaufmann, Los Altos, California Inc. Library of Congress Cataloging in Publication Data: The handbook of artificial intelligence. Bibliography: p. 363 Includes index. 1. Artificial intelligence. I. n. Feigenbaum, Edward A. 001.53'5 Q335.H36 ISBN 0-86576-004-7 ISBN 0-86576-005-5 Copyright © Barr, Avron, 1949- 80-28621 (set) (Vol. I) 1981 by William Kaufmann, Inc. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. For further information, write to: Permissions, William Kaufmann, Inc., One First Street, Los Altos, California 94022. All 10 rights reserved. 987654321 Printed in the United States of America To the graduate students CONTENTS OF VOLUME I List of Contributors / ix Preface I. / xi Introduction 1 / A. Artificial Intelligence B. C. / 3 The AI Handbook / 12 The AI literature / 14 E. Search / 19 A. Overview / 21 Problem representation 32 1. State-space representation / 32 2. Problem- reduction representation / 36 3. Game trees / 43 C. Search methods / 46 1. Blind state-space search / 46 2. Blind AND/OR Graph search / 54 3. Heuristic state- space search / 58 a. Basic concepts in heuristic search / 58 b. A* Optimal search for an optimal solution / 64 c. Relaxing the optimality requirement / 67 d. Bidirectional search / 72 4. Heuristic search of an AND/OR graph / 74 5. Game tree search / 84 a. Minimax procedure / 84 b. Alpha-beta pruning / 88 c. Heuristics in game tree search / 94 D. Sample search programs / 109 1. Logic Theorist / 109 2. General Problem Solver / 113 3. Gelernter's geometry theorem-proving machine / 119 4. Symbolic integration programs / 123 5. STRIPS / 128 6. ABSTRIPS / 135 B. — / Contents viii m. Knowledge Representation A. Overview / 141 143 B. Survey of representation techniques / 153 C. Representation schemes / 160 1. Logic / 160 2. Procedural representations / 172 3. Semantic networks / 180 4. Production systems / 190 5. Direct (analogical) representations / 200 6. Semantic primitives / 207 7. Frames and scripts / 216 / Language IV. Understanding Natural A. Overview 223 / 225 / B. Machine translation C. Grammars / 233 / 239 Formal grammars / 239 Transformational grammars / 245 3. Systemic grammar / 249 4. Case grammars / 252 D. Parsing / 256 1. Overview of parsing techniques / 256 2. Augmented transition networks / 263 3. The General Syntactic Processor / 268 E. Text generation / 273 F. Natural language processing systems / 281 1. Early natural language systems / 281 2. Wilks's machine translation system / 288 3. LUNAR / 292 4. SHRDLU / 295 5. MARGIE / 300 6. SAM and PAM / 306 7. LIFER / 316 1. 2. V. Understanding Spoken Language A. Overview / 325 B. Systems architecture C. / / 323 332 3. ARPA SUR projects HEARSAY / 343 HARPY / 349 HWIM / 353 4. The SRI/SDC speech systems The 1. 2. Bibliography for Volume I Name 1/391 Index for Volume Subject Index for Volume / I / 363 / 397 343 / 358 LIST The OF CONTRIBUTORS made the Handbook a reality. Together, over they have combed the entire literature of AI and make a coherent presentation of this very diverse following people have the last five years, have attempted to These researchers and students, from Stanford and other AI field. centers, have contributed to Volumes I and n or are now engaged in preparing Volume HI (being edited by Paul R. Cohen). Chapter Editors Janice Aikins James S. Bennett Victor Ciesielski (Rutgers U) William J. Clancey Paul R. Cohen James E. Davidson Thomas Dietterich Robert Elschlager Lawrence Fagan Anne v.d.L. Gardner Takeo Kanade (CMU) Jorge Phillips Steve Tappel Stephen Westfold Contributors Robert Anderson (Rand) Douglas Appelt David Arnold Michael Ballantyne (u Texas) Jon Doyle R. Geoff Dromey (u Wollongong) Richard Duda (Fairchild) Robert Engelmore David Barstow Ramez (Schlumberger) El-Masri (Honeywell) Lee Blaine (IMSSS) Susan Epstein (Rutgers U) Robert Filman (Indiana U) W. W. Fritz Fisher Peter Biesel (Rutgers U) Bledsoe (U Texas) Rodney Brooks Bruce Buchanan Richard Chestek Kenneth Clarkson Randall Davis (MIT) Gerard Dechen Johan de Kleer (Xerox) Christian Freksa (UC Berkeley) Peter Friedland Richard Gabriel Michael Genesereth Neil Goldman (ISI) Ira Goldstein (Xerox) George Heidorn (IBM) List of Contributors Douglas Hofstadter (Indiana U) Elaine Kant (CMU) William Laaser (Xerox) Douglas Lenat William Long (MIT) Robert London Pamela McCorduck Robert Moore (SRI) Richard Pattis Neil C. Rowe Gregory Ruth (MIT) Daniel Sagalowicz (SRI) William Scherlis (CMU) Andrew Silverman Donald Smith (Rutgers U) Phillip Smith (U Waterloo) Reid G. Smith (Canadian DREA) William Swartout (MIT) William van Melle Richard Waldinger (SRI) Richard Waters (MIT) Sholom Weiss (Rutgers David Wilkins (SRI) Terry Winograd U) Behrokh Samadi Reviewers Harold Abelson (MIT) Saul Amarel (Rutgers U) Robert Balzer Harry Barrow Jonathan King Casimir Kulikowski McCune (Rutgers U) (ISI) Brian P. (Fairchild) Donald Michie (U Edinburgh) Thomas Binford Daniel Bobrow (Xerox) John Seely Brown (Xerox) (Al&DS) Nils Nilsson (SRI) Andrea diSessa (MIT) Glen Ouchi (UC Santa Cruz) Ira Pohl (UC Santa Cruz) Herbert Simon (CMU) David E. Smith Dennis Smith Daniel Dolata (UC Santa Cruz) Mark Lee Erman (ISI) Adele Goldberg (Xerox) Cordell Green (SCI) Norman Haas (SRI) Kenneth Kahn (MIT) Albert Stevens (BBN) Richard Burton Lewis Creary (Xerox) Stefik (Xerox) Allan Terry Perry Thorndyke (Rand) Donald Walker (SRI) Keith Wescourt (Rand) Production Lester Ernest Marion Hazen David Fuchs Dianne Kanerva Roy Nordblom Thomas Rindfleisch Ellen Smith Helen Tognetti PREFACE Artificial Intelligence is of growing interdisciplinary interest and importance. People with widely varying backgrounds and pro- practical new fessions are discovering and new ideas tools in this young science. Theory-minded psychologists have developed new models of the mind based on the fundamental concepts of AI symbol systems and infor- — mation processing. as well as in programs Linguists are also interested in these basic notions, AI work that actually considering the progress, nonhuman intelligence, computational in understand linguistics, language. aimed at producing And and potential of problems, philosophers, this in work toward have sometimes found new perspectives on the mind and knowledge. people often first come age-old problems of the nature of In other spheres of activity, form of some own their infectious ging, system that "expert" area —chemical disease structural diagnosis, engineering, interpretation, DNA sequencing, viable. "cores" to will for structure the inevitably techniques. Since, be served many integration, computer systems debug- many new computer of these, calculational there are As the applications no mathematical use of the computer, such areas by symbolic models and symbolic inference Yet those who understand symbolic computation have been speaking largely to themselves for the first 25 years of AI's history. that this three-volume Handbook of Artificial Intelligence. is We urgent for AI to "go public" in the manner intended by feel it symbolic computer-chip design, and so on. fall, in the being applied experimentally in data cost of computation continues to become is AI across Preface xii have Handbook project began the Since labored produce to gramming techniques and to bridges build concepts. crossed dozens 1975, of researchers AI pro- With these volumes, we have by engineers, by professionals tried jargon- free short, be to in explanations of and and by our own colleagues in computer science. to cover the breadth and depth of AI, presenting general scientists in other fields, We have tried overviews of particular techniques the and exemplary we have presented important, well as issues, scientific computer key the detailed as discussions systems. concepts — search, And, of most divide-and- conquer, semantic nets, means-ends analysis, hierarchical planning, ATNs, procedural knowledge, blackboard architecture, scripts and frames, goal- — and many more in the If they were presented more context of their actual application in AI. abstractly, the unique perspective afforded by AI research on these Throughout, we have tried to keep in universal ideas would be lost. mind the reader who is not a specialist in AI. In short, we have tried to present a survey of AI research that is motivated historically and scientifically, without attempting to present a and data-driven processing, directed new synthesis of this young, learning, multifaceted, rapidly changing One field. can view these Handbook volumes as an encyclopedia of AI programming techniques, successful their computational the from Readers ways —we concepts different some of applications, have that hope that many of you used useful find will to and them. describe data these interpret will fields been limitations, their in different ideas and new articles. Key AI new perspectives. The Handbook contains several kinds of different and techniques are described in core articles semantic nets). Important individual AI programs concepts search, MACSYMA, PROSPECTOR) cate, among and the SHRDLU, other things, the designer's goals, the techniques employed, reasons be (e.g., are presented in separate articles that indi- why the program is important. The approaches in each major area are discussed in overview should heuristic (e.g., particularly useful to those who seek problems articles, summary a and which of the underlying issues that motivate AI research. We intend that the Handbook of and changing reference work. will take time to alert commission, and that editions. us Artificial In particular, to errors Intelligence we hope that our colleagues we have made, we have an opportunity be a living of omission or to correct these in future Preface xiii Acknowledgments Many ix-x is On people have contributed to the Handbook project. an alphabetical including list of those contributors, article who have been involved pages so far, and the chapter editors who reviewers, have spent months working the individual chapters into coherent preof a sentations particular AI subarea. The following reconstruction as possible of the contributions to this is as first accurate a volume over the last five years. The "Search" chapter was written by Anne Gardner, starting from some articles prepared for a problem seminar in the spring of 1975. Background material was made available by Nils Nilsson, who also read earlier drafts, as did Bruce Buchanan, Lewis Creary, James Davidson, Reid Smith, Mark and David Wilkins. "Representation of Knowledge" was edited by Avron Barr and James Davidson. The article on logic was written by Robert Filman, semantic nets by Douglas Appelt, semantic primitives by Anne Gardner, and frames by James Bennett. Mark Stefik carefully reviewed an early draft Ira Pohl, Stefik, of this chapter. Anne Gardner, James Davidson, and Avron Barr edited "Under- standing Natural Language." Articles were worked on by Janice Aikins, Rodney Brooks, William Clancey, Paul Cohen, Gerard Dechen, Richard Gabriel, Norman Haas, Douglas Hofstadter, Andrew Silverman, Phillip Smith, Reid Smith, William van Melle, and David Wilkins. Neil Gold- man reviewed an early draft of the chapter. Terry Winograd made background material available and also reviewed an early draft. "Understanding Spoken Language" was prepared by Lawrence Fagan, Paul Cohen, and Avron Barr, with helpful comments from James Bennett, Lee Erman, and Donald Walker. The professional editor responsible for the form of the final copy, and page design, was Dianne Kanerva. Earlier in the project's history, professional editing on several chapters was done by Helen Tognetti. Ellen Smith also assisted in this imporincluding electronic typesetting tant work. The book was Computer Modern and was Pubproduced directly on a computer-driven phototypesetting device. lisher William Kaufmann and his staff have been patient and helpful set in throughout this process. fonts (Knuth, 1979) Preface xiv The Advanced Research Projects Agency of the Department of Defense and the Biotechnology Resources Program of the National Institutes of Health supported the Handbook project as part of their longstanding and continuing efforts to develop and disseminate the science Earlier versions of Handbook material were and technology of AI. distributed as technical reports of the Stanford Computer Science Department. The electronic text-preparation facilities available to Stanford computer scientists on the SAIL, SCORE, and SUMEX computers were used. We during wish specially to acknowledge Anne Gardner, whose scholarship the early years of the Handbook project was invaluable, and inspirational. Finally, let us not forget that many of the programs described AI were labored over singlehandedly by graduate students trying to implement their thesis ideas. These AI systems have consistently been among the most complex and innovative computer programs of their day. They stand as a tribute to the caliber and creativity of those who have been drawn to AI research. herein as landmark events in the history of Chapter I Introduction CHAPTER I: INTRODUCTION A. Artificial Intelligence The C. The B. / 8 AI Handbook / 12 AI Literature / 14
- Xem thêm -