Representing diagnosis knowledge

This paper considers therepresentation problem: namely how to go from an abstract problem to a formal representation of the problem. We consider this for two conceptions of logic-based diagnosis, namely abductive and consistency-based diagnosis. We show how to represent diagnostic problems that can be conceptualised causally in each of the frameworks, and show that both representations of the same problems give the same answers. This is a local transformation that allows for an expressive (albeit propositional) language for giving the constraints on what symptoms and causes can coexist, including non-strict causation. This non-strict causation can be represented in each frameworkwithout adding special reasoning constructs to either framework. This is presented as a starting point for a study of the representation problem in diagnosis, rather than as an end in itself.     

基于一致性的中心诊断及中心溯因诊断

本文对溯因诊断的过程和中心溯因诊断的过程进行了刻画。将求中心溯因诊断的过程清晰地分为与领域有关的冲突识别及与领域无关的候选产生两大步骤。不仅指出了基于一致性的中心诊断与中心溯因诊断之间的关系，而且论证了中心溯因诊断与本原蕴含／蕴含式的直接关系。显示出基于一致性的中心诊断空间和中心溯因诊断空间不仅可同时计算，而且可用ＡＴＭＳ这类算法来计算，从而将我们的理论结果与实现联系起来。     

Process algebras for systems diagnosis

In this paper we propose a new characterization of model-based diagnosis based on process algebras, a framework which is widely used in several areas of computer science. We show that process algebras provide a powerful modelling language which allows us to capture, in an uniform way, different types of models of physical systems, including models of time-varying and dynamic behavior. Then we provide a characterization of diagnosis which is equivalent to the “classical” abductive one. This suggests new interesting opportunities for research on relations between model-based reasoning and process algebras.     

Compiling a default reasoning system into Prolog

Artificial intelligence researchers have been designing representation systems for default and abductive reasoning. Logic Programming researchers have been working on techniques to improve the efficiency of Horn clause deduction systems This paper describes how one such default and abductive reasoning system (namelyTheorist) can be translated into Horn clauses (with negation as failure), so that we can use the clarity of abductive reasoning systems and the efficiency of Horn clause deduction systems. We thus show how advances in expressive power that artificial intelligence workers are working on can directly utilise advances in efficiency that logic programming researchers are working on. Actual code from a running system is given.     

A spectrum of logical definitions of model-based diagnosis1

