Artificial intelligence; a new synthesis /
Nils j. Nilsson
Artificial intelligence; a new synthesis / NilsJ, Nilsson - Burlington: Morgan Kaufmann , 1998. - xxi, 513 p. ill. ;
Introduction
1.1 What Is AI?
1.2 Approaches to Artificial Intelligence
1.5 Brief History of AI
1.4 Plan of the Book
1.5 Additional Readings and Discussion
Exercises
Reactive Machines
Stimulus-Response Agents
2.1 Perception and Action
2.1.1 Perception
2.1.2 Action
2.1.3 Boolean Algebra
2.1.4 Classes and Forms of Boolean Functions
2.2 Representing and Implementing Action Functions
2.2.1 Production Systems
2.2.2 Networks
2.2.3 The Subsumption Architecture
2.3 Additional Readings and Discussion
Exercises
3 ^ Neural Networks
5.1 Introduction
3.2 Training Single TLUs
3.2.1 TLU Geometry
3.2.2 Augmented Vectors
3.2.3 Gradient Descent Methods
3.2.4 The Widrow-Hoff Procedure
3.2.5 The Generalized Delta Procedure
3.2.6 The Error-Correction Procedure
3.3 Neural Networks
3.3.1 Motivation
3.3.2 Notation
33.3 The Backpropagation Method
3.3.4 Computing Weight Changes in the Final Layer
3.3.5 Computing Changes to the Weights in Intermediate Layers
3.4 Generalization, Accuracy, and Overfitting
3.5 Additional Readings and Discussion
Exercises
Machine Evolution
4.1 Evolutionary Computation
4.2 Genetic Programming
4.2.1 Program Representation in GP
Contents
4.2.2 The GP Process
4.2.5 Evolving a Wall-Following Robot
4.3 Additional Readings and Discussion
Exercises
BFp^H State Machines
5.1 Representing the Environment by Feature Vectors
5.2 Elman Networks
5.3 Iconic Representations
5.4 Blackboard Systems
5.5 Additional Readings and Discussion
Exercises
Robot Vision
6.1 Introduction
6.2 Steering an Automobile
6.3 Two Stages of Robot Vision
6.4 Image Processing
6.4.1 Averaging
6.4.2 Edge Enhancement
6.4.3 Combining Edge Enhancement with Averaging
6.4.4 Region Finding
6.4.5 Using Image Attributes Other Than Intensity
6.5 Scene Analysis
6.5.1 Interpreting Lines and Curves in the Image
6.5.2 Model-Based Vision
6.6 Stereo Vision and Depth Information
6.7 Additional Readings and Discussion
Exercises
w
Contents
II Search in State Spaces
7L :• Agents That Plan
7.1 Memory Versus Computation
7.2 State-Space Graphs
7.3 Searching Explicit State Spaces
7.4 Feature-Based State Spaces
7.5 Graph Notation
7.6 Additional Readings and Discussion
Exercises
Uninformed Search
8.1 Formulating the State Space
8.2 Components of Implicit State-Space Graphs
8.3 Breadth-First Search
8.4 Depth-First or Backtracking Search
8.5 Iterative Deepening
8.6 Additional Readings and Discussion
Exercises
^ 9 J Heuristic Search
9.1 Using Evaluation Functions
9.2 A General Graph-Searching Algorithm
9.2.1 Algorithm A*
9.2.2 Admissibility of A*
9.2.5 The Consistency (or Monotone) Condition
9.2.4 Iterative-Deepening A*
9.2.5 Recursive Best-First Search
Ff7
9.5 Heuristic Functions and Search Efficiency
9.4 Additionad Readings and Discussion
Exercises
Planning, Acting, and Learning
10.1 The Sense/Plan/Act Cycle
10.2 Approximate Search
10.2.1 Island-Driven Search
10.2.2 Hierarchical Search
10.2.5 Limited-Horizon Search
10.2.4 Cycles
10.2.5 Building Reactive Procedures
10.3 Learning Heuristic Functions
10.3.1 Explicit Graphs
10.3.2 Implicit Graphs
10.4 Rewards Instead of Goals
10.5 Additional Readings and Discussion
Exercises
Alternative Search Formulations and
Applications
11.1 Assignment Problems
11.2 Constructive Methods
11.3 Heuristic Repair
11.4 Function Optimization
Exercises
j|2 Adversarial Search
12.1 Two-Agent Games
12.2 The Minimax Procedure
xii Contents
12.5 The Alpha-Beta Procedure
12.4 The Search Efficiency of the Alpha-Beta Procedure
12.5 Other Important Matters
12.6 Games of Chance
12.7 Learning Evaluation Functions
12.8 Additional Readings and Discussion
Exercises
III Knowledge Representation and
Reasoning 21;
The Propositional Calculus
13.1 Using Constraints on Feature Values
13.2 The Language
13.3 Rules of Inference
13.4 Definition of Proof
13.5 Semantics
13.5.1 Interpretations
13.5.2 The Propositional Truth Table
13.5.3 Satisfiability and Models
13.5.4 Validity
13.5.5 Equivalence
13.5.6 Entailment
13.6 Soundness and Completeness
13.7 The PSAT Problem
13.8 Other Important Topics
13.8.1 Language Distinctions
13.8.2 Metatheorems
13.8.3 Associative Laws
13.8.4 Distributive Laws
Exercises
I Resolution in the Propositional Calculns
14.1 A New Rule of Inference: Resolution
14.1.1 Clauses as wffs
14.1.2 Resolution on Clauses
14.1.5 Soundness of Resolution
- 14.2 Converting Arbitrary wffs to Conjunctions of Clauses
14.5 Resolution Refutations
14.4 Resolution Refutation Search Strategies
14.4.1 Ordering Strategies
14.4.2 Refinement Strategies
14.5 Horn Clauses
Exercises
The Predicate Calculus
15.1 Motivation
15.2 The Language and Its Syntax
15.5 Semantics
15.3.1 Worlds
15.3.2 Interpretations
15.3.3 Models and Related Notions
15.3.4 Knowledge
15.4 Quantification
15.5 Semantics of Quantifiers
15.5.1 Universal Quantifiers
15.5.2 Existential Quantifiers
15.5.3 Useful Equivalences
15.5.4 Rules of Inference
15.6 Predicate Calculus as a Language for Representing
Knowledge
15.6.1 Conceptualizations
15.6.2 Examples
15.7 Additional Readings and Discussion
Exercises
Resolution in the Predicate Calculus
16.1 Unification
16J2 Predicate-Calculus Resolution
16.5 Completeness and Soundness
16.4 Converting Arbitrary wffs to Clause Form
16.5 Using Resolution to Prove Theorems
16.6 Answer Extraction
16.7 Hie Equality Predicate
16.8 Additional Readings and Discussion
Exercises
Knowledge-Based Systems
17.1 Confronting the Real World
17.2 Reasoning Using Horn Clauses
17.3 Maintenance in Dynamic Knowledge Bases
V7A Rule-Based Expert Systems
17.5 Rule Learning
17.5.1 Learning Propositional Calculus Rules
17.5.2 Learning First-Order Logic Rules
17.5.3 Explanation-Based Generalization
17.6 Additional Readings and Discussion
Exercises
' J Representing Commonsense Knowledge
18.1 The Commonsense World
18.1.1 What Is Commonsense Knowledge?
18.1.2 Difficulties in Representing Commonsense Knowledge
18.1.3 The Importance of Commonsense Knowledge
18.1.4 Research Areas
18.2 Time
18.5 Knowledge Representation by Networks
18.5.1 Taxonomic Knowledge
18.3.2 Semantic Networks
18.3.3 Nonmonotonic Reasoning in Semantic Networks
18.3.4 Frames
18.4 Additional Readings and Discussion
Exercises
Reasoning with Uncertain Information
19.1 Review of Probability Theory
19.1.1 Fundamental Ideas
19.1.2 Conditional Probabilities
19.2 Probabilistic Inference
19.2.1 A General Method
19.2.2 Conditional Independence
19.5 Bayes Networks
19.4 Patterns of Inference in Bayes Networks
19.5 Uncertain Evidence
19.6 D-Separation
19.7 Probabilistic Inference in Polytrees
19.7.1 Evidence Above
19.7.2 Evidence Below
19.7.3 Evidence Above and Below
19.7.4 A Numerical Example
19.8 Additional Readings and Discussion
Exercises
lOlg] Learning and Acting with Bayes Nets
20.1 Learning Bayes Nets
20.1.1 Known Network Structure
20.1.2 Learning Network Structure
20.2 Probabilistic Inference and Action
20.2.1 The General Setting
20.2.2 An Extended Example
20.2.3 Generalizing the Example
20.3 Additional Readings and Discussion
Exercises
IV Planning Methods Based on
Logic
21 The Situation Calculus
21.1 Reasoning about States and Actions
21.2 Some Difficulties
21.2.1 Frame Axioms
21.2.2 Qualifications
21.2.3 Ramifications
21.3 Generating Plans
21.4 Additional Readings and Discussion
Exercises
H-''. 'iZZ ' 'I Planning
22.1 STRIPS Planning Systems
22.1.1 Describing States and Goals
22.1.2 Forward Search Methods
22.1.3 Recursive STRIPS
22.1.4 Plans with Run-Time Conditionals
22.1.5 The Sussman Anomaly
22.1.6 Backward Search Methods
22.2 Plan Spaces and Partial-Order Planning
22.3 Hierarchical Planning
22.3.1 ABSTRIPS
22.3.2 Combining Hierarchical and Partial-Order Planning
22.4 Learning Plans
22.5 Additional Readings and Discussion
Exercises
V Communication and Integration
Multiple Agents
23.1 Interacting Agents
23.2 Models of Other Agents
23.2.1 Varieties of Models
23.2.2 Simulation Strategies
23.2.3 Simulated Databases
23.2.4 The Intentional Stance
23.3 A Modal Logic of Knowledge
23.3.1 Modal Operators
23.3.2 Knowledge Axioms
23.5.3 Reasoning about Other Agents' Knowledge
23.5.4 Predicting Actions of Other Agents
25.4 Additional Readings and Discussion
Exercises
Communication among Agents
24.1 Speech Acts
24.1.1 Planning Speech Acts
24.1.2 Implementing Speech Acts
24.2 Understanding Language Strings
24.2.1 Phrase-Structure Grammars
24.2.2 Semantic Analysis
24.2.5 Expanding the Grammar
24.3 Efficient Communication
24.3.1 Use of Context
24.3.2 Use of Knowledge to Resolve Ambiguities
24.4 Natural Language Processing
24.5 Additional Readings and Discussion
Exercises
Agent Architectures
25.1 Three-Level Architectures
25.2 Goal Arbitration
25.5 The Triple-Tower Architecture
25.4 Bootstrapping
25.5 Additional Readings and Discussion
Exercises
9788181471901)pb)
006.3 / NIL/A
Artificial intelligence; a new synthesis / NilsJ, Nilsson - Burlington: Morgan Kaufmann , 1998. - xxi, 513 p. ill. ;
Introduction
1.1 What Is AI?
1.2 Approaches to Artificial Intelligence
1.5 Brief History of AI
1.4 Plan of the Book
1.5 Additional Readings and Discussion
Exercises
Reactive Machines
Stimulus-Response Agents
2.1 Perception and Action
2.1.1 Perception
2.1.2 Action
2.1.3 Boolean Algebra
2.1.4 Classes and Forms of Boolean Functions
2.2 Representing and Implementing Action Functions
2.2.1 Production Systems
2.2.2 Networks
2.2.3 The Subsumption Architecture
2.3 Additional Readings and Discussion
Exercises
3 ^ Neural Networks
5.1 Introduction
3.2 Training Single TLUs
3.2.1 TLU Geometry
3.2.2 Augmented Vectors
3.2.3 Gradient Descent Methods
3.2.4 The Widrow-Hoff Procedure
3.2.5 The Generalized Delta Procedure
3.2.6 The Error-Correction Procedure
3.3 Neural Networks
3.3.1 Motivation
3.3.2 Notation
33.3 The Backpropagation Method
3.3.4 Computing Weight Changes in the Final Layer
3.3.5 Computing Changes to the Weights in Intermediate Layers
3.4 Generalization, Accuracy, and Overfitting
3.5 Additional Readings and Discussion
Exercises
Machine Evolution
4.1 Evolutionary Computation
4.2 Genetic Programming
4.2.1 Program Representation in GP
Contents
4.2.2 The GP Process
4.2.5 Evolving a Wall-Following Robot
4.3 Additional Readings and Discussion
Exercises
BFp^H State Machines
5.1 Representing the Environment by Feature Vectors
5.2 Elman Networks
5.3 Iconic Representations
5.4 Blackboard Systems
5.5 Additional Readings and Discussion
Exercises
Robot Vision
6.1 Introduction
6.2 Steering an Automobile
6.3 Two Stages of Robot Vision
6.4 Image Processing
6.4.1 Averaging
6.4.2 Edge Enhancement
6.4.3 Combining Edge Enhancement with Averaging
6.4.4 Region Finding
6.4.5 Using Image Attributes Other Than Intensity
6.5 Scene Analysis
6.5.1 Interpreting Lines and Curves in the Image
6.5.2 Model-Based Vision
6.6 Stereo Vision and Depth Information
6.7 Additional Readings and Discussion
Exercises
w
Contents
II Search in State Spaces
7L :• Agents That Plan
7.1 Memory Versus Computation
7.2 State-Space Graphs
7.3 Searching Explicit State Spaces
7.4 Feature-Based State Spaces
7.5 Graph Notation
7.6 Additional Readings and Discussion
Exercises
Uninformed Search
8.1 Formulating the State Space
8.2 Components of Implicit State-Space Graphs
8.3 Breadth-First Search
8.4 Depth-First or Backtracking Search
8.5 Iterative Deepening
8.6 Additional Readings and Discussion
Exercises
^ 9 J Heuristic Search
9.1 Using Evaluation Functions
9.2 A General Graph-Searching Algorithm
9.2.1 Algorithm A*
9.2.2 Admissibility of A*
9.2.5 The Consistency (or Monotone) Condition
9.2.4 Iterative-Deepening A*
9.2.5 Recursive Best-First Search
Ff7
9.5 Heuristic Functions and Search Efficiency
9.4 Additionad Readings and Discussion
Exercises
Planning, Acting, and Learning
10.1 The Sense/Plan/Act Cycle
10.2 Approximate Search
10.2.1 Island-Driven Search
10.2.2 Hierarchical Search
10.2.5 Limited-Horizon Search
10.2.4 Cycles
10.2.5 Building Reactive Procedures
10.3 Learning Heuristic Functions
10.3.1 Explicit Graphs
10.3.2 Implicit Graphs
10.4 Rewards Instead of Goals
10.5 Additional Readings and Discussion
Exercises
Alternative Search Formulations and
Applications
11.1 Assignment Problems
11.2 Constructive Methods
11.3 Heuristic Repair
11.4 Function Optimization
Exercises
j|2 Adversarial Search
12.1 Two-Agent Games
12.2 The Minimax Procedure
xii Contents
12.5 The Alpha-Beta Procedure
12.4 The Search Efficiency of the Alpha-Beta Procedure
12.5 Other Important Matters
12.6 Games of Chance
12.7 Learning Evaluation Functions
12.8 Additional Readings and Discussion
Exercises
III Knowledge Representation and
Reasoning 21;
The Propositional Calculus
13.1 Using Constraints on Feature Values
13.2 The Language
13.3 Rules of Inference
13.4 Definition of Proof
13.5 Semantics
13.5.1 Interpretations
13.5.2 The Propositional Truth Table
13.5.3 Satisfiability and Models
13.5.4 Validity
13.5.5 Equivalence
13.5.6 Entailment
13.6 Soundness and Completeness
13.7 The PSAT Problem
13.8 Other Important Topics
13.8.1 Language Distinctions
13.8.2 Metatheorems
13.8.3 Associative Laws
13.8.4 Distributive Laws
Exercises
I Resolution in the Propositional Calculns
14.1 A New Rule of Inference: Resolution
14.1.1 Clauses as wffs
14.1.2 Resolution on Clauses
14.1.5 Soundness of Resolution
- 14.2 Converting Arbitrary wffs to Conjunctions of Clauses
14.5 Resolution Refutations
14.4 Resolution Refutation Search Strategies
14.4.1 Ordering Strategies
14.4.2 Refinement Strategies
14.5 Horn Clauses
Exercises
The Predicate Calculus
15.1 Motivation
15.2 The Language and Its Syntax
15.5 Semantics
15.3.1 Worlds
15.3.2 Interpretations
15.3.3 Models and Related Notions
15.3.4 Knowledge
15.4 Quantification
15.5 Semantics of Quantifiers
15.5.1 Universal Quantifiers
15.5.2 Existential Quantifiers
15.5.3 Useful Equivalences
15.5.4 Rules of Inference
15.6 Predicate Calculus as a Language for Representing
Knowledge
15.6.1 Conceptualizations
15.6.2 Examples
15.7 Additional Readings and Discussion
Exercises
Resolution in the Predicate Calculus
16.1 Unification
16J2 Predicate-Calculus Resolution
16.5 Completeness and Soundness
16.4 Converting Arbitrary wffs to Clause Form
16.5 Using Resolution to Prove Theorems
16.6 Answer Extraction
16.7 Hie Equality Predicate
16.8 Additional Readings and Discussion
Exercises
Knowledge-Based Systems
17.1 Confronting the Real World
17.2 Reasoning Using Horn Clauses
17.3 Maintenance in Dynamic Knowledge Bases
V7A Rule-Based Expert Systems
17.5 Rule Learning
17.5.1 Learning Propositional Calculus Rules
17.5.2 Learning First-Order Logic Rules
17.5.3 Explanation-Based Generalization
17.6 Additional Readings and Discussion
Exercises
' J Representing Commonsense Knowledge
18.1 The Commonsense World
18.1.1 What Is Commonsense Knowledge?
18.1.2 Difficulties in Representing Commonsense Knowledge
18.1.3 The Importance of Commonsense Knowledge
18.1.4 Research Areas
18.2 Time
18.5 Knowledge Representation by Networks
18.5.1 Taxonomic Knowledge
18.3.2 Semantic Networks
18.3.3 Nonmonotonic Reasoning in Semantic Networks
18.3.4 Frames
18.4 Additional Readings and Discussion
Exercises
Reasoning with Uncertain Information
19.1 Review of Probability Theory
19.1.1 Fundamental Ideas
19.1.2 Conditional Probabilities
19.2 Probabilistic Inference
19.2.1 A General Method
19.2.2 Conditional Independence
19.5 Bayes Networks
19.4 Patterns of Inference in Bayes Networks
19.5 Uncertain Evidence
19.6 D-Separation
19.7 Probabilistic Inference in Polytrees
19.7.1 Evidence Above
19.7.2 Evidence Below
19.7.3 Evidence Above and Below
19.7.4 A Numerical Example
19.8 Additional Readings and Discussion
Exercises
lOlg] Learning and Acting with Bayes Nets
20.1 Learning Bayes Nets
20.1.1 Known Network Structure
20.1.2 Learning Network Structure
20.2 Probabilistic Inference and Action
20.2.1 The General Setting
20.2.2 An Extended Example
20.2.3 Generalizing the Example
20.3 Additional Readings and Discussion
Exercises
IV Planning Methods Based on
Logic
21 The Situation Calculus
21.1 Reasoning about States and Actions
21.2 Some Difficulties
21.2.1 Frame Axioms
21.2.2 Qualifications
21.2.3 Ramifications
21.3 Generating Plans
21.4 Additional Readings and Discussion
Exercises
H-''. 'iZZ ' 'I Planning
22.1 STRIPS Planning Systems
22.1.1 Describing States and Goals
22.1.2 Forward Search Methods
22.1.3 Recursive STRIPS
22.1.4 Plans with Run-Time Conditionals
22.1.5 The Sussman Anomaly
22.1.6 Backward Search Methods
22.2 Plan Spaces and Partial-Order Planning
22.3 Hierarchical Planning
22.3.1 ABSTRIPS
22.3.2 Combining Hierarchical and Partial-Order Planning
22.4 Learning Plans
22.5 Additional Readings and Discussion
Exercises
V Communication and Integration
Multiple Agents
23.1 Interacting Agents
23.2 Models of Other Agents
23.2.1 Varieties of Models
23.2.2 Simulation Strategies
23.2.3 Simulated Databases
23.2.4 The Intentional Stance
23.3 A Modal Logic of Knowledge
23.3.1 Modal Operators
23.3.2 Knowledge Axioms
23.5.3 Reasoning about Other Agents' Knowledge
23.5.4 Predicting Actions of Other Agents
25.4 Additional Readings and Discussion
Exercises
Communication among Agents
24.1 Speech Acts
24.1.1 Planning Speech Acts
24.1.2 Implementing Speech Acts
24.2 Understanding Language Strings
24.2.1 Phrase-Structure Grammars
24.2.2 Semantic Analysis
24.2.5 Expanding the Grammar
24.3 Efficient Communication
24.3.1 Use of Context
24.3.2 Use of Knowledge to Resolve Ambiguities
24.4 Natural Language Processing
24.5 Additional Readings and Discussion
Exercises
Agent Architectures
25.1 Three-Level Architectures
25.2 Goal Arbitration
25.5 The Triple-Tower Architecture
25.4 Bootstrapping
25.5 Additional Readings and Discussion
Exercises
9788181471901)pb)
006.3 / NIL/A