Artificial Intelligence : Structures and Strategies for Complex Problem Solving

by Luger, George F.

• ISBN13: 9780201648669
• ISBN10: 0201648660
• Edition: 4th
• Format: Hardcover
• Copyright: 2002-01-01
• Publisher: Addison Wesley

Summary

Much has changed since the early editions of Artificial Intelligence were published. To reflect this the introductory material of this fifth edition has been substantially revised and rewritten to capture the excitement of the latest developments in AI work. Artificial intelligence is a diverse field. To ask the question "what is intelligence?" is to invite as many answers as there are approaches to the subject of artificial intelligence. These could be intelligent agents, logical reasoning, neural networks, expert systems, evolutionary computing and so on. This fifth edition covers all the main strategies used for creating computer systems that will behave in "intelligent" ways. It combines the broadest approach of any text in the marketplace with the practical information necessary to implement the strategies discussed, showing how to do this through Prolog or LISP programming.

Author Biography

George Luger is currently a Professor of Computer Science, Linguistics, and Psychology at the University of New Mexico in Albuquerque

Table of Contents

Preface	p. vii
Publisher's Acknowledgements	p. xv
Artificial Intelligence: Its Roots and Scope	p. 1
Al: History and Applications	p. 3
From Eden to ENIAC: Attitudes toward Intelligence, Knowledge, and Human Artifice	p. 3
Overview of AI Application Areas	p. 17
Artificial Intelligence--A Summary	p. 28
Epilogue and References	p. 29
Exercises	p. 31
Artificial Intelligence as Representation and Search	p. 33
The Predicate Calculus	p. 47
Introduction	p. 47
The Propositional Calculus	p. 47
The Predicate Calculus	p. 52
Using Inference Rules to Produce Predicate Calculus Expressions	p. 64
Application: A Logic-Based Financial Advisor	p. 75
Epilogue and References	p. 79
Exercises	p. 79
Structures and Strategies for State Space Search	p. 81
Introduction	p. 81
Graph Theory	p. 84
Strategies for State Space Search	p. 93
Using the State Space to Represent Reasoning with the Predicate Calculus	p. 107
Epilogue and References	p. 121
Exercises	p. 121
Heuristic Search	p. 123
Introduction	p. 123
An Algorithm for Heuristic Search	p. 127
Admissibility, Monotonicity, and Informedness	p. 139
Using Heuristics in Games	p. 144
Complexity Issues	p. 152
Epilogue and References	p. 156
Exercises	p. 156
Control and Implementation of State Space Search	p. 159
Introduction	p. 159
Recursion-Based Search	p. 160
Pattern-Directed Search	p. 164
Production Systems	p. 171
The Blackboard Architecture for Problem Solving	p. 187
Epilogue and References	p. 189
Exercises	p. 190
Representation and Intelligence: The AI Challenge	p. 193
Knowledge Representation	p. 197
Issues in Knowledge Representation	p. 197
A Brief History of AI Representational Systems	p. 198
Conceptual Graphs: A Network Language	p. 218
Alternatives to Explicit Representation	p. 228
Agent Based and Distributed Problem Solving	p. 235
Epilogue and References	p. 240
Exercises	p. 243
Strong Method Problem Solving	p. 247
Introduction	p. 247
Overview of Expert System Technology	p. 249
Rule-Based Expert Systems	p. 256
Model-Based, Case Based, and Hybrid Systems	p. 268
Planning	p. 284
Epilogue and References	p. 299
Exercises	p. 301
Reasoning in Uncertain Situations	p. 303
Introduction	p. 303
Logic-Based Abductive Inference	p. 305
Abduction: Alternatives to Logic	p. 320
The Stochastic Approach to Uncertainty	p. 333
Epilogue and References	p. 344
Exercises	p. 346
Machine Learning	p. 349
Machine Learning: Symbol-based	p. 351
Introduction	p. 603
A Framework for Symbol-based Learning	p. 354
Version Space Search	p. 360
The ID3 Decision Tree Induction Algorithm	p. 372
Inductive Bias and Learnability	p. 381
Knowledge and Learning	p. 386
Unsupervised Learning	p. 397
Reinforcement Learning	p. 406
Epilogue and References	p. 413
Exercises	p. 414
Machine Learning: Connectionist	p. 417
Introduction	p. 417
Foundations for Connectionist Networks	p. 419
Perceptron Learning	p. 422
Backpropagation Learning	p. 431
Competitive Learning	p. 438
Hebbian Coincidence Learning	p. 446
Attractor Networks or "Memories"	p. 457
Epilogue and References	p. 467
Exercises	p. 468
Machine Learning: Social and Emergent	p. 469
Social and Emergent Models of Learning	p. 469
The Genetic Algorithm	p. 471
Classifier Systems and Genetic Programming	p. 481
Artificial Life and Society-Based Learning	p. 492
Epilogue and References	p. 503
Exercises	p. 504
Advanced Topics for AI Problem Solving	p. 507
Automated Reasoning	p. 509
Introduction to Weak Methods in Theorem Proving	p. 509
The General Problem Solver and Difference Tables	p. 510
Resolution Theorem Proving	p. 516
PROLOG and Automated Reasoning	p. 537
Further Issues in Automated Reasoning	p. 543
Epilogue and References	p. 550
Exercises	p. 551
Understanding Natural Language	p. 553
Role of Knowledge in Language Understanding	p. 553
Deconstructing Language: A Symbolic Analysis	p. 556
Syntax	p. 559
Syntax and Knowledge with ATN Parsers	p. 568
Stochastic Tools for Language Analysis	p. 578
Natural Language Applications	p. 585
Epilogue and References	p. 592
Exercises	p. 557
Languages and Programming Techniques for Artificial Intelligence	p. 597
An Introduction to Prolog	p. 603
Introduction	p. 603
Syntax for Predicate Calculus Programming	p. 604
Abstract Data Types (ADTs) in PROLOG	p. 616
A Production System Example in PROLOG	p. 620
Designing Alternative Search Strategies	p. 625
A PROLOG Planner	p. 630
PROLOG: Meta-Predicates, Types, and Unification	p. 633
Meta-Interpreters in PROLOG	p. 641
Learning Algorithms in PROLOG	p. 656
Natural Language Processing in PROLOG	p. 666
Epilogue and References	p. 673
Exercises	p. 676
An Introduction to LISP	p. 679
Introduction	p. 679
LISP: A Brief Overview	p. 680
Search in LISP: A Functional Approach to the Farmer, Wolf, Goat, and Cabbage Problem	p. 702
Higher-Order Functions and Procedural Abstraction	p. 707
Search Strategies in LISP	p. 711
Pattern Matching in LISP	p. 715
A Recursive Unification Function	p. 717
Interpreters and Embedded Languages	p. 721
Logic Programming in LISP	p. 723
Streams and Delayed Evaluation	p. 732
An Expert System Shell in LISP	p. 736
Semantic Networks and Inheritance in LISP	p. 743
Object-Oriented Programming Using CLOS	p. 747
Learning in LISP: The ID3 Algorithm	p. 759
Epilogue and References	p. 771
Exercises	p. 772
Epilogue	p. 777
Artificial Intelligence as Empirical Enquiry	p. 779
Introduction	p. 779
Artificial Intelligence: A Revised Definition	p. 781
The Science of Intelligent Systems	p. 792
AI: Current Issues and Future Directions	p. 803
Epilogue and References	p. 807
Bibliography	p. 809
Author Index	p. 837
Subject Index	p. 843
Table of Contents provided by Syndetics. All Rights Reserved.

