Functional Stable Model Semantics and Answer Set Programming Modulo Theories

Michael Bartholomew, Joohyung LeeIJCAI 2013

TL;DR

This paper introduces ASPMT, a framework that tightly integrates Answer Set Programming (ASP) with Satisfiability Modulo Theories (SMT). ASPMT allows for "intensional" functions, which are defined by other functions and predicates, enabling more expressive modeling. A key contribution is showing that a fragment of ASPMT, called "tight" programs, can be translated into SMT instances, allowing efficient computation using existing SMT solvers.

What Problem Does This Paper Address?

Traditional Answer Set Programming (ASP) relies on Herbrand models, where function interpretations are pre-defined. This limits the representation of non-Boolean fluents, often requiring indirect encoding through predicates, which can lead to computational bottlenecks due to large grounding sets. Two recent lines of research have emerged to address these limitations: one focuses on enriching ASP with "intensional" functions (whose values are defined by other functions/predicates), and the other on improving computational efficiency by integrating ASP with paradigms like SMT. This paper bridges these two areas by proposing ASPMT, a framework that combines the expressiveness of intensional functions with the computational efficiency of SMT.

Methods

The paper builds upon the "functional stable model semantics" (FSM) developed by Bartholomew and Lee. It reformulates this semantics in terms of grounding and reduct for infinitary ground formulas, which is a more familiar approach for those acquainted with ASP. The core contribution is the definition of ASPMT as a special case of FSM. Crucially, the authors identify a syntactic class of ASPMT programs, termed "tight" programs, that can be translated into SMT instances. This translation allows existing SMT solvers to be used for computing ASPMT models. The paper also discusses how existing approaches like Clingcon programs and ASP(LC) programs can be viewed as special cases of ASPMT.

Datasets

Not discussed in the paper. The paper uses examples and experimental results from domains like the "Leaking Bucket" and "Gears World" to illustrate its concepts and evaluate performance.

Key Insights and Ideas

  • Intensional Functions for Expressiveness: The ability to define functions intensionally, rather than having them pre-defined, significantly enhances the modeling power of ASP, allowing for more natural representation of complex phenomena.
  • Bridging ASP and SMT: ASPMT offers a unified framework that leverages the strengths of both ASP (nonmonotonic reasoning) and SMT (efficient handling of theories and functions).
  • "Tightness" as a Key to SMT Translation: The concept of "tightness" in ASPMT programs is crucial. It ensures that these programs can be effectively translated into SMT instances, enabling the use of powerful SMT solvers for computation.
  • SMT Solvers Overcome Grounding Bottlenecks: Experimental results demonstrate that SMT solvers can handle ASPMT problems much more efficiently than traditional ASP solvers, particularly as problem complexity (e.g., instance size) increases, by avoiding the grounding bottleneck.
  • Generalization of Existing Frameworks: ASPMT provides a more general framework that encompasses and unifies several prior approaches to integrating ASP with constraint solving and theories.

Key Results

The paper demonstrates that "tight" ASPMT programs can be translated into SMT instances. Experimental results on the "Leaking Bucket" and "Gears World" domains show that SMT solvers (iSAT and z3) significantly outperform traditional ASP solvers (CLINGO) in terms of execution time and scalability as the instance size increases. For instance, in the Leaking Bucket experiment, CLINGO's execution time increases quadratically with instance size, while iSAT's increases linearly, and z3 also shows much better performance. This highlights the practical advantage of using SMT for solving ASPMT problems.

Limitations and Future Work

The paper acknowledges that the translation to SMT is currently limited to a fragment of ASPMT ("tight" programs). Future work could explore extending this translation to more general ASPMT programs. The authors also suggest that the relationship between ASPMT and SMT, similar to the well-established relationship between ASP and SAT, could lead to the transfer of many theoretical results and techniques from ASP to ASPMT. Further research could also investigate the practical implications and applications of ASPMT in various knowledge representation and reasoning tasks.

Summary updated

BibTeX
@inproceedings{bartholomew2013functional,
  author = {Michael Bartholomew and Joohyung Lee},
  title = {{Functional Stable Model Semantics and Answer Set Programming Modulo Theories}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2013},
}

Loading related content...

Figure