人工智能:一种现代方法(英文版)

Ⅰ Artificial Intelligence　1

1　Introduction　3
1.1　What Is AI?　4
?Acting humanly: The Turing Test approach　5
?Thinking humanly: The cognitive modelling approach　6
?Thinking rationally: The laws of thought approach　6
?Acting rationally: The rational agent approach　7
1.2　The Foundations of Artificial Intelligence　8
?Philosophy(428 B.C.-present)　8
?Mathematics(c.800-present)　11
?Psychology (1879-present)　12
?Computer engineering(1940-present)　14
?Linguistics(1957-present)　15
1.3　The History of Artificial Intelligence　16
?The gestation of artificial Intelligence(1943-1956)　16
?Early enthusiasm, great expectations(1952-1969)　17
?A dose of reality(1966-1974)　20
?Knowledge-based systems: The key to power?(1969-1979)　22
?AI becomes an Industry(1980-1988)　24
?The return of neural networks(1986-present)　24
?Recent events(1987-present)　25
1.4　The State of the Art　26
1.5　Summary　27
Bibliographical and Historical Notes　28
Exercises　28

2　Intelligent Agents　31
2.1　Introduction　31
2.2　How Agents Should Act　31
?The Ideal mapping from percept sequences to actions　34
?Autonomy　35
2.3　Structure of Intelligent Agents　35
?Agent programs　37
?Why not just look up the answers?　38
?An example　39
?Simple reflex agents　40
?Agents that keep track of the world　41
?Goal-based agents　42
?Utility-based agents　44
2.4　Environments　45
?Properties of environments　46
?Environment programs　47
2.5　Summary　49
?Bibliographical and Historical Notes　50
?Exercises　50

Ⅱ　Problem-solving　53

3　Solving Problems by Searching　55
3.1　Problem-Solving Agents　55
3.2　Formulating Problems　57
?Knowledge and problem types　58
?Well-defined problems and solutions　60
?Measuring problem-solving performance　61
?Choosing states and actions　61
3.3　Example Problems　63
?Toy Problems　63
?Real-world problems　68
3.4　Searching for Solutions　70
?Generating action sequences　70
?Data structures for search trees　72
3.5　Search Strategies　73
?Breadth-first search　74
?Uniform cost search　75
?Depth-first search　77
?Depth-limited search　78
?Iterative deepening search　78
?Bidirectional search　80
?Comparing search strategies　81
3.6　Avoiding Repeated States　82
3.7　Constraint Satisfaction Search　83
3.8　Summary　85
Bibliographical and Historical Notes　86
Exercises　87

4　Informed Search Methods　92
4.1　Best-First Search　92
?Minimize estimated cost to reach a goal:Greedy Search　93
?Minimizing the total path cost: A* search　96
4.2　Heuristic Functions　101
?The effect of heuristic accuracy on performance　102
?Inventing heuristic functions　103
?Heuristics for constraint satisfaction problems　104
4.3　Memory bounded Search　106
?Iterative deepening A* search (IDA*)　106
?SMA* search　107
4.4　Iterative Improvement Algorithms　111
?Hill-climbing search　111
?Simulated annealing　113
?Applications in constraint Satisfaction problems　114
4.5　Summary　115
Bibliographical and Historical Notes　115
Exercises　118

5　Game Playing　122
5.1　Introduction: games as Search Problems　122
5.2　Perfect Decisions in Two-Person Games　123
5.3　Imperfect Decisions　126
?Evaluation functions　127
?Cutting off search　129
5.4　Alpha-Beta Pruning　129
?Effectiveness of alpha-beta pruning　131
5.5　Games That Include an Element of Chance　133
?Position evaluation in games with chance nodes　135
?Complexity of expectiminimax　135
5.6　State-of-the-Art Game Programs　136
?Chess　137
?Checkers or Draughts　138
?Othello　138
?Backgammon　139
?Go 139
5.7　Discussion　139
5.8　Summary　141
Bibliographical and Historical Notes　141
Exercises　145

