Page 1
ARTIFICIAL INTELLIGENCE A Systems Approach M. TIM JONES INFINITY SCIENCE PRESS LLC Hingham, Massachusetts New Delhi
Contenu du document
Page 2
Copyright 2008 by INFINITY SCIENCE PRESS LLC All rights reserved. This publication, portions of it, or any accompanying software may not be reproduced in any way, stored in a retrieval system of any type, or transmitted by any means or media, electronic or mechanical, including, but not limited to, photocopy, recording, Internet postings or scanning, without prior permission in writing from the publisher. Publisher: DAVID PALLAI INFINITY SCIENCE PRESS LLC 11 Leavitt Street Hingham, MA 02043 Tel. 877-266-5796 (toll free) Fax 781-740-1677 info@infinitysciencepress.com www.infinitysciencepress.com This book is printed on acid-free paper. M. Tim Jones. Artificial Intelligence: A Systems Approach ISBN: 978-0-9778582-3-1 The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to distinguish their products. All brand names and product names mentioned in this book are trademarks or service marks of their respective companies. Any omission or misuse (of any kind) of service marks or trademarks, etc. is not an attempt to infringe on the property of others. Library of Congress Cataloging-in-Publication Data JONES, M. TIM. Artificial intelligence : a systems approach / M. Tim Jones. p. cm. Includes index. ISBN-13: 978-0-9778582-3-1 (hardcover with cd-rom : alk. paper) 1. Artificial intelligence--Data processing. 2. Artificial intelligence--Mathematical models. I. Title. Q336.J68 2008 006.3--dc22 2007045869 7 8 9 0 4 3 2 1 Our titles are available for adoption, license or bulk purchase by institutions, corporations, etc. For additional information, please contact the Customer Service Dept. at 877-266-5796 (toll free). Requests for replacement of a defective CD-ROM must be accompanied by the original disc, your mailing address, telephone number, date of purchase and purchase price. Please state the nature of the problem, and send the information to INFINITY SCIENCE PRESS, 11 Leavitt Street, Hingham, MA 02043. The sole obligation of INFINITY SCIENCE PRESS to the purchaser is to replace the disc, based on defective materials or faulty workmanship, but not based on the operation or functionality of the product.
Page 3
DEDICATION This book is dedicated to my wonderful wife, Jill, without whom this book would not be possible. I’m also indebted to my parents Maury and Celeta, who instilled in me a desire to learn and wonder.
Page 4
ACKNOWLEDGMENTS At the time of this writing, AI is celebrating its 50th anniversary. It was August of 1956 when researchers met at the Dartmouth Summer Research Project on Artificial Intelligence with the agenda of creating intelligent machines. In the 50 years that followed, AI has become a genuine field of study, but the road has not been without its bumps. Acknowledging all those who’ve contributed to AI would fill a book much larger than this. But I’d like to personally recognize John McCarthy for introducing AI in 1955 (at the Dartmouth Summer Project) and for having created the wonderful Lisp programming language.
Page 5
TABLE OF CONTENTS Chapter 1 The History of AI 1-19 What is Intelligence? 1 The Search for Mechanical Intelligence 2 The Very Early Days (the early 1950’s) 3 Alan Turing 3 AI, Problem Solving and Games 4 Artificial Intelligence Emerges as a Field 5 The Dartmouth AI Summer Research Project 5 Building Tools for AI 6 The Focus on Strong AI 6 Constrained Applications 7 Bottom-Up Approaches Emerge 7 AI’s Winter 8 Results-Oriented Applications 8 Additional AI Tools Emerge 9 Neat vs. Scruffy Approaches 9 AI Remerges 10 The Silent Return 10 Messy and Scruffy Approaches Take Hold 10 Agent Systems 12 AI Inter-disciplinary R&D 12 Systems Approach 13 Overview of this Book 15 Uninformed Search 15 Informed Search 15 AI and Games 15 Knowledge Representation 16
Page 6
Machine Learning 16 Evolutionary Computation 16 Neural Networks Part 1 16 Neural Networks Part 2 17 Intelligent Agents 17 Biologically Inspired and Hybrid Models 17 Languages of AI 17 Chapter Summary 18 References 18 Resources 18 Exercises 19 Chapter 2 Uninformed Search 21-48 Search and AI 21 Classes of Search 22 General State Space Search 22 Search in a Physical Space 22 Search in a Puzzle Space 23 Search in an Adversarial Game Space 25 Trees, Graphs and Representation 27 Uninformed Search 29 Helper APIs 30 General Search Paradigms 31 Depth-First Search 31 Depth-Limited Search 34 Iterative Deepening Search 36 Breadth-First Search 39 Bidirectional Search 42 Uniform-Cost Search 42 Improvements 45 Algorithm Advantages 46 Chapter Summary 46 Algorithms Summary 46 References 47 Exercises 47 Chapter 3 Informed Search 49-88 Search and AI 49 Best-First Search 50 Best-First Search and the N-Queens Problem 50
Page 7
Best-First Search Implementation 52 Variants of Best-First Search 56 A* Search 57 A* Search and the Eight Puzzle 59 Eight Puzzle Representation 59 A* Search Implementation 61 Eight Puzzle Demonstration with A* 64 A* Variants 65 Applications of A* Search 65 Hill Climbing Search 65 Simulated Annealing 66 The Traveling Salesman Problem (TSP) 68 TSP Tour Representation 68 Simulated Annealing Implementation 70 Simulated Annealing Demonstration 73 Tabu Search 75 Tabu Search Implementation 77 Tabu Search Demonstration 79 Tabu Search Variants 80 Constraint Satisfaction 81 Graph Coloring as a CSP 81 Scheduling as CSP 83 Constraint Satisfaction Problems 84 Generate and Test 84 Backtracking 84 Forward Checking and Look Ahead 84 Min-Conflicts Search 86 Chapter Summary 86 Algorithms Summary 86 References 86 Resources 87 Exercises 87 Chapter 4 AI and Games 89-142 Two Player Games 89 The Minimax Algorithm 92 Minimax and Tic-Tac-Toe 95 Minimax Implementation for Tic-Tac-Toe 98 Minimax with Alpha-Beta Pruning 101 Classical Game AI 106
Page 8
Checkers 106 Checker Board Representation 107 Techniques used in Checkers Programs 107 Opening Books 108 Static Evaluation Function 108 Search Algorithm 108 Move History 108 Endgame Database 109 Chess 109 Chess Board Representation 110 Techniques used in Chess Programs 110 Opening Book Database 110 Minimax Search with Alpha Beta Pruning 111 Static Board Evaluation 111 Othello 112 Techniques used in Othello Programs 112 Opening Knowledge 112 Static Evaluation Function 112 Search Algorithm 113 Endgames 113 Other Algorithms 113 Go 114 Go Board Representation 114 Techniques used in Go Programs 114 Opening Moves 115 Move Generation 115 Evaluation 115 Endgame 116 Backgammon 116 Techniques used in Backgammon Programs 116 Neurogammon 116 TD-Gammon 117 Poker 118 Loki – A learning Poker Player 119 Scrabble 120 Video Game AI 121 Applications of AI Algorithms in Video Games 122 Movement and Pathfinding 123 Table Lookup with Offensive and Defensive Strategy 123 NPC Behavior 129
Page 9
Static State Machines 130 Layered Behavior Architectures 131 Other Action-Selection Mechanisms 132 Team AI 132 Goals and Plans 134 Real-Time Strategy AI 136 Rules-Based Programming 136 Chapter Summary 139 References 139 Resources 140 Exercises 141 Chapter 5 Knowledge Representation 143-170 Introduction 143 Types of Knowledge 144 The Role of Knowledge 144 Semantic Nets 145 Frames 146 Proposi tional Logic 149 Deductive Reasoning with Propositional Logic 151 Limitations of Propositional Logic 152 First Order Logic (Predicate Logic) 152 Atomic Sentences 153 Compound Sentences 154 Variables 154 Quantifiers 155 First-Order Logic and Prolog 155 Simple Example 155 Information Retrieval and KR 157 Representing and Reasoning about an Environment 159 Semantic Web 163 Computational Knowledge Discovery 165 The BACON System 165 Automatic Mathematician 166 Ontology 167 Communication of Knowledge 167 Common Sense 168 Summary 169 References 169 Resources 169
Page 10
Exercises 170 Chapter 6 Machine Learning 171-193 Machine Learning Algorithms 171 Supervised Learning 172 Learning with Decision Trees 172 Creating a Decision Tree 174 Characteristics of Decision Tree Learning 176 Unsupervised Learning 176 Markov Models 177 Word Learning with Markov Chains 177 Word Generation with Markov Chains 179 Markov Chain Implementation 180 Other Applications of Markov Chains 184 Nearest Neighbor Classification 185 1NN Example 186 k-NN Example 188 Summary 192 Resources 192 Exercises 192 Chapter 7 Evolutionary Computation 195-247 Short History of Evolutionary Computation 195 Evolutionary Strategies 196 Evolutionary Programming 197 Genetic Algorithms 197 Genetic Programming 198 Biological Motivation 199 Genetic Algorithms 200 Genetic Algorithm Overview 200 Genetic Algorithm Implementation 204 Genetic Programming 212 Genetic Programming Algorithm 212 Genetic Programming Implementation 215 Evolutionary Strategies 220 Evolutionary Strategies Algorithm 221 Evolutionary Strategies Implementation 223 Differential Evolution 227 Differential Evolution Algorithm 228 Differential Evolution Implementation 230
Page 11
Particle Swarm Optimization 236 Particle Swarm Algorithm 236 Particle Swarm Implementation 238 Evolvable Hardware 244 Summary 244 References 245 Resources 245 Exercises 245 Chapter 8 Neural Networks I 249-287 Short History of Neural Networks 249 Biological Motiviation 250 Fundamentals of Neural Networks 251 Single Layer Perceptrons 252 Multi-Layer Perceptrons 254 Supervised vs. Unsupervised Learning Algorithms 257 Binary vs. Continuous Inputs and Outputs 257 The Perceptron 257 Perceptron Learning Algorithm 259 Perceptron Implementation 260 Least-Mean-Square (LMS) Learning 262 LMS Learning Algorithm 262 LMS Implementation 263 Learning with Backpropagation 265 Backpropagation Algorithm 267 Backpropagation Implementation 268 Tuning Backpropagation 274 Training Variants 274 Weight Adjustment Variants 274 Probabilistic Neural Networks 275 PNN Algorithm 276 PNN Implementation 277 Other Neural Network Architectures 281 Time Series Processing Architecture 281 Recurrent Neural Network 283 Tips for Building Neural Networks 283 Defining the Inputs 283 Defining the Outputs 284 Choice of Activation Functions 284 Number of Hidden Layers 285
Page 12
Chapter Summary 285 References 285 Exercises 285 Chapter 9 Neural Networks II 289-328 Unsupervised Learning 289 Hebbian Learning 290 Hebb’s Rule 291 Hebb Rule Implementation 292 Simple Competitive Learning 296 Vector Quantization 297 Vector Quantization Implementation 298 k-Means Clustering 304 k-Means Algorithm 305 k-Means Implementation 307 Adaptive Resonance Theory 313 ART-1 Algorithm 314 ART-1 Implementation 316 Hopfield Auto-Associative Model 322 Hopfield Auto-Associator Algorithm 323 Hopfield Implementation 324 Summary 327 References 328 Exercises 328 Chapter 10 Robotics and AI 329-348 Introduction to Robotics 329 What is a Robot? 330 A Sampling from the Spectrum of Robotics 331 Taxonomy of Robotics 332 Fixed 333 Legged 333 Wheeled 333 Underwater 333 Aerial 333 Other Types of Robots 334 Hard vs. Soft Robotics 334 Braitenburg Vehicles 334 Natural Sensing and Control 336 Perception with Sensors 337
Page 13
Actuation with Effectors 338 Robotic Control Systems 338 Simple Control Architectures 339 Reactive Control 340 Subsumption 340 Other Control Systems 342 Movement Planning 342 Complexities of Motion Planning 342 Cell Decomposition 343 Potential Fields 344 Group or Distributed Robotics 345 Robot Programming Languages 346 Robot Simulators 346 Summary 346 References 346 Resources 347 Exercises 347 Chapter 11 Intelligent Agents 349-391 Anatomy of an Agent 350 Agent Properties and AI 351 Rationale 352 Autonomous 352 Persistent 352 Communicative 352 Cooperative 353 Mobile 353 Adaptive 353 Agent Environments 353 Agent Taxonomies 356 Interface Agents 356 Virtual Character Agents 357 Entertainment Agents 358 Game Agents 358 ChatterBots 360 Eliza and Parry 360 AIML 361 Mobile Agents 362 User Assistance Agent 364 Email Filtering 364
Page 14
Information Gathering and Filtering 365 Other User-Assistance Applications 365 Hybrid Agent 366 Agent Architectures 366 What is Architecture? 366 Types of Architectures 367 Reactive Architectures 367 Deliberative Architectures 368 Blackboard Architectures 369 BDI Architecture 370 Hybrid Architectures 371 Mobile Architectures 371 Architecture Description 372 Subsumption Architecture (Reactive) 372 Behavior Networks (Reactive) 373 ATLANTIS (Deliberative) 375 Homer (Deliberative) 376 BB1 (Blackboard) 377 Open Agent Architecture (Blackboard) 377 Procedural Reasoning System (BDI) 378 Aglets (Mobile) 379 Messengers (Mobile) 380 SOAR (Hybrid) 382 Agent Languages 382 Telescript 382 Aglets 383 Obliq 384 Agent TCL 384 Traditional Languages 385 Agent Communication 385 Knowledge Query and Manipulation Language (KQML) 385 FIPA Agent Communication Language 388 Extensible Markup Language (XML) 388 Summary 389 Resources 389 References 390 Exercises 391 Chapter 12 Biologically Inspired and Hybrid Models 393-432 Cellular Automata 393
Page 15
One Dimensional CA 394 Two Dimensional CA 395 Conway Application 396 Turing Completeness 398 Emergence and Organization 398 Artificial Immune Systems 398 Self-Management Capabilities 399 Touchpoints 400 Touchpoint Autonomic Managers 400 Orchestrating Autonomic Managers 401 Integrated Management Console 401 Autonomic Summary 402 Artificial Life 402 Echo 403 Tierra 403 Simulated Evolution 403 Environment 403 The Bug (or Agent) 404 Variations of Artificial Life 408 Lindenmayer Systems 408 Fuzzy Logic 410 Introduction to Fuzzy Logic 410 Fuzzy Logic Mapping 411 Fuzzy Logic Operators 414 Fuzzy Control 415 Evolutionary Neural Networks 416 Genetically Evolved Neural Networks 416 Simulation Evolution Example 419 Ant Colony Optimization 423 Traveling Salesman Problem 423 Path Selection 425 Pheromone Intensification 425 Pheromone Evaporation 426 New Tour 426 Sample Usage 426 ACO Parameters 430 Affective Computing 430 Characterizing Human Emotion 430 Synthesizing Emotion 431 Resources 432
Page 16
Chapter 13 The Languages of AI 433-483 Language Taxonomy 433 Functional Programming 434 Imperative Programming 437 Object Oriented Programming 438 Logic Programming 441 Languages of AI 442 The LISP Language 443 The History of the LISP Language 443 Overview of the LISP Language 444 Data Representation 444 Simple Expressions 444 Predicates 445 Variables 445 List Processing 445 Programs as Data 447 Conditions 447 Functions in LISP 448 LISP Summary 451 The Scheme Language 451 History of Scheme 452 Overview of the Scheme Language 452 Data Representation 452 Simple Expressions 452 Predicates 453 Variables 453 List Processing 454 Conditions 455 Iteration and Maps 456 Procedures in Scheme 457 Scheme Summary 460 The POP-11 Language 460 History of POP-11 460 Overview of the POP-11 Language 460 Data Representation 460 Predicates 461 Simple Expressions 461 Variables 462 List Processing 462 Conditions 463
Page 17
Iteration and Maps 464 Pattern Matching 465 Procedures in POP-11 465 POP-11 Summary 468 Prolog 468 History of Prolog 469 Overview of the Prolog Language 469 Data Representation 469 List Processing 470 Facts, Rules, and Evaluation 471 Arithmetic Expressions 478 Prolog Summary 480 Other Languages 480 Chapter Summary 481 References 481 Resources 482 Exercises 482 About the CD-ROM 485 Index 487-498
Page 19
1 T H AI C h a p t e r HE ISTORY OF The history of AI is interesting all by itself. It’s a modern-day drama,filled with excitement and anticipation, discovery, and disappointment. From over-promises of early (and later) AI research, to fears of the unknown from the general public, AI’s history is worthy of study by itself. In this chapter, we’ll explore AI’s tumultuous history and also provide a summary introduction to each of the chapters of this book. WHAT IS INTELLIGENCE? To build software that is deemed intelligent, it’s helpful to begin with a definition of intelligence. Intelligence can be simply defined as a set of properties of the mind. These properties include the ability to plan, solve problems, and in general, reason. A simpler definition could be that intelligence is the ability to make the right decision given a set of inputs and a variety of possible actions. Using this simple definition of intelligence (making the right decision), we can apply this not only to humans, but also to animals that exhibit rational behavior. But the intelligence that is exhibited by human beings is much more complex than that of animals. For example, humans have the ability
Page 20
2 Artificial Intelligence to communicate with language, but so do some animals. Humans can also solve problems, but the same can be said of some animals. One difference then is that humans embody many aspects of intelligence (the ability to communicate, solve problems, learn and adapt) where animals typically embody a small number of intelligent characteristics, and usually at a much lower level than humans. We can use the same analogy on AI applied to computer systems. For example, it’s possible to build an application that plays a world-class game of Chess, but this program knows nothing of the game of Checkers, nor how to make a good cup of tea. A data mining application can help identify fraud, but can’t navigate a complex environment. From this perspective, the most complex and intelligent applications can be deemed intelligent from one perspective, but lack even the simplest intelligence that can be seen in the least intelligent of animals. NOTE Famed author Isaac Asimov once wrote about his experience with aptitude tests in the army. In the army, he scored well above the norm. But what he realized was that he could score well on tests that were developed by others that shared his academic bents. He opined that if the tests were developed by people involved in auto repair, he would have scored very poorly. The issue being that tests are developed around a core of expertise, and scoring poorly on one doesn’t necessarily indicate a lack of intelligence. THE SEARCH FOR MECHANICAL INTELLIGENCE History is filled with stories of the creation of intelligent machines. In the 800s BC, the Iliad described the winged Talos, a bronze automaton forged by Hephaestus to protect Crete. The inner workings of Talos weren’t described, except that he was bronze, and filled with ichor (or a Greek god’s blood). A more recent example is Mary Shelley’s Frankenstein, in which the scientist recreates life from old. In 1921, Karel Capek’s play “Rossum’s Universal Robots” introduced the concept of cheap labor through robotics. But one of the most interesting applications of artificial intelligence, in a non-robitic form, was that of the HAL 9000 introduced by Arthur C. Clark in his his novel “2001: A Space Odyssey.” HAL was a sentient artificial intelligence that occupied the Discovery spaceship (en route to Jupiter). HAL had no physical form, but instead managed the spaceship’s systems, visually watched the human occupants through a network of cameras, and
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !