CBR for DesignDesign ResearchReuse of DesignDesign TaskDesign Task (figure)Approaches for design tasksThe PCM ModelSlide 8Mapping Design Task to CBR-cycleCase Based DesignA Framework for CBD SystemsCharacteristics of CBD SystemCBR System ArchitectureCase Retrieval for Innovative/Creative designCase RetrievalFish & Shrink AlgorithmFish & ShrinkSlide 18Fish & Shrink MethodSlide 20Fish and ShrinkStructural Similarity Assessment and Adaptation Using GraphsRequired FunctionalityStructural similarity assessment and adaptationSlide 25Example of structural similarity assessment: TOPOCombination GraphSlide 28Structural Adaptation by Case CombinationSlide 30SummaryReferencesCBR for DesignUpmanyu MisraCSE 495Design ResearchDevelop tools to aid human designersAutomate design tasksBetter understanding of designIncrease quality Take lesser timeImprove predictability of design REUSEReuse of DesignReuse old design – share intellectual property (IP)As the ‘reuse’ increases, the complexity increasesHuman assistance is mandatoryDirected towards assisting human designer rather than making intelligent decisions by ownDesign TaskRoutine design-is completely a part of a set of potential designs-all variables, their ranges, and knowledge to compute their values are directly derivable from the set-easily implementedInnovative Design-is partially derived from the set of potential designs-all components need to be derived. The knowledge is incomplete-design needs to be iteratively derivedCreative Design-no overlap with the set of potential design. The set needs to be extended-All components need to be definedDesign Task (figure)Approaches for design tasksFormulaeConstraintsRules and grammarsCBRPrototype based reasoningRoutine Only- Goel (1989), Domeshek and Kolodner (1992), Hinrichs (1992)The PCM ModelPropose – involves using domain knowledge to map part or all of the specification to partial or complete design proposalsCritique – assessment of the proposed design solution Modify – takes info about a failure of a proposed design as its input and then changes the design to get closer to the desired specificationThe PCM ModelThe CBR CycleMapping Design Task to CBR-cycleCase Based DesignDefined as “the process of creating a new design solution by combining and/or adapting previous design solution(s)”useful tool for intelligent system design in a domain where either an explicit model does not exist or one is not yet adequately understoodcan learn from interaction with userA Framework for CBD SystemsCharacteristics of CBD SystemCan produce complete and complex designs based on relatively small knowledge basedesign starts from complete cases, implicitly achieving trade-offs between several constraintsdesign history of existing cases makes design problem solving more efficientusing cases as a source of knowledge allows learning by storing new casesCBR System ArchitectureFour Knowledge Containers-Vocabulary: should be able to capture all salient features of the design. Task dependent-Case base: -- usage: cases can capture both regular/normal situations as well as exceptions/abnormal situations-- granularity: for task-oriented user support, the grain size of the cases matches that of the decisions made-Similarity measures: to compare queries and cases in their corresponding representations-Solution transformation: contains knowledge required to evaluate solutionsCase Retrieval for Innovative/Creative designFlexible case retrievalStructural similarity assessmentSimilarity assessment in terms of adaptabilityCase RetrievalFlexible Case Retrieval – Given a large case base, a problem, and a number of aspects that are relevant for similarity assessment, a set of cases is to be retrieved which show similar aspects as in the actual problemThe aim is to exploit different views on single casesImportance of certain aspects for similarity assessment may not be known at memory organization time- dynamic weighting is required - use kd trees, Case Retrieval Nets etc.Fish & Shrink AlgorithmUsed for Flexible Case RetrievalSelects and ranks potential cases from a large set of casesConsiders different aspects (representations) of casesMain idea “it should be more efficient to avoid searching in the nearby neighborhood of cases which have already been found to be inappropriate”Fish & ShrinkA representation function takes the case and outputs the aspect in the desired representation space : case 1: (20, empty, 0.05) case 2: (19, half-empty, 0.9)A distance function that can take two representations in space and calculate the distance of the two cases in this aspect namenamenameemptyhalfcas e )2(220)1(1casename2(case1,case2) 0.5emptycase )1(219)2(1caseFish & ShrinkFish & Shrink MethodView distance SDThe view distance from the query to some case is called test distance, and the view distance between two cases is called the base distanceThis is a basic distance function, researchers generally use their ownPresumption: View distance function have to satisfy the triangle equalitySD(Fx,Fy,W )  wii(Fx,Fy)Fish & Shrink AlgorithmFish and Shrink01Distance to the queryT1T2T3Structural Similarity Assessment and Adaptation Using GraphsTo retrieve structurally most similar casesStructured case representation → GraphFind maximum common sub graphCAD example for industrial building:Object represented by set of attributes describing its geometry and typeDifferent pipe system shows different topological relationsBuilding structure can be mapped onto its pipe systemRequired Functionality A compile function is used to translate the selected attributes and their relations into graphsA recompile function is used to translate the selected solution graphs into their attributes-based representationRetrieving case is conducted by selecting the case having maximum common sub graph with the problemStructural adaptation proceeds by combining case parts that are not included in the sub graphStructural similarity assessment and adaptationA graph g=(V,E), where V is the set of vertex andmcs(G) is the maximum common sub graph of a set of graphs GLet be the set of all graphs, O be the a finite set of objects represented by attribute values