Excerpts

What we have to learn to do we learn by doing. . . -- ARISTOTLE,Ethics Welcome to the Fourth Edition! I was very pleased to be asked to produce a fourth edition of our artificial intelligence book. It is a compliment to the earlier editions, started more than a decade ago, that our approach to Al has been widely accepted. It is also exciting that, as new developments in the field emerge, we are able to present much of it in each new edition. We thank our readers, colleagues, and students for keeping our topics relevant and presentation up to date. Many sections of the earlier editions have endured remarkably well, including the presentation of logic, search algorithms, knowledge representation, production systems, machine learning, and the programming techniques developed in LISP and PROLOG. These remain central to the practice of artificial intelligence, and required a relatively small effort to bring them up to date. However, several sections, including those on natural language understanding, reinforcement learning, and reasoning under uncertainty, required, and received, extensive reworking. Other topics, such as emergent computation, case-based reasoning, and model-based problem solving, that were treated cursorily in the first editions, have grown sufficiently in importance to merit a more complete discussion. These changes are evidence of the continued vitality of the field of artificial intelligence. As the scope of the project grew, we were sustained by the support of our publisher, editors, friends, colleagues, and, most of all, by our readers, who have given our work such a long and productive life. We were also sustained by our own excitement at the opportunity afforded: Scientists are rarely encouraged to look up from their own, narrow research interests and chart the larger trajectories of their chosen field. Our publisher and readers have asked us to do just that. We are grateful to them for this opportunity. Although artificial intelligence, like most engineering disciplines, must justify itself to the world of commerce by providing solutions to practical problems, we entered the field of AI for the same reasons as many of our colleagues and students: we want to understand and explore the mechanisms of mind that enable intelligent thought and action. We reject the rather provincial notion that intelligence is an exclusive ability of humans, and believe that we can effectively investigate the space of possible intelligences by designing and evaluating intelligent artifacts. Although the course of our careers has given us no cause to change these commitments, we have arrived at a greater appreciation for the scope, complexity, and audacity of this undertaking. In the preface to our earlier editions, we outlined three assertions that we believed distinguished our approach to teaching artificial intelligence. It is reasonable, in writing a preface to this fourth edition, to return to these themes and see how they have endured as our field has grown. The first of these goals was to "unify the diverse branches of AI through a detailed discussion of its theoretical foundations." At the time we adopted that goal, it seemed that the main problem was reconciling researchers who emphasized the careful statement and analysis of formal theories of intelligence (the neats) with those who believed that intelligence itself was some sort of grand hack that could be best approached in an application-driven,ad hocmanner (the scruffies). That simple dichotomy has proven far too simple. In contemporary AI, debates between neats and scruffies have given way to dozens of other debates between proponents of physical symbol systems and students of neural networks, between logicians and designers of artificial life forms that evolve in a most illogical manner, between architects of expert systems and case-based reasoners, and finall