Preface
Part I Agents in the World
Chapter 1 Artificial Intelligence and Agents
1.1 What is Artificial Intelligence?
1.1.1 Artificial and Natural Intelligence
1.1.2 Natural Intelligence
1.2 A Brief History of Artificial Intelligence
1.2.1 Relationship to Other Disciplines
1.3 Agents Situated in Environments
1.4 Prototypical Applications
1.4.1 An Autonomous Delivery and Helping Robot
1.4.2 A Diagnostic Assistant
1.4.3 A Tutoring Agent
1.4.4 A Trading Agent
1.4.5 Smart Home
1.5 Agent Design Space
1.5.1 Modularity
1.5.2 Planning Horizon
1.5.3 Representation
1.5.4 Computational Limits
1.5.5 Learning
1.5.6 Uncertainty
1.5.7 Preference
1.5.8 Number of Agents
1.5.9 Interactivity
1.5.10 Interaction of the Dimensions
1.6 Designing Agents
1.6.1 Simplifying Environments and Simplifying Agents
1.6.2 Tasks
1.6.3 Defining a Solution
1.6.4 Representations
1.7 Social Impact
1.8 Overview of the Book
1.9 Review
1.10 References and Further Reading
1.11 Exercises
Chapter 2 Agent Architectures and Hierarchical Control
2.1 Agents and Environments
2.1.1 Controllers
2.1.2 Belief States
2.1.3 Agent Functions
2.2 Hierarchical Control
2.3 Designing Agents
2.3.1 Discrete, Continuous, and Hybrid
2.3.2 Choosing Agent Functions
2.3.3 Offline and Online Computation
2.4 Social Impact
2.5 Review
2.6 References and Further Reading
2.7 Exercises
Part II Reasoning and Planning with Certainty
Chapter 3 Searching for Solutions
3.1 Problem Solving as Search
3.2 State Spaces
3.3 Graph Searching
3.3.1 Formalizing Graph Searching
3.4 A Generic Searching Algorithm
3.5 Uninformed Search Strategies
3.5.1 Breadth-First Search
3.5.2 Depth-First Search
3.5.3 Iterative Deepening
3.5.4 Lowest-Cost-First Search
3.6 Informed (Heuristic) Search
3.6.1 A∗ Search
3.6.2 Branch and Bound
3.6.3 Designing a Heuristic Function
3.7 Pruning the Search Space
3.7.1 Cycle Pruning
3.7.2 Multiple-Path Pruning
3.7.3 Summary of Search Strategies
3.8 Search Refinements
3.8.1 Direction of Search
3.8.2 Dynamic Programming
3.9 Social Impact
3.10 Review
3.11 References and Further Reading
3.12 Exercises
Chapter 4 Reasoning with Constraints
4.1 Variables and Constraints
4.1.1 Variables and Assignments
4.1.2 Constraints
4.1.3 Constraint Satisfaction Problems
4.2 Solving CSPs by Searching
4.3 Consistency Algorithms
4.4 Domain Splitting
4.5 Variable Elimination
4.6 Local Search
4.6.1 Iterative Best Improvement
4.6.2 Randomized Algorithms
4.6.3 Local Search Variants
4.6.4 Evaluating Randomized Algorithms
4.6.5 Random Restart
4.7 Population-Based Methods
4.8 Optimization
4.8.1 Systematic Methods for Discrete Optimization
4.8.2 Local Search for Optimization
4.8.3 Gradient Descent for Continuous Functions
4.9 Social Impact
4.10 Review
4.11 References and Further Reading
4.12 Exercises
Chapter 5 Propositions and Inference
5.1 Propositions
5.1.1 Syntax of the Propositional Calculus
5.1.2 Semantics of the Propositional Calculus
5.2 Propositional Constraints
5.2.1 Clausal Form for CSPs
5.2.2 Exploiting Propositional Structure in Local Search
5.3 Propositional Definite Clauses
5.3.1 Queries and Answers
5.3.2 Proofs
5.4 Querying the User
5.5 Knowledge-Level Debugging
5.5.1 Incorrect Answers
5.5.2 Missing Answers
5.6 Proving by Contradiction
5.6.1 Horn Clauses
5.6.2 Assumables and Conflicts
5.6.3 Consistency-Based Diagnosis
5.6.4 Reasoning with Assumptions and Horn Clauses
5.7 Complete Knowledge Assumption
5.7.1 Non-Monotonic Reasoning
5.7.2 Proof Procedures for Negation as Failure
5.8 Abduction
5.9 Causal Models
5.10 Social Impact
5.11 Review
5.12 References and Further Reading
5.13 Exercises
Chapter 6 Deterministic Planning
6.1 Representing States, Actions, and Goals
6.1.1 Explicit State-Space Representation
6.1.2 The STRIPS Representation
6.1.3 Feature-Based Representation of Actions
6.1.4 Initial States and Goals
6.2 Forward Planning
6.3 Regression Planning
6.4 Planning as a CSP
6.4.1 Action Features
6.5 Partial-Order Planning
6.6 Social Impact
6.7 Review
6.8 References and Further Reading
6.9 Exercises
Part III Learning and Reasoning with Uncertainty
Chapter 7 Supervised Machine Learning
7.1 Learning Issues
7.2 Supervised Learning Foundations
7.2.1 Evaluating Predictions
7.2.2 Point Estimates with No Input Features
7.2.3 Types of Errors
7.3 Basic Models for Supervised Learning
7.3.1 Learning Decision Trees
7.3.2 Linear Regression and Classification
7.4 Overfitting
7.4.1 Pseudocounts
7.4.2 Regularization
7.4.3 Cross Validation
7.5 Composite Models
7.5.1 Boosting
7.5.2 Gradient-Boosted Trees
7.6 Limitations
7.7 Social Impact
7.8 Review
7.9 References and Further Reading
7.10 Exercises
Chapter 8 Neural Networks and Deep Learning
8.1 Feedforward Neural Networks
8.1.1 Parameter Learning
8.2 Improved Optimization
8.2.1 Momentum
8.2.2 RMS-Prop
8.2.3 Adam
8.2.4 Initialization
8.3 Improving Generalization
8.4 Convolutional Neural Networks
8.5 Neural Models for Sequences
8.5.1 Word Embeddings
8.5.2 Recurrent Neural Networks
8.5.3 Long Short-Term Memory
8.5.4 Attention and Transformers
8.5.5 Large Language Models
8.6 Other Neural Network Models
8.6.1 Autoencoders
8.6.2 Adversarial Networks
8.6.3 Diffusion Models
8.7 Social Impact
8.8 Review
8.9 References and Further Reading
8.10 Exercises
Chapter 9 Reasoning with Uncertainty
9.1 Probability
9.1.1 Semantics of Probability
9.1.2 Conditional Probability
9.1.3 Expected Values
9.2 Independence
9.3 Belief Networks
9.3.1 Observations and Queries
9.3.2 Constructing Belief Networks
9.3.3 Representing Conditional Probabilities and Factors
9.4 Probabilistic Inference
9.5 Exact Probabilistic Inference
9.5.1 Recursive Conditioning
9.5.2 Variable Elimination for Belief Networks
9.5.3 Exploiting Structure and Compilation
9.6 Sequential Probability Models
9.6.1 Markov Chains
9.6.2 Hidden Markov Models
9.6.3 Algorithms for Monitoring and Smoothing
9.6.4 Dynamic Belief Networks
9.6.5 Time Granularity
9.6.6 Probabilistic Language Models
9.7 Stochastic Simulation
9.7.1 Sampling from a Single Variable
9.7.2 Forward Sampling
9.7.3 Rejection Sampling
9.7.4 Likelihood Weighting
9.7.5 Importance Sampling
9.7.6 Particle Filtering
9.7.7 Markov Chain Monte Carlo
9.8 Social Impact
9.9 Review
9.10 References and Further Reading
9.11 Exercises
Chapter 10 Learning with Uncertainty
10.1 Probabilistic Learning
10.2 Bayesian Learning
10.2.1 Learning Probabilities
10.2.2 Probabilistic Classifiers
10.2.3 Probabilistic Learning of Decision Trees
10.2.4 Description Length
10.3 Unsupervised Learning
10.3.1 k-Means
10.3.2 Expectation Maximization for Soft Clustering
10.4 Learning Belief Networks
10.4.1 Hidden Variables
10.4.2 Missing Data
10.4.3 Structure Learning
10.4.4 General Case of Belief Network Learning
10.5 Social Impact
10.6 Review
10.7 References and Further Reading
10.8 Exercises
Chapter 11 Causality
11.1 Probabilistic Causal Models
11.1.1 Do-notation
11.1.2 D-separation
11.2 Missing Data
11.3 Inferring Causality
11.3.1 Backdoor Criterion
11.3.2 Do-calculus
11.3.3 Front-Door Criterion
11.3.4 Simpson’s Paradox
11.4 Instrumental Variables
11.5 Counterfactual Reasoning
11.6 Social Impact
11.7 Review
11.8 References and Further Reading
11.9 Exercises
Part IV Planning and Acting with Uncertainty
Chapter 12 Planning with Uncertainty
12.1 Preferences and Utility
12.1.1 Axioms for Rationality
12.1.2 Factored Utility
12.1.3 Prospect Theory
12.2 One-Off Decisions
12.2.1 Single-Stage Decision Networks
12.3 Sequential Decisions
12.3.1 Decision Networks
12.3.2 Policies
12.3.3 Optimizing Decision Networks using Search
12.3.4 Variable Elimination for Decision Networks
12.4 The Value of Information and Control
12.5 Decision Processes
12.5.1 Policies
12.5.2 Value Iteration
12.5.3 Policy Iteration
12.5.4 Dynamic Decision Networks
12.5.5 Partially Observable Decision Processes
12.6 Social Impact
12.7 Review
12.8 References and Further Reading
12.9 Exercises
Chapter 13 Reinforcement Learning
13.1 Reinforcement Learning Problem
13.2 Evolutionary Algorithms
13.3 Temporal Differences
13.4 Learning from Experiences
13.4.1 Q-learning
13.5 Exploration and Exploitation
13.6 Evaluating RL Algorithms
13.7 On-Policy Learning
13.8 Model-Based RL
13.9 RL with Generalization
13.9.1 SARSA with Linear Function Approximation
13.9.2 Escaping Local Optima
13.10 Social Impact
13.11 Review
13.12 References and Further Reading
13.13 Exercises
Chapter 14 Multiagent Systems
14.1 Multiagent Framework
14.2 Representations of Games
14.2.1 Normal-Form Games
14.2.2 Extensive Form of a Game
14.2.3 Multiagent Decision Networks
14.3 Solving Perfect Information Games
14.3.1 Adversarial Games
14.4 Reasoning with Imperfect Information
14.4.1 Computing Nash Equilibria
14.5 Group Decision Making
14.6 Mechanism Design
14.7 Multiagent Reinforcement Learning
14.7.1 Perfect-Information Games
14.7.2 Reinforcement Learning with Stochastic Policies
14.7.3 State-of-the-Art Game Players
14.8 Social Impact
14.9 Review
14.10 References and Further Reading
14.11 Exercises
Part V Representing Individuals and Relations
Chapter 15 Individuals and Relations
15.1 Exploiting Relational Structure
15.2 Symbols and Semantics
15.3 Predicate Calculus
15.3.1 Semantics of Ground Logical Formulas
15.3.2 Interpreting Variables
15.4 Datalog: A Relational Rule Language
15.4.1 Queries with Variables
15.5 Proofs and Substitutions
15.5.1 Instances and Substitutions
15.5.2 Bottom-Up Procedure for Datalog
15.5.3 Unification
15.5.4 Definite Resolution with Variables
15.6 Function Symbols and Data Structures
15.6.1 Proof Procedures with Function Symbols
15.7 Applications in Natural Language
15.7.1 Using Definite Clauses for Context-Free Grammars
15.7.2 Augmenting the Grammar
15.7.3 Building a Natural Language Interface to a Database
15.7.4 Comparison with Large Language Models
15.8 Equality
15.8.1 Allowing Equality Assertions
15.8.2 Unique Names Assumption
15.9 Complete Knowledge Assumption
15.9.1 Complete Knowledge Assumption Proof Procedures
15.10 Social Impact
15.11 Review
15.12 References and Further Reading
15.13 Exercises
Chapter 16 Knowledge Graphs and Ontologies
16.1 Knowledge Graphs
16.1.1 Triples
16.1.2 Individuals and Identifiers
16.1.3 Graphical Representations
16.2 Classes and Properties
16.2.1 Class and Property Hierarchies
16.2.2 Designing Classes
16.3 Ontologies and Knowledge Sharing
16.3.1 Description Logic
16.3.2 Top-Level Ontologies
16.4 Social Impact
16.5 Review
16.6 References and Further Reading
16.7 Exercises
Chapter 17 Relational Learning and Probabilistic Reasoning
17.1 From Relations to Features and Random Variables
17.2 Embedding-Based models
17.2.1 Learning a Binary Relation
17.2.2 Learning Knowledge Graphs
17.3 Learning Interdependence of Relations
17.3.1 Relational Probabilistic Models
17.3.2 Collective Classification and Crowd Sourcing
17.3.3 Language and Topic Models
17.3.4 Some Specific Representations
17.4 Existence and Identity Uncertainty
17.5 Social Impact
17.6 Review
17.7 References and Further Reading
17.8 Exercises
Part VI The Big Picture
Chapter 18 The Social Impact of Artificial Intelligence
18.1 The Digital Economy
18.2 Values and Bias
18.3 Human-Centred Artificial Intelligence
18.4 Work and Automation
18.5 Transportation
18.6 Sustainability
18.7 Ethics
18.8 Governance and Regulation
18.9 Review
18.10 Exercises
Chapter 19 Retrospect and Prospect
19.1 Deploying AI
19.2 Agent Design Space Revisited
19.3 Looking Ahead