Artificial Intelligence Illuminated

3y ago
230 Views
17 Downloads
5.34 MB
768 Pages
Last View : 2d ago
Last Download : 4m ago
Upload by : Elisha Lemon
Transcription

Artificial IntelligenceIlluminatedBen CoppinJONES AND BARTLETT PUBLISHERS

World HeadquartersJones and Bartlett Publishers40 Tall Pine DriveSudbury, MA 01776978-443-5000info@jbpub.comwww.jbpub.comJones and Bartlett PublishersCanada2406 Nikanna RoadMississauga, ON L5C 2W6CANADAJones and Bartlett PublishersInternationalBarb House, Barb MewsLondon W6 7PAUKCopyright 2004 by Jones and Bartlett Publishers, Inc.Cover image PhotodiscLibrary of Congress Cataloging-in-Publication DataCoppin, Ben.Artificial intelligence illuminated / by Ben Coppin.--1st ed.p. cm.Includes bibliographical references and index.ISBN 0-7637-3230-31. Artificial intelligence. I. Title.Q335.C586 2004006.3--dc2220030206043382All rights reserved. No part of the material protected by this copyright notice may bereproduced or utilized in any form, electronic or mechanical, including photocopying,recording, or any information storage or retrieval system, without written permissionfrom the copyright owner.Acquisitions Editor: Stephen SolomonProduction Manager: Amy RoseMarketing Manager: Matthew BennettEditorial Assistant: Caroline SenayManufacturing Buyer: Therese BräuerCover Design: Kristin E. OhlinText Design: Kristin E. OhlinComposition: Northeast CompositorsTechnical Artist: George NicholsPrinting and Binding: Malloy, Inc.Cover Printing: Malloy, Inc.Printed in the United States of America08 07 06 05 0410 9 8 7 6 5 4 3 2 1

For Erin

This page intentionally left blank

PrefaceWho Should Read This BookThis book is intended for students of computer science at the college level,or students of other subjects that cover Artificial Intelligence. It also isintended to be an interesting and relevant introduction to the subject forother students or individuals who simply have an interest in the subject.The book assumes very little knowledge of computer science, but doesassume some familiarity with basic concepts of algorithms and computersystems. Data structures such as trees, graphs, and stacks are explainedbriefly in this book, but if you do not already have some familiarity withthese concepts, you should probably seek out a suitable book on algorithmsor data structures.It would be an advantage to have some experience in a programming language such as C or Java, or one of the languages commonly used in Artificial Intelligence research, such as PROLOG and LISP, but this experienceis neither necessary nor assumed.Many of the chapters include practical exercises that require the reader todevelop an algorithm or program in a programming language of his or herchoice. Most readers should have no difficulty with these exercises. However, if any reader does not have the necessary skills he or she simply shoulddescribe in words (or in pseudocode) how his or her programs work, givingas much detail as possible.

viPrefaceHow to Read This BookThis book can be read in several ways. Some readers will choose to read thechapters through in order from Chapter 1 through Chapter 21. Any chapterthat uses material which is presented in another chapter gives a clear reference to that chapter, and readers following the book from start to finishshould not need to jump forward at any point, as the chapter dependenciestend to work in a forward direction.Another perfectly reasonable way to use this book is as a reference. When areader needs to know more about a particular subject, he or she can pick upthis book and select the appropriate chapter or chapters, and can be illuminated on the subject (at least, that is the author’s intent!)Chapter 12 contains a diagram that shows how the dependencies betweenchapters work (Section 12.6.2). This diagram shows, for example, that if areader wants to read Chapter 8, it would be a good idea to already have readChapter 7.This book is divided into six parts, each of which is further divided into anumber of chapters. The chapters are laid out as follows:Part 1: Introduction to Artificial IntelligenceChapter 1: A Brief History of Artificial IntelligenceChapter 2: Uses and LimitationsChapter 3: Knowledge RepresentationPart 2: SearchChapter 4: Search MethodologiesChapter 5: Advanced SearchChapter 6: Game PlayingPart 3: LogicChapter 7: Propositional and Predicate LogicChapter 8: Inference and Resolution for Problem SolvingChapter 9: Rules and Expert Systems

