resources and detailed contents

Introduction

What is artificial intelligence? 1
History of artificial intelligence 3
The future for AI 7

1  Knowledge in AI

1.1 Overview 9
1.2 Introduction 9
1.3 Representing knowledge 10
1.4 Metrics for assessing knowledge representation schemes 13
1.5 Logic representations 14
1.6 Procedural representation 17
1.6.1 The database 17
1.6.2 The production rules 18
1.6.3 The interpreter 18
1.6.4 An example production system: making a loan 19
1.7 Network representations 21
1.8 Structured representations 23
1.8.1 Frames 23
1.8.2 Scripts 24
1.9 General knowledge 26
1.10 The frame problem 27
1.11 Knowledge elicitation 28
1.12 Summary 28
1.13 Exercises 29
1.14 Recommended further reading 30

2  Reasoning

2.1 Overview 31
2.2 What is reasoning? 31
2.3 Forward and backward reasoning 33
2.4 Reasoning with uncertainty 34
2.4.1 Non-monotonic reasoning 35
  • tms.p (Prolog: TMS – truth maintenance system)
2.4.2 Probabilistic reasoning 36
  • bayes.p (Prolog: bayesian reasoning)
2.4.3 Certainty factors 37
2.4.4 Fuzzy reasoning 39
2.4.5 Reasoning by analogy 40
2.4.6 Case-based reasoning 40
2.5 Summary 43
2.6 Exercises 43
2.7 Recommended further reading 44

3  Search

3.1 Introduction 45
3.1.1 Types of problem 45
3.1.2 Structuring the search space 49
  • gentest.p (Prolog) generate and test for magic squares
  • prune.p (Prolog) pruning partial magic square solutions
  • hanext.p (Prolog) representation of Towers of Hanoi graph
  • hanint.p (Prolog) alternative representation of Towers of Hanoi graph
  • See also proof.p (Prolog) at 3.2.6 for addition graph
3.2 Exhaustive search and simple pruning 55
3.2.1 Depth and breadth first search 55
3.2.2 Comparing depth and breadth first searches 58
3.2.3 Programming and space costs 59
3.2.4 Iterative deepening and broadening 60
3.2.5 Finding the best solution — branch and bound 61
3.2.6 Graph search 62
  • proof.p (Prolog) arithmetic proof using closed lists
3.3 Heuristic search 63
3.3.1 Hill climbing and best first — goal-directed search 64
3.3.2 Finding the best solution — the A* algorithm 65
3.3.3 Inexact search 68
3.4 Knowledge-rich search 71
3.4.1 Constraint satisfaction 72
3.5 Summary 74
3.6 Exercises 75
3.7 Recommended further reading 75

4  Machine learning

4.1 Overview 77
4.2 Why do we want machine learning? 77
4.3 How machines learn 78
4.3.1 Phases of machine learning 79
4.3.2 Rote learning and the importance of generalization 80
4.3.3 Inputs to training 81
4.3.4 Outputs of training 82
4.3.5 The training process 83
4.4 Deductive learning 84
4.5 Inductive learning 85
4.5.1 Version spaces 86
page 88, errata 5/11/97
4.5.2 ID3 and decision trees 90
4.5.3 Rule induction 95
4.6 Explanation-based learning 96
4.7 Example: Query-by-Browsing 97
4.7.1 What the user sees 97
4.7.2 How it works 99
4.7.3 Problems 99
4.8 Summary 99
4.9 Recommended further reading 100

5  Game playing

5.1 Overview 101
5.2 Introduction 101
5.3 Characteristics of game playing 103
5.4 Standard games 104
5.4.1 A simple game tree 104
5.4.2 Heuristics and minimax search 105
5.4.3 Horizon problems 107
5.4.4 Alpha–beta pruning 108
5.4.5 The imperfect opponent 109
5.5 Non-zero-sum games and simultaneous play 109
5.5.1 The prisoner’s dilemma 110
5.5.2 Searching the game tree 111
5.5.3 No alpha–beta pruning 112
5.5.4 Pareto-optimality 113
5.5.5 Multi-party competition and co-operation 114
5.6 The adversary is life! 114
page 115, errata 10/1/2000
5.7 Probability 116
page 117, errata 10/1/2000
5.8 Summary 117
5.9 Exercises 118
5.10 Recommended further reading 119

6  Expert systems

6.1 Overview 121
6.2 What are expert systems? 121
6.3 Uses of expert systems 122
6.4 Architecture of an expert system 123
6.4.1 Explanation facility 124
6.4.2 Dialogue component 126
6.5 Examples of four expert systems 127
6.5.1 Example 1: MYCIN 127
6.5.2 Example 2: PROSPECTOR 128
6.5.3 Example 3: DENDRAL 128
6.5.4 Example 4: XCON 129
6.6 Building an expert system 129
6.6.1 Knowledge elicitation 130
Techniques for knowledge elicitation 130
Tool support for knowledge elicitation 132
6.6.2 Representing the knowledge 132
Expert system shells 132
High-level programming languages 133
Selecting a tool 133
6.7 Limitations of expert systems 134
6.8 Hybrid expert systems 135
6.9 Summary 135
6.10 Exercises 135
6.11 Recommended further reading 136

7  Natural language understanding

