Abstract
Fuzzy Answer Set Programming (FASP) extends classical Answer Set Programming (ASP) by allowing truth values to range within the continuous interval [0, 1]. While this provides flexibility for handling imprecise information, it often results in models that are "too vague," with truth values gravitating toward 0.5. This paper introduces the concept of Minimal Undefinedness, a framework for selecting the most "crisp" answer sets by minimizing the distance of truth values from the classical bounds of 0 and 1. We propose and evaluate several iterative search algorithms—Binary Search, Progression Search, and $\epsilon$-improvement—implemented using SMT solvers. Our results indicate that Binary Search is the most robust and efficient method for finding these optimal, less ambiguous solutions.
Introduction
Fuzzy Answer Set Programming (FASP) is a powerful paradigm that merges the non-monotonic reasoning of ASP with the ability of fuzzy logic to model uncertainty. However, the continuous nature of FASP semantics often leads to an uncountable number of answer sets, many of which assign truth values near 0.5. In many practical applications, such as fuzzy control systems, these "undefined" or ambiguous values are undesirable.
The core challenge addressed in this research is the lack of a "minimal undefinedness" principle in standard FASP. Without such a principle, solvers may return models that are logically valid but practically useless due to their vagueness. By formalizing 0.5 as the state of maximum undefinedness, we can define a preference for models that maximize information content by staying as close to classical truth values (0 or 1) as possible.
Methodology
To address the issue of vagueness, we introduce Minimal Undefinedness Fuzzy Answer Sets (MUFAS). The approach relies on a measure of undefinedness, $U_D$, defined for any atom as $\min(truth, 1-truth)$. The total undefinedness of a model is the sum of these values across all atoms.
We developed three iterative algorithms to find models that minimize $U_D$, leveraging the capabilities of SMT solvers:
- Binary Search: This algorithm bisects the range of possible undefinedness values to rapidly converge on the minimum.
- Progression Search: This method iteratively tightens the undefinedness bound using an increasing step size.
- $\epsilon$-improvement: A linear approach that seeks a model marginally better than the current one until no further improvement is possible.
These algorithms were implemented by extending the FASP2SMT system, using the Z3 solver as the backend. A specific summation constraint was added to Z3 to enforce the undefinedness bounds during the search process.
Results and Evaluation
The proposed algorithms were evaluated using satisfiable instances of the Hamiltonian Cycle problem, a standard benchmark in the ASP community. We compared the performance of our custom search strategies against Z3's native (and then-experimental) MINIMIZE instruction.
As shown in the experimental results, Binary Search significantly outperformed the other methods. At a precision threshold of $\epsilon = 0.1$, Binary Search solved 100% of the test instances. While performance naturally declined as the required precision increased (e.g., to $\epsilon = 0.001$), Binary Search remained the most resilient strategy. Notably, the native Z3 optimization (min.) performed poorly, solving only 6% of instances at $\epsilon = 0.1$ and failing completely at higher precisions. This underscores the effectiveness of domain-specific search strategies over general-purpose optimization tools in this context.
Conclusion
The introduction of Minimal Undefinedness provides a principled way to refine FASP solutions, ensuring they are as informative and "crisp" as possible. Our findings highlight that Binary Search, when integrated with SMT solvers, offers a highly effective path toward solving these optimization problems. Future work will explore alternative measures of undefinedness and the application of these techniques to complex abduction tasks in fuzzy circuits.
Summary updated