Subject: comps questions Date: Thu, 8 Apr 1999 22:00:11 -0400 (EDT) From: "Martha E. Pollack" To: tsamard@cs.pitt.edu Here they are. Let me know if you have any questions. Good luck, M Intelligent Systems Program Comprehensive Exam Ioannis Tsamardinos April 1999 This is an open book examination, so you may consult---and reference---any sources from the literature. Note, however, that you are not permitted to consult any person about this examination, with the exception that you may ask your committee members clarification questions. For Questions 1, please consult Prof. Cooper; for Questions 2 and 3, consult Prof. Pollack ; and for Questions 4 and 5, consult Prof. Buchanan Your answer to question 1 should be no more than 10 pages of single-spaced text in 12pt font, using 1" margins all around. Your answers to questions 2 through 5 should be no more 5 pages each, with the same font and spacing restrictions just mentioned. Your completed written exam is due back to the committee by 10am on April 19. Submission by email is fine. The oral portion of your exam will be held at 3:30pm on Apr. 21, in 103 MIB. --------------------------------------------------------- QUESTION 1. Consider time series data that provide a record of the observations and decisions of robot r. Let M_itr denote the observation of variable i at time t by robot r. For example, M_itr might be a GPS-derived location (observational variable i) at time t of robot r , who is trying to drive a car from point A to point B within a given city in the shortest amount of time. Similarly, decision j by robot r at time t is denoted D_jtr. For instance, D_jtr might denote the street and direction (decision variable j) that robot r decided to travel at time t. Other types of observations and decisions may exist as well. Suppose that over a long period of time a group of robots transmit their M_itr and D_jtr data as they repeatedly perform (at various times) a commonly designated goal, such as getting from point A to point B. Let DB denote the database containing the record of these transmissions. a) Describe a representation for this decision/planning problem that includes a representation of time and of uncertainty. What are the assumptions and design decisions inherent in your representation? b) Describe how to use the representation in part a to solve a decision/planning problem that involves time and uncertainty. c) Using your representation from part a and your solution method from part b, show how to represent and solve a simple version of the driving problem mentioned in the paragraph above. d) Describe how to use one of the methods from Mitchell's Machine Learning book to learn the temporal representation in part a from database DB. Explain the strengths and weaknesses of this method for this learning task. e) What is the time complexity of your learning method for part d in learning your temporal representation for part a? f) How would you propose to handle the problem of older data in DB becoming obsolete? In our example, roads may become closed for extended periods of time, and possibly new roads may become available for travel. g) Does your representation contain causal knowledge? Why or why not? Do all decision/planning systems contain causal knowledge, either explicitly or implicitly? Why or why not? h) In general, how might robots have an advantage in learning causal knowledge from each other, relative to humans learning such knowledge from each other? --------------------------------------------------------- QUESTION 2. In their paper "Decision-Theoretic Planning: Structural Assumptions and Computational Leverage," Boutilier, Dean and Hanks claim that MDP-related methods provide a unifying framework for modeling many classes of planning problems studied in AI. a) Give a formal statement of the problem solved by MDPs. b) Consider the following well-known approaches to plan generation: i. partial-order planning without contingencies (e.g., in UCPOP) ii. partial-order planning with contingencies (e.g., in Mahinur) iii. Graphplan-based planning (e.g., in IPP) iv. SAT-based planning (e.g., in Blackbox) v. HTN planning (e.g., in UMCP, or as described in Russell and Norvig) For each of these, give a formal statement of the planning problem they solve; and either show how it maps to the MDP problem, or explain why it doesn't. c) Each of the five class of planners listed in part (b) takes a different approach to making the planning process more efficient. For each, briefly describe the technique(s) used to improve effeciency, and explain whether, and if so, how, those techniques could be adopted by an MDP system. --------------------------------------------------------- QUESTION 3. The recent literature on temporal reasoning has led to a number of efficient algorithms for determining the consistency of a set of temporal constraints as well as for computing tight bounds for a set of events, given temporal constraints over them. a) Consider the following description of a plan you might have: You will give a party next Saturday at 8pm; it will last between 3 and 4 hours. At least 2, but no more than 3 weeks in advance, you need to invite your guests. This involves finding their email addresses, creating a mailing list, and sending an email message to the list. You also need to arrange food for the party, which you can do in one of two ways: you can either buy it and cook it, or you can call a caterer and have it delivered. If you choose the first option, you need to buy the food before you cook it, and you need to have it cooked before you clean up for the party. Cooking takes 4 hours. If you use a catering company, you need to give it 72 hours notice, and you require the food to be delivered no more than 1 hour before the party starts, and no later than the start time. You also need to clean up before the party: this involves first cleaning the house, which takes 2 hours, and then cleaning up yourself, which in turn involves taking a shower (1/2 hour) and then getting dressed (1/2 hour). Finally, after the party is done, you need to clean the house again (and again, this requires 2 hours). You need to have completed the clean up within 24 hours of the party's completion; also, you do not like to clean between the hours of midnight and 9am. Draw the constraint satisfaction network that you would use to represent this problem. Could you use an STN, as in Dechter, Meiri and Pearl, 1991? If not, identify a set of simplifications to the story that would enable you to do so. b) Most of the research on temporal reasoning has focused on "flat", non-hierarchical representations. Making reference to the story in part (a), discuss what advantages there might be to performing temporal reasoning over hierarchical sets of events and temporal constraints. c) For this question, assume a version of the story that allows you to employ STNs (either the original story or the simplifications you identified in part (a)). Explain how the algorithms used by STNs to determine consistency would have to be modified to make use of the hierarchical structure of the problem. Be as precise as you can, including pseudo-code. --------------------------------------------------------- QUESTION 4. STRIPS and SOAR both learn from experience. In what ways are their learning methods the same and in what ways are they different? E.g., How and how much do they generalize? When do they generalize? The architects of SOAR have said that chunking in SOAR is a "side effect" of problem solving. What do they mean? Is this also true of STRIPS? --------------------------------------------------------- QUESTION 5. In what problem areas can reactive machines be quite effective, and under what conditions will planning be cost-effective? Explain the essential tradeoffs and design issues in integrating a priori planning with a reactive machine.