CS6362 Applications of AI Sample Midterm Solutions 1) (10 pt) Pizza Delivery System a) (2.5 pt) THE FRAME PROBLEM: assume everything stays the same unless it is explicitly changed. This may not be true because of incomplete representation. The rules that are used to update the frames have to be modified every time a change is made. This is not easy to do automatically. A new kind of pizza may be added to the menu. However, if this pizza is cooked without cheese (some weird pizza) and the system is programmed by default to put cheese on every pizza we have a problem. b) (2.5 pt) THE SYMBOL GROUNDING PROBLEM: Many AI systems work and reason in a symbolic domain, i.e., an abstract representation of the real world. However, the system has no notion of what the symbol means. For example, for the pizza delivery system pizza may be defined as a box that needs to be delivered to an address. If the box is empty (no pizza in it) the system will still deliver it. c) (2.5 pt) THE QUALIFICATION PROBLEM: It is not possible to write down every qualification for every rule. In other words, in the real world it is difficult to define the circumstances under which a given action is guaranteed to work. The system may know how to deliver to the required address but if there is a road work going on in the neighborhood I will have to replan its route. If replanning is not in the system specification the system will fail. d) (2.5 pt) THE CLOSED WORLD ASSUMPTION: Assume anything that the system can't do is not possible. For example, if the customer lives in a newly constructed apartment complex the system may not know that address and refuse to deliver pizza. 2) (20 pt) Logic a) (i) (5 pt) \__/ \/ (x): (Pizza(x) AND Good(x)) => Hot(x) (ii) (5 pt) _ _| _| (x): Pizza(x) AND Has(Joe, x) AND Not(Hot(x)) (iii) (5 pt) _ _| _| (x): Pizza(x) AND [ Not(Hot(x)) OR Not(Good(x))] b) (5 pt) Modus Ponens states that if there is a rule "A=>B" and we know that A is true then we can conclude B. Or in logic terms: [A ^ (A=>B)]=> B In our case, upon substituting 'x' with 'Pizza1' we conclude: Eaten(Pizza1) 3) (15 pt) Briefly describe the difference between semantic nets, frames, and scripts. A frame is a data structure that includes all the knowledge about a particular object. The knowledge is organized in a special hierarchical structure that permits a diagnosis of knowledge independence (Class textbook p.187). In contrast to other representation schemes the values that describe an object are grouped together into a single unit. A script is a knowledge representation scheme similar to a frame, but instead of describing an object, the script describes a sequence of events. Like the frame the script portrays a stereotyped situation. Unlike the frame, it is usually presented in a particular context. To describe a sequence of events the script uses a series of slots containing information about the people, objects, and actions that are involved in the events (Class textbook, p.178). A semantic network is a knowledge representation scheme which is composed of nodes and links. Semantic networks are basically graphic depictions of knowledge that shows hierarchical relationships between objects (Class textbook p.174). They are very good in supporting system analysis, demonstrating changes, and inheritance relationships. Their major limitations are the difficulties in representing procedural knowledge and the lack of formalized structure. Write a pizza delivery script. Include actors, roles, events, etc. All of you did well on this task. Answer omitted. 4) (10 pt) A* Search algorithm A* gives us the power to perform optimal search for optimal solution in optimal time if we have a good heuristic. These are only possible if the search algorithm uses a heuristic defined in the following way: f*(n) = g*(n)+h*(n) where: g*(n) = minimum cost of path from start node to node n h*(n) = estimated minimum cost from node n to goal node. If h*() is perfect then no unnecessary nodes are ever expanded. Also, h*() should be ADMISSIBLE, i.e., it should never overestimate the cost to the goal. For details see the class notes on Search p.16-21. 5) (15 pt) Search methods a) (5 pt) A B D E C G b) (5 pt) A B C D G c) (5 pt) step 0- (A,0) <- select and expand A step 1- (B,10) (D,5) (E,1) <- select and expand E step 2- (B,10) (D,5) (F,3) (H,2) <- select and expand H step 3- (B,10) (D,5) (F,3) (I,6) <- select and expand F step 4- (B,10) (D,5) (G,4) (I,6) <- select G, Goal reached Thus the order of traversal is: A B D E F H I G Uniform cost is a variation of breadth first search for Cheapest path. For more details see the class notes on Search (p.7). 6) (20 pt) Answer only 2 of the following. a) (10 pt) Generate and test a la Dendral R1: To make pizza one needs the following ingredients: dough, pepperoni, mushrooms, and cheese. Test : Do we have all ingredients? No. We don't have mushrooms. R2: One can get mushrooms from the supermarket. Test: Try to buy mushrooms. Test successful. R3: Pizza baking should be similar to bread baking. R4: Pizza dough is prepared in the same way as for bread but is shaped differently by stretching it. Test: Do we get a pizza like shape? Yes. Go on. R5: Ingredients must be put on top of the dough. R6: The oven must be preheated. R7: Baking time is the same as for bread. Test: Bake and see if the pizza is good. No. It needs more baking. R8: Baking time must be increased by 10 minutes. Test: Did we get a good pizza? Yes. Goal achieved. For details on Dendral see the class notes on Problem Solving p.38-42. b) (10 pt) Problem reduction a la Noah Get ingredients / \ S - Preheat Oven - J \ / Bake the Pizza Get dough / \ - Get mushrooms - / \ / \ / Get pepperoni \ / \ S --- Preheat Oven - J \ / mix --> Bake ingredients ingredients Get dough / \ S- Buy mushrooms -J / \ / \ / Get pepperoni \ / \ S --- Preheat Oven-- -------------------------------- J \ | / \ ------>>--------- / \ prepare put put | Bake / - dough -> pepperoni-> mushrooms-->J-->ingredients -> Get dough / \ S- Buy mushrooms - J / \ / | / Get pepperoni | / | S --------------------- |------- Preheat Oven---- \ | | \ -------------<<------ --<<-- \| prepare put put | Bake J--> dough -> pepperoni-> mushrooms-->J-->ingredients -> Get Buy Get Prepare dough -> mushrooms-> pepperoni----> dough --->-- | ----------------------------------------------------- | | Put Put Preheat Bake --> pepperoni-> mushrooms----> oven ---> ingredients -> For details on Noah see the class notes on Problem Solving p.23-29. c) (10 pt) Case-Based Reasoning Task is to bake pizza. 1. Check the Case memory for similar experience 2. The closest match is baking Bread 3. We can adapt/modify this case for pizza - we prepare the dough in the same way but spread it in a thin layer and put topping on top then we bake for the same duration of time as for bread 4. Test: Do we have a good pizza? No. It is still raw. 5. Explain: It needs more baking. 6. Repair: Increase the baking time. 7 Test: Do we have a good pizza? Yes. 8. Store this solution in the Case memory. 7) (10 pt) What is intelligence? Answer only one. (10 pt) The Turing test. One version of the Turing test involves a person sitting in front of two terminals. The intelligence tester is free to ask any questions to the respondents on the other end of the terminals, one of which is a computer and the other a human being. If the questioneer cannot discriminate between the computer and the human subject, the computer is said to have passed the Turing test. The critics of the Turing test say that it 1) is biased towards symbolic problem solving; 2) does not test perceptual ability or locomotion/dexterity; and 3) forces intelligence to be human-like. (10 pt) Chinese Room argument: Suppose we have the following situation: An English speaker (the CPU), who can speak no other language, is locked in a room with a writing device(output), blank paper (mass storage), and a rule book (the program) that says what to do when presented with specific undecipherable Chinese characters. A slip of paper containing Chinese characters (the input) is presented through a small opening in the door. The human uses the rule book to perform transformations in Chinese, first by matching the characters from the input slip to corresponding entries in the rule book and then by carrying out the instructions specified in the book, creating new Chinese characters. This process generates correct answers in Chinese to the incoming Chinese questions. These are then passes in written form (output) to the outside through another small opening. The system can be envisioned as successfully passing the Turing test is a computer takes the place of the human. Searle (the author of the argument) contends that clearly the translator has no understanding of what the slips of paper contain and thus does not understand Chinese. Merely coming up with the right answer by any means possible does not constitute understanding.