Skip to main navigation Skip to search Skip to main content

ApproxASP - a Scalable Approximate Answer Set Counter

  • Mohimenul Kabir
  • , Flavio O. Everardo
  • , Ankit K. Shukla
  • , Markus Hecher
  • , Johannes Klaus Fichte
  • , Kuldeep S. Meel

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

Abstract

Answer Set Programming (ASP) is a framework in artificial intelligence and knowledge representation for declarative modeling and problem solving. Modern ASP solvers focus on the computation or enumeration of answer sets. However, a variety of probabilistic applications in reasoning or logic programming require counting answer sets. While counting can be done by enumeration, simple enumeration becomes immediately infeasible if the number of solutions is high. On the other hand, approaches to exact counting are of high worst-case complexity. In fact, in propositional model counting, exact counting becomes impractical. In this work, we present a scalable approach to approximate counting for ASP. Our approach is based on systematically adding parity (XOR) constraints to ASP programs, which divide the search space. We prove that adding random XOR constraints partitions the answer sets of an ASP program. In practice, we use a Gaussian elimination-based approach by lifting ideas from SAT to ASP and integrate it into a state of the art ASP solver, which we call ApproxASP. Finally, our experimental evaluation shows the scalability of our approach over existing ASP systems.

Original languageEnglish
Title of host publication36th AAAI Conference on Artificial Intelligence (AAAI-22)
EditorsVasant Honavar, Matthijs Spaan
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages5755-5764
Number of pages10
Volume36
Edition5
ISBN (Electronic)1577358767, 9781577358763
DOIs
Publication statusPublished - 2022
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 2022 - Online, United States of America
Duration: 22 Feb 2022 → 1 Mar 2022
Conference number: 36th
https://aaai-2022.virtualchair.net/index.html (Website)
https://aaai.org/conference/aaai/aaai-22/
https://ojs.aaai.org/index.php/AAAI/issue/view/510 (Proceedings)

Conference

ConferenceAAAI Conference on Artificial Intelligence 2022
Abbreviated titleAAAI 2022
Country/TerritoryUnited States of America
CityOnline
Period22/02/22 → 1/03/22
Internet address

Keywords

  • Knowledge Representation And Reasoning (KRR)
  • Constraint Satisfaction And Optimization (CSO)

Cite this