Introduction to Artificial Intelligencee

Introduction to Artificial Intelligence

1. Unit-II- Artificial Intelligence

2. Contents Introduction & Concept of AI Applications of AI Artificial Intelligence, Intelligent Systems, Knowledge –based Systems, AI Techniques Early work in AI & related fields Defining AI problems as a State Space Search Search and Control Strategies Problem Characteristics AI Problem: Water Jug Problem, Tower of Hanoi, Missionaries & Cannibal Problem Dr. Bharati Kawade RTIT MITACSC 2

3. Introduction & Concept of AI In today's world, technology is growing very fast, and we are getting in touch with different new technologies day by day. One of the booming technologies of computer science is Artificial Intelligence which is ready to create a new revolution in the world by making intelligent machines. The Artificial Intelligence is now all around us. It is currently working with a variety of subfields, ranging from general to specific, such as self-driving cars, playing chess, proving theorems, playing music, Painting, etc. Dr. Bharati Kawade RTIT MITACSC 3

4. Introduction & Concept of AI cont.. AI is one of the fascinating and universal fields of Computer science which has a great scope in future. AI holds a tendency to cause a machine to work as a human. Artificial Intelligence is composed of two words  Artificial  and  Intelligence , where Artificial defines  "man-made,"  and intelligence defines  "thinking power“. AI means  "a man-made thinking power." Dr. Bharati Kawade RTIT MITACSC 4

5. Introduction & Concept of AI cont.. AI can be defined as "It is a branch of computer science by which we can create intelligent machines which can behave like a human, think like humans, and able to make decisions."  Artificial Intelligence exists when a machine can have human based skills such as learning, reasoning, and solving problems Dr. Bharati Kawade RTIT MITACSC 5

6. Introduction & Concept of AI cont.. Why Artificial Intelligence? With the help of AI, you can create such software or devices which can solve real-world problems very easily and with accuracy such as health issues, marketing, traffic issues, etc. With the help of AI, you can create your personal virtual Assistant, such as Cortana , Google Assistant, Siri , etc. With the help of AI, you can build such Robots which can work in an environment where survival of humans can be at risk. AI opens a path for other new technologies, new devices, and new Opportunities. Dr. Bharati Kawade RTIT MITACSC 6

7. Introduction & Concept of AI cont.. Goals of Artificial Intelligence Following are the main goals of Artificial Intelligence: Replicate human intelligence Solve Knowledge-intensive tasks An intelligent connection of perception and action Building a machine which can perform tasks that requires human intelligence such as: Proving a theorem Playing chess Plan some surgical operation Driving a car in traffic Creating some system which can exhibit intelligent behaviour, learn new things by itself, demonstrate, explain, and can advise to its user. Dr. Bharati Kawade RTIT MITACSC 7

8. Introduction & Concept of AI cont.. Advantages of Artificial Intelligence Following are some main advantages of Artificial Intelligence: High Accuracy with less errors:  AI machines or systems are prone to less errors and high accuracy as it takes decisions as per pre-experience or information. High-Speed:  AI systems can be of very high-speed and fast-decision making, because of that AI systems can beat a chess champion in the Chess game. High reliability:  AI machines are highly reliable and can perform the same action multiple times with high accuracy. Useful for risky areas:  AI machines can be helpful in situations such as defusing a bomb, exploring the ocean floor, where to employ a human can be risky. Dr. Bharati Kawade RTIT MITACSC 8

9. Introduction & Concept of AI cont.. Advantages of Artificial Intelligence cont.. Digital Assistant:  AI can be very useful to provide digital assistant to the users such as AI technology is currently used by various E-commerce websites to show the products as per customer requirement. Useful as a public utility:  AI can be very useful for public utilities such as a self-driving car which can make our journey safer and hassle-free, facial recognition for security purpose, Natural language processing to communicate with the human in human-language, etc. Dr. Bharati Kawade RTIT MITACSC 9

