Introduction to Artificial Intelligence

In the chapters in Part I of this textbook the author introduces the fundamental ideas of artificial intelligence and computational intelligence. In Part II he explains key AI methods such as search, evolutionary computing, logic-based reasoning, knowledge representation, rule-based systems, pattern recognition, neural networks, and cognitive architectures. Finally, in Part III, he expands the context to discuss theories of intelligence in philosophy and psychology, key applications of AI systems, and the likely future of artificial intelligence. A key feature of the author's approach is historical and biographical footnotes, stressing the multidisciplinary character of the field and its pioneers. The book is appropriate for advanced undergraduate and graduate courses in computer science, engineering, and other applied sciences, and the appendices offer short formal, mathematical models and notes to support the reader. Preface 5 Acknowledgments 6 Contents 7 Part I Fundamental Ideas of Artificial Intelligence 11 1 History of Artificial Intelligence 12 2 Symbolic Artificial Intelligence 23 2.1 Cognitive Simulation 24 2.2 Logic-Based Approach 25 2.3 Rule-Based Knowledge Representation 27 2.4 Structural Knowledge Representation 27 2.5 Mathematical Linguistics Approach 29 3 Computational Intelligence 31 3.1 Connectionist Models 31 3.2 Mathematics-Based Models 33 3.3 Biology-Based Models 35 Part II Artificial Intelligence Methods 36 4 Search Methods 37 4.1 State Space and Search Tree 37 4.2 Blind Search 41 4.3 Heuristic Search 44 4.4 Adversarial Search 47 4.5 Search for Constraint Satisfaction Problems 50 4.6 Special Methods of Heuristic Search 55 5 Evolutionary Computing 58 5.1 Genetic Algorithms 58 5.2 Evolution Strategies 63 5.3 Evolutionary Programming 66 5.4 Genetic Programming 68 5.5 Other Biology-Inspired Models 71 6 Logic-Based Reasoning 72 6.1 World Description with First-Order Logic 73 6.2 Reasoning with the Resolution Method 77 6.3 Methods of Transforming Formulas into Normal Forms 81 6.4 Special Forms of FOL Formulas in Reasoning Systems 83 6.5 Reasoning as Symbolic Computation 85 7 Structural Models of Knowledge Representation 95 7.1 Semantic Networks 96 7.2 Frames 99 7.3 Scripts 102 8 Syntactic Pattern Analysis 106 8.1 Generation of Structural Patterns 107 8.2 Analysis of Structural Patterns 111 8.3 Interpretation of Structural Patterns 117 8.4 Induction of Generative Grammars 121 8.5 Graph Grammars 123 9 Rule-Based Systems 128 9.1 Model of Rule-Based Systems 128 9.2 Reasoning Strategies in Rule-Based Systems 130 9.3 Conflict Resolution and Rule Matching 139 9.4 Expert Systems Versus Rule-Based Systems 140 10 Pattern Recognition and Cluster Analysis 143 10.1 Problem of Pattern Recognition 144 10.2 Minimum Distance Classifier 146 10.3 Nearest Neighbor Method 147 10.4 Decision-Boundary-Based Classifiers 148 10.5 Statistical Pattern Recognition 150 10.6 Decision Tree Classifier 153 10.7 Cluster Analysis 155 11 Neural Networks 159 11.1 Artificial Neuron 160 11.2 Basic Structures of Neural Networks 169 11.3 Concise Survey of Neural Network Models 173 12 Reasoning with Imperfect Knowledge 177 12.1 Bayesian Inference and Bayes Networks 177 12.2 Dempster-Shafer Theory 185 12.3 Non-monotonic Reasoning 187 13 Defining Vague Notions in Knowledge-Based Systems 191 13.1 Model Based on Fuzzy Set Theory 192 13.2 Model Based on Rough Set Theory 199 14 Cognitive Architectures 204 14.1 Concept of Agent 205 14.2 Multi-agent Systems 208 Part III Selected Issues in Artificial Intelligence 212 15 Theories of Intelligence in Philosophy and Psychology 213 15.1 Mind and Cognition in Epistemology 213 15.2 Models of Intelligence in Psychology 218 16 Application Areas of AI Systems 223 16.1 Perception and Pattern Recognition 223 16.2 Knowledge Representation 224 16.3 Problem Solving 226 16.4 Reasoning 226 16.5 Decision Making 227 16.6 Planning 228 16.7 Natural Language Processing (NLP) 229 16.8 Learning 230 16.9 Manipulation and Locomotion 232 16.10 Social Intelligence, Emotional Intelligence and Creativity 233 17 Prospects of Artificial Intelligence 235 17.1 Issues of Artificial Intelligence 235 17.2 Potential Barriers and Challenges in AI 240 17.3 Determinants of AI Development 243 Appendix A Formal Models for Artificial Intelligence Methods: Formal Notions for Search Methods 246 Appendix B Formal Models for Artificial Intelligence Methods: Mathematical Foundations of Evolutionary Computation 249 Appendix C Formal Models for Artificial Intelligence Methods: Selected Issues of Mathematical Logic 254 Appendix D Formal Models for Artificial Intelligence Methods: Foundations of Description Logics 263 Appendix E Formal Models for Artificial Intelligence Methods: Selected Notions of Formal Language Theory 267 Appendix F Formal Models for Artificial Intelligence Methods: Theoretical Foundations of Rule-Based Systems 275 Appendix G Formal Models for Artificial Intelligence Methods: Mathematical Similarity Measures for Pattern Recognition 281 Appendix H Formal Models for Artificial Intelligence Methods: Mathematical Model of Neural Network Learning 285 Appendix I Formal Models for Artificial Intelligence Methods: Mathematical Models for Reasoning Under Uncertainty 289 Appendix J Formal Models for Artificial Intelligence Methods: Foundations of Fuzzy Set and Rough Set Theories 293 Bibliography 297 Index 308 Front Matter....Pages i-x Front Matter....Pages 1-1 History of Artificial Intelligence....Pages 3-13 Symbolic Artificial Intelligence....Pages 15-22 Computational Intelligence....Pages 23-27 Front Matter....Pages 29-29 Search Methods....Pages 31-51 Evolutionary Computing....Pages 53-66 Logic-Based Reasoning....Pages 67-89 Structural Models of Knowledge Representation....Pages 91-101 Syntactic Pattern Analysis....Pages 103-124 Rule-Based Systems....Pages 125-139 Pattern Recognition and Cluster Analysis....Pages 141-156 Neural Networks....Pages 157-174 Reasoning with Imperfect Knowledge....Pages 175-188 Defining Vague Notions in Knowledge-Based Systems....Pages 189-201 Cognitive Architectures....Pages 203-210 Front Matter....Pages 211-211 Theories of Intelligence in Philosophy and Psychology....Pages 213-222 Application Areas of AI Systems....Pages 223-234 Prospects of Artificial Intelligence....Pages 235-245 Back Matter....Pages 247-321