PrefacePart 4: Machine LearningChapter 10: Introduction to Machine LearningChapter 11: Neural NetworksChapter 12: Probabilistic Reasoning and Bayesian Belief NetworksChapter 13: Artificial Life: Learning through Emergent BehaviorChapter 14: Genetic AlgorithmsPart 5: PlanningChapter 15: Introduction to PlanningChapter 16: Planning MethodsPart 6: Advanced TopicsChapter 17: Advanced Knowledge RepresentationChapter 18: Fuzzy ReasoningChapter 19: Intelligent AgentsChapter 20: Understanding LanguageChapter 21: Machine VisionEach chapter includes an introduction that explains what the chapter covers, a summary of the chapter, some exercises and review questions, andsome suggestions for further reading. There is a complete bibliography atthe back of the book.This book also has a glossary, which includes a brief definition of most ofthe important terms used in this book. When a new term is introduced inthe text it is highlighted in bold, and most of these words are included inthe glossary. The only such terms that are not included in the glossary arethe ones that are defined in the text, but that are not used elsewhere in thebook.The use of third person pronouns is always a contentious issue for authorsof text books, and this author has chosen to use he and she interchangeably.In some cases the word “he” is used, and in other cases “she.” This is notintended to follow any particular pattern, or to make any representationsabout the genders, but simply is in the interests of balance.vii

viiiPrefaceThe first few chapters of this book provide introductory material, explaining the nature of Artificial Intelligence and providing a historical background, as well as describing some of the connections with otherdisciplines. Some readers will prefer to skip these chapters, but it is advisable to at least glance through Chapter 3 to ensure that you are familiarwith the concepts of that chapter, as they are vital to the understanding ofmost of the rest of the book.AcknowledgmentsAlthough I wrote this book single-handedly, it was not without help. Iwould like to thank, in chronological order, Frank Abelson; Neil Salkindand everyone at Studio B; Michael Stranz, Caroline Senay, StephenSolomon, and Tracey Chapman at Jones & Bartlett; also a number of people who read chapters of the book: Martin Charlesworth, Patrick Coyle,Peter and Petra Farrell, Robert Kealey, Geoffrey Price, Nick Pycraft, ChrisSwannack, Edwin Young, my parents, Tony and Frances, and of courseErin—better late than never.Thanks also to:The MIT Press for the excerpt from ‘Learning in Multiagent Systems’ bySandip Sen and Gerhard Weiss, 2001, The MIT Press.The MIT Press for the excerpt from ‘Adaptation in Natural and ArtificialSystems’ by John H. Holland, 1992, The MIT Press.The MIT Press for the excerpt from ‘The Artificial Life Roots of ArtificialIntelligence’ by Luc Steels, 1994, the Massachusetts Institute of Technology.The IEEE for the excerpt from ‘Steps Towards Artificial Intelligence’ byMarvin Minsky, 2001, IEEE.I have attempted to contact the copyright holders of all copyrighted quotesused in this book. If I have used any quotes without permission, then thiswas inadvertent, and I apologize. I will take all measures possible to rectifythe situation in future printings of the book.

ContentsPrefacevPA R T 1Introduction to Artificial IntelligenceChapter 11.11.21.31.41.51.61.71.81.91.10A Brief History of Artificial IntelligenceIntroduction 3What Is Artificial Intelligence? 4Strong Methods and Weak Methods 5From Aristotle to Babbage 6Alan Turing and the 1950s 7The 1960s to the 1990s 9Philosophy 10Linguistics 11Human Psychology and Biology 12All Programming Languages 121.10.1 PROLOG 131.10.2 LISP 141.11 Chapter Summary 151.12 Review Questions 161.13 Further Reading 1713

xContentsChapter 22.12.22.32.42.52.62.7Uses and Limitations 19Introduction 19The Chinese Room 20HAL—Fantasy or Reality? 21AI in the 21st Century 23Chapter Summary 24Review Questions 24Further Reading 25Chapter 33.13.23.33.43.5Knowledge Representation 27Introduction 27The Need for a Good Representation 28Semantic Nets 29Inheritance 31Frames 323.5.1 Why Are Frames Useful? 343.5.2 Inheritance 343.5.3 Slots as Frames 353.5.4 Multiple Inheritance 363.5.5 Procedures 373.5.6 Demons 383.5.7 Implementation 383.5.8 Combining Frames with Rules 403.5.9 Representational Adequacy 40Object-Oriented Programming 41Search Spaces 42Semantic Trees 44Search Trees 463.9.1 Example 1: Missionaries and Cannibals 473.9.2 Improving the Representation 493.9.3 Example 2: The Traveling Salesman 503.9.4 Example 3: The Towers of Hanoi 543.9.5 Example 4: Describe and Match 56Combinatorial Explosion 57Problem Reduction 573.63.73.83.93.103.11