10. Introduction & Concept of AI cont.. Disadvantages of Artificial Intelligence cont.. High Cost:  The hardware and software requirement of AI is very costly as it requires lots of maintenance to meet current world requirements. Can't think out of the box:  Even we are making smarter machines with AI, but still they cannot work out of the box, as the robot will only do that work for which they are trained, or programmed. No feelings and emotions:  AI machines can be an outstanding performer, but still it does not have the feeling so it cannot make any kind of emotional attachment with human, and may sometime be harmful for users if the proper care is not taken. Dr. Bharati Kawade RTIT MITACSC 10

11. Introduction & Concept of AI cont.. Disadvantages of Artificial Intelligence cont.. Increase dependency on machines:  With the increment of technology, people are getting more dependent on devices and hence they are losing their mental capabilities. No Original Creativity:  As humans are so creative and can imagine some new ideas but still AI machines cannot beat this power of human intelligence and cannot be creative and imaginative. Dr. Bharati Kawade RTIT MITACSC 11

12. Applications of AI Dr. Bharati Kawade RTIT MITACSC 12

13. Applications of AI cont.. 1. AI in Astronomy Artificial Intelligence can be very useful to solve complex universe problems. AI technology can be helpful for understanding the universe such as how it works, origin, etc. 2. AI in Healthcare In the lst , five to ten years, AI becoming more advantageous for the healthcare industry and going to have a significant impact on this industry. Healthcare Industries are applying AI to make a better and faster diagnosis than humans. AI can help doctors with diagnoses and can inform when patients are worsening so that medical help can reach to the patient before hospitalization. 3 . AI in Gaming AI can be used for gaming purpose. The AI machines can play strategic games like chess, where the machine needs to think of a large number of possible places. Dr. Bharati Kawade RTIT MITACSC 13

14. Applications of AI cont.. 4. AI in Finance AI and finance industries are the best matches for each other. The finance industry is implementing automation, chatbot, adaptive intelligence, algorithm trading, and machine learning into financial processes. 5. AI in Data Security The security of data is crucial for every company and cyber-attacks are growing very rapidly in the digital world. AI can be used to make your data more safe and secure. Some examples such as AEG bot, AI2 Platform, are used to determine software bug and cyber-attacks in a better way. 6.AI in Social Media Social Media sites such as Facebook, Twitter, and Snapchat contain billions of user profiles, which need to be stored and managed in a very efficient way. AI can organize and manage massive amounts of data. AI can analyze lots of data to identify the latest trends, hashtag, and requirement of different users. Dr. Bharati Kawade RTIT MITACSC 14

15. Applications of AI cont.. 7. AI in Travel & Transport AI is becoming highly demanding for travel industries. AI is capable of doing various travel related works such as from making travel arrangement to suggesting the hotels, flights, and best routes to the customers. Travel industries are using AI-powered chatbots which can make human-like interaction with customers for better and fast response. 8. AI in Automotive Industry Some Automotive industries are using AI to provide virtual assistant to their user for better performance. Tesla has introduced TeslaBot , an intelligent virtual assistant. Various industries are currently working for developing self-driven cars which can make your journey more safe and secure. Dr. Bharati Kawade RTIT MITACSC 15

16. Applications of AI cont.. 9. AI in Robotics: Artificial Intelligence has a remarkable role in Robotics. Usually, general robots are programmed such that they can perform some repetitive task, but with the help of AI, we can create intelligent robots which can perform tasks with their own experiences without pre-programmed. Humanoid Robots are best examples for AI in robotics, recently the intelligent Humanoid robot named as Erica and Sophia has been developed which can talk and behave like humans. 10. AI in Entertainment We are currently using some AI based applications in our daily life with some entertainment services such as Netflix or Amazon. With the help of ML/AI algorithms, these services show the recommendations for programs or shows. 11. AI in E-commerce AI is providing a competitive edge to the e-commerce industry, and it is becoming more demanding in the e-commerce business. AI is helping shoppers to discover associated products with recommended size, color , or even brand. Dr. Bharati Kawade RTIT MITACSC 16

