We present the CIFF proof procedure for abductive logic programming with constraints, and we prove its correctness. CIFF is an extension of the IFF proof procedure for abductive logic programming, relaxing the original restrictions over variable quantification (allowedness conditions) and incorporating a constraint solver to deal with numerical constraints as in constraint logic programming. Finally, we describe the CIFF system, comparing it with state of the art abductive systems and answer set solvers and showing how to use it to program some applications. (To appear in Theory and Practice of Logic Programming - TPLP).
In this performance comparison we restricted our attention to three systems: the @cite_16 and two state-of-the-art answer set solvers, namely the DLV system @cite_9 and SMODELS @cite_11 .
@cite_9 @cite_16 @cite_11
2004414305 1511336005 1551250655 1577827016
We propose a new translation from normal logic programs with constraints under the answer set semantics to propositional logic. Given a normal logic program, we show that by adding, for each loop in the program, a corresponding loop formula to the program's completion, we obtain a one-to-one correspondence between the answer sets of the program and the models of the resulting propositional theory. In the worst case, there may be an exponential number of loops in a logic program. To address this problem, we propose an approach that adds loop formulas a few at a time, selectively. Based on these results, we implement a system called ASSAT(X), depending on the SAT solver X used, for computing one answer set of a normal logic program with constraints. We test the system on a variety of benchmarks including the graph coloring, the blocks world planning, and Hamiltonian Circuit domains. Our experimental results show that in these domains, for the task of generating one answer set of a normal logic program, our system has a clear edge over the state-of-art answer set programming systems Smodels and DLV. In “answer set programming”[5,7] solutions to a problem are represented by answer sets (known also as stable models), and not by answer substitutions produced in response to a query, as in conventional logic programming. Instead of Prolog, answer set programming uses software systems capable of computing answer sets. Four such systems were demonstrated at the Workshop on Logic- Based AI held in June of 1999 in Washington, DC: dlv1, smodels,2, DeReS3 and ccalc4. In this dissertation we show how conflict clause learning, a technique that has been very useful in improving the efficiency of Boolean logic satisfiability search, can be adapted to speed up dramatically the search for models of answer set programs. Answer set programming is a knowledge representation paradigm related to the areas of logic programming and nonmonotonic reasoning. Many of the applications of answer set programming come from the areas of artificial intelligence-related diagnosis and planning. The problem of finding an answer set for a normal or extended logic program is NP-hard. Current complete answer set solvers are patterned after the Davis-Putnam-Loveland-Logemann ( DPLL) algorithm for solving Boolean satisfiability (SAT) problems, but are adapted to the nonmonotonic semantics of answer set programming. Recent SAT solvers include improvements to the DPLL algorithm. Conflict clause learning has been particularly effective in this regard. A conflict clause represents a backtracking solver's analysis of why a conflict occurred. This analysis can be used to further prune the search space and to direct the search heuristic. The use of such clauses has improved significantly the efficiency of satisfiability solvers over the past few years, especially on structured problems arising from applications. In this dissertation we describe how we have adapted conflict clause techniques for use in the answer set solver Smodels. We experimentally compare the performance of the resulting program, Smodelscc, to that of the original Smodels program. Our tests show dramatic speedups for Smodelscc on a wide range of problems. We also compare the performance of Smodelscc with that of two other recent answer set solvers, ASSAT and Cmodels-2. ASSAT and Cmodels-2 directly call Boolean satisfiability solvers in order to search for answer sets. On so-called “non-tight” problems, Smodelscc showed substantially better performance than these solvers. The performance advantage that Smodels cc enjoys on non-tight problems is due to the unfounded set test that Smodelscc inherits from the Smodels solver, and the fact that this test is executed frequently throughout the program's search for answer sets. The Smodels system is one of the state-of-the-art implementations of stable model computation for normal logic programs. In order to enable more realistic applications, the basic modeling language of normal programs has been extended with new constructs including cardinality and weight constraints and corresponding implementation techniques have been developed. This paper summarizes the extensions that have been included in the system, demonstrates their use, provides basic application methodology, illustrates the current level of performance of the system, and compares it to state-of-the-art satisfiability checkers.