Responses to Questions
about Adaptation in CBR

The following questions have been addressed for the
ECAI-96 Workshop on Adaptation in Case-Based Reasoning

Questions taken from http://wwwagr.informatik.uni-kl.de/~bergmann/adapt-quest.html

1. About your approach:

Main task

Constructing routine design expert systems that perform parametric design.

Major characteristics of your application domain

The design systems are expressed in DSPL, a design expert system language [Brown & Chandrasekaran 1989].

The design systems are structured as hierarchies of ``agents'' dealing with decomposed subtasks.

Design requirements, knowledge about the artifact (structure, function, etc) are given.

Essentials of your approach to adaptation

Decomposition and recomposition.

Links to design p-s knowledge is required but is hard to derive.

Constraint propagation and symbolic manipulation may be needed.

Non-CBR synthesis if needed.

Special achievements

None to speak of yet.

Differences to other systems

The cases are fragments of Design problem-solving knowledge, as opposed to Designs, as found in many other systems.

Subcase assembly guided by a heuristically derived description of the problem decomposition.

Decomposition/recomposition feasible.

Retrieval/adaptation at different levels of granulity of the cases.

Not a formal world.

High degree of dependency between subcases, due to their formation from an expert's experience (knowledge compilation), making them context dependent.

Ability to project the outcome of execution of a system, without actually running it.

Ability to fix failure of above "execution".

References

DSPL: D.C.Brown & B.Chandrasekaran (May 1989) Design Problem Solving: Knowledge Structures and Control Strategies. Research Notes in Artificial Intelligence Series, Pitman Publishing, Ltd., London, England.

KDD: J.Liu & D.C.Brown (August 1994) Generating Design Decomposition Knowledge for Parametric Design Problems. Artificial Intelligence in Design '94, (Eds.) Gero & Sudweeks, Kluwer Academic Publishers, 1994, pp. 661-678.

Ming He & David C. Brown (June 1996) An Application of CBR in Design System Generation, AID'96 Workshop on CBR in Design.

2. Adaptation knowledge :

What kind of knowledge is required to perform adaptation?

Knowledge that helps explain/justify the cases, such as structure and function, as well as equations.

Is this knowledge only useful for adaptation (or also for from scratch problem solving, for assessment, etc)?

They are also useful in retrieval, evaluation, and synthesis.

How is it influenced by your task and domain?

There is useful design and artifact specific knowledge.

The design task is hierarchically structured.

The design p-s knowledge may have preconditions.

How did you acquire and represent the knowledge?

Given by the experts along with the cases, hand-coded, or derived.

Exists in the cases as parts of the code, e.g. conditions, as comments, or in the design object knowledge base.

3. Retrieval and indexing:

What is the relationship between retrieval and adaptation?

Using selected surface features of cases, indexing/retrieval provides adaptation with the close matches.

Indexing/retrieval provide assessment that will drive most of the adaptation process--one goal of adaptation is to eliminate/minimize the index mismatches.

How do you make sure that adaptable cases are found?

Guaranteed mainly through component name matching, as well as selected features (e.g., parameter order).

Do you change your case memory (index, access structure or similarity function) in order to reflect adapted cases?

Complete cases are stored in flat memory, while subcases make up complete cases hierarchically. Each individule complete case suggests the structure of the target system.

4. Adaptation:

Why do you need adaptation?

Can't be sure of exact match with prior design problems.

Case sources limited, hence less perfectly matching cases used.

Case fragments are used and they need to be modified and reassembled.

Varying design requirements may require variations in the previous systems.

Are your cases insufficient or is your retrieval function suboptimal?

Available cases are insufficient.

Optimal retrieval would ensure exact match. Context-dependent subcases make that hard to do, as the retrieval process would be required to reason about key aspects of location where subcase to be retrieved will be inserted.

How do you exploit your cases during adaptation?

Decomposed/Recomposed(probably from different cases).

Clipped: parts removed.

Parameter changed: parameterized and substituted with different values.

Reinstantiated: components modified.

Glued: holes filled by synthesizor.

What kind of knowledge do they encode?

Mainly design problem solving knowledge: designing/redesigning, decomposition, plans, selection, constraining, etc etc.

If several cases combined during adaptation: what happens when stitching a set of pieces together gives local conflicts, when the cases found cannot fill the new problem completely, or when there are many competing cases for the same problem?

Local conflicts occurred as value dependency violations can be fixed by rearranging the order of subcases in reassembly.

Gaps are filled by non-CBR synthesizor

Generally no much case competition, and indexing features are distinctive enough.

If a generic problem solver (a traditional from-scratch problem solver) is used during adaptation, please characterize it. How do you justify the use of case-based adaptation versus from scratch problem solving?

Synthesizor: generates small designer based on constraint network and symbolic evaluation.

With a reasonablly good case library, CBR is more suitable to solve a problem with the given size, while the synthesizor works on subproblems of much smaller sizes not covered by the case library.

Did you compare both alternatives?

For a large problem from-scratch synthesis is not viable. CBR provides larger, tested p-s knowledge to use. Synthesis can be used to ``patch'' small flaws in the assembled cases.

If adaptation is performed in co-operation with the user, please describe it. For instance, do you use an anytime algorithm or do you provide your results with an estimate of their quality?

No user cooperation.

5. Strengths, Limitations, Evaluation:

What are the general benefits and limitations of your approach (coverage, security, quality, ...)?

Benefit: The task becomes less intractable.

Limitation: Too small case library.

Limitation: Adapatation at syntactic surface level only.

What type of domain and task is your approach is best suited?

Hierarchical problems.

Highly context-dependent cases.

Expert p-s knowledge.

Non-formal design/planning.

What has to be changed for another domain?

??

How is your approach evaluated (e.g. theoretically, empirically)?

Experimentally and empirically.

Replication of existing systems from subcases.

What are the evaluation criteria (e.g. efficiency of problem solving, competence of the case-based system, flexibility of reuse)?

Effectiveness/Efficiency of resulting design system.

Is there a notion of computationally expensive adaptation versus an inexpensive one?

Simple syntactic changes are inexpensive.

Knowledge-based changes will be expensive.

Generation from scratch will be expensive at both design system generation time, AND at design system run time.

(When) should expensive ones be avoided?

When they're too expensive?

When cheap ones don't work?

6. Discussion Issues:

What issues would you like to discuss at the workshop?

Any adaptation techniques for this kind of application.

Techniques for subcase assembly (recomposition).