Readings

Bhatta, S.R., Goel, A.K., Prabhakar, S. (1994) Innovation in Analogical design: A Model-Based Approach, Artificial Intelligence in Design '94, Gero and Sudweeks (eds.), Kluwer Academic Publishers, pp.57-74.

Branting, K.L. and Aha, D.W. (1995) Stratified Case-Based Reasoning: Reusing Hierarchical Problem Solving Episodes, Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal, Canada, August 20-25.

Branting, K.L. (1997) Stratified Case-Based Reasoning in Non-Refinable Abstraction Hierarchies. Proceedings of the Second International Conference on Case-Based Reasoning (ICCBR-97), Providence, Rhode Island, July 25-27, 1997, Lecture Notes in Artificial Intelligence 1266, pp. 519-530.

Giuchiglia, F. and Walsh, T. (1992) A theory of Abstraction, Artificial Intelligence 57 (1992), pp. 323-383.

Goel, A. K. (1997) Design, Analogy and Creativity. IEEE Expert, Intelligent Systems &their Applications, May/June 1997, pp. 62-70.

Kannapan, S. (1993) Function Metrics for Engineered Devices, AAAI Workshop on Reasoning about Function, Washington, D. C., July 11, pp. 53-59 (More detailed version in Journal of Applied Artificial Intelligence, Vol. 9, No. 1, 1995, pp. 45-64)

Notes

Bhatta, S.R., Goel, A.K., Prabhakar, S. (1994) Innovation in Analogical design: A Model-Based Approach, Artificial Intelligence in Design '94, Gero and Sudweeks (eds.), Kluwer Academic Publishers, pp.57-74.

• types of analogy:
1. within-problem analogy - involves transferring knowledge from one subproblem to another subproblem within the the context of solving the same problem
2. within-domain analogy - involves transferring knowledge from one problem to another problem in the same domain (e.g. case-based reasoning)
3. cross-domain analogy - involves transferring knowledge from one problem in a domain to another problem in a different domain
• stages of analogical reasoning (Gentner 83):
1. retrieval of a source analog
2. transfer of knowledge from the source analog to the target analog
3. evaluation of the solution to the target problem
4. generalization over the source and target
5. storage of the solution to the target problem and the generalization
• questions regarding the analogical reasoning:
• what is are content and representation of source analogs?
• how is the target problem be specified?
• how is a source analog retrieved? (superficial or deep features)
• how is the retrieved source analog mapped on to the target problem?
• how is knowledge transferred from the source to the target? (directly or through a shared abstraction)
• how does the transferred knowledge enable completing the solution?
• how is the solution to the target problem evaluated?
• what may be learned from the target problem and how? (generalization)
• is the target analog and/or generalization worth storing and if yes how? (indexing)

Model-Based approach to Transformational Analogy

Branting, K.L. and Aha, D.W. (1995) Stratified Case-Based Reasoning: Reusing Hierarchical Problem Solving Episodes, Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal, Canada, August 20-25, 1995.

• approaches for reducing complexity of indexing and matching complex cases:
1. precompute some portion of the match between cases (e.g. organizing cases into a hierarchy partially ordered by subgraph relations);
2. use case abstraction for indexing and matching;
• previous use of abstraction in indexing has focused on thematic abstraction (goals, expected failures)
• previous use of abstraction in matching has focused on feature generalization (finding common ancestors of new-case and old-case features)

• stratified case: a case whose representation has multiple abstractions
• benefits of stratified CBR:
• indexing and retrieval: a more abstract solution can provide an accurate index to a less abstract solution (consists of the more important aspects of te less abstract solutions)
• matching: comparing cases in abstract space may be much less expensive
• adaptation: stratified cases can be reused at te most specific level of abstraction without requiring adaptation of less abstract, non-matchingfacts
• the ideas are presented on an example (route-finding tsk)
• the cases used are generated starting from the highest level of abstraction and are refined to the lowes level
• the solution at each level is considered a case
• a refinement of a case us called its child (the case is called the parent of its refinement)
• distinct cases may have identical parents (they may be identical at higher level)
• cases are organized in a forest of taxonomic trees
• a case library consists of a taxonomic forest of cases sharing a common abstraction hierarchy but distinct pairs of start and goal positions (problems)
• stratified CBR algorithms:
• start by retrieving from the case library the set of most specific matching cases
• the search begins with the root of the case library,
• continues by recursing ith its children,
• until it reaches the ground level, or cases that no longer cover the problem

COVER: randomly selects one of the most specific matching cases and performs a hierarchical search at the next lower level of abstarction

CLOSEST: starting with the most specific matching cases finds the refinements of each case, adapts the refinement and selects the refinement having the shortest adapted solution; this is repeated till the ground level is reached

