Abstract
Answer Set Programming (ASP) is a powerful paradigm for solving combinatorial search problems, yet it remains fragile when faced with incoherent programs—those that return no answer sets due to logical cycles. Paracoherent semantics, specifically semi-stable and semi-equilibrium models, have been proposed to mitigate this by providing meaningful "safe mode" results. However, their practical application has been hindered by a lack of efficient computation methods. This paper introduces and evaluates four novel algorithmic strategies integrated into the WASP solver. Our results show that paracoherent reasoning is now practical, with the "Minimize" and "Split" algorithms significantly outperforming baseline approaches on standard benchmarks.
Introduction
ASP is widely used for hard search problems like scheduling and diagnosis. However, if a program contains cyclic default negation (e.g., a :- not b. b :- not a.), it may become incoherent, returning no solution. In critical applications like debugging or inconsistency-tolerant query answering, this "all-or-nothing" behavior is unacceptable. Paracoherent semantics address this by minimizing the "gap"—the set of atoms believed to be true but not formally provable—ensuring a solution is always provided.
Algorithmic Strategies
The authors propose five strategies to compute these models by treating the problem as a subset-minimization of the logical gap:
- Filtering (Baseline): A naive approach that enumerates all answer sets and filters for those with minimal gaps.
- Guess & Check: Uses a satellite solver to verify if a candidate answer set can be improved upon.
- Minimize: An iterative strategy that adds constraints to the solver to force successively smaller gaps.
- Split: A "divide and conquer" method that branches specifically on atoms involved in logical gaps.
- Weak Constraints: Utilizes native solver optimization features to penalize the presence of gap atoms.
These strategies were implemented in WASP, a state-of-the-art ASP solver.
Performance Analysis
The algorithms were tested on 157 instances from the 5th ASP Competition, focusing on domains like minimal diagnosis (MinDiagn) and spatial reasoning (QualSpatReas).
As shown in Table 1, the Minimize and Split algorithms are the most robust, solving 78 out of 157 instances for semi-stable semantics, whereas the baseline Filtering approach failed to solve any. For the more complex semi-equilibrium semantics, the Split algorithm showed a slight performance advantage over Minimize.
Grounding and Scalability
A significant challenge in paracoherent reasoning is the epistemic transformation required to label "gap atoms." This process can lead to a massive increase in the size of the logic program during the grounding phase.
Table 2 illustrates this "grounding explosion." For the StableMarriage problem, the transformation resulted in over 110 million rules, causing the system to exceed memory limits before the search could even begin. This highlights that the primary bottleneck for paracoherent reasoning is often the size of the transformed program rather than the search complexity itself.
Conclusion
This work demonstrates that paracoherent answer sets can be computed efficiently using optimization-based strategies like Minimize and Split. By integrating these into the WASP solver, the authors have made paracoherent reasoning a viable tool for real-world AI applications. Future work will focus on supporting more complex ASP features (like aggregates) and developing more compact transformations to mitigate grounding overhead.
Summary updated