CoChat
Sign Up
Cited by 309Logic, Reasoning, and KnowledgeLogic, programming, and type systemsMulti-Agent Systems and Negotiation

Multi-shot ASP solving with clingo

Open access
GEBSER, MARTIN, KAMINSKI, ROLAND, KAUFMANN, BENJAMIN, SCHAUB, TORSTEN·2019·Theory and Practice of Logic Programming
DOI 10.1017/s1471068418000054
Open this paper in CoChat — free accountOpen PDF

Abstract

We introduce a new flexible paradigm of grounding and solving in Answer Set Programming (ASP), which we refer to as multi-shot ASP solving, and present its implementation in the ASP system clingo . Multi-shot ASP solving features grounding and solving processes that deal with continuously changing logic programs. In doing so, they remain operative and accommodate changes in a seamless way. For instance, such processes allow for advanced forms of search, as in optimization or theory solving, or interaction with an environment, as in robotics or query answering. Common to them is that the problem specification evolves during the reasoning process, either because data or constraints are added, deleted, or replaced. This evolutionary aspect adds another dimension to ASP since it brings about state changing operations. We address this issue by providing an operational semantics that characterizes grounding and solving processes in multi-shot ASP solving. This characterization provides a semantic account of grounder and solver states along with the operations manipulating them. The operative nature of multi-shot solving avoids redundancies in relaunching grounder and solver programs and benefits from the solver's learning capacities. clingo accomplishes this by complementing ASP's declarative input language with control capacities. On the declarative side, a new directive allows for structuring logic programs into named and parameterizable subprograms. The grounding and integration of these subprograms into the solving process is completely modular and fully controllable from the procedural side. To this end, clingo offers a new application programming interface that is conveniently accessible via scripting languages. By strictly separating logic and control, clingo also abolishes the need for dedicated systems for incremental and reactive reasoning, like iclingo and oclingo , respectively, and its flexibility goes well beyond the advanced yet still rigid solving processes of the latter.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1017/s1471068418000054

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • In the multi-shot cycle, a ground program is given to an ASP solver, yielding an answer set, whose processing leads to a (first-order) extension of the program; only this extension then needs grounding and adding to the running ASP instance, which means that the running solver may maintain learned conflicts.

    “The essence of the multi-shot cycle is that a ground program is given to an ASP solver, yielding an answer set, who's processing leads to a (first-order) extension of the program. Only this extension then needs grounding and adding to the running ASP instance, which means that the running solver may, for example, maintain learned conflicts.”

    From Learning programs by learning from failures (2021) · cites this paper as Gebser et al. 2019

    Split into 2 atoms — 1 confirmed, 1 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.

    Experimental — accuracy not yet measured

  • The idea of multi-shot solving is that state of the solving process for an ASP program can be saved to help solve modifications of that program.

    “The idea of multi-shot solving is that state of the solving process for an ASP program can be saved to help solve modifications of that program.”

    From Learning programs by learning from failures (2021) · cites this paper as Gebser et al. 2019

  • Using Clingo's multi-shot solving improves efficiency by maintaining state between the three stages.

    “To improve efficiency, we use Clingo's multi-shot solving (Gebser et al. 2019) to maintain state between the three stages.”

    From Learning programs by learning from failures (2021) · cites this paper as Gebser et al. 2019

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 36

  1. ABITEBOUL, S., HULL, R., AND VIANU, V. 1995. Foundations of Databases. Addison-Wesley.
  2. ABSEHER, M., BLIEM, B., CHARWAT, G., DUSBERGER, F., HECHER, M., AND WOLTRAN, S. 2014. The D-FLAT system for dynamic programming on tree decompositions. In Proceedings of the Fourteenth European Conference on Logics in Artificial Intelligence (JELIA'14), E. Fermé and J. Leite, Eds. Lecture Notes in Artificial Intelligence, vol. 8761. Springer-Verlag, 558-572.
  3. ALVIANO, M., FABER, W., AND GEBSER, M. 2015. Rewriting recursive aggregates in answer set program- ming: Back to monotonicity. Theory and Practice of Logic Programming 15, 4-5, 559-573. Available at http://arxiv.org/abs/1507.03923. · arXiv
  4. ANDRES, B., KAUFMANN, B., MATHEIS, O., AND SCHAUB, T. 2012. Unsatisfiability-based optimization in clasp. In Technical Communications of the Twenty-eighth International Conference on Logic Programming (ICLP'12), A. Dovier and V. Santos Costa, Eds. Vol. 17. Leibniz International Proceedings in Informatics (LIPIcs), 212-221.
  5. BALDUCCINI, M. AND JANHUNEN, T., Eds. 2017. Proceedings of the Fourteenth International Confer- ence on Logic Programming and Nonmonotonic Reasoning (LPNMR'17). Lecture Notes in Artificial Intelligence, vol. 10377. Springer-Verlag.
  6. BARAL, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press.
  7. BREWKA, G., DELGRANDE, J., ROMERO, J., AND SCHAUB, T. 2015a. asprin: Customizing answer set preferences without a headache. In Proceedings of the Twenty-Ninth National Conference on Artificial Intelligence (AAAI'15), B. Bonet and S. Koenig, Eds. AAAI Press, 1467-1474.
  8. BREWKA, G., EITER, T., AND MCILRAITH, S., Eds. 2012. Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning (KR'12). AAAI Press.
  9. CABALAR, P. AND SON, T., Eds. 2013. Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13). Lecture Notes in Artificial Intelligence, vol. 8148. Springer-Verlag.
  10. CALIMERI, F., COZZA, S., AND IANNI, G. 2007. External sources of knowledge and value invention in logic programming. Annals of Mathematics and Artificial Intelligence 50, 3-4, 333-361.
  11. CALIMERI, F., IANNI, G., AND TRUSZCZY ŃSKI, M., Eds. 2015. Proceedings of the Thirteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'15). Lecture Notes in Artificial Intelligence, vol. 9345. Springer-Verlag.
  12. DE CAT, B., BOGAERTS, B., BRUYNOOGHE, M., AND DENECKER, M. 2014. Predicate logic as a modelling language: The IDP system. CoRR abs/1401.6312. · arXiv
  13. DE MOURA, L. AND BJØRNER, N. 2008. Z3: An efficient SMT solver. In Proceedings of the Fourteenth In- ternational Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'08), C. Ramakrishnan and J. Rehof, Eds. Lecture Notes in Computer Science, vol. 4963. Springer-Verlag, 337-340.
  14. DE POOTER, S., WITTOCX, J., AND DENECKER, M. 2013. A prototype of a knowledge-based programming environment. In Proceedings of the Nineteenth International Conference on Applications of Declarative Programming and Knowledge Management (INAP'11) and the Twenty-fifth Workshop on Logic Program- ming (WLP'11), H. Tompits, S. Abreu, J. Oetsch, J. Pührer, D. Seipel, M. Umeda, and A. Wolf, Eds. Lecture Notes in Computer Science, vol. 7773. Springer-Verlag, 279-286.
  15. DELGRANDE, J. AND FABER, W., Eds. 2011. Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'11). Lecture Notes in Artificial Intelligence, vol. 6645. Springer-Verlag.
  16. DELGRANDE, J., SCHAUB, T., TOMPITS, H., AND WOLTRAN, S. 2008. Belief revision of logic programs under answer set semantics. In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR'08), G. Brewka and J. Lang, Eds. AAAI Press, 411-421.
  17. DELGRANDE, J., SCHAUB, T., TOMPITS, H., AND WOLTRAN, S. 2009. Merging logic programs under answer set semantics. In Proceedings of the Twenty-fifth International Conference on Logic Programming (ICLP'09), P. Hill and D. Warren, Eds. Lecture Notes in Computer Science, vol. 5649. Springer-Verlag, 160-174.
  18. DODARO, C., GASTEIGER, P., LEONE, N., MUSITSCH, B., RICCA, F., AND SCHEKOTIHIN, K. 2016. Driving CDCL search. CoRR abs/1611.05190. · arXiv
  19. DODARO, C., RICCA, F., AND SCH ÜLLER, P. 2016. External propagators in wasp: Preliminary report. In Proceedings of the Twenty-third International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA'16). Vol. 1745. CEUR Workshop Proceedings, 1-9.
  20. E ÉN, N. AND S ÖRENSSON, N. 2004. An extensible SAT-solver. In Proceedings of the Sixth International Conference on Theory and Applications of Satisfiability Testing (SAT'03), E. Giunchiglia and A. Tacchella, Eds. Lecture Notes in Computer Science, vol. 2919. Springer-Verlag, 502-518.
  21. FUSC À, D., GERMANO, S., ZANGARI, J., ANASTASIO, M., CALIMERI, F., AND PERRI, S. 2016. A framework for easing the development of applications embedding answer set programming. In Proceedings of the Eighteenth International Symposium on Principles and Practice of Declarative Programming (PPDP'16), J. Cheney and G. Vidal, Eds. ACM Press, 38-49.
  22. GEBSER, M., HARRISON, A., KAMINSKI, R., LIFSCHITZ, V., AND SCHAUB, T. 2015. Abstract Gringo. Theory and Practice of Logic Programming 15, 4-5, 449-463. Available at http://arxiv.org/ abs/1507.06576. · arXiv
  23. GEBSER, M., KAMINSKI, R., KAUFMANN, B., LINDAUER, M., OSTROWSKI, M., ROMERO, J., SCHAUB, T., AND THIELE, S. 2015. Potassco User Guide, Second edition ed. University of Potsdam.
  24. GEBSER, M., KAMINSKI, R., KAUFMANN, B., OSTROWSKI, M., SCHAUB, T., AND THIELE, S. 2008. Engineering an incremental ASP solver. In Proceedings of the Twenty-fourth International Conference on Logic Programming (ICLP'08), M. Garcia de la Banda and E. Pontelli, Eds. Lecture Notes in Computer Science, vol. 5366. Springer-Verlag, 190-205.
  25. GEBSER, M., KAMINSKI, R., KAUFMANN, B., OSTROWSKI, M., SCHAUB, T., AND WANKO, P. 2016. Theory solving made easy with clingo 5. In Technical Communications of the Thirty-second International Conference on Logic Programming (ICLP'16), M. Carro and A. King, Eds. Vol. 52. Open Access Series in Informatics (OASIcs), 2:1-2:15.
  26. GEBSER, M., KAMINSKI, R., KAUFMANN, B., AND SCHAUB, T. 2014. Clingo = ASP + control: Preliminary report. In Technical Communications of the Thirtieth International Conference on Logic Programming (ICLP'14), M. Leuschel and T. Schrijvers, Eds. Theory and Practice of Logic Programming, Online Supplement, vol. 14(4-5). Available at http://arxiv.org/abs/1405.3694v1. · arXiv
  27. GEBSER, M., KAMINSKI, R., OBERMEIER, P., AND SCHAUB, T. 2015. Ricochet robots reloaded: A case-study in multi-shot ASP solving. In Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation: Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday, T. Eiter, H. Strass, M. Truszczyński, and S. Woltran, Eds. Lecture Notes in Artificial Intelligence, vol. 9060. Springer-Verlag, 17-32.
  28. GEBSER, M., KAUFMANN, B., OTERO, R., ROMERO, J., SCHAUB, T., AND WANKO, P. 2013. Domain- specific heuristics in answer set programming. In Proceedings of the Twenty-Seventh National Conference on Artificial Intelligence (AAAI'13), M. desJardins and M. Littman, Eds. AAAI Press, 350-356.
  29. GEBSER, M., KAUFMANN, B., AND SCHAUB, T. 2013. Advanced conflict-driven disjunctive answer set solving. In Proceedings of the Twenty-third International Joint Conference on Artificial Intelligence (IJCAI'13), F. Rossi, Ed. IJCAI/AAAI Press, 912-918.
  30. GEBSER, M., OBERMEIER, P., AND SCHAUB, T. 2013. A system for interactive query answering with answer set programming. In Proceedings of the Sixth Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP'13), M. Fink and Y. Lierler, Eds. Vol. abs/1312.6143. CoRR. · arXiv
  31. GELFOND, M. AND LIFSCHITZ, V. 1988. The stable model semantics for logic programming. In Proceedings of the Fifth International Conference and Symposium of Logic Programming (ICLP'88), R. Kowalski and K. Bowen, Eds. MIT Press, 1070-1080.
  32. KAMINSKI, R., SCHAUB, T., AND WANKO, P. 2017. A tutorial on hybrid answer set solving with clingo. In Proceedings of the Thirteenth International Summer School of the Reasoning Web, G. Ianni, D. Lembo, L. Bertossi, W. Faber, B. Glimm, G. Gottlob, and S. Staab, Eds. Lecture Notes in Computer Science, vol. 10370. Springer-Verlag, 167-203.
  33. LEONE, N., PFEIFER, G., FABER, W., EITER, T., GOTTLOB, G., PERRI, S., AND SCARCELLO, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7, 3, 499-562.
  34. LIFSCHITZ, V. AND TURNER, H. 1994. Splitting a logic program. In Proceedings of the Eleventh International Conference on Logic Programming. MIT Press, 23-37.
  35. NIEUWENHUIS, R., OLIVERAS, A., AND TINELLI, C. 2006. Solving SAT and SAT modulo theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T). Journal of the ACM 53, 6, 937-977.
  36. OIKARINEN, E. AND JANHUNEN, T. 2006. Modular equivalence for normal logic programs. In Proceedings of the Seventeenth European Conference on Artificial Intelligence (ECAI'06), G. Brewka, S. Coradeschi, A. Perini, and P. Traverso, Eds. IOS Press, 412-416.

Cited by

Sorted by citations

Authors
GEBSER, M., KAMINSKI, R., KAUFMANN, B., & SCHAUB, T.
Affiliations
  • University of Potsdam (DE)
  • Institut national de recherche en sciences et technologies du numérique (FR)
ORCID
Venue
Theory and Practice of Logic Programming
Publisher
Cambridge University Press (CUP)
Published
2018-07-10
Volume
19
Issue
1
Pages
27-82
ISSN
  • 1471-0684 (ISSN-L)
  • 1475-3081
DOI
10.1017/s1471068418000054
OpenAlex
W2619622334
Cited by
309
References
0
Citations by year
2026: 41 · 2025: 48 · 2024: 39 · 2023: 65 · 2022: 41 · 2021: 29 · 2020: 23 · 2019: 15 · 2018: 7 · 2017: 1
FWCI
10.41
Type
journal article
Language
en
Open access
Licence
Locations
  • Theory and Practice of Logic Programming (publishedVersion, other-oa)
  • arXiv (Cornell University) (submittedVersion)
  • publish.UP (University of Potsdam) (submittedVersion)
  • arXiv (Cornell University)
Funders
Deutsche Forschungsgemeinschaft (SCHA 550/9)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
  • Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Multi-Agent Systems and Negotiation
Keywords
answer set programming, clingo, incremental reasoning, operational semantics, optimization, query answering

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review