7.1 Overview 137
7.2 What is natural language understanding? 137
7.3 Why do we need natural language understanding? 138
7.4 Why is natural language understanding difficult? 138
7.5 An early attempt at natural language understanding: SHRDLU 140
7.6 How does natural language understanding work? 141
7.7 Syntactic analysis 143
7.7.1 Grammars 144
7.7.2 An example: generating a grammar fragment 145
7.7.3 Transition networks 147
7.7.4 Context-sensitive grammars 150
7.7.5 Feature sets 152
7.7.6 Augmented transition networks 153
7.8 Semantic analysis 153
7.8.1 Semantic grammars 154
An example: a database query interpreter revisited 154
7.8.2 Case grammars 155
7.9 Pragmatic analysis 158
7.9.1 Speech acts 159
7.10 Summary 160
7.11 Exercises 160
7.12 Recommended further reading 161
7.13 Solution to SHRDLU problem 161

8  Computer vision

The Prolog examples in this chapter use images coded in two formats a simple list of lists representation defined in image.p, and a more complex representation using Prolog meta-logical mechanisms defined in gimage.p. The former is used for input and output, but the latter makes the definition of filters etc. easier. The actual images used in the chapter are held in a file eximages.p.

If you are doing image processing, Prolog is not the best language choice! However, we have included the Prolog examples to have a common language throughout.

8.1 Overview 163
8.2 Introduction 163
8.2.1 Why computer vision is difficult 163
8.2.2 Phases of computer vision 164
8.3 Digitization and signal processing 165
8.3.1 Digitizing images 165
8.3.2 Thresholding 166
  • threshold.p (Prolog) thresholding of grey-scale images
8.3.3 Digital filters 169
  • filter.p (Prolog) linear filters including simple gradient filters
Linear filters 169
Smoothing 170
Gaussian filters 171
Practical considerations 172
8.4 Edge detection 173
8.4.1 Identifying edge pixels 173
Gradient operators 174
Robert’s operator 174
Sobel’s operator 176
Laplacian operator 178
Successive refinement and Marr’s primal sketch 179
8.4.2 Edge following 180
8.5 Region detection 182
8.5.1 Region growing 182
8.5.2 The problem of texture 183
8.5.3 Representing regions — quad-trees 183
8.5.4 Computational problems 184
8.6 Reconstructing objects 185
8.6.1 Inferring three-dimensional features 185
Problems with labelling 188
8.6.2 Using properties of regions 189
8.7 Identifying objects 191
8.7.1 Using bitmaps 191
8.7.2 Using summary statistics 193
8.7.3 Using outlines 194
8.7.4 Using paths 195
8.8 Multiple images 197
8.8.1 Stereo vision 197
8.8.2 Moving pictures 199
8.9 Summary 200
8.10 Exercises 201
8.11 Recommended further reading 202

9  Planning and robotics

The observant reader may have noticed an uncanny resemblance between some of the robots depicted in this chapter and Daleks, the most famous adversaries of Dr Who.

Read this BBC article about a UN report in on the rise of domestic robots.

9.1 Overview 203
9.2 Introduction 203
9.2.1 Friend or foe? 203
9.2.2 Different kinds of robots 204
9.3 Global planning 205
9.3.1 Planning actions — means-ends analysis 205
9.3.2 Planning routes — configuration spaces 208
9.4 Local planning 210
9.4.1 Local planning and obstacle avoidance 210
9.4.2 Finding out about the world 213
9.5 Limbs, legs and eyes 216
9.5.1 Limb control 216
9.5.2 Walking — on one, two or more legs 220
9.5.3 Active vision 221
9.6 Practical robotics 223
9.6.1 Controlling the environment 223
9.6.2 Safety and hierarchical control 224
9.7 Summary 225
9.8 Exercises 226
9.9 Recommended further reading 227

10  Agents

10.1 Overview 229
10.2 Software agents 229
10.2.1 The rise of the agent 230
10.2.2 Triggering actions 231
10.2.3 Watching and learning 232
10.2.4 Searching for information 234
10.3 Co-operating agents and distributed AI 236
10.3.1 Blackboard architectures 236
10.3.2 Distributed control 239
10.3.3 Emergent behaviour 240
10.4 Summary 242
10.5 Exercises 242
10.6 Recommended further reading 244

11  Models of the mind

11.1 Overview 245
11.2 Introduction 245
11.3 What is the human mind? 245
11.4 Production system models 247
11.4.1 ACT* 247
11.4.2 SOAR 249
11.5 Connectionist models of cognition 251
11.5.1 Multi-layer perceptron 251
page 255, errata
17/1/2000
11.5.2 Associative memories 256
11.5.3 Kohonen self-organizing networks 258
  • kohonen a C package of programs implementing Kohonen nets
11.6 Summary 258
11.7 Exercises 258
11.8 Recommended further reading 259
11.9 Notes 260

12  Epilogue: philosophical and sociological issues

12.1 Overview 261
12.2 Intelligent machines or engineering tools? 261
12.3 What is intelligence? 262
12.4 Computational argument vs.Searle’s Chinese Room 263
12.5 Who is responsible? 264
12.6 Morals and emotions 264
12.7 Social implications 265
12.8 Summary 266
12.9 Recommended further reading 266

Index

Bibliography