Artificial Intelligence
By
Dr Zafar. M. Alvi
,Artificial Intelligence (CS607)
Table of Contents:
1 Introduction............................................................................................................................................ 4
1.1 What is Intelligence? .................................................................................................................... 4
1.2 Intelligent Machines ..................................................................................................................... 7
1.3 Formal Definitions for Artificial Intelligence............................................................................... 7
1.4 History and Evolution of Artificial Intelligence ........................................................................... 9
1.5 Applications ............................................................................................................................... 13
1.6 Summary .................................................................................................................................... 14
2 Problem Solving .................................................................................................................................. 15
2.1 Classical Approach..................................................................................................................... 15
2.2 Generate and Test ....................................................................................................................... 15
2.3 Problem Representation.............................................................................................................. 16
2.4 Components of Problem Solving................................................................................................ 17
2.5 The Two-One Problem ............................................................................................................... 18
2.6 Searching.................................................................................................................................... 21
2.7 Tree and Graphs Terminology.................................................................................................... 21
2.8 Search Strategies ........................................................................................................................ 23
2.9 Simple Search Algorithm ........................................................................................................... 24
2.10 Simple Search Algorithm Applied to Depth First Search........................................................... 25
2.11 Simple Search Algorithm Applied to Breadth First Search........................................................ 28
2.12 Problems with DFS and BFS...................................................................................................... 32
2.13 Progressive Deepening ............................................................................................................... 32
2.14 Heuristically Informed Searches ................................................................................................ 37
2.15 Hill Climbing.............................................................................................................................. 39
2.16 Beam Search............................................................................................................................... 43
2.17 Best First Search......................................................................................................................... 45
2.18 Optimal Searches........................................................................................................................ 47
2.19 Branch and Bound ...................................................................................................................... 48
2.20 Improvements in Branch and Bound .......................................................................................... 55
2.21 A* Procedure.............................................................................................................................. 56
2.22 Adversarial Search ..................................................................................................................... 62
2.23 Minimax Procedure .................................................................................................................... 63
2.24 Alpha Beta Pruning .................................................................................................................... 64
2.25 Summary .................................................................................................................................... 71
2.26 Problems..................................................................................................................................... 72
3 Genetic Algorithms.............................................................................................................................. 76
3.1 Discussion on Problem Solving.................................................................................................. 76
3.2 Hill Climbing in Parallel ............................................................................................................ 76
3.3 Comment on Evolution............................................................................................................... 77
3.4 Genetic Algorithm ...................................................................................................................... 77
3.5 Basic Genetic Algorithm ............................................................................................................ 77
3.6 Solution to a Few Problems using GA ....................................................................................... 77
3.7 Eight Queens Problem................................................................................................................ 82
3.8 Problems..................................................................................................................................... 88
4 Knowledge Representation and Reasoning.......................................................................................... 89
4.1 The AI Cycle .............................................................................................................................. 89
4.2 The dilemma............................................................................................................................... 90
4.3 Knowledge and its types............................................................................................................. 90
4.4 Towards Representation ............................................................................................................. 91
4.5 Formal KR techniques................................................................................................................ 93
4.6 Facts ........................................................................................................................................... 94
4.7 Rules........................................................................................................................................... 95
4.8 Semantic networks ..................................................................................................................... 97
4.9 Frames ........................................................................................................................................ 98
4.10 Logic........................................................................................................................................... 98
4.11 Reasoning ................................................................................................................................. 102
4.12 Types of reasoning ................................................................................................................... 102
5 Expert Systems .................................................................................................................................. 111
2
© Copyright Virtual University of Pakistan
,Artificial Intelligence (CS607)
5.1 What is an Expert? ................................................................................................................... 111
5.2 What is an expert system? ........................................................................................................ 111
5.3 History and Evolution .............................................................................................................. 111
5.4 Comparison of a human expert and an expert yystem.............................................................. 112
5.5 Roles of an expert system......................................................................................................... 113
5.6 How are expert systems used?.................................................................................................. 114
5.7 Expert system structure ............................................................................................................ 115
5.8 Characteristics of expert systems ............................................................................................. 121
5.9 Programming vs. knowledge engineering ................................................................................ 122
5.10 People involved in an expert system project ............................................................................ 122
5.11 Inference mechanisms .............................................................................................................. 123
5.12 Design of expert systems.......................................................................................................... 129
6 Handling uncertainty with fuzzy systems .......................................................................................... 145
6.1 Introduction .............................................................................................................................. 145
6.2 Classical sets ............................................................................................................................ 145
6.3 Fuzzy sets ................................................................................................................................. 146
6.4 Fuzzy Logic.............................................................................................................................. 147
6.5 Fuzzy inference system ............................................................................................................ 153
6.6 Summary .................................................................................................................................. 158
6.7 Exercise .................................................................................................................................... 158
7 Introduction to learning...................................................................................................................... 159
7.1 Motivation ................................................................................................................................ 159
7.2 What is learning ?..................................................................................................................... 159
7.3 What is machine learning ? ...................................................................................................... 160
7.4 Why do we want machine learning .......................................................................................... 160
7.5 What are the three phases in machine learning?....................................................................... 160
7.6 Learning techniques available .................................................................................................. 162
7.7 How is it different from the AI we've studied so far?............................................................... 163
7.8 Applied learning ....................................................................................................................... 163
7.9 LEARNING: Symbol-based..................................................................................................... 165
7.10 Problem and problem spaces .................................................................................................... 165
7.11 Concept learning as search ....................................................................................................... 171
7.12 Decision trees learning ............................................................................................................. 176
7.13 LEARNING: Connectionist ..................................................................................................... 181
7.14 Biological aspects and structure of a neuron ........................................................................... 181
7.15 Single perceptron...................................................................................................................... 182
7.16 Linearly separable problems..................................................................................................... 184
7.17 Multiple layers of perceptrons.................................................................................................. 186
7.18 Artificial Neural Networks: supervised and unsupervised ....................................................... 187
7.19 Basic terminologies .................................................................................................................. 187
7.20 Design phases of ANNs............................................................................................................ 188
7.21 Supervised ................................................................................................................................ 190
7.22 Unsupervised ............................................................................................................................ 190
7.23 Exercise .................................................................................................................................... 192
8 Planning ............................................................................................................................................. 195
8.1 Motivation ................................................................................................................................ 195
8.2 Definition of Planning .............................................................................................................. 196
8.3 Planning vs. problem solving ................................................................................................... 197
8.4 Planning language .................................................................................................................... 197
8.5 The partial-order planning algorithm – POP ............................................................................ 198
8.6 POP Example ........................................................................................................................... 199
8.7 Problems................................................................................................................................... 202
9 Advanced Topics ............................................................................................................................... 203
9.1 Computer vision ....................................................................................................................... 203
9.2 Robotics.................................................................................................................................... 204
9.3 Clustering ................................................................................................................................. 205
10 Conclusion .................................................................................................................................... 206
3
© Copyright Virtual University of Pakistan
, Artificial Intelligence (CS607)
Artificial Intelligence
1 Introduction
This booklet is organized as chapters that elaborate on various concepts of
Artificial Intelligence. The field itself is an emerging area of computer sciences
and a lot of work is underway in order to mature the concepts of this field.
In this booklet we will however try to envelop some important aspects and basic
concepts which will help the reader to get an insight into the type of topics that
Artificial Intelligence deals with.
We have used the name of the field i.e. Artificial Intelligence (commonly referred
as AI) without any explanation of the name itself. Let us now look into a simple
but comprehensive way to define the field.
To define AI, let us first try to understand that what is Intelligence?
1.1 What is Intelligence?
If you were asked a simple question; how can we define Intelligence? many of
you would exactly know what it is but most of you won’t exactly be able to define
it. Is it something tangible? We all know that it does exist but what actually it is.
Some of us will attribute intelligence to living beings and would be of the view that
all living species are intelligent. But how about these plants and tress, they are
living species but are they also intelligent? So can we say that Intelligence is a
trait of some living species? Let us try to understand the phenomena of
intelligence by using a few examples.
Consider the following image where a mouse is trying to search a maze in order
to find its way from the bottom left to the piece of cheese in the top right corner of
the image.
This problem can be considered as a common real life problem which we deal
with many times in our life, i.e. finding a path, may be to a university, to a friends
house, to a market, or in this case to the piece of cheese. The mouse tries
various paths as shown by arrows and can reach the cheese by more than one
path. In other words the mouse can find more than one solutions to this problem.
The mouse was intelligent enough to find a solution to the problem at hand.
Hence the ability of problem solving demonstrates intelligence.
Let us consider another problem. Consider the sequence of numbers below:
1, 3, 7, 13, 21, ___
4
© Copyright Virtual University of Pakistan
By
Dr Zafar. M. Alvi
,Artificial Intelligence (CS607)
Table of Contents:
1 Introduction............................................................................................................................................ 4
1.1 What is Intelligence? .................................................................................................................... 4
1.2 Intelligent Machines ..................................................................................................................... 7
1.3 Formal Definitions for Artificial Intelligence............................................................................... 7
1.4 History and Evolution of Artificial Intelligence ........................................................................... 9
1.5 Applications ............................................................................................................................... 13
1.6 Summary .................................................................................................................................... 14
2 Problem Solving .................................................................................................................................. 15
2.1 Classical Approach..................................................................................................................... 15
2.2 Generate and Test ....................................................................................................................... 15
2.3 Problem Representation.............................................................................................................. 16
2.4 Components of Problem Solving................................................................................................ 17
2.5 The Two-One Problem ............................................................................................................... 18
2.6 Searching.................................................................................................................................... 21
2.7 Tree and Graphs Terminology.................................................................................................... 21
2.8 Search Strategies ........................................................................................................................ 23
2.9 Simple Search Algorithm ........................................................................................................... 24
2.10 Simple Search Algorithm Applied to Depth First Search........................................................... 25
2.11 Simple Search Algorithm Applied to Breadth First Search........................................................ 28
2.12 Problems with DFS and BFS...................................................................................................... 32
2.13 Progressive Deepening ............................................................................................................... 32
2.14 Heuristically Informed Searches ................................................................................................ 37
2.15 Hill Climbing.............................................................................................................................. 39
2.16 Beam Search............................................................................................................................... 43
2.17 Best First Search......................................................................................................................... 45
2.18 Optimal Searches........................................................................................................................ 47
2.19 Branch and Bound ...................................................................................................................... 48
2.20 Improvements in Branch and Bound .......................................................................................... 55
2.21 A* Procedure.............................................................................................................................. 56
2.22 Adversarial Search ..................................................................................................................... 62
2.23 Minimax Procedure .................................................................................................................... 63
2.24 Alpha Beta Pruning .................................................................................................................... 64
2.25 Summary .................................................................................................................................... 71
2.26 Problems..................................................................................................................................... 72
3 Genetic Algorithms.............................................................................................................................. 76
3.1 Discussion on Problem Solving.................................................................................................. 76
3.2 Hill Climbing in Parallel ............................................................................................................ 76
3.3 Comment on Evolution............................................................................................................... 77
3.4 Genetic Algorithm ...................................................................................................................... 77
3.5 Basic Genetic Algorithm ............................................................................................................ 77
3.6 Solution to a Few Problems using GA ....................................................................................... 77
3.7 Eight Queens Problem................................................................................................................ 82
3.8 Problems..................................................................................................................................... 88
4 Knowledge Representation and Reasoning.......................................................................................... 89
4.1 The AI Cycle .............................................................................................................................. 89
4.2 The dilemma............................................................................................................................... 90
4.3 Knowledge and its types............................................................................................................. 90
4.4 Towards Representation ............................................................................................................. 91
4.5 Formal KR techniques................................................................................................................ 93
4.6 Facts ........................................................................................................................................... 94
4.7 Rules........................................................................................................................................... 95
4.8 Semantic networks ..................................................................................................................... 97
4.9 Frames ........................................................................................................................................ 98
4.10 Logic........................................................................................................................................... 98
4.11 Reasoning ................................................................................................................................. 102
4.12 Types of reasoning ................................................................................................................... 102
5 Expert Systems .................................................................................................................................. 111
2
© Copyright Virtual University of Pakistan
,Artificial Intelligence (CS607)
5.1 What is an Expert? ................................................................................................................... 111
5.2 What is an expert system? ........................................................................................................ 111
5.3 History and Evolution .............................................................................................................. 111
5.4 Comparison of a human expert and an expert yystem.............................................................. 112
5.5 Roles of an expert system......................................................................................................... 113
5.6 How are expert systems used?.................................................................................................. 114
5.7 Expert system structure ............................................................................................................ 115
5.8 Characteristics of expert systems ............................................................................................. 121
5.9 Programming vs. knowledge engineering ................................................................................ 122
5.10 People involved in an expert system project ............................................................................ 122
5.11 Inference mechanisms .............................................................................................................. 123
5.12 Design of expert systems.......................................................................................................... 129
6 Handling uncertainty with fuzzy systems .......................................................................................... 145
6.1 Introduction .............................................................................................................................. 145
6.2 Classical sets ............................................................................................................................ 145
6.3 Fuzzy sets ................................................................................................................................. 146
6.4 Fuzzy Logic.............................................................................................................................. 147
6.5 Fuzzy inference system ............................................................................................................ 153
6.6 Summary .................................................................................................................................. 158
6.7 Exercise .................................................................................................................................... 158
7 Introduction to learning...................................................................................................................... 159
7.1 Motivation ................................................................................................................................ 159
7.2 What is learning ?..................................................................................................................... 159
7.3 What is machine learning ? ...................................................................................................... 160
7.4 Why do we want machine learning .......................................................................................... 160
7.5 What are the three phases in machine learning?....................................................................... 160
7.6 Learning techniques available .................................................................................................. 162
7.7 How is it different from the AI we've studied so far?............................................................... 163
7.8 Applied learning ....................................................................................................................... 163
7.9 LEARNING: Symbol-based..................................................................................................... 165
7.10 Problem and problem spaces .................................................................................................... 165
7.11 Concept learning as search ....................................................................................................... 171
7.12 Decision trees learning ............................................................................................................. 176
7.13 LEARNING: Connectionist ..................................................................................................... 181
7.14 Biological aspects and structure of a neuron ........................................................................... 181
7.15 Single perceptron...................................................................................................................... 182
7.16 Linearly separable problems..................................................................................................... 184
7.17 Multiple layers of perceptrons.................................................................................................. 186
7.18 Artificial Neural Networks: supervised and unsupervised ....................................................... 187
7.19 Basic terminologies .................................................................................................................. 187
7.20 Design phases of ANNs............................................................................................................ 188
7.21 Supervised ................................................................................................................................ 190
7.22 Unsupervised ............................................................................................................................ 190
7.23 Exercise .................................................................................................................................... 192
8 Planning ............................................................................................................................................. 195
8.1 Motivation ................................................................................................................................ 195
8.2 Definition of Planning .............................................................................................................. 196
8.3 Planning vs. problem solving ................................................................................................... 197
8.4 Planning language .................................................................................................................... 197
8.5 The partial-order planning algorithm – POP ............................................................................ 198
8.6 POP Example ........................................................................................................................... 199
8.7 Problems................................................................................................................................... 202
9 Advanced Topics ............................................................................................................................... 203
9.1 Computer vision ....................................................................................................................... 203
9.2 Robotics.................................................................................................................................... 204
9.3 Clustering ................................................................................................................................. 205
10 Conclusion .................................................................................................................................... 206
3
© Copyright Virtual University of Pakistan
, Artificial Intelligence (CS607)
Artificial Intelligence
1 Introduction
This booklet is organized as chapters that elaborate on various concepts of
Artificial Intelligence. The field itself is an emerging area of computer sciences
and a lot of work is underway in order to mature the concepts of this field.
In this booklet we will however try to envelop some important aspects and basic
concepts which will help the reader to get an insight into the type of topics that
Artificial Intelligence deals with.
We have used the name of the field i.e. Artificial Intelligence (commonly referred
as AI) without any explanation of the name itself. Let us now look into a simple
but comprehensive way to define the field.
To define AI, let us first try to understand that what is Intelligence?
1.1 What is Intelligence?
If you were asked a simple question; how can we define Intelligence? many of
you would exactly know what it is but most of you won’t exactly be able to define
it. Is it something tangible? We all know that it does exist but what actually it is.
Some of us will attribute intelligence to living beings and would be of the view that
all living species are intelligent. But how about these plants and tress, they are
living species but are they also intelligent? So can we say that Intelligence is a
trait of some living species? Let us try to understand the phenomena of
intelligence by using a few examples.
Consider the following image where a mouse is trying to search a maze in order
to find its way from the bottom left to the piece of cheese in the top right corner of
the image.
This problem can be considered as a common real life problem which we deal
with many times in our life, i.e. finding a path, may be to a university, to a friends
house, to a market, or in this case to the piece of cheese. The mouse tries
various paths as shown by arrows and can reach the cheese by more than one
path. In other words the mouse can find more than one solutions to this problem.
The mouse was intelligent enough to find a solution to the problem at hand.
Hence the ability of problem solving demonstrates intelligence.
Let us consider another problem. Consider the sequence of numbers below:
1, 3, 7, 13, 21, ___
4
© Copyright Virtual University of Pakistan
