Contents and Resources
Use and purpose of code examples
Use and purpose of code examples
All code examples in Prolog and C/C++ are provided for personal and educational use only.
You may modify or distribute the code in source or compiled form for similar purposes so long as the original source is clearly identified.
If you wish to use any of the code examples, in part or whole, for commercial purposes please contact Alan Dix.
Most are written principally with ease of comprehension in mind and are not necessarily the most efficient coding of the algorithm.
In particular, Prolog code, especially the early examples, try to avoid 'clever' Prolog tricks.
However, the nature of the examples, means that sequential code achieved using cuts and mutable store achieved using assert/retract is often necessary.
Code examples are being added incrementally.
If you have any problems with the existing code, or if critical
examples are too slow appearing, please contact Alan Dix
who will try to correct/add to the code as appropriate in a reasonable time!
Some of the prolog examples use predicates defined in the following utility files.
Many of these predicates may already be available on your system either in
libraries or as built-in predicates.
- list.p - list and set processing predicates
- concat/3, length/2, element_at/3
- member/2, count_members/3, add_member/3
- remove_member/3, remove_members/3, remove_list/3
- notsubset/2, subset/2, sameset/2
- union/3, intersect/3, setdiff/3
- sumlist/2, maxlist/2
- range_list/3
- meta.p - meta-logical predicates
- findall/3, findone/2, sumall/3, maxall/3
- retractall/1
- in_range/3
- math.p - mathematical utilities
- max/3, min/3
- fdiv/3 - for Prologs without floating point divide!
- round/2 - may need to be redefined for your Prolog
- cond.p - handles lists of postive/negative conditions
- test_one_cond/2, set_one_cond/3
- test_cond_list/2, set_cond_list/3
AI elsewhere
The
CMU
AI Repository contains code for many AI programs and languages including Terry
Winnograd's original code for SHRDLU
Preface
Introduction
- What is artificial intelligence? 1
- History of artificial intelligence 3
-
You can see more about SHRDLU on Terry
Winnograd's own HCI course pages
- And an online web version of Eliza you can talk to.
- 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
- tbirds.p (Prolog)
- you may have noticed that the characters in this example come from Thunderbirds,
the classic Gerry Anderson television series.
- 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
- prod.p (Prolog)
- 1.7 Network representations 21
- network.p (Prolog)
- 1.8 Structured representations 23
- 1.8.1 Frames 23
- frames.p (Prolog)
- 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
- forback.p (Prolog)
- 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: baysian reasoning)
- 2.4.3 Certainty factors 37
- certf.p (Prolog)
- 2.4.4 Fuzzy reasoning 39
- fuzzy.p (Prolog)
- 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
- additional notes and pseudo-code for ID3
- also notes on extending ID3 to cope with between variable comparisons
- 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 definiton 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 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
- meansend.p (Prolog) means-end analysis
- 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
- blackboard.p
(Prolog) blackboard interpreter
- 10.3.2 Distributed control 239
- 10.3.3 Emergent behaviour 240
- life.p
(Prolog) Conway's Game of Life
- Eric Weisstein's Treasure
Trove of Life has lots of links related to Conway's Game of Life
- 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
Bibliography
Index
maintained by Alan Dix