logging in or signing up AI ankush85 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 5316 Category: Education License: All Rights Reserved Like it (24) Dislike it (1) Added: March 19, 2009 This Presentation is Public Favorites: 9 Presentation Description No description available. Comments Posting comment... By: teabag_a1 (4 month(s) ago) Please email to me? sarah.n10@hotmail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: mohanboddu (4 month(s) ago) sir plz send me fast to mohan_chowdary@ymail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: yuexiangyu (9 month(s) ago) i need this ppt file for my final project....thank you very much... my email id is yuexiangyu168@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: Tanudixit (11 month(s) ago) kindly mail this presentation to er.tanudixit@sify.com or allow me to download it. Saving..... Post Reply Close Saving..... Edit Comment Close By: sainivicky96 (11 month(s) ago) PLZ MAIL AT sainivicky96@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close loading.... See all Premium member Presentation Transcript Slide 1: 1 ARTIFICIAL INTELLIGENCE CONTENTS : 2 Introduction To Artificial Intelligence (AI) History Of AI Main Issues In AI Application Areas In AI Computer Systems For AI AI Programs Verses Conventional Programs Turing Test Why AI ? CONTENTS ARTIFICIAL INTELLIGENCE : 3 ARTIFICIAL INTELLIGENCE AI Is The Part Of Computer Science Concerned With The Design Of Computer Systems Which Exhibit The Attributes Of Human Intelligence Such As understanding Of Languages, Learning New Information, Reasoning, Solving Problems, Planning, Perception And Creativity. ASPECTS OF INTELLIGENCE : 4 ASPECTS OF INTELLIGENCE Use Of Intuition Common Sense - Application Of Knowledge To New Situations Creativity - Creating Something New And Useful Learning From Experience Memory Retention And Recall Goal - Directed Search Human Information Processing Has And Hope To Find In Machines ARTIFICIAL INTELLIGENCE : 5 ARTIFICIAL INTELLIGENCE AI Is A Technology Of Information Processing Concerned With Processes Of Reasoning Learning And Perception. AI Is Problem Oriented Interdisciplinary Fascinating Challenging Why AI ? : 6 Why AI ? Computer Systems Will Be Processing Knowledge As A Result The Application Areas Of Computer Areas Will Increase. New Tools Can Be Built Which Have Commercial Value And Can Improve The Life Style. ENVIRONMENT : 7 ENVIRONMENT MAIN ISSUES IN AI : 8 MAIN ISSUES IN AI LEVEL 1 ISSUES Is it possible to create non human intelligence ? Can we model the brain ? Can we teach machines to think & solve problems like humans ? LEVEL 2 ISSUES : 9 LEVEL 2 ISSUES What are our assumptions about intelligence ? What kind of techniques will be useful for solving AI problems ? At what level of detail are we trying to model human intelligence ? LEVEL 3 ISSUES : 10 LEVEL 3 ISSUES Knowledge Representation Schemes Search - Avoids Combinatorial Explosion Perception - Involves Analog Signals With Noise Inference ARTIFICIAL INTELLIGENCE : 11 ARTIFICIAL INTELLIGENCE Can we develop a good model of the processes involved in intelligent reasoning ? Cognitive science is a filed in which psychologists, linguistics' and computer scientists all work together to develop such a model. HISTORY OF AI : 12 HISTORY OF AI Work in AI started in 1956 Scientists ALLEN NEWELL - HERBERT SIMON Simulate neural networks - MARVIN MINSKY of the brain. - OLIVER SELFIDGE JOHN MCCARTHY Year Developments : 13 Year Developments 1950s - Check etc – playing program was developed 1960s - Theorem proving programs 1967s - Dendral expert system for predicting unknown chemical compounds 1970s - Speech recognition system that can identify few spoken words 1980s - Interpretation of visual images ACRONYM was successful in interpreting airport images 1990s - Chess-playing program that could compete with grandmasters APPLICATION AREAS IN AI : 14 APPLICATION AREAS IN AI Game playing Theorem proving Computer vision, Robotics Natural Language understanding Export Systems Medical diagnosis Chemical analysis Engineering Design AI systems process symbols : 15 AI systems process symbols Knowledge Inferences If x is a bird, x can fly Robin is a bird Robin can fly Purpose of AI To build useful new tools not only for commercial purposes, but also to improve life style COMPUTER STYSTEMS FOR AI : 16 COMPUTER STYSTEMS FOR AI Tend to have Symbolic & Logic processing features in the software - Ex, LISP, PROLOG, OOPS Expert system shells with built-in features as - Knowledge acquisition capability - Knowledge Representation capability - Inference mechanism - Reasoning capability Good graphics and natural language features Large memories & fast processors Processors optimized for symbolic processing PHYSICAL SYMBOL SYSTEM : 17 PHYSICAL SYMBOL SYSTEM At the heart of research in AI lies physical symbol system (pass) hypothesis NEWELL and SIMON defined PSS as below. A PSS is a machine that operates on symbols to produce collection of symbol structures. It has the necessary and sufficient means for general intelligent action. Computers can generate any PSS we like importance of PSS It is a significant theory of the nature of human intelligence It forms the basis of the belief that it is possible to build programs that can perform intelligent tasks now performed by people. CONVENTIONAL VERSES AI PROGRAMS : 18 CONVENTIONAL VERSES AI PROGRAMS Conventional Programs AI Programs * Definite algorithms let completely well * There is no definite algorithm defined steps of solution * Uses data structures like arrays, records, lists * Uses knowledge representation semantic nets, predicate logic etc. * Predominantly manipulates numbers, characters * Manipulates macros, objects, symbols * Deterministic well defined and will bounded * Open ended, large and problem uncertainty dominate problem * Predefined data * Dynamic data ( due to knowledge acquisition) * Primitive user interface * Sophisticated user interface AI REQUIRES KNOWLEDGE : 19 AI REQUIRES KNOWLEDGE PROPERTIES OF KNOWLEDGE Knowledge is essential - that can not be done without It is voluminous Difficult to characterize accurately Constantly changing Differs from data by being organized Data may be acquired automatically from instruments Knowledge is provided by people who understand it Can be used in many situations Can be easily modified to correct errors. AI technique is a method to exploit knowledge NATURAL LANGUAGE UNDERSTANDING (NLU)EXAMPLE : 20 NATURAL LANGUAGE UNDERSTANDING (NLU)EXAMPLE “ I need to go to New York as soon as possible” An airline database system will have understand if it finds the first available plans to New York . Your best friend will have understood if he/she realizes that there may be a need for you to go to New York. Collecting, organizing the background knowledge and applying it for languages comprehension terms the major problem in NLU TURING TEST : 21 TURING TEST Dr. Alan Turing has devised a test to know whether AI has achieved. Comparison with a human be the criteria by which it is decided whether or not a machine can think TURING TEST : 22 TURING TEST Machine and human are in one room Interrogator does not know who is answering He gets answers through intermediary system As they responds to questions, A and B must convince the interrogator that he is the human. If the machine can convince, the machine passes the TURNING TEST. TURING TEST : 23 TURING TEST Intelligence has many quantity of knowledge Kinds of inference it can make with knowledge Well-directed search procedure ? Read automatic knowledge acquisition ? SIMULATION OF INTELLIGENT BEHAVIOUR : 24 SIMULATION OF INTELLIGENT BEHAVIOUR GAME . PLAYING TIC-TAC-TOE 9 Positions, 2 Players Each player inputs a number Win : Same number vertically horizontally or diagonally makes a player win PROGRAM - I : 25 PROGRAM - I Data Structure Board : A nine0element vector representing the board, the elements of the vector correspond to board positions as above. Element Value 0 blank 1 if X in a square 2 if 0 in a square Moveable A vector of 39 = 19,683 elements. Each element is a nine-element vector chosen specifically to allow the algorithm to work. ALGORITHM : 26 ALGORITHM View the board as a ternary (base 3) number. Convert it to a decimal number. Use the number as an index into move table and access the vector stored there. The vector selected represents the current board position i.e. after the move that should be made Slide 27: 27 Example (i) (ii) (iii) (iv) EXAMPLE - cont : 28 EXAMPLE - cont The vector corresponding to board position (i) 000 000 000 The vector corresponding to board position (ii) 100 000 000 The vector corresponding to board position (iii) 200 000 000 The vector corresponding to board position (iv) 120 000 000 Board position next to (i)is(ii) means move-table [0] =100 000 000 Board position following (ii) is (iv) means move-table [6561] = 120 000 000 ( 100 000 000) = 3 (6561) 10 Comments : 29 Comments It is very efficient in terms of time. It can play an optional game. Lot of space is required to store move-table Total strategy has been figured out in advance so cannot be extended to three dimensions, in fact this technique would no longer work due to enormous amount of memory requirement TIC-TAC-TOE : 30 TIC-TAC-TOE PROGRAM – 2 Data Structures Board same as in program - I Turn 2 blank 3 –3 , 5 – 0 an integer indicating the move number 1 – First move, 9 last move PROCEDURES : 31 PROCEDURES MAKE – 2 Returns 2 if center square is blank i.e. Board [5] = 2, otherwise return any blank non-corner square ( 2, 4, 6 or 8 ) Posswin(p) Returns 0 if player p cannot win on his next move, otherwise return the number of the winning square Enables to win and to block opponent’s moves Slide 32: 32 Checks each of the rows, columns and the diagonal X can win if the product of the row/column/diagonal is 18 ( 3 x 3 x 2) 0 can win if the product is 50 ( 5 x 5 x 2) Go(n) Makes a move in square n. Board [n] = 3 if turn is odd Board [n] = 5 if turn is even Increments turn by 1 Algorithm has a built-in strategy : 33 Algorithm has a built-in strategy Odd-numbered moves – if X is playing corner system Even-numbered moves – if 0 is playing Center or non-corner system Algorithm with Example : 34 Algorithm with Example Turn = 1 Turn = 2 Go (1) if Board [5] = v Go (5) else Go (1) Algorithm with Example : 35 Algorithm with Example Turn = 3 Turn = 4 IF Board [9] b/ if pops. Can win, Go 99) else Go [3] block it else Go (Maks. (2)) Algorithm with Example : 36 Algorithm with Example Turn = 5 Turn = 6win or block win win or block winelse if Board [7] = b/ else Go [Make – 2]Go [7], else Go [3] Algorithm with Example : 37 Algorithm with Example Turn = 7 Turn = 8check b/ win check b/ winor block pop. or block pop.Win else 90 Win else 90any where in any where inblank square blank square Algorithm with Example : 38 Algorithm with Example Turn = 9 check b/ win or block pop. Win else 90 any where in blank square Example - 2 : 39 Example - 2 S Board (5) c+b Go [1] Example - 2 : 40 Example - 2 S C Example - 2 : 41 Example - 2 S C S Example - 2 : 42 Example - 2 C S Example - 3 : 43 Example - 3 C S C Go [1] Board [9]=b/ Go [9] Example - 3 : 44 Example - 3 S C S Block app.'s move Example - 3 : 45 Example - 3 C Comments Win : 46 Comments Win Not efficient in terms of time since, it has to check several conditions before making a move More efficient in terms of space Cannot generalize the knowledge to a different domain as 3-D tic-tac-toe Program – 21 : 47 Program – 21 SAME AS PROGRAM 2 but the board positions are as below All the rows, columns, and diagonals sum to 15 : magic square Slide 48: 48 The process of checking for a possible win is simplified Keep a list of square a player owns Compute the difference : D = 15 – sum of two squares Two squares are not collinear : D is not positive or can be ignored if D is greater than 9. Slide 49: 49 The third square along with the two collinear square (with D as required) Is blank, A move there will produce a win Fewer Squares will be examined as no player can have > 4 squares at any time Comments : : 50 Comments : Suitable for a conventional computer which processes numbers People are parallel processors and can look at several parts of the board at once Different from problem solving by peeve Program – 3 : 51 Program – 3 Data Structures A structure containing a nine-element vector representing the board A list of board positions that could result from the next move A number representing an estimate of how likely the board position is to lead to an ultimate Won. ALGORITHM : (Minimum Maximum procedure) : 52 ALGORITHM : (Minimum Maximum procedure) To decide on the next move, look ahead at the board positions that result each possible move Decide which position is best and make the move leading to that position Assign the rating of that best move to the current position Slide 53: 53 How to decide which of a set of board positions is best ? If it is a win call it the best by giving highest possible rating Otherwise, consider all the moves the opponent could make next, see which of them is worst for us (by recursively calling this procedure), whatever rating that move has, assign it to the node we are considering The best node is then the one with the highest rating. The algorithm attempts to maximize the likelihood of winning Comments : 54 Comments This is an example of an AI technique Can be applied to any game playing progress Can be used when traditional techniques fail Requires much more time than others Can be augmented by a specific kind of knowledge about games and how to play them It might consider only a subject only a subset of all possible next moves Question Answering : 55 Question Answering Consider the following text Mary went shopping for a new coat. She found a red one she really liked. When she got it home she discovered that it went perfectly with he favorite dress. Let us try to attempt to each of the following questions with different programs Slide 56: 56 Q1. What did Mary go shopping for ? Q2. What did Mary find that she liked ? Q3. Did Mary buy anything ? PROGRAM - 1 : 57 PROGRAM - 1 It matches text fragments in the questions against the input text. Data Structures Question Patterns A set of templates that match common question forms and produce text Patterns to be used to match against inputs. If the template “who did x y “ matches an input questions then the text pattern “x y z “ is matched against the input text, and the value of z is the answer the question. Data Structure : 58 Data Structure Text The input text stored as a long character string Question The current question also stored as a character string Algorithm to answer a question : 59 Algorithm to answer a question Compare each element of question patterns against the question, to generate a set of text patterns. Generate a new, expanded set of text patterns to generate alternative forms of verbs for example go might match went. Apply each of the text patterns to text, and collect answer Reply with the set of answers collected Example : : 60 Example : Q1: “What did x y “ template matches Q1 and generates the text pattern “ Mary go shopping for z “. Using a convention that variables match the longest possible string up-to a sentence delimiter the answer “ a new coat” is assigned to z. Slide 61: 61 Q2. If the template set is very large allowing Insertion of object of find between it and “that she liked”. Insertion of really is the text between it and find that she liked. Substitution of she for Mary Slide 62: 62 Q3: Since no answer is directly contained in the text – it can not be answered Comments : In adequate to answer the kinds of questions people could answer Depends on the form in which questions are stated PROGRAM – 2 : 63 PROGRAM – 2 This converts the input text and the questions into a structured sentences. It finds answers by matching structured forms against each other. Data Structures : 64 Data Structures English know : A description of words, grammar and appropriate semantic interpretations of English to account for input texts. Input text : The input text in character form Structured text A structured representation to capture the essential knowledge contained in the input text (slot-and-filler structure) Input Question - Input question in character form Structure Question - Same structure used to represent input text Slide 65: 65 Event – 2 Thing – 1 Event – 2 Instance : Finding Instance : Coat Instance : Liking Tense : Past Color : Red Tense : Past Agent : Mary Modifier : Much Object : Thing1 Object : Thing1 ((Set-and-filler) Structure representation of “ She found a red one she really liked” Algorithm : 66 Algorithm Convert the input text into structured form using knowledge contained in English know Convert the question to structured form use “who or what” any such marker to indicate the past of structure that should be returned as the answer. Match the question structured form against input text structured form Return as answer those parts of the text that match the requested segment of the question Slide 67: 67 Q1. The question is answered straightforwardly with “ a new coat”. Q2. This is also answered successfully with “ a red coat” Q3. Can not be answered Comments on Program – 2 : 68 Comments on Program – 2 Knowledge - based and hence effective More time required for searching various Knowledge – bases (English know, Structured Text) Powerful Knowledge base requires additional knowledge about the world with which the text deal. Slide 69: 69 Mary walked up to the salesperson. She asked where the toy department was. Mary walked up to the salesperson. She asked her if she needed any help. She refers to whom ? For this knowledge about the roles of customers and salespersons in stores is essential. Program – 3 : 70 Program – 3 Combines prior knowledge about the objects and situations involved in the text. Data Structures World Knowledge : A structured representation of background world knowledge (about objects, actions and situation) Slide 71: 71 English know : As in Program – 2 Input Text : The input text in character form Integrated text : Structured representation of the knowledge combined with background, related knowledge) Input Questions: As in Program – 2 Structure Representing System’s Knowledge about shopping : 72 Structure Representing System’s Knowledge about shopping Shopping Script : Roles : C (Customer), S (Salesperson) Props:M (Merchantman), D (Dollar) Location : L ( a store) Algorithm : 73 Algorithm Convert the input text into structured form using both the knowledge in English know and world model. Convert the question to structured form use world mode if necessary. Match the structured form against Integrated Text. Return as answer those parts of the text that match the requested segment of the question Slide 74: 74 Q1. As in Program – 2 Q2. As in Program – 2 Q3. This question can be answered Using the integrated text as the basis for question answer allows the program to respond “ She bought a red Coat”. M’ is bound to red coat [ Step 14 from script and from text red coat is what got taken]. Comments on Program - 3 : 75 Comments on Program - 3 This is an AI technique It exploits more knowledge Cannot answer when the answer is not contained explicitly in the Integrated text. General inference mechanism is required to answer any type of questions. Example : 76 Example Saturday morning Mary went shopping. Her brother tried to call her there but she couldn’t get hold of her. Q. Why couldn’t Mary’s brother reach her ? R. Because she want at home. Answering like above requires knowledge that are can’t be two places at once, and the fact that Mary couldn’t have been home because she was shopping. Slide 77: 77 Conclusions : The two (final) examples illustrate three AI techniques. Search : Provides a way of solving problems for which no direct approach is available. Use of Knowledge : Provides a way of solving complex problems by exploiting the structures of the objects that are involved. Abstraction : Provides a way of separating important features and variations from the Mary un-important ones. NATURAL LANGUAGE UNDERSTANDING (NLU) : 78 NATURAL LANGUAGE UNDERSTANDING (NLU) EXAMPLE “ I need to go to New York as soon as possible” An airline database system will have understand if it finds the first available plans to New York . Your best friend will have understood if he/she realizes that there may be a need for you to go to New York. Collecting, organizing the background knowledge and applying it for languages comprehension terms the major problem in NLU Slide 79: 79 SHRDLU - Solves blocks world problem could answer queries as “ What color block is on the blue cube ? Perform actions such as “ move the red pyramid on to the green brick” Solves well understood specialized problem areas Requires tremendous amount of knowledge RECEPTION : PLANNING AND ROBOTICS : 80 RECEPTION : PLANNING AND ROBOTICS Robot That Can Move, Forward, Backward, Right Or Left There Are A Large Number Of Ways A Robot Can Move Around A Room Assume Also There Are Obstacles In The Room The Robot Must Select A Path That Moves Around Then In Some Efficient Fashion Such A Robot Must Begin Moving Through The Room Based On What It Has Perceived And Correct Its Path As Other Obstacles Re Detected PROBLEMS, PROBLEM SPACES AND SEARCH : 81 PROBLEMS, PROBLEM SPACES AND SEARCH To solve on AI problem 1. Define the problem in respect of initial situation, and final expected situation. 2. Analyze the problem. Find important features of the problem. Explore various alternative techniques of solving it . 3. Represent the knowledge that is necessary to solve the problem. 4. Choose the best problem solving technique and apply it to the problem Slide 82: 82 EXAMPLE : To build a program that could play CHESS Specifications The starting position of the chess board The rules that define the legal moves The board positions that represent a win for one side or the other Slide 83: 83 The Goal : * To Play a legal game * To win the game Starting position cab be described as an 8 x 8 array where each position contains a symbol GOAL : * Play a legal game * Win the game ( The opponent’s king is under attack) Starting Position : An 8 x 8 array where each position contains a symbol Slide 84: 84 64 squares 16 symbols ~ 10120 board positions 16 64 = (24)64 = 2 254 10 120 ~ (23)120 = 2360 Slide 85: 85 Through legal moves reach from initial state to a good state A generalized rule for the above move for a white pawn to move two positions ahead White pawn at Square (file e, rank 2) move pawn from square (file e, rank 2) and Square (file e, rank 3) is empty to square (file 2, rank 4) and Square (file e, rank 4) is empty Slide 86: 86 The problem of playing chess can be defined a problem of moving around in a space where each state corresponds to a legal position of the board state space representation forms the basis of most of the AI methods State space representation enables to solve problems by allowing Slide 87: 87 The formal definition of a problem using a set of operations The define the problem solving process as a combination of known techniques and search to try some path from current state to the goal state. Search is a very imported process in the solution of hard problems for which no more direct techniques are available. A WATER JUG PROBLEM : 88 A WATER JUG PROBLEM Given : A - 4 - gallon jug [without any measuring marks] B - 3 - gallon jug Pump : To fill the jugs with water Problem : To get exactly 2 gallons of water into the 4 – gallon jug. Slide 89: 89 Let:x be the number of gallons of water in A y be the number of gallons of water in B x can be 0,1,2,3,4 : y can be 0,1,2,3 State space can be represented as a pair (x, y) Start state : ( 0, u ) Goal State: ( 2, n) for any n Assumptions : 90 Assumptions We can fill the jug from the pump We can pour water out of jug to the ground We can pour water from one jug to another There are no measuring devices available. In the production rules, the left sides are matched against the current state, and right sides describe the new resulting from applying the rule. PRODUCTION RULES : 91 PRODUCTION RULES 1.(x, y) ? (4, y) Fill the 4 gallon jug if x < 4 if it is already not full 2. (x, y) ?(x, 3) Fill the 3 gallon jug if y < 3 3. (x, y) ? (x-d, y) Pour some water out of the I f x > 0 4 gallon jug 4. (x, y) ?(x,y-d) Pour some water out of the if y > 0 3 – gallon jug Slide 92: 92 5. (x, y) ? (0, y) Empty the four gallon jug if x > 0 on the ground 6. (x, y) ? (x, 0) Empty the three gallon jug if y > 0 on the ground 7. (x, y) ? (4, y- (4-x)) Pour water from B into A if x +y = 4 and y > 0 until A is full 8. (x, y) ? (x- (3-y), 3) Pour water from A into B if x +y = 3 and x > 0 until B is full Slide 93: 93 9. (x, y) ? (x + y,0) Pour all the water from B into A if x +y = 4 and y > 0 10. (x, y) ? (0, x + y) Pour all the water from A into B if x +y = 3 and x > 0 11. (0,2) ? (2,0) Pour 2 gallons from B into A 12. (2,y) ? (0,y) Empty the 2 gallons in A on the ground Solution to the water jug problem : 94 Solution to the water jug problem There are several sequence of operators that solve the problem. The shortest sequence is supposed to be the best. The speed with which the problem get solved depends on the next operation to be performed. SOLUTION : 95 SOLUTION State of A State of B Rule applied 0 0 0 3 2 3 0 9 3 3 2 4 2 7 0 2 5 or 12 2 0 7 or 11 Slide 96: 96 Issue to discuss in converting information problem statement into a formal description 1. The role of the condition (x,y) ? (4,y) The constraints like fill A x<4 (x,y) ? 4,y if it is already not full increases the efficiency of the problem-solving program. Slide 97: 97 2. Rules 3 & 4 (pour some water out of A , pour some water out of B) are allowed by the problem statement, but doing so will never get us closer to the solution. This emphasizes the difference between writing a set of rules that describe the problem itself or writing rules that describe both the problem and some knowledge about its solution. Slide 98: 98 3.Rule 11 (0,2) ? (2,0) Rule 12 (2,y) ? (0,y) Rule 5 (x,y) ? (0,y) If x>0 Rule 9 (x,y) ? (x+y,0) If x+y = 4 and y>0 Slide 99: 99 Rules 11 and 12 are provided in rules 985. They do not actually add power to the system Chess, Water jug problem are highly structured problems. We can produce formal description from informal ones. For natural language understanding problems producing an informal specification itself is a very hard problem. STEPS TO PROVIDE A FORMAL DESCRIPTION OF A PROBLEM : 100 STEPS TO PROVIDE A FORMAL DESCRIPTION OF A PROBLEM Define a state space than contain all possible configurations of the relevant objects. It may be possible to define the space without enumerating all the states it contains. Specify one or more initial states Specify one or more states as foal states Specify a set of rules that describe the actions. While doing this the following issues need to be considered. Slide 101: 101 What unstated assumptions are present in the informal description of the problem ? How general should the rule be ? How much of the work required to solve the problem should be precomputed and represented in the rules ? PERCEPTION : PLANNING AND ROBOTICS : 102 PERCEPTION : PLANNING AND ROBOTICS Robot That Can Move, Forward, Backward, Right Or Left There Are A Large Number Of Ways A Robot Can Move Around A Room Assume Also There Are Obstacles In The Room The Robot Must Select A Path That Moves Around Then In Some Efficient Fashion Such A Robot Must Begin Moving Through The Room Based On What It Has Perceived And Correct Its Path As Other Obstacles Re Detected PROBLEMS, PROBLEM SPACES AND SEARCH : 103 PROBLEMS, PROBLEM SPACES AND SEARCH To solve on AI problem 1. Define the problem in respect of initial situation, and final expected situation. 2. Analyze the problem. Find important features of the problem. Explore various alternative techniques of solving it . 3. Represent the knowledge that is necessary to solve the problem. 4. Choose the best problem solving technique and apply it to the problem. EXAMPLE : To build a program that could play CHESS Specifications : 104 Specifications The starting position of the chess board The rules that define the legal moves The board positions that represent a win for one side or the other The Goal : * To Play a legal game * To win the game Starting position cab be described as an 8 x 8 array where each position contains a symbol GOAL : 105 GOAL GOAL : * Play a legal game * Win the game (The opponent’s king is under attack) Starting Position : An 8x8 array where each position contains a symbol Through legal moves reach from initial state to a good state A generalized rule for the above move for a white pawn to move two positions ahead : 106 A generalized rule for the above move for a white pawn to move two positions ahead White pawn at Square (file e, rank z) move pawn from square (file e, rank z) and Square (file e, rank 3) is empty to square (file 2, rank 4) and Square (file e, rank 4) is empty : 107 The problem of playing chess can be defined a problem of moving around in a space where each state corresponds to a legal position of the board state space representation forms the basis of most of the AI methods : 108 State space representation enables to solve problems by allowing The formal definition of a problem using a set of operations The define the problem solving process as a combination of known techniques and search to try some path from current state to the goal state. Search is a very important process in the solution of hard problems for which no more direct techniques are available You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
AI ankush85 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 5316 Category: Education License: All Rights Reserved Like it (24) Dislike it (1) Added: March 19, 2009 This Presentation is Public Favorites: 9 Presentation Description No description available. Comments Posting comment... By: teabag_a1 (4 month(s) ago) Please email to me? sarah.n10@hotmail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: mohanboddu (4 month(s) ago) sir plz send me fast to mohan_chowdary@ymail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: yuexiangyu (9 month(s) ago) i need this ppt file for my final project....thank you very much... my email id is yuexiangyu168@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: Tanudixit (11 month(s) ago) kindly mail this presentation to er.tanudixit@sify.com or allow me to download it. Saving..... Post Reply Close Saving..... Edit Comment Close By: sainivicky96 (11 month(s) ago) PLZ MAIL AT sainivicky96@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close loading.... See all Premium member Presentation Transcript Slide 1: 1 ARTIFICIAL INTELLIGENCE CONTENTS : 2 Introduction To Artificial Intelligence (AI) History Of AI Main Issues In AI Application Areas In AI Computer Systems For AI AI Programs Verses Conventional Programs Turing Test Why AI ? CONTENTS ARTIFICIAL INTELLIGENCE : 3 ARTIFICIAL INTELLIGENCE AI Is The Part Of Computer Science Concerned With The Design Of Computer Systems Which Exhibit The Attributes Of Human Intelligence Such As understanding Of Languages, Learning New Information, Reasoning, Solving Problems, Planning, Perception And Creativity. ASPECTS OF INTELLIGENCE : 4 ASPECTS OF INTELLIGENCE Use Of Intuition Common Sense - Application Of Knowledge To New Situations Creativity - Creating Something New And Useful Learning From Experience Memory Retention And Recall Goal - Directed Search Human Information Processing Has And Hope To Find In Machines ARTIFICIAL INTELLIGENCE : 5 ARTIFICIAL INTELLIGENCE AI Is A Technology Of Information Processing Concerned With Processes Of Reasoning Learning And Perception. AI Is Problem Oriented Interdisciplinary Fascinating Challenging Why AI ? : 6 Why AI ? Computer Systems Will Be Processing Knowledge As A Result The Application Areas Of Computer Areas Will Increase. New Tools Can Be Built Which Have Commercial Value And Can Improve The Life Style. ENVIRONMENT : 7 ENVIRONMENT MAIN ISSUES IN AI : 8 MAIN ISSUES IN AI LEVEL 1 ISSUES Is it possible to create non human intelligence ? Can we model the brain ? Can we teach machines to think & solve problems like humans ? LEVEL 2 ISSUES : 9 LEVEL 2 ISSUES What are our assumptions about intelligence ? What kind of techniques will be useful for solving AI problems ? At what level of detail are we trying to model human intelligence ? LEVEL 3 ISSUES : 10 LEVEL 3 ISSUES Knowledge Representation Schemes Search - Avoids Combinatorial Explosion Perception - Involves Analog Signals With Noise Inference ARTIFICIAL INTELLIGENCE : 11 ARTIFICIAL INTELLIGENCE Can we develop a good model of the processes involved in intelligent reasoning ? Cognitive science is a filed in which psychologists, linguistics' and computer scientists all work together to develop such a model. HISTORY OF AI : 12 HISTORY OF AI Work in AI started in 1956 Scientists ALLEN NEWELL - HERBERT SIMON Simulate neural networks - MARVIN MINSKY of the brain. - OLIVER SELFIDGE JOHN MCCARTHY Year Developments : 13 Year Developments 1950s - Check etc – playing program was developed 1960s - Theorem proving programs 1967s - Dendral expert system for predicting unknown chemical compounds 1970s - Speech recognition system that can identify few spoken words 1980s - Interpretation of visual images ACRONYM was successful in interpreting airport images 1990s - Chess-playing program that could compete with grandmasters APPLICATION AREAS IN AI : 14 APPLICATION AREAS IN AI Game playing Theorem proving Computer vision, Robotics Natural Language understanding Export Systems Medical diagnosis Chemical analysis Engineering Design AI systems process symbols : 15 AI systems process symbols Knowledge Inferences If x is a bird, x can fly Robin is a bird Robin can fly Purpose of AI To build useful new tools not only for commercial purposes, but also to improve life style COMPUTER STYSTEMS FOR AI : 16 COMPUTER STYSTEMS FOR AI Tend to have Symbolic & Logic processing features in the software - Ex, LISP, PROLOG, OOPS Expert system shells with built-in features as - Knowledge acquisition capability - Knowledge Representation capability - Inference mechanism - Reasoning capability Good graphics and natural language features Large memories & fast processors Processors optimized for symbolic processing PHYSICAL SYMBOL SYSTEM : 17 PHYSICAL SYMBOL SYSTEM At the heart of research in AI lies physical symbol system (pass) hypothesis NEWELL and SIMON defined PSS as below. A PSS is a machine that operates on symbols to produce collection of symbol structures. It has the necessary and sufficient means for general intelligent action. Computers can generate any PSS we like importance of PSS It is a significant theory of the nature of human intelligence It forms the basis of the belief that it is possible to build programs that can perform intelligent tasks now performed by people. CONVENTIONAL VERSES AI PROGRAMS : 18 CONVENTIONAL VERSES AI PROGRAMS Conventional Programs AI Programs * Definite algorithms let completely well * There is no definite algorithm defined steps of solution * Uses data structures like arrays, records, lists * Uses knowledge representation semantic nets, predicate logic etc. * Predominantly manipulates numbers, characters * Manipulates macros, objects, symbols * Deterministic well defined and will bounded * Open ended, large and problem uncertainty dominate problem * Predefined data * Dynamic data ( due to knowledge acquisition) * Primitive user interface * Sophisticated user interface AI REQUIRES KNOWLEDGE : 19 AI REQUIRES KNOWLEDGE PROPERTIES OF KNOWLEDGE Knowledge is essential - that can not be done without It is voluminous Difficult to characterize accurately Constantly changing Differs from data by being organized Data may be acquired automatically from instruments Knowledge is provided by people who understand it Can be used in many situations Can be easily modified to correct errors. AI technique is a method to exploit knowledge NATURAL LANGUAGE UNDERSTANDING (NLU)EXAMPLE : 20 NATURAL LANGUAGE UNDERSTANDING (NLU)EXAMPLE “ I need to go to New York as soon as possible” An airline database system will have understand if it finds the first available plans to New York . Your best friend will have understood if he/she realizes that there may be a need for you to go to New York. Collecting, organizing the background knowledge and applying it for languages comprehension terms the major problem in NLU TURING TEST : 21 TURING TEST Dr. Alan Turing has devised a test to know whether AI has achieved. Comparison with a human be the criteria by which it is decided whether or not a machine can think TURING TEST : 22 TURING TEST Machine and human are in one room Interrogator does not know who is answering He gets answers through intermediary system As they responds to questions, A and B must convince the interrogator that he is the human. If the machine can convince, the machine passes the TURNING TEST. TURING TEST : 23 TURING TEST Intelligence has many quantity of knowledge Kinds of inference it can make with knowledge Well-directed search procedure ? Read automatic knowledge acquisition ? SIMULATION OF INTELLIGENT BEHAVIOUR : 24 SIMULATION OF INTELLIGENT BEHAVIOUR GAME . PLAYING TIC-TAC-TOE 9 Positions, 2 Players Each player inputs a number Win : Same number vertically horizontally or diagonally makes a player win PROGRAM - I : 25 PROGRAM - I Data Structure Board : A nine0element vector representing the board, the elements of the vector correspond to board positions as above. Element Value 0 blank 1 if X in a square 2 if 0 in a square Moveable A vector of 39 = 19,683 elements. Each element is a nine-element vector chosen specifically to allow the algorithm to work. ALGORITHM : 26 ALGORITHM View the board as a ternary (base 3) number. Convert it to a decimal number. Use the number as an index into move table and access the vector stored there. The vector selected represents the current board position i.e. after the move that should be made Slide 27: 27 Example (i) (ii) (iii) (iv) EXAMPLE - cont : 28 EXAMPLE - cont The vector corresponding to board position (i) 000 000 000 The vector corresponding to board position (ii) 100 000 000 The vector corresponding to board position (iii) 200 000 000 The vector corresponding to board position (iv) 120 000 000 Board position next to (i)is(ii) means move-table [0] =100 000 000 Board position following (ii) is (iv) means move-table [6561] = 120 000 000 ( 100 000 000) = 3 (6561) 10 Comments : 29 Comments It is very efficient in terms of time. It can play an optional game. Lot of space is required to store move-table Total strategy has been figured out in advance so cannot be extended to three dimensions, in fact this technique would no longer work due to enormous amount of memory requirement TIC-TAC-TOE : 30 TIC-TAC-TOE PROGRAM – 2 Data Structures Board same as in program - I Turn 2 blank 3 –3 , 5 – 0 an integer indicating the move number 1 – First move, 9 last move PROCEDURES : 31 PROCEDURES MAKE – 2 Returns 2 if center square is blank i.e. Board [5] = 2, otherwise return any blank non-corner square ( 2, 4, 6 or 8 ) Posswin(p) Returns 0 if player p cannot win on his next move, otherwise return the number of the winning square Enables to win and to block opponent’s moves Slide 32: 32 Checks each of the rows, columns and the diagonal X can win if the product of the row/column/diagonal is 18 ( 3 x 3 x 2) 0 can win if the product is 50 ( 5 x 5 x 2) Go(n) Makes a move in square n. Board [n] = 3 if turn is odd Board [n] = 5 if turn is even Increments turn by 1 Algorithm has a built-in strategy : 33 Algorithm has a built-in strategy Odd-numbered moves – if X is playing corner system Even-numbered moves – if 0 is playing Center or non-corner system Algorithm with Example : 34 Algorithm with Example Turn = 1 Turn = 2 Go (1) if Board [5] = v Go (5) else Go (1) Algorithm with Example : 35 Algorithm with Example Turn = 3 Turn = 4 IF Board [9] b/ if pops. Can win, Go 99) else Go [3] block it else Go (Maks. (2)) Algorithm with Example : 36 Algorithm with Example Turn = 5 Turn = 6win or block win win or block winelse if Board [7] = b/ else Go [Make – 2]Go [7], else Go [3] Algorithm with Example : 37 Algorithm with Example Turn = 7 Turn = 8check b/ win check b/ winor block pop. or block pop.Win else 90 Win else 90any where in any where inblank square blank square Algorithm with Example : 38 Algorithm with Example Turn = 9 check b/ win or block pop. Win else 90 any where in blank square Example - 2 : 39 Example - 2 S Board (5) c+b Go [1] Example - 2 : 40 Example - 2 S C Example - 2 : 41 Example - 2 S C S Example - 2 : 42 Example - 2 C S Example - 3 : 43 Example - 3 C S C Go [1] Board [9]=b/ Go [9] Example - 3 : 44 Example - 3 S C S Block app.'s move Example - 3 : 45 Example - 3 C Comments Win : 46 Comments Win Not efficient in terms of time since, it has to check several conditions before making a move More efficient in terms of space Cannot generalize the knowledge to a different domain as 3-D tic-tac-toe Program – 21 : 47 Program – 21 SAME AS PROGRAM 2 but the board positions are as below All the rows, columns, and diagonals sum to 15 : magic square Slide 48: 48 The process of checking for a possible win is simplified Keep a list of square a player owns Compute the difference : D = 15 – sum of two squares Two squares are not collinear : D is not positive or can be ignored if D is greater than 9. Slide 49: 49 The third square along with the two collinear square (with D as required) Is blank, A move there will produce a win Fewer Squares will be examined as no player can have > 4 squares at any time Comments : : 50 Comments : Suitable for a conventional computer which processes numbers People are parallel processors and can look at several parts of the board at once Different from problem solving by peeve Program – 3 : 51 Program – 3 Data Structures A structure containing a nine-element vector representing the board A list of board positions that could result from the next move A number representing an estimate of how likely the board position is to lead to an ultimate Won. ALGORITHM : (Minimum Maximum procedure) : 52 ALGORITHM : (Minimum Maximum procedure) To decide on the next move, look ahead at the board positions that result each possible move Decide which position is best and make the move leading to that position Assign the rating of that best move to the current position Slide 53: 53 How to decide which of a set of board positions is best ? If it is a win call it the best by giving highest possible rating Otherwise, consider all the moves the opponent could make next, see which of them is worst for us (by recursively calling this procedure), whatever rating that move has, assign it to the node we are considering The best node is then the one with the highest rating. The algorithm attempts to maximize the likelihood of winning Comments : 54 Comments This is an example of an AI technique Can be applied to any game playing progress Can be used when traditional techniques fail Requires much more time than others Can be augmented by a specific kind of knowledge about games and how to play them It might consider only a subject only a subset of all possible next moves Question Answering : 55 Question Answering Consider the following text Mary went shopping for a new coat. She found a red one she really liked. When she got it home she discovered that it went perfectly with he favorite dress. Let us try to attempt to each of the following questions with different programs Slide 56: 56 Q1. What did Mary go shopping for ? Q2. What did Mary find that she liked ? Q3. Did Mary buy anything ? PROGRAM - 1 : 57 PROGRAM - 1 It matches text fragments in the questions against the input text. Data Structures Question Patterns A set of templates that match common question forms and produce text Patterns to be used to match against inputs. If the template “who did x y “ matches an input questions then the text pattern “x y z “ is matched against the input text, and the value of z is the answer the question. Data Structure : 58 Data Structure Text The input text stored as a long character string Question The current question also stored as a character string Algorithm to answer a question : 59 Algorithm to answer a question Compare each element of question patterns against the question, to generate a set of text patterns. Generate a new, expanded set of text patterns to generate alternative forms of verbs for example go might match went. Apply each of the text patterns to text, and collect answer Reply with the set of answers collected Example : : 60 Example : Q1: “What did x y “ template matches Q1 and generates the text pattern “ Mary go shopping for z “. Using a convention that variables match the longest possible string up-to a sentence delimiter the answer “ a new coat” is assigned to z. Slide 61: 61 Q2. If the template set is very large allowing Insertion of object of find between it and “that she liked”. Insertion of really is the text between it and find that she liked. Substitution of she for Mary Slide 62: 62 Q3: Since no answer is directly contained in the text – it can not be answered Comments : In adequate to answer the kinds of questions people could answer Depends on the form in which questions are stated PROGRAM – 2 : 63 PROGRAM – 2 This converts the input text and the questions into a structured sentences. It finds answers by matching structured forms against each other. Data Structures : 64 Data Structures English know : A description of words, grammar and appropriate semantic interpretations of English to account for input texts. Input text : The input text in character form Structured text A structured representation to capture the essential knowledge contained in the input text (slot-and-filler structure) Input Question - Input question in character form Structure Question - Same structure used to represent input text Slide 65: 65 Event – 2 Thing – 1 Event – 2 Instance : Finding Instance : Coat Instance : Liking Tense : Past Color : Red Tense : Past Agent : Mary Modifier : Much Object : Thing1 Object : Thing1 ((Set-and-filler) Structure representation of “ She found a red one she really liked” Algorithm : 66 Algorithm Convert the input text into structured form using knowledge contained in English know Convert the question to structured form use “who or what” any such marker to indicate the past of structure that should be returned as the answer. Match the question structured form against input text structured form Return as answer those parts of the text that match the requested segment of the question Slide 67: 67 Q1. The question is answered straightforwardly with “ a new coat”. Q2. This is also answered successfully with “ a red coat” Q3. Can not be answered Comments on Program – 2 : 68 Comments on Program – 2 Knowledge - based and hence effective More time required for searching various Knowledge – bases (English know, Structured Text) Powerful Knowledge base requires additional knowledge about the world with which the text deal. Slide 69: 69 Mary walked up to the salesperson. She asked where the toy department was. Mary walked up to the salesperson. She asked her if she needed any help. She refers to whom ? For this knowledge about the roles of customers and salespersons in stores is essential. Program – 3 : 70 Program – 3 Combines prior knowledge about the objects and situations involved in the text. Data Structures World Knowledge : A structured representation of background world knowledge (about objects, actions and situation) Slide 71: 71 English know : As in Program – 2 Input Text : The input text in character form Integrated text : Structured representation of the knowledge combined with background, related knowledge) Input Questions: As in Program – 2 Structure Representing System’s Knowledge about shopping : 72 Structure Representing System’s Knowledge about shopping Shopping Script : Roles : C (Customer), S (Salesperson) Props:M (Merchantman), D (Dollar) Location : L ( a store) Algorithm : 73 Algorithm Convert the input text into structured form using both the knowledge in English know and world model. Convert the question to structured form use world mode if necessary. Match the structured form against Integrated Text. Return as answer those parts of the text that match the requested segment of the question Slide 74: 74 Q1. As in Program – 2 Q2. As in Program – 2 Q3. This question can be answered Using the integrated text as the basis for question answer allows the program to respond “ She bought a red Coat”. M’ is bound to red coat [ Step 14 from script and from text red coat is what got taken]. Comments on Program - 3 : 75 Comments on Program - 3 This is an AI technique It exploits more knowledge Cannot answer when the answer is not contained explicitly in the Integrated text. General inference mechanism is required to answer any type of questions. Example : 76 Example Saturday morning Mary went shopping. Her brother tried to call her there but she couldn’t get hold of her. Q. Why couldn’t Mary’s brother reach her ? R. Because she want at home. Answering like above requires knowledge that are can’t be two places at once, and the fact that Mary couldn’t have been home because she was shopping. Slide 77: 77 Conclusions : The two (final) examples illustrate three AI techniques. Search : Provides a way of solving problems for which no direct approach is available. Use of Knowledge : Provides a way of solving complex problems by exploiting the structures of the objects that are involved. Abstraction : Provides a way of separating important features and variations from the Mary un-important ones. NATURAL LANGUAGE UNDERSTANDING (NLU) : 78 NATURAL LANGUAGE UNDERSTANDING (NLU) EXAMPLE “ I need to go to New York as soon as possible” An airline database system will have understand if it finds the first available plans to New York . Your best friend will have understood if he/she realizes that there may be a need for you to go to New York. Collecting, organizing the background knowledge and applying it for languages comprehension terms the major problem in NLU Slide 79: 79 SHRDLU - Solves blocks world problem could answer queries as “ What color block is on the blue cube ? Perform actions such as “ move the red pyramid on to the green brick” Solves well understood specialized problem areas Requires tremendous amount of knowledge RECEPTION : PLANNING AND ROBOTICS : 80 RECEPTION : PLANNING AND ROBOTICS Robot That Can Move, Forward, Backward, Right Or Left There Are A Large Number Of Ways A Robot Can Move Around A Room Assume Also There Are Obstacles In The Room The Robot Must Select A Path That Moves Around Then In Some Efficient Fashion Such A Robot Must Begin Moving Through The Room Based On What It Has Perceived And Correct Its Path As Other Obstacles Re Detected PROBLEMS, PROBLEM SPACES AND SEARCH : 81 PROBLEMS, PROBLEM SPACES AND SEARCH To solve on AI problem 1. Define the problem in respect of initial situation, and final expected situation. 2. Analyze the problem. Find important features of the problem. Explore various alternative techniques of solving it . 3. Represent the knowledge that is necessary to solve the problem. 4. Choose the best problem solving technique and apply it to the problem Slide 82: 82 EXAMPLE : To build a program that could play CHESS Specifications The starting position of the chess board The rules that define the legal moves The board positions that represent a win for one side or the other Slide 83: 83 The Goal : * To Play a legal game * To win the game Starting position cab be described as an 8 x 8 array where each position contains a symbol GOAL : * Play a legal game * Win the game ( The opponent’s king is under attack) Starting Position : An 8 x 8 array where each position contains a symbol Slide 84: 84 64 squares 16 symbols ~ 10120 board positions 16 64 = (24)64 = 2 254 10 120 ~ (23)120 = 2360 Slide 85: 85 Through legal moves reach from initial state to a good state A generalized rule for the above move for a white pawn to move two positions ahead White pawn at Square (file e, rank 2) move pawn from square (file e, rank 2) and Square (file e, rank 3) is empty to square (file 2, rank 4) and Square (file e, rank 4) is empty Slide 86: 86 The problem of playing chess can be defined a problem of moving around in a space where each state corresponds to a legal position of the board state space representation forms the basis of most of the AI methods State space representation enables to solve problems by allowing Slide 87: 87 The formal definition of a problem using a set of operations The define the problem solving process as a combination of known techniques and search to try some path from current state to the goal state. Search is a very imported process in the solution of hard problems for which no more direct techniques are available. A WATER JUG PROBLEM : 88 A WATER JUG PROBLEM Given : A - 4 - gallon jug [without any measuring marks] B - 3 - gallon jug Pump : To fill the jugs with water Problem : To get exactly 2 gallons of water into the 4 – gallon jug. Slide 89: 89 Let:x be the number of gallons of water in A y be the number of gallons of water in B x can be 0,1,2,3,4 : y can be 0,1,2,3 State space can be represented as a pair (x, y) Start state : ( 0, u ) Goal State: ( 2, n) for any n Assumptions : 90 Assumptions We can fill the jug from the pump We can pour water out of jug to the ground We can pour water from one jug to another There are no measuring devices available. In the production rules, the left sides are matched against the current state, and right sides describe the new resulting from applying the rule. PRODUCTION RULES : 91 PRODUCTION RULES 1.(x, y) ? (4, y) Fill the 4 gallon jug if x < 4 if it is already not full 2. (x, y) ?(x, 3) Fill the 3 gallon jug if y < 3 3. (x, y) ? (x-d, y) Pour some water out of the I f x > 0 4 gallon jug 4. (x, y) ?(x,y-d) Pour some water out of the if y > 0 3 – gallon jug Slide 92: 92 5. (x, y) ? (0, y) Empty the four gallon jug if x > 0 on the ground 6. (x, y) ? (x, 0) Empty the three gallon jug if y > 0 on the ground 7. (x, y) ? (4, y- (4-x)) Pour water from B into A if x +y = 4 and y > 0 until A is full 8. (x, y) ? (x- (3-y), 3) Pour water from A into B if x +y = 3 and x > 0 until B is full Slide 93: 93 9. (x, y) ? (x + y,0) Pour all the water from B into A if x +y = 4 and y > 0 10. (x, y) ? (0, x + y) Pour all the water from A into B if x +y = 3 and x > 0 11. (0,2) ? (2,0) Pour 2 gallons from B into A 12. (2,y) ? (0,y) Empty the 2 gallons in A on the ground Solution to the water jug problem : 94 Solution to the water jug problem There are several sequence of operators that solve the problem. The shortest sequence is supposed to be the best. The speed with which the problem get solved depends on the next operation to be performed. SOLUTION : 95 SOLUTION State of A State of B Rule applied 0 0 0 3 2 3 0 9 3 3 2 4 2 7 0 2 5 or 12 2 0 7 or 11 Slide 96: 96 Issue to discuss in converting information problem statement into a formal description 1. The role of the condition (x,y) ? (4,y) The constraints like fill A x<4 (x,y) ? 4,y if it is already not full increases the efficiency of the problem-solving program. Slide 97: 97 2. Rules 3 & 4 (pour some water out of A , pour some water out of B) are allowed by the problem statement, but doing so will never get us closer to the solution. This emphasizes the difference between writing a set of rules that describe the problem itself or writing rules that describe both the problem and some knowledge about its solution. Slide 98: 98 3.Rule 11 (0,2) ? (2,0) Rule 12 (2,y) ? (0,y) Rule 5 (x,y) ? (0,y) If x>0 Rule 9 (x,y) ? (x+y,0) If x+y = 4 and y>0 Slide 99: 99 Rules 11 and 12 are provided in rules 985. They do not actually add power to the system Chess, Water jug problem are highly structured problems. We can produce formal description from informal ones. For natural language understanding problems producing an informal specification itself is a very hard problem. STEPS TO PROVIDE A FORMAL DESCRIPTION OF A PROBLEM : 100 STEPS TO PROVIDE A FORMAL DESCRIPTION OF A PROBLEM Define a state space than contain all possible configurations of the relevant objects. It may be possible to define the space without enumerating all the states it contains. Specify one or more initial states Specify one or more states as foal states Specify a set of rules that describe the actions. While doing this the following issues need to be considered. Slide 101: 101 What unstated assumptions are present in the informal description of the problem ? How general should the rule be ? How much of the work required to solve the problem should be precomputed and represented in the rules ? PERCEPTION : PLANNING AND ROBOTICS : 102 PERCEPTION : PLANNING AND ROBOTICS Robot That Can Move, Forward, Backward, Right Or Left There Are A Large Number Of Ways A Robot Can Move Around A Room Assume Also There Are Obstacles In The Room The Robot Must Select A Path That Moves Around Then In Some Efficient Fashion Such A Robot Must Begin Moving Through The Room Based On What It Has Perceived And Correct Its Path As Other Obstacles Re Detected PROBLEMS, PROBLEM SPACES AND SEARCH : 103 PROBLEMS, PROBLEM SPACES AND SEARCH To solve on AI problem 1. Define the problem in respect of initial situation, and final expected situation. 2. Analyze the problem. Find important features of the problem. Explore various alternative techniques of solving it . 3. Represent the knowledge that is necessary to solve the problem. 4. Choose the best problem solving technique and apply it to the problem. EXAMPLE : To build a program that could play CHESS Specifications : 104 Specifications The starting position of the chess board The rules that define the legal moves The board positions that represent a win for one side or the other The Goal : * To Play a legal game * To win the game Starting position cab be described as an 8 x 8 array where each position contains a symbol GOAL : 105 GOAL GOAL : * Play a legal game * Win the game (The opponent’s king is under attack) Starting Position : An 8x8 array where each position contains a symbol Through legal moves reach from initial state to a good state A generalized rule for the above move for a white pawn to move two positions ahead : 106 A generalized rule for the above move for a white pawn to move two positions ahead White pawn at Square (file e, rank z) move pawn from square (file e, rank z) and Square (file e, rank 3) is empty to square (file 2, rank 4) and Square (file e, rank 4) is empty : 107 The problem of playing chess can be defined a problem of moving around in a space where each state corresponds to a legal position of the board state space representation forms the basis of most of the AI methods : 108 State space representation enables to solve problems by allowing The formal definition of a problem using a set of operations The define the problem solving process as a combination of known techniques and search to try some path from current state to the goal state. Search is a very important process in the solution of hard problems for which no more direct techniques are available