17. Applications of AI cont.. 12. AI in Agriculture Agriculture is an area which requires various resources, labour, money, and time for best result. Now a day's agriculture is becoming digital, and AI is emerging in this field. Agriculture is applying AI as agriculture robotics, soil and crop monitoring, predictive analytics. AI in agriculture can be very helpful for farmers. 13. AI in education: AI can automate grading so that the tutor can have more time to teach. AI chatbot can communicate with students as a teaching assistant. AI in the future can work as a personal virtual tutor for students, which will be accessible easily at any time and any place. Dr. Bharati Kawade RTIT MITACSC 17

18. Intelligent System What is Intelligence? The ability of a system to calculate, reason, perceive relationships and analogies, learn from experience, store and retrieve information from memory, solve problems, comprehend complex ideas, use natural language fluently, classify, generalize, and adapt new situations. What is Intelligent System? Intelligent systems are technologically advanced machines that perceive and respond to the world around them. Intelligent systems can take many forms, from automated vacuums such as the Roomba to facial recognition programs to Amazon's personalized shopping suggestions.  Dr. Bharati Kawade RTIT MITACSC 18

19. AI began to emerge as a separate field of study during the 1940s and 1950s when the computer became a commercial. Prior to this, work in AI already began in 1920s and 1930s. Turing, sometimes regarded as father of AI demonstrated a simple computer processor could manipulate symbols and numbers. (Turing Machines) Cybernetics, the study of communication in human and machines, became an active area of research during 1940s and 1950s. During 1950, several events occurred marked as real beginning of AI. This was period noted for chess playing programs which were developed by researchers like Claude Shannon at MIT in 1952. Dr. Bharati Kawade RTIT MITACSC 19 Intelligent System cont..

20. Other types of game playing and simulation programs were also being developed during this time. In 1950s much efforts was being expended on machine translation programs, to produce accurate translation from one language to another During this time researches work on automatic theorem proving and new programming languages As a part of this development programming languages like IPL (Information Processing Language), FORTRAN etc were developed in the area of natural language processing Several programming projects were developed during 1950 including GPS(General Problem Solver) developed by Newell and Simon written in IPL. Gelernter’s geometry theorem proving machine written in FORTRAN Dr. Bharati Kawade RTIT MITACSC 20 Intelligent System cont..

21. Intelligent System cont.. Some significant AI events of the 1960s include the following: 1961-A. L. Samuel developed a program which learned to play checkers at a master’s level 1965- DENDRAL was the first knowledge based expert system developed which discover molecular structures given only information of the constituents of the compound 1968- work on MACSYMA was initiated at MIT by William Martin and Joel Moses. MACSYMA is a large interactive program which solves numerous types of mathematical problems. Dr. Bharati Kawade RTIT MITACSC 21

22. Intelligent System cont.. Applications of intelligent systems Intelligent systems are poised to fill a growing number of roles in today's society, including: Factory automation Field and service robotics Assistive robotics Military applications Medical care Education Dr. Bharati Kawade RTIT MITACSC 22

23. Intelligent System cont.. Applications of intelligent systems cont.. Entertainment Visual inspection Character recognition Human identification using various biometric modalities (e.g. face, fingerprint, iris, hand) Visual surveillance Intelligent transportation Dr. Bharati Kawade RTIT MITACSC 23

24. Intelligent System cont.. Challenges in intelligent systems Research in intelligent systems faces numerous challenges, many of which relate to representing a dynamic physical world computationally. Uncertainty : Physical sensors/effectors provide limited, noisy and inaccurate information/action. Therefore, any actions the system takes may be incorrect both due to noise in the sensors and due to the limitations in executing those actions. Dynamic world : The physical world changes continuously, requiring that decisions be made at fast time scales to accommodate the changes in the environment. Dr. Bharati Kawade RTIT MITACSC 24

25. Intelligent System cont.. Challenges in intelligent systems cont.. Time-consuming computation : Searching for the optimal path to a goal requires extensive search through a very large state space, which is computationally expensive. The drawback of spending too much time on computation is that the world may change in the meantime, thus rendering the computed plan obsolete. Mapping : A lot of information is lost in the transformation from the 3D world to the 2D world. Computer vision must deal with challenges including changes in perspective, lighting and scale; background clutter or motion; and grouping items with intra/inter-class variation. Dr. Bharati Kawade RTIT MITACSC 25

26. Knowledge –based Systems A knowledge-based system (KBS) is a form of artificial intelligence (AI) that aims to capture the knowledge of human experts to support decision-making. Examples of knowledge-based systems include expert systems, which are so called because of their reliance on human expertise. The typical architecture of a knowledge-based system, which informs its problem-solving method, includes a knowledge base and an inference engine. The knowledge base contains a collection of information in a given field -- medical diagnosis, for example. The inference engine deduces insights from the information housed in the knowledge base. Knowledge-based systems also include an interface through which users query the system and interact with it. Dr. Bharati Kawade RTIT MITACSC 26

27. Knowledge –based Systems cont.. A knowledge-based system may vary with respect to its problem-solving method or approach. Some systems encode expert knowledge as rules and are therefore referred to as rule-based systems. Another approach, case-based reasoning, substitutes cases for rules. Cases are essentially solutions to existing problems that a case-based system will attempt to apply to a new problem. Dr. Bharati Kawade RTIT MITACSC 27

28. Knowledge –based Systems cont.. Where knowledge-based systems are used Over the years, knowledge-based systems have been developed for a number of applications. MYCIN, for example, was an early knowledge-based system created to help doctors diagnose diseases. Healthcare has remained an important market for knowledge-based systems, which are now referred to as clinical decision-support systems in the health sciences context. Knowledge-based systems have also been employed in applications as diverse as avalanche path analysis, industrial equipment fault diagnosis and cash management. Dr. Bharati Kawade RTIT MITACSC 28

29. Knowledge –based Systems Knowledge-based systems and artificial intelligence While a subset of artificial intelligence, classical knowledge-based systems differ in approach to some of the newer developments in AI. Daniel Dennett, a philosopher and cognitive scientist, in his 2017 book,  From Bacteria to Bach and Back , cited a strategy shift from early AI. It is characterized by "top-down-organized, bureaucratically efficient know-it-all" systems to systems. It connects Big Data and "statistical pattern-finding techniques" such as data-mining and deep learning in a more bottom-up approach. Examples of AI following the latter approach include neural network systems. It is a type of deep-learning technology that concentrates on signal processing and pattern recognition problems such as facial recognition. Dr. Bharati Kawade RTIT MITACSC 29

30. AI Techniques AI technique is considered as a method of using knowledge. The research in AI for the first three decades concludes that intelligence requires knowledge. More the knowledge an individual has, the more intelligent he is. Few properties of knowledge are: It occupies large volume.  It is not easy to describe or characterize correctly.  It is varying in nature i.e., it is continuously changing.  It is different from data i.e., it is organized in accordance with the ways of using it. The methods to represent knowledge in order to use it in AI technique' is as follows.  Dr. Bharati Kawade RTIT MITACSC 30

31. AI Techniques cont.. The knowledge captures general things. That is, grouping situations that share common properties rather than representing each situation separately. Knowledge is supposed to process this property otherwise a lot of memory space is wasted in representing such situations separately. If knowledge does not posses this property then it is termed as "data".  The knowledge should be expressed in such a way that it can be understood by the people who must provide It.  The knowledge must be adjusted easily to correct errors if occurred and also to reflect changes in the world.  The knowledge could be useful in many different situations even though it may not be entirely complete or accurate. Knowledge could be used to overcome its own sheer bulk by aiding to limit the range of possibilities that need to be considered.  Dr. Bharati Kawade RTIT MITACSC 31

