Artificial Intelligence

by Nilsson

• ISBN13: 9781558604674
• ISBN10: 1558604677
• Format: Hardcover
• Copyright: 1998-04-01
• Publisher: Elsevier Science

Summary

Intelligent agents are employed as the central characters in this new introductory text. Beginning with elementary reactive agents, Nilsson gradually increases their cognitive horsepower to illustrate the most important and lasting ideas in AI. Neural networks, genetic programming, computer vision, heuristic search, knowledge representation and reasoning, Bayes networks, planning, and language understanding are each revealed through the growing capabilities of these agents. The book provides a refreshing and motivating new synthesis of the field by one of AI's master expositors and leading researchers. Artificial Intelligence: A New Synthesis takes the reader on a complete tour of this intriguing new world of AI. * An evolutionary approach provides a unifying theme * Thorough coverage of important AI ideas, old and new * Frequent use of examples and illustrative diagrams * Extensive coverage of machine learning methods throughout the text * Citations to over 500 references * Comprehensive index

Table of Contents

Preface	xix
1 Introduction	1	(18)
1.1 What Is AI?	1	(5)
1.2 Approaches to Artificial Intelligence	6	(2)
1.3 Brief History of AI	8	(3)
1.4 Plan of the Book	11	(3)
1.5 Additional Readings and Discussion	14	(3)
Exercises	17	(2)
I Reactive Machines	19	(96)
2 Stimulus-Response Agents	21	(16)
2.1 Perception and Action	21	(6)
2.1.1 Perception	24	(1)
2.1.2 Action	24	(1)
2.1.3 Boolean Algebra	25	(1)
2.1.4 Classes and Forms of Boolean Functions	26	(1)
2.2 Representing and Implementing Action Functions	27	(6)
2.2.1 Production Systems	27	(2)
2.2.2 Networks	29	(3)
2.2.3 The Subsumption Architecture	32	(1)
2.3 Additional Readings and Discussion	33	(1)
Exercises	34	(3)
3 Neural Networks	37	(22)
3.1 Introduction	37	(1)
3.2 Training Single TLUs	38	(6)
3.2.1 TLU Geometry	38	(1)
3.2.2 Augmented Vectors	39	(1)
3.2.3 Gradient Descent Methods	39	(2)
3.2.4 The Windrow-Hoff Procedure	41	(1)
3.2.5 The Generalized Delta Procedure	41	(2)
3.2.6 The Error-Correction Procedure	43	(1)
3.3 Neural Networks	44	(7)
3.3.1 Motivation	44	(1)
3.3.2 Notation	45	(1)
3.3.3 The Backpropagation Method	46	(2)
3.3.4 Computing Weight Changes in the Final Layer	48	(1)
3.3.5 Computing Changes to the Weights in Intermediate Layers	48	(3)
3.4 Generalization, Accuracy, and Overfitting	51	(3)
3.5 Additional Readings and Discussion	54	(1)
Exercises	55	(4)
4 Machine Evolution	59	(12)
4.1 Evolutionary Computation	59	(1)
4.2 Genetic Programming	60	(9)
4.2.1 Program Representation in GP	60	(2)
4.2.2 The GP Process	62	(3)
4.2.3 Evolving a Wall-Following Robot	65	(4)
4.3 Additional Readings and Discussion	69	(1)
Exercises	69	(2)
5 State Machines	71	(14)
5.1 Representing the Environment by Feature Vectors	71	(2)
5.2 Elman Networks	73	(1)
5.3 Iconic Representations	74	(3)
5.4 Blackboard Systems	77	(3)
5.5 Additional Readings and Discussion	80	(1)
Exercises	80	(5)
6 Robot Vision	85	(30)
6.1 Introduction	85	(1)
6.2 Steering an Automobile	86	(2)
6.3 Two Stages of Robot Vision	88	(3)
6.4 Image Processing	91	(11)
6.4.1 Averaging	91	(2)
6.4.2 Edge Enhancement	93	(3)
6.4.3 Combining Edge Enhancement with Averaging	96	(1)
6.4.4 Region Finding	97	(4)
6.4.5 Using Image Attributes Other Than Intensity	101	(1)
6.5 Scene Analysis	102	(6)
6.5.1 Interpreting Lines and Curves in the Image	103	(3)
6.5.2 Model-Based Vision	106	(2)
6.6 Stereo Vision and Depth Information	108	(2)
6.7 Additional Readings and Discussion	110	(1)
Exercises	111	(4)
II Search in State Spaces	115	(100)
7 Agents That Plan	117	(12)
7.1 Memory Versus Computation	117	(1)
7.2 State-Space Graphs	118	(3)
7.3 Searching Explicit State Spaces	121	(1)
7.4 Feature-Based State Spaces	122	(2)
7.5 Graph Notation	124	(1)
7.6 Additional Readings and Discussion	125	(1)
Exercises	126	(3)
8 Uninformed Search	129	(10)
8.1 Formulating the State Space	129	(1)
8.2 Components of Implicit State-Space Graphs	130	(1)
8.3 Breadth-First Search	131	(2)
8.4 Depth-First or Backtracking Search	133	(2)
8.5 Iterative Deepening	135	(1)
8.6 Additional Readings and Discussion	136	(1)
Exercises	137	(2)
9 Heuristic Search	139	(24)
9.1 Using Evaluation Functions	139	(2)
9.2 A General Graph-Searching Algorithm	141	(14)
9.2.1 Algorithm A*	142	(3)
9.2.2 Admissibility of A*	145	(5)
9.2.3 The Consistency (or Monotone) Condition	150	(3)
9.2.4 Iterative-Deepening A*	153	(1)
9.2.5 Recursive Best-First Search	154	(1)
9.3 Heuristic Functions and Search Efficiency	155	(5)
9.4 Additional Readings and Discussion	160	(1)
Exercises	160	(3)
10 Planning, Acting, and Learning	163	(18)
10.1 The Sense/Plan/Act Cycle	163	(2)
10.2 Approximate Search	165	(7)
10.2.1 Island-Driven Search	166	(1)
10.2.2 Hierarchical Search	167	(2)
10.2.3 Limited-Horizon Search	169	(1)
10.2.4 Cycles	170	(1)
10.2.5 Building Reactive Procedures	170	(2)
10.3 Learning Heuristic Functions	172	(3)
10.3.1 Explicit Graphs	172	(1)
10.3.2 Implicit Graphs	173	(2)
10.4 Rewards Instead of Goals	175	(2)
10.5 Additional Readings and Discussion	177	(1)
Exercises	178	(3)
11 Alternative Search Formulations and Applications	181	(14)
11.1 Assignment Problems	181	(2)
11.2 Constructive Methods	183	(4)
11.3 Heuristic Repair	187	(2)
11.4 Function Optimization	189	(3)
Exercises	192	(2)
12 Adversarial Search	195	(20)
12.1 Two-Agent Games	195	(2)
12.2 The Minimax Procedure	197	(5)
12.3 The Alpha-Beta Procedure	202	(5)
12.4 The Search Efficiency of the Alpha-Beta Procedure	207	(1)
12.5 Other Important Matters	208	(1)
12.6 Games of Chance	208	(2)
12.7 Learning Evaluation Functions	210	(2)
12.8 Additional Readings and Discussion	212	(1)
Exercises	213	(2)
III Knowledge Representation and Reasoning	215	(146)
13 The Propositional Calculus	217	(14)
13.1 Using Constraints on Feature Values	217	(2)
13.2 The Language	219	(1)
13.3 Rules of Inference	220	(1)
13.4 Definition of Proof	221	(1)
13.5 Semantics	222	(4)
13.5.1 Interpretations	222	(1)
13.5.2 The Propositional Truth Table	223	(1)
13.5.3 Satisfiability and Models	224	(1)
13.5.4 Validity	224	(1)
13.5.5 Equivalence	225	(1)
13.5.6 Entailment	225	(1)
13.6 Soundness and Completeness	226	(1)
13.7 The PSAT Problem	227	(1)
13.8 Other Important Topics	228	(1)
13.8.1 Language Distinctions	228	(1)
13.8.2 Metatheorems	228	(1)
13.8.3 Associative Laws	229	(1)
13.8.4 Distributive Laws	229	(1)
Exercises	229	(2)
14 Resolution in the Propositional Calculus	231	(8)
14.1 A New Rule of Inference: Resolution	231	(1)
14.1.1 Clauses as wffs	231	(1)
14.1.2 Resolution on Clauses	231	(1)
14.1.3 Soundness of Resolution	232	(1)
14.2 Converting Arbitrary wffs to Conjunctions of Clauses	232	(1)
14.3 Resolution Refutations	233	(2)
14.4 Resolution Refutation Search Strategies	235	(2)
14.4.1 Ordering Strategies	235	(1)
14.4.2 Refinement Strategies	236	(1)
14.5 Horn Clauses	237	(1)
Exercises	238	(1)
15 The Predicate Calculus	239	(14)
15.1 Motivation	239	(1)
15.2 The Language and Its Syntax	240	(1)
15.3 Semantics	241	(4)
15.3.1 Worlds	241	(1)
15.3.2 Interpretations	242	(1)
15.3.3 Models and Related Notions	243	(1)
15.3.4 Knowledge	244	(1)
15.4 Quantification	245	(1)
15.5 Semantics of Quantifiers	246	(2)
15.5.1 Universal Quantifiers	246	(1)
15.5.2 Existential Quantifiers	247	(1)
15.5.3 Useful Equivalences	247	(1)
15.5.4 Rules of Inference	247	(1)
15.6 Predicate Calculus as a Language for Representing Knowledge	248	(2)
15.6.1 Conceptualizations	248	(1)
15.6.2 Examples	248	(1)
15.7 Additional Readings and Discussion	250	(1)
Exercises	250	(3)
16 Resolution in the Predicate Calculus	253	(16)
16.1 Unification	253	(3)
16.2 Predicate-Calculus Resolution	256	(1)
16.3 Completeness and Soundness	257	(1)
16.4 Converting Arbitrary wffs to Clause Form	257	(3)
16.5 Using Resolution to Prove Theorems	260	(1)
16.6 Answer Extraction	261	(1)
16.7 The Equality Predicate	262	(3)
16.8 Additional Readings and Discussion	265	(1)
Exercises	265	(4)
17 Knowledge-Based Systems	269	(32)
17.1 Confronting the Real World	269	(1)
17.2 Reasoning Using Horn Clauses	270	(5)
17.3 Maintenance in Dynamic Knowledge Bases	275	(5)
17.4 Rule-Based Expert Systems	280	(6)
17.5 Rule Learning	286	(11)
17.5.1 Learning Propositional Calculus Rules	286	(5)
17.5.2 Learning First-Order Logic Rules	291	(4)
17.5.3 Explanation-Based Generalization	295	(2)
17.6 Additional Readings and Discussion	297	(1)
Exercises	298	(3)
18 Representing Commonsense Knowledge	301	(16)
18.1 The Commonsense World	301	(5)
18.1.1 What Is Commonsense Knowledge?	301	(2)
18.1.2 Difficulties in Representing Commonsense Knowledge	303	(1)
18.1.3 The Importance of Commonsense Knowledge	304	(1)
18.1.4 Research Areas	305	(1)
18.2 Time	306	(2)
18.3 Knowledge Representation by Networks	308	(5)
18.3.1 Taxonomic Knowledge	308	(1)
18.3.2 Semantic Networks	309	(1)
18.3.3 Nonmonotonic Reasoning in Semantic Networks	309	(3)
18.3.4 Frames	312	(1)
18.4 Additional Readings and Discussion	313	(1)
Exercises	314	(3)
19 Reasoning with Uncertain Information	317	(26)
19.1 Review of Probability Theory	317	(6)
19.1.1 Fundamental Ideas	317	(3)
19.1.2 Conditional Probabilities	320	(3)
19.2 Probabilistic Inference	323	(2)
19.2.1 A General Method	323	(1)
19.2.2 Conditional Independence	324	(1)
19.3 Bayes Networks	325	(3)
19.4 Patterns of Inference in Bayes Networks	328	(1)
19.5 Uncertain Evidence	329	(1)
19.6 D-Separation	330	(2)
19.7 Probabilistic Inference in Polytrees	332	(6)
19.7.1 Evidence Above	332	(2)
19.7.2 Evidence Below	334	(2)
19.7.3 Evidence Above and Below	336	(1)
19.7.4 A Numerical Example	336	(2)
19.8 Additional Readings and Discussion	338	(1)
Exercises	339	(4)
20 Learning and Acting with Bayes Nets	343	(18)
20.1 Learning Bayes Nets	343	(8)
20.1.1 Known Network Structure	343	(3)
20.1.2 Learning Network Structure	346	(5)
20.2 Probabilistic Inference and Action	351	(7)
20.2.1 The General Setting	351	(1)
20.2.2 An Extended Example	352	(4)
20.2.3 Generalizing the Example	356	(2)
20.3 Additional Readings and Discussion	358	(1)
Exercises	358	(3)
IV Planning Methods Based on Logic	361	(44)
21 The Situation Calculus	363	(10)
21.1 Reasoning about States and Actions	363	(4)
21.2 Some Difficulties	367	(2)
21.2.1 Frame Axioms	367	(2)
21.2.2 Qualifications	369	(1)
21.2.3 Ramifications	369	(1)
21.3 Generating Plans	369	(1)
21.4 Additional Readings and Discussion	370	(1)
Exercises	371	(2)
22 Planning	373	(32)
22.1 STRIPS Planning Systems	373	(12)
22.1.1 Describing States and Goals	373	(1)
22.1.2 Forward Search Methods	374	(2)
22.1.3 Recursive STRIPS	376	(3)
22.1.4 Plans with Run-Time Conditionals	379	(1)
22.1.5 The Sussman Anomaly	380	(1)
22.1.6 Backward Search Methods	381	(4)
22.2 Plan Spaces and Partial-Order Planning	385	(8)
22.3 Hierarchical Planning	393	(3)
22.3.1 ABSTRIPS	393	(2)
22.3.2 Combining Hierarchical and Partial-Order Planning	395	(1)
22.4 Learning Plans	396	(2)
22.5 Additional Readings and Discussion	398	(2)
Exercises	400	(5)
V Communication and Integration	405	(48)
23 Multiple Agents	407	(14)
23.1 Interacting Agents	407	(1)
23.2 Models of Other Agents	408	(4)
23.2.1 Varieties of Models	408	(2)
23.2.2 Simulation Strategies	410	(1)
23.2.3 Simulated Databases	410	(1)
23.2.4 The Intentional Stance	411	(1)
23.3 A Modal Logic of Knowledge	412	(5)
23.3.1 Modal Operators	412	(1)
23.3.2 Knowledge Axioms	413	(2)
23.3.3 Reasoning about Other Agents' Knowledge	415	(2)
23.3.4 Predicting Actions of Other Agents	417	(1)
23.4 Additional Readings and Discussion	417	(1)
Exercises	418	(3)
24 Communication among Agents	421	(22)
24.1 Speech Acts	421	(4)
24.1.1 Planning Speech Acts	423	(1)
24.1.2 Implementing Speech Acts	423	(2)
24.2 Understanding Language Strings	425	(10)
24.2.1 Phrase-Structure Grammars	425	(3)
24.2.2 Semantic Analysis	428	(4)
24.2.3 Expanding the Grammar	432	(3)
24.3 Efficient Communication	435	(2)
24.3.1 Use of Context	435	(1)
24.3.2 Use of Knowledge to Resolve Ambiguities	436	(1)
24.4 Natural Language Processing	437	(3)
24.5 Additional Readings and Discussion	440	(1)
Exercises	440	(3)
25 Agent Architectures	443	(10)
25.1 Three-Level Architectures	444	(2)
25.2 Goal Arbitration	446	(2)
25.3 The Triple-Tower Architecture	448	(1)
25.4 Bootstrapping	449	(1)
25.5 Additional Readings and Discussion	450	(1)
Exercises	450	(3)
Bibliography	453	(40)
Index	493