92-DH-DISS An Extensible, Task-Specific Shell For Routine Design Problem Solving David Joseph Herman Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University $8.50 92-HN-DISS Imagery, Diagrams and Reasoning N. Hari Narayanan Presented in Partial Fulfillment of the Requirements for the Degree Doctor of in the Graduate School of The Ohio State y complicated cognitive tasks involving devices; they are able to find faults, if any, in a device given a description of its behavior, or predict what a device to other humans. Although it is conceivable, if necessary, to accomplish these tasks by considPhilosophy in the Graduate School of The Ohio State University $8.00 92-PK-DISS Causality and Knowledge-Based Diagnosis of Nuclear Power Plants Probal K. Acharyya Presented in Partial Fulfillment iate to the task at hand. Similar comments are true of humans who understand computer programs. In this work, I determine the requirements for a representation of program understanding to support reasoning of this nature. This dissertation describes eering all possible states of the device, one seldom does this when performing such a task. Rather, one deliberately considers an appropriate subset of the states of the device, or an abstraction that aggregates various subsets of the states, as is appropr also to axiomatic proofs of program correctness. This approach contributes to machine understanding of programs by resolving the tension between plan-based and theorem-based approaches to automatic debugging. A strategy reminiscent of plan-matching approaches is used to reduce the part of a proof that must be constructed by an automatic theorem prover. This approach also contributes to machine understanding of devices by connecting the Functional Representation to a domain which has a formal definition xtensions to the Functional Representation language (first described by Sembugamoorthy and Chandrasekaran in [27]), which satisfies many of these requirements, to include connecting the representation of program understanding not only to program code, buttunderstandable report of the error. Dudu is able to recognize the correctness of many programs that do not correspond to the representation in an obvious way by completing a correctness proof of the program, with guidance from the functional representatiofor its semantics. The properties of the representation are demonstrated with a program that runs in Interlisp-D on a Xerox 1108 that uses a functional representation of a computer program to verify program code, and, if the code is incorrect, to give an of the Requirements for the Degree Master of Science in the Graduate School of The Ohio State University $8.00 92-RF-DISS Layered Abduction For Speech Recognition From Articulation Richard Keith Fox Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University $8.00 91-MD-DISS Causal Processes in the Problemsal Processes in the Problem Space Computational Model: Integrating Multiple Representations of Causal Processes in Abductive Problem Solving Matthew DeJongh Presented in Partial lem Solving Matthew DeJongh Presented in Partial ve Problem Solving Matthew DeJongh Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University ABSTRACT: This work investigates the use of so-called shallow and deep representations of causal processes in physical systems. In particular, I describe a framework that I have developed for integrating simulation with abduction, and demonstrate a problem solving system for pretransfusion blood typing that I have used it to build. Within my framework, the Hypothesis Model represents associations between hypotheses regarding causal processes and the data that the hypotheses can be used to explain, and the Physical Model represents knowledge regarding the structure, behavior and function of a physical system and its components. The Hypothesis Model is used for confirming and disconfirming hypotheses, and the Physical Model is used o simulate causal processes for formulating and evaluating hypotheses. The representation of the Physical Model is based upon the Functional Representation of Sembugamoorthy and Chandrasekaran, which is used to represent knowledge regarding the functions that components of a physical system achieve and the behaviors by which the components of laboratory tests can be used to formulate hypotheses by deriving the sequence of events that caused the observed violations of assumptions underlying the standard method of interpreting test results. My framework is implemented within the Problem Space Computational Model, in the SOAR architecture. The framework uses automatic subgoaling in SOAR to integrated the use of the Hypothesis Model and Physical Model to achieve abductive subgoals, and uses chunking in SOAR to create representations of associations between hypotheses and data from the results of simulating causal processes. $8.00 91-MW-DISS An Explanation-Based Approach to Assigning Credit Michael Alan Weintraub Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University $8.00 91-OF-DISS Cognitively Plausible Heuristics To Tackle The Computational Complexity of Abductive Reasoning Olivier Fischer Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University $6.00 91-TJ-DISS Generic Taskke Graduate School of The Ohio State University $6.00 91-TJ-DISS Generic Tasknted in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University ABSTRACT: A Generic Task identifies a problem of general utility and provides a problem-solving theory and architecture to support the development of systems that solve that problem. The architecture consists of a domain-independent problem-solving method for solving the problem and a language for representing the knowledge needed by the method. These architectures speed design, facilitate the acquisition and specification of knowledge, and enhance the explanatory capabilities of knowledge systems. A major limitation with this approach is that the resulting knowledge systems tend to be too inflexible-they only behave appropriately on a narrow range of problem instances. This problem is exacerbated if one wants to build systems that use problem-solving methods from multiple tools. Often, the tools are not designed to work together or they over-constrain the interaction between the problem-solving methods. In contrast to work on generic tasks, work on general architectures has let to theories about how to build flexible systems. The problem-space paradigm, embodied in the soar architecture, has proven to be particularly useful for generating and explaining flexible behavior. This approach, however, does not supply theories about how particular kinds of problems are solved. The work presented in this dissertation shows how these tow approaches can be integrated such that problem-solving theories and architectures can be designed so that they can be used to produce flexible systems without losing the advantages of existing generic-task architectures. The contributions of the research reported here are as follows. First I develop the concept of Generic Task Problem Spaces (GTPS), demonstrate that problem spaces can be used as an implementation-independent language for describing generic tasks, and provide a set of guidelines to help ensure flexibility. Second, I show how GTPSs can be implemented in Soar to produce system-building tools with the same advantages as tradition generic-task tools. Third, I have used the GTPS-Soar approach to implement generic-task tools for abduction, classification, and hypothesis matching. s in the Problem-Space Paradigm: Building Flexible Knowledge Systems While Using Task-Level Constraints Todd Richard Johnson Preseints Todd Richard Johnson Preseilding Flexible Knowledge Systems While Using Task-Level Constraints Todd Richard Johnson Prese Dean T. Allemang Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of the Ohio State University ABSTRACT: Humans are able to perform mannction of a physical system and its components. The Hyp Finally, I describe a knowledge system that makes use of these tools in a flexible way to solve a family of complex abduction problems. $8.00 90-DA-DISS Understanding Programs As Devicesssd[, 3or of Philosophy in the Graduate School of The Ohio State University ABSTRACT: In the case-based approach to design, a novel problem is solved by adapting a design known to solve a related problem. Adapting a known design to solve a related problem by the commonly used methods of heuristic association and search, however,m can be computationally expensive if the adaptation search space is not small. the adaptation space, then, needs to be decomposed into smaller and simpler spaces that can be searched more efficiently and effectively. The knowledge for decomposing the adaptation search space can be rep[resented as a behavior-structure model that specifies how the structure of the known design results in its output behaviors. This research investigates the use of such behavior-structure models for adapting the designs of physical devices. Comprehension of how the output behaviors of a design arise from its structure is represented as a behavioral component-substance model for the design. The model explicitly specifies (i) the expected output behaviors of the design including its functions, (ii) the elementary structural and behavioral interactions between components and substances constituting the structure of the design, and (iii) the internal causal behaviors of the design that compose the elementary interactions into its output behaviors. The causal behaviors of the design, in this model, are indexed by the expected output behaviors for which they are responsible. The model aids case-based design in several ways. First, it identifies conceptual primitives for specifying the functions of designs, which are used to index the known designs stored in a case-based memory. Second, it identifies elementary types of behavior transformations and elementary types of structure modifications. Third, it provides knowledge for decomposition of the adaptation search space into smaller spaces so that search for the needed structure modifications is localized. Fourth, it leads to a novel method for simulating the behavioral effects of structure modifications. The output and causal behaviors of the modified design, in this method, are derived by revising the output and causal behaviors of the known design. This integrative approach unifies case-based methods, associative methods, heuristic search methods, decomposition methods, and model-based methods into one architecture for adaptive design problem solving. Core portions of this approach have been implemented in an experimental design system called KRITIK. n. $8.00 89-AG-DISS Integration Of Case-Based Reasoning And Model-Based ReasonAdaptive Design Problem Solving Ashok Kumar Goel Presented in Partial Fulfillment of the Requirements for the Degree Do of The Ohio State University ABSTRACT: This dissertation investigates how diagnostic conclusions made by a diagnostic problem-solving system can be explained by showing how the hypothesized malfunction causally gives rise to the observations. In particular, it shows how this explanation can be constructed from a deep model of the system being diagnosed, I.e., a model that explicitly represents the underlying structure of the system and the functions and behaviors of its components. In the past, researchers have investigated how diagnosis itself can be performed from deep models, but using these representation for individual diagnostic problems can be computationally expensive. Compiled knowledge helps in efficiency in problem solving. However, the compiled knowledge may be incomplete and there may be a doubt about the correctness of the diagnostic conclusion. If a causal story can be put together computationally effectively, using the diagnosed answer as a focus, one gets the computational benefits of compiled knowledge to obtain the diagnostic answer as well as the use of the deep model for causal validation and elaboration of the answer. The goal of this research is to determine how, and to what degree, causal explanations of malfunctions can be derived from an understanding of how a device is expected to work. Efforts simultaneously concentrate on the following: (1) what it means to provide a causal story of device function and malfunction, and (2) in order to produce these stories, what knowledge is needed to model devices and how should it be organized and indexed in a way that contributes toward a general solution to representation of device. The representation developed in this work build s upon an earlier model introduced by Sembugamoorthy and Chandrasekaran called the Functional Representation. Representational enhancements include the specification of a taxonomy of function types (achieving a state, maintaining a state, preventing an undesirable state, and controlling variations in state), and explicit representation of state and behavioral abstractions (such as oscillation and feedback). The explanation generation process then uses the organization and primitives of the representation to simulate malfunctioning devices and produce causaing for Adaptive Design Problem Solving Ashok Kumar Goel Presented in Partial Fulfillment of the Requirements for the Degree Doctthis mapping of architecture to task it is possible to derive answers to the diagnostic questions. I illustrate these ideas byial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University ABSTRACT: We would like problem-solving systems to explain themselves for a variety of reasons, including convincing users that problem solutions are correct and showing that solutions follow from appropriate methods. An important aspect of explanation is showing that the actions and conclusion of a problem-solving system are related to the logical structure of the task that the system performs. That is, the system and its users must share e an understanding of what the task is. Explanations can then relate the goal-subgoal structure of the problem solve to this shared understanding. The shared understanding, or shared model, of the task represents the logical structure of the task, i.e., the features that characterize correct answers and correct problem solving. One thing that a shared model for any task will show is ways in which users might be puzzled, that is, the issues they will be concerned about and about which they may ask questions. In this dissertation I develop this idea in the concrete domain of diagnosis. In common with many others, I consider diagnosis to be an abduction problem-determine the disease, or set of diseases, that best explain a given set of symptoms. The logical structure of this can be used to derive the question that a diagnostic system can be asked; the questions are those that arise solely because the system does diagnosis. I give an architecture based on generic tasks for a system that can do diagnosis. Parts of this system serve parts of the diagnostic task; from this mapping of architecture to task it is possible to derive answers to the diagnostic questions. I illustrate these ideas by describing the development of explanation for RED, which is not actually a diagnostic system, but what is does is enough like diagnosis to be informative. There are many aspects to the problem of explanation, including the problem of how to present explanations to users. But central to any explanation is its content. This dissertation is about the content of explanation and how the ocnten can be derived form the structure and memory of problem solvers by reference to the logical structure of their problem-solvi $15.00 89-AK-DISS Machine Understanding of Devices Causal Explanation of Diagnostic Conclusions AAarie Keuneke Presented in Partial fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate Schoning William F. Punch III Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University ABSTRACT: Design of Knowledge Based Systems (KBS) that address complex problems often require multiple problem solving methods t achieve/solve all of that problems subgoals/subproblems. There is therefore a strong need to address the problems of integrating multiple problem solving methods that operate in the service of solving complex problems. To the extent that research in KBS has dealt with these problems at all, such integration is usually hard wired, that is method selection is fixed at the time the KBS is designed. Such design results in problem solvers that are brittle, that is, when a hardwired method fails, the system cannot evaluate the appropriateness of other methods for continuing problem solving. Furthermore, these problem solvers do not scale up and are difficult to modify. Some general purpose architectures such as BB1 and SOAR, however, do allow method selection to occur dynamically, that is which method is selected is based on the runtime state of the problem and its goals. What is still needed are some guidelines on how to more directly map the goals and subgoals of a problem to the various methods used to achieve them. This dissertation makes three contributions. The first is an approach h called as specific integration which provides guidelines on how to determine the appropriateness of methods for solving complex problems based on the goal structure of the problem and the capabilities of each method for achieving those goals. An architecture (TIPS) is provide for implementing systems using the task specific approach. The second contribution is the design of a medical diagnosis system using the TIPS architecture. This system incorporates a number of methods including: causal reasoning, compiled reasoning, data gathering, data validation and others. The third contribution is how a causal reasoning method can contribute to the general problem of diagnosis. As used in the medical diagnosis system above, primitives about causal interactions are provided to describe some of the causal results of a malfunction. This knowledge can be used to investigate causal interanne Marie Keuneke Presented in Partial fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School(4e~s[0! ! }e}sHH! selxplanations to users8.50 86-DS-DISS A Knowledge Based Framework for Procedure Synthesis and its Application to the Emergency Response in a Nuclear Power Plant Deva-Datta Sharma Presented in Partial Fulfillment of the Requirements for the Degree Doctor or Philosophy in the Gl chains, consisting of malfunctioning components and observations, leading from diagnostic hypotheses to observed symptoms. $6.00 89-MT-DISS Explaining Knowledge Systems: Justifying Diagnostic Conclusions Michael Clay Tanner Presented in Pa $6.00 89-MT-DISS Explaining Knowledge Systems: Justifying Diagnostic Conclusions Michael Clay Tanner Presented in Parttt structure and memory of problem solvers by reference to the logical structure of their problem-solving task. The main ideasng task. The main ideas should transfer to tasks other than diagnosis. $8.00 89-WP-DISS A Diagnosis System Using a Task Integrated Problem Solver Architecture (TIPS), Including Causal Reasoo2mechanism that is especially suited for ctions between active malfunction hypotheses, potentially resulting new diagnostic conclusion based on cause. $8.00 87-JS-DISS MDX2 An Integrated Medical Diagnostic System Jon Sticklen Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University ABSTRACT: How shall we analyze the logic of science? The Cartesian quest for absolute certainty fails. When we turn to humean Empiricism we find the view suffering from three significant difficulties. One is a difficulty with foundations for induction, another concerns the status of theoretical entities, and the third concerns the analysis of causal relations. In Gilbert Harmans conception of induction as inference to the best explanation we find the basis of an alternative paradigm; and in the present work such an alternative paradigm is articulated. The success of explationism in treating the three difficulties argues for that approach to analyzing the logic of science. In particular, by treating certain probabilities as propensities, the defects of Reichenbachs vindication of induction can be repaired, and the traditional problem of induction made less intransigent. \ According to the new view: $8.00 87-JS-DISS MDX2 An Integrated Medical Diagnostic System Jon Sticklen $$e three difficulties argues for that approach to analyzing the logic of science. In particular, by treating certainnraduate School of the Ohio State University $15.00 86-TB-DISS Consolidation: A Method for Reasoning About the Behavior of Devices Thomas C. Bylander Presented in partial fulfillment of the requirements for the degree Doctor of Philosophy in the graduate school of The Ohio State University $8.00 85-JS-DISS RED: A Classificatory and Abductive Expert System Jack Willard Smith Jr. Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University $8.00 84-DB-DISS Expert Systems For Design Pophy in the Graduate School of The Ohio State University $8.00 84-DB-DISS Expert Systems For Design Problem-Solving Using Design Refinement With Plan Selection And Redesigning David Christopher Brown Presented in partial fulfillment of the requirements for the degree Doctor of Philosophy in the graduate school of The Ohio State University $8.00 82-JJ-DISS Explanation and Induction John R. Josephson Presented in Partial Fulfillment of theeeeeeee $8.00 82-JJ-DISS Explanation and Induction John R. Josephson Presented in Partial Fulfillment of the without absolute certainty, understanding an rationality are nevertheless possible; science is built upon the physical senses and experiments; and things-as-they-are can be known, even seen. $8.50 81-FG-DISS On General And Expert Knowledge-Based Methods In Problem-Solving Fernando J. Gomez Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of the Ohio State University $8.00 e Ohio State University $8.00 80-SM-DISS Design of a Distributed Medical Diagnosis and Data Base System Sanjay Mittal $8.00 $8.00 89-WP-DISS Ama@ABCDEFGVIJKLMNOPQW\S]^_`aXYZ[bcdl E9 9  ?. :  1 _ s / !d a  M l ? i  -* z C 2  e/  @ >9& F? ? @4 ;4 ) 2 _4 ty4 "E? b60 N  @ j_h? .  {> D 2 f4 4 A ??>?HHxJ50[= eOp>?HHxV+0[= eN >?x "\HHx0[= >?HHx 0[= eR>?HHx0o[= eR0>?HHx"0[= eQ>?HHx10[= eP>?HHxpA0[= eP >?HHxL0[= eOp>?HHxVK0[= eNJ. Josephson ABSTRACT: An experiment was