We study the framework of abductive logic programming extended with integrity constraints. For this framework, we introduce a new measure of the simplicity of an explanation based on its degree of arbitrariness : the more arbitrary the explanation, the less appealing it is, with explanations having no arbitrariness — they are called constrained — being the preferred ones. In the paper, we study basic properties of constrained explanations. For the case when programs in abductive theories are stratified we establish results providing a detailed picture of the complexity of the problem to decide whether constrained explanations exist.
Abduction was introduced to artificial intelligence in early 1970s by Harry Pople Jr. , where it is now commonly understood as the @cite_3 . Over the years several criteria have been proposed to identify the preferred (best) explanations, all rooted in the Occam's razor parsimony principle. The most commonly considered one is subset-minimality @cite_2 @cite_20 @cite_6 . A more restrictive condition of minimum cardinality has also been broadly studied @cite_8 . The abduction reasoning formalism we study in the paper uses logic programs to represent background knowledge in abductive theories. It is referred to as @cite_10 @cite_15 @cite_17 . Abductive explanations which allow the removal of hypotheses are first introduced by Inoue and Sakama . The importance of abductive logic programming to knowledge representation was argued by Denecker and Schreye . It was applied in diagnosis @cite_21 , planning @cite_7 @cite_13 , natural language understanding @cite_11 , and case-based reasoning @cite_9 . Denecker and Kakas provide a comprehensive survey of the area.
@cite_13 @cite_11 @cite_7 @cite_8 @cite_9 @cite_21 @cite_6 @cite_3 @cite_2 @cite_15 @cite_10 @cite_20 @cite_17
2487701457 2063499502 2041428960 1540899940 2133291246 1546644035 2174466192 1509180139 1967802770 105821165
Abstract We investigate the relationship between various alternative semantics for logic programming, viz. the stable model semantics of Gelfond and Lifschitz (1988), the supported model semantics as developed by Apt, Blair and Walker (1988), autoepistemic translations (cf. Moore (1985)) of general logic programs and default translations of general logic programs, Reiter (1980). Contents: Abduction and Diagnostic Inference.- Computational Models for Diagnostic Problem Solving.- Basics of Parsimonious Covering Theory.- Probabilistic Causal Model.- Diagnostic Strategies in the Probabilistic Causal Model.- Causal Chaining.- Parallel Processing for Diagnostic Problem-Solving.- Conclusion.- Bibliography.- Index. Several artificial intelligence architectures and systems based on "deep" models of a domain have been proposed, in particular for the diagnostic task. These systems have several advantages over traditional knowledge based systems, but they have a main limitation in their computational complexity. One of the ways to face this problem is to rely on a knowledge compilation phase, which produces knowledge that can be used more effectively with respect to the original one. We show how a specific knowledge compilation approach can focus reasoning in abductive diagnosis, and, in particular, can improve the performances of AID, an abductive diagnosis system. The approach aims at focusing the overall diagnostic cycle in two interdependent ways: avoiding the generation of candidate solutions to be discarded a posteriori and integrating the generation of candidate solutions with discrimination among different candidates. Knowledge compilation is used off-line to produce operational (i.e., easily evaluated) conditions that embed the abductive reasoning strategy and are used in addition to the original model, with the goal of ruling out parts of the search space or focusing on parts of it. The conditions are useful to solve most cases using less time for computing the same solutions, yet preserving all the power of the model-based system for dealing with multiple faults and explaining the solutions. Experimental results showing the advantages of the approach are presented. Introduction 1. Conceptual analysis of abduction: what is abduction? 2. Knowledge-based systems and the science of AI: 3. Two RED systems 4. Generalizing the control strategy 5. More kinds of knowledge: TIPS and PATHEX LIVER TIPS 6. Better task analysis, better strategy 7. Computational complexity of abduction 8. Diagnostic systems MDX2 and QUADS 9. Practical abduction 10. Perception and language understanding Appendices. Abduction in Logic Programming started in the late 80s, early 90s, in an attempt to extend logic programming into a framework suitable for a variety of problems in Artificial Intelligence and other areas of Computer Science. This paper aims to chart out the main developments of the field over the last ten years and to take a critical view of these developments from several perspectives: logical, epistemological, computational and suitability to application. The paper attempts to expose some of the challenges and prospects for the further development of the field. Abstract There are two distinct formalizations for reasoning from observations to explanations, as in diagnostic tasks. The consistency based approach treats the task as a deductive one, in which the explanation is deduced from a background theory and a minimal set of abnormalities. The abductive method, on the other hand, treats explanations as sentences that, when added to the background theory, derive the observations. We show that there is a close connection between these two formalizations in the context of simple causal theories: domain theories in which a set of sentences are singled out as the explanatorily relevant causes of observations. There are two main results, which show that (with certain caveats) the consistency based approach can emulate abductive reasoning by adding closure axioms to a causal theory; and that abductive techniques can be used in place of the consistency based method in the domain of logic based diagnosis. It is especially interesting that in the latter case, the abductive techniques generate only relevant explanations, while diagnoses may have irrelevant elements.