s a n t i a g o   v   l o m b e y d a

   on

   k r i t i k :
   c a s e - b a s e
   d e s i g n   s y s t e m

   by

   A   G o e l ,   S   B h a t t a ,   E   S t r o u l i a

k r i t i k . p s


p a p e r   s u m a r y


Case-Base reasoning describes the process by which new situations are solved (computationally) by retrieving and modifying old such situations. Once such adaptation takes place and a correct solution is found, the results become part of the systems knowledge base. In these such systems, the issues that become the centerpoint of the research are: case representation and organization (storage,) indexing of such cases, case retrieval, evaluation, modification, and verification.

Kritik ("designer" in Sanskrit) is one such system. Its domain is Function-to-Structure design tasks in engineering. Function-to-Structure meaning, cases which may be indexed by function, and then mapped to their structure. Thus, areas of engineering touched were such as electric circuits and heat transfer systems (i.e. substance coolers.)

Kritik is in fact "one of the earliest systems to integrate case-base reasoning and model-based reasoning." (p.3) It addresses each of the issues faced in case-base reasoning revolving around the main idea of specifying cases in Structure-Behavior-Function (SBF.) Using what they call as SBF language, Kritik is able to describe a model not only in terms of its underlying structure, but it's ultimate functionality, as well its behavior. Each of these terms are described as set of attributes, which make be links across terms. Further, there may be a central substance flowing throughout all components (i.e. electricity), or a component/structure mode which links all pieces (i.e. mechanical arm and its joints positions.)

Structure includes such attributes as components and structural relations. Function is described by the output the design contributes (makes) and the causal behavioral sequence (by) which makes such possible. Function further may include fields such as conditionals (give, provided) as well as the stimulus, which is the trigger for the functionality. Meanwhile behavior is described as a sequence of behavioral states with transitions between them. Behavioral states as described in Kritik with attributes proper of a doubly linked list, as well as the necessary causal behavior for the transition to have reached this state (enabled by) and to go to the next state (enabling.) Other information encapsulated in Behavioral states is the substance state or component state. Finally Behavioral Transitions describe the different effects and needed environment attributes for a transition to take place.

With this basic infrastructure Kritik is able to receive the query for a new design as a description the functionality: the given (starting attributes and/or input) and the makes (desired attributes and/or output.) Once such as received, Kritik searches through its Case Memory, and returns a list of possible candidates (if any,) ordered by the ease of adaptation. Here the issue of indexing and organization is very well addressed by SBF, since the Case Memory is indexed as a hierarchical tree organized by functionality. Thus finding possible candidates means traversing the tree with a heuristic of what makes one function similar or different from another one (distance.) It is important to highlight that such heuristic has to consider some modifications simpler that other ones. An example cited in the paper, is that it is easier to replace Sulfuric Acid for Nitric Acid in a cooling system, that replacing a high-acidity substance for a low-acidity substance, due to its obvious requirements of the environment and the design. The selection algorithm is given and explained in page 24, figure 16.

Once a candidate is retrieve, it is Kritik's next step to diagnose it as to its "faults", things that need be modified. Modifications come up as a consequence of functional differences between the needed design and the candidate, thus mapping into structural modifications. The rest of modifications will come up as part of execution and evaluation of the candidate. The Diagnose algorithm is also give and explained in page 29, figure 17.

The next step is "repairing faults" in the candidate model. For that , first "SBF proves a vocabulary for expressing certain type of functionality differences between design cases, such as substance difference, substance property value difference, ..." In Kritik2, the repair interleaved with the evaluation process, thus plans for both are generated and performed. The evaluation of modifications itself, involves the actual simulation of behavior (cause and effects) within the design. As behavior states change, links are propagated, the model has to be updated, reevaluated, and thus changes made sound. The Model Revision Algorithm is supplemented in page 38, figure 19.

The final step in this subview of the process is the storage of new cases. This is intrinsic with the indexing, and is performed in a breath first algorithm, as described in page 41, figure 20. Since modifications are done throughout evaluation, it is necessary to learn as the process goes along. Thus, every successful modification is recorded and "learnt," for though the new design may not be finished, the modification done may be helpful for another one to eventually take place.

Theoretically, Kritik proved to be computationally feasible. When tested it successfully modified cases to resolve a query, as well as used previously learnt knowledge for new results. Kritik also proved to be efficient, though the number of cases tested was small. In fact when it comes to analyze scalability the issue of memory requires is not as much a concern to the authors, as is the issue of compiling the knowledge itself. Furthermore SBF is an inadequate language to comprise every aspect in engineering. When introducing different type of models, SBF fell short. However, the case base reasoning as addressed in Kritik is strong, and with modifications done to SBF for specific environments, new tasks have been successfully execute (such as navigation, though the results are premature.)

SBF and Kritik do mark a great step stone towards reaching feasible and efficient case base reasoning systems. SBF provides a good topology, and it successfully describes the functionality of a design ("capture[s] a reasoner's comprehension of how a device works.") It is in the view of the authors that the issues raised by case base reasoning implementation are truly what must be studied in order to further progress.

Kritik offers strong algorithms for adaptation of models, diagnosing, and learning; along with a language/scheme (SBF) capable of capturing the function of an inert design. It is the believe of the person writing this summary, that Kritik offers a lot in terms of machine modeling and knowledge base systems; though the efficiency and feasibly of the system needs further development to the point that a "full" case memory may be exploited, and the Kritik may prove useful as not only a great theoretical/research tool.

Bibliography:
Goel, Ashok K, Sambasiva R. Bhatta, Eleni Stroulia; "Kritik: an early case-based design system"; Georgian Institute of Technology; Atlanta, 1996.

Word 6.0 for win 95
Word 6.0 for mac






p r e s e n t a t i o n


t o p

i. title

ii. intro

iii. issues

iv. s b f

v. structure

vi. function & behavior

vii. adaptive design

viii. evaluation

ix. conclusions

Word 6.0 for mac Claris Works for mac Word 2.0 for win



[ Back to Home Page | Back to KB Page | mcs771: Knowledge Base Systems | A Goel's Home Page ]

P A G E   B Y   S A N T I A G O   L O M B E Y D A