Contents
II
Artificial Intelligence
Introduction
1.1 What Is AI?
1.2 The Foundations of Artificial Intelligence
1.3 The History of Artificial Intelligence
1.4 The State of the Art
Intelligent Agents
2.1 Agents and Environments
2.2 Good Behavior: The Concept of Rationality
2.3 The Nature of Environments
2.4 The Structure of Agents
2.5 Summary, Bibliographical and Historical Notes
Problem-solving
Solving Problems by Searching
3.1 Problem-Solving Agents
3.2 Example Problems
3.3 Searching for Solutions
3.4 Uninformed Search Strategies
3.5 Informed (Heuristic) Search Strategies
3.6 Heuristic Functions
3.7 Summary, Bibliographical and Historical Notes
Beyond Classical Search
Exercises
Exercises
Exercises
4.1 Local Search Algorithms and Optimization Problems
4.2 Local Search in Continuous Spaces
4.3 Searching with Nondeterministic Actions
4.4 Searching with Partial Observations
4.5 Online Search Agents and Unknown Environments
4.6 Summary, Bibliographical and Historical Notes
Adversarial Search
5.1 Games
5.2 Optimal Decisions in Games
5.3 Alpha-Beta Pruning
5.4 Imperfect Real-Time Decisions
5.5 Stochastic Games
Xlll
Exercises
Partially Observable Games
State-of-the-Art Game Programs
Alternative Approaches
Summary, Bibliographical and Historical Notes
Constraint Satisfaction Problems
6.1 Defining Constraint Satisfaction Problems
6.2 Constraint Propagation: Inference in CSPs
6.3 Backtracking Search for CSPs
6.4 Local Search for CSPs
6.5 The Structure of Problems
6.6 Summary, Bibliographical and Historical Notes
III Knowledge, reasoning, and planning
Logical Agents
7.1 Knowledge-Based Agents
7.2 The Wumpus World
7.3 Logic
7.4 Propositional Logic: A Very Simple Logic
7.5 Propositional Theorem Proving
7.6 Effective Propositional Model Checking
7.7 Agents Based on Propositional Logic
7.8 Summary, Bibliographical and Historical Notes
First-Order Logic
8.1 Representation Revisited
8.2 Syntax and Semantics of First Order Logic
8.3 Using First-Order Logic
8.4 Knowledge Engineering in First-Order Logic
8.5 Summary, Bibliographical and Historical Notes
Inference in First-Order Logic
9.2 Unification and Lifting
9.3 Forward Chaining
9.4 Backward Chaining
9.5 Resolution
9.6 Summary, Bibliographical and Historical Notes
10 Classical Planning
10.1 Definition of Classical Planning
10.2 Algorithms for Planning as State-space Search
10.3 Planning Graphs
Exercises
Contents
Other Classical Planning Approaches
Analysis of Planning Approaches
Summary, Bibliographical and Historical Notes
11 Planning and Acting in the Real World
11.1 Time. Schedules. and Resources
11.2 Hierarchical Planning
Exerc]ses
11.3 Planning and Acting in Nondeterministic Domains
11.4 Multiagent Planning
11.5 Summary, Bibliographical and Historical Notes
12 Knowledge Representation
12.1 Ontological Engineering
12.2 Categories and Objects
12.3 Events
12.4 Mental Events and Mental Objects
12.5 Reasoning Systems for Categories
12.6 Reasoning with Default Information
12.7 The Intemet Shopping World
12.8 Summary, Bibliographical and Historical Notes
IV Uncertain knowledge and reasoning
13
14
Quantifying Uncertainty
Acting under Uncertainty
Basic Probability Notation
Inference Using Full Joint Distributions
Independence
Bayes' Rule and Its Use
The Wumpus World Revisited
Summary, Bibliographical and Historical Notes
ab
stic Reasoning
Exercises
Representing Knowledge in an Uncertain Domain
The Semantics of Bayesian Networks
Efficient Representation of Conditional Distributions
Exact Inference in Bayesian Networks
Approximate Inference in Bayesian Networks
Relational and First-Order Probability Models
Other Approaches to Uncertain Reasoning
Summary, Bibliographical and Historical Notes
15 Probabilistic Reasoning over Time
15.1 Time and Uncertainty
Exerc]ses
XV
Inference in Temporal Models
Hidden Markov Models
Kalman Filters
Dy
namlc Bayesian Networks
Keeping Track of Many Objects
Summary, Bibliographical and Historical Notes
16 Making Simple Decisions
16.1 Combining Beliefs and Desires under
16.2 The Basis of Utility Theory
16.3 Utility Functions
16.4 Multiattribute Utility Functions
16.5 Decision Networks
16.6 The Value of Information
16.7 Decision-Theoretic Expert Systems
Exercises
Uncertainty
16.8 Summary, Bibliographical and Historical Notes
17 Making Complex Decisions
17.1 Sequential Decision Problems
17.2 Value Iteration
17.3 Policy Iteration
17.4 Partially Observable MDPs
17.5 Decisions with Multiple Agents
17.6 Mechanism Design
Game Theory
17.7 Summary, Bibliographical and Historical Notes
Learning
18 Learning from Examples
18.1 Forms of Learning
18.2 Supervised Learning
18.3 Learning Decision Trees
18.4 Evaluating and Choosing the Best Hypothesis
18.5 The Theory of Learning
Exercises
Exercises
18.6 Regression and Classification with Linear Models
18.7 Artificial Neural Networks
18.8 Nonparametric Models
18.9 Support Vector Machines
18.10 Ensemble Learning
18.11 Practical Machine Learning
18.12 Summary, Bibliographical and Historical Notes
19 Knowledge in Learning
19.1 A Logical Formulation of Learning
Exercises
Contents
Knowledge in Learning
Explanation-Based Learning
Learning Using Relevance Information
Inductive Logic Programming
Summary, Bibliographical and Historical Notes
20 Learning Probabilistic Models
20.1 Statistical Learning
20.2 Learning with Complete Data
Exercises
20.3 Learning with Hidden Variables: The EM Algorithm
20.4 Summary, Bibliographical and Historical Notes, Exercises
21 Reinforcement Learning
Communicating, perceiving, and acting
22 Natural Language Processing
22.1 Language Models
22.2 Text Classification
22.3 Information Retrieval
22.4 Information Extraction
22.5 Summary, Bibliographical and Historical Notes
23 Natural Language for Communication
23.1 Phrase Structure Grammars
23.2 Syntactic Analysis (Parsing)
Exercises
Exercises
23.3 Augmented Grammars and Semantic Interpretation
23.4 Machine Translation
23.5 Speech Recognition
23.6 Summary, Bibliographical and Historical Notes
24 Perception
24.1 Image Formation
24.2 Early Image-Processing Operations
24.3 Object Recognition by Appearance
24.4 Reconstructing the 3D World
24.5 Object Recognition from Structural Information
Exercises
XVll
XVlll
Using Vision
Summary, Bibliographical and Historical Notes
25 Robotics
25.1 Introduction
25.2 Robot Hardware
25.3 Robotic Perception
25.4 Planning to Move
25.5 Planning Uncertain Movements
25.6 Moving
25.7 Robotic Software Architectures
25.8 Application Domains
25.9 Summary, Bibliographical and Historical Notes
Conclusions
26 Philosophical Foundations
26.1 Weak AI: Can Machines Act Intelligently?
26.2 Strong AI: Can Machines Really Think
Exercises
Exercises
26.3 The Ethics and Risks of Developing Artificial Intelligence
26.4 Summary, Bibliographical and Historical Notes
27 AI: The Present and Future
27.1 Agent Components
27.2 Agent Architectures
27.3 Are We Going in the Right Direction?
27.4 What If AI Does Succeed?
A Mathematical background
A. 1 Complexity Analysis and O() Notation
A.2 Vectors, Matrices, and Linear Algebra
A.3 Probability Distributions
B Notes on Languages and Algorithms
B. 1 Defining Languages with B ackus-Naur Form
B.2 Describing Algorithms with Pseudocode
B.3 Online Help
Bibliography