Ⅲ　Knowledge and reasoning　149

6　Agents that Reason Logically　151
6.1　A Knowledge-Based Agent　151
6.2　The Wumpus World Environment　153
?Specifying the environment　154
?Acting and reasoning in the wumpus world　155
6.3　Representation, Reasoning, and Logic　157
?Representation　160
?Inference　163
?Logics　165
6.4　Propositional Logic: A Very Simple Logic　166
?Syntax　166
?Semantics　168
?Validity and inference　169
?Models　170
?Rules of inference for propositional logic　171
?Complexity of propositional inference　173
6.5　An Agent for the Wumpus World　174
?The knowledge base　174
?Finding the wumpus　175
?Translating knowledge into action　176
?Problems with the propositional agent　176
6.6　Summary　178
Bibliographical and Historical Notes　178
Exercises　180

7　First-Order Logic　185
7.1　Syntax and Semantics　186
?Terms　188
?Atomic sentences　189
?Complex sentences　189
?Quantifiers　189
?Equality　193
7.2　Extensions and Notational Variations　194
?Higher-order logic　195
?Functional and predicate expressions using the λ operator　195
?The uniqueness quantifier Э!　196
?The uniqueness operator ι　196
?Notational variations　196
7.3　Using First-Order Logic　197
?The kinship domain　197
?Axioms, definitions, and theorems　198
?The domain of sets　199
?Special notations for sets, lists and arithmetic　200
?Asking questions and getting answers　200
7.4　Logical Agents for the Wumpus World　201
7.5　A Simple Reflex Agent　202
Limitations of simple reflex agents　203
7.6　Representing Change in the World　203
?Situation calculus　204
?Keeping track of location　206
7.7　Deducing Hidden Properties of the World　208
7.8　Preferences Among Actions　210
7.9　Toward a Goal-Based Agent　211
7.10　Summary　211
Bibliographical and Historical Notes　212
Exercises　213

8　Building a knowledge Base　217
8.1　Properties of Good and Bad Knowledge Bases　218
8.2　Knowledge Engineering　221
8.3　The Electronic Circuits Domain　223
?Decide what to talk about　223
?Decide on a vocabulary　224
?Encode general rules　225
?Encode the specific instance　225
?Pose queries to the inference procedure　226
8.4　General Ontology　226
?Representing Categories　229
?Measures　231
?Composite objects　233
?Representing change with events　234
?Times, intervals, and actions　238
?Objects revisited　240
?Substances and objects　241
?Mental events and mental objects　243
?Knowledge and action　247
8.5　The Grocery Shopping World　247
?Complete description of the shopping simulation　248
?Organizing knowledge　249
?Menu-planning　249
?Navigating　252
?Gathering　253
?Communicating　254
?Paying　256
8.6　Summary　256
Bibliographical and Historical Notes　256
Exercises　261

9　Inference in First-Order Logic　265
9.1　Inference Rules Involving Quantifiers　265
9.2　An Example Proof　266
9.3　Generalized Modus Ponens　269
?Canonical form　270
?Unification　270
?Sample proof revisited　271
9.4　Forward and Backward Chaining　272
?Forward-chaining algorithm　273
?Backward-chaining algorithm　275
9.5　Completeness　276
9.6　Resolution: A Complete Inference Procedure　277
?The resolution inference rule　278
?Canonical forms for resolution　278
?Resolution Proofs　279
?Conversion to Normal Form　281
?Example proof　282
?Dealing with equality　284
?Resolution strategies　284
9.7　Completeness of resolution　286
9.8　Summary　290
Bibliographical and Historical Notes　291
Exercises　294

10　Logical Reasoning Systens　297
10.1　Introduction　297
10.2　Indexing, Retrieval, and Unification　299
?Implementing sentences and terms　299
?Store and fetch　299
?Table-based indexing　300
?Tree-based indexing　301
?The unification algorithm　302
10.3　Logic Programming Systems　304
?The Prolog language　304
?Im