Contents3.12 Goal Trees 583.12.1 Top Down or Bottom Up?3.12.2 Uses of Goal Trees 61Example 1: Map ColoringExample 2: Proving TheoremsExample 3: Parsing Sentences 63Example 4: Games3.13 Chapter Summary 643.14 Review Questions 653.15 Exercises 653.16 Further Reading 66PA R T 2Chapter 44.14.24.34.44.54.64.74.84.94.104.114.1260Search 69Search Methodologies 71Introduction 71Problem Solving as Search 72Data-Driven or Goal-Driven Search 73Generate and Test 74Depth-First Search 75Breadth-First Search 76Properties of Search Methods 784.7.1 Complexity 784.7.2 Completeness 794.7.3 Optimality 794.7.4 Irrevocability 80Why Humans Use Depth-First Search? 804.8.1 Example 1: Traversing a Maze 814.8.2 Example 2: Searching for a Gift 81Implementing Depth-First and Breadth-First SearchExample: Web Spidering 88Depth-First Iterative Deepening 88Using Heuristics for Search 904.12.1 Informed and Uninformed Methods 914.12.2 Choosing a Good Heuristic 924.12.3 The 8-Puzzle 9283xi

xiiContents4.134.144.154.164.174.184.194.20Chapter 55.15.25.35.45.55.65.75.84.12.4 Monotonicity 954.12.5 Example: The Modified Traveling SalesmanProblem 96Hill Climbing 984.13.1 Steepest Ascent Hill Climbing 984.13.2 Foothills, Plateaus, and Ridges 101Best-First Search 104Beam Search 106Identifying Optimal Paths 1074.16.1 A* Algorithms 1084.16.2 Uniform Cost Search 1104.16.3 Greedy Search 1114.16.4 Example: The Knapsack Problem 111Chapter Summary 113Review Questions 114Exercises 115Further Reading 116Advanced Search 117Introduction 117Constraint Satisfaction Search 118Forward Checking 121Most-Constrained Variables 121Example: Cryptographic Problems 122Heuristic Repair 123Combinatorial Optimization Problems 125Local Search and Metaheuristics 1265.8.1 Exchanging Heuristics 1265.8.2 Iterated Local Search 1275.8.3 Tabu Search 1275.8.4 Ant Colony Optimization 1285.9 Simulated Annealing 1285.9.1 Uses of Simulated Annealing 1305.10 Genetic Algorithms for Search 1315.11 Real-Time A* 131

Contents5.12 Iterative-Deepening A* (IDA*) 1325.13 Parallel Search 1325.13.1 Task Distribution 1345.13.2 Tree Ordering 1355.13.3 Search Engines 1355.14 Bidirectional Search 1365.15 Nondeterministic Search 1365.16 Island-Driven Search 1375.17 Nonchronological Backtracking 1375.18 Chapter Summary 1385.19 Review Questions 1395.20 Exercises 1405.21 Further Reading 141Chapter 6 Game Playing 1436.1 Introduction 1436.2 Game Trees 1446.2.1 Rationality, Zero Sum, and OtherAssumptions 1456.2.2 Evaluation Functions 1466.2.3 Searching Game Trees 1486.3 Minimax 1496.3.1 Bounded Lookahead 1516.4 Alpha-Beta Pruning 1536.4.1 The Effectiveness of Alpha-Beta Pruning6.4.2 Implementation 1556.5 Checkers 1596.5.1 Chinook 1606.5.2 Chinook’s Databases 1616.5.3 Chinook’s Evaluation Function 1626.5.4 Forward Pruning 1636.5.5 Limitations of Minimax 1636.5.6 Blondie 24 1646.6 Chess 164154xiii

xivContents6.7 Go 1656.7.1 Go-Moku 1666.8 Othello (Reversi) 1666.9 Games of Chance 1666.9.1 Expectiminimax 1676.10 Chapter Summary 1676.11 Review Questions 1686.12 Exercises 1696.13 Further Reading 170PA R T 3Chapter 77.17.27.37.47.57.67.77.87.97.107.11Knowledge Representation and AutomatedReasoning 173Propositional and Predicate Logic 175Introduction 175What Is Logic? 176Why Logic Is Used in Artificial Intelligence 176Logical Operators 177Translating between English and Logic Notation 178Truth Tables 1817.6.1 Not 1817.6.2 And 1827.6.3 Or 1827.6.4 Implies 1837.6.5 iff 184Complex Truth Tables 184Tautology 186Equivalence 187Propositional Logic 1897.10.1 Syntax 1897.10.2 Semantics 190Deduction 1917.11.1 -Introduction 1917.11.2 -Eliminations 1917.11.3 Or-Introduction 1927.11.4 ?Elimination 192

