Artificial Intelligence : Structures and Strategies for Complex Problem Solving

by Luger, George F.

• ISBN13: 9780321263186
• ISBN10: 0321263189
• Edition: 6th
• Format: Hardcover
• Copyright: 2009-01-01
• Publisher: Addison Wesley

Summary

[Shelving Category: Artificial Intelligence] "One of the few books on the market that covers all the topics I have included in my course for the past 10 years." Bruce Maxim, University of Michigan Dearborn "The book is a perfect complement to an AI course. It gives the reader both an historical point of view and a practical guide to all the techniques. It is THE book I recommEND as an introduction to this field." Pascal RebreyEND, Dalarna University "Excellent additions and improvements. I will use the 5th EDITION in my introduction and advanced AI courses." Peter Funk, Mtrade;lardalen University "The style of writing and comprehensive treatment of the subject matter makes this a valuable addition to the AI literature." Malachy Eaton, University of Limerick Can machines think like people? This question is the driving force behind Artificial Intelligence, but it is only the starting point of this ever-evolving, exciting discipline. AI uses different strategies to solve the complex problems that arise wherever computer technology is applied, from those areas pertaining to perception and adaptation (neural networks, genetic algorithms) to the fields of intelligent agents, natural language understanding and sTOChastic models. George Luger examines complex problem solving techniques while demonstrating his enthusiasm and excitement for the study of intelligence itself. He shows how to use a number of different software tools and techniques to address the many challenges faced by today's computer scientists. New to this EDITION Brand new chapter which introduces the sTOChastic methodology. ExtENDed material in many sections addresses the continuing importance of agent-based problem solving and embodiment in AI technology. Presentation of issues in natural language understanding, including sections on sTOChastic methods for language comprehension; Markov models; CART trees; mutual information clustering; and statistic based parsing. Further discussion of the AI ENDeavor from the perspectives of philosophy, psychology, and neuro-psychology. Artificial Intelligence: Structures and Strategies for Complex Problem Solving is ideal for a one or two semester university course on AI, as well as an invaluable reference for researchers in the field or practitioners wishing to employ the power of current AI techniques in their work. After receiving his PhD from the University of Pennsylvania,George Lugerspent five years researching and teaching at the Department of Artificial Intelligence of the University of Edinburgh. He is currently a Professor of Computer Science, Linguistics, and Psychology at the University of New Mexico.

Author Biography

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

Table of Contents

