Possibilistic Answer Set Programming Revisited

Kim Bauters, Steven Schockaert, Martine De Cock, Dirk VermeirUAI 2010 · OpenReview

Abstract

Possibilistic answer set programming (PASP) extends answer set programming (ASP) by attaching to each rule a degree of certainty. While such an extension is important from an application point of view, existing semantics are not well-motivated, and do not always yield intuitive results. To develop a more suitable semantics, we first introduce a characterization of answer sets of classical ASP programs in terms of possibilistic logic where an ASP program specifies a set of constraints on possibility distributions. This characterization is then naturally generalized to define answer sets of PASP programs. We furthermore provide a syntactic counterpart, leading to a possibilistic generalization of the well-known Gelfond-Lifschitz reduct, and we show how our framework can readily be implemented using standard ASP solvers.

Introduction

Answer Set Programming (ASP) is a powerful tool for solving complex combinatorial problems, but it traditionally operates in a world of absolute certainty. Possibilistic Logic (PL) was introduced to handle "partial ignorance"—situations where facts are known with varying degrees of certainty. However, previous attempts to combine these into Possibilistic Answer Set Programming (PASP) encountered significant issues with "negation-as-failure" (NAF), often producing counterintuitive results where minor uncertainties could completely collapse logical conclusions. This paper addresses these frictions by providing a robust mathematical foundation for reasoning with rules that carry degrees of certainty.

The Motivating "Concert" Example

The primary issue with earlier PASP semantics was an "all-or-nothing" behavior regarding uncertainty. Consider a scenario where a "long drive" is contingent on a booked concert not being canceled.

Figure 1: A PASP program representing the concert booking scenario.

In this example, we are 100% certain the concert is booked (Rule 1). However, there is a 20% certainty (perhaps a rumor) that the concert is canceled (Rule 3). Under old PASP semantics, that 20% rumor would completely destroy the certainty about the long drive, leaving the user with 0% certainty. Intuitively, however, one should still be approximately 80% certain of the drive. The authors' new semantics fix this behavior, allowing certainty to degrade gracefully rather than collapse.

Methodology

The authors move away from simply weighting classical answer sets and instead rebuild the semantics from the ground up using Possibility Theory.

  1. Semantic Characterization: They define an ASP program as a set of constraints on a possibility distribution ($\pi$). This distribution maps every possible world to a value between 0 and 1, representing its plausibility.
  2. The New "Not": They redefine not a to mean "it cannot be established that $a$ is certain." This allows the certainty of a conclusion to be influenced by the degree of certainty of its negation.
  3. Possibilistic Reduct: The paper introduces a syntactic counterpart to the famous Gelfond-Lifschitz reduct. This new version transforms a possibilistic program into a "definite" program by adjusting rule weights based on a candidate valuation.
  4. Simulation via Classical ASP: To ensure practical utility, the authors demonstrate that a PASP program can be simulated by a standard ASP program. By discretizing certainty levels and creating multiple versions of each atom (e.g., atom_0.8, atom_0.6), the framework can be implemented using off-the-shelf solvers like clingo or DLV.

Key Insights and Results

  • Link to Possibilistic Logic: The authors prove that ASP is essentially a specific way of constraining possibility distributions. This bridge allows the use of the "least specific" distribution to find the most logical answer sets.
  • Handling Paradoxes: The framework is more robust in handling "unstable" logic. For example, the Liar Paradox (a :- not a), which has no answer set in classical ASP, yields a unique answer set with a certainty of 0.5 in this framework.
  • Practical Implementation: The syntactic-semantic equivalence ensures that the new reduct method matches the possibility-distribution definition, and the simulation method allows for high-performance execution without specialized new solvers.

Limitations and Future Work

While the simulation method is practical, it requires choosing a finite set of certainty levels (discretization), which may not capture truly continuous uncertainty. Additionally, the number of rules in the simulated program grows linearly with the number of certainty levels, potentially impacting performance on very large-scale problems. Future work may involve extending this approach to "disjunctive" programs, where rules have multiple possible heads.

Summary updated

Abstract

Possibilistic answer set programming (PASP) extends answer set programming (ASP) by attaching to each rule a degree of certainty. While such an extension is important from an application point of view, existing semantics are not well-motivated, and do not always yield intuitive results. To develop a more suitable semantics, we first introduce a characterization of answer sets of classical ASP programs in terms of possibilistic logic where an ASP program specifies a set of constraints on possibility distributions. This characterization is then naturally generalized to define answer sets of PASP programs. We furthermore provide a syntactic counterpart, leading to a possibilistic generalization of the well-known Gelfond-Lifschitz reduct, and we show how our framework can readily be implemented using standard ASP solvers.
BibTeX
@inproceedings{bauters2010possibilistic,
  author = {Kim Bauters and Steven Schockaert and Martine De Cock and Dirk Vermeir},
  title = {{Possibilistic Answer Set Programming Revisited}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2010},
  url = {https://openreview.net/forum?id=-JVmFVGbhf},
}
Figure