32. AI Techniques cont.. The three most important AI techniques are: Search:   It is a way of finding solutions to the problems that cannot be solved directly. It also acts as a framework to which direct techniques can be applied.  2) Use of Knowledge : It is a way of finding solutions to the complicated problems by means of manipulating structures of the objects.  3) Abstraction:   It is a way of isolating important aspects and manipulations from those of the unimportant ones. This eliminates confusion pertaining to the unimportant aspects. Dr. Bharati Kawade RTIT MITACSC 32

33. AI AI Techniques 1. Search A general technique required when writing AI programs is search . It provides a way of solving problems for which no more direct approach is available. Often there is no direct way to find a solution to some problem. However, you do know how to generate possibilities. For example, in solving a puzzle you might know all the possible moves, but not the sequence that would lead to a solution. Dr. Bharati Kawade RTIT MITACSC 33

34. AI Techniques cont.. 2. Use of Knowledge A lots of knowledge is required to solve simple problems . Use of knowledge Provides a way of solving complex problems by exploiting the structure of the objects that are involved. To understand a single sentence requires extensive knowledge of both language and of the context. In order to solve the complex problems encountered in artificial intelligence, one needs both a large amount of knowledge and some mechanisms for manipulating that knowledge to create solutions Dr. Bharati Kawade RTIT MITACSC 34

35. AI Techniques cont.. 3. Abstraction Abstraction means to hide the details of something. For example, if we want to compute the square root of a number then we simply call the function sqrt() in C. We do not need to know the implementation details of this function. Abstraction provides a way of separating important features and variations from the many unimportant ones that would otherwise overwhelm any process. Dr. Bharati Kawade RTIT MITACSC 35

36. AI and Related Fields Fields that are closely related to AI includes Robotics, Linguistics, Psychology, Engineering etc. Robotics: Robotics is considered as a separate field which combines concepts and techniques of AI, electrical and mechanical engineering. The robots that can see and move around, perform mechanical tasks, and understand human speech. Example: In manufacturing industry robots are used for moving, spraying, painting, precision checking, drilling, cleaning, coating, carving, etc Psychology: Psychology studies how human mind behave and how human brain processes information. Researchers in AI have much in common with psychologists. AI has adopted models of thinking and learning from psychologist in turn AI has given psychologist ability to model human functions on computer. Dr. Bharati Kawade RTIT MITACSC 36

37. AI and Related Fields cont.. Natural Language Processing: NLP allows a user to communicate with computer in user’s natural language. The computer can both understand and respond to commands given in natural language. Both NLP and AI fields have desired to build a system that understand natural languages. Dr. Bharati Kawade RTIT MITACSC 37

38. AI and Related Fields cont.. Expert System: Expert system is concerned with solving real life situations. Speech and Voice Recognition: The speech recognition aims at understanding WHAT was spoken. The objective of voice recognition is to recognize WHO is speaking. Handwriting Recognition : The handwriting recognition software reads the text written on paper by a pen or on screen by a stylus. It can recognize the shapes of the letters and convert it into editable text. AI overlap with almost all fields such as medicine, law, manufacturing, economics, banking, biology, chemistry, defence etc Dr. Bharati Kawade RTIT MITACSC 38

39. Defining AI problems as a State Space Search Problem as State Space Search A set of all possible states for a given problem is known as state space of the problem. Representation of states is highly beneficial in AI because they provide all possible states, operations and the goals. If the entire sets of possible states are given, it is possible to trace the path from the initial state to the goal state and identify the sequence of operators necessary for doing it. Representation allows for a formal definition of a problem using a set of permissible operations as the need to convert some given situation into some desired situation. Dr. Bharati Kawade RTIT MITACSC 39

40. Defining AI problems as a State Space Search cont.. h and Control Strategies We are free to define the process of solving a particular problem as a combination of known techniques. Each of which are represented as a rule defining a single step in the space, and search, the general technique of exploring the space to try to find some path from the current state to a goal state. AI problem can be solved by searching for a path through the space. i.e. from initial state to goal state. Search refers to the search for a solution in a problem space. Search proceeds with different types of search control strategies So it is necessary to choose the appropriate control structure such that the search can be as efficient as possible. Dr. Bharati Kawade RTIT MITACSC 40