CLOSEST THRESHOLD: attempts to recognize situations in which adapting an existing case will be more expensive than problem solving (if there are no matching cases it uses search at the highest level of abstraction, then compares the solution found to the adapted top level cases and decides whether to use CLOSEST of hierarchical search).

• empirical evaluation to explore the following hypotheses:
1. reusing stored case solutions decreases search cost
2. reusing abstract case solutions decreases cost more than reusing only ground-level solutions
3. partial matching yields lower search costs than perfect matching
4. preventing extensive partial matching (via thresholding) yields the best performance (on this task)

Branting, K.L. (1997) Stratified Case-Based Reasoning in Non-Refinable Abstraction Hierarchies. Proceedings of the Second International Conference on Case-Based Reasoning (ICCBR-97), Providence, Rhode Island, July 25-27, 1997, Lecture Notes in Artificial Intelligence 1266, pp. 519-530.

• benefits of the use of case abstarction:
• indexing and retrieval: a more abstract solution consists of the most importanat aspects of the less abstract solutions - they can provide an accurate index
• matching: matching in more abstract spaces may be less expensive
• adaptation: an abstraction of a stored case may be much easier to reuse; stratified cases can be reused at the most specific level without requiring abstraction

Can stratified CBR be applied in hierarchies without the downward refinement property?

• nonrefinable abstractions - cannot be refined into a valid solution at a lower lavel of abstraction (they may occur due to the way abstraction is done)
• nonrefinability may cause problems to stratified CBR:
1. an abstract case that appears to be reusable may turn out not to have useful children
2. the computation expense of using hierarchical problem solving for adaptation is likely to be higher in nonrefinable hierarchies

• empirical evaluation to explore the following hypotheses:
1. stratified search can reduce search even in nonrefinable hierarchies
2. the performance of CLOSEST relative to hierarchical problem solving is better for nonrefinable than for refinable hierarchies - infirmed
3. bstraction hierarchies created bottom-up lead to better peformance by stratified CBR than those created top-down in nonrefinable hierarchies - not always true

Kannapan, S. (1993) Function Metrics for Engineered Devices, AAAI Workshop on Reasoning about Function, Washington, D. C., July 11, pp. 53-59 (More detailed version in Journal of Applied Artificial Intelligence, Vol. 9, No. 1, 1995, pp. 45-64)

• function definition
• thinking of a purpose for a device requires thinking of a context for the device where a certain goal is to be achived.
• the notion of purpose relates a device, the behavior of the device, a context, an intended interpretation of device behavior in the context and a goal for the context
• the notion of purpose needs to include attributes in addition to behaviors !!!
• derivability of function
• the functions of components can be computed by analyzing the trace of verification of the device behavior
• function metrics:
1. sharing (component) - number of intents supported by the component / total number of intents of the device
2. overload (utilization) - number of intents the utilization supports / total number of intents of the device
3. modularity (intent) - number of components (utilizations) that only support that intent / number of all components (utilizations) that support that intent
4. efficiency (component (device)) - number of utilizations (intents) / number of modeled behaviors
5. redundancy (intent) - number of disjunctions "to what extent other intents can substitute for it"
6. fault tolerance (intent and two usages that that support it) - number of utilizations that are not in the intersection of te usages / number of utilizations in the two usages
7. criticality (utilization) - number of utilizations supported by string functionality / total number of intents supported.
8. complexity:
• component complexity (intent ) - number of components supporting it
• utilization complexity (intent) - number of utilizations supporting it
• complexity (device) - number of intents for the device

Giuchiglia, F. and Walsh, T. (1992) A theory of Abstraction, Artificial Intelligence (1992) 57, pp. 323-383.

Goel, A. K. (1997) Design, Analogy and Creativity. IEEE Expert, Intelligent Systems &their Applications, May/June 1997, pp. 62-70.

• two characterizations of creative design (withing a general theory of information processing and arising from specific theories of design)
• analogy-based creative design:
1. why? (what task is analogical design used for) - analogical reasoning can help address any design task.
2. what? (what is the content of the knowledge transferred) - depends on the design task addressed
3. how? (what are the methods for reminding and transfer) - may depend both on the design task and on the knowledge content of the transfer.
• in general analogical transfer requires the use of generic abstractions
• learning of generic abstractions is an important process of analogical reasoning
4. when? (what is the strategic control of processing)
• e.g. learning of generic abstractions can happen at:
1. storage time - when a new design is stored (eager learning)
2. retrieval time - when a known design is reminded (lazy learning)
3. problem-solving time - when knowledge is transferred (lazy learning)
• examples of generic abstractions:
1. design prototypes (Dssua) - abstraction over specific design instances FBS model)
• the abstraction occurs at transfer time
2. design concepts (Syn) - maximal common subgraph
• ssumes that the topological pattern is given
3. design patterns (Ideal) - design analogs are indexed by their functions and organized around design concepts that specify the primitive functions of a design
1. esign patterns are generated at storage time.