In this paper, we analyze the logical definitions of model-based diagnosis recently presented in the literature, and we propose a unified framework (based on the integration of abductive and consistency-based reasoning) in which most of such definitions can be captured. This allows us to single out the existence of a spectrum of alternatives in the logical definition of diagnosis. A lot of attention in the paper is devoted to analyzing the differences among the definitions in the spectrum. In particular, we show that the definitions can be compared on the basis of their restrictive-ness and we relate such a restrictiveness with the completeness of the model of the system to be diagnosed. Dans cet article, les auteurs analysent les définitions logiques de diagnostics basés sur un modèle dont il a été question récemment dans certains ouvrages. Ils proposent un cadre unifié (basé sur l'intégration du raisonnement abductif et du raisonnement basé sur la consistance) à l'interieur duquel la plupart de ces définitions peuvent ětre regroupées. Cette particularité permet de mettre en lumière l'existence d'un spectre d'alternatives dans la définition logique du diagnostic. Cet article accorde une attention toute particulière à l'analyse des différences entre les définitions du spectre. En outre, les auteurs démontrent que les définitions peuvent ětre compareées en fonction de leur caractère restrictif, qui est ensuite mis en relation avec la complétude du modèle du système faisant l'objet d'un diagnostic.     

基于扩展的因果理论的鉴别诊断

许多学者将因果关系这一概念应用于基于模型的诊断领域.然而,他们的研究只局限于简单因果理论.该文提出的扩展的因果理论则包容了更多的信息,指出了扩展的因果理论的诊断空间小于等于相应简单因果理论的诊断空间.另外,还将扩展的因果理论用于测试领域,证明了对于封闭的扩展的因果理论,溯因鉴别诊断等于基于一致性鉴别诊断.这一结果可应用于测试选择的策略.     

Programming Rational Agents in a Modal Action Logic

In this paper we describe a language for reasoning about actions that can be used for modelling and for programming rational agents. We propose a modal approach for reasoning about dynamic domains in a logic programming setting. Agent behavior is specified by means of complex actions which are defined using modal inclusion axioms. The language is able to handle knowledge producing actions as well as actions which remove information. The problem of reasoning about complex actions with incomplete knowledge is tackled and the temporal projection and planning problems is addressed; more specifically, a goal directed proof procedure is defined, which allows agents to reason about complex actions and to generate conditional plans. We give a non-monotonic solution for the frame problem by making use of persistency assumptions in the context of an abductive characterization. The language has been used for implementing an adaptive web-based system.     

Three-valued completion for abductive logic programs

In this paper, we propose a three-valued completion semantics for abductive logic programs, which solves some problems associated with the Console et al. two-valued completion semantics. The semantics is a generalization of Kunen's completion semantics for general logic programs, which is known to correspond very well to a class of effective proof procedures for general logic programs. Secondly, we propose a proof procedure for abductive logic programs, which is a generalization of a proof procedure for general logic programs based on constructive negation. This proof procedure is sound and complete with respect to the proposed semantics. By generalizing a number of results on general logic programs to the class of abductive logic programs, we present further evidence for the idea that limited forms of abduction can be added quite naturally to general logic programs.     

N-Prolog and equivalence of logic programs

The aim of this work is to develop a declarative semantics for N-Prolog with negation as failure. N-Prolog is an extension of Prolog proposed by Gabbay and Reyle (1984, 1985), which allows for occurrences of nested implications in both goals and clauses. Our starting point is an operational semantics of the language defined by means of top-down derivation trees. Negation as finite failure can be naturally introduced in this context. A goal-G may be inferred from a database if every top-down derivation of G from the database finitely fails, i.e., contains a failure node at finite height.Our purpose is to give a logical interpretation of the underlying operational semantics. In the present work (Part 1) we take into consideration only the basic problems of determining such an interpretation, so that our analysis will concentrate on the propositional case. Nevertheless we give an intuitive account of how to extend our results to a first order language. A full treatment of N-Prolog with quantifiers will be deferred to the second part of this work.Our main contribution to the logical understanding of N-Prolog is the development of a notion of modal completion for programs, or databases. N-Prolog deductions turn out to be sound and complete with respect to such completions. More exactly, we introduce a natural modal three-valued logic PK and we prove that a goal is derivable from a propositional program if and only if it is implied by the completion of the program in the logic PK. This result holds for arbitrary programs. We assume no syntactic restriction, such as stratification (Apt et al. 1988; Bonner and McCarty 1990). In particular, we allow for arbitrary recursion through negation.Our semantical analysis heavily relies on a notion of intensional equivalence for programs and goals. This notion is naturally induced by the operational semantics, and is preserved under substitution of equivalent subexpressions. Basing on this substitution property we develop a theory of normal forms of programs and goals. Every program can be effectively transformed into an equivalent program in normal form. From the simple and uniform structure of programs in normal form one may directly define the completion.     

Classification and Concept Consistency

Abstract

This article investigates the extent to which undergraduates consistently use a single mechanism as a basis for classifying mathematical objects. We argue that the concept image/concept definition distinction focuses on whether students use an accepted definition but does not necessarily capture the more basic notion that there should be a fixed basis for classification. We examine students’ classifications of real sequences before and after exposure to definitions of increasing and decreasing; we develop an abductive plausible explanations method to estimate the consistency within the participants’ responses and suggest that this provides evidence that many students may lack what we call concept consistency.     

Tarsier and ICMS: two approaches to framework development

Modelling frameworks provide models with support components that handle tasks such as visualisation, data management and model integration. Within these broad requirements different approaches to framework development are possible. Tarsier is a modelling framework that supports the development of models in a high-level language, such as C++. This approach allows Tarsier model developers to craft object oriented solutions to large modelling problems. ICMS is a software system that supports the development of models in a custom modelling language that allows modellers with little programming experience to develop, integrate and visualise catchment models. Both frameworks provide sophisticated tools for model linking, data management, and data analysis and visualisation. By focusing on different user groups, Tarsier and ICMS have evolved into quite different environments, yet both satisfy the definition of a modelling framework. This paper concentrates on the components within each framework and the strengths and weaknesses of the different approaches.     

基于结构的弱诊断模型

本文首先给出一种弱诊断模型，利用系统的结构信息，快速得到系统的弱诊断，在不丢失解的情况下缩小诊断空间，以提高诊断效率。对仅知道系统的整体功能和物理结构系统，无法进行一致性诊断或更强的诊断，我们仍然可以对其进行弱诊断。其次，我们给出了弱诊断、一致诊断、溯因诊断间的关系。最后，根据诊断和真正故障元件集合间的关系，定义了诊断的可采纳性，并证明了弱诊断、一致诊断是可采纳的。     

Applying algorithm selection to abductive diagnostic reasoning

The complexity of technical systems requires increasingly advanced fault diagnosis methods to ensure safety and reliability during operation. Particularly in domains where maintenance constitutes an extensive portion of the entire operation cost, efficient and effective failure identification holds the potential to provide large economic value. Abduction offers an intuitive concept for diagnostic reasoning relying on the notion of logical entailment. Nevertheless, abductive reasoning is an intractable problem and computing solutions for instances of reasonable size and complexity persists to pose a challenge. In this paper, we investigate algorithm selection as a mechanism to predict the “best” performing technique for a specific abduction scenario within the framework of model-based diagnosis. Based on a set of structural attributes extracted from the system models, our meta-approach trains a machine learning classifier that forecasts the most runtime efficient abduction technique given a new diagnosis problem. To assess the predictor’s selection capabilities and the suitability of the meta-approach in general, we conducted an empirical analysis featuring seven abductive reasoning approaches. The results obtained indicate that applying algorithm selection is competitive in comparison to always choosing a single abductive reasoning method.     

Consistency-based diagnosis of configuration knowledge bases

Configuration problems are a thriving application area for declarative knowledge representation that currently experiences a constant increase in size and complexity of knowledge bases. Automated support of the debugging process of such knowledge bases is a necessary prerequisite for effective development of configurators. We show that this task can be achieved by consistency-based diagnosis techniques. Based on the formal definition of consistency-based configuration we develop a framework suitable for diagnosing configuration knowledge bases. During the test phase of configurators, valid and invalid examples are used to test the correctness of the system. In case such examples lead to unintended results, debugging of the knowledge base is initiated. Starting from a clear definition of diagnosis in the configuration domain we develop an algorithm based on conflicts. Our framework is general enough for its adaptation to diagnosing customer requirements to identify unachievable conditions during configuration sessions.A prototype implementation using commercial constraint-based configurator libraries shows the feasibility of diagnosis within the tight time bounds of interactive debugging sessions. Finally, we discuss the usefulness of the outcomes of the diagnostic process in different scenarios.     

刻画基于模型的中心诊断*

虽然对基于模型的诊断存在一系列不同的逻辑定义,但所幸的是存在一个统一的抽象定义,它概括了以往的不同定义.在该定义基础上提出了基于模型的中心诊断的概念.通过刻画基于模型的中心诊断过程,论证了基于模型的中心诊断与本原蕴含/蕴含式的直接关系,从而将其理论结果与ATMS(assumption-based truth maintenance system)这类算法联系起来.进一步指出,对基于一致性中心诊断的刻画仅仅是文中所给出的刻画的一个特殊情形.     

Weak Generalized Closed World Assumption

Explicit representation of negative information in logic programs is not feasible in many applications such as deductive databases and artificial intelligence. Defining default rules which allow implicit inference of negated facts from positive information encoded in a logic program has been an attractive alternative to the explicit representation approach. There is, however, a difficulty associated with implicit default rules. Default rules such as the CWA and the GCWA, which closely model logical negation, are in general computationally intractable. This has led to the development of weaker definitions of negation such as the Negation-As-Failure (NF) and the Support-For-Negation (SN) rules which are computationally simpler. These are sound implementations of the CWA and the GCWA, respectively. In this paper, we define an alternative rule of negation based upon the fixpoint definition of the GCWA. This rule, called the Weak Generalized Closed World Assumption (WGCWA), is a weaker definition of the GCWA that allows us to implement a sound negation rule, called the Negation-As-Finite-Failure (NAFF), similar to the NF-rule and less cumbersome than the SN-rule. We present three definitions of the NAFF. Two declarative definitions similar to those for the NF-rule and one procedural definition based on SLI-resolution.     

Modelling Problem-solving for an Educational System

Abstract

When constructing a system that presents students with problem-solving, the essential problem to be considered is the definition of the system's conceptual model of the problem-solving expertise. We study two possible approaches of the definition of this model: refining generic problem-solving models and modelling by data-abstraction from an observed expertise. We emphasise that these two approaches have opposite advantages. The former facilitates the definition of rational systematic problem-solving models, the latter facilitates the respect of the problem-solving pedagogic specificities of a particular domain. In order to help in the refinement of the model constructed by either method we claim that a paper-based model is not sufficient and advocate the use of prototyping as a means to support modelling. To allow this prototyping we need a high-level language that (1) allows a quick operationalisation of the model while not enforcing predefined conceptual primitives, and (2) allows a control of what problem-solving material is used according to both problem-solving and pedagogical issues, these two aspects not being mixed. We present an example of such a language, the Zola language, and how it tackles these objectives, with examples from a system (under construction) that aims at training students to linear programming techniques.