Preface	vii
Publisher's Acknowledgements	xvi
PART I ARTIFICIAL INTELLIGENCE: ITS ROOTS AND SCOPE	1	(34)
AI: Early History and Applications	3	(32)
From Eden to ENIAC: Attitudes toward Intelligence, Knowledge, and Human Artifice	3	(17)
Overview of AI Application Areas	20	(10)
Artificial Intelligence---A Summary	30	(1)
Epilogue and References	31	(2)
Exercises	33	(2)
PART II ARTIFICIAL INTELLIGENCE AS REPRESENTATION AND SEARCH	35	(188)
The Predicate Calculus	45	(34)
Introduction	45	(1)
The Propositional Calculus	45	(5)
The Predicate Calculus	50	(12)
Using Inference Rules to Produce Predicate Calculus Expressions	62	(11)
Application: A Logic-Based Financial Advisor	73	(4)
Epilogue and References	77	(1)
Exercises	77	(2)
Structures and Strategies for State Space Search	79	(44)
Introduction	79	(3)
Graph Theory	82	(11)
Strategies for State Space Search	93	(14)
Using the State Space to Represent Reasoning with the Predicate Calculus	107	(14)
Epilogue and References	121	(1)
Exercises	121	(2)
Heuristic Search	123	(42)
Introduction	123	(4)
Hill-Climbing and Dynamic Programming	127	(6)
The Best-First Search Algorithm	133	(12)
Admissibility, Monotonicity, and Informedness	145	(5)
Using Heuristics in Games	150	(7)
Complexity Issues	157	(4)
Epilogue and References	161	(1)
Exercises	162	(3)
Stochastic Methods	165	(28)
Introduction	165	(2)
The Elements of Counting	167	(3)
Elements of Probability Theory	170	(12)
Applications of the Stochastic Methodology	182	(2)
Bayes' Theorem	184	(6)
Epilogue and References	190	(1)
Exercises	191	(2)
Building Control Algorithms for State Space Search	193	(30)
Introduction	193	(1)
Recursion-Based Search	194	(6)
Production Systems	200	(17)
The Blackboard Architecture for Problem Solving	217	(2)
Epilogue and References	219	(1)
Exercises	220	(3)
PART III REPRESENTATION AND INTELLIGENCE: THE AI CHALLENGE	223	(162)
Knowledge Representation	227	(50)
Issues in Knowledge Representation	227	(1)
A Brief History of AI Representational Schemes	228	(20)
Conceptual Graphs: A Network Language	248	(10)
Alternatives to Explicit Representation	258	(7)
Agent-Based and Distributed Problem Solving	265	(5)
Epilogue and References	270	(3)
Exercises	273	(4)
Strong Method Problem Solving	277	(56)
Introduction	277	(2)
Overview of Expert System Technology	279	(7)
Rule-Based Expert Systems	286	(12)
Model-Based, Case-Based, and Hybrid Systems	298	(16)
Planning	314	(15)
Epilogue and References	329	(2)
Exercises	331	(2)
Reasoning in Uncertain Situations	333	(52)
Introduction	333	(2)
Logic-Based Abductive Inference	335	(15)
Abduction: Alternatives to Logic	350	(13)
The Stochastic Approach to Uncertainty	363	(16)
Epilogue and References	379	(2)
Exercises	381	(4)
PART IV MACHINE LEARNING	385	(160)
Machine Learning: Symbol-Based	387	(66)
Introduction	387	(3)
A Framework for Symbol-based Learning	390	(6)
Version Space Search	396	(12)
The ID3 Decision Tree Induction Algorithm	408	(9)
Inductive Bias and Learnability	417	(5)
Knowledge and Learning	422	(11)
Unsupervised Learning	433	(9)
Reinforcement Learning	442	(7)
Epilogue and References	449	(1)
Exercises	450	(3)
Machine Learning: Connectionist	453	(54)
Introduction	453	(2)
Foundations for Connectionist Networks	455	(3)
Perceptron Learning	458	(9)
Backpropagation Learning	467	(7)
Competitive Learning	474	(10)
Hebbian Coincidence Learning	484	(11)
Attractor Networks or ``Memories''	495	(10)
Epilogue and References	505	(1)
Exercises	506	(1)
Machine Learning: Social and Emergent	507	(38)
Social and Emergent Models of Learning	507	(2)
The Genetic Algorithm	509	(10)
Classifier Systems and Genetic Programming	519	(11)
Artificial Life and Society-Based Learning	530	(11)
Epilogue and References	541	(1)
Exercises	542	(3)
PART V ADVANCED TOPICS FOR AI PROBLEM SOLVING	545	(90)
Automated Reasoning	547	(44)
Introduction to Weak Methods in Theorem Proving	547	(1)
The General Problem Solver and Difference Tables	548	(6)
Resolution Theorem Proving	554	(21)
Prolog and Automated Reasoning	575	(6)
Further Issues in Automated Reasoning	581	(7)
Epilogue and References	588	(1)
Exercises	589	(2)
Understanding Natural Language	591	(44)
The Natural Language Understanding Problem	591	(3)
Deconstructing Language: A Symbolic Analysis	594	(3)
Syntax	597	(9)
Syntax and Knowledge with ATN Parsers	606	(10)
Stochastic Tools for Language Analysis	616	(7)
Natural Language Applications	623	(7)
Epilogue and References	630	(2)
Exercises	632	(3)
PART VI LANGUAGES AND PROGRAMMING TECHNIQUES FOR ARTIFICIAL INTELLIGENCE	635	(186)
An Introduction to Prolog	641	(82)
Introduction	641	(1)
Syntax for Predicate Calculus Programming	642	(12)
Abstract Data Types (ADTs) in Prolog	654	(4)
A Production System Example in Prolog	658	(5)
Designing Alternative Search Strategies	663	(5)
A Prolog Planner	668	(3)
Prolog: Meta-Predicates, Types, and Unification	671	(8)
Meta-Interpreters in Prolog	679	(15)
Learning Algorithms in Prolog	694	(10)
Natural Language Processing in Prolog	704	(12)
Epilogue and References	716	(3)
Exercises	719	(4)
An Introduction to Lisp	723	(98)
Introduction	723	(1)
LISP: A Brief Overview	724	(22)
Search in LISP: A Functional Approach to the Farmer, Wolf, Goat, and Cabbage Problem	746	(5)
Higher-Order Functions and Abstraction	751	(4)
Search Strategies in LISP	755	(4)
Pattern Matching in LISP	759	(2)
A Recursive Unification Function	761	(4)
Interpreters and Embedded Languages	765	(2)
Logic Programming in LISP	767	(9)
Streams and Delayed Evaluation	776	(4)
An Expert System Shell in LISP	780	(7)
Semantic Networks and Inheritance in LISP	787	(4)
Object-Oriented Programming Using CLOS	791	(12)
Learning in LISP: The ID3 Algorithm	803	(12)
Epilogue and References	815	(1)
Exercises	816	(5)
PART VII EPILOGUE	821	(34)
Artificial Intelligence as Empirical Enquiry	823	(32)
Introduction	823	(2)
Artificial Intelligence: A Revised Definition	825	(13)
The Science of Intelligent Systems	838	(10)
AI: Current Challenges and Future Directions	848	(5)
Epilogue and References	853	(2)
Bibliography	855	(28)
Author Index	883	(8)
Subject Index	891