227.237.247.257.11.5 Reductio Ad Absurdum 1927.11.6 ?Introduction 1937.11.7 Elimination 1937.11.8 Example 1 1937.11.9 Example 2 1947.11.10 Example 3 1947.11.11 Example 4 195The Deduction Theorem 195Predicate Calculus 1967.13.1 Syntax 1967.13.2 Relationships between " and 1977.13.3 Functions 199First-Order Predicate Logic 199Soundness 200Completeness 200Decidability 200Monotonicity 201Abduction and Inductive Reasoning 201Modal Logics and Possible Worlds 2037.20.1 Reasoning in Modal Logic 204Dealing with Change 205Chapter Summary 205Review Questions 205Exercises 206Further Reading 208Chapter 8 Inference and Resolution for Problem Solving8.1 Introduction 2098.2 Resolution in Propositional Logic 2108.2.1 Normal Forms 2108.2.2 The Resolution Rule 2128.2.3 Resolution Refutation 2138.2.4 Proof by Refutation 2148.3 Applications of Resolution 2168.4 Resolution in Predicate Logic 218209xv

xviContents8.5 Normal Forms for Predicate Logic 2198.6 Skolemization 2208.6.1 Example of Skolemization 2218.6.2 Second Example of Skolemization 2228.6.3 Unification 2228.6.4 Most General Unifiers 2248.6.5 Unification Algorithm 2248.6.6 Unification Example 2258.7 Resolution Algorithm 2268.8 Horn Clauses and PROLOG 2278

PA R T 1 Introduction to Artificial Intelligence 1 Chapter 1 A Brief History of Artificial Intelligence 3 1.1 Introduction 3 1.2 What Is Artificial Intelligence? 4 1.3 Strong Methods and Weak Methods 5 1.4 From Aristotle to Babbage 6 1.5 Alan Turing and the 1950s 7 1.6 The 1960s to the 1990s 9 1.7 Philosophy 10 1.8 Linguistics 11

Related Documents:

Artificial Intelligence -a brief introduction Project Management and Artificial Intelligence -Beyond human imagination! November 2018 7 Artificial Intelligence Applications Artificial Intelligence is the ability of a system to perform tasks through intelligent deduction, when provided with an abstract set of information.

Artificial Intelligence (AI) will be considered – AI is interdisciplinary ! Foundational Topics to Covered – Intelligent Agents . Artificial Intelligence: A New Synthesis. Morgan Kaufmann, 1998 – B. Coppin. Artificial Intelligence Illuminated. Jones and Bartlett, 2004

and artificial intelligence expert, joined Ernst & Young as the person in charge of its global innovative artificial intelligence team. In recent years, many countries have been competing to carry out research and application of artificial intelli-gence, and the call for he use of artificial

BCS Foundation Certificate in Artificial Intelligence V1.1 Oct 2020 Syllabus Learning Objectives 1. Ethical and Sustainable Human and Artificial Intelligence (20%) Candidates will be able to: 1.1. Recall the general definition of Human and Artificial Intelligence (AI). 1.1.1. Describe the concept of intelligent agents. 1.1.2. Describe a modern .

IN ARTIFICIAL INTELLIGENCE Stuart Russell and Peter Norvig, Editors FORSYTH & PONCE Computer Vision: A Modern Approach GRAHAM ANSI Common Lisp JURAFSKY & MARTIN Speech and Language Processing, 2nd ed. NEAPOLITAN Learning Bayesian Networks RUSSELL & NORVIG Artificial Intelligence: A Modern Approach, 3rd ed. Artificial Intelligence A Modern Approach Third Edition Stuart J. Russell and Peter .

Peter Norvig Prentice Hall, 2003 This is the book that ties in most closely with the module Artificial Intelligence (2nd ed.) Elaine Rich & Kevin Knight McGraw Hill, 1991 Quite old now, but still a good second book Artificial Intelligence: A New Synthesis Nils Nilsson Morgan Kaufmann, 1998 A good modern book Artificial Intelligence (3rd ed.) Patrick Winston Addison Wesley, 1992 A classic, but .

BCS Essentials Certificate in Artificial Intelligence Syllabus V1.0 BCS 2018 Page 10 of 16 Recommended Reading List Artificial Intelligence and Consciousness Title Artificial Intelligence, A Modern Approach, 3rd Edition Author Stuart Russell and Peter Norvig, Publication Date 2016, ISBN 10 1292153962

* ASTM C 33 Table 2 Size Number 501–2.2 CEMENT. Cement shall conform to the requirements of ASTM C 150 Type I, Type II, or Type III. NOTE TO SPECIFIER: The FAA allows the following: ASTM C 150 – Type I, II, III, or IV. ASTM C 595 – Type IP, IS, S, I. Type I, Type II, or Type III cement was used in the Standard Specifications other types may be specified in the Special Provisions. ASTM C .