Artificial intelligence : theory and practice / Thomas Dean, James Allen, Yiannis Aloimonos.

CONTENIDO
1 INTRODUCTION 1
Robot Explorers, 2
1.1 Artificial Intelligence in Practice 3
Examples of Artificial Intelligence Systems, 4
1.2 Artificial Intelligence Theory 5
Examples of Artificial Intelligence Theory, 6
1.3 Identifying and Measuring Intelligence
1.4 Computational Theories of Behavior 9
Representation, 10
Syntax and Semantics, 11
1.5 Automated Reasoning 12
Inference and Symbolic Manipulation, 13
Representing Common-Sense Knowledge, 14
Combinatorial Problems and Search, 14
Complexity and Expressivity, 15
1.6 How This Book Is Organized 16
2 SYMBOLIC PROGRAMMING 23
2.1 Rule-Based Reactive System Example 25
Representing Sensors and Sensor Values as Symbols, 26
2.2 Introduction to Lisp 27
Language Requirements,27
Common Lisp, 27
Lists and Lisp Syntax, 28
Symbols, 28
Programs and Documentation, 28
2.3 Interacting with Lisp 29
The Lisp Interpreter, 29
2.4 Functions in Lisp 31
Function Invocation, 31
Procedural Abstraction, 32
Conditional Statements, 33
Recursive Functions, 35
Evaluating Functions in Files, 35
2.5 Environments, Symbols, and Scope 36
Assigning Values to Symbols, 36
Eval and Apply Revisited, 37
Structured Environments, 38
Variables, 39
Lexical Scoping, 40
2.6 More on Functions 42
Functions with Local State, 42
Lambda and Functions as Arguments, 43
2.7 List Processing 44
Suspending Evaluation Using Quote, 44
Building and Accessing Elements in Lists, 45
Lists in Memory, 45
Modifying List Structures in Memory, 46
Alternative Parameter-Passing Conventions, 47
Predicates on Lists, 48
Built-In List Manipulation Functions, 48
Optional Arguments, 49
List-Processing Examples, 49
Data Abstraction, 51
2.8 Iterative Constructs 53
Mapping Functions to Arguments, 53
General Iteration, 54
Simple Iteration, 55
2.9 Monitoring and Debugging Programs 56
Tracing and Stepping Through Programs, 56
Formatted Output, 58
2.10 Rule-Based Reactive System Revisited 58
3 REPRESENTATION AND LOGIC 71
3.1 Propositional Logic 73
Syntax for P, 74
Semantics for P, 75
3.2 Formal System for/v 76
Logical Axioms of P, 77
Normal Forms, 78
Rules of Inference, 79
Proofs and Theorems, 79
Resolution Rule of Inference, 80
Completeness, Soundness, and Decidability, 81
Computational Complexity, 82
Solving Problems with Logic, 82
3.3 Automated Theorem Proving in P 84
Goal Reduction in P, 85
Proof by Contradiction, 87
3.4 Predicate Calculus 88
Syntax for PC, 89
Translating English Sentences into Logic, 90
More About Quantification, 91
Semantics for PC, 91
3.5 Formal System for PC 93
Specifying Programs in Prolog, 94
Eliminating Quantifiers, 94
Learning and Deductive Inference, 96
Decidability, 98
3.6 Automated Theorem Proving in PC 99
Matching and Universal Instantiation, 99
Goal Reduction in PC, 101
Unification, 103
Concept Description Languages, 107
Semantic Networks, 108
3.7 Nonmonotonic Logic 109
Closed-World Assumption, 109
Abductive and Default Reasoning, 111
Minimal Models, 112
3.8 Deductive Retrieval Systems 113
Forward and Backward Chaining, 114
Reason Maintenance Systems, 116
Nonmonotonic Data Dependencies, 118
Lisp Implementation: Data Dependencies 127
4 SEARCH 131
4.1 Basic Search Issues 133
Search Spaces and Operators, 134
Appliance Assembly Example, 135
Exploiting Structure to Expedite Search, 136
4.2 Blind Search 137
Depth-First Search, 138
Depth-First Search Is Space Efficient, 139
Breadth-First Search, 140
Breadth-First Search Is Guaranteed, 141
Iterative-Deepening Search, 141
Iterative-Deepening Search Is Asymptotically Optimal, 143
Searching in Graphs, 144
4.3 Heuristic Search 144
Best-First Search, 145
Admissible Evaluation Functions, 146
4.4 Optimization and Search 149
Hill-Climbing Search, 149
Local Minima and Maxima, 151
Gradient Search, 153
Simulated Annealing, 153
Simulated Evolution and Genetic Algorithms, 154
Application to Vehicle Routing, 158
4.5 Adversary Search 160
Minimax Search, 160
a-B Search, 163
4.6 Indexing in Discrimination Trees 166
Storing and Retrieving Predicate Calculus Formulas, 167
Decision Trees, 168
Lisp Implementation: Discrimination Trees 174
5 LEARNING 179
5.1 Classifying Inductive Learning Problems 180
Supervised Learning, 180
Classification and Concept Learning, 182
Unsupervised Learning, 183
Online and Batch Learning Methods, 183
5.2 Theory of Inductive Inference 183
The Role of Inductive Bias, 184
Restricted Hypothesis Space Biases, 184
Preference Biases, 185
Probably Approximately Correct Learning, 186
PAC Learnable Concept Classes, 187
Finding Consistent Hypotheses, 188
5.3 Version Spaces 188
Attributes, Features, and Dimensions, 189
Specializing and Generalizing Concepts, 190
Maintaining Version-Space Boundaries, 191
Data Structures for Learning, 192
Implementing the Version-Space Method, 194
Optimal Method for Conjunctions of Positive Literals, 195
5.4 Decision Trees 195
Implementing a Preference for Small Decision Trees, 196
Disorder and Information Theory, 199
Decision Trees in Practice, 202
5.5 Network Learning Methods 202
Model for Computation in Biological Systems, 203
Adjustable Weights and Restricted Hypothesis Spaces, 205
5.6 Gradient Guided Search 206
Searching in Linear Function Spaces, 207
Experimental Validation, 208
Nonlinear Function Spaces and Artificial Neural Networks, 210
Deriving the Gradient for Multilayer Networks, 211
Error Backpropagation Procedure, 212
Implementing Artificial Neural Networks in Lisp, 214
Representational and Computational Issues, 217
Networks with Adjustable Thresholds, 218
Comparing the Performance of Different Networks, 220
5.7 Perceptrons 221
Perceptron Learning Rule, 222
Linearly Separable Functions, 223
5.8 Radial Basis Functions 224
Approximating Functions by Combining Gaussians, 225
Two-Step Strategy for Adjusting Weights, 227
Functions with Multidimensional Input Spaces, 230
5.9 Learning in Dynamic Environments 231
Reinforcement Learning. 231
Computing an Optimal Policy, 235
Online Methods for Learning Value Functions, 235
Learning by Exploration, 239
Lisp Implementation: Learning Algorithms 249
6 ADVANCED REPRESENTATION 255
6.1 Temporal Reasoning 256
6.2 The Situation Calculus 257
Constraining Fluents in Situations, 260
Frame Problem, 260
Qualification Problem, 262
6.3 First-Order Interval Temporal Logic 264
Syntax for the Interval Logic, 265
Representing Change in the Interval Logic, 267
Semantics for the Interval Logic, 268
6.4 Managing Temporal Knowledge 269
6.5 Knowledge and Belief 273
Possible-Worlds Semantics, 277
6.6 Spatial Reasoning 279
Representing Spatial Knowledge, 279
Planning Paths in Configuration Space, 281
Path Planning as Graph Search, 282
Locally Distinctive Places, 285
Lisp Implementation: Temporal Reasoning 291
7 PLANNING 297
7.1 State-Space Search 298
What is Planning?, 298
Planning as Search, 300
Representing and Solving Search Problems, 301
State Progression, 3O2
Goal Regression, 303
Means/Ends Analysis, 303
Machine Assembly Example, 305
Operant Schemas, 306
Block-Stacking Problems, 307
7.2 Least Commitment Planning 308
Search in the Space of Partially Ordered Plans, 309
Sound, Complete, and Systematic Search, 312
Block-Stacking Example, 313
Recognizing and Resolving Conflicts, 316
Variables in Partially Ordered Plans, 317
7.3 Planning in a Hierarchy of Abstraction Spaces 320
Analysis of Planning with levels of Abstraction, 321
Towers-of-Hanoi Problems, 322
Task Reduction Planning, 325
7.4 Adapting Previously Generated Plans 326
Indexing, Retrieving, and Adapting Plans, 326
Analysis of Adaptive Planning, 331
7.5 Planning with Incomplete Information 332
The Copier-Repair Problem, 332
Generating Conditional Plans, 335
Contexts Represent Possible Sets of Observations, 336
7.6 More Expressive Models of Action 340
Conditional Effects, 341
Disjunctive Preconditions, 342
Universally Quantified Effects, 343
Wandering Briefcase Example, 344
Processes Outside the Planner's Control, 345
Lisp Implementation: Refining Partially Ordered Plans 351
8 UNCERTAINTY 355
8.1 Motivation for Reasoning Under Uncertainty 357
Sources of Uncertainty, 357
Representing Uncertain Knowledge, 357
Applications Involving Uncertainty, 358
8.2 Probability Theory 359
Frequency Interpretation of Probability, 359
Save Interpretation of Probability, 359
Degrees of Belief, 360
Random Variables and Distributions, 361
Conditional Probability, 362
Calculus for Combining Probabilities, 364
Conditional Independence, 366
Maintaining Consistency, 367
8.3 Probabilistic Networks 368
Graphical Models, 369
Path-Based Characterization of Independence, 371
Quantifying Probabilistic Networks, 372
Inference in Probabilistic Networks, 373
Exact Inference in Tree-Structured Networks, 374
Propagating Evidence in Trees, 378
Exact Inference in Singly Connected Networks, 380
Approximate Inference Using Stochastic Simulation, 382
Likelihood-Weighting Algorithm, 384
Probabilistic Reasoning in Medicine, 386
8.4 Decision Theory 388
Preferences and Utilities, 389
Decision Tree Methods, 390
Computing the Value of Information, 393
Automated Decision Making in Medicine, 394
Lisp Implementation: Inference in Probabilistic Networks 399
9 IMAGE UNDERSTANDING 409
9.1 Sensors and Images 410
Digital Images, 410
Noise in Image Processing, 410
9.2 Computer Vision 412
Understanding Images, 413
Vision Versus Thought, 414
9.3 Human Vision 415
Transferring Information from the Eye to the Brain, 415
Compressing Visit Information, 417
9.4 Vision as a Recovery Problem 418
What to Recover, 420
Geometric Aspects of Image Formation, 420
Perspective Projection, 420
Orthographic Projection, 423
Paraperspective Projection, 425
Shape Representation, 426
Surface Orientation and Shape Under Perspective, 426
Surface Orientation and Shape Under Orthography, 426
Stereographic Projection, 427
Geometric Properties of the Perspective Projection, 427
Imaging with tenses, 430
Photometric Aspects of Image Formation, 430
9.5 Recovery of Image Descriptions 431
Edge Detection, 431
Differentiation Approaches, 432
Model-Based Approaches, 436
Edge Grouping and Hough Transform, 437
Image Segmentation, 438
9.6 Shape from Contour 440
Qualitative Analysis Using Edge Labels, 441
Quantitative Analysis Using Skewed Symmetries, 442
9.7 Shape from Shading 444
Reflectance Maps, 445
Solving Ill-Posed Problems, 448
Photometric Stereo, 449
9.8 Shape from Texture 450
Density of Textural Elements, 450
Textural Reflectance Maps, 451
9.9 Stereo 453
Addressing the Correspondence Problem, 453
Intensity-Based Matching, 455
Edge-Based Matching, 456
9.10 Analysis of Visual Motion 457
Motion Fields, 458
Motion Field Estimation, 460
Motion Field Interpretation, 463
9.11 Active Vision 465
9.12 Applications 466
Autonomous Vehicle Navigation, 467
Object Recognition, 469
Lisp Implementation: Labeling Polyhedral Scenes 482
10 NATURAL LANGUAGE PROCESSING 489
10.1 Components of Language 491
Content and Function Words, 491
Structure of Phrases, 492
10.2 Context-Free Grammars 493
Parsing, 495
10.3 Parsing Context-Free Grammars 496
Exploiting the Lexicon, 498
Building a Parse Tree, 499
10.4 Grammars Involving Features 502
Matching with Features, 505
10.5 Efficient Parsing with Charts 507
Ambiguous Sentences, 507
10.6 Semantic Interpretation 511
Word Senses, 512
Semantic Interpretation Using Features, 515
Disambiguating Word Senses, 517
10.7 Generating Natural Language 519
10.8 Natural Language in Context 521
Speech Acts, 521
Establishing Reference, 522
Handling Database Assertions and Queries, 524
10.9 Quantifier Scoping 529
Lisp Implementation: Simple Parser 533