EXPERT SYSTEMS Most expert systems use the method of HEURISTIC ASSOCIATION. The general ARCHITECTURE of expert systems looks something like this: --------------------- | | | Inference Engine | | (Control) | | | --------------------- / \ / \ / \ / \ / \ / \ -------------------- ------------------ | | | | | Knowledge Base |------------| Database | | (Heuristic | | (General Data, | | Associations) | | Static Facts) | | | | | -------------------- ------------------ The CONTENT of associations is specific to the TASK being performed, e.g., the associations in a medical diagnostic expert system would map symptons into diseaes. The associations are usually represented in the LANGUAGE of rules, e.g, IF ... THEN ... Expert systems are often called "rule-based systems", because they are built on a production system architecture (see below) and they use rules to represent knowledge. (But we'll see non-rule-based expert systems too.) The control of processing can be Forward Chaining (from antecedents to consequents), or Backward Chaining (from consequents to antecedents) %---------------------------------------------------------------------------- Examples: - Finding molecular structure: DENDRAL - Locating oil and mineral sites: PROPECTOR - Medical diagnosis: MYCIN, INTERNIST/CADUCEUS - Tax consultant - Computer system component selection (R1/XCON) - Analyzing pulmonary problems (PUFF) - Optimal autoclave layout (CLAVIER) - ... PUFF, XCON (a descendent of R1) and CLAVIER are good examples of systems that have been very useful commercially. Expert system tasks and problem categories (adapted from Waterman 1986): - INTERPRETATION (UNDERSTANDING): Forming high level conclusions or descriptions from collections of raw data. - PREDICTION: Projecting probable consequences of given situations. - DIAGNOSIS: Determining the cause of malfunctions in complex situations based on observable symptoms. - DESIGN: Determining a configuration of system componenents that meets certain performance goals while satisfying a set of constraints. - PLANNING: Devising a sequence of actions that will achieve a set of goals given certain starting conditions. - MONITORING: Comparing the observed behavior of a system to its expected behavior. - DEBUGGING and REPAIR: Prescribing and implementing remedies for malfunctions. - INSTRUCTION: Detecting and correcting deficiencies in students' understanding of a subject domain. - CONTROL: Governing the behavior of a complex environment. %---------------------------------------------------------------------------- PRODUCTION SYSTEMS (Post, 1943: computational model; Newell and Simon 1972) A production system is a set of test-action or situation-action pairs, also known as production rules or if-then rules (hence the name "rule-based system"). A production system is Turing equivalent; one can built a universal Turing machine with one, and hence do everything computable. Two types of justifications for production systems: 1. Psychological modelling 2. Knowledge engineering A production system has 3 parts: 1. A set of production rules ("rule base", "knowledge base", "production memory"). 2. A data base that can be examined and written ("data base", "world model", "context", "STM (short term memory)", "working memory"). The short term memory sometimes has a size limit (to model human like memory which has a size of about 5 +/- 2 items). 3. A mechanism to evaluate rules and select an action to perform ("interpreter", "control mechanism"). PRODUCTION WORKING Algorithm: MEMORY MEMORY WHILE match(tk,fi) p1: (t1 --> a1) f1 for some test tk and some fact fi p2: (t2 --> a2) f2 DO: ... ... 1. Find all matching p's (the pk: (tk --> ak) fi CONFLICT SET) ... \-----MATCH--/... 2. Decide which one to "fire" ... ... (CONFLICT RESOLUTION) pn: (tn --> an) fm 3. Execute its action (add or delete a fact in memory) Ideal production system: 1. All tests are evaluated simultaneously w.r.t. current data base. 2. There is a mechanism to resolve ties. 3. Right hand side actions are simple: they can only add or delete data base elements. They can't include procedures to fire other rules. Productions can perform the following actions: 1. Write a new item into short term memory at the front, dislodging the last item from the back. 2. Note items in short term memory by moving them to the front. 3. Mark an item in short term memory, to avoid it being matched again and again to the same production rules. 4. Send a message requesting information, or receive a message and place the information at the front of short term memory. Production systems that do not model short term memory explicitly (i.e., don't maintain a queue for short term memory) basically perform the following actions: 1. Place an item into short term memory. 2. Look for (or match) an item in short term memory. 4. Productions "communicate" only via the data base. Real production systems: 1. In each cycle, tests are evaluated sequentially. 2. Actions activate or build other production rules (so rules communicate outside the data base). Characteristics necessary for successful application of this technique: 1. Problem should lend itself to a modular solution. 2. Solution should not be hierarchical (because all productions are "equal"). 3. Solution should be based more on declarative than procedural knowledge. (These are not hard and fast rules because, since production systems are Turing equivalent, they can be used for any computational problem. However, the presence of these characteristics makes them a more "natural" choice.) Advantages of production systems: 1. Psychological plausibility. 2. Homogeneous knowledge representation (ideally). All knowledge is represented using the same kind of rules in the same kind of format. 3. Modular (ideally). In theory, each rule is independent. 4. Allows incremental growth (so good for learning). You can (ideally) add a production without worrying about what else the system knows because of modularity. (You can even semi-automate the learnign process, e.g., TEIRESIAS helps an expert add and revise rules for use by MYCIN.) 5. Allows well-defined and almost unrestricted communication between pieces of knowledge. 6. Natural way to represent many kinds of knowledge. Disadvantages of production systems: 1. Inefficient. 2. Opaqueness, unexpected interactions. Very hard to figure out the effects of adding a rule; very hard to figure out what depends on what and how. 3. Difficult to design. 4. Difficult to debug. 5. Is knowledge really rule-based? Major issues: Theoretical: How to represent knowledge in a rule based manner. Engineering: How to get experts to voice their internal rules. Design: Control: how to select which production to fire. Methods for selecting which production to fire (control mechanism): 1. Serial evaluation -- first matched. This is equivalent to parallel evaluation with a static ranking on rules. 2. Production with most specific (stringent) test is allowed to fire. 3. Most recently used production is allowed to fire. 4. Production most useful in the past is allowed to fire. 5. Dynamic ranking by some external process (not a "pure" production system). 6. Other methods. Example: A production system to help Merv find the bananas. (In a "pure" production system, right hand side actions would explicitly manipulate the database by adding and deleting assertions.) Data base: Current world state represented as an assertion such as (ON GRASP DOOR). Control scheme: Doesn't really matter because rules are mutually exclusive (except R3 and R6 below, but they make the same recommendation). Production rules: R1: if (ungrasping off (not window)) then push-right. R2: if (ungrasping on (not window)) then climb-down. R3: if (grasping * (not window)) then ungrasp. R4: if (ungrasping off window) then climb-up. R5: if (ungrasing on window) then grasp. R6: if (grasping off *) then ungrasp. R7: if (grasping on window) then STOP. Notes: Need a production rule to recognize the goal state and stop. Control issue circumvented because of clever design of rules. 12 states, 7 rules: pretty good (not brute force). Designer responsible for inventing the rules. Speed and quality of solution depends on the particular rules we write. Psychological validity: 1. Sequence of rules represent "protocol" of "thoughts". "Human problem solving" (Newell and Simon, 1972): Did protocol analysis of humans solving cryptarithmetic, tower of hanoi, etc. 2. Newell's production system exhibits the no serial-position effect. Difficult to get this in a search system. 3. Anderson's ACT. 4. The timings of a production system can be made to match human timings. (However, since a production system is a Turing machine that can encode any algorithm, this is not really evidence.) Applications of production systems: 1. Psychological modelling (above). 2. Expert systems. Where is the "intelligence" in a production system? Totally in the production rules. %---------------------------------------------------------------------------- EXPERT SYSTEMS - A computer program that solves expert problems by expert knowledge, or handles tasks that require detailed knowledge in a particular area. (Expert knowledge is distinct from commonsense knowledge.) - Operates in a micro-world where a particular kind of problem solving is required. - Encapsulates a significant portion of the specialized knowledge that an expert human problem solver would bring to bear. - Usually exhibits performance approaching that of an expert. - Usually built on a production system, with certainty values attached to hypotheses - User interface is often critical Development history (Winston and Prendergast 1984): (Expert systems are shown in upper case, expert system shells in lower case) HEARSAY-I ------> HEARSAY-II ---------> hearsay-III -----> | | ------> HARPY ---------> age -------------> MYCIN -------------> emycin ---> PUFF | -----------> TEIRESIAS | ---------> PROSPECTOR ---> kas -------> | ----------------> rita ----> rosie ---> INTERNIST -------------------------QMR-> ---- CASNET -------------> expert ----------> psg ---------> ops -----> ops4 --> ops5 --> | --> R1 SAINT -------> SIN ------> MATHLAB --------> MACSYMA -------------------> ----- DENDRAL ----------> META-DENDRAL -------------> ------1965---------------1970---------------1975---------------1980------ Research issues - Knowledge acquisition - Knowledge representation - Inference and uncertainty - Explanation - Theoretical limitations Knowledge engineering - Transfer of experience or knowledge from expert into machine. The knowledge engineer "debriefs" the expert. Expert system shells ("empty" expert systems): E.g., EMYCIN (Empty MYCIN) -- general expert system shell created by removing all domain knowledge from MYCIN. Can be used by knowledge engineers to create expert systems by adding domain knowledge (e.g., PUFF was created in 5 man years using EMYCIN, a remarkable saving). A good expert system application: (Davis 1982) - Doesn't require common sense - Takes an expert a few mintues to a few hours to solve - has an expert available and willing to be committed Hayes-Roth (1981) - is non-trivial but tractable, with promising avenues for incremental expansion Expertise - Reflects empirical associations (if A, then B is likely) - Requires the ability to: - Recognize problem (situation) - Recall solution (potential) - Is often associational - May require "intuition" (Do experts leap to a conclusion, or perform formal inferencing?) Experts - Know more than they can verbalize - Can discuss and debug in context, but not so easily in the abstract - Have heuristic knowledge - Are uncomfortable admitting tricks of the trade - Have knowledge focussed on one particular domain - Take about 10 years to develop expertise Questions: - What's the difference (w.r.t. knowledge and reasoning processes) between a novice and an expert? Do they possess different wetware? - How does an expert organize his knowledge? - Why does it take so long to become an expert? - Do experts (a) solve problems (b) recognize solutions or (c) both? Structure of knowledge: - Conclusions must arise form a finite set of specific elements - Evidence must be reliable obtained - Knowledge base used to link evidence to conclusions - Reasoning (control strategy) needed to guide the system Meta rules (rules on rules): E.g., Use an experienced engineer's advice over brade new hire. E.g., Use the design with fewer parts if costs are nearly equal. Control issues: - At the rule level, similar control issues to production systems. - The larger issues: - What overall reasoning strategy to implement so as to reach accurate conclusions efficiently? - E.g., Backward chaining: No pre-ordering necessary, less efficient, asumies no circular reasoning possible (no loops). - Scoring function: Need not be optimal; can use heuristics that will work in limited circumstances. - Examples (problem solving methods): - Generate and test (DENDRAL) - Contingent back chaining (MYCIN) - Bayesian inference network (PROSPECTOR) - Forward chaining production system (R1/XCON) - Distributed hypothesize and test (HEARSAY) - Questioning strategies to ensure system asks reasonable questions: - Ask least costly question - Ask question regarding most highly weighted hypothesis - Ask question that can produce marked change in confidence level - Combining multiple reasoning strategies Examples of rules: MYCIN: if the stain of the organism is gram-positive and the morphology of the organism is coccus and the growth conformation of the organism is clumps then (0.7) the identify of the organism is staphyloccus R1: if the most current active context is distributing massbus devices and there is a single-port disk drive that has not been assigned to the massbus and there are no unassigned dual-port disk drives and the number of devies that each massbus should support is known and there is a massbus that has been assigned at least one disk drive and this massbus should support additional disk drives and the type of cable needed to connect the disk drive to the previous device on the massbus is known then assign the disk drive to the massbus PROSPECTOR: if magnetite of pyrite in disseminated or veinlet form is present then (2, -4) there is favorable mineralization and texture for the propylitic stage Research issues in expert systems: 1. Meta-reasoning. 2. Explanation. 3. Transfer of expertise. 4. Multi-expert consensus. 5. Ability to reason from underlying models. 6. Case-based reasoning: reasoning from previous experience. 7. Learning and knowledge acquisition. %---------------------------------------------------------------------------- Readings: 1. Charniak and McDermott, chapter 8. 2. B.G. Buchanan and E.A. Feigenbaum, "Dendral and Meta-Dendral: Their applications dimension", readings list. 3. E.H. Shortliffe, "Consultation systems for physicians: The role of AI techniques", readings list. 4. R.O. Duda and E.H. Shortliffe, "Expert Systems Research", Science, Vol. 220, No. 4594, April 1983. 5. M. Stefik, et al, "The Organization of Expert Systems: A Tutorial", Artificial Intelligence, 18, pages 135-173, 1982. 6. D. Waterman, "A Guide to Expert Systems", Addison-Wesley, 1986. %---------------------------------------------------------------------------- DENDRAL (Buchanan et al) Heuristic DENDRAL (Feigenbaum et al 1971) Input: Empirical formula Fragment mass table (from mass spectrograph) Output: Organic structure C8 H16 O ---\ O \ || | ------> DENDRAL -----> CH3--CH3--C--CH2--CH2--CH2--CH2--CH3 | | | / | | | | | ---/ ----------- Performs better than most chemists. DENDRAL parts: Experise: Prelimary inference maker Families of organic compounds Data adjuster Generate and adjust fragment mass table Structure generator Simple combining theory valence info Prediction Rough mass spectrometer theory Evaluation Comparison metric consistency rules Each part is a production system. DENDRAL is efficient because it assumes that it is interacting with a knowledgeable user who can delete certain hypotheses from further consideration. Basic problem solving paradigm: GENERATE AND TEST Given an "important" fragment mass, find rules which generate a (partially) structured compuond which accounts for the fragment. Then account for the unstructured part. Necessary list Forbidden list | | | | v v Chemical -------------------------- Formula ---------->| Structure | | Generator | -------------------------- | | v -------------------------- | Spectrogram | | Analyzer | -------------------------- | | Synthetic spectrogram v Experimental -------------------------- Spectrogram ----->| Matcher/Evaluator | -------------------------- | v Acceptable chemical structures %---------------------------------------------------------------------------- MYCIN (Shortliffe, Buchanan 1975; Davis et al 1977) - One of the first, and one of the most successful, expert systems. - Diagnosis of bacteriological infectious diseases - Can express its rules and conclusions in English (important in medical domain for human trust) - Computes certainties for conclusions - About 300 rules - Can diagnose about 100 diseases and prescribe treatment Basic problem solving paradigm: Abduction using backward chaining - Abduction used to form plausible explanations for observed symptoms by backward chaining through medical rules - Basic problem: combining evidence - Want causal connections. If there is a rule: (-> (in ?patient ward-5) (have ?patient cancer) we don't want to infer that (has Eliza cancer) is caused by (in Eliza ward-5). - Uses statistical abduction rules representing P(disease|symptom) [read: P disease given symptom, the probability of "disease" being true assuming (hypothetically) that you know "symptom" is true.] Example: (cause (condition-of (liver-of ?patient) pickeled) (color-of (skin-of ?patient) yellow) 0.5 <-- P(disease|symptom): Not usually known 0.01) <-- P(symptom|disease) - Big problem: Where do the numbers come from? Statistical/probabilistic knowledge: What doctors know (sort of): P(puffy eyes | pickled liver) = 0.01 (approx) P(bloody urine | pickled liver) = 0.60 (approx) P(jaundice | pickled liver) = 0.90 (approx) and prior probabilities: P(some disease) P(some symptom) Bayes theorem: P(d) P(s|d) P(d|s) = ------------- P(s) Diagnosis tree: AND/OR graph in which AND nodes represent right-hand-sides which depend on conjunctive left-hand-sides and OR nodes represent alternative rules which lead to the same conclusion. Each production rule has an attenuation factor between 0 and 1. AND nodes: multiply attenuation by smallest certainty daughter. OR nodes: Each production contributes against remaining uncertainty. This is an ad hoc method: not quite Bayesian probabilities. In later expert systems (e.g., PROSPECTOR), the Bayesian approach (and other formal approaches) was used explicitly. Problems: - Computationally: Say 500 diseases, 3000 symptoms. Need roughly 1,500,000 probability numbers, given one symptom is present at a time. For conditional probability of a disease given two symptoms, need about 45,000,000 numbers. Assuming many diseases are unrelated to many symptoms (statistical independence), the numbers can be kept tractable (but barely). - If multiple diseases are possible, the combinatorial explosion gets even worse. - Need HEURISTICS to keep these problems under control (see chapter 8). - MYCIN achieves expert performance, but extensive and unprincipled tuning of probabilities is required. Other successful medical expert systems include INTERNIST, available commercially as QMR (Quick Medical Reference) for about $1000. %---------------------------------------------------------------------------- MYCIN's Task: Diagnosis and Therapy Input: Features about infectious organisms in a patient's culture. Output: (i) Diagnostic hypotheses about the identity of organisms; (ii) Advice for therapy Domain: Medicine (infectious diseases) Size: Number of possible organisms large, Numbre of possible features VERY large, Intercations: very limited interactions between hypotheses Method: Knowledge Used: (i) Knowledge of diagnostic hypotheses in the domain; (ii) Judgemental (heuristic) associations between the input features and intermediate features, and between intermediate features and diagnostic hypotheses about the identity of organisms; (iii) Certainty factors (certainty that specific feature combinations imply specific hypotheses) (iv) Therapy procedures (v) Associations between diagnostic hypotheses and applicable therapy procedures Sub-Tasks: Diagnosis and Therapy Selection Control of Processing: First diagnose and then select a therapy %---------------------------------------------------------------------------- MYCIN Sub-Task: Diagnosis Input: Features about infectious organisms in a patient's culture. Output: Hypotheses about the identity of organisms. Method: Generate and Test Knowledge Used: (i) Knowledge of diagnostic hypotheses in the domain; (ii) Judgemental (heuristic) associations between the input features and intermediate features, and between intermediate features and diagnostic hypotheses about the identity of organisms; (iii) Certainty factors (certainty that specific feature combinations imply specific hypotheses) Sub-Tasks: Hypothesis Generation and Testing of diagnostic hypotheses Control of Processing: First Generate hypotheses and then Test them. Accept only those hypotheses whose final certainty values are above some threshold theta. %---------------------------------------------------------------------------- MYCIN Sub-SubTask: Generation of Diagnostic Hypothses Input: Features about infectious organisms in a patient's culture. Output: A hypothesis about the identity of one of the organisms. Method: Search Knowledge Used: Knowledge of diagnostic hypotheses in the domain; Sub-Tasks: None. Control of Processing: Pick a hypothesis from the pre-enumerated set of diagnostic hypotheses. %---------------------------------------------------------------------------- MYCIN Sub-SubTask: Testing of Diagnostic Hypotheses Input: A hypothesis about the identity of one of the organisms in the patient's culture. Output: An evaluation of the hypothesis in terms of its certainty. Method: Heuristic Association Knowledge Used: (i) Judgemental (heuristic) associations between the input features and intermediate features, and between intermediate features and diagnostic hypotheses about the identity of organisms; (ii) Certainty factors (certainty that specific feature combinations imply specific hypotheses) Sub-Tasks: None Control of Processing: Backward chaiing %---------------------------------------------------------------------------- MYCIN Sub-Task: Therapy Advice Input: A set of hypotheses about the identities of the organisms in the patient's culture. Output: Advice for treating the patient. Method: Table Look-Up Knowledge Used: (i) Therapy procedures (ii) Associations between diagnostic hypotheses and applicable therapy procedures Control of Processing: Select a set of procedure that covers the hypothesis set. %------------------------------------------------------------------------ ABDUCTION: The diagnosis task is an instance of the abduction task. Abductive inference also occurs in perception, language processing, etc. Input: A set of data, e.g., features of the oragnisms in a patient'c culture Output: A set of hypotheses that EXPLAIN the data, e.g., the identity of the organisms. Other fundamental types of inference: Deduction, Induction, and Prediction. %---------------------------------------------------------------------------- R1/XCON: An expert system for computer design (McDermott 1980) One of the first, and commercially one of the most successful, expert systems (used by DEC). R1's Task: Configuring the layout of a computer system according to given specifications. Input: The specification of the components of a computer system, e.g., 1 floating point accelerator, 1 unibus adaptor, 1 unibus expansion box, 6 memory, 1 memory controller, 1 cpu expansion box, ... etc., etc. Output: A configuration for the computer system, i.e., layout for the components and the connections between them. Domain: Computer Systems (DEC VAX systems) Size: Number of possible components large, Number of possible configurations VERY large, Interactions: very limited interactions between the components Example rule: if the context is layout and assigning a power supply and an sbi module of any type has been put in a cabinet and the position it occupies in the cabinet is known and there is space available in the cabinet for a power supply and there is an avilable power supply then put the power supply in the cabinet in the available space Method: Heuristic Association Knowledge Used: (i) Knowledge of components in the domain; (ii) Knowledge of possible relations between components; (iii) Heuristic associations between components and their connections. Sub-Tasks: None, really. Control of Processing: Forward chaining. Algorithm: 1. Check the specifications, looking for mismatched items and missing components. 2. Lay out the processor in cabinets. 3. Put boxes in the input/output cabinets, and put components in those boxes. 4. Put panels in the input/output cabinets. 5. Lay out the floor plan. 6. Do the cabling. Each step is implemented using a simple forward-chaining rule based system. Currently, XCON has about 2500 rules and is routinely used by DEC for handling computer system orders involving 100-200 components. %------------------------------------------------------------------------ DESIGN: The configuration task is an instance of the more general design task. Input: A specification of the constraints on an artifact; the constraints can pertain to the functions of the artifact, its structure (as in R1), cost, construction, aesthetics, etc. Output: A specification of the structure for the artifact; its components, relations among the components, layout, etc. %---------------------------------------------------------------------------- "Expert systems" for Vision and Language ACRONYM (Brooks) Model-based computer vision program that uses prestored models of possible objects to identify objects in a visual scene. Uses generate-and-test paradigm: generates predictions about the scene, and tries to test the predictions by looking for those components in the scene. CA/ELI (Riesbeck; Birnbaum and Selfridge) Can think of "requests" (test-action pairs for natural language understanding) as "production rules". But not really pure production system, since requests can do more than add and delete items from short term memory (the "C-list" in this case) -- they can also add requests to the "R-list", trigger old (pending) requests, etc. %---------------------------------------------------------------------------- Most simple rule based systems are basically DEDUCTION systems. Their IF-THEN rules encode certain or logically correct inferences. However, some rule based systems can deal with uncertainty. Approaches to dealing with uncertainty: 1. Bayesian nets (probability) 2. Dempster-Shafer theory of evidence (weaker than probability theory) 3. Fuzzy logic, Zadeh's fuzzy set theory (possibility theory) 4. Non-monotonic reasoning 5. Heuristic methods (e.g., SOLOMON, Cohen 1985) 6. Ad hoc methods (e.g., MYCIN, Buchanan and Shortliffe, 1984) %---------------------------------------------------------------------------- Other expert system architectures (in addition to production systems): 1. Associative or semantic networks (e.g., CASNET, Weiss et al 1978) 2. Frame systems (e.g., PIP, Szolovits and Parker 1978) 3. Decision trees (e.g., Patterson 1987) 4. Blackboards (e.g., HEARSAY, Reddy et al 1976; Nii 1986) 5. Analogical and case-based reasoning (e.g., JUDGE, Bain 1986) 6. Neural networks (e.g., Gallant 1988) %---------------------------------------------------------------------------- Case-based expert systems E.g., JUDGE (Bain 1986): Relative (and often subjective) assessment of input situations in the domain of sentencing criminal cases. E.g., CLAVIER (Barletta and Mark): Optimal use of an autoclave. In commercial use at Lockheed. Differences between "rule-based" and "case-based" expert systems (Bain 1986): 1. Rule-based systems rely on knowledge extracted from experts and encoded in knowledge bases, whereas case-based systems rely on knowledge they extract for themselves through experience. Therefore, case-based systems are inherently: a. Empirical. b. Learning systems. 2. Rule-based expert systems tend to be classification systems (some exceptions are ABEL (diagnostic reasoning with causal models, Patil et al 1981), NEOMYCIN (classification + tutoring, Clancey and Letsinger 1981), XPLAIN (classification + explanation, Swartout 1983)). This works for problems such as medical diagnosis ("classify input symptoms into some known disease category"), but not for other kinds of tasks which are not classification tasks (e.g., JUDGE's task is not really even diagnosis). These tasks may require classification but are more than just that. The reason is that all the features and interactions can't be anticipated in advance. 3. Rule-based systems work well in domains where knowledge is statistical or classificatory, but not in domains where knowledge is experiential, episodic and empirical. Case-based reasoning in JUDGE requires INTERPRETATION ("understanding", causal construction, analytical characterization), CLASSIFICATION (retrieval of known cases), and ADAPTATION (application and modification of prescriptions from known cases). %---------------------------------------------------------------------------- CLAVIER: An example of a fully automated case-based expert system in commercial use. Input: A list of composite (graphite and fiberglass) parts to be cured in an autoclave, with priorities. Task: Determine a loading of parts that optimizes use of the autoclave, i.e., cures as many parts as possible, especially high priority parts. Essentially a "bin packing" problem with constraints. Problem: Spatial layout is critical. Airflow aournd odd-shaped parts is complex and drastically affects the curing process. Output: An autoclave load. Each load has a number of different parts, arranged spatially for efficient air flow and even curing. Each load consists of several tables, each table containing several parts. Algorithm: Use problem description to retrieve a case. The initially retrieved case may not handle all the parts in the current problem, so it is adapted to include the unmatched parts by retrieving other cases with similar layouts. [slides] Parts list (problem description) -> Best match case retrieval from case memory -> Initially retrieved case (with unmatched parts) -> Context determination < -> Retrieval from case memory < -> Context matching < Adaptation -> Part selection < -> Suggested substitution < -> Adapted case (solution to problem) %---------------------------------------------------------------------------- Issues in case-based reasoning: Indexing and retrieval of cases Adaptation Evaluation/Criticism of solution Learning (Storing new solution in a form that can be retrieved later) %---------------------------------------------------------------------------- Copyright (c) Ashwin Ram, 1990-93 Assistant Professor, College of Computing Georgia Institute of Technology, Atlanta, Georgia 30332-0280 E-mail: