Artificial intelligence : structures and strategies for complex problem solving / George F. Luger.

Includes bibliographical references (pages 705-733) and indexes.

Summary Already in its fifth edition, thanks to artificial intelligence (AI) being one of the most volatile fields in computer science, this text is designed for the classroom as well as a reference tool. Luger (computer science, linguistics, and technology, U. of New Mexico) describes the aspects of AI, including representation and search (including the predicate calculus, and heuristic and stochastic search methods), representation and intelligence (including knowledge-intensive and strong methods), machine learning (symbol- based, connectionist, social and emergent), problem solving (automated reasoning and natural language), language and programming techniques, and a closing essay on AI as empirical inquiry. Luger includes exercises and references for each chapter.

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 pages vii Publisher's Acknowledgements pages xv Part I Artificial Intelligence: Its Roots and Scope pages 1 1 Al: History and Applications pages 3 1.1 From Eden to ENIAC: Attitudes toward Intelligence, Knowledge, and Human Artifice pages 3 1.2 Overview of AI Application Areas pages 17 1.3 Artificial Intelligence--A Summary pages 28 1.4 Epilogue and References pages 29 1.5 Exercises pages 31 Part II Artificial Intelligence as Representation and Search pages 33 2 The Predicate Calculus pages 47 2.0 Introduction pages 47 2.1 The Propositional Calculus pages 47 2.2 The Predicate Calculus pages 52 2.3 Using Inference Rules to Produce Predicate Calculus Expressions pages 64 2.4 Application: A Logic-Based Financial Advisor pages 75 2.5 Epilogue and References pages 79 2.6 Exercises pages 79 3 Structures and Strategies for State Space Search pages 81 3.0 Introduction pages 81 3.1 Graph Theory pages 84 3.2 Strategies for State Space Search pages 93 3.3 Using the State Space to Represent Reasoning with the Predicate Calculus pages 107 3.4 Epilogue and References pages 121 3.5 Exercises pages 121 4 Heuristic Search pages 123 4.0 Introduction pages 123 4.1 An Algorithm for Heuristic Search pages 127 4.2 Admissibility, Monotonicity, and Informedness pages 139 4.3 Using Heuristics in Games pages 144 4.4 Complexity Issues pages 152 4.5 Epilogue and References pages 156 4.6 Exercises pages 156 5 Control and Implementation of State Space Search pages 159 5.0 Introduction pages 159 5.1 Recursion-Based Search pages 160 5.2 Pattern-Directed Search pages 164 5.3 Production Systems pages 171 5.4 The Blackboard Architecture for Problem Solving pages 187 5.5 Epilogue and References pages 189 5.7 Exercises pages 190 Part III Representation and Intelligence: The AI Challenge pages 193 6 Knowledge Representation pages 197 6.0 Issues in Knowledge Representation pages 197 6.1 A Brief History of AI Representational Systems pages 198 6.2 Conceptual Graphs: A Network Language pages 218 6.3 Alternatives to Explicit Representation pages 228 6.4 Agent Based and Distributed Problem Solving pages 235 6.5 Epilogue and References pages 240 6.6 Exercises pages 243 7 Strong Method Problem Solving pages 247 7.0 Introduction pages 247 7.1 Overview of Expert System Technology pages 249 7.2 Rule-Based Expert Systems pages 256 7.3 Model-Based, Case Based, and Hybrid Systems pages 268 7.4 Planning pages 284 7.5 Epilogue and References pages 299 7.6 Exercises pages 301 8 Reasoning in Uncertain Situations pages 303 8.0 Introduction pages 303 8.1 Logic-Based Abductive Inference pages 305 8.2 Abduction: Alternatives to Logic pages 320 8.3 The Stochastic Approach to Uncertainty pages 333 8.4 Epilogue and References pages 344 8.5 Exercises pages 346 Part IV Machine Learning pages 349 9 Machine Learning: Symbol-based pages 351 9.0 Introduction pages 603 9.1 A Framework for Symbol-based Learning pages 354 9.2 Version Space Search pages 360 9.3 The ID3 Decision Tree Induction Algorithm pages 372 9.4 Inductive Bias and Learnability pages 381 9.5 Knowledge and Learning pages 386 9.6 Unsupervised Learning pages 397 9.7 Reinforcement Learning pages 406 9.8 Epilogue and References pages 413 9.9 Exercises pages 414 10 Machine Learning: Connectionist pages 417 10.0 Introduction pages 417 10.1 Foundations for Connectionist Networks pages 419 10.2 Perceptron Learning pages 422 10.3 Backpropagation Learning pages 431 10.4 Competitive Learning pages 438 10.5 Hebbian Coincidence Learning pages 446 10.6 Attractor Networks or "Memories" pages 457 10.7 Epilogue and References pages 467 10.8 Exercises pages 468 11 Machine Learning: Social and Emergent pages 469 11.0 Social and Emergent Models of Learning pages 469 11.1 The Genetic Algorithm pages 471 11.2 Classifier Systems and Genetic Programming pages 481 11.3 Artificial Life and Society-Based Learning pages 492 11.4 Epilogue and References pages 503 11.5 Exercises pages 504 Part V Advanced Topics for AI Problem Solving pages 507 12 Automated Reasoning pages 509 12.0 Introduction to Weak Methods in Theorem Proving pages 509 12.1 The General Problem Solver and Difference Tables pages 510 12.2 Resolution Theorem Proving pages 516 12.3 PROLOG and Automated Reasoning pages 537 12.4 Further Issues in Automated Reasoning pages 543 12.5 Epilogue and References pages 550 12.6 Exercises pages 551 13 Understanding Natural Language pages 553 13.0 Role of Knowledge in Language Understanding pages 553 13.1 Deconstructing Language: A Symbolic Analysis pages 556 13.2 Syntax pages 559 13.3 Syntax and Knowledge with ATN Parsers pages 568 13.4 Stochastic Tools for Language Analysis pages 578 13.5 Natural Language Applications pages 585 13.6 Epilogue and References pages 592 13.7 Exercises pages 557 Part VI Languages and Programming Techniques for Artificial Intelligence pages 597 14 An Introduction to Prolog pages 603 14.0 Introduction pages 603 14.1 Syntax for Predicate Calculus Programming pages 604 14.2 Abstract Data Types (ADTs) in PROLOG pages 616 14.3 A Production System Example in PROLOG pages 620 14.4 Designing Alternative Search Strategies pages 625 14.5 A PROLOG Planner pages 630 14.6 PROLOG: Meta-Predicates, Types, and Unification pages 633 14.7 Meta-Interpreters in PROLOG pages 641 14.8 Learning Algorithms in PROLOG pages 656 14.9 Natural Language Processing in PROLOG pages 666 14.10 Epilogue and References pages 673 14.11 Exercises pages 676 15 An Introduction to LISP pages 679 15.0 Introduction pages 679 15.1 LISP: A Brief Overview pages 680 15.2 Search in LISP: A Functional Approach to the Farmer, Wolf, Goat, and Cabbage Problem pages 702 15.3 Higher-Order Functions and Procedural Abstraction pages 707 15.4 Search Strategies in LISP pages 711 15.5 Pattern Matching in LISP pages 715 15.6 A Recursive Unification Function pages 717 15.7 Interpreters and Embedded Languages pages 721 15.8 Logic Programming in LISP pages 723 15.9 Streams and Delayed Evaluation pages 732 15.10 An Expert System Shell in LISP pages 736 15.11 Semantic Networks and Inheritance in LISP pages 743 15.12 Object-Oriented Programming Using CLOS pages 747 15.13 Learning in LISP: The ID3 Algorithm pages 759 15.14 Epilogue and References pages 771 15.15 Exercises pages 772 Part VII Epilogue pages 777 16 Artificial Intelligence as Empirical Enquiry pages 779 16.0 Introduction pages 779 16.1 Artificial Intelligence: A Revised Definition pages 781 16.2 The Science of Intelligent Systems pages 792 16.3 AI: Current Issues and Future Directions pages 803 16.4 Epilogue and References pages 807 Bibliography pages 809 Author Index pages 837 Subject Index pages 843

In this accessible, comprehensive text, George Luger captures the essence of artificial intelligence-solving the complex problems that arise wherever computer technology is applied. Key representation techniques including logic, semantic and connectionist networks, graphical models, and many more are introduced. Presentation of agent technology and the use of ontologies are added. A new machine-learning chapter is based on stochastic methods, including first-order Bayesian networks, variants of hidden Markov models, inference with Markov random fields and loopy belief propagation. A new presentation of parameter fitting with expectation maximization learning and structure learning using Markov chain Monte Carlo sampling. Use of Markov decision processes in reinforcement learning. Natural language processing with dynamic programming (the Earley parser) and other probabilistic parsing techniques including Viterbi, are added. A new supplemental programming book is available online and in print: "AI Algorithms in Prolog, Lisp and Java (TM). "References and citations are updated throughout the Sixth Edition. For all readers interested in artificial intelligence