From MCLAREN@cgi.com Tue Feb 27 11:05 EST 1996 Return-Path: MCLAREN@cgi.com Received: from cgi.com (cggate.cgi.com [128.129.3.207]) by pogo.isp.pitt.edu (8.6.9/8.6.9) with SMTP id LAA02315 for ; Tue, 27 Feb 1996 11:05:23 -0500 From: MCLAREN@cgi.com Date: Tue, 27 Feb 1996 11:07:29 -0500 (EST) Message-Id: <960227110729.21e24d21@CGIVA> Subject: My comp exam To: conati@isp.pitt.edu X-Vmsmail-To: @[MCLAREN.DIS]CONATI Content-Type: text Content-Length: 10755 Status: RO Bruce McLarens ISP Comprehensive Examination Committee: Kevin Ashley (Pitt), Richmond Thomason (Pitt), Manuela Veloso (CMU) Written Examination Due by 4:00 pm on October 11, 1995 Oral Examination: 10 am October 16, 1995 This examination comprises four questions. Your answers to each of the first three problems should each be no more than 5 pages of single-spaced text in 12pt font. The final problem, consisting of 5 parts, includes some discussion/essay questions as well as some practical exercises. Plan to write not more than 15 pages of single-spaced text in 12pt font for the discussion/essay questions. Please provide three copies of your answers. 1. (Rich Thomason) The authors of "Living with CLASSIC" say: "Work on the KL-ONE knowledge representation system [Brachman & Schmolze, 1975] in the late 1970s inspired the development of a number of frame-based knowledge representation systems. These systems have all embraced the ideas of [1] frames as structured descriptions, [2] differentiation between terminological and assertional aspects of aspects of knowledge representation, [3] and the central nature of subsumption and classification inferences." -- Principles of Semantic Networks, J. Sowa, ed., 1991, p. 402. Some of these features are shared by other frame-oriented systems, others are peculiar to the KL-One systems. Clarify these features, and discuss their advantages and disadvantages in knowledge representation and reasoning. 2. (Rich Thomason) Representing information using First-Order Logic and using resolution theorem-proving as the reasoning method has many theoretical advantages. What are the advantages? However, experience has shown that this methodology is plagued by practical problems having to do with efficiency. Give a general description of some of the techniques that can be used to overcome these problems, while still using the resolution method. 3. (Kevin Ashley) It is widely believed that adaptation is a corner stone of case-based reasoning. See, for instance, the discussion in Case-Based Reasoning, J. Kolodner, 1993, p. 21: In case-based problem solving, old solutions are used as inspiration for solving new problems. Because new situations rarely match old ones exactly, however, old solutions must be fixed to fit new situations. In this step, called adaptation, the ballpark solution is adapted to fit the new situation. On p. 395, she presents ten methods by which adaptation can be performed and devotes two chapters (11 and 12) or a total of 75 pages to elaborating them. By contrast, Ralph Barletta, a well-known expert on applications of case-based reasoning, has declared that the trade offs of benefits and costs in delivering an adaptation capability in industrial applications of case-based reasoning simply do not justify the effort. As far as Barletta is concerned, adaptation is a non-starter in real world applications of case-based reasoning: it does not work, it cannot be made to work, and people will not use it even if it does work. Use these contrasting opinions to frame a discussion of adaptation in case-based reasoning. Who is right and why? What are the problems in making adaptation work? Are there promising approaches? What are they and why are they promising? If there are no promising approaches, how can there be case-based reasoning without adaptation? 4. (Manuela Veloso) Problem -- Machine Learning and Planning In this problem, you are to analyze the use of machine learning applied to problem solving/planning. There are a few discussion/essay questions and two practice exercises. The essay questions and the practical exercises are related to each other and therefore it may help to interleave your work for the practice and discussion questions. 4.1. (a) Enumerate and discuss a few reasons why problem solving and planning is a complex task. State the general complex issues related to a domain-indepdent AI problem solving or planning system, but feel also free to focus your arguments with illustrative domain-specific examples. (b) Machine learning has been used to overcome some of the problems faced by planning systems. What are the main approaches that you know have been successfully applied to automatically improve the efficiency of a problem solver? In general, efficiency is not directly related with quality of the solution. Explain why this is the case and discuss a learning approach (existing or hypothesized by you) in which both efficiency and quality would be improved. (c) Explain the difference between explanation-based learning and case-based reasoning when applied to planning. (d) State the advantages and disadvantages of learning rules versus learning cases in planning. 4.2. Case-based reasoning involves the potential accumulation of large case libraries. Discuss whether you think that experts in fact do or do not accumulate such large case libraries. If you think they do, discuss how you think experts can retrieve applicable relevant cases efficiently. If you think they do not, discuss how rules are formed from examples. If you think that both rules and cases are maintained, discuss a transition model from examples to cases to rules and possibly vice versa. Give examples of problem solving/planning AI systems that are able to reason both about rules and cases. Do these systems have a dynamic transition model from cases to rules and vice versa? How or why not? 4.3. (a) Most (if not all) of the similarity metrics used in case-based reasoning are static, i.e., the weights given to specific features are predetermined. Discuss why this may be a limiting factor to apply case-based reasoning to dynamic real-world problems. Please illustrate with examples from your own research or from your readings. (b) Suppose that you are advising a new graduate student and you (and the student) are particularly interested in investigating how to learn dynamic similarity metrics in case-based reasoning systems. If you know of one developed case-based reasoning system that can dynamically change the similarity metric, explain its features. If you dont, design a procedure for a research project for your student, advising the student in what you believe will be a potentially successful approach. 4.4. Consider the following three operators from a logistics transportation domain. (Operator LOAD-AIRPLANE (Operator UNLOAD-AIRPLANE (preconds (preconds (( AIRPLANE) (( AIRPLANE) ( OBJECT) ( OBJECT) ( AIRPORT)) ( AIRPORT)) (and (and (at-obj ) (inside-airplane ) (at-airplane )) (at-airplane )) (effects (effects ((add (inside-airplane ((del (inside-airplane )) )) (del (at-obj ))))) (add (at-obj ))))) (Operator FLY-AIRPLANE (preconds (( AIRPLANE) ( AIRPORT) ( AIRPORT)) (effects ((add (at-airplane )) (del (at-airplane ))))) Consider now the planning situation illustrated in Figure 1. This planning problem includes three cities, city1, city2, and city3, each with one post office and one airport. Initially, there is one package, package1, at airport1, and one airplane, plane1, at airport2. The goal of the problem is to bring both package1 and plane1 to airport3. (a) Use backward-chaining to generate a plan to the problem shown in Figure 1. Show the search space, but do not expand alternatives that fail or lead to an unoptimal (longer) solution. However, clearly identify what are the alternatives available for each decision point in the search for a solution to the problem. (b) Mark the decision points found in two distinct classes, namely the ones that lead to failure (F) (like loops in the search space) and the ones that lead to unoptimal solutions (U). (c) Apply explanation-based learning to learn a control rule that selects the correct alternative for a decision point of your choice. City1 City2 ------------------------------ ------------------------------ | Post Office1 | | Post Office2 | | | | | | | | | | Airport1 | | Airport2 | | (Package1) | | (Plane1) | | | | | ------------------------------ ------------------------------ City3 --------------------------------- | Post Office3 | | | | Airport3 | | | --------------------------------- Initial State: (and (at-obj package1 airport1) (at-airplane plane1 airport2)) Goal State: (and (at-airplane plane1 airport3) (at-obj package1 airport3)) Figure 1: A Problem - Initial State and Goal State 4.5. Consider the following two operations in the Blocks World: unstack (x, y) putdown(x) preconds: (on x y) preconds: (holding x) (clear x) adds: (on-table x) (arm-empty) (clear x) adds: (holding x) (arm-empty) (clear y) dels: (holding x) dels: (on x y) (clear x) (arm-empty) Suppose that our initial state is as follows: ---- (on A B) | A | (on-table B) ------ ---- (on-table C) | C | | B | (clear A) ============== (clear C) (arm-empty) and the goal is (clear B). (a) Show the search space explored by backward chaining from the goal. (b) Use this example to show how explanation-based learning (EBL) would learn an operation for achieving the goal (clear ) and the preconditions of this operation. Present the result of learning in the form of an if-then-else rule that describes a situation from which the target goal, (clear ), can be achieved. (c) Now consider the goal (clear C) and the following initial state: ---- | A | ---- | B | ---- ---- | D | | C | =================== Show that the learned rule does not help in this problem. Why? What conclusion about EBL learning and the precise match reuse process can you draw from this example? (d) One can relax the use of learned rules and apply them in similar (not necessarily identical) situations. Show how the use of a learned planning case by analogical reasoning with multiple case reuse and partial match can help reduce the search in our last problem. What conclusion can you draw about analogy as compared to direct application of learned rules?