41. Control Strategy It helps us in deciding which rule to apply next. What to do when there are more than 1 matching rule The features of good control strategy: A good control strategy is that which causes motion. A good control strategy must be systematic: A control strategy is not systematic; we may explore a particular useless sequence of operators several times before we finally find a solution. Dr. Bharati Kawade RTIT MITACSC 41

42. AI Problem 1.Water Jug Problem Problem Statement1 :- We are given 2 jugs, a 4 litter one and a 3 litter one. Neither has any measuring markers on it. There is a pump that can be used to fill the jugs with water. We can pour water out of a jug to the ground. We can pour water from one jug to another. How can we get exactly 2 litters of water into the 4-liter jug? Solution:- The state space for this problem can be defined as x -represents the number of litters of water in the 4-liter jug. y -represents the number of litters of water in the 3-liter jug. Therefore, x =0,1,2,3 or 4 and y=0,1,2 or 3. The initial state is ( 0,0) .The goal state is to get ( 2,n) for any value of ‘n’. Dr. Bharati Kawade RTIT MITACSC 42

43. AI Problem cont.. Rule No Production Rule Action 1 (x,y) if x<4 => (4,y) Fill the 4 Liter jug 2 (x,y) if y<3 => (x,3) Fill the 3 Liter jug 3 (x,y) if x>0 =>(0,y) Empty 4 Liter jug on ground 4 (x,y) if y>0 =>(x,0) Empty 3 Liter jug on ground 5 (x,y) if x+y<=4 =>(x+y,0) Pour all the water from 3 liter jug into 4 liter jug 6 (x,y) if x+y<=3 =>(0,x+y) Pour all the water from 4 liter jug into 3 liter jug 7 (x,y) if x+y>=4 => (4,y- (4-x) Pour water from 3 liter jug to 4 liter jug until 4 liter jug is full 8 (x,y) if x+y>=3 =>(x-(3- y),3) Pour water from 4 liter jug to 3 liter jug until 3 liter jug is full 9 (0,2) =>(2,0) Pour 2 liter from 3 liter jug to 4 liter jug Dr. Bharati Kawade RTIT MITACSC 43 1.Water Jug Problem cont.. The various Production Rules that are available to solve this problem may be stated as given in the following table .

44. AI Problem cont.. Dr. Bharati Kawade RTIT MITACSC 44 1.Water Jug Problem cont..

45. Liter in 4 Liter Jug Liter in 3 Liter Jug Rule Applied 3 2 3 7 3 3 2 4 2 5 2 3 2 5 Solution 1 AI Problem cont.. Dr. Bharati Kawade RTIT MITACSC 45 1.Water Jug Problem cont..

46. Liter in 4 Liter Jug Liter in 3 Liter Jug Rule Applied 4 1 1 3 8 1 4 1 6 4 1 1 2 3 8 Solution 2 Dr. Bharati Kawade RTIT MITACSC 46 AI Problem cont.. 1.Water Jug Problem cont..

47. Liter in 4 Liter Jug Liter in 3 Liter Jug Rule Applied 4 1 1 3 8 3 3 3 5 3 3 2 4 2 7 2 3 2 5 Solution 3 AI Problem cont.. Dr. Bharati Kawade RTIT MITACSC 47 1.Water Jug Problem cont..

48. Problem Statement2: The following is a problem which can be solved by using state space search technique. “we have 3 jugs of capacities 3,5, and 8 litters respectively. There is no scale on the jugs. So it is only their capacities that we certainly know. Initially the 8 litter jug is full of water, the other two are empty. We can pour water from one jug to another, and the goal is to have exactly 4 litters of water in any of the jug. There is no scale on the jug and we do not have any other tools that would help. The amount of water in the other two jugs at the end is irrelevant. Dr. Bharati Kawade RTIT MITACSC 48 AI Problem cont..

49. AI Problem cont.. Formalize the above problem as state space search You should, Suggest suitable representation of the problem State the initial and goal state of this problem Specify the production rules for getting from one state to another. Dr. Bharati Kawade RTIT MITACSC 49

50. AI Problem cont.. Solution:- The state space for this problem can be defined as x -represents the number of litters of water in the 8 liter jug y -represents the number of litters of water in the 5-liter jug z –represent the number of litters of water in he 3-liter jug Therefore, x =0,1,2,3,5,6,7 or 8 y=0,1,2 ,3,4 or 5 z=0,1,2 or 3 The initial state is ( 8,0,0). The goal state is to get 4 litre of water in any jug. The goal state can be defined as (4,n,n) or (n,4,n) for any value of n. Dr. Bharati Kawade RTIT MITACSC 50

51. 8,5,3 Liter water jug problem Rule Production Rule Action 1 (x,y,z) if x+y<=5 =>(0,x+y,z) Pour all water from 8 liter jug to 5 liter jug 2 (x,y,z) if x+z<=3 =>(0,y,x+z) Pour all water from 8 liter jug to 3 liter jug 3 (x,y,z) if x+y<=8 =>(x+y,0,z) Pour all water from 5 liter jug to 8 liter jug 4 (x,y,z) if y+z<=3 =>(x,0,y+z) Pour all water from 5 liter jug to 3 liter jug 5 (x,y,z) if x+z<=8 =>(x+z,y,0) Pour all water from 3 liter jug to 8 liter jug 6 (x,y,z) if y+z<=5 =>(x,y+z,0) Pour all water from 3 liter jug to 5 liter jug 7 (x,y,z) if x+y>=5 => (x-(5-y),5,z) Pour water from 8 liter jug to 5 liter jug until 5 liter jug is full 8 (x,y,z) if x+z>=3 => (x-(3-z),y,3) Pour water from 8 liter jug to 3 liter jug until 3 liter jug is full 9 (x,y,z) if y+z>=3 => (x,y-(3-z),3) Pour water from 5 liter jug to 3 liter jug until 3 liter jug is full 10 (x,y,z) if y+z>=5 => (x,5,z-(5-y)) Pour water from 3 liter jug to 5 liter jug until 5 liter jug is full Dr. Bharati Kawade RTIT MITACSC 51 The following table shows various production rules that are available to solve this problem. AI Problem cont..

52. 8,5,3 Liter water jug problem One solution to water jug problem is given as Liter in 8 Liter Jug Liter in 5 Liter Jug Liter in 3 Liter Jug Rule A ppli e d 8 3 5 7 3 2 3 9 6 2 5 6 2 4 1 5 2 7 1 4 3 9 Dr. Bharati Kawade RTIT MITACSC 52 AI Problem cont..

53. Thus, to solve any difficult, unstructured problems, we have to provide a formal description to solve a problem and for that we have to do following: Specify one or more states within that space that describes possible situations from which the problem solving process may start, called as initial state Specify one or more states that would be acceptable as solution to the problem. These states are called as goal state Define a state space that contains all the possible configuration of the relevant objects Specify a set of rules that describes the action available T h e p r o bl em can b e s o l v ed b y u s in g th e r u l es a n d a l s o with appropriate control strategy. Dr. Bharati Kawade RTIT MITACSC 53 AI Problem cont..

54. 2. Missionaries and Cannibals Problem: Problem Statement : Three missionaries and three cannibals find themselves on one side of a river. They would like to get to the other side, such that the number of missionaries on either side of the river should never less than the number of cannibals who are on the same side. The only boat available can holds only two at a time. How can everyone cross the river without the missionaries risking being eaten? Formalize the above problem in terms of state space search. You should, Suggest a suitable representation for the problem State the initial state and final state List the actions for getting from one state to another state Dr. Bharati Kawade RTIT MITACSC 54 AI Problem cont..

55. Solution: The state space for this problem can be defined as, Let, i represents the number missionaries in one side of a river Therefore i =0,1,2 or 3 j represents the number of cannibals in the same side of river Therefore j=0,1,2 or 3 The initial state ( i,j ) is (3,3) i.e. three missionaries and three cannibals on side A of a river and ( 0,0) on side B of the river . The goal state is to get (3,3) at Side B and (0,0) at Side A. Dr. Bharati Kawade RTIT MITACSC 55 AI Problem cont..

56. R ule No Production Rule Action 1 (i,j) if i-1>=j on one side and i+1>=j on other side One missionary can cross the river 2 (i,j) if j-1<=i or i=0 on one side and j+1<=i or j=0 on other side One cannibal can cross the river 3 (i,j) if i-2>=j or i-2=0 on one side and i+2>=j on other side Two missionary can cross the river 4 (i,j) if j-2<=i or i=0 on one side and j+2<=i or i=0 on other side Two cannibals can cross the river 5 (i,j) if i-1>=j-1 or i=0 on one side and i+1>=j+1 or i=0 on other side One missionary and one cannibal can cross the river AI Problem cont.. Dr. Bharati Kawade RTIT MITACSC 56 The various Production Rules that are available to solve this problem may be stated as given in the following table.

57. Solution of Missionary Canibal Problem Side A (M,C) Boat (M,C) Side B (M,C) Rule Applied (3,3) Empty (0,0) (3,1) (0,2) (0,2) 4 (3,2) (0,1) (0,1) 2 (3,0) (0,2) (0,3) 4 (3,1) (0,1) (0,2) 2 (1,1) (2,0) (2,2) 3 (2,2) (1,1) (1,1) 5 (0,2) (2,0) (3,1) 3 (0,3) (0,1) (3,0) 2 (0,1) (0,2) (3,2) 4 (0,2) (0,1) (3,1) 2 (0,0) (0,2) (3.3) 4 Dr. Bharati Kawade RTIT MITACSC 57 AI Problem cont..

58. Tower o f AI Problem cont.. Hanoi Problem Problem Statement: The Tower of Hanoi is a mathematical game or puzzle. It consist of three rods and a no. Of disks of different sizes, which can slide onto any rod. The puzzle start with the disks in a stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objectives of the puzzel is to move the entire stack into another rod, using following simple constraint. 1. Only one disk can be moved at a time. 2. Each move consist of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod. 3. No larger disk may be placed on top of a smaller disk. The minimal no of moves required to solve these problem. Dr. Bharati Kawade RTIT MITACSC 58

59. Dr. Bharati Kawade RTIT MITACSC 59

60. AI Problem cont.. 1.Disk 1 moved from R1 to R3 2. Disk 2 moved from R1 to R2 3. Disk 1 moved from R3 to R2 4. Disk 3 moved from R1 to R3 5. Disk 1 moved from R2 to R1 6. Disk 2 moved from R2 to R3 7.Disk 1 moved from R1 to R3 Dr. Bharati Kawade RTIT MITACSC 60

61. AI Problem cont.. The state is represented as a tuple , (rod no, Sequence of disks) ->{(R1,1,2,3),(R2,Nil),(R3,Nil} Initial State ->{(R1,2,3),(R2,NIL)(R3,1)} ->{(R1,3),(R2,2),(R3,1)} ->{(R1,3),(R2,1,2),(R3,NIL)} ->{(R1,NIL),(R2,1,2),(R3,3)} ->{(R1,1),(R2,NIL),(R3,2,3)} ->{(R1,NIL),(R2,NIL),(R3,1,2,3)} Goal State Total No of moves are 6. Dr. Bharati Kawade RTIT MITACSC 61

62. Summary AI is discussed along with different applications. Elaborated Intelligent Systems, Knowledge –based Systems, AI Techniques Discussed Early work in AI & related fields in detail. Discussed about Defining AI problems as a State Space Search. Search and Control Strategies are explained with examples. Problem Characteristics are discussed. Following AI Problems are discussed in detail with their solutions: Water Jug Problem Tower of Hanoi Missionaries & Cannibal Problem Dr. Bharati Kawade RTIT MITACSC 62