We study abduction in First Order Horn logic theories where all atoms can be abduced and we are looking for preferred solutions with respect to three objective functions: cardinality minimality, coherence, and weighted abduction. We represent this reasoning problem in Answer Set Programming (ASP), in order to obtain a flexible framework for experimenting with global constraints and objective functions, and to test the boundaries of what is possible with ASP. Realizing this problem in ASP is challenging as it requires value invention and equivalence between certain constants, because the Unique Names Assumption does not hold in general. To permit reasoning in cyclic theories, we formally describe fine-grained variations of limiting Skolemization. We identify term equivalence as a main instantiation bottleneck, and improve the efficiency of our approach with on-demand constraints that were used to eliminate the same bottleneck in state-of-the-art solvers. We evaluate our approach experimentally on the ACCEL benchmark for plan recognition in Natural Language Understanding. Our encodings are publicly available, modular, and our approach is more efficient than state-of-the-art solvers on the ACCEL benchmark.
In an acyclic theory, our reasoning problem is related to non-recursive negation-free Datalog theories and non-recursive logic programming with equality, which has been studied (although not with respect to abductive reasoning) in @cite_15 .
@cite_15
1801368039 1586012806 2078139775 1488364561
To explain observations from nonmonotonic background theories, one often needs removal of some hypotheses as well as addition of other hypotheses. Moreover, some observations should not be explained, while some are to be explained. In order to formalize these situations, extended abduction was introduced by Inoue and Sakama (1995) to generalize traditional abduction in the sense that it can compute negative explanations by removing hypotheses and antidexplanations to unexplain negative observations. In this paper, we propose a computational mechanism for extended abduction. When a background theory is written in a normal logic program, we introduce its transaction program for computing extended abduction. A transaction program is a set of nonddeterministic production rules that declaratively specify addition and deletion of abductive hypotheses. Abductive explanations are then computed by the fixpoint of a transaction program using a bottomdup model generation procedure. The correctness of the proposed procedure is shown for the class of acyclic covered abductive logic programs. In the context of deductive databases, a transaction program provides a declarative specification of database update. We provide a simple formulation of a framework where three main extensions of logic programming for non-monotonic reasoning are treated uniformly: Negation-by-default, explicit negation and abduction. The resulting semantics is purely model-theoretic and gives meaning to any consistent abductive logic program. Moreover, it embeds and generalises existing semantics which deal with negation and abduction separately. The abductive framework is equipped with a correct top-down proof procedure. Abstract This paper presents the framework of Abductive Constraint Logic Programming (ACLP), which integrates Abductive Logic Programming (ALP) and Constraint Logic Programming (CLP). In ACLP, the task of abduction is supported and enhanced by its non-trivial integration with constraint solving. This integration of constraint solving into abductive reasoning facilitates a general form of constructive abduction and enables the application of abduction to computationally demanding problems. The paper studies the formal declarative and operational semantics of the ACLP framework together with its application to various problems. The general characteristics of the computation of ACLP and of its application to problems are also discussed. Empirical results based on an implementation of the ACLP framework on top of the CLP language of ECLiPSe show that ACLP is computationally viable, with performance comparable to the underlying CLP framework on which it is built. In addition, our experiments show the natural ability for ACLP to accommodate easily and in a robust way new or changing requirements of the original problem. ACLP thus combines the advantages of modularity and flexibility of the high-level representation afforded by abduction together with the computational effectiveness of low-level specialised constraint solving. This paper presents a new system, called the A- System, performing abductive reasoning within the framework of Abductive Logic Programming. It is based on a hybrid computational model that implements the abductive search in terms of two tightly coupled processes: a reduction process of the highlevel logical representation to a lower-level constraint store and a lower-level constraint solving process. A set of initial "proof of principle" experiments demonstrate the versatility of the approach stemming from its declarative representation of problems and the good underlying computational behaviour of the system. The approach offers a general methodology of declarative problem solving in AI where an incremental and modular refinement of the high-level representation with extra domain knowledge can improve and scale the computational performance of the framework.