CS607 Handouts by VUBuddy

Table of Contents:

1. 1
2. 2
3. 3
4. 4 History and Evolution of Artificial Intelligence...........................................................................9
5. 5 Applications ............................................................................................................................... 13
6. 6 Summary .................................................................................................................................... 14 Problem Solving .................................................................................................................................. 15
7. 1 Classical Approach..................................................................................................................... 15
8. 2 Generate and Test....................................................................................................................... 15
9. 3 Problem Representation.............................................................................................................. 16
10. 4 Components of Problem Solving................................................................................................ 17
11. 5 The Two-One Problem............................................................................................................... 18
12. 6 Searching.................................................................................................................................... 21
13. 7 Tree and Graphs Terminology.................................................................................................... 21
14. 8 Search Strategies ........................................................................................................................ 23
15. 9 Simple Search Algorithm ........................................................................................................... 24
16. 10 Simple Search Algorithm Applied to Depth First Search........................................................... 25
17. 11 Simple Search Algorithm Applied to Breadth First Search........................................................ 28
18. 12 Problems with DFS and BFS...................................................................................................... 32
19. 13 Progressive Deepening............................................................................................................... 32
20. 14 Heuristically Informed Searches ................................................................................................ 37
21. 15 Hill Climbing.............................................................................................................................. 39
22. 16 Beam Search............................................................................................................................... 43
23. 17 Best First Search......................................................................................................................... 45
24. 18 Optimal Searches........................................................................................................................ 47
25. 19 Branch and Bound...................................................................................................................... 48
26. 20 Improvements in Branch and Bound.......................................................................................... 55
27. 21 A* Procedure.............................................................................................................................. 56
28. 22 Adversarial Search ..................................................................................................................... 62
29. 23 Minimax Procedure .................................................................................................................... 63
30. 24 Alpha Beta Pruning .................................................................................................................... 64
31. 25 Summary .................................................................................................................................... 71
32. 26 Problems..................................................................................................................................... 72 Genetic Algorithms.............................................................................................................................. 76
33. 1 Discussion on Problem Solving.................................................................................................. 76
34. 2 Hill Climbing in Parallel ............................................................................................................ 76
35. 3 Comment on Evolution............................................................................................................... 77
36. 4 Genetic Algorithm...................................................................................................................... 77
37. 5 Basic Genetic Algorithm ............................................................................................................ 77
38. 6 Solution to a Few Problems using GA ....................................................................................... 77
39. 7 Eight Queens Problem................................................................................................................ 82
40. 8 Problems..................................................................................................................................... 88 Knowledge Representation and Reasoning.......................................................................................... 89
41. 1 The AI Cycle .............................................................................................................................. 89
42. 2 The dilemma............................................................................................................................... 90
43. 3 Knowledge and its types............................................................................................................. 90
44. 4 Towards Representation ............................................................................................................. 91
45. 5 Formal KR techniques................................................................................................................ 93
46. 6 Facts ........................................................................................................................................... 94
47. 7 Rules........................................................................................................................................... 95
48. 8 Semantic networks ..................................................................................................................... 97
49. 9 Frames........................................................................................................................................ 98
50. 10 Logic........................................................................................................................................... 98
51. 11 Reasoning................................................................................................................................. 102
52. 12 Types of reasoning ................................................................................................................... 102 Expert Systems .................................................................................................................................. 111
53. 1 What is an Expert? ................................................................................................................... 111
54. 2 What is an expert system? ........................................................................................................ 111
55. 3 History and Evolution .............................................................................................................. 111
56. 4 Comparison of a human expert and an expert yystem.............................................................. 112
57. 5 Roles of an expert system......................................................................................................... 113
58. 6 How are expert systems used?.................................................................................................. 114
59. 7 Expert system structure ............................................................................................................ 115
60. 8 Characteristics of expert systems ............................................................................................. 121
61. 9 Programming vs. knowledge engineering ................................................................................ 122
62. 10 People involved in an expert system project ............................................................................ 122
63. 11 Inference mechanisms .............................................................................................................. 123
64. 12 Design of expert systems.......................................................................................................... 129 Handling uncertainty with fuzzy systems .......................................................................................... 145
65. 1
66. 2 Classical sets ............................................................................................................................ 145
67. 3 Fuzzy sets ................................................................................................................................. 146
68. 4 Fuzzy Logic.............................................................................................................................. 147
69. 5 Fuzzy inference system ............................................................................................................ 153
70. 6 Summary .................................................................................................................................. 158
71. 7 Exercise .................................................................................................................................... 158 Introduction to learning...................................................................................................................... 159
72. 1 Motivation ................................................................................................................................ 159
73. 2 What is learning ?..................................................................................................................... 159
74. 3 What is machine learning ? ...................................................................................................... 160
75. 4 Why do we want machine learning .......................................................................................... 160
76. 5 What are the three phases in machine learning?....................................................................... 160
77. 6 Learning techniques available .................................................................................................. 162
78. 7 How is it different from the AI we've studied so far?............................................................... 163
79. 8 Applied learning....................................................................................................................... 163
80. 9 LEARNING: Symbol-based..................................................................................................... 165
81. 10 Problem and problem spaces.................................................................................................... 165
82. 11 Concept learning as search ....................................................................................................... 171
83. 12 Decision trees learning ............................................................................................................. 176
84. 13 LEARNING: Connectionist ..................................................................................................... 181
85. 14 Biological aspects and structure of a neuron ........................................................................... 181
86. 15 Single perceptron...................................................................................................................... 182
87. 16 Linearly separable problems..................................................................................................... 184
88. 17 Multiple layers of perceptrons.................................................................................................. 186
89. 18 Artificial Neural Networks: supervised and unsupervised ....................................................... 187
90. 19 Basic terminologies .................................................................................................................. 187
91. 20 Design phases of ANNs............................................................................................................ 188
92. 21 Supervised ................................................................................................................................ 190
93. 22 Unsupervised............................................................................................................................ 190
94. 23 Exercise .................................................................................................................................... 192 Planning ............................................................................................................................................. 195
95. 1 Motivation ................................................................................................................................ 195
96. 2 Definition of Planning.............................................................................................................. 196
97. 3 Planning vs. problem solving ................................................................................................... 197
98. 4 Planning language .................................................................................................................... 197
99. 5 The partial-order planning algorithm – POP ............................................................................ 198
100. 6 POP Example ........................................................................................................................... 199
101. 7 Problems................................................................................................................................... 202 Advanced Topics ............................................................................................................................... 203
102. 1 Computer vision ....................................................................................................................... 203
103. 2 Robotics.................................................................................................................................... 204
104. 3 Clustering ................................................................................................................................. 205 Conclusion .................................................................................................................................... 206

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?

Q1. 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, ___